akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);

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

  for (i=1; i<n; i++) {
    for (j=i; j!=0 && arr[j-1]>arr[j]; j--) {
      tmp=arr[j];
      arr[j]=arr[j-1];
      arr[j-1]=tmp;
    }

    for (k=0; k<n; k++) {
      if (k<n-1) {
        printf("%d ", arr[k]);
      } else {
        printf("%d\n", arr[k]);
      }
    }
  }
  return 0;
}


Measured memory_bytes: 2052
from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li.sort()

a = li.pop()
if len(li) == 1:
    print(a,li[0])
else:
    bi = bisect.bisect_left(li,a/2)
    b = li[bi]
    if bi != 0:
        c = li[bi-1]
        if abs(a/2-c) <= abs(a/2-b):
            print(a,c)
        else:
            print(a,b)
    else:
        print(a,b)

Measured memory_bytes: 14428
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n, k;
  cin >> n >> k;

  vll ps(n);
  rep(i, n) cin >> ps[i];
  Sort(ps);

  ll ans = accumulate(ps.begin(), ps.begin() + k, 0);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3600
a,b,c,x,y = map(int,input().split())
single = (a*x)+(b*y)
ab_pizza2 = c*max(x,y)*2
if x > y:
	ab_pizza = c*(2*y)
	x -= y
	ab_pizza += a*x
else:
	ab_pizza = c*(2*x)
	y -= x
	ab_pizza += b*y
total = min(single,ab_pizza,ab_pizza2)
print(total)

Measured memory_bytes: 9192
N=int(input())
L=list(map(int,input().split()))
from bisect import bisect_right as br
from bisect import bisect_left as bl

L.sort()

res=0
for i in range(N):
    for j in range(N):
        if not i<j:
            continue
        m=abs(L[i]-L[j])
        M=L[i]+L[j]
        r=bl(L,M)-br(L,m)
        if m<L[i]<M:
            r-=1
        if m<L[j]<M:
            r-=1
        res+=r
print(res//3)

Measured memory_bytes: 75108
N, x = map(int, input().split())
a = [int(x) for x in input().split()]

ans = 0
for i in range(N-1) :
    temp = a[i] + a[i+1]
    if temp <= x :
        continue
    elif a[i] <= x :
        ans += a[i] + a[i+1] - x
        a[i+1] -= a[i] + a[i+1] - x
    else :
        ans += a[i] + a[i+1] - x
        a[i+1] = 0
        a[i] -= a[i] - x

print(ans)


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

const int INF = 1001001001;
vector<int> to[200005];

int main()
{
    int n, m;
    cin >> n >> m;
    rep(i, 0, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    
    vector<int> dist(n, INF);
    vector<int> ans(n);
    queue<int> q;
    auto update = [&](int v, int x){
        if(dist[v] != INF) return;
        dist[v] = x;
        q.push(v);
    };
    update(0, 0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u : to[v]){
            update(u, dist[v]+1);
        }
    }
    rep(i, 1, n){
        for(int u : to[i]){
            if(dist[u] == dist[i]-1){
                ans[i] = u;
            }
        }
    }
    cout << "Yes" << endl;
    rep(i, 1, n){
        cout << ans[i]+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 13068
#include<cstdio>
int main()
{
    int N;
    scanf("%d",&N);
    int a,b;
    if(N==1)
        printf("Hello World\n");
    else if(N==2)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",a+b);
    }
    return 0;
}


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  rep(i,n) p[i]++;
  int s = 0;
  int mx = 0;
  queue<int> q;
  rep(i,n) {
    s += p[i];
    q.push(p[i]);
    if (q.size() > k){
      s -= q.front(); q.pop();
    }
    if (q.size() == k) mx = max(mx, s);
  }
  double ans = mx;
  ans /= 2;
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    cin>>n;
    vector<ll> v(n+1);
    for(int i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        v[i] = v[i-1]+x;
    }
    vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
    int diff=1;
    while(diff<n)
    {
        int r = 1;
        int c = r+diff;
        while(c<=n)
        {
            ll ans=LONG_MAX;
            for(int k=r;k<c;k++)
            {
                ans = min(ans,dp[r][k]+dp[k+1][c]+v[c]-v[r-1]);
            }
            dp[r][c] = ans;
            r++;
            c++;
        }
        diff++;
    }
    cout<<dp[1][n];
}


Measured memory_bytes: 4852
process.stdin.resume();
process.stdin.setEncoding('utf8');
 
var lines = [];
var reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});
reader.on('line', (line) => {
    // ここで入力を処理する
    lines.push(line);
});
reader.on('close', () => {
    // ここで出力する
    for(var i =0; i<lines.length; i++){
      	switch(lines[i]){
    case 'SUN':
        console.log('7');
        break;
 
 
    case 'MON':
        console.log('6');
        break;
 
 
    case 'TUE':
        console.log('5');
        break;
    

    case 'WED':
        console.log('4');
        break;
 
 
    case 'THU':
        console.log('3');
        break;
 
 
    case 'FRI':
        console.log('2');
        break;


    case 'SAT':
        console.log('1');
        break;
	}
    }
});

