akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;

class Myon
{
    static Scanner cin;
    public Myon() { }
    public static int Main()
    {
        //Console.SetOut(new Printer(Console.OpenStandardOutput()));
        cin = new Scanner();
        new Myon().calc();
        return 0;
    }


    public void calc()
    {
        int n = cin.nextInt(), m = cin.nextInt();
        int[] a = new int[m], b = new int[m];
        for(int i = 0;i<m;i++) { a[i] = cin.nextInt();b[i] = cin.nextInt(); }

        for(int i= 0; i < n; i++)
        {
            int count = 0;
            for(int j = 0; j < m; j++)
            {
                if (a[j] == i + 1 || b[j] == i + 1) count++;
            }
            ShowL($"{count}");
        }

    }

    void ShowL(string s)
    {
        Console.WriteLine(s);
    }
    
}

class Printer : StreamWriter
{
    public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
    public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
    public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { }
}

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        while (i >= s.Length)
        {
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
        }
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

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

int main() {
  long long a,b,c,k;
  cin >> a >> b >> c >> k;
  if (a >= k) {
    cout << k <<endl;
  }
  else if (a+b >= k) {
    cout << a <<endl;
  }
  else {
    cout << a-(k-a-b) <<endl;
  }
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int n, c;
    cin>>n>>c;
    vector<vector<pair<int, int> > > v(c);
    rep(i, n){
        int s, t, ch;
        cin>>s>>t>>ch;
        --ch;
        v[ch].push_back(make_pair(s, t));
    }
    map<int, int> mp;
    rep(ch, c){
        map<int, int> now;
        rep(i, v[ch].size()){
            int s = v[ch][i].first;
            int t = v[ch][i].second;
            for(int j = s;j<=t;j++){
                now[j] = 1;
            }
        }
        for(auto p : now){
            mp[p.first]+=p.second;
        }
    }
    int ans = 0;
    for(auto p : mp){
        ans = max(ans, p.second);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 10624
import java.util.*;

public class Main {
	private static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String a = sc.next().substring(0,1);
		String b = sc.next().substring(0,1);
		String c = sc.next().substring(0,1);
		System.out.println((a+b+c).toUpperCase());
	}
}


Measured memory_bytes: 21716
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;

    if(n<=1000)
        cout<<1000-n<<endl;
    else if(n%1000==0)
            cout<<0<<endl;
    else
        cout<<1000-(n%1000)<<endl;

        return 0;
}


Measured memory_bytes: 3600
#include<stdio.h>
int dp[50];

int fib(int n){
  if(n==0||n==1)
      return dp[n]=1;
  if(dp[n]!=-1)
    return dp[n];
  return dp[n]=fib(n-1)+fib(n-2);
}

int main(){
  int n,i;
  for(i=0;i<50;i++)
    dp[i]=-1;
  scanf("%d",&n);
  printf("%d\n",fib(n));

  return 0;
}


Measured memory_bytes: 2112
k, a, b = map(int, input().split())

# ビスケットの売値が買値より安い場合
if a+2 > b:
    print(1 + k)
    exit()

# 交換獲得に必要なターン数
roop_turn = a+2

# 初回時ビスケット１枚を余分に所持
if k < roop_turn-1:
    print(1 + k)
    exit()

# 獲得ビスケット
ret = b

# 残りターン
remaining = k - (roop_turn-1)

q, mod = divmod(remaining, 2)

