akhauriyash/Code-Regression huggingface dataset:
/* include */
#include <bits/stdc++.h>

/* using */
using namespace std;

/* main constructor */
struct Fast
{
    Fast()
    {
        std::cin.tie(0);
        ios::sync_with_stdio(0);
        //cout << fixed << setprecision(12);
    }
} fast;

/* template */
template <class T>
bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0; }
template <class T>
bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0; }

/* define */
#define REP(i, x, n) for (int i = x; i < (int)(n); ++i)
#define RREP(i, x, n) for (int i = x - 1; i >= (int)(n); --i)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) REP(i, 1, n + 1)
#define rrep(i, n) RREP(i, n, 0)
#define each(i, n) for (auto &i : n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define eunique(x) \
    sort(all(x));  \
    (x).erase(unique(all(x)), (x).end())
#define int long long
#define mp make_pair
#define r0 return 0

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

/* const */
const int inf = 1e9 + 7;
const int dxl[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dyl[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dxs[4] = {1, 0, -1, 0};
const int dys[4] = {0, 1, 0, -1};

/* main */
signed main(void)
{
    int x,t;
    cin >> x >> t;
    if(x-t>=0){
        cout << x - t << endl;
    }
    else{
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll MOD = 1000000007;
const ll INF = 10000000000;
#define all(v) v.begin(), v.end()

int main(){
  ll H,W;
  cin >> H >> W;
  vector<vector<ll>> A(H,vector<ll>(W)),B(H,vector<ll>(W));
  vector<vector<vector<ll>>> dp(H,vector<vector<ll>>(W,vector<ll>(8001,0)));
  rep(i,H)rep(j,W) cin >> A.at(i).at(j);
  rep(i,H)rep(j,W) cin >> B.at(i).at(j);
  dp.at(0).at(0).at(abs(A.at(0).at(0)-B.at(0).at(0)))=1;
  rep(i,H){
    rep(j,W){
      ll t=abs(A.at(i).at(j)-B.at(i).at(j));
      rep(k,8001){
        if(i!=0){
          if(dp.at(i-1).at(j).at(k)==1){
            if(t+k<8001){
              dp.at(i).at(j).at(t+k)=1;
            }
            dp.at(i).at(j).at(abs(t-k))=1;
          }
        }
        if(j!=0){
          if(dp.at(i).at(j-1).at(k)==1){
            if(t+k<8001){
              dp.at(i).at(j).at(t+k)=1;
            }
            dp.at(i).at(j).at(abs(t-k))=1;
          }
        }
      }
    }
  }
  rep(k,8001){
    if(dp.at(H-1).at(W-1).at(k)==1){
      cout << k << endl;
      return 0;
    }
  }
}

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

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

  int max = 1000000000;
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;

    int count = 0;
    while (true) {
      if (A == 0) break;
      if (A % 2 == 1) break;
      A /= 2;
      count++;
    }
    if (count < max) max = count;
  }
  cout << max << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main(int argc, char **argv)
{
    ll K;
    cin >> K;

    if (K <= 10) {
        cout << K << endl;
    }
    else {
        priority_queue<ll, vector<ll>, greater<ll>> q;
        deque<string> dq;
        FOR(i, 0, 10) dq.push_back(to_string(i));
        int c = 10;
        int n = 0;
        while(true) {
            REP (j, c) {
                string s = dq.front();
                dq.pop_front();
                //cout << s << endl;
                if (s[0] != '0') {
                    q.push(stoll(s));
                }
                ll dig = s.length();
                int i = (int)(s[0] - '0');
                if (s[0] != '0') {
                    dq.push_back(to_string(i - 1) + s);
                    n++;
                }
                dq.push_back(to_string(i) + s);
                n++;
                if (s[0] != '9') {
                    dq.push_back(to_string(i + 1) + s);
                    n++;
                }
            }
            c = n;
            n = 0;
            if (q.size() >= K) break;
        }
        int len = q.size();
        for (int i = 0; i < K - 1; ++i) {
            q.pop();
        }
        cout << q.top() << endl;
    }


    return 0;
}


Measured memory_bytes: 23792
#include<stdio.h>

int main(void)
{
	int n,i;
	char s1='0',s2;
	int sum=0;
	
	scanf("%d",&n);
	for(i=0;i<=n;i++)
	{
		scanf("%c",&s2);
		
		if(s1!=s2){
			s1=s2;
			sum++;
		}
	}
	printf("%d",sum-1);
	return 0;
}

Measured memory_bytes: 128
//KI RE CHUDIR VAIRA CODE DEKHSOS KN????
/* SHIRIR NICHE BIRIR DOKAN 
HOREK ROKOM BIRI PAWA JAI,NICHE TADER NAAM AAR DAAM ------>>
বেন্সন - ১৩/- 
গোল্ডলিফ - ১০/-
মার্লবোরো - ১৪/-
রয়্যালস(ROYALS) - ৫/-
স্টার - ৫/- 
ডার্বি - ৫/-
জোয়ি ব্ল্যাক - ১০/-, ১৫/-
ডানহিল - ১৫/-,  ২০/-
পিকক - ১০/-
প্রাইড - ১০/-
পাইন - ১৫/-
মার্বেল - ১০/-
555 - ১৫/- , ১৭/-
গুরু - ১০/-
গুদাংগারাম - ২৫/- , ৩৫/-
এসসে (লাইট) - ১০/-
মন্ড - ১৫/-
*/
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
const int INF = 1e9 + 5;
 
int main() {
    int n;
    scanf("%d", &n);
    vector<int> h(n);
    for(int& x : h) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j : {i + 1, i + 2}) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);
  return 0;
} 

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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

int main() {
    ios_base::sync_with_stdio(false);
    ll n,k;
    cin >> n >> k;
    ll b = 1;
    ll ans = 1;
    while(b*k <= n) ans++, b *= k;
    cout << ans << endl;
    return 0;
}



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

const int MOD = (int)1e9+7;

int main(){
	int N;
	cin >> N;
	vector<int> A(N),B(N),C(N);
	for(int i=0;i<N;i++)	cin >> A.at(i);
	for(int i=0;i<N;i++)	cin >> B.at(i);
	for(int i=0;i<N;i++)	cin >> C.at(i);

	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	sort(C.begin(),C.end());
	long long ans=0;
	for(int i=0;i<N;i++){
		long long b=B.at(i);
		long long a=lower_bound(A.begin(),A.end(),b)-A.begin();
		long long c=C.end()-upper_bound(C.begin(),C.end(),b);
		ans+=a*c;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1408
use proconio::{input, fastout};
use proconio::marker::Chars;

#[fastout]
fn main() {
    input! {
        s: Chars,
    }
    let mut ans = 0;
    if s[0] == '1' { ans += 1; }
    if s[1] == '1' { ans += 1; }
    if s[2] == '1' { ans += 1; }
    println!("{}", ans);
}

Measured memory_bytes: 2160
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long

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

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

	string A = "",B = "";

	string c = to_string(a);
	string d = to_string(b);

	for(int i = 0;i<a;i++)
		A = A + d;
	for(int i = 0;i<b;i++)
		B = B + c;


	vector<char>P,Q;

	for(int i = 0;i<A.length();i++)
		P.push_back(A[i]);

	for(int i = 0;i<B.length();i++)
		Q.push_back(B[i]);

	if(lexicographical_compare(P.begin(),P.end(),Q.begin(),Q.end()))
		cout<<A<<endl;

	else
		cout<<B<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=50;
double a[maxn][maxn];
int n,d;
bool judge(int i,int j)
{
    double sum1=0;
    for(int k=1;k<=d;k++)
        sum1+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);

    int sum=sqrt(sum1);
    if(sum*sum==sum1)
        return true;
    else return false;
}
int main()
{
    cin>>n>>d;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=d;j++)
            cin>>a[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(judge(i,j))
              ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
void ABC50(void);
void ABC51(void);
void ABC52(void);
void ABC53(void);
void ABC54(void);
void ABC55(void);
void ABC56(void);
void ABC57(void);
void ABC58(void);
void ABC59(void);

int main(void){
    ABC50();
    return 0;
}

void ABC50(void){
    int a,b;
    char c;
    cin >> a >> c >> b;
    if(c=='+'){cout << a+b <<endl;}
    else{cout << a-b << endl;}
}

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

int main(){
    std::cin.tie(nullptr);std::cin.sync_with_stdio(false);
    int n;std::cin>>n;
    for(int i=0;i<n;i++){
        char c;std::cin>>c;
        if(c=='Y'){
            std::cout<<"Four"<<std::endl;
            return 0;
        }
    }
    std::cout<<"Three"<<std::endl;
}

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

from collections import Counter

MOD = 10**9+7

def prime_factorize(n):
    res = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res.append(i)
            n //= i
    if n != 1:
        res.append(n)
    return res

prime_fac = []
for i in range(1, N+1):
    prime_fac.extend(prime_factorize(i))

c = Counter(prime_fac)

ans = 1
for v in c.values():
    ans *= v+1
    ans %= MOD
print(ans)

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1){
    c-=b;
    if(c<=0){
        cout<<"Yes"<<endl;
        return 0;
    }
    a-=d;
    if(a<=0){
        cout<<"No"<<endl;
        return 0;
    }

    }
    return 0;

}
/*


*/


Measured memory_bytes: 3636
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include<string>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <ctime>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k<=a) cout<<k;
	if(k>a&&k<=a+b) cout<<a;
	if(k>a+b&&k<=a+b+c) cout<<a-(k-a-b); 
    if(k>a+b+c) cout<<a-c;

}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  string A,B;cin>>A>>B;

  if(A.size()>B.size()){
    cout<<"GREATER"<<"\n";
    return 0;
  }else if(B.size()>A.size()){
    cout<<"LESS"<<"\n";
    return 0;
  }

  for(int t=0;t<100;t++){
    if(A[t]>B[t]){
      cout<<"GREATER"<<"\n";
      return 0;
    }else if(A[t]<B[t]){
      cout<<"LESS"<<"\n";
      return 0;
    }else{
      cout<<"EQUAL"<<"\n";
      return 0;
    }
  }

}