Measured memory_bytes: 7500
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define rep(i, n) for(int i=0; i<(n); ++i)
#define max  200001

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    int n, p[max];
    int amax=INT_MIN, ans=0;
    
    scanf("%d", &n);
    rep(i, n){
        scanf("%d", &p[i]);
        if (amax<p[i]) {
            amax=p[i];
        }
        ans+=p[i];
    }
    
    printf("%d", ans-amax/2);
    
    return 0;
}


Measured memory_bytes: 1724
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string S;
int ans[100005];

int main(){
  cin >> S;
  int cnt1 = 0, cnt2 = 0;
  int n = S.size();
  int tmp1 = 0, tmp2 = 0;
  S[-1] = 'R';
  S[n] = 'L';  
  for(int i = 0; i <= n; ++i){
    if((S[i] == 'R' && S[i - 1] == 'L') || (i == n)){
      if((cnt1 + cnt2) % 2 == 0){
        ans[tmp1] = (cnt1 + cnt2) / 2;
        ans[tmp2] = (cnt1 + cnt2) / 2;
        //cout << i << endl;
      }else{
        int s = max(cnt1, cnt2);
        if(s % 2 == 0){
          if(cnt1 < cnt2){
            ans[tmp1] = ((cnt1 + cnt2) + 1) / 2;
            ans[tmp2] = ((cnt1 + cnt2) - 1) / 2;
            //cout << i << endl;
          }else{
            ans[tmp1] = ((cnt1 + cnt2) - 1) / 2;
            ans[tmp2] = ((cnt1 + cnt2) + 1) / 2;
            //cout << i << endl;
          }
        }else{
          if(cnt1 < cnt2){
            ans[tmp1] = ((cnt1 + cnt2) - 1) / 2;
            ans[tmp2] = ((cnt1 + cnt2) + 1) / 2;
          }else{
            ans[tmp1] = ((cnt1 + cnt2) + 1) / 2;
            ans[tmp2] = ((cnt1 + cnt2) - 1) / 2;
          }
          
        }
      }
      cnt1 = 0;
      cnt2 = 0;
    }
    if(S[i] == 'R'){
      cnt1++;
      tmp1 = i;
      tmp2 = tmp1 + 1;
    }
    if(S[i] == 'L'){
      cnt2++;
    }
  }
  for(int i = 0; i < n; ++i){
    cout << ans[i] << " ";
  }
  cout << endl;
}

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

using namespace std;

int main() {
  int n, source_len, sign_len, count = 0, suffix;
  string source, sign;

  cin >> n >> source;
  source_len = source.length();

  bool success;
  for (int i = 0; i < n; i++) {
	cin >> sign;
	sign_len = sign.length();
	success = false;
	for (int j = 0; j < sign_len; j++) { //先頭文字のループ
	  for (int k = 0; k <= sign_len / 2; k++) { //間隔のループ
		for (int l = 0, suffix = j; l < source_len; l++) { //文字のループ
		  if (source[l] != sign[suffix]) {
			break;
		  }
		  if (l == source_len - 1) {
			success = true;
			count++;
			break;
		  }
		  if ((suffix += k + 1) >= sign_len) break;
		}
		if (success) break;
	  }
	  if (success) break;
	}
  }

  cout << count << endl;

  return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> v(n-1);
  for(int i=0; i<n-1; ++i) cin >> v[i];
  vector<int> ans(n);
  ans[0] = v[0];
  ans[n-1] = v[n-2];
  for(int i=1; i<n-1; ++i){
    ans[i] = min(v[i-1],v[i]);
  }
  int cnt = 0;
  for(int i=0; i<n; ++i) cnt += ans[i];
  cout << cnt << endl;
}

Measured memory_bytes: 3604
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <math.h>
using namespace std;
#define ll long long int

int main(void)
{
	int a, b, d, g, count = 0;
	string l, m, n ;
	
	vector<int> vec(3);
	map<char, int> mp;

	for (int i = 0;i < 3;i++)
	{
		cin >> vec[i];
		count += vec[i];
	}	

	if (count <= 21)
	{
		cout << "win" << endl;
	}
	else
	{
		cout << "bust" << endl;
	}
	
	
}

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

int main() {
  string N;
  cin >> N;
  int sum = 0;
  for(int i; i < N.size(); i++){
    string s = N.substr(i,1);
    sum += stoi(s);
  }
  if(sum != 0){
    if( stoi(N) % sum == 0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	static FastReader input = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);

	static int n;
	static double[] pHead;
	static double[][] memo;
	static boolean[][] visited;

	static double solve(int i, int heads) {
		if (i >= n) {
			if (heads > n - heads) {
				return 1;
			} else {
				return 0;
			}
		}

		if (visited[i][heads]) {
			return memo[i][heads];
		}
		visited[i][heads] = true;

		return memo[i][heads] = pHead[i] * solve(i + 1, heads + 1) + ((1 - pHead[i]) * solve(i + 1, heads));

	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		n = input.nextInt();
		pHead = new double[n];
		memo = new double[n + 10][n + 10];
		visited = new boolean[n + 10][n + 10];

		for (int i = 0; i < n; i++) {
			pHead[i] = input.nextDouble();
		}

		System.out.println(solve(0, 0));

	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			String str = "";
			str = br.readLine();
			return str;
		}
	}
}