ret += (b-a)*q + mod
print(ret)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
int a[30010][10];
void solve()
{
	int n;string s;cin>>n>>s;
  	REP(i,10)a[n][i]=-1;
    for(int i=n-1;i>=0;i--){
        REP(j,10)a[i][j]=a[i+1][j];
        a[i][s[i]-'0']=i;
    }
    //REP(i,n){REP(j,10)cout<<setw(2)<<a[i][j]<<" ";cout<<endl;}cout<<endl;
    int ans=0;
    REP(i,10)REP(j,10)REP(k,10){
        int x=0;
        if(a[x][i]==-1)continue;
        x=a[x][i]+1;
        if(a[x][j]==-1)continue;
        x=a[x][j]+1;
        if(a[x][k]==-1)continue;
        ans++;
    }
    cout<<ans<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 1536
N=int(input())
z=[]
for  i in range(N):
    z.append(list(map(int,input().split())))
s=0
for i in range(N):
    for j in range(N):
        if i<j:
            s +=((z[i][0]-z[j][0])**2+(z[i][1]-z[j][1])**2)**0.5
print(2*s/N)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int n, k;

int main()
{
    cin >> n >> k;
    int sum = k;
    for (int i = 1; i < n; i++)
    {
        sum *= k - 1;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  vstring s(n);
  vint p(n);
  rep(i,n){
    cin>>s[i]>>p[i];
  }
  int count=0;
  vint ans(n);
  rep(i,n){
    count=0;
    rep(j,n){
      if(s[i]>s[j]){
        count++;
      }
      else if(s[i]==s[j]){
        if(p[i]<p[j]){
          count++;
        }
      }
    }
    ans[count]=i+1;
  }
  rep(i,n){
    cout<<ans[i]<<'\n';
  }
  return(0);
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  int cur = 1;
  long long ans = 0;
  int a;
  cin >> a;
  ans += a - 1;
  for (int i = 1; i < n; i++) {
    cin >> a;
    if (a <= cur) continue;
    if (cur + 1 == a) {
      cur++;
      continue;
    }
    ans += (a - 1) / (cur + 1);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 384
ninzu,okashi=map(int,input().split())
okashimochi=[list(map(int,input().split())) for i in range(okashi*2)]
for i in range(0,okashi,1):
    del okashimochi[i]
okashininzu=sum(okashimochi,[])
print(ninzu-len(set(okashininzu)))

Measured memory_bytes: 9180
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
using namespace std;
map <int ,int> mpa,mpb;

int N ,A[51];

int solve(int i, int m){
  if(m==0) return 1;
  if(i>=N) return 0;
  int ans=solve(i+1, m) || solve(i+1, m-A[i]);
  return ans;
}

int main(){
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  int q,t;
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> t;
    if(solve(0,t)) {
      cout << "yes" << endl;
    } else {
      cout << "no" << endl;
    }
  }
  return 0;
}


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

constexpr long long int M = 1000000007, m = 79133769, n = 536396504, mask = 1073741823;
 
inline long long int MR(long long int A){
    long long int ret = (A + M * (m * A & mask)) >> 30;
    return ret - (ret >= M) * M;
}

template<int N>
struct Fact{
  long long int val[N];
  constexpr Fact() : val() {
    val[0] = 73741817;
    for(int i = 1; i < N; ++i)val[i] = val[i - 1] * i % M;
  }
};

template<int N, long long F>
struct IFact{
  long long int val[N];
  constexpr IFact() : val() {
    val[N - 1] = F * 73741817 % M;
    for(int i = N - 1; i > 0; --i)val[i - 1] = val[i] * i % M;
  }
};

long long int N, ans;
constexpr auto fact = Fact<1000001>();
constexpr auto ifact = IFact<1000001, 397802501>();

int main(){
    scanf("%lld", &N);
    for(int i = N / 2; i < N - 1; ++i){
        ans += MR(MR(fact.val[i] * fact.val[i - 1]) * ifact.val[i * 2 - N]);
    }
    ans = fact.val[N] - fact.val[N - 1] - ans;
    ans %= M;
    cout << MR(ans > 0 ? ans : M + ans) << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	
	int n;
	int[][] m;
	int[] r;
	int[] c;
	
	public void input() {
		n = sc.nextInt();
		m = new int[n][n];
		r = new int[n];
		c = new int[n];
		for(int i=0; i<n; i++) {
			r[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}
	}
	
	public int solve(int start, int goal) {
		if(start == goal) { return 0; }
		if(m[start][goal] == 0) {
			int min = Integer.MAX_VALUE;
			for(int i=start; i<goal; i++) {
				int swap = solve(start,i)+solve(i+1,goal)+r[start]*c[i]*c[goal];
				min = Math.min(swap,min);
			}
			m[start][goal] = min;
		}
		return m[start][goal];
	}
	
	public void output() {
		System.out.println( solve(0,n-1) );
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.input();
		obj.output();
	}
}



Measured memory_bytes: 27272
from collections import Counter
import sys
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int,input().split()))

b = Counter(a)

ans = 1
if n % 2 == 0:
    for i in range(1,n,2):
        if b[i] == 2:
            ans = ans * 2 % MOD
        else:
            print(0)
            sys.exit()
            
else:
    if b[0] == 1:
        for i in range(2,n,2):
            if b[i] == 2:
                ans = ans * 2 % MOD
            else:
                print(0)
                sys.exit()
    else:
        print(0)
        sys.exit()
        
print(ans)


Measured memory_bytes: 55532
#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let n = get!(usize);
    let mut v = get!([usize]);
    for i in 0..n {
        if v[i] & 3 == 0 {
            v[i] = 2;
        } else if v[i] & 1 == 0 {
            v[i] = 1;
        } else {
            v[i] = 0;
        }
    }
    let a = v.iter().filter(|&&x| x == 2).count();
    if 2 <= v.iter().filter(|&&x| x == 1).count() {
        v = v.into_iter().filter(|&x| x != 1).collect();
        let b = v.iter().filter(|&&x| x != 2).count();
        if b <= a {
            println!("Yes");
            return;
        } else {
            println!("No");
            return;
        }
    }
    let b = v.iter().filter(|&&x| x != 2).count();
    if b <= a + 1 {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

typedef long long ll;
#define mx 100005

const ll inf = 1e18;
int n,a[mx];
ll DP[mx];
ll dp(int i)
{
  //  if(i>=n) return inf;
    if(i>=n-1) return 0;
    if(DP[i]!=-1) return DP[i];
    ll value,value2;
    value=abs(a[i+1]-a[i])+dp(i+1);
    if(i+2<=n-1) value2=abs(a[i+2]-a[i])+dp(i+2);
    else value2=inf;
    return DP[i]=min(value,value2);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    memset(DP,-1,sizeof(DP));
    ll ans = dp(0);
    printf("%lld\n",ans);


    return 0;
}


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

    using namespace std;
    template <typename T>
    void debug(string t, T input) {
        cout<<t<<"-> "<<input<<"\n";
    }
    template <typename T>
    void debug(int i,string t, T input) {
        cout<<"Case#"<<i<<" "<<t<<"-> "<<input<<"\n";
    }


    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin>>n;
        string s;
        cin>>s;
        long long r=0,g=0,b=0;
        for(int i=0;i<n;i++){
            if(s[i]=='R')
                r++;
            if(s[i]=='G')
                g++;
            if(s[i]=='B')
                b++;
        }
        long long total=r*g*b;
        int rgb=(int)('R') + (int)('G') + (int)('B');
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int k=2*j-i;
                if(k<n)
                    if((int)s[i]+(int)s[j]+(int)s[k]==rgb)
                        total--;
            }
        }
        cout<<total;
        return 0;
    }


