akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define index_of(as, x) distance(as.begin(), lower_bound(as.begin(), as.end(), x))
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
typedef pair<int,int> P;
int H, W, M;
int row[300005],col[300005]; 
vector<int> G[300005];

vector<P> get_max(vector<P> &A) {
  vector<P> ret;
  int mx = A[0].first;
  int idx=0;
  while(mx==A[idx].first && idx < A.size()) {
    ret.push_back(A[idx]);
    idx++;
  }
  return ret;
} 

int main() {
  INCANT;
  cin >> H >> W >> M;
  int h, w;
  rep(i, M) {
    cin >> h >> w;
    h--;w--;
    row[h]++;
    col[w]++;
    G[h].push_back(w);
  }
  vector<P> rcnt(H), ccnt(W);
  rep(i, H) rcnt[i]=P(row[i], i);
  sort(ALL(rcnt), greater<P>());
  rep(i, W) ccnt[i]=P(col[i], i);
  sort(ALL(ccnt), greater<P>());
  vector<P> rkouho = get_max(rcnt);
  vector<P> ckouho = get_max(ccnt);
  int MAX = rcnt[0].first+ccnt[0].first;
  for (auto rp: rkouho) {
    int r=rp.second;
    vector<int> vec = G[r];
    sort(ALL(vec));
    for (auto cp: ckouho) {
      int c=cp.second;
      int id = index_of(vec, c);
      if (vec[id]==c) continue;
      cout << MAX << endl;
      return 0;
    }
  }
  cout << MAX-1 << endl;
  
  return 0;
}

Measured memory_bytes: 34992
#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() {
    string s, t;
    cin >> s;
    cin >> t;

    rep(i,s.size()) {
        if (s==t) {
            cout << "Yes" << endl;
            return 0;
        } else {
            char lastchar=t.at(t.size()-1);
            t.pop_back();
            t = lastchar + t;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n, false), b(n, false);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    if (u == 0) b[v] = true;
    if (v == 0) b[u] = true;
    if (v == n - 1) a[v] = true;
    if (v == n - 1) a[u] = true;
  }
  for (int i = 0; i < n; i++) {
    if (a[i] && b[i]) {
      cout << "POSSIBLE" << '\n';
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << '\n';
  return 0;
}

Measured memory_bytes: 1792
S = int(input())
p = 10**9+7
if S<3:
    print(0)
else:
    G = [0]*(2000+1)
    G[3] = 1
    G[4] = 1
    G[5] = 1
    for k in range(6,2000+1):
        G[k] = 1
        for t in range(3,k-2):
            G[k] = (G[k] + G[t])%p
    print(G[S])


Measured memory_bytes: 64668
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		if(n%10 == 9)
			printf("Yes\n");
		else if(n/10%10 == 9)
			printf("Yes\n");
		else 
			printf("No\n");
	}
}

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

int main(){
    long long N, A, B, C, D, E;
    cin >> N;
    cin >> A >> B >> C >> D >> E;
    long long MinMove = min( {A, B, C, D, E} );
    long long ans = ((N + MinMove - 1) / MinMove) + 4;

    cout << ans << endl;
}


Measured memory_bytes: 256
def main():
	N, K = map(int, input().split())
	S = input()
	ans = S
	if K > N-1:
		ans = S[:K-1]+S[K-1:].lower()
	elif K > 1:
		ans = S[:K-1]+S[K-1:K].lower()+S[K:]
	else:
		ans = S[:1].lower()+S[1:]
	print(ans)


if __name__ == '__main__':
	main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
long long const MOD=1e9+7;
long long black[100100];
long long white[100100];
int vs[100100];
long long n;
void dfs(int e,vector<int> adj[])
{
	if(vs[e]!=0)
	{
		return;
	}
	vs[e]=1;
	for(auto x: adj[e])
	{
		dfs(x,adj);
	}
	for(auto x:adj[e])
	{
		if(vs[x]==2)
		{
			white[e]=(white[e]*(black[x]+white[x]))%MOD;
			black[e]=(black[e]*white[x])%MOD;
		}
	}
	vs[e]=2;
	return;
}
int main()
{
	cin >> n;
	if(n==1)
	{
		cout << "2";
		return 0;
	}
	long long ans=2;
	vector<int> adj[n+1];
	long long gt;
	for(int i=1;i<n;i++)
	{
		long long a,b;
		cin >> a >> b;
		if(i==1)
		{
			gt=a;
		}
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		black[i]=1;
		white[i]=1;
		vs[i]=0;
	}
	dfs(gt,adj);
	long long dapan=(black[gt]+white[gt])%MOD;
	cout << dapan;
}

