akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main{
	static Node root;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		for(int i = 0; i < n; i++) {
			String com = scan.next();
			if(com.equals("insert")) {
				int k = scan.nextInt();
				insert(k);
			}else if(com.equals("find")){
				int k = scan.nextInt();
				Node t = find(k, root);
				if(t != null) {
					System.out.println("yes");
				}else {
					System.out.println("no");
				}
			}else {
				inorder(root);
				System.out.println();
				preoder(root);
				System.out.println();
			}
		}
		scan.close();
	}
	static class Node{
		int key;
		Node parent, left, right;
		Node(int key){
			this.key = key;
		}
	}
	static void insert(int k) {
		Node y = null;
		Node x = root;
		Node z = new Node(k);
		while(x != null) {
			y = x;
			if(k < x.key) {
				x = x.left;
			}else {
				x = x.right;
			}
		}
		z.parent = y;
		if(y == null) {
			root = z;
		}else {
			if(z.key < y.key) {
				y.left = z;
			}else {
				y.right = z;
			}
		}
	}
	static Node find(int k, Node x) {
		while(x != null && k != x.key) {
			if(k < x.key) x = x.left;
			else x = x.right;
		}
		return x;
	}
	static void inorder(Node u) {
		if(u == null) return;
		inorder(u.left);
		System.out.print(" " + u.key);
		inorder(u.right);
	}
	static void preoder(Node u) {
		if(u == null) return;
		System.out.print(" " + u.key);
		preoder(u.left);
		preoder(u.right);
	}
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int a, b;
	cin >> a >> b;
	if(a != 2 && b != 2){
		cout << "Yes" << endl;
		return 0;
	}else{
		cout << "No" << endl;
		return 0;
	}

}


Measured memory_bytes: 256
def calc(s):
    n = len(s)

    dec = [0 for i in range(n)]
    inc = [0 for i in range(n)]
    ran = [0 for i in range(n)]

    for i in range(n):
        dec[i] = n-1-i
        inc[i] = i

    i = 0
    while i<n:
        if s[i] == '0':
            i += 1
        else:
            st = i
            while i<n and s[i]=='1':
                i += 1
            for j in range(st,i):
                ran[j] = i-st

    ans = n
    for i in range(n):
        v = max(dec[i],inc[i],ran[i])
        if s[i] == '1':
            ans = min(ans,v)
    return ans

def main():
    s = input()
    n = len(s)

    t = list(s[:])
    for i in range(n):
        if t[i] == '0':
            t[i] = '1'
        else:
            t[i] = '0'
    t = ''.join(t)

    return max(calc(s),calc(t))

if __name__ == '__main__':
    print(main())


Measured memory_bytes: 15076
def main():
    N,L = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    flg = False
    for i in range(N-1):
        if(A[i]+A[i+1] >= L):
            flg = True
            break
    if not flg:
        print("Impossible")
        return
    print("Possible")
    for j in range(1,i+1):
        print(j)
    for j in reversed(range(i+2,N)):
        print(j)
    print(i+1)
main()


Measured memory_bytes: 63984
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_c>
問題文============================================================
 xy平面上の0≦x≦W,0≦y≦Hをみたす領域にあるx,yともに整数である点すべてに、ひとつずつ家があります。
 
 x座標が等しくy座標の差が1であるか、y座標が等しくx座標の差が1であるような2点の組のうち、
 両方の点に家が存在するような全てのものに対し、その2点の間には舗装されていない道路があります。
 
 座標(i,j)と(i+1,j)にある家の間の道路を舗装するのにはjの値にかかわらずコストがpi、
 座標(i,j)と(i,j+1)にある家の間の道路を舗装するのにはiの値にかかわらずコストがqjかかります。
 
 高橋君は、このうちいくつかの道路を舗装し、
 舗装された道路のみを通って任意の2つの家の間を行き来できるようにしたいです。
 かかるコストの総和の最小値を求めてください。
 
 1≦W,H≦10^5
 1≦pi≦10^8(0≦i≦W−1)
 1≦qj≦10^8(0≦j≦H−1)
 pi(0≦i≦W−1)は整数である
 qj(0≦j≦H−1)は整数である
=================================================================

解説=============================================================

