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

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
		    int x = sc.nextInt();
		    if (map.containsKey(x)) {
		        map.put(x, map.get(x) + 1);
		    } else {
		        map.put(x, 1);
		    }
		}
		int total = 0;
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
		    int x = entry.getKey();
		    int y = entry.getValue();
		    if (x > y) {
		        total += y;
		    } else {
		        total += y - x;
		    }
		}
       System.out.println(total);
	}
}


Measured memory_bytes: 60900
package main

import "fmt"

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	w := make([]int, n)
	for i := range w {
		fmt.Scan(&w[i])
	}
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = w[i] + s[i]
	}
	ans := 10000
	for i := 1; i < n; i++ {
		s1 := s[i]
		s2 := s[n] - s1
		ans = min(ans, abs(s1-s2))
	}
	fmt.Println(ans)
}


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

int main() {
  int n,m;cin>>n>>m;
  vector<vector<int>> a(n,vector<int>(m));
  vector<int> b(m);
  rep(i,n){
    rep(j,m){
      cin>>a[i][j];
    }
  }
  rep(i,m){
    cin>>b[i];
  }
  rep(i,n){
    int c=0;
    rep(j,m)c+=a[i][j]*b[j];
    cout<<c<<endl;
  }
}


Measured memory_bytes: 3144
readint()=parse.(Int,readline())
N=readint()
c=chomp(readline())

#N=200000
#c="WWRR"

function WR2bit(c)
    b=zeros(Bool,length(c))
    for i in 1:length(c)
        b[i]= c[i]=='W'
    end
    b
end
C=WR2bit(c)

function check_c(C)
    for i in 1:length(C)-1
        C[i] == true && C[i+1] == false && (return i)
    end
    return 0
end
function WR_change(C)
    L=length(C)
    W=sum(C.==true)
    R=L-W
    if R==0
        return 0
    else
        nR=sum(C[1:R].==false)
        return R-nR
    end
end
print(WR_change(C))

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

using ll = long long;
using vll = vector<long long>;
using vi = vector<int>;

// Long long max = 1LL << 50LL;

int solve(vi arr){
  vi dp(arr.size());
  dp[0] = 0;
  dp[1] = abs(arr[1] - arr[0]);
  for(int i = 2; i < arr.size(); i++){
    dp[i] = min(dp[i-1] + abs(arr[i]-arr[i-1]), dp[i-2] + abs(arr[i]-arr[i-2]));
  }
  return dp[arr.size()-1];
}


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

  int n;
  cin >> n;

  vi arr(n);
  for(auto &x: arr) cin >> x;
  cout << solve(arr) << endl;
  return 0;
}

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

using namespace std;

