akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<math.h>
double d,r,s,z[6];
int n,i,j,a[50];
int main(){
	for(scanf("%d",&n);n--;){
		for(i=0;i<6;i++)
			scanf("%lf",z+i);
		r=z[2];
		s=z[5];
		d=hypot(*z-z[3],z[1]-z[4]);
		printf("%d\n",a[j++]=d>r+s?0:r>d+s?2:s>d+r?-2:1);
	}
	
	i=a[8];
	if(i==2)puts("");
	else if(i==-2)while(1);
	else if(i==1)return 1;
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int sval(string& s, int i)
{
	return s[i] - '0';
}

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

	int n, p; cin >> n; cin >> p;
	string s; cin >> s;

	if (p == 2 || p == 5) {
		int64_t ans = 0;
		FOR_DW(i, n - 1, 0) {
			if (sval(s, i) % p == 0) {
				ans += (i + 1);
			}
		}
		cout << ans << endl;
		return 0;
	}

	vector<int64_t> ns(p);
	{
		int64_t v = 1;
		int64_t t = 0;
		FOR_DW(i, n - 1, 0) {
			t += v * sval(s, i);
			t %= p;
			v *= 10;
			v %= p;

			ns[t]++;
		}
	}

	int64_t ans = 0;
	int64_t v = 1;
	int64_t t = 0;
	FOR_DW(i, n - 1, 0) {
		ans += ns[t];
		t += v * sval(s, i);
		t %= p;
		v *= 10;
		v %= p;
		ns[t]--;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 720
import java.util.*;
public class Main
{
  public static void main(String[] args)
  {
    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
   int a[]=new int[n];
   HashSet<Integer> h=new HashSet<Integer>();
boolean b=true;
  for(int i=0;i<n;i++)
  {
    a[i]=s.nextInt();
if(b)
{
if(h.contains(a[i]))
b=false;
else
{
h.add(a[i]);
}
}
}
if(b)
System.out.println("YES");
else
    {
     System.out.println("NO");
   }
}
}

   



Measured memory_bytes: 102676
const long long MOD = 1000000007;
#include <bits/stdc++.h>
using namespace std; void solve(); int main(){cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); solve();}
using ll=int_fast64_t; using ld=long double; using pll=pair<ll,ll>; using pld=pair<ld,ld>;
#define fi first
#define se second
#define SELECTOR(_1,_2,_3,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
template<class T> void vecout(const T &v){for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n"))cout<<*it;}
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}

template <std::uint_fast64_t Modulus> class modint {
public:
  ll a;
  constexpr modint(const ll x = 0) noexcept : a(x % Modulus) {}
  constexpr ll &value() noexcept { return a; }
  constexpr const ll &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    ll exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

void solve(){
  ll L,R; cin>>L>>R;
  ll D=61;
  auto dp=make_v(D+1,2,2,2,modint<MOD>(0));
  dp[D][0][0][0]=modint<MOD>(1);
  for(ll d=D-1;d>=0;--d){
    ll lb=L>>d&1, rb=R>>d&1;
    rep(i,2)rep(j,2)rep(m,2)rep(x,2)rep(y,2){
      ll ni=i,nj=j,nm=m;
      if(x>y) continue;
      // i:L<=X
      if(!i && lb>x) continue;
      if(lb<x) ni=1;
      // j:Y<=R
      if(!j && y>rb) continue;
      if(y<rb) nj=1;
      // m:MSB
      if(!m && x!=y) continue;
      if(x==1 && y==1) nm=1;
      dp[d][ni][nj][nm]+=dp[d+1][i][j][m];
    }
  }
  modint<MOD> ans=0;
  rep(i,2)rep(j,2)rep(m,2) ans+=dp[0][i][j][m];
  cout<<ans.a<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
#include <stdlib.h>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define ssort(z) sort(z.begin(),z.end())
#define rsort(z) sort(z.rbegin(),z.rend())
#define eerase(z) z.erase(unique(z.begin(),z.end()),z.end())
#define ccnt(z,w) count(z.begin(),z.end(),w)


void printVec(std::vector<int> & vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec2(std::vector<Int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a / gcd(a, b) *b;
	//a*bは64bit integer overflow
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

string gen(int num) {
	string str = "";
	for (int i = 0; i < num; i++) str += ".";
	return str;
}
Int fact(int num) {
	if (num == 0) return 1;
	else return num * fact(num - 1);
}


int main() {
	string s; cin >> s;
	int ss = 0;
	for (int i = 0; i < 4; i++) {
		if (s[i] == '+')ss++;
		else ss--;
	}
	cout << ss;

	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
long long x[200000],s[200000][3],n,m,b[200000],sum;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		if(i>=2){
			for(int j=b[i-1];j<b[i];j++){
				x[j]++;
			}
			for(int j=b[i];j<b[i-1];j++){
				x[j]++;
			}
		}
	}
	for(int i=1;i<n;i++){
		cin>>s[i][0]>>s[i][1]>>s[i][2];
	}
	for(int i=1;i<n;i++){
		sum+=min(s[i][0]*x[i],s[i][1]*x[i]+s[i][2]);
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 5256
#include<bits/stdc++.h>
using namespace std;
int n,a[100050],b[100050];
bool cmp(int x,int y)
{
	return a[x]==a[y]?x>y:a[x]<a[y];
}
set<int>st;
set<int>::iterator it;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=i;
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int x=b[i];
		if(st.size())
		{
			it=st.lower_bound(x);
			if(it!=st.begin())
			{
				it--;
				st.erase(it);
			}
		}
		st.insert(x);
	}
	cout<<st.size();
}

Measured memory_bytes: 5760
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - 755
            int n = int.Parse(Console.ReadLine());
            
            //Nのケタ数を取得
            int digit = n.ToString().Length;
            int count = 0;

            for(int i = 1; i <= digit; i++)
            {
                var numStrs = CreateThreeNumberPairs(i);
                count += CountShichigosanNumbers(numStrs, n);
            }
                
            Console.WriteLine(count);    
        }
        
        static int CountShichigosanNumbers(List<string> numStrs, int upper)
        {
            int count = 0;
            
            foreach(var s in numStrs)
            {
                if(s.Contains("3") && s.Contains("5") && s.Contains("7"))
                {
                    int num = int.Parse(s);
                    
                    if(num >= 357 && num <= upper)
                    {
                        //Console.WriteLine(s);
                        count++;    
                    }
                }    
            }
            
            return count;
        }

        static List<string> CreateThreeNumberPairs(int digit)
        {
            var threes = new List<string> { "3", "5", "7" };
            var result = new List<string>(threes);

            for(int i = 1; i < digit; i++)
            {
                var source = new List<string>(result);
                result.Clear();

                foreach(string s in source)
                {
                    for(int j = 0; j < 3; j++)
                    {
                        result.Add(s + threes[j]);    
                    }
                }
            }

            return result;
        }
    }
}

Measured memory_bytes: 13268
/*#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin>>x>>y;
  cout<< x+y+2-1-__gcd(x,y) <<endl;
  return 0;
}*/
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int	x,y,sum;
	cin>>x>>y;
	sum=x+y+1-__gcd(x,y);
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3120
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 整数の入力
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    // 判定の出力
    if (a-b == b-c || c-b == b-a) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }
}