Measured memory_bytes: 256
N = int(input())
xyhs = []
for i in range(N):
  x, y, h = map(int, input().split())
  xyhs.append((x, y, h))
x0, y0, h0 = max(xyhs, key=lambda xyh: xyh[2])
for cx in range(0, 101):
  for cy in range(0, 101):
    H = h0+abs(x0-cx)+abs(y0-cy)
    ok = True
    for x, y, h in xyhs:
      if h != max(0, H-abs(x-cx)-abs(y-cy)):
        ok = False
        break
    if ok:
      print(cx, cy, H)
      exit()
print(-1)


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

int a[105];

int main()
{
    int n , k;

    cin >> n >> k;

    for(int i = 1 ; i<=n ; i++)
    {
        cin >> a[i];
    }
    sort(a+1 , a+n+1);

    int ans = 0;

    for(int i = n ; i>=(n-k+1) ; i--)
    {
        ans+=a[i];
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define max(a,b,c) max(max(a,b),c)
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

ll inv[100010], fac[100010], finv[100010];

void prepare()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < 100010; i++)
    {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fac[i] = fac[i - 1]* (ll)i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll C(int a,int b)
{
    if (a < b || b < 0) return 0;
    return fac[a] * (finv[b] * finv[a - b] % MOD) % MOD;
}

int a[100010];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	prepare();
	ll n, x, d;
	cin >> n;
	for (int i = 1; i <= n + 1; ++i)
	{
		cin >> x;
		if (!a[x])
		{
			a[x] = i;
		}
		else
		{
			d = n + 1 - (i - a[x] + 1);
			break;
		}
	}
	for (int i = 1; i <= n + 1; ++i)
	{
		cout << (C(n + 1, i) -  C(d, i - 1) + MOD) % MOD << endl;
	}
	return 0;
}

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

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

Measured memory_bytes: 4060
n, a, b = map(int, input().split())
if (a+b)%2:
  if a-1 <= n-b:
    print(a+(b-a-1)//2)
  else:
    print(n-b+1+(n-(a+n-b+1))//2)
else:
  print((b-a)//2)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
const LL MO=1e9+7;
 
LL qmi(LL a,LL b) {
    LL res=1;
    while(b) {
        if (b&1) {
            res=res*a%MO;
        }
        a=a*a%MO;
        b>>=1;
    }
    return res;
}
 
int main() {
    LL n;
    cin>>n;
 
    cout<<((qmi(10ll,n)-2*qmi(9ll,n)+qmi(8ll,n))%MO+MO)%MO<<"\n";
 
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 100000;

int main(){
    
    int n,t;
    ll a[maxn];
    int ans = 0;
    ll m=INF,M=0;
    ll Mdis=0;
    map<ll,int> ma;
    
    cin >> n>>t;
    rep(i,n)cin >> a[i];
    
    rep(i,n){
        if(m>a[i]){
            m=a[i];
            M=0;
        }
        if(M<a[i]){
            M=a[i];
            Mdis=max(Mdis,M-m);
        }
        ma[a[i]]=i;
    }
    
    rep(i,n){
        if(i<ma[a[i]+Mdis])ans++;
    }
    
    cout << ans<<endl;
    
    return 0;
}


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

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

  vector<ll> A(N, 0);
  for(ll i = 0; i < N; i++){
    cin >> A[i];
  }

  ll dif = 0;
  ll maxdif = 0;
  for(ll i = 0; i < N; i++){
    for(ll j = i + 1; j < N; j++){
      dif = llabs(A[i] - A[j]);
      maxdif = max(maxdif, dif);
    }
  }

  cout << maxdif << endl;

  return 0;

}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip()

S = input()
L = []
R = []
rev = 0
for _ in range(int(input())):
    A = input().split()
    if A[0] == "1":
        rev ^= 1
    else:
        if (int(A[1]) ^ rev) & 1:
            L.append(A[2])
        else:
            R.append(A[2])

if rev:
    print("".join(R[::-1]) + S[::-1] + "".join(L))
else:
    print("".join(L[::-1]) + S + "".join(R))


Measured memory_bytes: 6252
from collections import deque
s=deque(list(input()))

Q=int(input())
append_flag=False
Q_=[]

for q in range(Q):
    T = list(input().split())
    if T[0]=='2':
        append_flag=True
    if append_flag:
        Q_.append(T)
        
rev=1
rev_num=0
for q in Q_:
    if q[0]=='1':
        rev = -1*rev
        rev_num+=1
    elif rev == 1:
        if q[1]=='1':
            s.appendleft(q[2])
        elif q[1]=='2':
            s.append(q[2])
    elif rev == -1:
        if q[1]=='2':
            s.appendleft(q[2])
        elif q[1]=='1':
            s.append(q[2])

s=list(s)
if rev_num%2 != 0:
    s.reverse()
    
print(''.join(s))

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = max((a),(b))
#define chmin(a, b) a = min((a),(b))
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;

bool double_check(int a){
    rep(i,inf){
        if(i*i==a){
            return true;
        }
        else if(i*i>a){
            return false;
        }
    }
}

char table[105][105];

int main(){
    int h,w;
    cin>>h>>w;
    rep(i,h)rep(j,w){
        cin>>table[i][j];
    }
    vint ansh;
    vint answ;
    rep(i,h){
        bool check=true;
        rep(j,w){
            if(table[i][j]=='#'){
                check=false;
                break;
            }
        }
        if(check==false){
            ansh.pb(i);
        }
    }
    rep(j,w){
        bool check=true;
        rep(i,h){
            if(table[i][j]=='#'){
                check=false;
                break;
            }
        }
        if(check==false){
            answ.pb(j);
        }
    }   
    for(auto i: ansh){
        for(auto j:answ){
            cout<<table[i][j];
        }
        cout<<endl;
    }
}

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

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

    int a,b;
    cin >> a >> b;
    
    int ans = 0;
    if(a >= 13) ans = b;
    else if(a >= 6) ans = b / 2;
    
    cout << ans << endl;

    return 0;
}

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

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

    l = input().rstrip()
    n = len(l)

    # dp[i]:上からi+1桁目まで見ている
    # l以下が確定している場合の数
    dp1 = [0]*n
    # lに沿ってる場合の数
    dp2 = [0]*n
    
    # 先頭は1で固定されているので
    dp1[0] = 1
    dp2[0] = 2
    
    for i in range(1, n):
        if l[i] == '1':
            dp1[i] = (dp1[i-1] * 3 + dp2[i-1]) % mod
            dp2[i] = dp2[i-1] * 2 % mod
        else:
            dp1[i] = dp1[i-1] * 3 % mod
            dp2[i] = dp2[i-1]
    print((dp1[-1]+dp2[-1]) % mod)

if __name__ == '__main__':
    main()

Measured memory_bytes: 41200
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Scanner cin2;


    void calc()
    {
        cin = new Scanner();
        cin2 = new Scanner();
        int N = cin.nextInt();
        int[] H=cin.ArrayInt(N,0);
        int ans=0;
        int max=0;
        for(int i=0;i<N;i++)
        {
            if(max<=H[i])
            {
                ans++;
                max=H[i];
            }
        }
        Console.WriteLine(ans);
    }


}



class Scanner
{
    string[] s;
    int i;

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

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

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

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

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

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

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


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include<string>
#include<map>
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include <time.h>
#include<cmath>
#include<limits.h>
#include<unordered_map>
#include <set>
#include <iostream>     // std::cout, std::fixed
#include <iomanip>
#include<queue>
#define PI 3.1415926535897932384626433832795028841971693993751058209749445923078164062861
using namespace std;
const int N = 1e6 + 1;
void solve2() {
    int n,m; cin >> n >> m;
    vector<int> g[n + 1];
    for (int i = 0; i < m; i ++) {
        int x,y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    vector<bool> used(n + 1);
    vector<int> d(n + 1);
    used[1] = 1;
    vector<int> p(n + 1, 0);
    d[1] = 0;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for (size_t i = 0; i < g[v].size(); i ++) {
            int to = g[v][i];
            if (!used[to]) {
                q.push(to);
                used[to] = true;
                p[to] = v;
            }
        }
    }
    for (int i = 2; i < n + 1; i ++) {
        if (p[i] == 0) {
            cout << "No";
            return;
        }
    }
    cout << "Yes" << endl;
    for (int i = 2; i < n + 1; i ++) {
        cout << p[i] << endl;
    }
}

int main() {
    solve2();
//    double A,B,H,M; cin >> A >> B >> H >> M;
//    H = H * 30 + double(M)/2;
//    cout << H << endl;
//    M = M * 6;
//    int diff = (H - M);
//    long double ans = (A*A + B*B) - (2*A*B * cos(diff*PI/180));
//    cout << setprecision(16) << sqrt(ans) << endl;
}



Measured memory_bytes: 10732
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
ll n;
VV gragh;
V vec;
V result;
void dfs(ll x,ll prev){
 //   cout<<x<<" "<<prev<<endl;
    rep(i,gragh[x].size()){
        if(gragh[x][i]!=prev){
            dfs(gragh[x][i],x);
        }
    }
    if(x==0)return;
    result[x] = vec[0];
   // cout<<x<<" "<<vec[0]<<endl;
    vec.erase(vec.begin());
    return;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    gragh.resize(n);
    vec.resize(n);
    result.resize(n);
    rep(i,n-1){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        gragh[a].push_back(b);
        gragh[b].push_back(a);
    }
    rep(i, n) cin >> vec[i];
    if(n==1){
        cout << vec[0] << endl;
        return 0;
    }
    sort(all(vec));
    result[0] = vec[vec.size() - 1];
    vec.pop_back();
    ll R = 0;
    rep(i,vec.size()){
        R += vec[i];
    }
    cout << R << endl;
    dfs(0,-1);
    rep(i,n){
        cout << result[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<double,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const LL INF=1<<30;


int main(){
    int N;
    cin >> N;
    LL a[N+1],b[N+1];
    a[N]=0;b[N]=0;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    for(int i=0;i<N;i++){
        cin >> b[i];
    }
    for(int i=0;i<N;i++){
        if(a[i]>b[i]) a[N]+=a[i]-b[i];
        else if(a[i]<b[i]){
            b[N]+=(b[i]-a[i])/2;
        }
    }
    if(a[N]>b[N]) puts("No");
    else puts("Yes");
    return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cstdio>
const int N=200005,mo=1000000007;
int id[N],l[N],r[N],f[N];
struct info{int x,v;}p[N];
bool cmp2(info a,info b){return a.x<b.x;}
bool cmp(int a,int b){return p[a].v<p[b].v;}
int main(){
	int n;
	scanf("%d\n",&n);
	for (int i=1;i<=n;i++) scanf("%d%d\n",&p[i].x,&p[i].v);
	std::sort(p+1,p+n+1,cmp2);
	for (int i=1;i<=n;i++) id[i]=i;
	std::sort(id+1,id+n+1,cmp);
	for (int i=1;i<=n;i++) l[id[i]]=r[id[i]]=i;
	for (int i=2;i<=n;i++) r[i]=std::max(r[i],r[i-1]);
	for (int i=n-1;i;i--) l[i]=std::min(l[i],l[i+1]);
	f[0]=1;
	for (int i=1,j=0,sum=1;i<=n;i++){
		for (;j<l[i]-1;) sum=(sum-f[j++]+mo)%mo;
		(f[r[i]]+=sum)%=mo;
		(sum<<=1)%=mo;
	}
	printf("%d\n",f[n]);
}

Measured memory_bytes: 4864
x1, y1, x2, y2 = gets.split.map(&:to_i)
v1 = [x2 - x1, y2 - y1]
v2 = [-v1[1], v1[0]]
v3 = v1.map{|it| - it}
p3 = [x2 + v2[0] , y2 + v2[1]]
p4 = [p3[0] + v3[0] , p3[1] + v3[1]]

puts (p3 + p4).join(" ")


Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector <int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	vector <int> mi(n);
	int ans = 1;
	mi[0] = a[0];
	for (int i = 1; i < n; i++) {
		mi[i] = min(mi[i - 1], a[i]);
		if (mi[i] == a[i])
			ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1792
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[] p = new int[n];
			for(int i = 0 ; i < n ; i++) {
				p[i] = sc.nextInt();
			}
			BigDecimal max = BigDecimal.ZERO;
			for(int i = 0 ; i < k ; i++) {
				max = max.add(getEx(p[i]));
			}
			BigDecimal start = getEx(p[0]);
			BigDecimal pre = max;
			for(int i = k ; i < n ; i++) {
				BigDecimal now = pre.subtract(start).add(getEx(p[i]));
				if(now.compareTo(max) > 0) {
					max = now;
				}
				start =  getEx(p[i - k + 1]);
				pre = now;
			}
			max = max.setScale(6);
			System.out.println(max.toString());
		}

	}

	private static BigDecimal getEx(int num) {
		long sum = 0;
		for(int i = 1 ; i <= num ; i++) {
			sum += i;
		}
		return BigDecimal.valueOf(sum).divide(BigDecimal.valueOf(num), 20, BigDecimal.ROUND_HALF_UP);
	}
}


Measured memory_bytes: 127800
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
	int h, m, hl, ml;
	double angle, radian, ans;
	scanf("%d%d%d%d", &hl, &ml, &h, &m);//先看数据范围 
	angle = abs(0.5 *( h * 60 + m) - 6 * m );//小数取绝对值 
	//cout<<angle<<endl;
	if(angle > 180) angle = 360 - angle;
//	if(angle == 0) 
//	{
//		printf("%d", abs(hl - ml));
//		return 0;
//	}
//	if(angle == 180) 
//	{
//		printf("%d", hl + ml);
//		return 0;
//	}
	printf("%.10f", sqrt(hl * hl + ml *ml - 2 * hl * ml * cos(angle * M_PI/180)));
	return 0;
} 

Measured memory_bytes: 4116
#include <bits/stdc++.h>
using namespace std;
const int AMAX= 1 + (int) 1e5;

int main(){
    int N,Q,B,C;
    cin >> N;
    int A[AMAX]={},Atmp;
    for(int i=0; i<N; i++){
        cin >> Atmp;
        A[Atmp]++;
    }
    cin >> Q;

    long ans=0l;
    for(int i=0; i<AMAX; i++){
        ans += (long) A[i]*i;
    }

    for(int i=0; i<Q; i++){
        cin >> B >> C;
        Atmp=A[B];
        A[B]=0;
        A[C]+=Atmp;
        ans -= (long) Atmp*B;
        ans += (long) Atmp*C;
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>

using namespace std;

int N, A[202020], B[202020], order[202020];
bool early_deadline(int i, int j){
	return B[i] < B[j];
}
int main(){
	//freopen("test.in", "r+", stdin);
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> A[i] >> B[i];
		order[i] = i;
	}
	sort(order, order + N, early_deadline);
	long long int total = 0;
	bool flag = true;
	for(int i = 0; i < N; i++){
		total += A[order[i]];
		if(B[order[i]] < total){
			cout << "No\n";
			flag = false;
			break;
		}		
	}
	if(flag)cout << "Yes\n";
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
using namespace std;

vector<int> like;
inline bool isOK(int index, int key){
    if(like.at(index)>=key) return true;
    else return false;
}
inline int binary(int key){
    int left=-1, right=like.size();
    while(right-left>1){
        int mid=left+(right-left)/2;
        if(isOK(mid, key)) right=mid;
        else left=mid;
    }
    return right;
}

signed main(){
    
    vector<int> pr(100001);
    rep(i,100001) pr.at(i)=i;
    vector<bool> isP(100001,true); isP.at(0)=isP.at(1)=false;
    for(int i=2; i<=100000; i++){
        if(isP.at(i)){
            for(int j=i*2; j<=100000; j+=i){
                isP.at(j)=false;
            }
        }
    }
    for(int i=1; i<=100000; i+=2){
        if(isP.at(i) and isP.at((i+1)/2)) like.push_back(i);
    }
    
    int q; cin>>q;
    vector<int> l(q), r(q);
    rep(i,q) cin>>l.at(i)>>r.at(i);
    rep(i,q){
        cout<<binary(r.at(i)+1)-binary(l.at(i))<<endl;
    }
}

Measured memory_bytes: 3072
D,G = map(int,input().split())
PC = [list(map(int,input().split())) for _ in range(D)]
INF = 10**10

P = [D-1-i for i in range(D)]
res = INF
for x in range(2**D):
    x = str(format(x,"b"))
    x = x.zfill(D)#1であれば全部解く、0であれば解かない
    c = 0#点数
    cnt = 0#解いた問題数
    solved = []
    for i,num in enumerate(x):
        if num == "0":
            pass
        else:
            cnt += PC[i][0]
            c += (i+1)*PC[i][0]*100 + PC[i][1]
            solved.append(i)
    if c < G:
        for p in P:
            if p not in solved:
                a = min((G-c)//((p+1)*100),PC[p][0]-1)
                cnt += a
                c += a*(p+1)*100
    if c >= G:
        if cnt <= res:
            res = cnt
print(res)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define file_se_input  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pp long long int
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define eb emplace_back
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned long long int
#define test int t;cin>>t; while(t--)
#define um unordered_map
#define en '\n'
#define us unordered_set
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007
int f[2345678];
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________

	int n;
	cin >> n;
	rep(i, 1, 100)
	{
		rep(j, 1, 100)
		{
			rep(k, 1, 100)
			{
				int x = i * i + j * j + k * k + i * j + j * k + i * k;
				f[x]++;
			}
		}
	}
	rep(i, 1, n)
	{
		cout << f[i] << en;
	}


	return 0;
}



Measured memory_bytes: 4112
use std::collections::BTreeSet;
use std::str::FromStr;

struct Candles {
    xs: Vec<u64>,
    ys: Vec<u64>,
    zs: Vec<u64>,
}

fn parse_line() -> Vec<u64> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let buf = buf.trim();

    buf.split_whitespace()
        .map(|s| u64::from_str(s).unwrap())
        .collect()
}

fn parse() -> (u16, Candles) {
    let fst = parse_line();
    assert_eq!(fst.len(), 4);
    let k = fst[3] as u16;

    let mut xs = parse_line();
    xs.sort();

    let mut ys = parse_line();
    ys.sort();

    let mut zs = parse_line();
    zs.sort();

    let candles = Candles {
        xs: xs,
        ys: ys,
        zs: zs,
    };

    (k, candles)
}

#[derive(Default)]
struct Status {
    candidates: BTreeSet<(u64, u16, u16, u16)>,
}

impl Status {
    fn new(candles: &Candles) -> Status {
        let mut status = Status::default();

        let x = (candles.xs.len() - 1) as u16;
        let y = (candles.ys.len() - 1) as u16;
        let z = (candles.zs.len() - 1) as u16;

        status.push(candles, x, y, z);
        status
    }

    fn pop(&mut self) -> (u64, u16, u16, u16) {
        let ret;

        {
            let mut it = self.candidates.iter();
            ret = *it.next_back().unwrap();
        }

        self.candidates.remove(&ret);

        ret
    }

    fn push(&mut self, candles: &Candles, x: u16, y: u16, z: u16) {
        let val = candles.xs[x as usize] + candles.ys[y as usize] + candles.zs[z as usize];
        self.candidates.insert((val, x, y, z));
    }
}

fn main() {
    let (k, candles) = parse();
    let mut vs = Vec::with_capacity(k as usize);
    let mut status = Status::new(&candles);

    for _ in 0..k {
        let (m, x, y, z) = status.pop();
        vs.push(m);

        if 0 < x {
            status.push(&candles, x - 1, y, z);
        }
        if 0 < y {
            status.push(&candles, x, y - 1, z);
        }
        if 0 < z {
            status.push(&candles, x, y, z - 1);
        }
    }

    for v in &vs {
        println!("{}", v);
    }
}


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

vector<int>vn,vm;

int main(){
	int ma=1,n,m;
	while(cin>>n>>m,n,m){
		for(int i=0;i<n;i++){
			int a;
			cin>>a;
			vn.push_back(a);
			}
		for(int i=0;i<m;i++){
			int a;
			cin>>a;
			vm.push_back(a);
			}
			
			int j=0;
			while(1){
				ma+=vm[j];
				j++;
				if(n<=ma)break;
				ma+=vn[ma-1];
				if(ma<=0)ma=1;
				if(n<=ma)break;
				}
				
				cout<<j<<endl;
				vn.clear();
				vm.clear();	
				ma=1;
		}
		return 0;
	}

Measured memory_bytes: 3040
# include<iostream>
using namespace std;
int main ()
{
	 int n;
	 cin>>n;
	 int k;
	 cin>>k;
   int sum=0;
	 for(int i=0;i<n;i++)
	 {
	 	  int v;
	 	  cin>>v;
	 	  if(v>=k)
	 	  {
	 	  	 sum++;
		   }
	 }
	 
	 cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

	int w;
	int n;
	int a,b;
	char str;
	int ami[30];
	int i;
	int tmp;

	for(i=1;i<=30;i++){
		ami[i-1] = i;
	}

	while(1){
		scanf("%d",&w);
		if(w<=30){
			break;
		}
	}
	while(1){
		scanf("%d",&n);
		if(n<=30){
			break;
		}
	}

	for(n;n>0;n--){
		scanf("%d%c%d",&a,&str,&b);
		tmp = ami[a-1];
		ami[a-1] = ami[b-1];
		ami[b-1] = tmp;
	}

	for(i=0;i<w;i++){
		printf("%d\n",ami[i]);
	}

	return 0;
}

Measured memory_bytes: 0
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define MAX 1000
#define VMAX 10000

int n, A[MAX], s;
int B[MAX], T[VMAX+1];

int solve(){
    int ans = 0;

    bool V[MAX];
    for(int i=0; i<n; i++){
        B[i] = A[i]; //複製
        V[i] = false; //全部falseにする
    }
    sort(B, B+n); //第一引数が先頭イテレータ、第二引数が末尾イテレータ
    for(int i=0; i<n; i++) T[B[i]] = i;
    for(int i=0; i<n; i++){
        if(V[i]) continue;
        int cur = i;
        int S = 0;
        int m = VMAX;
        int an = 0;
        while(1){
            V[cur] = true;
            an++; //サイクル要素数カウント
            int v = A[cur];
            m = min(m,v); //サイクル内最小値更新
            S += v; //サイクル内の総和
            cur = T[v];
            if(V[cur] == true) break;
        }
        ans += min(S+(an-2)*m, m+S+(an+1)*s); //sは最小値(mainで定義)
    }
    return ans;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0); //この2行はより速度を向上させる
    cin >> n;
    s = VMAX;
    for(int i=0; i<n; i++){
        cin >> A[i];
        s = min(s, A[i]);
    }
    int ans = solve();
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3236
use std::{io, cmp};

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let n: i32 = input.split_whitespace().next().unwrap().parse().unwrap();
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let k: i32 = input.split_whitespace().next().unwrap().parse().unwrap();
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let x: i32 = input.split_whitespace().next().unwrap().parse().unwrap();
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let y: i32 = input.split_whitespace().next().unwrap().parse().unwrap();

    // println!("n = {}, k = {}, x = {}, y = {}", n, k, x, y);

    let first = x * cmp::min(n, k);
    let rest = y * cmp::max(0, n - k);
    println!("{}", first + rest);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int
#define mp make_pair
#define endl "\n"
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define lb lower_bound
#define forn(i,n) for(ll i=0 ; i<n ; i++)
#define arr(a,n) for(ll i=0;i<n;i++){ cin>>a[i]; }
#define ub upper_bound
#define pb push_back
#define pi pair<int,int>
#define mod 1000000007
#define vectormax *max_element
#define vectormin *min_element
#define arraysize 1000000
#define setbit _builtin_popcountll
using namespace std;

bool check(int*arr,int n){
vector<int>v,e;
for(int i=0;i<n;i++)
    {
        if(arr[i]!=INT_MIN)
        v.pb(arr[i]);
    }
for(int i=0;i<v.size();i++)
    e.pb(v[i]);
sort(v.begin(),v.end(),greater<int>());
for(int i=0;i<v.size();i++){

    if(v[i]!=e[i])
        return false;

}
return true;
}
int main(){
    int n;
    cin>>n;
//    int a[n];
//    for(int i=0;i<n;i++)
//        cin>>a[i];
//    int arr[43]={};
//    int c=0;
//    for(int i=0;i<43;i++){
//        if(i!=4 and i!=8 and i!=15 and i!=16 and i!=23 and i!=42)
//            arr[i]=INT_MIN;
//    }
//    for(int i=0;i<n;i++){
//        arr[a[i]]++;
//
//        if(!check(arr,43)){
//            c++;
//            arr[a[i]]--;
//        }
//    }
//    cout<<c<<endl;
int ans=0;
if(n%1000==0)
    ans=0;
else
 ans=(n/1000+1)*1000-n;
 cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iomanip>


#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;


// <<fixed<<setprecision(6)<<


int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}


int digsum(int n) {
  int res = 0;
  while(n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}


int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}


int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}


int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}


int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}


int main(){
  vector<int> l;
  for(int i=0;i<5;i++){
    int j;
    cin>>j;
    l.pb(j);
  }
  int k;
  cin>>k;
  bool is=true;
  for(int i=4;i>0;i--){
    for(int j=i-1;j>=0;j--){
      if(l[i]-l[j]>k){
        is=false;
      }
    }
  }
  if(is){
    cout<<"Yay!";
  }
  else{
    cout<<":(";
  }
}

Measured memory_bytes: 256
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial

sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))