Measured memory_bytes: 3664
N, M = map(int, input().split())
a = [True] * (N + 3)
a[N + 1] = False
a[N + 2] = False

for _ in range(M) :
    a[int(input())] = False

MOD = 10 ** 9 + 7

dp = [0] * (N + 3)
dp[0] = 1
for i in range(N + 1) :
    if a[i + 1] :
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
    if a[i + 2] :
        dp[i + 2] = (dp[i + 2] + dp[i]) % MOD
   
print(dp[N])

Measured memory_bytes: 45400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
#define MODSIZE 1000000007
// priority_queue<int, vector<int>, greater<int> > PQ; // 昇順PQ
priority_queue<int> PQ;

int main(){
  ll n;
  ll a[100005];
  ll mx;

  mx = 1000000000000000000;

  scanf("%lld", &n);

  int i;
  ll ans = 1;
  int f = 0;
  for(i = 0;i < n;i++) {
    scanf("%lld", &a[i]);
    if(a[i] == 0) f = 1;
  }

  ans = a[0];
  mx /= a[0];

  if(f){
    printf("0\n");
    return 0;
  }

  for(i = 1;i < n;i++){
    if(mx < a[i]){
      printf("-1\n");
      return 0;
    }

    ans *= a[i];
    mx /= a[i];
  }

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

  return 0;
}

Measured memory_bytes: 4604
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,n) loop(i,0,n)

const int MAX_N = 104729;
int p[(MAX_N + 1) / 2];
bool isp[MAX_N + 1];
int f(){
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = false;
    int idx = 0;
    loop(i, 2, MAX_N + 1){
        if (!isp[i]) continue;
        p[idx++] = i;
        for (int j = i + i; j <= MAX_N; j += i){
            isp[j] = false;
        }
    }
    return idx;
}

int main(){
    int n;
    f();
    while (cin >> n, n){
        long sum = accumulate(p, p + n, 0);
        cout << sum << endl;
    }
}

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