Measured memory_bytes: 11136
N = int(input())
A = list(map(int, input().split(' ')))
flag = True
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] % 3 == 0 or A[i] % 5 == 0:
            pass
        else:
            flag = False

if flag:
    print("APPROVED")
else:
    print("DENIED")


Measured memory_bytes: 2940
def decide_H(Cx,Cy):
    for x,y,h in T:
        H=h+abs(x-Cx)+abs(y-Cy)
        if h>=1:
            return(H)

def check_H(Cx,Cy,H):
    for x,y,h in T:
        if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
            return False
    return True

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

for Cx in range(101):
    for Cy in range(101):
        H=decide_H(Cx,Cy)
        if check_H(Cx,Cy,H):
            print(Cx,Cy,H)
            exit(0)

Measured memory_bytes: 3064
n = int(input())
s = [input() for i in range(n)]
s.sort()

result = []
m = 0
word = s[0]
count = 0
for i in range(n):
    if word == s[i]:
        count += 1
    else:
        result.append([word, count])
        word = s[i]
        count = 1
    if count > m:
        m = count
result.append([word, count])

for i in range(len(result)):
    if result[i][1] == m:
        print(result[i][0])

Measured memory_bytes: 39108
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1000000007;
const ll N=998244353;
ll power(ll x,ll n){ll res=1;while(n>0){if(n&1) res=res*x%MOD;x=x*x%MOD;n>>=1;}return res;}
ll modinverse(ll a){return power(a, MOD-2);}
void solve()
{
    ll n, x, t;
    cin>>n>>x>>t;
    if(n%x==0)
    {
    	cout<<(n/x)*t;
    }
    else
    {
    	cout<<(n/x+1)*t;
    }
}
int main()
{
	#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll test=1;
    //cin>>test;
    while(test--)
    {
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

int indeg[10005];
int ts[10005], tt = 0;
int q[10005], qh = 0, qt = 0;
vector<int> G[10005];

int main() {
	int v, e; cin >> v >> e;
	for (int i = 1; i <= e; i++) {
		int a, b; cin >> a >> b;
		G[a].push_back(b);
		indeg[b]++;
	}
	for (int i = 0; i < v; i++)
		if (!indeg[i])
			q[qt++] = i;
	while (qh < qt) {
		int t = q[qh++];
		ts[tt++] = t;
		for (int h : G[t]) {
			indeg[h]--;
			if (!indeg[h]) q[qt++] = h;
		}
	}
	for (int i = 0; i < tt; i++) cout << ts[i] << endl;
}


Measured memory_bytes: 3800
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n,cap; cin >> n >> cap;
  vector<int>w(n), v(n);
  for (int i = 0; i < n; ++i) {
    cin >> w[i] >> v[i];
  }
  vector<vector<long long>>dp(n + 1, vector<long long>(cap + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= cap; j++) {
      dp[i][j] = dp[i-1][j];
      if (j >= w[i-1]) {
        dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
      }
    }
  }
  cout << dp[n][cap] << endl;
  return 0;
}

Measured memory_bytes: 80256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

int h, w;
vector<string> s;
int ans[2005][2005];
bool used[2005][2005], used2[2005][2005];

int dfs(int x, int y, int sum = 0){
    if(y >= w || used[x][y])    return sum;
    used[x][y] = true;
    int add = dfs(x, y + 1, sum + 1);
    ans[x][y] += add;
    return add;
}

int dfs2(int x, int y, int sum = 0){
    if(x >= h || used2[x][y])   return sum;
    used2[x][y] = true;
    int add = dfs2(x + 1, y, sum + 1);
    ans[x][y] += add;
    return add;
}

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

    cin >> h >> w;
    s.resize(h);
    for(int i = 0; i < h; ++i)  cin >> s[i];
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(s[i][j] == '#'){
                used[i][j] = true;
                used2[i][j] = true;
            }
        }
    }
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(!used[i][j]) dfs(i, j);
            if(!used2[i][j])    dfs2(i, j);
        }
    }
    int ans2 = 0;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            chmax(ans2, ans[i][j] - 1);
            // cerr << max(0, ans[i][j] - 1) << " ";
        }
        // cerr << endl;
    }
    if(ans2 < 0)    ans2 = 0;
    cout << ans2 << endl;
}

Measured memory_bytes: 28288
#https://atcoder.jp/contests/abc104/tasks/abc104_c
 
d, g = map(int, input().split())
pc = []
 
for i in range(d):
  pc.append(list(map(int,input().split())))
 
ans = float("inf")
 