Measured memory_bytes: 23892
import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')

Measured memory_bytes: 44744
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

l = []
l.append(a)
l.append(b)
l.append(c)
l.append(d)
l.append(e)
ans = 0
for i in range(5):
    for j in range(i+1,5):
        if l[j] - l[i] > k :
            ans += 1

if ans == 0 :
    print("Yay!")
else :
    print(":(")


Measured memory_bytes: 9136
def main():
    n, c = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(c)]
    C = [list(map(int, input().split())) for _ in range(n)]
    ans = [None]*3
    for k in range(3):
        costs = []
        for nc in range(c):
            cost = 0
            for i in range(n):
                s = (i+k)%3
                ci = C[i]
                for j in range(2-s, n, 3):
                    color = ci[j]-1
                    cost += D[color][nc]
            costs.append(cost)
        ans[k] = list(sorted({index:cost for index, cost in enumerate(costs)}.items(), key=lambda x: x[1]))[:3]
    out = 10**12
    for i in range(3):
        for j in range(3):
            for k in range(3):
                if len(set([ans[0][i][0], ans[1][j][0], ans[2][k][0]])) == 3:
                    out = min(out, ans[0][i][1]+ans[1][j][1]+ans[2][k][1])
    print(out)
            
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 43232
def selectionSort(table):
    swap_count = 0
    for nAchieve in range(len(table)):
        min_index = nAchieve
        for i in range(nAchieve, len(table)):
            if table[i] < table[min_index]:
                min_index = i
        if min_index != nAchieve:
            table[min_index], table[nAchieve] = table[nAchieve], table[min_index]
            swap_count += 1
    return swap_count