Measured memory_bytes: 130860
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 303+5;
void solve(){
	string s; 
	cin>>s; 
	int n = s.size();
	for(int i=1;i<n;i++){
		if(s[i]==s[i-1]){
			cout<<i<<" "<<i+1<<endl;
			return ;
		}
	}
	for(int i=2;i<n;i++){
		if(s[i]==s[i-2]){
			cout<<i-1<<" "<<i+1<<endl;
			return ;
		}
	}
	cout<<-1<<" "<<-1<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
    ll n;
    cin >> n;
    ll ans = n*(n-1)/2LL;
    cout << ans << endl;
    return 0;
}

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

#define ll double

int main()
{
    int n,m;
    cin>>n>>m;
    ll a[n],sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }   
    double save = (sum/(4*m));
    int c=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>=save)
            c++;
    }
    if(c>=m)
        cout<<"Yes";
    else
    {
        cout<<"No";
    }
    
    return 0;
}

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

using i64 = int64_t;

i64 base_n(i64 n, i64 m){
    i64 res = 0;
    while(m > 0){
        res += m % n;
        m /= n;
    }
    return res;
}

int main(){
    i64 n;
    cin >> n;
    i64 ans = n;
    for(i64 i=0;i<=n;++i){
        ans = min(ans, base_n(6, i)+base_n(9, n-i));
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int N, M; cin >> N >> M;
  int dist[100][100]; rep(i, 100) rep(j, 100) dist[i][j] = i == j ? 0 : inf;
  using Edge = tuple<int, int, int>;
  vector<Edge> edges;
  rep(i, M) {
    int a, b, c; cin >> a >> b >> c; a--, b--;
    dist[a][b] = dist[b][a] = c;
    edges.emplace_back(a, b, c);
  }
  rep(k, N) rep(i, N) rep(j, N) {
    if (dist[i][k] != inf && dist[k][j] != inf) {
      minimize(dist[i][j], dist[i][k] + dist[k][j]);
    }
  }
  set<Edge> st;
  rep(i, N) {
    for (auto const& e: edges) {
      int a, b, c; tie(a, b, c) = e;
      if ((dist[i][b] == dist[i][a] + c) ||
          (dist[i][a] == dist[i][b] + c)) {
        st.insert(e);
      }
    }
  }
  cout << M - (int)st.size() << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using i64 = int64_t;
using ll = long long;
const ll MAX = 1e15 + 1;
int main() {
  ll sum=0,N,Q;
  cin >> N;
  vector<ll> A(N);
  map<ll,ll> list;
  rep(i,N){
    cin >> A.at(i);
    sum += A.at(i);
    if(list.count(A.at(i))){
      list.at(A.at(i)) ++;
    }
    else{
      list[A.at(i)] = 1;
    }
  }
  cin >> Q;
  rep(i,Q){
    ll B,C;
    cin >> B >> C;
    if(list.count(B)){
      sum += (C - B)* list.at(B);
      if(list.count(C)){ 
        list.at(C) += list.at(B);
        list.erase(B);
      }
      else{
        list[C] = list.at(B);
        list.erase(B);
      }
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 7924
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, R = [int(x) for x in input().split()]
    if N >= 10:
        print(R)
    else:
        print(100 * (10 - N) + R)
    
    

if __name__ == '__main__':
    main()



Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  char s[100002];
  cin>>s;
 
  int len = strlen(s);
 
  char stk[len+2];
  int i=0,top=-1;
  while(s[i])
  {
 
    if(top==-1)
      stk[++top]=s[i];
    else
    {
      if(stk[top]==s[i])
        stk[++top]=s[i];
      else
        top--;
    }
    i++;
  }
 
    cout<<len-top-1<<endl;
 
}
 

Measured memory_bytes: 384
X = int(input())
tmp = [0]*(10**5+107)
tmp[0] = 1
S = [i for i in range(100, 106)]
for i in range(10**5+1):
    for j in S:
        tmp[i+j] = tmp[i]+tmp[i+j]
if tmp[X] > 0:
    print(1)
else:
    print(0)

Measured memory_bytes: 67420
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll n,k;
cin >> n >> k;
ll d[k];
map<ll, bool> mp;
for (ll i = 0; i < k;i++){
    cin >> d[i];
    for (ll j = 0; j < d[i];j++){
        ll t;
        cin >> t;
        mp[t] = true;
    }
}
    cout << n-mp.size() << endl;
}


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

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

	int cnt=0;
	for(int i=0;i<N;i++){
 	int h;
 	cin >> h;
 	if(h>=K) cnt++;
	}
  	
  	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007;
//ユークリッドの互除法
int LCM(int a,int b){
    int x=a*b;
    int tmp;
    if(a<b){
        tmp=a;
        a=b;
        b=tmp;
    }
    int r;
    r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a*b;
    }
    return x/b;
}
//最大公約数
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
signed main(){
    string s,t;
    cin>>s>>t;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    if(s<t){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<class I,class V=typename I::value_type>V sum_up(const I&l,const I&r){V v;for(I i=l;i!=r;i++)v=i==l?*i:v+*i;return v;}
template<class I,class T=iterator_traits<I>>I operator+(I it,int n){for(int i=0;i<n;i++)it++;return it;}
template<class I,class T=iterator_traits<I>>I operator-(I it,int n){for(int i=0;i<n;i++)it--;return it;}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int x;fixprec(int d):x(d){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.x);}
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }
/*!* [union_find] *!*/
/*+* UnionFind 木 *+*/
// T (typename) : グラフの頂点を表す型, (int)parent を持つ必要あり
template <typename T>
struct UnionFind {
    vector<T> &u;
    UnionFind(vector<T> &u) : u(u) {
        for (int i = 0; i < u.size(); i++) {
            u[i].parent = i;
            u[i].edge_num = 0;
        }
    }
    int root(int x) {
        if (x < 0 || u.size() <= x) return -1;
        else if (x == u[x].parent) return x;
        else return u[x].parent = root(u[x].parent);
    }
    bool connect(int a, int b) {
        a = root(a), b = root(b);
        bool retval = a != b;
        if (retval) {
            u[a].X += u[b].X;
            u[a].Y += u[b].Y;
            u[a].edge_num += u[b].edge_num;
        }
        u[a].edge_num++;
        u[b].parent = a;
        return retval;
    }
};

struct Node {
    int parent;
    int X, Y;
    int edge_num;
};

int main() {
    int N;
    cin >> N;
    const int V = 2e5;
    vector<Node> uf(V);
    for(int i = 0; i < V; i++) {
        uf[i].X = i < V / 2 ? 1 : 0;
        uf[i].Y = i < V / 2 ? 0 : 1;
    }
    UnionFind<Node> uf_tree(uf);
    for(int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        y += 1e5;
        uf_tree.connect(x, y);
    }
    i64 ans = 0;
    for(int i = 0; i < V; i++) {
        if(uf_tree.root(i) == i) {
            i64 x = uf[i].X, y = uf[i].Y, e = uf[i].edge_num;
            ans += x * y - e;
        }
    }
    cout << ans << endl;
    return 0;
}




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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,x=0;
    cin>>n;
    vector<int> v(n),v1(n);
    for(int i=0;i<n;i++) {
      cin>>v[i];
      v1[i]=v[i];
    }
    sort(v1.begin(),v1.end());
    for(int i=0;i<n;i++) {
      if(v[i]!=v1[i]) x++;
    }
    if(x<=2) cout<<"YES";
    else cout<<"NO";
    return 0;
}

Measured memory_bytes: 256
'use strict';
class Queue {
    constructor(size) {
        this.arr = new Array(size);
        this.head = this.tail = 0;
    }
    is_full() {
        return this.head == (this.tail + 1) % this.arr.length;
    }
    push(v) {
        if (this.is_full()) {
            this.arr.length *= 2;
        }
        this.arr[this.tail] = v;
        this.tail = (this.tail + 1) % this.arr.length;
    }
    is_empty() {
        return this.head == this.tail;
    }
    pop() {
        if (this.is_empty()) {
            throw -1;
        }
        let v = this.arr[this.head];
        this.head = (this.head + 1) % this.arr.length;
        return v;
    }
    maxsize() {
        return this.arr.length;
    }
}
function main(input) {
    let lines = input.split('\n');
    let v = lines[0].split(' ').map((n) => parseInt(n));
    let h = v[0];
    let w = v[1];
    let c = [];
    let d = [];
    for (let i = 1; i < h + 1; i++) {
        c.push(lines[i]);
        d.push([]);
    }
    let q = new Queue(1000000);
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            if (c[i][j] == '#') {
                q.push([i, j]);
                d[i][j] = 0;
            }
            else {
                d[i][j] = -1;
            }
        }
    }
    let p = q.pop();
    let max = 0;
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];
    while (true) {
        const xx = p[0];
        const yy = p[1];
        for (let i = 0; i < 4; i++) {
            let x = xx + dx[i];
            let y = yy + dy[i];
            if (x < 0 || x > h - 1 || y < 0 || w - 1 < y || d[x][y] >= 0) {
                continue;
            }
            if (c[x][y] == '.') {
                q.push([x, y]);
                let count = d[xx][yy] + 1;
                if (max < count) {
                    max = count;
                }
                d[x][y] = count;
            }
        }
        if (q.is_empty()) {
            break;
        }
        p = q.pop();
    }
    console.log(max);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int main(){
  int n;
  scanf("%d",&n);
  int a[120000];
  int cntx[100100]={};
  int cnty[100100]={};
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    if(i%2!=0){
      cntx[a[i]]++;
    }else{
      cnty[a[i]]++;
    }
  }
  int tmp=0;
  int tmpp=0;
  int tmps=0;
  int tmpps=0;
  int m,mm;
  for(int i=0;i<=100000;i++){
    if(cntx[i]>=tmp){
      tmps=tmp;
      tmp=cntx[i];
      m=i;

    }else{
      if(cntx[i]>=tmps){
        tmps=cntx[i];
      }
    }
    if(cnty[i]>=tmpp){
      tmpps=tmpp;
      tmpp=cnty[i];
      mm=i;

    }else{
      if(cnty[i]>=tmpps){
        tmpps=cnty[i];
      }
    }
  }
  int ans=n-tmp-tmpp;
  if(m==mm){
    if(ans==0){
      printf("%d",n/2);
    }else{
      int a=n-tmp-tmpps;
      int b=n-tmps-tmpp;
      printf("%d",min(a,b));
    }

  }else{
    printf("%d",ans);
  }
}