#各配点について解くか解かないかを決め、その上で G 点に満たなければ、まだ解いてない配点のうち一番高い配点のものを足りない分解く
 
for i in range(2**d):
    count = 0 #解く問題数
    sum = 0
    nokori = set(range(1, d + 1)) #点数の列
 
    for j in range(d):
        if (i>>j)&1:
            sum += pc[j][0] * (j + 1) * 100 + pc[j][1] #(j+1)*100点+bounus
            count += pc[j][0]
            nokori.discard(j + 1) #(j+1)*100点を処理したので削除
 
    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(nokori)
        # 解く問題が問題数を超えないように注意
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100
 
    if sum >= g:
        #数が小さい方を残す
        ans = min(ans, count)
 
print(ans)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
typedef long long llong;

static const int NMAX = 200001;

int main(){
    llong n, a[NMAX], num[NMAX], sum=0;
    cin >> n;
    for(int i=1; i<=n; i++) num[i] = 0;
    
    for(int i=0; i<n; i++){
        cin >> a[i];
        num[a[i]]++;
    } 

    for(int j=1; j<=n; j++){
        sum += num[j] * (num[j] - 1) / 2;
    }

    for(int i=0; i<n; i++){
        llong ans = sum - (num[a[i]] - 1);
        cout << ans  << endl;
    }

}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#define ll long long
char s[4005];
int sum[3][4005];
int main()
{
	int n;
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= 2; j++)
			sum[j][i] = sum[j][i + 1];
		if (s[i] == 'R')
			sum[0][i]++;
		else if (s[i] == 'G')
			sum[1][i]++;
		else
			sum[2][i]++;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
 		for (int j = i + 1; j <= n; j++)
		{
			if (s[i] == s[j])
				continue;
			else {
				if ((s[i] == 'R' && s[j] == 'G')|| (s[i] == 'G' && s[j] == 'R'))
					ans += sum[2][j] - ((j + j - i <= n && s[j + j - i] == 'B') ? 1 : 0);
				else if ((s[i] == 'R' && s[j] == 'B')|| (s[i] == 'B' && s[j] == 'R'))
					ans += sum[1][j] - ((j + j - i <= n && s[j + j - i] == 'G') ? 1 : 0);
				else if ((s[i] == 'B' && s[j] == 'G')|| (s[i] == 'G' && s[j] == 'B'))
					ans += sum[0][j] - ((j + j - i <= n && s[j + j - i] == 'R') ? 1 : 0);
			}
		}
	}
	printf("%lld", ans);
}
/*
39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB
*/

Measured memory_bytes: 3864
#include "stdio.h"


int main()
{
	int a, b, c, i = 0;
		int sum=0;
	
		scanf("%d %d %d", &a, &b, &c);
		
		
						if (a == b || b == c || a == c) {
							sum = 2;
							if (a == b && b == c) {
								sum = 1;
							}

						}
						else { sum = 3; }

			
					printf("%d\n", sum);
    return 0;
	

}



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

#define watch(x) cout << (#x) << " is " << (x) << endl
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i, st, en) for(int i=st; i<=en; i++)
#define repn(i, st, en) for(int i=st; i>=en; i--)
#define sq(a) (a*a)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll mod = 1e9+7;

void add_self(int &a, int b){
    a += b;
    if(a >= mod) a -= mod;
}

int sub_mod(int a, int b){
    a -= b;
    if(a < 0) a += mod;
    return a;
}

const int nax = 3005;
int pref[nax] = {0};

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    /// dp[i][j] - count of valid permutations for size i with last element as j
    dp[1][1] = 1;

    pref[1] = 1;

    for(int len  = 2; len <= n; ++len){
        char x = s[len - 2];

        for(int nxt = 1; nxt <= len; ++nxt){

            if(x == '<'){
                /// _ < _, and condn: nxt >= prev + 1
                add_self(dp[len][nxt], pref[nxt - 1]);

            } else {
                /// _ > _ and condn: nxt <= prev
                add_self(dp[len][nxt], sub_mod(pref[len - 1], pref[nxt - 1]));

            }
        }

        /// restore pref for next iteration, len + 1
        int s = 0;
        for(int j = 1; j <= len; j++){
            add_self(s, dp[len][j]);
            pref[j] = s;
        }
    }

    int res = 0;
    for(int j = 1; j <= n; ++j){
        add_self(res, dp[n][j]);
    }
    cout<<res;
}

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

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

    return 0;
}