int main(){
    int n;  cin >> n;   vector<int> vec(n); int sum=0;
    for(int i=0;n>i;i++){
        cin >> vec[i];  sum+=vec[i];
    }
    if(sum%10){
        cout << sum;    return 0;
    }
    sort(vec.begin(), vec.end());
    for(int i=0;n>i;i++){
        if(vec[i]%10){
            cout << sum-vec[i];    return 0;
        }
    }
    cout << 0;
}


Measured memory_bytes: 256
from collections import deque
import sys

input = sys.stdin.buffer.readline
n = int(input())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append((b, i + 1))
    graph[b].append((a, i + 1))
par = [-1] * (n + 1)
que = deque([(1, -1, -1, -1)])  # edge, color, par, hen_num
color = [-1] * (n)
num = 0  # 使った色の数
while que:
    v, c, p, hen = que.popleft()
    par[v] = p
    color[hen] = c
    cnt = 0
    for i in range(len(graph[v])):
        u, hen_num = graph[v][i]
        if u == par[v]:
            continue
        cnt += 1
        if cnt == c:
            cnt += 1
        color[hen_num] = cnt
        num = max(num, cnt)
        que.append((u, cnt, v, hen_num))
print(num)
print(*color[1:], sep="\n")


Measured memory_bytes: 45876
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
void solve()
{
    ld a, b;
    cin>>a>>b;
    cout<<(ll)floor(a*b);
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}

Measured memory_bytes: 3732
def main():
    _ = int(input())
    h = [int(s) for s in input().split()]

    if solve(h):
        print('Yes')
    else:
        print('No')

def solve(h):
    th = h[0]

    for x in h[1:]:
        if x > th:
            th = x
        elif x == th or x + 1 == th:
            continue
        else:
            return False
    return True


main()


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

int main(void) {
    int N;
    std::cin >> N;
    vector< int > L(N);
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (L[i] == L[j]) {
                continue;
            }
            for (int k = j; k < N; k++) {
                if (L[j] == L[k]) {
                    continue;
                }
                if (L[i] + L[j] > L[k]) {
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);

    return 0;
}


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

using namespace std;

int main () {

    string s;
    int m, y;

    cin >> s;

    string s1 = s.substr(0,2);
    string s2 = s.substr(2,2);

    m = atoi(s1.c_str());
    y = atoi(s2.c_str());


    if ((m==0 or m > 12) and (y>0 and y <= 12)) {
        cout << "YYMM" << endl;
    }
    else if ((y==0 or y > 12) and (m>0 and m <= 12)) {
        cout << "MMYY" << endl;
    }
    else if ((m < 1 or m > 12) and (y < 1 or y > 12)) {
        cout << "NA" << endl;
    }
    else {
        cout << "AMBIGUOUS" << endl;
    }
    return 0;
}

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

using namespace std;

int mod = 1e9 + 7;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int substract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}

int pow (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

/*void Prec (int lim){fac[0] = inv[0] = 1;for (int i=1; i<=lim; i++)fac[i] = mul (fac[i - 1], i);
inv[lim] = pow (fac[lim], mod - 2);for (int i=lim - 1; i>=1; i--)inv[i] = mul (inv[i + 1], i + 1);}
int comb (int N, int K){int ans = mul (fac[N], inv[N - K]);ans = mul (ans, inv[K]);return ans;}*/

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

long long N, M;
scanf ("%lld %lld", &N, &M);
long long p = 0, u = max (N, M), mij, ras;
while (p <= u)
{
    mij = (p + u) >> 1LL;
    if (mij == 234530)
        mij = 234530;
    bool ok = 0;
    long long k = 0;
    if (mij >= N)
    {
        k = mij - N;
        if ((M - 2 * k) / 2 >= mij) ok = 1;
    }
    else
    if (M / 2 >= mij) ok = 1;
    if (ok) ras = mij, p = mij + 1;
    else u = mij - 1;
}
printf ("%lld\n", ras);

return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

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

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  
  unordered_map<int, int> as(N);
  F0R(i, N) {
    int a;
    cin >> a;
    a--;
    as[a]++;
  }

  map<int, int> bs; // map[i] = j : ちょうどi個同じである数はj組
  F0R(i, N) {
    if (as[i]) {
      bs[as[i]]++;
    }
  }

  vector<int> cs(N+1);
  F0R(i, N) {
    cs[i + 1] = cs[i] + (i + 1) * bs[i + 1];
  }
  vector<int> ds(N + 1);
  RF0(i, N) {
    ds[i] = ds[i + 1] + bs[i + 1];
  }

  vector<int> fs(N + 1);
  F0R(i, N) {
    fs[i] = (cs[i + 1] + (i + 1) * ds[i + 1]) / (i + 1);
  }
  //Print(fs);

  int n = fs.size() - 1;
  F0R(i, N) {
    while (n >= 0 && fs[n] < i + 1) n--;

    cout << (n+1) << newl;
  }
}
#endif