Measured memory_bytes: 1408
import sys
O = str(input())
E = str(input())
# print(O)
# print(E)
O_array = list(O)
E_array = list(E)
# print(O_array)
# print(E_array)
if not O.islower() or not E.islower():
    sys.exit()
if len(O) < 0 or len(O) > 50 or len(E) < 0 or len(E) > 50:
    sys.exit()
diff_length = len(O) - len(E)
if not (diff_length == 0 or diff_length == 1):
    sys.exit()

for e in range(len(E)):
    print(O[e], end='')
    print(E[e], end='')
if diff_length == 1:
    print(O[-1])
else:
    print('')

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

#define F first
#define S second
#define MP make_pair
#define PB emplace_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1;

long long int a[N];

int main () {
    IOS;
    int n, k, x;
    cin >> n >> x >> k;
    int nw = 0, ans = 0;
    while(nw < n) {
        nw+=x;
        ans+=k;
    }
    cout << ans;
}


Measured memory_bytes: 3644
import std.algorithm;
import std.array;
import std.ascii;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

bool calc(int a, int b, string s) {
    if (s[a] != '-') return false;

    for (int i = 0; i < s.length; i++) {
        if (i == a) continue;
        if (!isDigit(s[i])) return false;
    }
    return true;
}

void main() {
    auto ab = readints;
    int a = ab[0], b = ab[1];
    auto s = read!string;

    writeln(calc(a, b, s) ? "Yes" : "No");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll m1, m2, d1, d2;
    cin >> m1 >> d1 >> m2 >> d2;

    if(m1 != m2){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
/*+lmake
 * STD = c++14
 * DEFINE += MDEBUG
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

void solve(long long N, vector<long long> A){
	vector<LL> b,c;
	int n=1;
	b.push_back(0);
	c.push_back(0);
	for(int i=0; i<N; ++i) {
		if (A[i]==0 && b[n-1]==0) {
				c[n-1]++;
		} else {
			b.push_back(A[i]);
			c.push_back(1);
			++n;
		}
	}
	LL ans=0;
	for(int i=0; i<n; ++i) {
		ans+=c[i]*(c[i]+1)/2;
	}
	for(int i=0; i<n; ++i) {
		int t=b[i];
		LL x=0;
		for(int j=i+1; j<n; ++j) {
			if ((b[j]&t)>0) break;
			t|=b[j];
			x+=c[j];
		}
		ans+=c[i]*x;
	}	
	cout<<ans<<endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
	}
	solve(N, A);
	return 0;
}



Measured memory_bytes: 6764
#include<stdio.h>

int main(){
  int i=0,a,b,c,x;
  scanf("%d %d %d",&a,&b,&c);
  for(x = a;x<=b;x++){
    if(c%x == 0){
      i++;  
    }
  }
  printf("%d\n",i);
}

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

int main(){
    int N;
    cin >> N;
    int a[N], b[N];
    for(int i = 0; i < N; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a, a+N);
    for(int i = 0; i < N; i++){
        if(b[i] <= a[N/2-1]) cout << a[N/2] << endl;
        else cout << a[N/2-1] << endl;
    }
    
    return 0;
}

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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

int main(){
    ll N; cin>>N;
    vec_ll A(N), B(N);
    vec_ll A_sorted(N), B_sorted(N);
    rep(i,N){
        cin>>A.at(i)>>B.at(i);
        A_sorted.at(i) = A.at(i);
        B_sorted.at(i) = B.at(i);
    }

    sort(A_sorted.begin(),A_sorted.end());
    sort(B_sorted.begin(),B_sorted.end());


    if(N%2==1){
        //奇数の時に中央値の取りうる範囲は、
        //A_sorted.at((N-1)/2) ~ B_sorted.at((N-1)/2)
        cout<<B_sorted.at((N-1)/2)-A_sorted.at((N-1)/2)+1<<endl;
    }else{
        //偶数の時にとりうる中央値の範囲は、
        //N/2とN/2+1のとりうる範囲をそれぞれ決めて、その二つで考えればよい
        ll a1 = A_sorted.at(N/2-1);
        ll a2 = A_sorted.at(N/2);
        ll b1 = B_sorted.at(N/2-1);
        ll b2 = B_sorted.at(N/2);
        //中央値の最小値は(a1+a2)/2, 最大値は(b1+b2)/2
        //そこまでの間1/2ずつ進めばよい
        cout<<(b1+b2)-(a1+a2)+1<<endl;



    }


    return 0;
}

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

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

// 解説放送より：普通のDFSを用いて累積和をとっていく方法

vector<vi> g;
vi ans;
void dfs(int v, int p=-1) {
    ans[v] += ans[p];
    for (int t : g[v]) {
        if (t == p) continue;
        dfs(t, v);
    }
}

int main(){
    int n, q;
    cin >> n >> q;
    g.resize(n);
    ans.resize(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    rep(i, q) {
        int p, x;
        cin >> p >> x;
        --p;
        ans[p] += x;
    }
    dfs(0);
    rep(i, n) printf("%d%c", ans[i], (i<n-1?' ':'\n'));
    return 0;
}


Measured memory_bytes: 24324
#include<bits/stdc++.h>
using namespace std;
int main(){

    int a, b, c; cin >> a >> b >> c;

    int r = a/(b+c);
    int m = a%(b+c);

    if( m >= c ){
        cout << r << '\n';
    }else{
        cout << r-1 << '\n';
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


void solve()
{
	int A, B;
	cin >> A >> B;
	if (B % A == 0)
	{
		cout << A + B << endl;
	}
	else
	{
		cout << B - A << endl;
	}
}

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

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

typedef long long ll; // -9,223,372,036,854,775,808 から 9,223,372,036,854,775,807

template <class T> using vec = std::vector<T>;
template <class T> using vec2 = vec<vec<T>>;
template <class T> using vec3 = vec<vec<vec<T>>>;

#define DEBUG


bool isOk(long long N, long long K, std::vector<long long> A, std::vector<long long> F, ll val){
    ll ops = 0;
    for(int i=0; i < N; i++){
        // A.at(i)*F.at(i) <= valとなるようA.at(i)を調整する必要がある。
        // つまり、A.at(i) <= val/F.at(i)となるようにする必要があり、
        // A.at(i) > val/F.at(i) のときにはval/F.at(i)-A.at(i)だけ左辺にたしてそうする。opsもたす
        if(A.at(i) > val/F.at(i)){
            ops += abs(val/F.at(i) - A.at(i));
        }
    }

    return ops <= K;
}

void solve(long long N, long long K, std::vector<long long> A, std::vector<long long> F){
    sort(A.begin(), A.end());
    auto cmp = [](ll a, ll b){return a > b;};
    sort(F.begin(), F.end(), cmp);

    ll inf = 0;
    for(int i=0; i < N; i++){
        inf = max(inf, A.at(i)*F.at(i));
    }

    ll ng = -1;
    ll ok = inf + 1;
    while(abs(ok - ng) > 1){
        ll piv = (ok + ng)/2;
        if(isOk(N, K, A, F, piv)){
            ok = piv;
        }else{
            ng = piv;
        }

    }

    cout << ok << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> F(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&F[i]);
    }
    solve(N, K, std::move(A), std::move(F));
    return 0;
}


Measured memory_bytes: 6608
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <cstring>
#define INF 1e9
using namespace std;

typedef pair<int,int> P;
struct edge{
	int to,cap,cost,rev;
	edge(int t,int ca,int co,int r){
		to=t;
		cap=ca;
		cost=co;
		rev=r;
	}
};
int V;
vector<edge> G[200];
int h[201];
int dist[201];
int prevv[201],preve[201];

void add_edge(int from,int to,int cap,int cost){
	G[from].push_back(edge(to,cap,cost,G[to].size()));
	G[to].push_back(edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int s,int t,int f){
	int res=0;
	fill(h,h+V,0);
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > que;
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF)return -1;
		for(int v=0;v<V;v++){
			h[v]+=dist[v];
		}
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}

int n,m,b;
int ax[101],ay[101];
int indist[101][6];
int bx[6],by[6],c[6],f[6];

int make_graph(int bit,int d){
	V=2+n+m*2;
	for(int i=0;i<2+n+m*2;i++)G[i].clear();
	for(int i=0;i<n;i++){
		add_edge(0,2+i,1,0);
		for(int j=0;j<m;j++){
			if(bit>>j & 1){
				int adcost=0;
				if(indist[i][j]>d)adcost=(indist[i][j]-d);
				add_edge(2+i,2+n+j,1,adcost);
			}
		}
	}
	for(int i=0;i<m;i++){
		add_edge(2+n+i,2+n+m+i,c[i],0);
		add_edge(2+n+m+i,1,c[i],0);
	}
	return min_cost_flow(0,1,n);
}

int res;

int dicide_d(int bit){
	int fcost=0;
	int allcap=0,cnt=0;
	for(int i=0;i<m;i++){
		if(bit>>i & 1){
			fcost+=f[i];
			allcap+=c[i];
			cnt++;
		}
	}
	if(allcap<n || res<fcost)return -1;
	int l=0,r=4001;
	/*
	for(int i=0;i<25;i++){
		int ddl=(l*2+r)/3,ddr=(l+r*2)/3;
		int dl=make_graph(bit,(l*2+r)/3)+ddl*b*cnt;
		if(l*b*cnt+fcost>res)return -1;
		int dr=make_graph(bit,(l+r*2)/3)+ddr*b*cnt;
		if(dl>dr)l=(l*2+r)/3;
		else r=(l+r*2)/3;
	}
	*/
	for(int i=0;i<16;i++){
		int m=(l+r)/2;
		int dm=make_graph(bit,m);
		int dm1=make_graph(bit,m+1);
		if(dm>=b*cnt+dm1)l=m;
		else r=m+1;
	}
	return fcost+min(make_graph(bit,(l*2+r)/3)+((l*2+r)/3)*b*cnt,make_graph(bit,(l+r*2)/3)+((l+r*2)/3)*b*cnt);
}

int main(void){
	while(1){
		scanf("%d %d %d",&n,&m,&b);
		if(n+m+b==0)break;
		for(int i=0;i<n;i++){
			scanf("%d %d",&ax[i],&ay[i]);
		}
		for(int i=0;i<m;i++){
			scanf("%d %d %d %d",&bx[i],&by[i],&c[i],&f[i]);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				indist[i][j]=abs(ax[i]-bx[j])+abs(ay[i]-by[j]);
			}
		}
		res=INF;
		for(int i=1;i<(1<<m);i++){
			int icost=dicide_d(i);
			if(icost!=-1)res=min(res,icost);
		}
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 1076
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
	int A,B;
	cin >> A >> B;
	int N;
	cin >> N;
	vector<int> V(1003,0);
	bool result = false;
	for(int a = 0;a < N;a++){
		int s,f;
		cin >> s >> f;
		for(int i = s; i < f; ++i)
			++V[i];
	}
	for(int i = A; i < B; ++i)
		if(V[i])result = 1;
	cout<<(result?1:0)<<endl;
}



Measured memory_bytes: 3072
import copy

def bubble_sort(n, c):
  for i in range(n):
    for j in reversed(range(i + 1, n)):
      if int(c[j][1:]) < int(c[j - 1][1:]):
        c[j], c[j - 1] = c[j - 1], c[j]
  return c

def selection_sort(n, c):
  for i in range(n):
    minj = i
    for j in range(i, n):
      if int(c[j][1:]) < int(c[minj][1:]):
        minj = j
    if i != minj:
      c[i], c[minj] = c[minj], c[i]
  return c

n = int(input())
c = [i for i in input().split()]
c1 = bubble_sort(n, copy.copy(c))
c2 = selection_sort(n, copy.copy(c))

print(*c1)
print('Stable')
print(*c2)
print('Stable' if c1 == c2 else 'Not stable')



Measured memory_bytes: 6348
import math

N,K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

if K >= sum(A):
    print(0)
    exit()

A.sort(reverse=True)
F.sort()

def is_ok(mid):
    cnt = 0
    for i in range(N):
        if A[i] * F[i] <= mid:
            continue
        else:
            cnt += math.ceil((A[i] * F[i] - mid) / F[i]) # A[i]が1減少するごとにF[i]減るのでF[i]で割る  
    
    return cnt <= K

# okは全員がX以下になる最小値に着地するので、A*F<=10**12 なので＋１して最大のケースにも対応する
ok = 10**12 + 1
# 0ではないことが上で保証されてるので、条件を満たさない最大値の0にしておく
ng = 0
while ok - ng > 1:
    
    mid = (ok + ng) // 2
    #print(ok,ng,mid)
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

#print(ok,ng,mid)
print(ok)

Measured memory_bytes: 119500
#define _USE_MATH_DEFINES
#include<iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
	int n;
	vector<int> a;
	cin >> n;

	int min[8], max[8];
	
	for (int i = 0; i < 8; i++){
		min[i] = 400 * i;
		max[i] = 400 * (i+1)-1;
	}
	min[0] = 1;

	for (int i = 0; i < n; i++){
		int num;
		cin >> num;
		a.push_back(num);
	}

	sort(a.begin(), a.end());

	int color = 0;
	int k = 0;
	for (int colori = 0; colori < 8; colori++){
		for (int i = 0; i < n; i++){
			if (min[colori] <= a[i] && a[i] <= max[colori]){
				k = i;
				color++;
				break;
			}
		}
	}
	for (int i = k; i < n; i++){
		if (a[i]>max[7]){
			break;
		}
		k = i;
	}

	int mincolor = color;
	int maxcolor = color + (n - k-1);

	if (mincolor > 0){
		cout << mincolor << " " << maxcolor;
	}
	else{
		cout << mincolor+1 << " " << maxcolor+1;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

int main() {
    string E[1000];

    int n=0;
    while(cin>>E[n]){
        n++;
    }
//    for(int i=0; i<n; i++){
//        cout<<E[i]<<" ";
//    }
    
    int B[1000]={0};
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++){
            if(E[i]==E[j]){
                B[i]++;
            }
        }
    }
    
    int max=0;
    int max_num=0;
    for(int i=0; i<n; i++){
        if(B[i]>max){
            max=B[i];
            max_num=i;
        }
    }
    cout<<E[max_num]<<" ";
    
    max=0;
    max_num=0;
    for(int i=0; i<n; i++){
        if((int)E[i].length()>max){
            max=(int)E[i].length();
            max_num=i;
        }
    }
    cout<<E[max_num]<<endl;
    return 0;
}