Measured memory_bytes: 36744
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
const double PI = acos(-1);
struct mint {
  ll x; 
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
int main(){
    int n,k;cin>>n>>k;
    vl a(n),b,c;
    rep(i,n){
        cin>>a[i];
        if(a[i]<0)c.push_back(a[i]);
        else
        {
             b.push_back(a[i]);
        }
        }
    mint ans = 1;
    bool mi =false;
    if(b.size()>0){
        if(n==k)mi=(c.size()%2==0);
        else mi=true;
    }
    else{
        mi=(k%2==0);
    }
    if(mi){
        sort(been(a));
        sort(been(b));
        sort(been(c),greater<ll>());
        vl memo;
        if(k%2){
            ans *= b.back();
            b.pop_back();
        }
        while(b.size()>1){
            ll sum =b.back();
            b.pop_back();
            sum*=b.back();b.pop_back();
            memo.push_back(sum);
        }
        while (c.size()>1)
        {
            ll sum =c.back();
            c.pop_back();
            sum*=c.back();c.pop_back();
            memo.push_back(sum);
        }
        sort(been(memo),greater<ll>());
        rep(i,k/2){
            ans*=memo[i];
        }
        cout<<ans<<endl;
    }
    else{
        sort(been(a),[](ll x,ll y){return abs(x)<abs(y);});
        rep(i,k){
            ans*=a[i];
        }
        cout<<ans<<endl;      
    }
    
}

Measured memory_bytes: 8156
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define fo(i,n) for(ll i=0;i<n;i++)
#define fok(i,k,n) for(ll i=k;i<n;i++)
#define ci(x) cin>>x
#define ci2(x,y) cin>>x>>y
#define co(x) cout<<x<<"\n"
#define co2(x,y) cout<<x<<" "<<y<<"\n"
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const int mod = 1000000007;
const int INF =1e9;

int main(){
	int n,m;
	ci2(n,m);
	vi profit[m];
	fo(i,n){
		int a,b;
		ci2(a,b);
		if(a>m) continue;
		profit[m-a].pb(b);
	}
	priority_queue<int> pq;
	ll ans=0;
	for(int i=m-1;i>=0;i--){
		if(!profit[i].empty()){
			for(auto c : profit[i]){
				pq.push(c);
			}
		}
		if(!pq.empty()){
			ans+=pq.top();
			pq.pop();
		}
	}
	co(ans);
}


Measured memory_bytes: 5504
#include "bits/stdc++.h"
using namespace std;typedef long long lint;typedef vector<lint> liv;
//#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(),v.end()
#define linf 1152921504606846976
#define MAXN 100010
#define md 1000000007//998244353

#define pb push_back
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
//template<class T>
//ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
//template<class T>
//ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }

inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
template <class T>
inline bool out(T t){ cout<<t<<'\n';return 0; }
inline bool out(){ cout<<'\n';return 0; }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }

#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define rrep(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_trrep1))((__VA_ARGS__))
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define fi i.first
#define se i.second
#define YES(c) cout<<((c)?"YES\n":"NO\n")
#define Yes(c) cout<<((c)?"Yes\n":"No\n")

int main(){
	stin(s);
	lint n=s.size();
	lint g=0,p=0;rep(n)if(s[i]=='g')++g;else ++p;
	lint can=n/2;
	cout<<can-p<<endl;
}

Measured memory_bytes: 512
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)*}
    };
}

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)*}
    };
}

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")
    };
}

fn main() {
    input! {
        n: usize,
        v: [usize; n],
        c: [usize; n],
    }
    let mut s = 0;
    for i in 0..n {
        if v[i] > c[i] {
            s += v[i] - c[i];
        }
    }
    println!("{}", s);
}


Measured memory_bytes: 4352
//============================================================================
// Name        : Hello5.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using p = pair<int,int>;//<key,value>


int main() {
int n;

cin>>n;
map<string,int> mp;
rep(i,n) {
string a;
cin>>a;
mp[a]++;
}
int mx =0;
for (auto p : mp) mx = max(mx, p.second);
for(auto p:mp){
if(p.second!= 1)
{
	cout<<"NO"<<endl;
	return 0;
}

}
cout<<"YES"<<endl;
return 0;
}




Measured memory_bytes: 24832
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);