s = set(A)
if len(s) == len(A):
    print('YES')
else:
    print('NO')



Measured memory_bytes: 25440
n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
for i in range(n):
  h[i]=abs(a-(t-h[i]*0.006))
ansmin = min(h)
for i in range(n):
  if h[i]==ansmin:
    print(i+1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define F first
#define S second
#define sq(x) (x)*(x)
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
const LL MOD = 1e9 + 7;
const int maxn = 2e5 + 5;
LL pre[maxn];
LL inv[maxn];
LL prei[maxn];
void build(int n){
    pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % MOD;
        inv[i] = (MOD - MOD / i * inv[MOD % i] % MOD) % MOD;
        prei[i] = prei[i-1] * inv[i] % MOD;
    }
}
LL C(int n, int k){
   return pre[n] * prei[k] % MOD * prei[n-k] % MOD;
}
void marmot0814() {
    int h, w, n; cin >> h >> w >> n;
    build(maxn - 1);
    vector<pii> arr(n);
    for (auto &p : arr)
        cin >> p.F >> p.S;
    arr.push_back({h, w});
    sort(arr.begin(), arr.end());
    n ++;
    vector<LL> dp(n, 0);
    for (int i = 0 ; i < n ; i++) {
        dp[i] = C(arr[i].F - 1 + arr[i].S - 1, arr[i].F - 1);
        for (int j = 0 ; j < i ; j++) {
            if (arr[j].F > arr[i].F || arr[j].S > arr[i].S)
                continue;
            int x = arr[i].F - arr[j].F;
            int y = arr[i].S - arr[j].S;
            (dp[i] -= dp[j] * C(x + y, x) % MOD - MOD) %= MOD;
        }
    }
    cout << dp[n - 1] << '\n';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1, kase = 0; // cin >> t;
    while (t--) {
        // cout << "Case #" << ++kase << ":";
        marmot0814();
    }
}