Measured memory_bytes: 30336
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

ll dp[100010][13];

int main(){
	string s; cin >> s;
	int n = s.l_ength();
	dp[0][0] = 1;
	for( int i = 0; i < n; ++i ){
		if( s[i] == '?' ){
			for( int d = 0; d <= 9; ++d ){
				for( int r = 0; r < 13; ++r ){
					dp[i+1][(r*10+d)%13] += dp[i][r];
					dp[i+1][(r*10+d)%13] %= mod;
				}
			}
		} else {
			for( int r = 0; r < 13; ++r ){
				dp[i+1][(r*10+(s[i]-'0'))%13] += dp[i][r];
				dp[i+1][(r*10+(s[i]-'0'))%13] %= mod;
			}
		}
	}
	cout << dp[n][5] << endl;
}

Measured memory_bytes: 10624
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>

using namespace std;

#define ll long long

int main()
{
	int x, y, z, k;
	cin >> x >> y >> z >> k;
	vector<ll> a(x), b(y), sum(x * y), c(z);
	auto comp = [](const pair<ll, int> &l, const pair<ll, int> &r) {return l.first < r.first; };
	
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, decltype(comp)>	q(comp);
	for (int i = 0; i < x; i++)
		cin >> a[i];
	for (int i = 0; i < y; i++)
	{
		cin >> b[i];
		for (int j = 0; j < x; j++)
			sum[x * i + j] = a[j] + b[i];
	}
	sort(sum.begin(), sum.end(), greater<ll>());

	for (int i = 0; i < z; i++)
	{
		cin >> c[i];
		q.push(make_pair(c[i] + sum[0], 0));
	}

	for (int i = 0; i < k; i++)
	{
		pair<ll, int> now = q.top();
		q.pop();
		printf("%lld\n", now.first);
		if (++now.second >= x * y)
			now.first = -1;
		else
			now.first += sum[now.second] - sum[now.second - 1];
		q.push(now);
	}

	return 0;
}


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


int main(){

    long N,M;
    cin >> N >> M;

    long sumA=0;
    int tmp;

    //vector<int> A(M,0);
    for(int i=0;i<M;i++){
        cin >> tmp;
        sumA += tmp;
    }

    if(N>=sumA){
        cout << N-sumA << endl;
    }else{
        cout << -1 << endl;
    }
    

    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

const int INF = 0x7fffffff;
const int _INF = 0x7fffffff + 1;

int main()
{
    char s[1002];
    int n;
    cin>>n;getchar();
    cin>>s;

    int ans = 0;
    int x = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'I')
            x++;
        else if(s[i] == 'D')
            x--;
        if(x >= ans)
            ans = x;
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 256
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

let main() =
    let [| H; N |] = reada int
    let abs = Array.zeroCreate N
    for i in 0 .. N - 1 do
        let [| a; b |] = reada int
        abs.[i] <- (a, b)

    // dp[i][h] : i番目までの魔法からいくつかの魔法を選んでダメージの総和がhとなる方法のうち、消費魔力が最小となる値
    let inf = 1e9 |> int
    let dp = Array2D.init (N + 10) (H + 10) (fun _ _ -> inf)
    dp.[0, 0] <- 0
    for i in 0 .. N - 1 do
        let a, b = abs.[i]
        for h in 0 .. H do
            // i番目の魔法を使わない場合
            dp.[i + 1, h] <- min dp.[i + 1, h] dp.[i, h]
            // i番目の魔法を使う場合
            let lim = min (a + h) H // Hを超える分は無駄なのでスキップ
            dp.[i + 1, lim] <- min dp.[i + 1, lim] (dp.[i + 1, h] + b)

    let ans = dp.[*, H] |> Array.min
    puts ans

main()
writer.Close()


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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);