int main(){
  int N, R; cin >> N >> R;

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


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

#define ll long long int

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

	int n; 
	cin >> n;
	string s;
	cin >> s;

	if(n % 2)
	{
		cout << "No";
		return 0;
	}

	int k = n / 2;

	for(int i = 0; i < k; ++i)
	{
		if(s[i] != s[i + k])
		{
			cout << "No";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;
}

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

#define int long long
#define pb push_back 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i, n) for( int i = 0; i < (n); i++ )
#define Rrep(i, a, n) for( int i = (a); i < (n); i++ )
#define All(v) v.begin(), v.end()

typedef pair<int, int> Pii; 
typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

int N, A, B, C, D;
bool flag = 0;

signed main()
{ 
  cin >> N >> A >> B >> C >> D;
  int sa = (B - A);

  for ( int i = 0; i < N; i++ ) {
    int ll = -(D * i), lr = -(C * i), rl = C * i, rr = D * i;
    if ( ll + C * (N - 1 - i) <= sa && sa <= lr + D * (N - 1 - i) ) flag = true;
    if ( rl - D * (N - 1 - i) <= sa && sa <= rr - C * (N - 1 - i) ) flag = true; 
  }

  if ( flag ) cout << "YES" << endl;
  else cout << "NO" << endl;
}


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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll W, H, x, y;
    cin >> W >> H >> x >> y;

    double ans = (double)W * (double)H / 2.0;  
    bool isMulti = false;
    if (W % 2 == 0 && H % 2 == 0)
    {
        if (W / 2 == x && H / 2 == y)
        {
            isMulti = true;
        }
    }

    ll multi = isMulti ? 1 : 0;
    cout << ans << " " << multi << endl;;

}


Measured memory_bytes: 256
from heapq import heappush, heappop

def main():
  n, m = map(int, input().split())
  ab = []
  for _ in range(n):
    ab.append(tuple(map(int, input().split())))
  ab = list(sorted(ab))
  abi = 0
  hb = []
  ans = 0
  for i in range(1, m+1):
    while abi<n and ab[abi][0] <= i:
      heappush(hb, -ab[abi][1])
      abi += 1
    if len(hb) == 0:
      continue
    b = heappop(hb)
    ans += -b
  print(ans)


if __name__ == '__main__':
  main()


Measured memory_bytes: 20388
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int N; 
    cin >> N;
    string str;
    cin >> str;
    
    int count=1;
    for(int n=1; n<N; n++) {
        if(str[n]!=str[n-1]) {
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
    
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using lli = long long int;
using ulli = unsigned long long int;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl


namespace atcoder {
	template<typename T>
	T ncr(T left, T right) {
		right = min(left - right, right);
		T ans = 1;
		for (T i = 1; i <= right; i++) {
			ans = ans * (left - right + i) / i;
		}
		return ans;
	}

	const int MOD = 1000000007;
	const lli LIMIT = 1'0'000'000'000'000'000 * 5;
	const int tenfive = 100000;
}

using namespace atcoder;


int main() {
	int N, M, C;
	cin >> N >> M >> C;
	vector<int> B(M),A(M);
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int cnt = C;
		for (int j = 0; j < M; j++) {
			cin >> A[j];
			cnt += A[j] * B[j];
		}
		if (cnt > 0)ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
using namespace std;
typedef long long ll;
const int Mod=1e9+7;
int n,u,v,sz[5100],tmp[5100],f[5100][5100],g[5100];
int edgenum,vet[11000],Next[11000],Head[5100];
void addedge(int u,int v){
	vet[++edgenum]=v;
	Next[edgenum]=Head[u];
	Head[u]=edgenum;
}
void dfs(int u,int fa){
	sz[u]=1; f[u][1]=1;
	for (int e=Head[u];e;e=Next[e])
		if (vet[e]!=fa){
			dfs(vet[e],u);
			for (int j=0;j<=sz[u]+sz[vet[e]];j++) tmp[j]=f[u][j],f[u][j]=0;
			for (int i=1;i<=sz[u];i++)
				for (int j=0;j<=sz[vet[e]];j++)
					f[u][i+j]=(f[u][i+j]+(ll)tmp[i]*f[vet[e]][j]%Mod)%Mod;
			sz[u]+=sz[vet[e]];
		}
	for (int j=0;j<=sz[u];j++) f[u][0]=(f[u][0]+(Mod-(ll)f[u][j]*g[j]%Mod)%Mod)%Mod;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	g[2]=1;
	for (int i=4;i<=n;i++) g[i]=(ll)g[i-2]*(i-1)%Mod;
	dfs(1,0);
	printf("%d\n",(Mod-f[1][0])%Mod);
	return 0;
}


Measured memory_bytes: 100224
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

int main(){
    string s; cin >> s;
    string r = "2019/04/30";
    if(s > r) cout << "TBD" << endl;
    else cout << "Heisei" << endl;
    return 0;
}

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

using namespace std;

using ll = long long;

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

    ll n;
    cin >> n;

    ll sum_b = 0;
    vector<ll> score(n);
    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        sum_b -= b;
        score[i] = a + b;
    }

    sort(score.begin(), score.end(), greater<ll>());
    ll sum_a = 0;
    for (int i = 0; i < n; i += 2)
        sum_a += score[i];

    cout << sum_a + sum_b << endl;

    return 0;
}


Measured memory_bytes: 1024
a = int(input().split()[0])
s = input()
if (s[:a]+s[a+1:]).replace('0','').replace('1','').replace('2','').replace('3','').replace('4','').replace('5','').replace('6','').replace('7','').replace('8','').replace('9','') or s[a] != '-':
    print('No')
else:
    print('Yes')

Measured memory_bytes: 3060
n,m,x = map(int, input().split())
arr = []
money = []
vector = 0
for i in range(n):
  row = list(map(int, input().split()))
  money.append(row[0])
  arr.append(row[1:])
  vector += 2 ** (n-i-1)

ans = float('inf')
for i in range(vector+1):
  j = n-1
  result = [0] * m
  spend = 0
  while i > 0:
    if i % 2:
      result = [x + y for (x, y) in zip(result, arr[j])]
      spend += money[j]
    i //= 2
    j -= 1
  if min(result) >= x:
    ans = min(ans, spend)

if ans == float('inf'):
  print(-1)
else:
  print(ans)

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

int main() {
  ll N = 0,K = 0;
  cin >> N >> K;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  vector<ll>sum(N-K+1);
  rep(i,N-K+1){
    if(A[i]<0 && A[i+K-1]>=0){
      sum[i] = 2*min(abs(A[i]),abs(A[i+K-1])) + max(abs(A[i]),abs(A[i+K-1]));
    }
    else{
      sum[i] = max(abs(A[i+K-1]),abs(A[i]));
    }
  }
  sort(sum.begin(), sum.end());
  cout << sum[0];
}

Measured memory_bytes: 4304
#include<iostream>
#include<cstdio>
#include<ios>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<list>
#include<utility>
#include<tuple>
#include<map>
#include<unordered_map>
#include<complex>
using namespace std;
typedef long long llong;
llong gcd(llong a, llong b) {
	if (a < b) std::swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
llong lcm(llong a, llong b) {
	llong g = gcd(a, b);
	return a * b / g;
}
//ここまで共通

int N;
bool f = true;
stack<int> H;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int h; cin >> h;
		H.push(h);
	}
	int h1 = H.top();
	H.pop();
	int h2;

	while(!H.empty()) {
		h2 = H.top();
		H.pop();

		if (h2 - h1 > 1) {
			f = false;
		}
		else if (h2 - h1 == 1) {
			h2 = h2 - 1;
		}
		else{}

		h1 = h2;
	}
	if (f) cout << "Yes";
	else cout << "No";

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int N,M;
    Scd2(N,M);

    vector<ll> A(N);
    Rep(i,N){
        Scll(A[i]);
    }
    using pll =  pair<ll,ll>;
    vector<pll> B(M);
    Rep(i,M){
        Scll2(B[i].second,B[i].first);
    }

    sort(A.begin(), A.end() );
    sort(B.begin(), B.end() );
    reverse( B.begin(), B.end() );

    int bi = 0;
    Rep(i,N){
        if( bi == M ) break;
        if( B[bi].first > A[i] ) A[i] = B[bi].first;
        else break;
        B[bi].second -= 1;
        if( B[bi].second == 0 ) bi++;
    }

    ll ans = 0;
    Rep(i,N){
        ans += A[i];
    }

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




    return 0;
}



Measured memory_bytes: 2560
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using static System.Console;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        int[] NM = ReadLineParseIntArray();
        int N = NM[0];
        int M = NM[1];
        long ans = 1;
        long[] stairs = new long[N + 1];
        bool[] canNotMove = new bool[N + 1];
        for (int i = 0; i < M; i++)
            canNotMove[ReadLineParseInt()] = true;

        stairs[0] = 1;
        stairs[1] = canNotMove[1] ? 0 : 1;
        for(int i = 2; i <= N; i++)
        {
            if (canNotMove[i]) continue;
            long v = 0;
            v += canNotMove[i - 1] ? 0 : stairs[i - 1];
            v += canNotMove[i - 2] ? 0 : stairs[i - 2];
            stairs[i] = v % 1000000007;
        }
        WriteLine(stairs[N]);
    }
    static int[] ReadLineParseIntArray() => ReadLine().Split(' ').Select(int.Parse).ToArray();
    static int ReadLineParseInt() => int.Parse(ReadLine());
}

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

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 100005;
int n, a, b, d[MX], res, t[MX];
vi adj[MX];
string s;
bitset<MX> ex;
queue<int> q;