element = int(input())
table = list(map(int, input().split()))
swap_count = selectionSort(table)

print(' '.join(map(str, table)))
print(swap_count)



Measured memory_bytes: 5600
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for (ll i = 0; i < (n); ++i)

double a,b;
int h,m;
int t;
double r_a_x,r_a_y,r_b_x,r_b_y;
double theta_a,theta_b;
double dx,dy;
double dist;

int main() {
    cin >> a >> b >> h >> m;
    t = h*60 + m;
    theta_a = (-1.0)*t*(M_PI/360.0)+(M_PI/2.0);
    theta_b = (-1.0)*t*(M_PI/30.0)+(M_PI/2.0);
    r_a_x = a*cos(theta_a);
    r_a_y = a*sin(theta_a);
    r_b_x = b*cos(theta_b);
    r_b_y = b*sin(theta_b);
    dx = r_a_x - r_b_x;
    dy = r_a_y - r_b_y;
    dist = sqrt(dx*dx + dy*dy);
    cout << fixed << setprecision(9) << dist << endl;
    return 0;
}

Measured memory_bytes: 4096
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(raw_input())
a = map(int, raw_input().split())

'''math
total=x+y
y=total-x
x-y=x-(total-x)
   =2x-total
|x-y|=|2x-total|
'''

total = sum(a)
x = a[0]
answer = abs(x*2-total)
for i in range(1,N-1):
    x += a[i]
    answer = min(answer, abs(x*2-total))

print answer


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

const int max_n = 1e5 + 10;

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

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main()
{
    string s;
    cin >> s;
    long long count[2], result[max_n];
    for (int i = 0; i < max_n; ++i)
    {
        result[i] = 0;
    }
    count[0] = 0;
    count[1] = 0;

    for (int i = 0; i < s.size() - 1; ++i)
    {
        if (s[i] == 'R')
        {
            ++count[i % 2];

            if (s[i + 1] != 'R')
            {
                result[i] += count[i % 2];
                result[i + 1] += count[(i + 1) % 2];
                count[0] = 0;
                count[1] = 0;
            }
        }
    }

    count[0] = 0;
    count[1] = 0;
    for (int i = s.size() - 1; i >= 1; --i)
    {
        if (s[i] == 'L')
        {
            ++count[i % 2];
            if (s[i - 1] != 'L')
            {
                result[i] += count[i % 2];
                result[i - 1] += count[(i - 1) % 2];
                count[0] = 0;
                count[1] = 0;
            }
        }
    }

    for (int i = 0; i < s.size(); ++i)
    {
        cout << result[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Contest20191031
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] b = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] c = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int sum = b[0];

            for (int i = 1; i < n; i++) 
            {
                sum += b[i];

                if (a[i] - a[i - 1] == 1)
                    sum += c[a[i - 1]-1];

            }

            Console.WriteLine(sum);

        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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 long long ll;

using namespace std;




int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout<<setprecision(10);
  int h,w;
  cin>>h>>w;
  int edge[10][10];
  rep(i,10)rep(j,10)cin>>edge[i][j];
  vector<int> dist(10,1000);
  dist[1]=0;
  rep(i,100)rep(j,10)rep(k,10)
  {
    if(dist[k]==1000)continue;
    chmin(dist[j],dist[k]+edge[j][k]);
  }
  int res=0;
  rep(i,h)rep(j,w){int a;cin>>a;if(a>=0)res+=dist[a];}
  cout<<res<<endl;
    return 0;

}