using ll = long long;
using namespace std;

int main() {
    double w, h, x, y;

    cin >> w >> h >> x >> y;

  	if (x+x==w && y+y==h) {
      	cout << setprecision(20) << w*h/2.0 << " " << 1 << endl;
    } else {
      	cout << setprecision(20) << w*h/2.0 << " " << 0 << endl;
    }
  
    return 0;
}

Measured memory_bytes: 256
import bisect
n = int(input())
n_list = list(map(int,input().split()))
m = int(input())
m_list = list(map(int,input().split()))
n_list.sort()

long_list = []
for j in range(1<<n):
    ans = 0
    for z in range(n):
        if (j>>z)&1:
            ans += n_list[z]
    long_list.append(ans)

long_list.sort()

#print((long_list))

for j in range(m):
    num = bisect.bisect_left(long_list,m_list[j])
    
    if num <= len(long_list) - 1 and long_list[num] == m_list[j]:
        print("yes")
    else:
        print("no")



Measured memory_bytes: 47004
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<ctime>

using namespace std;

vector<int> getInput(int input);

int main()
{
	vector<int> input = getInput(2);
	int N = input[0];
	int K = input[1];
	int result = 0;
	vector<int> h = getInput(N);
	for (auto& v : h) {
		if (v >= K) {
			result++;
		}
	}
	cout << result << endl;
}

vector<int> getInput(int input) {
	vector<int> vec(input);
	for (auto& v : vec) {
		cin >> v;
	}
	return vec;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll n;
    cin >> n;
    ll ans = 1e18+10;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, -100, 101){
        ll t = 0;
        rep(j, 0, n){
            t += (i - a[j]) * (i - a[j]);
        }
        ans = min(ans, t);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define PI 3.141592653
using namespace std;

ll A[100001];
bool B[100001];

void solve(){
	int n; cin>>n;
	A[0] = -100;
	for(int i=1; i<=n ; i++) cin>>A[i];

	A[1]--;
	for(int i=2; i<=n; i++){
		if(A[i] < A[i-1]){
			cout<<"No";
			return;
		}
		else if(A[i] > A[i-1]){
			A[i]--;
		}
	}
	cout<<"Yes";
}

int main()
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(12);

    int t =1; //cin>>t;
    for(int i=1; i<=t; i++){
        solve();
        cout<<"\n";
    }
    return 0;

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }

int main() {
  int N,x;
  cin>>N>>x;
  vector<int>a(N);
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  int sum=0;
  for(int i=0;i<N;i++){
    if(x>=a[i]){
      if(i<N-1){sum++;x-=a[i];}
      else {
        if(x==a[i]){sum++;x-=a[i];}
        else{x-=a[i];}
      }
    }
    else{break;}
  }
  cout<<sum<<endl;
  return 0;  
}

Measured memory_bytes: 3640
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main(){
    int n, m, s, g1, g2, b1, b2, c, d[101][101];
    const int INF = 700000000;
    while(scanf("%d%d%d%d%d", &n, &m, &s, &g1, &g2), n){
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j <= n; ++j){
                d[i][j] = INF;
            }
            d[i][i] = 0;
        }
         
        for(int i = 0; i < m; ++i){
            scanf("%d%d%d", &b1, &b2, &c);
            d[b1][b2] = c;
        }
         
        for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j){
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
         
        int ans = INF;
        for(int i = 1; i <= n; ++i){
            ans = min(ans, d[s][i] + d[i][g1] + d[i][g2]);
        }
        printf("%d\n", ans);
    }
}

Measured memory_bytes: 1068
package main

import (
	"fmt"
)