ii dfs (int u, int p) {
	ii res(0, u);

	for (int v : adj[u])
		if (v != p && ex[v])
			res = max(res, dfs(v, u));
	
	res.fi += 1 + t[u];
	return res;
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	cin >> s;
	s = "0" + s;

	for (int i = 1; i <= n; i++) {
		d[i] = adj[i].size();
		if (d[i] <= 1 && s[i] == 'B') q.push(i); 
		else ex[i] = 1;
	}

	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int v : adj[u])
			if (ex[v]) {
				d[v]--;
				if (d[v] == 1 && s[v] == 'B') q.push(v), ex[v] = 0;
			}
	}

	if (!ex.count()) {
		cout << 0 << endl;
		return 0;
	}

	if (ex.count() == 1) {
		cout << 1 << endl;
		return 0;
	}

	for (int i = 1; i <= n; i++)
		if (ex[i])
			if ((s[i] == 'W') ^ (d[i] & 1)) {
				t[i] = 1;
				res++;
			} else {
				t[i] = -1;
			}

	for (int i = 1; i <= n; i++)
		if (ex[i]) {
			cout << res + 2 * ((int)ex.count() - 1) - dfs(dfs(i, -1).se, -1).fi << endl;
			return 0;
		}

	return 0;
}


Measured memory_bytes: 17640
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200009];
ll b[200009];
ll tree[800009];
void upd(int node,int l,int r,int k,ll val){
	if(l == r){
		tree[node] = val;
		return;
	}
	if(k <= (l+r)/2) upd(node*2,l,(l+r)/2,k,val);
	else upd(node*2+1,(l+r)/2+1,r,k,val);
	tree[node] = max(tree[node*2],tree[node*2+1]);
}
ll query(int node,int l,int r,int s,int e){
	if(s <= l && e >= r) return tree[node];
	if(s <= (l+r)/2 && e >= (l+r)/2+1){
		return max(query(node*2,l,(l+r)/2,s,e),query(node*2+1,(l+r)/2+1,r,s,e));
	}
	if(s <= (l+r)/2) return query(node*2,l,(l+r)/2,s,e);
	return query(node*2+1,(l+r)/2+1,r,s,e);
}
int main(){
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<n;i++){
		ll id = a[i],val = b[i];
		ll x = query(1,0,n-1,0,id-1);
		upd(1,0,n-1,id-1,x+val);
	}
	cout<<tree[1]<<endl;
}