================================================================
*/
ll solve(){
    ll ret = 0;
    ll W,H; cin >> W >> H;
    vector<ll> p(W),q(H);
    for(auto &in:p) cin >> in;
    for(auto &in:q) cin >> in;
    vector<pll> event(W+H);
    for(int i = 0; i < W;i++) event[i] = {p[i],0};
    for(int i = 0; i < H;i++) event[i+W] = {q[i],1};
    sort(event.begin(),event.end());
    
    W++; H++;
    for(const pll& e:event){
        if(e.second == 0){
            ret += e.first*H; W--;
        }else{
            ret += e.first*W; H--;
        }
    }
    return ret;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


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

class WarshallFloyd {
public:
    using Matrix = std::vector<std::vector<int>>;

    WarshallFloyd(int V) {
        mat.resize(V);
        for (int i = 0; i < V; ++i) {
            mat[i].resize(V, INT32_MAX);
            mat[i][i] = 0;
        }
    }
    ~WarshallFloyd() = default;

    void add(int s, int t, int d) noexcept {
        this->mat[s][t] = d;
    }

    // return all pairs of shortest path from vertex to vertex  
    // if unreachble from vertex i to j, shortest_path[i][j] is INT32_MAX
    Matrix allPairs() const noexcept {
        Matrix sp = this->mat; // shortest path
        for (size_t k = 0; k < this->mat.size(); ++k) {
            for (size_t i = 0; i < this->mat.size(); ++i) {
                for (size_t j = 0; j < this->mat.size(); ++j) {
                    if (sp[i][k] == INT32_MAX || sp[k][j] == INT32_MAX) {
                        continue;
                    }

                    sp[i][j] = std::min(sp[i][j], sp[i][k] + sp[k][j]);
                }
            }
        }

        return sp;
    }

private:
    Matrix mat; // adjacency matrix  
};

int main() {
    int V, E;
    std::cin >> V >> E;

    WarshallFloyd wf(V);
    int s, t, c;
    for (int i = 0; i < E; ++i) {
        std::cin >> s >> t >> c;
        wf.add(s, t, c);
    }

    std::vector<std::vector<int>> d = wf.allPairs();

    for (int i = 0; i < V; ++i) {
        if (d[i][i] < 0) {
            std::cout << "NEGATIVE CYCLE" << std::endl;
            return 0;
        }
    }

    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (d[i][j] == INT32_MAX) {
                std::cout << "INF";
            } else {
                std::cout << d[i][j];
            }

            if (j == (V - 1)) {
                std::cout << std::endl;
            } else {
                std::cout << " ";
            }
        }
    }

    return 0;
}



Measured memory_bytes: 3252
import sys,re
c=lambda l,n:re.sub("[a-z]",lambda x:chr((ord(x.group(0))-97+n)%26+97),l)
for i in sys.stdin:
	n=0
	while not re.search("th(e|is|at)",c(i,n)):n+=1
	print c(i,n).strip()

Measured memory_bytes: 4204
N = int(input())
A = [0]*N
B = [0]*N 
for i in range(N):
    s,t = map(int,input().split())
    A[i] = s
    B[i] = t