int penalty[100010];
int main() {
    memset(penalty, 0, sizeof(penalty));
    int n, m;
    cin>>n>>m;
    set<int> solvedP;
    int tp = 0;
    while(m--) {
        int q;
        string status;
        cin>>q>>status;
        if(status == "AC") {
            solvedP.insert(q);
        } 
        else if(solvedP.find(q) == solvedP.end()){
            penalty[q]++;
        }
    }
    for(auto i: solvedP) {
        tp += penalty[i];
    }
    
    cout<<solvedP.size()<<" "<<tp;
    return 0;
}

Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
const long double PI = acos(-1);
const long long INF = (1 << 30);
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}

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

  ll n, c, k;
  cin >> n >> c >> k;
  vector<ll> t(n);
  for(ll i = 0; i < n; i++) cin >> t[i];
  sort(all(t));

  ll lim = t[0] + k;
  ll cnt = 0;
  ll ans = 1;
  for(ll i = 0; i < n; i++){
    if(cnt < c && t[i] <= lim){
      cnt++;
    }else{
      cnt = 1;
      lim = t[i] + k;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>

using namespace std;

typedef pair<int, int> P;
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define _1 first
#define _2 second
#define pb push_back
#define mod 1000000007
#define INF 105000000000

const int maxn = 1e5 + 10;
vi g[maxn];
int dis1[maxn], dis2[maxn];

void dfs(int t, int f, int dis[], int dep)
{
	dis[t] = dep;
	for (auto i : g[t])if (i != f) dfs(i, t, dis, dep + 1);
}

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

	ll n; cin >> n;

	int a, b;
	rep(i, n-1) 
	{ 
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	
	dfs(1, 0, dis1, 0);
	dfs(n, 0, dis2, 0);
	int count = 0;
	FOR(i, 1, n + 1) if (dis1[i] <= dis2[i]) count++;

	if (count > n - count) Print("Fennec");
	else Print("Snuke");

	return 0;
}

Measured memory_bytes: 12800
#include <iostream>

int main()
{
  // 用意と入力
  int n;
  int i, nMax = 0;
  int sum;
  std::cin >> n;
  int p[n];
  for (i = 0; i < n; i++)
  {
    std::cin >> p[i];
  }

  // 計算
  for (i = 0; i < n; i++)
  {
    if (p[i] > p[nMax])
    {
      nMax = i;
    }
  }

  sum = p[nMax] / 2;
  for (i = 0; i < n; i++)
  {
    if (i != nMax)
    {
      sum += p[i];
    }
  }

  // 出力
  std::cout << sum << std::endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(input()) for i in range(N)]

A_copy = A[:]
A_copy.sort()
A_max = A_copy[len(A_copy)-1]
A_second = A_copy[len(A_copy)-2]

for i in range(N):
    if A[i] != A_max:
        print(A_max)
    else:
        print(A_second)

Measured memory_bytes: 14112
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key = lambda x: x[1])
'''
Bi についてソートするときには当然ながら 
Aiもこれにしたがってソートしたいので、便宜上これらを 
Xi とまとめてしまいます。
'''
# a[i]はA[i]まで終わらせるためにかかる累積時間
a = [0] * N
a[0] = X[0][0]
for i in range(1, N):
	a[i] = a[i - 1] + X[i][0]

for j in range(N):
	if a[j] > X[j][1]:
		print("No")
		exit()
print("Yes")

Measured memory_bytes: 58260
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int a, b;
    cin >> a >> b;
    if(a > b && b != 1){
        cout << "Alice" << endl;
    }
    else if(a > b && b == 1){
        cout << "Bob" << endl;
    }
    else if(a < b && a != 1){
        cout << "Bob" << endl;
    }
    else if(a < b && a == 1){
        cout << "Alice" << endl;
    }
    else if(a == b){
        cout << "Draw" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
int main(){
    long long int n, m, M, sum, tmp;
    m=1000000;
    M=-1000000;
    sum=0;
    scanf("%lld", &n);
    for(int i = 0; i < n; i++){
        scanf("%lld", &tmp);
        m = std::min(m, tmp);
        M = std::max(M, tmp);
        sum += tmp;
    }
    printf("%lld %lld %lld\n", m, M, sum);
    return 0;
}


Measured memory_bytes: 2752
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n; cin >> n;
  vector<pair<int, int>> A;
  for (int i = 0; i < n; ++i) {
    int a, b; cin >> a >> b;
    A.emplace_back(b, a);
  }
  sort(A.begin(), A.end());
  LL curT = 0;
  for (int i = 0; i < n; ++i) {
    curT += A[i].second;
    if (curT > A[i].first) {
      cout << "No\n";
      exit(0);
    }
  }
  cout << "Yes\n";
}


Measured memory_bytes: 2420
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL n,m,k;
LL ma = INF,mb = INF;
LL ans = INF,a[500005],b[500005],u,v,w;

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(LL i = 1;i <= n;i ++){
		cin >> a[i];
		ma = min(ma,a[i]);
	} 
	for(LL i = 1;i <= m;i ++){
		cin >> b[i];
		mb = min(mb,b[i]);
	}
	ans = ma + mb;
	while(k --){
		cin >> u >> v >> w;
		ans = min(ans,a[u] + b[v] - w);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5120
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int H, W;
    cin >> H >> W;
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    vector<vector<int>> res(H, vector<int>(W));
    vector<int> color;
    rep(i, N) {
        while(A[i] > 0) {
            A[i]--;
            color.pb(i + 1);
        }
    }
    int now = 0;
    for(int i = 0; i < H; i++) {
        if(i % 2 == 0) {
            for(int j = 0; j < W; j++) {
                res[i][j] = color[now];
                now++;
            }
        } else {
            for(int j = W - 1; j >= 0; j--) {
                res[i][j] = color[now];
                now++;
            }
        }
    }
    rep(i, H) {
        rep(j, W) { cout << res[i][j] << " "; }
        cout << endl;
    }
    return 0;
}

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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    map<char, int> mp;
    rep(i, n) {
        mp[s[i]]++;
    }

    int index = 0;
  
  	int cnt = 0;
  	
    rep(i, 26) {
        if(mp[i+'a']==0) {
            index = i;
            break;
        }
      	cnt++;
    }
  
  	//cout << index << endl;
  	char ans = 'a' + index;

    cnt==26 ? cout << "None" << endl :
            cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,s;
    cin>>n>>k>>s;
    vector<int>v(n,s);
    for(int i=k;i<n;i++)
        v[i]=s==1000000000?1:s+1;
    for(int&t:v)
        cout<<t<<' ';
    cout<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h> 
using namespace std; 
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define lcm(a,b)     (a*b)/__gcd(a,b)
#define bs(v,x)      binary_search(v.begin(),v.end(),x)
#define ub(v,x)      upper_bound(v.begin(),v.end(),x)
#define lb(v,x)      lower_bound(v.begin(),v.end(),x)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) (a).begin(),(a).end() 
#define inp(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cerr<<endl;
#define printv(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n";
#define Pi 3.14159265
#define PII pair<ll, ll>; 
#define reset(x) memset(x,'z',sizeof(x))
#define f first
#define s second
#define mp make_pair
#define pq1 priority_queue<ll>;
#define pq2 priority_queue<ll, vector<ll>,greater<ll>>;
typedef long long ll;
typedef vector<ll> vll;
typedef bool B;
typedef double ff;
//const ll INF=1e10;
const ll MAX_N = 100005;
char en='\n';   
         
         void solve()
         {
            ll x;
            cin>>x;
            if(x>=30)
               cout<<"Yes";
            else cout<<"No";
         }

         int main()
         { 
               ios_base::sync_with_stdio(false);cin.tie(NULL); 
               #ifndef ONLINE_JUDGE 
                        freopen("input.txt", "r", stdin); 
                        freopen("error.txt", "w", stderr); 
                        freopen("output.txt", "w", stdout); 
               #endif 
                        int t=1; 
                        //cin>>t; 
                        while(t--) 
                        {   
                           solve();
                           cout<<en;
                        } 
               cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
               return 0; 
         }

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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

int n, t;
int a[MAXN];

bool read() {
    if (!(cin >> n >> t))
        return false;

    forn (i, n)
        cin >> a[i];

    return true;
}

void solve() {
    int curmn = a[0], diff = 0, ans = 0;

    for (int i = 1; i < n; ++i) {
        if (a[i] - curmn > diff) {
            diff = a[i] - curmn;
            ans = 0;
        }

        if (a[i] - curmn == diff)
            ++ans;

        curmn = min(curmn, a[i]);
    }

    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

 class Main {

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

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

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

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

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

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

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }


    public static void main(String[] args){
        FastReader sc = new FastReader();
         int d =sc.nextInt(),n=sc.nextInt();
         /*if(d==0)
             System.out.println(n);
         else if (d==1)
             System.out.println(n*100);
         else{
             System.out.println(n*10000);
         }*/
         if(n>8 || d>8)
             System.out.println(":(");
         else
             System.out.println("Yay!");
}


}


Measured memory_bytes: 21076
{-# LANGUAGE OverloadedStrings #-}
import           Control.Monad
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

import qualified Control.Arrow               as Arrow
import           Data.Bool
import qualified Data.ByteString.Char8       as BSC8

type UnionFind = VUM.IOVector Int

newUF :: Int -> IO UnionFind
newUF n = VUM.replicate n (-1)

rootUF :: UnionFind -> Int -> IO Int
rootUF uf x = do
  p <- VUM.read uf x
  if p < 0 then
    return x
  else do
    r <- rootUF uf p
    VUM.write uf x r
    return r

connectedUF :: UnionFind -> Int -> Int -> IO Bool
connectedUF uf x y = liftM2 (==) (rootUF uf x) (rootUF uf y)

uniteUF :: UnionFind -> Int -> Int -> IO ()
uniteUF uf x y = do
  a <- rootUF uf x
  b <- rootUF uf y
  when (a /= b) $ do
    ar <- VUM.read uf a
    br <- VUM.read uf b
    let (p, c) = if ar < br then (a,b) else (b,a)
    when (ar == br) $ VUM.modify uf pred p
    VUM.write uf c p



type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine

main :: IO ()
main = do
  (n, q) <- parse2
  uf <- newUF n
  replicateM_ q $ do
    (t, u, v) <- parse3
    case t of
      0 -> uniteUF uf u v
      1 -> connectedUF uf u v >>= print . bool 0 1


Measured memory_bytes: 6708
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
void solve(); int main() { solve(); return 0; }

void solve() {
  int a, b;
  string s;
  cin >> a >> b >> s;
  int i=0;
  while (i<a) {
    if (s[i++] == '-') {
      cout << "No" << endl;
      return;
    }
  }
  if (s[i++] != '-') {
    cout << "No" << endl;
    return;
  }
  b += 1 + a;
  while (i<b) {
    if (s[i++] == '-') {
      cout << "No" << endl;
      return;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 3608
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,op[110][20],p[110][20],now[20],ans=INT_MIN;

void dfs(int pos,bool whe)
{
	if(pos==10)
	{
		if(!whe) return;
		int cnt=0,res=0;
		rep(i,n)
		{
			cnt=0;
			rep(j,10) if(now[j]==op[i][j]&&now[j]==1) cnt++;
			res+=p[i][cnt];
		}
		ans=max(ans,res);
		return;
	}
	now[pos]=1;
	dfs(pos+1,true);
	now[pos]=0;
	dfs(pos+1,whe);
}

int main()
{
	cin>>n;
	rep(i,n) rep(j,10) cin>>op[i][j];
	rep(i,n) rep(j,11) cin>>p[i][j];
	dfs(0,false);
	cout<<ans<<endl;
	rt0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,a,b;scanf("%lld%lld%lld",&n,&a,&b);
	long long x,r,sum;x=n/(a+b); r=n%(a+b);
	if(r>a)
	sum=x*a+a;
	else sum=x*a+r;
	printf("%lld",sum); 
}

Measured memory_bytes: 256
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
using namespace std;

int main() {
	int N, A;
	cin >> N >> A ;
	if (N  % 500 <= A) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
	
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void Say(bool say, string a = "Yes", string b = "No"){cout << (say ? a : b) << endl;};
typedef pair<ll, ll>P;

int main(){

    ll N;
    cin >> N;
    vector<ll>a(N);
    for(ll i = 0; i < N; i++)cin >> a[i];
    ll ok = N, ng = 0;
    while(ng + 1 < ok){
        ll p = (ng + ok) / 2;
        set<P>S;
        S.insert(P(-1, -1));
        ll flg = 1;
        for(ll i = 0; i < N; i++){
            set<P>::iterator it = S.lower_bound(P(a[i], 0));
            it--;
            if((*it).first < 0 && S.size() <= p){
                S.insert(P(a[i], i));
            }
            else if((*it).first < 0){
                flg = 0;
                break;
            }
            else{
                S.erase(it);
                S.insert(P(a[i], i));
            }
        }
        if(flg)ok = p;
        else ng = p;
    }
    cout << ok << endl;

    return 0;
}

Measured memory_bytes: 7296
N, M, K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a, b=[0], [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
ans, j=0, M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j]>K-a[i]:
        j-=1
    ans=max(ans, i+j)
print(ans)

Measured memory_bytes: 47372
#include <iostream>

using namespace std;


int main() {
	
	int a, b;

	cin >> a >> b;

	if (a >= b)
		cout << "1\n";

	else if (b % a == 0)
		cout << b / a << "\n";

	else
		cout << b / a + 1 << "\n";

	return 0;

}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100;
vector<vector<pair<int, int>>> data(1000); 
void solve()
{
}
int main()
{
    int n, i = 0;
    cin >> n;
    cout << 180 * (n - 2) << endl;
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std; 
int main() { 
  int a, b, c, d, l, ja, math;   
  cin >> l >> a >> b >> c >> d; 
  ja = a/c;
  if(a%c!=0) ja++; 
  math = b/d;  
  if(b%d!=0) math++;  
  if(ja > math) l-=ja; 
  else l-=math;   
  cout << l << endl; 
  return 0;
}


Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
vector<ll>a[200010];
ll n,q,ans[200010];
void dep(ll now,ll p){
	if(p!=-1&&a[now].size()==1){
		return ;
	}
	for(ll i=0;i<a[now].size();i++){
		ll next=a[now][i];
		if(next==p){
			continue;
		}
		ans[next]=ans[now]+ans[next];
		dep(next,now);
	}
}
int main() {
	cin>>n>>q;
	for(ll i=0;i<n-1;i++){
		ll x,y;
		cin>>x>>y;
		x--;y--;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(ll i=0;i<q;i++){
		ll x,y;
		cin>>x>>y;
		x--;
		ans[x]+=y;
	}
	dep(0,-1);
	for(ll i=0;i<n;i++){
		cout << ans[i]<<" ";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 24320
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;

int main() {
	speed;
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < s.size(); ++i)
		if (s[i] != t[i])
			ans++;
	cout << ans;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
vi P, Q;

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int a; cin >> a; a--;
		P.pb(a);
	}
	rep(i, 0, N) {
		int a; cin >> a; a--;
		Q.pb(a);
	}
	int a = -1, b = -1;
	int cnt = 0;

	vi vec;
	rep(i, 0, N) vec.pb(i);

	do {
		if(vec == P) a = cnt;
		if(vec == Q) b = cnt;
		cnt++;
	} while(next_permutation(all(vec)));
	cout << abs(a - b) << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
bool map[256][256],cop[256][256];
int main() {
	int n;
	char z;
	while(true){
	cin>>n;
	if(n==0)break;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>z;
			if(z=='0')map[i][j]=false;
			else map[i][j]=true;
		}
	}
	int dx[4]={0,1,1,-1},dy[4]={1,0,1,1};
	int ans=0;
	for(int set=0;set<4;set++){
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)cop[i][j]=map[i][j];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(cop[i][j]){
					int cnt=0,x=j,y=i;
					while(true){
						if(!(x>=0&&x<n&&y>=0&&y<n))break;
						if(!map[y][x])break;
						cop[y][x]=false;
						x+=dx[set],y+=dy[set];
						cnt++;
					}
					ans=max(cnt,ans);
				}
			}
		}
	}
	cout<<ans<<endl;
    }
	return 0;
}

Measured memory_bytes: 1292
/*
SHERAJUL ARIFIN
Dept. of CSE,
IUT.
*/

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long int N,x,y,a=0,b=0;
    cin>>N;


    int root=sqrt(N);


    int i;
    for(i=root; i>=1; i--)
    {
        if(N%i==0)
        {
            a=i;
            b=N/i;
            break;
        }
    }
    x=a-1;
    y=b-1;
    cout<<x+y; 



    return 0;
}


Measured memory_bytes: 256
import math

X, K, D = map(int, input().split())

dis_X = abs(X)
stps = int(dis_X/D)

if K < stps:
  print(dis_X - K*D)
else:
  diff_stps = K - stps
  if diff_stps % 2 : #odd
    print( (stps+1)*D - dis_X )
  else: # even
    print( dis_X - stps*D )


Measured memory_bytes: 9120
n = gets.chomp.to_i
for i in 0..(n - 1)
  a = gets.split(' ').map{|item| item.to_i}
  a = a.sort
  if a[2] ** 2 == a[0] ** 2 + a[1] ** 2
    puts "YES"
  else
    puts "NO"
  end
end



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

int	main()
{
    string S;
    cin >> S;
    int N = S.size();
    int max_len = 0;
    set<char> ATGC_set({'A', 'T', 'G', 'C'});
    for (int i = 0; i < N; ++i) {
        for (int j = i; j < N; ++j) {
            bool is_ATGC = true;
            for (int k = i; k <= j; ++k) {
                if (!ATGC_set.count(S.at(k))) {
                    is_ATGC = false;
                    break;
                }
            }
            if (!is_ATGC)
                continue;
            int len = j - i + 1;
            if (max_len < len)
                max_len = len;
        }
    }
    cout << max_len << endl;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, a[N], cnt[35];
int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	ll ans = 0;
 	int l = 0;
	for(int i=1; i<=n; i++)
	{	
		bool ok = 1;
		for(int j=0; j<=30; j++)
		{
			if((a[i]>>j)&1) 
			{
				cnt[j]++;
				if(cnt[j]>1) ok = 0;
			}
		}
		if(ok) ans += i - l;
		else
		{
			for(l=l+1; l<=i;l++)
			{
				for(int k=0; k<=30; k++)
				{
					if((a[l]>>k)&1) cnt[k]--;
				}
				bool ok = 1;
				for(int k=0; k<=30; k++)
					if(cnt[k]>1) ok = 0;
				if(ok) break;
			}
			ans += i - l;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1152
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe
import qualified Data.Set as Set

readInt = fst . fromJust . BS.readInt

readString = map BS.unpack . BS.words

getInt = readInt <$> BS.getLine

getString = readString <$> BS.getLine

ordNub :: Ord a => [a] -> [a]
ordNub xs =
  foldr
    ( \x k s ->
        if Set.member x s
          then k s
          else x : k (Set.insert x s)
    )
    (const [])
    xs
    Set.empty

comb' :: Int -> String -> String -> [String]
comb' _ [] _ = []
comb' 1 xs _ = [[x] | x <- (ordNub xs)]
comb' n (x : xs) ys
  | x `notElem` ys = [x : y | y <- comb' (n -1) xs []] ++ comb' n xs (x : ys)
  | otherwise = comb' n xs ys

main = do
  n <- getInt
  [s] <- getString
  print $ length (comb' 3 s "")


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
    ll k,a,b;
    cin>>k>>a>>b;
    for(ll i=a;i<=b;i++){
        if(i%k==0) {
            cout<<"OK"<<en;
            return;
        }
    }
    cout<<"NG"<<en;

}

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

    solve();
    //ll t;cin>>t;REP(i,t) solve();

    return 0;
}


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

int main() {
    // 制約見て！！！デカかったらlong longにすること！
    long q,h,s,d,n;
    cin >>q>>h>>s>>d>>n;
    q *= 4;
    h *= 2;
    long minimum = min(q,h);
    minimum = min(minimum,s);
    long ans = 0;
    if(n >= 2){
        if(2*minimum > d){
            ans = n/2 * d;
            n = n%2;
        }
    }
    ans += n*minimum;
    cout << ans <<endl;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1234567;
int u[maxn], dist[maxn];
void init(int sz){
	for(int i = 0; i < sz; i++) u[i] = i;
}
int find(int x){
	if(x == u[x]) return x;
	return u[x] = find(u[x]);
}
vector<pair<int,int> > e[maxn], ed[maxn];
int nds;
int main(){
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x, y, z; cin >> x >> y >> z;
		ed[z].push_back({x, y});
	}
	nds = n + 1;
	for(int i = 0; i < maxn; i++){
		if(ed[i].empty()) continue;
		vector<int> now;
		for(auto ee : ed[i]){
			now.push_back(ee.first);
			now.push_back(ee.second);
		}
		sort(now.begin(), now.end());
		now.erase(unique(now.begin(), now.end()), now.end());
		int len = now.size();
		init(len);
		for(auto ee : ed[i]) u[find(lower_bound(now.begin(), now.end(), ee.first) - now.begin())] = find(lower_bound(now.begin(), now.end(), ee.second) - now.begin());
		vector<int> who(len);
		for(int i = 0; i < len; i++) who[i] = nds++;
		for(auto ee : ed[i]){
			int x, y; tie(x, y) = ee; int par = who[find(lower_bound(now.begin(), now.end(), x) - now.begin())];
			e[x].push_back({par, 1});
			e[y].push_back({par, 1});
			e[par].push_back({x, 0});
			e[par].push_back({y, 0});
		}
	}
	deque<pair<int,int> > q;
	memset(dist, -1, sizeof(dist));
	q.push_back({1, 0}); dist[1] = 0;
	while(!q.empty()){
		int cur, steps; tie(cur, steps) = q.front(); q.pop_front();
		if(dist[cur] != steps) continue;
		if(cur == n) return cout << steps << endl, 0;
		for(auto ee : e[cur]){
			if(dist[ee.first] == -1 || dist[ee.first] > dist[cur] + ee.second){
				dist[ee.first] = dist[cur] + ee.second;
				if(ee.second) q.push_back({ee.first, dist[ee.first]});
				else q.push_front({ee.first, dist[ee.first]});
			}
		}
	}
	cout << -1 << endl;
	return 0;
}





Measured memory_bytes: 81920
using System;

namespace ITP1_3_B
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int j=1; j<10001; j++)
            {
                long num = long.Parse(Console.ReadLine());

                if (num == 0) break;
                                
                Console.WriteLine("Case {0}: {1}", j, num);
                
            }
        }
    }
}

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

using ll = long long;
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define repk(n) for (int k = 0; j < n; k++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (auto i = a; i < b; i++)
#define repv(itr) for (auto&& v : itr)
#define swap(x, y)    \
  {                   \
    auto ___temp = x; \
    x = y;            \
    y = ___temp;      \
  }

const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << min(c, b / a) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(a.rbegin(), a.rend());
	int tmp = -1;
	rep(i, n - 1) {
		if (a[i] == a[i + 1]) {
			if (tmp == -1) {
				tmp = a[i];
				i++;
			}
			else {
				cout << (long long)tmp * a[i] << endl;
				return 0;
			}
		}
	}
	cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    ll n,d;cin>>n>>d;d*=d;
    ll res=0;
    rep(i,n){
        ll x,y;cin>>x>>y;
        ll buf=x*x+y*y;
        if(buf<=d)res++;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define my_max(a, b) ((a) > (b) ? (a) : (b))
#define my_min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rep(i, s, t) for(int i = (int)(s); i <= (int)(t); i++)
#define rev(i, t, s) for(int i = (int)(t); i >= (int)(s); i--)
#define lson rt << 1
#define rson rt << 1 | 1
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double lb;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> VI;
typedef std::vector<ll> VL;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
ll gcd(ll x, ll y) {
    return y % x == 0 ? x : gcd(y % x, x);
}
template<class T>T my_abs(T a) {
    if(a < 0)
        a = -a;
    return a;
}
inline ll read() {
    ll ret = 0, sign = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')
            sign = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        ret = ret * 10 + c - '0';
        c = getchar();
    }
    return ret * sign;
}
inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

//void expand_stack_space(){
//    int size = 256 << 20; // 256MB
//    char *p = (char*)malloc(size) + size;
//    __asm__("movl %0, %%esp\n" :: "r"(p));
//}
const int maxn = 2e5 + 7;
const int inf = 0x3f3f3f3f;
int n, a[maxn], dp[maxn], ans[maxn];

vector<int> G[maxn];

void dfs(int u, int fa) {
    auto it = lower_bound(dp + 1, dp + n + 1, a[u]);
    int tmp = *it;
    *it = a[u];
    ans[u] = lower_bound(dp + 1, dp + n + 1, inf) - dp - 1;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
    *it = tmp;
}
int main() {
#ifndef ONLINE_JUDGE
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}


Measured memory_bytes: 28480
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctype.h>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef priority_queue<int> p_que;
typedef priority_queue<int, vector<int>, greater<int>()> p_que_rev;
// const int INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};


int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    int n_pal = 0;
    string s = to_string(n);
    n_pal = (s[2] - '0') * 100 + (s[1] - '0') * 10 + (s[0] - '0');
    if(n == n_pal){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

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

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

  int n;
  cin >> n;
  vector<int> h(n);
  rep(i, 0, n) cin >> h[i];
  rep(i, 1, n) {
    if (h[i] > h[i - 1]) h[i]--;
    if (h[i] < h[i - 1]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000000

int main(){
	
	long long N,M;
	cin>>N>>M;
	
	vector<vector<int>> E(N,vector<int>());
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	vector<int> color(N,-1);
	queue<int> Q;
	Q.push(0);
	color[0] = 0;
	
	while(Q.size()!=0){
		int u = Q.front();
		Q.pop();
		for(int i=0;i<E[u].size();i++){
			int v = E[u][i];
			if(color[v]==-1){
				color[v]=color[u]^1;
				Q.push(v);
			}
			else{
				if(color[v]==color[u]){
					cout<<N*(N-1)/2 - M<<endl;
					return 0;
				}
			}
		}
	}
	
	vector<long long> c(2,0);
	
	for(int i=0;i<N;i++)c[color[i]]++;
	
	cout<<c[0]*c[1]-M<<endl;
	
	return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define low lower_bound
#define upp upper_bound
#define inf 1000000007 //10^9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
	int n,cnt=0,MAX=0;
	cin>>n;
	int a[n];
	mii mp;
	rep(i,n) {
		cin>>a[i];
		mp[a[i]]++;
		MAX=max(MAX,a[i]);
	}
	rep(i,MAX) {
		if(mp[i+1]) cnt++;
	}
	cout<<cnt-(cnt+1)%2<<endl;
}


Measured memory_bytes: 7296
#pragma GCC optimize("O3")

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second

ll mod =1e9+7;

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n,k;
    cin >> n >> k;
    vector<ll> arr(n);
    F0R(i,n) cin >> arr[i];
    vector<pair<ll,ll>> ba(n,{0,0});
    F0R(i,n)
    {
        F0R(j,n)
        {
            if(j<i && arr[j]<arr[i])
                ba[i].f++;
            if(j>i && arr[i]>arr[j])
                ba[i].s++;
        }
        //cout << ba[i].f << " " << ba[i].s << endl;
    }
    ll tot=0;
    F0R(i,n)
    {
        tot+=((k*(k-1)/2)%mod)*(ba[i].f+ba[i].s);
        tot%=mod;
        tot+=(k)*ba[i].s;
        tot%=mod;
    }
    cout << tot;

    return 0;
}


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

using namespace std;

int main() {
  string s;
  cin >> s;
  string t = s;
  int n = (int) s.size();
  vector<bool> seen(26, false);
  for (char &c : s) {
    seen[c -= 'a'] = 1;
  }
  set<int> st;
  for (int i = 0; i < 26; i++) {
    if (!seen[i]) {
      st.insert(i);
    }
  }
  if (s.size() < 26) {
    s += *st.begin();
  } else {
    for (int i = n - 1; i >= 0; i--) {
      st.insert(s[i]);
      if (*st.rbegin() <= s[i]) {
        continue;
      }
      for (int x : st) {
        if (x > s[i]) {
          s[i] = x;
          st.erase(x);
          break;
        }
      }
      for (int j = i + 1; j < n; j++) {
        s.pop_back();
      }
      break;
    }
  }
  for (char &c : s) {
    c += 'a';
  }
  if (s == t) {
    cout << -1 << endl;
  } else {
    cout << s << endl;
  }
}


Measured memory_bytes: 3632
#import"bits/stdc++.h"
main(){long long n,a,b,c,d,m;std::cin>>n>>a>>b;for(int i=n;n>1;n--){std::cin>>c>>d;m=std::max((a-1)/c+1,(b-1)/d+1);a=c*m;b=d*m;}std::cout<<a+b;}

Measured memory_bytes: 256