Measured memory_bytes: 9600
#include<iostream>

using namespace std;

int main(){
  int x,y;
  cin >> x >> y;
  while(x != 0||y != 0){
    if(x <= y){
      cout << x << " " << y << endl;
    }else{
      cout << y << " " << x << endl;
    }
    cin >> x >> y;
  }
  return 0;
}


Measured memory_bytes: 3060
n, m, q = map(int, input().split())
cities = [[0] * (n + 1) for _ in range(n + 1)]
trains = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    trains[l][r] += 1

for i in range(n):
    for j in range(n):
        cities[i + 1][j + 1] = cities[i + 1][j] + trains[i + 1][j + 1]
for _ in range(q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q + 1):
        ans += cities[i][q] - cities[i][p - 1]
    print(ans)


Measured memory_bytes: 55672
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        char[] b = sc.nextLine().toCharArray();
        char[] a = new char[30];
        a['A' - 'A'] = 'T';
        a['C' - 'A'] = 'G';
        a['G' - 'A'] = 'C';
        a['T' - 'A'] = 'A';
        System.out.println(a[b[0] - 'A']);
    }
}

Measured memory_bytes: 21588
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#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 fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
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;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
 
template<typename T>
 
struct BIT{
    vector<T> data;
    BIT(int sz){
        data.assign(sz+1,0);
    }
    T sum(int a){ //sum[1,x]
        T res=0;
        for(int x=a;x>0;x-=(x&-x)) res+=data[x];
        return res;
    }
    void add(int a,T y){ //data[x]+=y
        for(int x=a;x<=data.size();x+=(x&-x)) data[x]+=y;
    }
};
 
vector<int> shrink(vector<ll> a){
    vector<ll> val=a;
    vector<int> ret(a.size());
    sort(ALL(val));
    val.erase(unique(ALL(val)),val.end());
    rep(i,a.size()){
        int id=lower_bound(ALL(val),a[i])-val.begin();
        ret[i]=id+1;
    }
    return ret;
}
 