A.sort()
B.sort()
if N%2 == 1:
    a = A[(N-1)//2]
    b = B[(N-1)//2]
    print(b-a+1)
if N%2 == 0:
    a = A[N//2 - 1] + A[N//2]
    b = B[N//2 - 1] + B[N//2]
    print(b-a+1)

Measured memory_bytes: 25488
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
const int mod = 1000000007;

int main() {
    int N;
    cin >> N;
    ll power = 1;
    for (int i = 1; i <= N; i++){
        power = (power % mod) * i;
    }
    cout << power % mod << endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const int N = 100000;


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a[N],x,ans=0;
	CLR(a);
	int n;
	cin >> n >> x;
	FOR(i,0,n)cin >> a[i];
	if(a[0]>x){
		ans += a[0]-x;
		a[0] = x;
	}
	FOR(i,0,n-1){
		ll b = a[i] + a[i+1];
		if(b <= x)continue;
		ll c = b - x;
		ans += c;
		a[i+1] -= c;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <stack>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

vector<string> split(const string &str, char delim) {
	vector<string> res;
	size_t current = 0, found;
	while((found = str.find_first_of(delim, current)) != string::npos) {
		res.push_back(string(str, current, found - current));
		current = found + 1;
	}
	res.push_back(string(str, current, str.size() - current));
	return res;
}

int main() {
	int n;
	while(cin >> n && n) {
		vector<string> s(n);
		rep(i, n) cin >> s[i];

		map<string, set<string> > m;
		map<string, int> id;
		vector<string> res[n];
		rep(i, n) {
			vector<string> ret = split(s[i], ':');
			id[ret[0]] = i;
			string t = "";
			rep(j, ret[1].size()) {
				if(ret[1][j] == ',' || ret[1][j] == '.') {
					m[ret[0]].insert(t);
					res[i].push_back(t);
					t = "";
				} else {
					t += ret[1][j];
				}
			}
		}

		set<string> S;
		stack<string> st;
		bool used[105];
		memset(used, 0, sizeof(used));
		used[0] = true;

		rep(i, res[0].size()) {
			st.push(res[0][i]);

			while(st.size()) {
				string tp = st.top();
				st.pop();

				if(m.count(tp) == 0) {
					S.insert(tp);
				} else if(!used[id[tp]]){
					used[ id[tp] ] = true;

					set<string>::iterator ite;
					for(ite = m[tp].begin(); ite != m[tp].end(); ite++) {
						st.push(*ite);
					}
				}
			}
		}

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

	return 0;
}

Measured memory_bytes: 1444
#include<cstdio>
#include<algorithm>
using namespace std;

int n,p,l[100000];

void heap_sort(void){
  int now,nxt;
  for(int i=1;i<n-1;i++){
    now = i;
    while(now){
      nxt = (now-1)>>1;
      if(l[nxt] < l[now])swap(l[nxt],l[now]);
      else break;
      now = nxt;
    }
  }
  
  for(int i=n-2;i>0;i--){
    swap(l[i],l[0]);
    now = 0; nxt = (now+1)<<1;
    while(nxt-1 < i){
      if(l[now] < l[nxt-1]){
	if(nxt<i && l[nxt-1] < l[nxt]){
	  swap(l[now],l[nxt]);
	  now = nxt;
	}else{
	  swap(l[now],l[nxt-1]);
	  now = nxt-1;
	}
      }else if(nxt<i && l[now] < l[nxt]){
	swap(l[now],l[nxt]);
	now = nxt;
      }else break;
      nxt = (now+1)<<1;
    }
  }
}

int main(){
  while(scanf("%d",&n),n){
    long long num = n,len = 0;
    for(int i=0;i<n;i++){ scanf("%d",&p); len += p;}

    for(int i=0;i<n-1;i++)scanf("%d",&l[i]);
    heap_sort();
    
    for(int i=n-2;i>=0;i--){
      if( (num-1)*(len+l[i]) < num*len )break;
      num--; len += l[i];
    }
    printf("%lld\n",num*len);
  }
}

Measured memory_bytes: 1284
#include<iostream>
#include<string>

int main()
{

	while (true) {
		std::string x;
		std::cin >> x;
		if (x == "0") break;

		int sum = 0;
		for (int i = 0; i < x.size()
			; i++) {
			sum += x[i] - '0';
		}
		std::cout << sum << std::endl;
	}
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll MOD = 1e9 + 7;
using namespace std;

int main()
{
    IOS
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    string s;
    cin >> s;
    ll n = s.length(),c = 0,ans = 0;
    for(ll i = n-1;i>=0;--i)
    {
    	if(s[i] == 'B')
    	{
    		ans += c;
    	}
    	else
    		++c;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)	for(int i=a; i<n; i++)
#define loop(i,a,n)	for(int i=a; i>=n; i--)

int main() 
{		
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(0);
	
	long long int a,b;
	cin>>a>>b;
	long long int c[b],mx=0;
	forr(i,0,b)	
		cin>>c[i];
	forr(i,0,b-1)
	{
		mx=max(mx,abs(c[i+1]-c[i]));
	}
	mx=max(mx,abs(a-c[b-1])+c[0]);
	cout<<a-mx;
	
	return 0;	
}

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

using namespace std;


int main()
{
    int n;
    string s;

    cin >> n;
    cin >> s;

    long long int n_R = 0, n_G = 0, n_B = 0;

    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
            n_R++;
        if (s[i] == 'G')
            n_G++;
        if (s[i] == 'B')
            n_B++;
    }

    long long int condition_1 = n_R*n_G*n_B;
    
    long long int non_condition_2 = 0;

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
    
            int k = 2*j - i;
            if (k < n)
                if (s[i] != s[j])
                    if (s[j] != s[k])
                        if (s[i] != s[k])
                            non_condition_2++;
        }

    long long int ans = condition_1 - non_condition_2; 

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

Measured memory_bytes: 3644
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

double mul[] = {0.0625, 0.125, 0.25, 0.5};

int main(){
  double x;

  while(cin >> x, x != -1){
    int a = (int)floor(x);

    if(a >= (1 << 8)){
      cout << "NA" << endl;
      continue;
    }

    int bit = -1;
    double b = x - a;

    for(int i = 0; i < (1 << 4); i++){
      double sum = 0;
      for(int j = 0; j < 4; j++){
        if(!(i & (1 << j))) continue;
        sum += mul[j];
      }
      if(sum == b){
        bit = i;
        break;
      }
    }

    if(bit == -1){
      cout << "NA" << endl;
      continue;
    }

    for(int i = 7; i >= 0; i--){
      cout << (a & (1 << i) ? 1 : 0);
    }
    cout << ".";
    for(int i = 3; i >= 0; i--){
      cout << (bit & (1 << i) ? 1 : 0);
    }
    cout << endl;
  }
}

Measured memory_bytes: 1228
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "cmath"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;


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

	cin >> N;
	M = (N / 100) % 10;
	K = (N / 10) % 10;
	H = N % 10;
	N /= 1000;
	if (N + M + K + H == 7) {
		cout << N << "+" << M << "+" << K << "+" << H << "=7" << endl;
		return 0;
	}
	if (N + M + K - H == 7) {
		cout << N << "+" << M << "+" << K << "-" << H << "=7" << endl;
		return 0;
	}
	if (N + M - K + H == 7) {
		cout << N << "+" << M << "-" << K << "+" << H << "=7" << endl;
		return 0;
	}
	if (N + M - K - H == 7) {
		cout << N << "+" << M << "-" << K << "-" << H << "=7" << endl;
		return 0;
	}
	if (N - M + K + H == 7) {
		cout << N << "-" << M << "+" << K << "+" << H << "=7" << endl;
		return 0;
	}
	if (N - M + K - H == 7) {
		cout << N << "-" << M << "+" << K << "-" << H << "=7" << endl;
		return 0;
	}
	if (N - M - K + H == 7) {
		cout << N << "-" << M << "-" << K << "+" << H << "=7" << endl;
		return 0;
	}
	if (N - M - K - H == 7) {
		cout << N << "-" << M << "-" << K << "-" << H << "=7" << endl;
		return 0;
	}
	return 0;
}

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

int main() {
    int N,M, p;
    string s;
    int penalty = 0;
    int correct = 0;
    cin>>N>>M;
    vector<int> pena(N, 0);
    vector<bool> ac(N, false);
    REP(i, 0, M){
        cin>>p>>s;
        if(s=="WA" && !ac[p-1]){
            pena[p-1]++;
        }else if(s=="AC" && !ac[p-1]){
            ac[p-1] = true;
            correct++;
        }
    }
    REP(i, 0, N){
        if(ac[i]){
            penalty += pena[i];
        }
    }
    cout<<correct<<" "<<penalty<<endl;
}


Measured memory_bytes: 640
INF = 10**9
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
h, w = map(int, input().split())
s = [input() for _ in range(h)]
def conv_coor(i, j):
    return i*w+j
def update(i, j, d,  q):
    if dist[conv_coor(i, j)] != INF:
        return
    dist[conv_coor(i, j)] = d
    q.append((i, j))

dist = [INF]*h*w
dist[0] = 0
q = [(0,0)]
while len(q) > 0:
    current = q.pop(0)
    i = current[0]
    j = current[1]
    for direction in range(4):
        ni = i + di[direction]
        nj = j + dj[direction]
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if s[ni][nj] == "#":
            continue
        d = dist[conv_coor(i, j)]
        update(ni, nj, d+1, q)
if dist[conv_coor(h-1,w-1)] == INF:
    print(-1)
    exit()
b_num = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            b_num += 1
print(h*w-b_num-dist[conv_coor(h-1, w-1)]-1)




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



int main() {

	int n;
	int a = 0, b = 0, c = 0;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(x & 1) a++;
		else if(x % 4 == 0) c++;
		else b++;
	}

	
	if(c >= a || (c == a-1 && c + a == n)) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}

Measured memory_bytes: 256
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const S = input.slice(1, -1).map((line) => line[0]);

  S.sort();

  return S.join("");
};

console.log(main(read()));


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

int main(){
    int n;
    cin >> n;
    vector<vector<int>> node(n+1);
    for (int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }

    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];

    sort(c.begin(), c.end(), greater<int>());
    vector<bool> check(n+1, true);

    vector<int> ans(n+1);
    int now = 0;
    queue<int> q;
    q.push(1);
    check[1] = false;
    ans[1] = c[now];
    now++;

    while (q.size() > 0){
        int x = q.front(); q.pop();
        int k = (int)node[x].size();
        for (int i = 0; i < k; i++){
            if (check[node[x][i]]){
                ans[node[x][i]] = c[now];
                now++;
                check[node[x][i]] = false;
                q.push(node[x][i]);
            }
        }
    }
    cout << accumulate(c.begin(), c.end(), 0) - c[0] << endl;
    for (int i = 1; i < n; i++) cout << ans[i] << " ";
    cout << ans[n] << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n;
	cin>>n;
	ll a[100000];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	sort(a, a+n);
	ll ans=0;
	if(n%2==0){
		for(ll i=0; i<n/2-1; i++){
			ans+=(a[i+1]-a[i])*2*(i+1);
			ans+=(a[n-1-i]-a[n-2-i])*2*(i+1);
		}
		ans+=(a[n/2]-a[n/2-1])*((ll)n-1);
	}else{
		for(ll i=0; i<n/2; i++){
			ans+=(a[i+1]-a[i])*2*(i+1);
			ans+=(a[n-1-i]-a[n-2-i])*2*(i+1);
		}
		ans-=(min(a[n/2+1]-a[n/2], a[n/2]-a[n/2-1]));
	}
	cout<<ans<<endl;
    return 0;
}

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

int N,M,K;
int par[100010];
int rf[100010];
int df[100010];
int ans[100010];
void init(int n){
  for(int i=1;i<=n;i++){
    par[i] = i;
    rf[i] = 1;
  }
}
int find(int x){
  if(par[x]==x) return x;
  return par[x] = find(par[x]);
}
void unite(int x,int y){
  int nx = find(x);
  int ny = find(y);
  if(nx==ny) return;
  if(rf[nx]<rf[ny]){
    par[nx] = ny;
    rf[ny] += rf[nx];
  }else{
    par[ny] = nx;
    rf[nx] += rf[ny];
  }
  
}
bool same(int x,int y){
  return find(x)==find(y);
}
int main(){
  cin >> N >> M >> K;
  init(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin >> a >> b;
    unite(a,b);
    df[a]++; df[b]++;
  }
  for(int i=1;i<=N;i++){
    ans[i] = rf[find(i)]-df[i];
  }
  for(int i=0;i<K;i++){
    int c,d;
    cin >> c >> d;
    if(!same(c,d)) continue;
    ans[c]--;
    ans[d]--;
  }
  for(int i=1;i<=N;i++){
    cout << ans[i]-1 << endl;
  }
}

Measured memory_bytes: 5128
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
int main()
{
    int n, t, a, i, h, poz;
    float min=INT_MAX;
    cin>>n>>t>>a;
    for(i=1; i<=n; i++)
    {
        cin>>h;
        if(fabs(a-t+h*0.006) < min)
        {
            poz=i;
            min=fabs(a-t+h*0.006);
        }
    }
    cout<<poz;
    return 0;
}


Measured memory_bytes: 256
import numpy as np

def f(a, b, x):
    v = a**2*b
    if x >= v/2:
        return np.rad2deg(np.arctan((v-x)*2/a**3))
    else:
        return np.rad2deg(np.arctan((a*b**2/(x*2))))

x = map(int, input().split())
print(f(*x))

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

class convex_hull_trick {
    using T = long long;

    bool check(int f1, int f2, T aa, T bb) {
        return (a[f2] - a[f1]) * (bb - b[f2]) >= (b[f2] - b[f1]) * (aa - a[f2]);
    }
    bool check(int f1, int f2, int f3) {
        return (a[f2] - a[f1]) * (b[f3] - b[f2]) >= (b[f2] - b[f1]) * (a[f3] - a[f2]);
    }

    T f(int idx, T x) {
        return a[idx] * x + b[idx];
    }

public:
    convex_hull_trick() = default;
    convex_hull_trick(std::vector<T> const& a_, std::vector<T> const& b_) {
        assert(a_.size() == b_.size());
        for(int i = 0; i < a_.size(); ++i) {
            add_f(a_[i], b_[i]);
        }
    }

    void add_f(T aa, T bb) {
        while(a.size() >= 2 && check(a.size() - 2, a.size() - 1, aa, bb)) {
            a.pop_back();
            b.pop_back();
        }
        a.push_back(aa);
        b.push_back(bb);
    }
    T min(T x) {
        assert(a.size() > 0);
        while(a.size() >= 2 && f(0, x) >= f(1, x)) {
            a.pop_front();
            b.pop_front();
        }
        return a[0] * x + b[0];
    }

private:
    std::deque<T> a, b; // functions
};

using namespace std;

using ll = long long;

constexpr ll INF = 2e18;

int main() {
    ll s, n, m;
    cin >> s >> n >> m;
    vector<ll> d(s);
    for(int i = 0; i < s; ++i) {
        cin >> d[i];
    }
    vector<ll> x(n);
    for(int i = 0; i < n; ++i) {
        ll t, p;
        cin >> t >> p;
        x[i] = t - d[p - 1];
    }
    sort(x.begin(), x.end());
    vector<ll> sum(n + 1);
    for(int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + x[i];
    }

    vector<vector<ll>> dp(m + 1, vector<ll>(n, INF));
    vector<convex_hull_trick> cht(m + 1);
    for(int i = 0; i < n; ++i) {
        dp[1][i] = i * x[i] - sum[i];
        cht[1].add_f(-i, dp[1][i] + sum[i + 1]);
    }
    for(int i = 2; i <= m; ++i) {
        for(int j = 0; j < n; ++j) {
            if(j == 0) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = cht[i - 1].min(x[j]) + j * x[j] - sum[j + 1];
            }
            cht[i].add_f(-j, dp[i][j] + sum[j + 1]);
        }
    }
    cout << dp[m][n - 1] << endl;
}


Measured memory_bytes: 19792
#include<stdio.h>
int main(void){
int x,y,z,i,all,cou=0,cou2=0;
while(scanf("%d,%d,%d",&x,&y,&z)!=EOF){
    if(z*z==x*x+y*y)cou++;
    if(x==y){
        if(x+y<z)cou2--;
            cou2++;
    }

}
printf("%d\n%d\n",cou,cou2);
return 0;
}

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

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

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;


int main() {
   int n, k;
   cin >> n >> k;
   if(k%2==0){
       int a = n/k;
       int b = n/(k/2) - a;
       cout << (ll)(pow(a,3)+pow(b,3)) << endl;
   }else{
       int a = n/k;
       cout << (ll)pow(a,3) << endl;
   }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(int i=0;i<N;i++)
typedef long long ll;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>v(M);
	vector<int>p(M);
	int k;
	int s;
	for(int i=0;i<M;i++){
		cin>>k;
		for(int j=0;j<k;j++){
			cin>>s;
			v[i].pb(s);
		}
	}
	int P;
	for(int i=0;i<M;i++){
		cin>>P;
		p[i]=P;
	}
	int count=0;
	int hantei=0;
	bool flag=true;
	for(int bit=0;bit<(1<<N);bit++){
		for(int i=0;i<M;i++){
			if (flag==false){break;}
			hantei=0;
			for(int j=0;j<v[i].size();j++){
				if((bit&1<<(v[i][j]-1))!=0){hantei++;}//スイッチは1からなので
			}
			if (hantei%2!=p[i])flag=false;
		}
		if(flag==true){count++;}
		flag=true;
	}
	cout<<count<<endl;
}

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

struct P
{
    int x,y;

    /*bool operator<(const P &a)const{
        if(x!=a.x)
              return x>a.x;
        return y>a.y;
    }*/

};

vector<int> v;

//bitset<4001000> b;
int i,n,d,m,k,a,b,c;

int o[222221];
int l[1];
int j[1];
int e;


//int dx[10]={2,2,-2,-2,1,1,-1,-1},dy[10]={1,-1,1,-1,2,-2,2,-2};

int dx[10]={0,1,0,-1,1,1,-1,-1},dy[10]={1,0,-1,0,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
long long mod=1000000007,mod2=1000000009,mod3=2017;
long long x,z,y;
double pi=3.14159265;
P u[100333];
stack<int> s;
//set<int> s[222][22];
//priority_queue<int> q1;
queue<int> q;
//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p,p1;
/*
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<long long, int, custom_hash> safe_map;
*/
//list<int> l;

string r;
//char r[222253];
//deque<int> de;
//srand((int)time(NULL));
/*bool as(P a,P b)
{
    if(a.x!=b.x)
    return a.x<b.x;
    return a.y<b.y;
}*/



bool as(P a,P b)
{
    if(a.x!=b.x)
    return a.x<b.x;
    return a.y<b.y;
}


int main()
{
    cin>>r;
    for(int t=0;t<r.size();o[t]+=o[t-1],t++)
        if(r[t]=='B') o[t]++;
    for(int t=0;t<r.size();t++)
        if(r[t]=='W')
        x+=o[t];
    printf("%lld",x);
}






Measured memory_bytes: 1412
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)
    ans = 0
    for v in c.values():
        if v > 1:
            ans += v*(v-1)//2
    for k, a in enumerate(A):
        cnt = 0
        add = 0
        if c[a] > 1:
            cnt = c[a]*(c[a]-1)//2
        if c[a] > 2:
            add = (c[a]-1)*(c[a]-2)//2
        print(ans - cnt + add)


if __name__ == '__main__':
    main()


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

int find_parent(int i,int par[])
{
    if(i==par[i])
        return i;
        
    return par[i]=find_parent(par[i],par);
}

int main()
{
  	int n,m;
  	cin>>n>>m;
  	
  	int par[n];
  	int sz[n];
  	
  	for(int i=0;i<n;i++)
  	{
  	    par[i]=i;
  	    sz[i]=1;
  	}
  	
  	int ma=1;
  	int a,b;
  	
  	for(int i=0;i<m;i++)
  	{
  	    cin>>a>>b;
  	    a--,b--;
  	    
  	    a=find_parent(a,par);
  	    b=find_parent(b,par);
  	    
  	    if(a!=b)
  	    {
  	        par[b]=a;
  	        sz[a]+=sz[b];
  	        
  	        ma=max(ma,sz[a]);
  	    }
  	}
  	
  	cout<<ma<<endl;
  	return 0;
}

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

int main(){
   int n;
   cin >> n;
   int a[n+1];
   int input;
   for(int i = 0; i < n+1; i++){
       a[i] = 0;
   }
   for(int i = 1; i < n ; i++){
       cin >> input;
       a[input] += 1;
   }
   for(int i = 1; i < n+1; i++){
       cout << a[i] << endl;
   }
   return 0;
}

Measured memory_bytes: 4416
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramA
    {
        static void Main()
        {
            int a = NextInt;
            var s = Line;

            if (a >= 3200)
            {
                System.Console.WriteLine(s);
            }
            else
            {
                System.Console.WriteLine("red");
            }
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 13268
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int f[1000001],r1,r2,a[100001],b[100001],ans;
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    while(ch=='-') c*=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
int main() 
{
    int n,m;
    n=read();m=read();
    for(re int i=1;i<=n;i++)
    	a[i]=read(),b[a[i]]=i;
    for(re int i=1;i<=n;i++)
    	f[i]=i;
    for(re int i=1;i<=m;i++){
    	int x=read(),y=read();
    	r1=find(a[x]);r2=find(a[y]);
    	if(r1!=r2) f[r2]=r1;
    }
    for(re int i=1;i<=n;i++){
    	r1=find(i),r2=find(a[i]);
    	if(r1==r2) 
		ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1408
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

char s[maxn],t[maxn];

int main()
{
	scanf("%s",s+1); scanf("%s",t+1);
	int ls=strlen(s+1),lt=strlen(t+1),ans=inf;
	rep(i,1,ls)
	{
		int l=i,r=i+lt-1; if(r>ls) break;
		int tmp=0;
		rep(j,l,r) if(s[j]!=t[j-l+1]) tmp++;
		ans=min(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

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

int N, C[501], S[501], F[501], t;

int main() {
    cin >> N;

    for (int i = 1; i <= N - 1; ++i) {
        cin >> C[i] >> S[i] >> F[i];
    }

    for (int i = 1; i <= N - 1; ++i) {
        t = 0;

        for (int j = i; j <= N - 1; ++j) {
            if (j == i) {
                t = S[j];
                t += C[j];
            } else if (t < S[j]) {
                t = S[j];
                t += C[j];
            } else {
                int St = t - S[j];
                int Ft = St % F[j];

                if (Ft != 0) {
                    t += F[j] - Ft;
                }

                t += C[j];
            }
        }

        cout << t << endl;
    }

    cout << 0 << endl;
}


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;
const int INT_INF = 2147483647;
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; }
typedef pair<int,int> P;

const int MAX = 100005;
const int MOD = 1000000007;
ll 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;
    }
}

// 二項係数計算
ll 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;
}

int main(){
  int n,k;
  cin >> n >> k;
  int a[n];
  rep(i,n)cin >> a[i];
  sort(a,a+n);
  COMinit();
  ll mx=0;
  for(int i=n-1;i>=0;i--){
    if(i<k-1)break;
    mx += (a[i]*COM(i, k-1))%MOD;
    //cout << a[i]*COM(i, k-1) << endl;
    mx %= MOD;
  }
  ll mn=0;
  rep(i,n){
    if(n-i-1<k-1)break;
    mn += (a[i]*COM(n-i-1,k-1))%MOD;
    //cout << a[i]*COM(n-i-1,k-1) << endl;
    mn %= MOD;
  }
  ll ans = (mx-mn)%MOD;
  if(ans<0)ans += MOD;
  cout << ans << endl;
  // rep(i,n){
  //   if(i<k)
  // }
  //cout << ans << endl;
}


Measured memory_bytes: 2944
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main(){
    int H,W;
    while(true){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
}


Measured memory_bytes: 2512
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

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

        int h = sc.nextInt();
        int w = sc.nextInt();
        boolean[][] a = new boolean[h][w];

        Queue<Mass> queue = new ArrayDeque<>();
        int ans = 0;

        for (int i = 0; i < h; i++) {
            String s = sc.next();
            for (int j = 0; j < w; j++) {
                a[i][j] = s.charAt(j) == '#' ? true : false;
                if (a[i][j])
                    queue.add(new Mass(j, i, 0));
            }
        }

        int[][] b = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            Mass mass = queue.remove();
            for (int i = 0; i < b.length; i++) {
                int x = mass.x + b[i][0];
                int y = mass.y + b[i][1];
                int cnt  = mass.cnt + 1;

                if (x < 0 || x >= w || y < 0 || y >= h || a[y][x])
                    continue;

                queue.add(new Mass(x, y, cnt));
                a[y][x] = true;
                ans = Math.max(ans, cnt);
            }
        }

        System.out.print(ans);
    }

    static class Mass {
        int x;
        int y;
        int cnt;

        Mass(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

Measured memory_bytes: 68560
s = input()
ans = 0
while s:
    if s[0] == s[-1]:
        s = s[1:-1]
    elif s[0] == 'x':
        s = s[1:]
        ans += 1
    elif s[-1] == 'x':
        s = s[:-1]
        ans += 1
    else:
        ans = -1
        break
print(ans)
# https://img.atcoder.jp/code-festival-2017-qualc/editorial.pdf


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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();


    int a, b, c, d;

    cin>> a>> b>> c>> d;

    cout<< ( ((c+ b-1)/ b) > (( a+ d-1)/d) ? "No\n" : "Yes\n" );

    return 0;
}




Measured memory_bytes: 3624
from operator import itemgetter
N, M = map(int, input().split())
C = []*N
for i in range(N):
    x, y = map(int, input().split())
    C.append((x,y))
C.sort(key=itemgetter(0))

res = 0
for i,j in C:
    if M==0:
        break
    if M > j:
        res += i*j
        M -= j
    else:# M <= j
        res += i*M
        M -= M
print(res)

Measured memory_bytes: 18188
/*
 * 5/26 19:25 ~ 5/28 11:58
 * Status: Wrong Answer
 */
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

int iN;
int iHx;
int iHy;
int iDx;
int iDy;
int iCx[20];
int iCy[20];
double dCd[20];

// ú»
void init() {
}

double getDis(double x1, double y1, double x2, double y2) {
  return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

// üÍ + I¹»è
bool input() {
  int i;

  // üÍ + I¹»è
  scanf("%d %d %d %d %d", &iN, &iHx, &iHy, &iDx, &iDy);
  if (iN == 0 && iHx == 0 && iHy == 0 && iDx == 0 && iDy == 0)
    return false;
  for (i = 0; i < iN; i++) {
    scanf("%d %d", &iCx[i], &iCy[i]);
    dCd[i] = getDis(iCx[i], iCy[i], iDx, iDy);
  }
  return true;
}

void pri(bool nFlag[]) {
  int i;
  for (i = 0; i < iN; i++) {
    printf("%d ", nFlag[i]);
  }
  printf("\n");
}
// ÄAÄÑoµ
bool recur(bool nFlag[], double sum) {
  int i;
  double minD, maxH;

  //pri(nFlag);
  for (i = 0; i < iN; i++) {
    if (!nFlag[i]) {
      break;
    }
  }
  if (i == iN)
    return true;
  minD = 2000000.0; // INF
  maxH = -2000000.0; // -INF
  for (i = 0; i < iN; i++) {
    if (nFlag[i])
      continue;
    /*
     if (minD > dCd[i]) {
     minD = dCd[i];
     }
     if (maxH < getDis(iCx[i], iCy[i], iHx, iHy) + sum) {
     maxH = getDis(iCx[i], iCy[i], iHx, iHy) + sum;
     }
     */
    if (minD > dCd[i]) {
      minD = dCd[i];
      maxH = getDis(iCx[i], iCy[i], iHx, iHy) + sum;
    }
  }
  //printf("%f >= %f\n", maxH, minD);
  if (maxH >= minD) {
    return false;
  }
  //
  for (i = 0; i < iN; i++) {
    int tmpx, tmpy;
    if (nFlag[i])
      continue;
    nFlag[i] = true;
    tmpx = iHx;
    iHx = iCx[i];
    tmpy = iHy;
    iHy = iCy[i];
    if (recur(nFlag, sum + getDis(iCx[i], iCy[i], tmpx, tmpy))) {
      return true;
    }
    nFlag[i] = false;
    iHx = tmpx;
    iHy = tmpy;
  }
  //printf("sum:%f\n", sum);
  return false;
}

// 
void manage() {
  bool nFlag[iN];

  fill(nFlag, nFlag + iN, false);

  if (recur(nFlag, 0.0)) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
}

// mainÖÍCÂlIÉSâè¤Ê
int main() {
  init(); // ú»
  while (true) {
    if (!input()) // üÍ + I¹»è
      break; // I¹
    manage(); // 
  }
  return 0;
}

Measured memory_bytes: 0
import java.io.*;
import java.lang.*;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++){
            arr[i] = in.nextInt();
        }
        int count = 1;
        int max = arr[0];
        for(int i = 1; i<n; i++){
            if(arr[i]>=max){
                ++count;
                max = arr[i];
            }
        }
        out.println(count);
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return null;
        }

        public boolean hasNext() {
            String next = null;
            try {
                next = reader.readLine();
            } catch (Exception e) {
            }
            if (next == null) {
                return false;
            }
            tokenizer = new StringTokenizer(next);
            return true;
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}



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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

struct Sieve {
    i64 n;
    vector<i64> f;
    using P = pair<i64, i64>;

    Sieve(i64 n = 1) : n(n), f(n + 1, 1) {
        for (i64 i = 2; i <= n; i++) {
            if (f[i] > 1) continue;
            f[i] = 2;
            for (i64 j = i + i; j <= n; j += i) {
                i64 c = 0;
                i64 x = j;
                while (x % i == 0) {
                    x /= i;
                    c++;
                }
                f[j] *= (c + 1);
            }
        }
    }
};


int main() {
    i64 N; cin >> N;

    Sieve sieve(N);

    i64 cnt = 1;
    for (i64 k = 2; k <= N; k++) {
        cnt += k * sieve.f[k];
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 81336
n=int(input())
a,b,c=[list(map(int,input().split())) for _ in [0]*3]
from itertools import accumulate
a.sort()
b.sort()
c.sort()
a+=[10**20]
b+=[10**20]
 
p,q=0,0
cnt=0
ans=[0]*n
for i in range(n):
    for j in range(p,n+1):
        if b[i]>a[j]:
            pass
        else:
            break
    ans[i]=j
    p=j
ans=[0]+list(accumulate(ans))

for i in range(n):
    for j in range(q,n+1):
        if c[i]>b[j]:
            pass
        else:
            break
    q=j
    cnt+=ans[j]
print(cnt)

Measured memory_bytes: 24760
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := intScanner()
	if n%10 == 9 || n/10 == 9 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

int W,H;
char fie[111][111];
int res[111][111];
int main(){
  cin>> H >> W;
  memset(res,-1,sizeof(res));
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++) cin >> fie[j][i];
  for(int y=0;y<H;y++){
    for(int x=0;x<W;x++){
      int cnt = 0;
      for(int nx = x; nx>-1;nx--){
        if( fie[nx][y] == 'c' ){
          res[x][y] = cnt; break;
        }        
        cnt++;
      }
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if( j ) cout << " ";
      cout << res[j][i];
    } cout << endl;
  }
       

}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
int main() {
  int n;
  cin >> n;
  bool ans = false;
  for(int i = 1; i <= 9;i++){
    if(n%i == 0){
      if(n/i <= 9) ans = true;
    }
  }
  puts(ans ? "Yes":"No");
  }


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int  INF=10e7;

typedef  pair<int,int> P;


int main(){
     int n;
     cin>>n;
     long long t=1,a=1;
     for(int i=0;i<n;++i){
          int t1,a1;
          cin>>t1>>a1;
          long long n=max((t+t1-1)/t1,(a+a1-1)/a1);
          t=t1*n;
          a=a1*n;
     }
     cout<<t+a<<endl;
}

Measured memory_bytes: 256