Measured memory_bytes: 1196
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N;
    double a;
    vector<double> table;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a;
        table.push_back(a);
    }
    for(int i=0;i<N-1;i++){
        sort(table.begin(),table.end());
        double min=table[0];
        double min2=table[1];
        table.push_back((min+min2)/2.0);
        table.erase(table.begin());
        table.erase(table.begin());
    }
    cout << table[0];
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    while(true){
        int N;cin>>N;if(!N)break;
        vl a(100000);
        rep(i,N){
            string S;cin>>S;
            int h=(S[0]-'0')*10+(S[1]-'0'),m=(S[3]-'0')*10+(S[4]-'0'),s=(S[6]-'0')*10+(S[7]-'0');
            a[(h*60+m)*60+s]++;
            cin>>S;
            h=(S[0]-'0')*10+(S[1]-'0'),m=(S[3]-'0')*10+(S[4]-'0'),s=(S[6]-'0')*10+(S[7]-'0');
            a[(h*60+m)*60+s]--;
        }
        rep(i,90000){
            a[i+1]+=a[i];
        }
        ll ans=0;
        rep(i,100000)ans=max(ans,a[i]);
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3936
N,X=(int(T) for T in input().split())
A=list(map(int,input().split()))
ans=0
for i in range(0,N-1):
    if A[i]+A[i+1]>X:
        s=A[i]+A[i+1]-X
        ans=s+ans
        A[i]=A[i]-max(0,A[i]-A[i+1])
        A[i+1]=max(0,A[i+1]-s)
print(ans)


Measured memory_bytes: 20100
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int mod = 1e9 + 7;

int main()
{
  string s;
  int k, n;
  cin >> n >> k >> s;
  s[--k] |= 0x20;
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq[101];

int main()  {

    int t, idx = 0;
    char str[31];
    map<string, int> m;
    string stra;

    while(scanf("%s %d", str, &t) != EOF) {
        stra = str;
        if (stra == ".") break;
        if (m.find(stra) == m.end()) {
            m.insert({stra, idx});
            pq[idx++].push(t);
        } else {
            pq[m[stra]].push(t);
        }
    }

    for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << it->first << endl;
        idx = 0;
        while (!pq[it->second].empty()) {
            if (idx) cout << " ";
            cout << pq[it->second].top(); pq[it->second].pop();
            idx++;
        }
        cout << endl;
    }


    return 0;
}



Measured memory_bytes: 3204
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,p):
        return n * (100+p) // 100

    while True:
        x,y,s = LI()
        if x == 0:
            break
        a = set()
        m = -1
        for i in range(1,s):
            for j in range(i,s):
                u = f(i,x) + f(j,x)
                if u > s:
                    break
                if u == s:
                    t = f(i,y) + f(j,y)
                    if m < t:
                        m = t
        rr.append(m)

    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9052