Measured memory_bytes: 8400
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

#Binary Indexed Tree（１点加算）
#1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def add(self, index, x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self, index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self, value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N = I()
S = list(str(input()))
Q = I()

def calc(c):
    return ord(c)-ord('a')

bit = [BIT(N) for _ in range(26)]
for i in range(N):
    bit[calc(S[i])].add(i+1,1)

for i in range(Q):
    now = list(input().split())
    if now[0]=='1':
        iq = int(now[1])
        cq = str(now[2])
        bit[calc(S[iq-1])].add(iq,-1)
        bit[calc(cq)].add(iq,1)
        S[iq-1] = cq
    else:
        lq = int(now[1])
        rq = int(now[2])
        ans = 0
        for j in range(26):
            if lq == 1:
                if bit[j].sum(rq) >= 1:
                    ans += 1
            else:
                if bit[j].sum(rq) != bit[j].sum(lq-1):
                    ans += 1
        print(ans)

Measured memory_bytes: 168656
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    int ans;
    if(a > b){
        ans = b;
    }else{
        ans = a;
    }
    if(c > d){
        ans += d;
    }else{
        ans += c;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#define INF 123456789
#define MOD 1000000007


int N;
int M;
int data[12345678][2];
int hnt[12345678];
int hnt_num = 0;

bool ans_data[12345678];


int main()
{

	scanf("%d%d", &N, &M);

	for (int a = 0; a < M; ++a)
	{
		scanf("%d%d", &data[a][0], &data[a][1]);

		if (data[a][1] == N)
		{
			hnt[hnt_num] = data[a][0];
			++hnt_num;
		}

	}

	std::sort(hnt, hnt + hnt_num);

	ans_data[hnt[0]] = true;

	for (int a = 1; a < hnt_num; ++a)
		if (hnt[a] != hnt[a - 1]) ans_data[hnt[a]] = true;

	for (int a = 0; a < M; a++)
	{
		if (data[a][0] == 1 && ans_data[data[a][1]] == true)
		{
			puts("POSSIBLE");
			return 0;
		}
	}


	puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 8576