func main() {
	var n int
	var line string
	fmt.Scan(&n, &line)
	blacks, whites := make([]int, n), make([]int, n)
	bcount, wcount := 0, 0
	for i, j := range line {
		s := string(j)
		if s == "#" {
			bcount++
		} else {
			wcount++
		}
		blacks[i] = bcount; whites[i] = wcount
	}
	mn := bcount
	if mn > wcount {
		mn = wcount
	}
	for i := 0; i < n - 1; i++ {
		tmp := blacks[i] + whites[n - 1] - whites[i]
		if mn > tmp {
			mn = tmp
		}
	}
	fmt.Println(mn)
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*POW(a,b-1)%mod;ll k=POW(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

//d桁の集合->d+1桁の集合
vi foo(const vi &v){
  vi res;
  for(auto p:v){
    REP(j,-1,2){
      int add=(p%10)+j;
      if(isin(add,0,9)) res.eb(p*10+add);
    }
  }
  return res;
}

void solve() {
  int k; cin>>k;
  vi a; //全列挙
  vi cur; //1桁
  REP(v,1,10){
    cur.eb(v); a.eb(v);
  }
  REP(d,1,10){
    cur=foo(cur);
    for(auto p:cur) a.eb(p);
  }
  out(a[k-1]);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 3440
k, n = map(int, input().split())
array = list(input().split())
array2 = []
for i in range(len(array)-1):
    array2.append(int(array[i+1]) - int(array[i]))
first = int(array[0]) + k - int(array[len(array)-1])
array2.append(first)
print(k - max(array2))

Measured memory_bytes: 19604
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#include <iomanip>
#include <limits>
#include <string>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
const long long INF = 1LL << 60;
using namespace std;

int main(){
	string s; cin >>s;
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='x')cnt++;
	}
	cout << (cnt<=7?"YES":"NO") << endl;
}

Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    x = I()
    ans = (x//11)*2
    t = x%11
    if t == 0:
        pass
    elif t >= 1 and t <= 6:
        ans += 1
    else:
        ans += 2
    print(ans)

if __name__ == '__main__':
    main()

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

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

    rep(x, n + 1) rep(y, n - x + 1) {
        int z = n - x - y;
        if (0 <= z && x * 10000 + y * 5000 + z * 1000 == Y) {
            cout << x << " " << y << " " << z << endl;
            return 0;
        }
    }
    
    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
long nCr(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};

signed main() {
	int a, b;
	cin >> a >> b;
	if (a < 10 && b < 10) {
		cout << a * b << endl;
	}
	else cout << -1 << endl;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        # print(i)
        # print(bin(K)[2:], bin(1<<i_inv)[2:])
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) #上位i+1bit            
            # print(bin(a)[2:],bin(left_a)[2:])
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 82136
n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

all_score = [k - q for _ in range(n)]
for ai in a:
    all_score[ai - 1] += 1
for j in all_score:
    if j > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 11784
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+20;
int n;
vector<int> g[N], h[N];

int dfs(int x, int f, int d) {
	h[x].clear();
	for (int y:g[x]) if (y!=f) h[x].pb(dfs(y,x,d));	
	if (h[x].size()%2==0) h[x].pb(0);
	if (h[x].size()==1) return h[x][0]+1;
	sort(h[x].begin(),h[x].end());
	int sz=h[x].size(),l=0,r=sz-1,ans=-1;
	while (l<=r) {
		int ql=0,qr=sz-1,ok=1;
		while (1) {
			if (ql==mid) ++ql;
			if (qr==mid) --qr;
			if (ql>qr) break;
			if (h[x][ql]+h[x][qr]>d) ok=0;
			++ql,--qr;
		}
		if (ok) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans<0?INF:h[x][ans]+1; 
}

int main() {
	scanf("%d", &n);
	REP(i,2,n) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].pb(v),g[v].pb(u);
	}
	int cnt = 0, rt = 0;
	REP(i,1,n) if (g[i].size()&1) rt = i, ++cnt;
	cnt /= 2;
	int l = 0, r = n-1, ans;
	while (l<=r) {
		if (dfs(rt,0,mid)<=mid+1) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d %d\n", cnt, ans);
}









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

struct Card
{
	char suit, value;
};

void Bubble_sort(Card C[], int N)
{
	for (int i = 0; i < N; i++)
		for (int j = N-1; j > i; j--)
			if (C[j].value < C[j-1].value)
				swap(C[j], C[j-1]);
}

void Selection_sort(Card C[], int N)
{
	for (int i = 0; i < N; i++)
	{
		int	mini = i;
		for (int j = i; j < N; j++)
			if (C[j].value < C[mini].value)
				mini = j;

		if (i != mini)
			swap(C[i], C[mini]);
	}
}

void print_result(Card C[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (i > 0) cout << " ";
		cout << C[i].suit << C[i].value;
	}
	cout << "\n";
}

bool isStable (Card C1[], Card C2[], int N)
{
	for (int i = 0; i < N; i++)
		if (C1[i].suit != C2[i].suit)
			return false;
	return true;
}
int main()
{
	int N;
	cin >> N;
	Card C[N], D[N];
	for (int i = 0; i < N; i++)
		cin >> C[i].suit >> C[i].value;
	
	for (int i = 0; i < N; i++)
		D[i] = C[i];
	
	Bubble_sort(C, N);
	Selection_sort(D, N);
	print_result(C, N);
	cout << "Stable" << "\n";
	print_result(D, N);
	if (isStable(C, D, N))
		cout << "Stable" << endl;
	else
		cout << "Not stable" << endl;
}




Measured memory_bytes: 3100
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    a = set([I() for _ in range(M)])

    dp = [0] * (N + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(N - 1):
        if i + 2 not in a:
            dp[i+2] = dp[i] + dp[i+1]
            dp[i+2] %= MOD

    print(dp[-1])

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 19764
/*Remember: The Struggle Is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     __gcd((a),(b))
#define     lcm(a,b)     ((a)*(b))/gcd((a),(b))
#define     pb           push_back
#define     ins          insert
#define     F            first
#define     S            second

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

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

    int mx=0,cnt=1;
    for(int i=1;i<n;++i)
    {
        if(v[i]<=v[i-1])
            ++cnt;
        else
        {
            mx=max(mx,cnt);
            cnt=1;
        }
    }

    cout<<max(cnt,mx)-1;
}

int32_t main()
{
    fast();

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

    return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
typedef long long ll;
using namespace std;

int main() {
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(),a.end());
    if(a[0]==5 && a[1]==5 && a[2]==7){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;

int a[MAXN];

int main(void)
{
	int n,d;
	scanf("%d%d",&n,&d);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	
	sort(a+1,a+n+1);
	int ans = 0;
	for(int i=1; i<=d; ++i) ans += a[i];
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
int main () {
  long R, G, B, N;
  cin >> R >> G >> B >> N;
  long count = 0;
  for(int i = 0; i <= N; i += R){
    for(int j = 0; j <= N - i; j += G){
      if((N - i - j) % B == 0)count++;
    }
  }
  cout << count << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
  int K;
  int A,B;
  bool x = false;
  cin >> K >> A >> B;
  int i;
  for(i=0;i<=10000;i++)
    if(K * i <= B && K * i >= A) x = true;
  if(x) cout << "OK";
  else cout << "NG";
}

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

int main() {
  int n;
  cin >> n;
  vector<tuple<string, int, int>> v(n);
  
  for (int i = 0; i < n; i++) {
    string s;
    int p;
    cin >> s;
    cin >> p;
    v.at(i) = make_tuple(s, 100 - p, i + 1);
  }
  
  sort(v.begin(), v.end());
  
  for (auto p : v) {
    cout << get<2>(p) << endl;
  }
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
int h,w,a,b;
int f[1001][1001];
int main()
{
	scanf("%d %d %d %d",&h,&w,&a,&b);
	for (int i=1;i<=b;i++)
		for (int j=a+1;j<=w;j++) f[i][j]=1;
	
	for (int i=b+1;i<=h;i++)
		for (int j=1;j<=a;j++) f[i][j]=1;
	
	for (int i=1;i<=h;i++)
	{
		for (int j=1;j<=w;j++)
		printf("%d",f[i][j]);
		printf("\n");
	}
}
 

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

int main(){
  long long N,ans=0;
  cin >> N;
  
  for(int i=1;i<=N;i++){
    if(i%3!=0 && i%5!=0) ans += i;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int val = (int) (n/(1.08));
		if ((int)(1.08 * val) == n) {
			System.out.println(val);
		} else if ((int) (1.08 * (val + 1)) == n) {
			System.out.println(val + 1);
		} else {
			System.out.println(":(");
		}
		sc.close();
	}

}


Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
int main(){
  int n,m;
  cin >> n >> m;
  int ans = 0;
  int a[100005];
  int p[100005];
  int miss = 0;
  for(int i = 0;i<100005;++i){
    a[i] = 0;
    p[i] = 0;
  }
  int b;
  string s;   
  for(int i = 0;i<m;++i){
    cin >> b >> s;
    if(a[b-1] > 0){
      continue;
    }
    else{
      if(s == "AC"){
        ans++;
        a[b-1] = 1;
      }else{
        p[b-1]++;
      }
    }
  }
  for(int i = 0;i<100005;++i) miss += a[i]*p[i];
  cout << ans << " " << miss << endl;
}

Measured memory_bytes: 1024