Measured memory_bytes: 384
#include<stdio.h>
#include<math.h>
int main()
{
	long long int n;
	scanf("%lld", &n);
	long long int ans = 0;
	long long int i;
	for (i = 1; i < sqrt(n); i++)
		if (n % i == 0)
			if ((n / i) - 1 > i)
				ans += (n / i) - 1;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
#include <numeric>
using namespace std;


const long double PI = 3.14159265358979323846264338327950;
const int N = 3;

template <class T>
T gcd(T a, T b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int digit[N];

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

	int n, k;
	cin >> n >> k;
	int ans = log(n) / log(k) + 1;
	cout << ans << '\n';
}


Measured memory_bytes: 3824
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int n = ni(), a = ni(), b = ni();
        int[] c = new int[3];
        for(int i = 0; i< n; i++){
            int x = ni();
            if(x<=a)c[0]++;
            else if(x<=b)c[1]++;
            else c[2]++;
        }
        pn(Math.min(c[0], Math.min(c[1], c[2])));
    }
    //SOLUTION END
    void hold()throws Exception{throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1e9+7, IINF = (long)4e18;
    final int INF = (int)2e9, MX = (int)1e6+1;
    DecimalFormat df = new DecimalFormat("0.000000000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        //Solution Credits: Taranpreet Singh
        pre();for(int i = 1; i<= T; i++)solve(i);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    String nln(){return in.nextLine();}
    int ni(){return Integer.parseInt(in.next());}
    long nl(){return Long.parseLong(in.next());}
    double nd(){return Double.parseDouble(in.next());}

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

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

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

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

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)

ll INF = 1ll<<61;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

class Dijkstra {
private:
    int N;
    vvii E;

    void init(int n) {
        E.resize(0); E.clear();
        N = n; E.resize(n);
    }

public:
    Dijkstra() {}
    Dijkstra(int n) { init(n); }

    void add(int from, int to, int cost) {
        E[from].push_back(ii(to, cost));
    }

    vi solve(int s) {
        vi dis(N, INF);
        vector<bool> vis(N);
        dis[s] = 0;

        min_priority_queue<ii> q;
        q.push(ii(0, s));

        while (!q.empty()) {
            int t, d;
            tie(d, t) = q.top(); q.pop();

            if (vis[t]) continue;
            vis[t] = true;

            FORE (p, E[t]) {
                ll next = p.first, c = p.second;
                if (vis[next]) continue;
                if (dis[t] + c < dis[next]) {
                    dis[next] = dis[t] + c;
                    q.push(ii(dis[next], next));
                }
            }
        }
        return dis;
    }
};

ll N, M, S, T;
Dijkstra dij_y, dij_s;

void solve() {
    vi cost_y = dij_y.solve(S);
    vi cost_s = dij_s.solve(T);

    min_priority_queue<ii> que;
    REP (i, N) que.push(ii(cost_y[i] + cost_s[i], i));

    REP (i, N) {
        while (que.top().second < i) que.pop();
        cout << (ll)1e15 - que.top().first << " ";
    }
    cout << endl;
}

int main() {
    cin >> N >> M >> S >> T;
    S--; T--;
    dij_y = dij_s = Dijkstra(N);
    REP (i, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        dij_y.add(u, v, a); dij_y.add(v, u, a);
        dij_s.add(u, v, b); dij_s.add(v, u, b);
    }
    solve();
}

Measured memory_bytes: 19836
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, X;
  cin >> A >> B >> X;
  if (A <= X && A + B >= X) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

        

Measured memory_bytes: 3596
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdlib>  
#include <cmath>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int>h(n);
    int ans = 0;
    for(int i = 0; i < n; i++){
      cin >> h.at(i);
      if(h.at(i) >= k){
        ans++;
      }
    }
    cout << ans << endl;
}



Measured memory_bytes: 640
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { 
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int N = I.nextInt();
		long min = (long)(1e12);
		long[] a = new long[N];
		long ans = 0;
		int in = N-1;
		for (int i = 0; i < N; i++) {
			long x = I.nextLong();
			a[i] = x;
		}
		Arrays.sort(a);
		ans+=a[in];
		in--;
		int left = (int)ceil(N-1,2); //Have already fixed biggest
		int itr = 0;
		int tot = 2;
		while (tot<N) {
			ans+=a[in];
			itr++;
			if (itr==2) {
				itr=0;
				in--; //Every other number has 2 slots
			} 
			tot++;
		}
		O.pln(ans);
	}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				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());};
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
	}
}