ll outen(vector<ll> a){
    vector<int> resh=shrink(a);
    ll OUTEN=0;
    BIT<int> b(1001001);
    rep(i,resh.size()){
        OUTEN+=i-b.sum(resh[i]);
        b.add(resh[i],1);
    }
    return OUTEN;
}

signed main(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll l=-1,r=1001001001;
    while(r-l>1){
        ll mid=l+(r-l)/2;
        vector<int> c(n+1);
        c[0]=0;
        rep(i,n){
            if(a[i]<=mid) c[i+1]=c[i]+1;
            else c[i+1]=c[i];
        }
        vector<ll> d(n+1);
        rep(i,n+1) d[i]=2*c[i]-i;
        reverse(ALL(d));
        ll rs=outen(d);
        if(rs>n*(n+1)/4) r=mid; //ans<=mid
        else l=mid;
    }
    cout << r << endl;
}


Measured memory_bytes: 8896
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

ll x[110], y[110], h[110];
int main()
{
	int N; cin >> N;
	int point = 0;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> h[i];
		if (h[i] != 0)  point = i;
	}
	for (int X = 0; X <= 100; X++) {
		for (int Y = 0; Y <= 100; Y++) {
			ll H = h[point] + abs(x[point] - X) + abs(y[point] - Y);
			bool ok = true;
			for (int i = 0; i < N; i++) {
				if (h[i] != max(H - abs(x[i] - X) - abs(y[i] - Y), 0ll)) {
					ok = false;
						break;
				}
			}
			if (ok) {
				cout << X << " " << Y << " " << H << endl;
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var N = input[0];
            var M = input[1];
            var X = input[2];
            var Y = input[3];
            var x = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var y = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var xMax = x.Max();
            var yMin = y.Min();

            if (xMax < Y)
            {
                if (xMax > X) X = xMax;
            }
            else
            {
                Console.WriteLine("War");
                return;
            }
            if (yMin >= X)
            {
                if (yMin < Y) Y = yMin;
            }
            else
            {
                Console.WriteLine("War");
                return;
            }
            if (X == Y)
            {
                Console.WriteLine("War");
                return;
            }

            Console.WriteLine("No War");
        }
    }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define ss second
#define ff first 
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
const ll M=1000000007;
ll power(ll x,ll n,ll m){if(n==0)return 1;else if(n%2==0)return (power(((x%m)*(x%m))%m,n/2,m))%m;else return ((x%m)*power(x,n-1,m)%m);}
ll ncr(int n,int r){if(r>n)return 0;if(r > n - r) r = n - r;ll ans = 1;
int i;for(i = 1; i <= r; i++){ans *= n - r + i;ans /= i;}return ans;}
ll nCrModpDP(ll n, ll r, ll p){ 
    ll C[r+1]; 
    memset(C, 0, sizeof(C)); 
    C[0] = 1;
    for (ll i = 1; i <= n; i++){ 
        for (ll j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
} 
ll ncrmod(ll n, ll r, ll p){ 
   if (r==0) 
      return 1; 
   ll ni = n%p, ri = r%p; 
   return (ncrmod(n/p, r/p, p) * 
           nCrModpDP(ni, ri, p)) % p;  
} 
ll modInverse(ll a,ll m) 
{ 
   ll m0 = m; 
   ll y = 0, x = 1; 
  
    if (m == 1) 
      return 0; 
  
    while (a > 1) 
    { 
       ll q = a / m; 
       ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    } 
    if (x < 0) 
       x += m0; 
  
    return x; 
} 
int dx[] = {1,-1,0,0,1,1,-1,-1}; 
int dy[] = {0,0,1,-1,-1,1,-1,1}; 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string str;
cin>>str;
ll ans=0;
for(int i=0; i<str.length(); i++){
ans+=(str[i]-48);
}
if(ans%9==0)
cout<<"Yes";
else
cout<<"No";
return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------


int main(){
ll n,k;
cin>>n>>k;
string s;
cin>>s;
for(int i=0;i<n;i++){
    if(i==k-1){
        cout<<(char)(s.at(i)+' ');
    }else{
        cout<<s.at(i);
    }
}
}









Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }

const int MAX_N = 500005;
int r[MAX_N];
int l[MAX_N];
int a[MAX_N];

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    for(int i = 0; i < n; ++i) {
        if(s[i] == '<') {
            l[i+1] = l[i] + 1;
        }
    }
    for(int i = n-1; i >= 0; --i) {
        if(s[i] == '>') {
            r[i] = r[i+1] + 1;
        }
    }
    rep(i, n+1) a[i] = max(l[i], r[i]);
    ll sum = 0;
    rep(i,n+1) sum += a[i];
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 6660