B = "#"
W = "."
INF = 10000000

h, w = gets.split.map(&:to_i)
s = Array.new(h).map{Array.new(w)}
for i in 0..(h-1)
  s[i] = gets.chomp.split("")
end

a = Array.new(h).map{Array.new(w,0)}
a[0][0] = 1 if s[0][0] == B
for i in 1..([h,w].max-1)
  if i <= h-1
    for j in 0..([i-1,w-1].min)
      (s[i-1][j]==W && s[i][j]==B) ? (dw=a[i-1][j]+1):(dw=a[i-1][j])
      if j > 0 && j < w
        (s[i][j-1]==W && s[i][j]==B) ? (ri=a[i][j-1]+1):(ri=a[i][j-1])
      else
        ri = INF
      end
      a[i][j] = [dw,ri].min
    end
  end
  if i <= w-1
    for j in 0..([i-1,h-1].min)
      if j > 0 && j < h
        (s[j-1][i]==W && s[j][i]==B) ? (dw=a[j-1][i]+1):(dw=a[j-1][i])
      else
        dw = INF
      end
      (s[j][i-1]==W && s[j][i]==B) ? (ri=a[j][i-1]+1):(ri=a[j][i-1])
      a[j][i] = [dw,ri].min
    end
  end
  x = [i,w-1].min
  y = [i,h-1].min
  if x > 0
    (s[y][x-1]==W && s[y][x]==B) ? (dw=a[y][x-1]+1):(dw=a[y][x-1])
  else
    dw = INF
  end
  if y > 0
    (s[y-1][x]==W && s[y][x]==B) ? (ri=a[y-1][x]+1):(ri=a[y-1][x])
  else
    ri = INF
  end
  a[y][x] = [dw,ri].min
end
puts a[h-1][w-1]

Measured memory_bytes: 4860