Measured memory_bytes: 56328
#include<iostream>
using namespace std;
#define int long long
const int Mod = 1e9+7 ;
const int mxn = 2e6 ;
const int N=200005, M=8000;
int frac[mxn+5], inv[mxn+5];
int dp[M/2+5][M/2+5], base=M/4+2;
int n, a[N], b[N];
int power(int a, int b){
	int res=1, car=a; 
	while(b){
		if(b&1) (res*=car)%=Mod;
		(car*=car)%=Mod;
		b>>=1;
	}
	return res;
}
void init(){
	frac[0]=1 ;
	for(int i=1;i<mxn;++i) (frac[i]=frac[i-1]*i)%=Mod ;
	inv[mxn-1] = power(frac[mxn-1], Mod-2);
	for(int i=mxn-2;i>0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;
	inv[0] = 1 ;
}
int C(int n, int k){
	return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;
}
long long ans = Mod ;
signed main(){
	init() ; cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i]>>b[i], ++dp[base-a[i]][base-b[i]];
	for(int i=1;i<=M/2+2;++i) for(int j=1;j<=M/2+2;++j) (dp[i][j]+=(dp[i-1][j]+dp[i][j-1]))%=Mod;
	for(int i=1;i<=n;++i) (ans+=dp[a[i]+base][b[i]+base]), (ans-=C(2*a[i]+2*b[i], 2*a[i]))%=Mod ; (ans+=Mod)%=Mod ;
	cout<<(ans*power(2, Mod-2))%Mod<<endl ;
}

Measured memory_bytes: 159872
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/



int main() {
int X,N;
cin>>X>>N;
int p;
map<int,int> map;
rep(i,N){
  cin>>p;
  map[p]++;
}


rep(i,1000){
  if(map[X-i]==0){
    cout<<X-i<<endl;
    return 0;
  }
  if(map[X+i]==0){
    cout<<X+i<<endl;
    return 0;
  }

  
}


return 0;
}

Measured memory_bytes: 3596
# include<iostream>
# include<cstring>
using namespace std;
int main ()
{
	
    int S,W;
	cin>>S>>W;
	
	if(S<=W)
   {
   	  cout<<"unsafe"<<endl;
   }
   else
   {
   	   cout<<"safe"<<endl;
	   }	
	
 } 

Measured memory_bytes: 3636
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
ans=0
for i in range(N):
    A=list(map(int,input().split()))
    l=0
    for i in range(M):
        l+=A[i]*B[i]
    if l+C>0:
        ans+=1
print(ans)

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

int main()
{
    int k;
    cin >> k;
    vector<int> a(k + 1);
    for(int i = 1; i <= k; i++) {
        a[i] = (a[i - 1] * 10 + 7) % k;
        if(!a[i]) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 7104
#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define endl '\n'
using namespace std;
typedef long long ll;
int main()
{
	ll n,x,a[101];
	cin>>n>>x;
	for(int i = 0; i<n; i++)
		cin>>a[i];
	sort(a,a+n);
	//a.reverse();
	int d,cnt = 0;
	for(int i = 0; i<n; i++)
	{
		if(x>=a[i])cnt++,x = x-a[i];
		else break;
	}
	if(cnt == n && x)cnt--;
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

const string YES = "Yes";
const string NO = "No";

int main()
{
  long long D;
  scanf("%lld", &D);
  long long T;
  scanf("%lld", &T);
  long long S;
  scanf("%lld", &S);

  if (D <= T * S)
    cout << YES << endl;
  else
    cout << NO << endl;

  return 0;
}


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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, n, m) for (int i = n; i < m; i++)
#define ll long long int

using namespace std;

int main() {
  ll DIV = 998244353;
  ll n;
  ll a[300];
  ll dp[2][90001] = {};
  ll sum = 0;
  cin >> n;
  REP(i,n) {
    cin >> a[i];
    sum += a[i];
  }


  REP(i,n) {
    if(i == 0) {
      dp[i][a[i]] = 1;
      dp[i][0] = 2;
      continue;
    }
    REP(r,sum+1) {
      int t = i%2;
      dp[t][r] = (dp[(t+1)%2][r]*2)%DIV;
      if (r - a[i] >= 0) {
        dp[t][r] = (dp[t][r] + dp[(t+1)%2][r - a[i]])%DIV;
      }
    }
  }

  ll result = 1;
  REP(i,n) {
    result = (result*3)%DIV;
  }
  FOR(i, (sum+1)/2, sum+1) {
    // *3はRのところを誰と交換するかの自由度
    result = (result - dp[(n+1)%2][i]*3 + DIV)%DIV;
  }

  if (sum%2 == 0) {
    ll dp2[2][90001] = {};
    REP(i, n) {
      if (i == 0) {
        dp2[i][a[i]] = 1;
        dp2[i][0] = 1; // rに入らないやつはbに入ると決め撃つ
        continue;
      }
      REP(r, sum + 1) {
        int t = i % 2;
        dp2[t][r] = dp2[(t + 1) % 2][r] % DIV;
        if (r - a[i] >= 0) {
          dp2[t][r] = (dp2[t][r] + dp2[(t + 1) % 2][r - a[i]]) % DIV;
        }
      }
    }
    result = (result + dp2[(n + 1) % 2][(sum + 1) / 2] * 3) % DIV;
  }
  cout << result << endl;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define REP(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
int gcd(int x,int y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
int n,ans;
string s,t;
string pr[200],su[200];
signed main(){
    cin>>n;
    cin>>s>>t;
    ans=2*n;
    REP(i,1,n+1){
        pr[i-1]=s.substr(n-i);
        su[i-1]=t.substr(0,i);
        if(pr[i-1]==su[i-1])ans=(2*n)-i;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll M = 1000000007;
ll A[10005];
ll inv(ll K) {
  ll A = M - 2;
  ll ret = 1;
  ll D = K;
  while (A > 0) {
    if (A % 2 == 1) {
      ret = (ret * D) % M;
    }
    D = (D * D) % M;
    A /= 2;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  map<ll,int> m, p;
  for (int i=0; i<N; i++) {
    cin >> A[i];
    ll d = A[i];
    p.clear();
    for (ll j=2; j*j <= d; j++) {
      while (d % j == 0) {
        p[j]++;
        d /= j;
      }
    }
    p[d]++;
    for (auto& it : p) {
      m[it.first] = max(m[it.first], it.second);
    }
  }
  ll L = 1;
  for (auto& it : m) {
    for (int j=0; j < it.second; j++) {
      L = (L * it.first) % M;
    }
  }
  ll ret = 0;
  for (int i=0; i<N; i++) {
    ll d = (L * inv(A[i])) % M;
    ret = (ret + d) % M;
  }
  cout << ret << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>

#define ll long long int

using namespace std;

const int INF = (1<<30) - 1;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int H;
    while (cin>>H, H) {
        vector<vector<int>> field(H, vector<int>(5));
        for(int i=0; i<H; i++)
            for(int j=0; j<5; j++)
                cin >> field[i][j];
        
        int ans = 0;
        bool updated = true;
        while (updated) {
            updated = false;
            for (int i=0; i<H; i++) {
                int c = 1;
                int a = 0, b = 0;
                for(int j=1; j<5; j++){
                    if(field[i][j] != 0 && field[i][j-1] == field[i][j])
                        c++;
                    else
                        c = 1;
                    if(c >= 3){
                        b = j + 1;
                        a = b- c;
                        updated = true;
                    }
                }
                for(int j=a; j<b; j++){
                    ans += field[i][j];
                    field[i][j] = 0;
                }
            }
            
            for(int i=0; i<5; i++){
                int index = H-1;
                for(int j=H-1; 0<=j; j--){
                    while(index >= 0 && field[index][i] == 0)
                        index--;
                    
                    field[j][i] = (index < 0 ? 0 : field[index--][i]);
                }
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1216
/*input
6 5
1 2
3 2
4 2
1 6
5 6
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 2020
#define INF 0x3f3f3f3f


int n , m;
vector<int> v[MAX];
int DFS(int now , int fa , int deep , int need){
    int cnt = deep <= need;
    for(auto to : v[now]) if(to != fa) cnt += DFS(to , now , deep + 1 , need);
    return cnt;
}
int32_t main(){
    IOS;
    cin >> n >> m;
    REP(i , 1 , n + 0){
        int a , b; cin >> a >> b;
        v[a].pb(b) , v[b].pb(a);
    }
    int ans = 0;
    REP(i , 1 , n + 1){
        int v1 = m / 2 , v2 = m - v1 , base = 1;
        for(auto to : v[i]) base += DFS(to , i , 1 , v1);
        for(auto to : v[i]) ans = max(ans , base - DFS(to , i , 1 , v1) + DFS(to , i , 1 , v2));
    }
    cout << n - ans << endl;
    return 0;
}

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

int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int main(){
  int N;
  int x[205],y[205];
  while(1){
    cin>>N;
    if(N==0)break;
    int maxx,minix,maxy,miniy;
    maxx=maxy=minix=miniy=0;
    x[0]=y[0]=0;
    for(int i=1;i<N;i++){
      int n,d;
      cin>>n>>d;
      x[i]=x[n]+dx[d];
      y[i]=y[n]+dy[d];
      maxx=max(maxx,x[i]);
      maxy=max(maxy,y[i]);
      minix=min(minix,x[i]);
      miniy=min(miniy,y[i]);
    }
    cout<<maxx-minix+1<<" "<<maxy-miniy+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 2984
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,t;
long long ans;
char s[N];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='W'){
			ans+=t;
		}else{
			t++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
/*
LANG:C++
PROB:

*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
// #define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)


using namespace __gnu_pbds;
using namespace std;


typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
typedef unsigned long long ui64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int mod=1000000007;
  i64 poww(i64 a, i64 b)
  {
    a%=mod;
    i64 res=1;
    while(b)
      {
if(b&1)res=res*a%mod;

      a=a*a%mod;
      b/=2;

      }
      return res;
  }
  i64 inv(i64 a)
  {
    return poww(a,mod-2);
  }
  void solve()
  {

int n;
cin>>n;
i64 ans=poww(10,n);
ans-=poww(9,n);
ans-=poww(9,n);
ans+=poww(8,n);
ans%=mod;
if(ans<0)ans+=mod;

cout<<ans;
  }
  
  int main()
  {
ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
    #endif
int t=1;
while(t--)
{
  solve();
}

    return 0;
  }


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

int main(){
	int N;
	cin >> N;
	vector<int> A(N);
	for(auto &i:A)cin >> i;
	int ans=1;
	multiset<int> m;
	m.insert(A[0]);
	
	for(int i=1;i<N;i++){
		
		auto it=m.lower_bound(A[i]);
		if(it==m.begin()){
			ans++;
			m.insert(A[i]);
		}
		else{
			it--;
			m.erase(it);
			m.insert(A[i]);
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define mp make_pair
#define X first
#define Y second
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2010;
const int INF = 1e9 + 7;

int n, low[N], high[N], cnt[N];
bool hasPices[N];
vector <int> adj[N];

void dfs(int u, int p){
    cnt[u] = hasPices[u];
    high[u] = 0;
    int maxLow = 0;
    bool isLeaf = 1;
    for(int v : adj[u])
        if (v != p){
            dfs(v, u);
            isLeaf = 0;
            cnt[u] += cnt[v];
            high[u] += high[v] + cnt[v];
            maxLow = max(maxLow, low[v] + cnt[v]);
        }
    if (isLeaf){
        low[u] = 0;
    } else {
        int x = maxLow;
        int sum = 0;
        for(int v : adj[u])
            if (v != p)
                sum += min(high[v] + cnt[v], x - abs(high[v] + cnt[v] - x) % 2);
        if (x * 2 > sum)
            low[u] = x * 2 - sum;
        else
            low[u] = sum % 2;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    string s;
    cin >> s;
    FOR(i, 1, n)
        hasPices[i] = (s[i - 1] == '1');
    FOR(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = INF;
    FOR(i, 1, n){
        dfs(i, i);
        if (low[i] == 0)
            ans = min(ans, high[i] / 2);
    }
    cout << (ans == INF? -1 : ans);

    return 0;
}


Measured memory_bytes: 640
def divide_two_count(n):
    count = 0
    while n%2 == 0:
        n /= 2
        count += 1
    return count


n = int(input())
list = []

for i in range(1, n+1):
    a = divide_two_count(i)
    list.append(a)

print(list.index(max(list))+1)

Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int main()
{
	int n,m,a,b,c;
	int cost[100][100],s1[100][100],s2[100][100];
	int i,j,k;
	while(scanf("%d%d",&n,&m),n)
	{
		memset(cost,INF,sizeof(cost));
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			--a; --b;
			cost[a][b]=cost[b][a]=c;
			s1[a][b]=s1[b][a]=true;
		}
		for(i=0;i<n;++i)
			cost[i][i]=0;
		for(k=0;k<n;++k)
			for(i=0;i<n;++i)
				for(j=0;j<n;++j)
				{
					cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
					s2[i][j] = (s2[i][j] || s1[i][k]&&s1[k][j]);
				}
		int res=cost[0][n-1];
		for(i=0;i<n;++i)
			for(j=0;j<n;++j)
				if(s2[i][j])
					res = min(res,cost[0][i]+cost[j][n-1]);
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+5,mod = 998244353;
ll fct[N],inv[N],invfct[N];
void init(){
    fct[0]=fct[1]=1;
	inv[1]=1;
	invfct[0]=invfct[1]=1;
	for(ll i=2;i<N;i++){
		fct[i]=i*fct[i-1]%mod;
		inv[i]=ll(mod-inv[mod%i])*(mod/i)%mod;
		invfct[i]=ll(inv[i])*invfct[i-1]%mod;
	}
}
inline ll ncr(ll n,ll r){
    if(n-r<0 || n<0 || r<0)return 0;
    ll ans = fct[n]*invfct[n-r];
    ans%=mod;
    ans = ans*invfct[r];
    ans%=mod;
    return ans;
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    init();
    ll n,ans=0,A,B,K;cin>>n>>A>>B>>K;
    for(ll a=0;a<=n&&K-A*a>=0;a++){
        ll val = K - A*a;
        if(val%B || val/B>n)continue;
        ans = ans + (ncr(n,a)*ncr(n,val/B))%mod;
        ans%=mod;
    }
    cout<<ans;
}

Measured memory_bytes: 7296
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	n := nextInt()
	a := make([]int, n)
	for i := 0; i<n; i++ {
		a[i] = nextInt()
	}

	idx := 0
	count := 0
	for {
		if idx + count > len(a) - 1 {
			break
		}

		if a[idx + count] != idx + 1 {
			count++
		} else {
			idx++
		}
	}

	if len(a) == 0 || count > n-1 {
		fmt.Printf("%d", -1)
	} else {
		fmt.Printf("%d", count)
	}
}


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

int main() {
    ll h, n;
    cin >> h >> n;
    vector<pair<ll, ll>> ab(n);
    rep(i, n) cin >> ab[i].first >> ab[i].second;

    vector<ll> dp(1e8, 0);
    for (ll i = 0; i <= 1e8; i++) {
        rep(j, n) {
            if (i - ab[j].second >= 0) {
                dp[i] = max(dp[i], dp[i - ab[j].second] + ab[j].first);
            }
        }
        if (dp[i] >= h) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 781568
#include <stdio.h>

int main(){

  int a[1010];
  int n,i,j,k,key;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<n-1;i++){
    printf("%d ",a[i]);
  }
  printf("%d\n",a[n-1]);

  for(i=1;i<=n-1;i++){
    key=a[i];
    j=i-1;
    while(j>=0 && a[j]>key){
      a[j+1]=a[j];
      j--;
      a[j+1]=key;
    }
    for(k=0;k<n-1;k++){
      printf("%d ",a[k]);
    }
    printf("%d\n",a[n-1]);
  }
  return 0;
}


Measured memory_bytes: 600
S = input()
ans = True
W = ['dream', 'erase', 'eraser', 'dreamer']
while S:
  if S[:5] in W[:2]:
    match = False
    mw = ''
    for w in W:
      if S == w:
        match = True
        mw = w
    for w1 in W:
      for w2 in W:
        if S[:len(w1) + len(w2)] == w1 + w2:
          match = True
          mw = w1
    if match:
      S = S[len(mw):]
    else:
      ans = False
      break
  else:
    ans = False
    break
print('YES' if ans else 'NO')

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin >> n;
  string t = "MARCH";
  int cnt[5] = {};
  for(int i = 0; i < n ; i++ ){
    string s;
    cin >> s;
    for(int j = 0 ; j < 5 ; j++ )if(s[0] == t[j])cnt[j]++;
  }
  int ans=0;
  for(int i=0;i<5;i++)
    for(int j=i+1;j<5;j++)
      for(int k=j+1;k<5;k++)
	ans+=cnt[i]*cnt[j]*cnt[k];
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int n; cin >> n;
    vector<int> w(n); for(int i = 0;i < n; i++) cin >> w[i];
    int ans = 1e9;
    for(int i = 1; i < n; i++){
        int lsum = 0, rsum = 0;
        for(int j = 0; j < n; j++){
            if(j < i) lsum += w[j];
            else rsum += w[j];
        }
        ans = min(ans, abs(rsum-lsum));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584