akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

#ifdef LOCAL
#include<prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

ostream& operator << (ostream& os, const mint a) {
    os << a.x;

    return os;
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    string L;
    cin >> L;

    int M = L.size();
    mint dp[M+1][2];
    dp[0][0] = 0;
    dp[0][1] = 1;

    REP(i, M) {
        int s = L[i] - '0';
        if (s) {
            // smaller
            dp[i+1][0] = dp[i][0] * 3 + dp[i][1];

            // exact
            dp[i+1][1] = dp[i][1] * 2;
        } else {
            // smaller
            dp[i+1][0] = dp[i][0] * 3;

            // exact
            dp[i+1][1] = dp[i][1];

        }
    }

    cout << dp[M][0] + dp[M][1] << endl;

    
}


Measured memory_bytes: 2000
/// Thank you tanakh!!!
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn next(v: (i64, i64)) -> (i64, i64) {
    let (x, y) = v;
    (-y, x)
}

fn main() {
    input!(k: usize);
    let a = k / 2;
    let b = (k + 1) / 2;
    println!("{}", a * b);
}


Measured memory_bytes: 4352
import java.util.HashSet;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		HashSet hs = new HashSet();
		hs.add(scanner.nextInt());
		hs.add(scanner.nextInt());
		hs.add(scanner.nextInt());

		System.out.println(hs.size());

		scanner.close();
	}
}

Measured memory_bytes: 23380
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define all(n)      (n).begin(), (n).end()
#define ll long long

void solve() {
	int n; cin >> n;
	set<string> _s;
	while (n--) {
		string s; cin >> s;
		_s.insert(s);
	}
	cout << _s.size() << endl;


}


int main () {

	ios::sync_with_stdio(0);
	cin.tie(0);
	//Write from here.
	solve();

	return 0;
}

Measured memory_bytes: 19152
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a + 3);
  cout << a[0] << " " << a[1] << " " << a[2] << endl;
  return 0;
}


Measured memory_bytes: 3160
#define  _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#pragma comment (linker, "/STACK:526000000")

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(10);
}

#define int ll
void solve() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0) return;
		vector<vector<int>> inputs;
		REP(i, n) {
			int a;
			cin >> a;
			vector<int> geko;
			REP(i, a) {
				int b;
				cin >> b;
				geko.push_back(b);
			}
			inputs.push_back(geko);
		}
		int k;
		cin >> k;
		vector<int> tmps;
		REP(i, k) {
			int a;
			cin >> a;
			tmps.push_back(a);
		}
		vector<int> ans;
		REP(i, n) {
			int ok = 1;
			for (int q = 0; q < k; ++q) {
				int geko = 0;
				REP(j, inputs[i].size()) {
					if (tmps[q] == inputs[i][j]) {
						geko = 1;
					}
				}
				if (geko == 0) {
					ok = 0;
				}
			}
			if (ok == 1) {
				ans.push_back(i + 1);
			}
		}
		if (ans.size() != 1) {
			cout << -1 << endl;
			continue;
		}
		cout << ans[0] << endl;
	}
}
#undef int

int main() {
	init();
	solve();
}


Measured memory_bytes: 3300
import java.util.*;


public class Main {
	//template
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
//		new Main().aoj0532();
		new Main().aoj0535();
	}

	int min(int[] arr){
		int ret = arr[0];
		for(int i = 0; i < arr.length; i++){
			if(ret>arr[i])ret = arr[i];
		}
		return ret;
	}
	
	int max(int[] arr){
		int ret = arr[0];
		for(int i = 0; i < arr.length; i++){
			if(ret<arr[i])ret = arr[i];
		}	
		return ret;
	}
	
	int sum(int[] array){
		int sum = 0;
		for(int v : array){
			sum += v;
		}
		return sum;
	}
	
	
	//--------------------------
	
	void aoj0532(){
		for(int i = 0; i < 3; i++){
			int in = sc.nextInt()*60*60+sc.nextInt()*60+sc.nextInt();
			int out = sc.nextInt()*60*60+sc.nextInt()*60+sc.nextInt();
			int diff = out - in;
			
			int h = diff/(60*60);
			diff -= h*60*60;
			int m = diff/60;
			diff -= m*60;
			int s = diff;
			
			System.out.println(h+" "+m+" "+s);
		}
	}
	
	void aoj0533(){
		int[] wp = new int[10];
		int[] kp = new int[10];
		for(int i=0; i<10; i++){ wp[i] = sc.nextInt(); }
		for(int i=0; i<10; i++){ kp[i] = sc.nextInt(); }
		
		Arrays.sort(wp); Arrays.sort(kp);
		System.out.println((wp[9]+wp[8]+wp[7]) + " " + (kp[9]+kp[8]+kp[7]));
	}
	
	
	int aoj0535_dfs(int[][] f, int y, int x, int n, int m){
		int[] dxs = {1, 0, -1, 0};
		int[] dys = {0, 1, 0, -1};
		
		int mx = -1;
		for(int i=0; i<4; i++){
			int dx = x+dxs[i], dy = y+dys[i];
			if (0 <= dx && dx < m && 0 <= dy && dy < n){
				if (f[dy][dx] == 1){
					f[dy][dx] = 0;
					int v = aoj0535_dfs(f, dy, dx, n, m);
					if (v > mx) mx = v;
					f[dy][dx] = 1;
				}
			}
		}
		
		return mx + 1;
	}
	void aoj0535(){
		while(true){
			int m = sc.nextInt();
			int n = sc.nextInt();
			int[][] field = new int[n][m];
			
			if (m==0 && n==0) break;
			
			//in
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
//					System.out.println(i + " " + j);
					field[i][j] = sc.nextInt();
				}
			}
			
			int mx = 0;
			for(int i=0; i<n; i++) { //i=y
				for(int j=0; j<m; j++) { //j=x
					if(field[i][j] == 1){
						int v = aoj0535_dfs(field, i, j, n, m); //その座標からたどれる区画数
						if (v > mx) mx = v;
					}
				}
			}
			System.out.println(mx);
		}
	}
	
}

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

const int N = 105;
const int M = 3;
int w[N],v[N];

ll dp[N][N*M][N];

ll solveDp(int ind,int weight,int k,int n,int W) {
    ll R = (ll)k*w[1] + weight;
    if(R>W) {
        return -1e18;
    }
    if(ind>n) {
        return 0;
    }
    ll &ret = dp[ind][weight][k];
    if(ret!=-1) {
        return ret;
    }
    ret = v[ind] + solveDp(ind+1,weight + w[ind]-w[1],k+1,n,W);
    ret = max(ret, solveDp(ind+1,weight,k,n,W));
    return ret;
}

void solve() {
    int n,W;
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&w[i],&v[i]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld\n", solveDp(1,0,0,n,W));
}

int main() {
   //freopen("input.txt","r",stdin);
   solve();
}

Measured memory_bytes: 27392
# -*- coding: utf-8 -*-

N = int(input())
a = []
for i in range(2):
    a.append(list(map(int, input().split())))
result = 0
for i in range(N):
    tmp = sum(a[0][0:i+1]) + sum(a[1][i:N])
    if tmp > result:
        result = tmp
print(result)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <functional>
#include <iomanip>
#include <climits> // LLONG_MAX, LLONG_MIN, INT_MIN, INT_MAX
#include <assert.h>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define ll long long
#define int ll
#define INF LLONG_MAX/10

using namespace std;
using Pi = pair<int, int>;
using Graph = vector<vector<int> >;
using WeightGraph = vector<vector<Pi> >;

signed main() {
  int L, R; cin >> L >> R;
  if (R - L >= 2018) {
    cout << 0 << endl;
    return 0;
  } 
  int x = L % 2019;
  int y = R % 2019;

  int ans = INF;

  for (int i = x; i < y; i = (i + 1) % 2019) {
    for (int j = (i + 1) % 2019; j <= y; j = (j + 1) % 2019) {
      if (i == 0 || j == 0) {
        cout << 0 << endl;
        return 0;
      }
      ans = min(ans, (i * j) % 2019);
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

const long long INF = 1e10;

const int MAX_D = 1000005;

vector<long long> dp(vector<pair<long long, long long>>& a){
	vector<long long> res(MAX_D, INF);
	res[0] = 0;
	rep(i,MAX_D){
		rep(j,a.size()){
			int idx = min<int>(i + a[j].second, MAX_D - 1);
			res[idx] = min(res[idx], res[i] + a[j].first);
		}
	}

	return res;
}

int main(){
	int n;
	while(cin >> n,n){
		vector<long long> h(n);
		rep(i,n){
			cin >> h[i];
		}

		int m;
		cin >> m;
		vector<pair<long long,long long>> s, a; // first MP, second damage
		rep(i,m){
			long long MP, damage;
			string target;
			cin >> target >> MP >> target >> damage;
			(target  == "Single" ? s : a).emplace_back(MP, damage);
		}

		vector<long long> al = dp(a);
		vector<long long> si = dp(s);

		for (int i = MAX_D - 1; i > 0; i--) {
			si[i - 1] = min(si[i - 1], si[i]);
		}

		long long ans = al[*max_element(all(h))];
		rep(i,MAX_D){
			if(al[i] == INF) continue;
			long long sum = al[i];
			rep(j,n){
				sum += si[max(h[j] - i, 0LL)];
			}
			ans = min(ans, sum);
		}
		cout << ans << endl;
	}
}



Measured memory_bytes: 18456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0;i<(int)(n);i++)
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
const int inf=1e9+1;
template <class T>
void print(T x){cout << x << '\n';}

void solve(long long N, std::vector<long long> d){
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end()); // v = { 1, 2, 3 }
    print(d.size());
}

int main(){
  long long N;
  scanf("%lld",&N);
  std::vector<long long> d(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&d[i]);
  }
  solve(N, std::move(d));
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(){
	int l; scanf("%d", &l);
	int n = 1, r = 0;
	while(2 * n <= l) { n *= 2; r++; }
	int m = 2 * r + __builtin_popcount(l - n);
	printf("%d %d\n", r + 1, m);
	for(int i = 0; i < r; i++){
		printf("%d %d %d\n", i + 1, i + 2, 0);
		printf("%d %d %d\n", i + 1, i + 2, 1 << i);
	}
	for(int i = r - 1; l > n; i--) if(l - (1 << i) >= n){
		l -= 1 << i;
		printf("%d %d %d\n", i + 1, r + 1, l);
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define FOR(i,n) for(size_t i=0;i<(n);i++)
#define REP(n) FOR(i,n)
#define cinv(v,n) for(size_t i=0;i<(n);i++){cin>>(v)[i];}
#define nvec(type,v,n) vector<type> v(n);cinv(v,n)
#define npairs(type1,type2,v,n) vector<pair<type1,type2>> v(n);for(size_t i=0;i<(n);i++){cin>>v[i].first>>v[i].second;}
#define npairs(type1,type2,v,n) vector<pair<type1,type2>> v(n);for(size_t i=0;i<(n);i++){cin>>v[i].first>>v[i].second;}
#define ntuples(type1,type2,type3,v,n) vector<tuple<type1,type2,type3>> v(n);for(size_t i=0;i<(n);i++){cin>>get<0>(v[i])>>get<1>(v[i])>>get<2>(v[i]);}

#define min_index(v) size_t(min_element(all(v))-(v).begin())
#define max_index(v) size_t(max_element(all(v))-(v).begin())
#define min_e(v) *min_element(all(v))
#define max_e(v) *max_element(all(v))

#define count_le(v,a) size_t(upper_bound(all(v),a)-(v).begin())
#define count_lt(v,a) size_t(lower_bound(all(v),a)-(v).begin())
#define count_ge(v,a) size_t((v).end()-lower_bound(all(v),a))
#define count_gt(v,a) size_t((v).end()-upper_bound(all(v),a))

#define order(neq_sl) [](const auto s, const auto l){return neq_sl;}
#define make_lr(v,type,l,r) vector<type> l(n+1),r(n+1);FOR(i,n){l[i+1]=l[i]+v[i];r[i+1]=r[i]+v[n-1-i];}

#define acm accumulate
#define SUM(v) accumulate(all(v),0l)

int main() {
  int n;
  cin>>n;
  nvec(int,a,n);
  int k=1;
  for (size_t i = 0; i < n; i++) {
    if(a[i]==k)k++;
  }
  if(k==1){
      cout<<-1;
      return 0;
  }
  cout<<n-k+1;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int, input().split()))

b = [0] * ((n + 1) // 2)

if n % 2 == 0:
    for x in a:
        if x % 2 == 0:
            print(0)
            exit()
        b[x // 2] += 1
    for y in b:
        if y != 2:
            print(0)
            exit()
else:
    for x in a:
        if x % 2 != 0:
            print(0)
            exit()
        b[x // 2] += 1
    for y in b[1:]:
        if y != 2:
            print(0)
            exit()
        if b[0] != 1:
            print(0)
            exit()

print((2 ** (n//2)%(10**9+7)))


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

using ll = long long;
ll x1 = (ll)1e9;
ll y1 = 1;

int main() {
  ll S;
  cin >> S;
  // |x1y2 - y1x2| = S
  // x1 = 1e9, y1 = 1
  // 1e9 * y2 - x2 = S
  ll x2 = (x1 - S % x1) % x1;
  ll y2 = (S + x2) / x1;
  cout << 0 << " " << 0 << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
  return 0;
}

Measured memory_bytes: 256
if __name__ == "__main__":
	a, b, c, k = map(int, input().strip().split(' '))
	s, i = 0, 0
	if k <= a:
		s = k
	elif k > a:
		s = a
		k -= a
		if k > b:
			k -= b
			s -= k
	print(s)

Measured memory_bytes: 9176
#include <cstdio>

int n, a[30];
long long ans;

void dfs(int k, int p) {
	if(k >= n) {
		if(~p & 1) {
			++ans;
		}
		return;
	}
	for(int i = -1; i <= 1; ++i) {
		dfs(k + 1, p * (a[k] + i));
	}
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", a + i);
	}
	dfs(0, 1);
	printf("%lld\n", ans);
	return 0;
}


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


int main()
{
  int x;
  cin >> x;
  int max1 = 1;
  int ans = 0;
  for(int i = 2;i <= x;i++){
    ans = i*i;
    if(ans > x) break;
    while(ans <= x){
      max1 = max(max1,ans);
      ans = ans * i;
    }
  }
  cout << max1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Max 500000
#define NIL NULL

struct node{
  int key;
  struct node *right;
  struct node *left;
  struct node *p; 

};

typedef struct node *Node;
 
Node  root;


void insert(int  z){

  Node data;
  Node x;
  Node y;

  y = NIL;
  x = root;

  data = malloc(sizeof(struct node));
  data->key = z;
  data->right = NIL;
  data->left = NIL;
  data->p = NIL;

  while( x != NIL ){
    y = x;
    if( data->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  
  data->p = y;
  
  if( y == NIL)
    root = data;
  else if( data->key < y->key)
    y->left = data;
  else 
    y->right = data;
}

void print1(Node u){
  if( u == NIL)
    return;
  print1(u->left);
  printf(" %d",u->key);
  print1(u->right);
}

void print2(Node u){
  if( u == NIL)
    return;
  printf(" %d",u->key);
  print2(u->left);
  print2(u->right);
}

int main(){

  int i, m, num;
  char order[10];
  char order1[] = "insert";
  char order2[] = "print"; 

  scanf("%d",&m);

  for( i = 0 ; i < m ; i++){
    scanf("%s",order);

 
    if( (strcmp(order,order1)) == 0){
      scanf("%d",&num );
      insert(num);
    }
    if(( strcmp(order,order2)) == 0){
      print1(root);  
      printf("\n");
      print2(root);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 24048
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m;
const int MAXN=1e5+50;

int num[MAXN];
int a[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int num1=0;
    memset(num,0,sizeof(num));
    int mm=0;
    for(int i=0;i<n;i++)
    {
        num[a[i]]++;
        num[a[i]+1]++;
        if(a[i]==0) num1++;
        else
        num[a[i]-1]++;
       // mm=max(mm,a[i])
    }
    for(int i=0;i<MAXN;i++)
    {
        num1=max(num1,num[i]);
        //cout<<num1<<"  "<<num[i]<<endl;
    }
    cout<<num1<<endl;
    return 0;
}



Measured memory_bytes: 1024
#include <cstdio>
#include <utility>
using namespace std;

typedef pair<int,int> pii;

pii par[100001];
int rank[100001];

pii find(int x){
	if(par[x].first != x){
		pii p = find(par[x].first);
		par[x] = pii(p.first, par[x].second + p.second);
	}
	return par[x];
}

int main(){
	int m, n, a, b, w;
	char cmd;
	while(scanf("%d%d", &n, &m), m != 0){
		for(int i = 1; i <= n; ++i){
			par[i] = pii(i, 0);
			rank[i] = 0;
		}
		
		for(int i = 0; i < m; ++i){
			scanf(" %c", &cmd);
			if(cmd == '!'){
				scanf("%d%d%d", &a, &b, &w);
				pii pa = find(a), pb = find(b);
				if(pa.first != pb.first){
					if(rank[pa.first] < rank[pb.first]){
						par[pa.first] = pii(pb.first, pb.second - pa.second + w);
					}
					else{
						par[pb.first] = pii(pa.first, pa.second - pb.second - w);
						if(rank[pa.first] == rank[pb.first]){
							++rank[pa.first];
						}
					}
				}
			}
			else{
				scanf("%d%d", &a, &b);
				pii pa = find(a), pb = find(b);
				if(pa.first != pb.first){
					puts("UNKNOWN");
				}
				else{
					printf("%d\n", pa.second - pb.second);
				}
			}
		}
	}
}

Measured memory_bytes: 2212
import java.util.Scanner;

class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] P = new int[N];
		for (int i = 0; i < N; i++) {
			P[i] = sc.nextInt();
		}
		double max = 0;
		double tail;
		for (int i = 0; i < K; i++) {
			tail = 0.5 * (P[i] + 1);
			max += tail;
		}
		double prev = max;
		for (int i = K; i < N; i++) {
			prev -= 0.5 * (P[i - K] + 1);
			prev += 0.5 * (P[i] + 1);
			max = Math.max(prev, max);
		}
		System.out.println(max);
	}


}

class Main {
	public static void main(String... args) {
		Scanner in = new Scanner(System.in);

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

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

using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a>=1 && a<=9)&&(b>=1 && b<=9))
	{
		cout<<a*b<<endl;
	}
	else
		cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define max(a,b,c) max(a,max(b,c))
#define min(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF 1145141919

int fibo(int fib){
  int f0=1,f1=1,f2,i;
  if(fib==0){
    return f0;
  }
  else if(fib==1){
    return f1;
  }
  else{
    for(i=2;i<=fib;i++){
      f2=f1+f0;
      f0=f1;
      f1=f2;
      f0=f0%MOD;
      f1=f1%MOD;
      f2=f2%MOD;
    }
    return f2;
  }
}

using namespace std;

int main(void){
  int N,M,i,check=0;
  unsigned long long int ans=1;
  cin >> N >> M;
  int a[M];
  for(i=0;i<M;i++){
    cin >> a[i];
  }
  for(i=0;i<M-1;i++){
    if(a[i+1]-a[i]==1){
      cout << "0" << endl;
      check=1;
      break;
    }
  }
  if(check==0){
    int dis[100000]={};
    dis[0]=a[0]-1;
    for(i=1;i<M+1;i++){
      dis[i]=a[i]-a[i-1]-2;
    }
    dis[M]=N-a[M-1]-1;
    for(i=0;i<M+1;i++){
      ans=(ans*fibo(dis[i]))%MOD;
    }
    if(M==0){
      ans=fibo(N);
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 768
#include <iostream>

using namespace std;

int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int i = 0;
	while (a > 0 && c > 0) {
		if (i % 2 == 0) {
			c -= b;
		} else {
			a -= d;
		}
		i++;
	}

	if (a > 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979

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; }




ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int ans = 0;
int N, M, Q;

template<typename T>
void showall(vector<T> v){
  rep(i, 0, v.size()){
    cout << v[i] << " ";
  }
  cout << endl;
}


void dfs(vector<int> A, int n, vector<int> a, vector<int> b, vector<int> c, vector<int> d){
  vector<int> B = A;
  B.push_back(n);
  if(B.size() == N){
    int score = 0;
    rep(i, 0, Q){
      if(B[b[i]-1] - B[a[i]-1] == c[i]){
        score += d[i];
      }
    }

    if(score > ans){
      ans = score;
    }
  }else{
    for(int i = n; i <= M; i++){
      dfs(B, i, a, b, c, d);
    }
  }
}


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

  vector<int> a(Q), b(Q), c(Q), d(Q), A;
  rep(i, 0, Q){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }

  rep(i, 1, M+1){
    dfs(A, i, a, b, c, d);
  }
  
  cout << ans << endl;
  
}

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

using namespace std;

#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

int main() {
    ll k,a,b;
    while(~scanf("%lld%lld%lld",&k,&a,&b)) {
        if(b-a>2) {
            ll ans=0;
            if((a-1)<=k) {
                k-=(a-1);
                if(k%2) ans++;
                ans+=a+(k/2)*(b-a);
            }
            else {
                ans=k+1;
            }
            printf("%lld\n",ans);
        }
        else {
            ll ans=k+1;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Measured memory_bytes: 256
loop do
    a, op, b = gets.chomp.split
    if op == "?"
        break
    elsif op == "+"
        x = a.to_i + b.to_i
        puts "#{x}"
    elsif op == "-"
        x =  a.to_i - b.to_i
        puts "#{x}"
    elsif op == "*"
        x = a.to_i * b.to_i
        puts "#{x}"
    elsif op == "/"
        x = a.to_i / b.to_i
        puts "#{x}" 
    end
end

Measured memory_bytes: 8736
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include <ctime>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
const int maxn = 1e7+5;

ll divisor_num[maxn];
void init(ll n){
    for(int i = 1; i <= n; i++)
    {
        divisor_num[i]++;
       for(int j = i * 2; j <= n; j += i)
            divisor_num[j]++;
    }
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("text1.in","r",stdin);
	//freopen("text1.out","w",stdout);
	ll n;
	cin>>n;
//	clock_t startTime,endTime;
//    startTime = clock();//计时开始
	init(n);
	ll ans=0;
	for(ll i=1;i<=n;i++) {
		ans+=i*divisor_num[i];
	}
	cout<<ans<<endl;
//	endTime = clock();//计时结束
//    cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}


Measured memory_bytes: 81776
#include<iostream>
using namespace std;
int main(){
	int a,b;
	while(true){
	cin>>a>>b;
	if(a==0 && b==0)break;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(i==0 || i==a-1 || j==0 || j==b-1){
				cout<<"#";
			}
			else{
				cout<<".";
			}
		}
		cout<<endl;
	}
	cout<<endl;
	}
}

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

using namespace std;

int main()
{
    string a;
    int flag=0;
    cin>>a;
    for(int i=0;i<a.size()-1;i++)
    {
        if(a[i]==a[i+1])
            {flag=1;break;}
    }
    if(flag==1)
        cout<<"Bad";
    else
        cout<<"Good";
    return 0;
}


Measured memory_bytes: 256
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

func getString() string {
	sc.Scan()
	return sc.Text()
}

type node struct {
	to []int
}

var c []int
var dp [2][100001]int

/*
func dfs(col, next, prev int, n []node) int {
	if dp[col][next] != -1 {
		return dp[col][next]
	}

	r0 := 1
	r1 := 1
	for _, v := range n[next].to {
		if c[v] != 0 {
			r1 = 0
			break
		}
	}
	for _, v := range n[next].to {
		if v == prev {
			continue
		}
		c[next] = 1
		r1 *= dfs(1, v, next, n)
		c[next] = 0
		r0 *= dfs(0, v, next, n)
	}

	dp[col][next] = r0 + r1
	out(col, next, prev, r0+r1)

	return r0 + r1
}
*/

const mod = 1000000007

func dfs(col, next, prev int, n []node) int {
	if dp[col][next] != -1 {
		return dp[col][next]
	}

	r0 := 1
	r1 := 1
	for _, v := range n[next].to {
		if c[v] != 0 {
			r1 = 0
			break
		}
	}

	for _, v := range n[next].to {
		if v == prev {
			continue
		}
		c[next] = 1
		r1 *= dfs(1, v, next, n)
		r1 %= mod
		c[next] = 0
		r0 *= dfs(0, v, next, n)
		r0 %= mod
	}

	r := (r0 + r1) % mod
	dp[col][next] = r
	//	out(col, next, prev, r0+r1)

	return r
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	n := make([]node, N)
	c = make([]int, N)

	for i := 0; i < 100001; i++ {
		dp[0][i] = -1
		dp[1][i] = -1
	}
	for i := 0; i < N-1; i++ {
		from, to := getInt()-1, getInt()-1
		n[from].to = append(n[from].to, to)
		n[to].to = append(n[to].to, from)
	}
	out(dfs(0, 0, -1, n))
}


Measured memory_bytes: 38656
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arrA = new int[n];
		int[] arrB = new int[n];
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			arrA[x - 1] = i + 1;
			arrB[x - 1] = i + 1;
		}
		for (int i = 1; i < n; i++) {
			arrA[i] += arrA[i - 1];
			arrB[n - i - 1] += arrB[n - i];
		}
		StringBuilder sbA = new StringBuilder();
		StringBuilder sbB = new StringBuilder();
		for (int i = 0; i < n; i++) {
			if (i != 0) {
				sbA.append(" ");
				sbB.append(" ");
			}
			sbA.append(arrA[i]);
			sbB.append(arrB[i]);
		}
		System.out.println(sbA);
		System.out.println(sbB);
	}
}


Measured memory_bytes: 42952
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>

using namespace std;

int gcd(int n, int m) {
    if (n == 0) return m;
    return gcd(m % n, n);
}

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind c(n);

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        c.unite(x-1, y-1);
    }

    set<int> s;
    for (int i = 0; i < n; ++i) {
        s.insert(c.root(i));
    }

    cout << s.size() << endl;
}


Measured memory_bytes: 5376
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<endl
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
//#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 998244353; const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 2e18;


void solve() {
	string S, T; cin >> S >> T;
	cout << T + S << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q;cin>>q;
	//while(q--)
	solve();
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
	#define dbg(x) cout << #x << " : " << x << endl;
#else 
	#define dbg(x)
#endif

#define int long long
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 200010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   	
   	int n, m, k;
   	cin >> n >> m >> k;
   	vi a(n);
   	vi b(m);
	fi(0, n) cin >> a[i];
	fi(0, m) cin >> b[i];
	int sumb = 0;
	int it = 0;
	while (it < m && sumb + b[it] <= k) {
		sumb += b[it];
		++it;
	}
	int res = it;
	--it;
	fi(0, n) {
		k -= a[i];
		if (k < 0)
			break;
		while (it >= 0 && sumb > k) {
			sumb -= b[it--];
		}
		maxe(res, i + 1 + it + 1);
	}
	cout << res << '\n';
}

Measured memory_bytes: 6400
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
	char name[100];
	int t;
}P;

P Q[LEN];
int head,tail,n;

void enqueue(P x){
	Q[tail]=x;
	tail=(tail+1)%LEN;
}

P dequeue(){
	P x=Q[head];
	head=(head+1)%LEN;
	return x;
}

int min(int a,int b){return a<b ? a:b;}//min

int main(){
	int elaps=0,c;
	int i,q;
	P u;
	scanf("%d %d",&n,&q);
	
	for(i=1;i<=n;i++){
		scanf("%s",Q[i].name);
		scanf("%d",&Q[i].t);
	}
	head=1;
	tail=n+1;
	
	//シミュレーション
	while(head!=tail){
		u=dequeue();
		c=min(q,u.t);
		u.t-=c;
		elaps+=c;
		if(u.t>0)enqueue(u);
		else printf("%s %d\n",u.name,elaps);
	}

return 0;
}

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

int main() {
    int n; ll k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    vector<int> s;
    vector<int> ord(n+1, -1);
    int c = 1, l = 0;
    {
        int v = 1;
        while (ord[v] == -1) {
            ord[v] = s.size();
            s.push_back(v);
            v = a[v-1];
        }
        c = s.size() - ord[v];
        l = ord[v];
    }

    if (k < l) cout << s[k] << endl;
    else { 
        k -= l;
        k %= c;
        cout << s[l+k] << endl;
    }
    return 0;
}

Measured memory_bytes: 5892
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define N 300005
#define vi vector<int>
#define all(v) v.begin(),v.end()

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n;
   cin>>n;
   map<int,int>m;
   int a[n];
   for(int i=1;i<n;i++)
   {
       cin>>a[i];
       m[a[i]]++;
   }
   for(int i=1;i<=n;i++)
   {
       cout<<m[i]<<endl;
   }
}


Measured memory_bytes: 17652
#include<bits/stdc++.h>
using namespace std;
using ll=long long;



int main(){
  int n;
  cin >> n;
  vector<vector<ll>> a(n,vector<ll>(n));
  vector<vector<ll>> w(n,vector<ll>(n));
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      cin >> a[i][j];
      w[i][j]=a[i][j];
    }
  }
  for(int k=0;k<n;++k){
    for(int i=0;i<n;++i){
      for(int j=0;j<n;++j){
        if(i==k || k==j || i==j || w[i][k]==-1 || w[k][j]==-1)continue;
        if(w[i][k]+w[k][j]==w[i][j]) w[i][j]=-1;
        else if(w[i][k]+w[k][j]<w[i][j]){
          cout << "-1" << endl;
          return 0;
        }
      }
    }
  }
  ll ans=0;
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      if(w[i][j]==-1)continue;
      ans+=w[i][j];
    }
  }
  ans/=2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5024
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] b = new int[n];
        Arrays.fill(b, -1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int l = -1, r = n-1;
            while(1 < r-l){
                int m = (l + r) / 2;
                if(b[m] < a[i]) r = m;
                else l = m;
            }
             b[r] = a[i];
            if(max < r) max = r;
        }
        System.out.println(max+1);
        sc.close();

    }

}


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

using namespace std;

int main(void)
{
	int n, k;
	cin >> n >> k;
	int p[n];
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	sort(p, p+n);
	int price = 0;
	for (int i = 0; i < k; i++) {
		price += p[i];
	}
	cout << price << endl;
	return 0;
}

Measured memory_bytes: 3632
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int n;
	int[] pow;
	String[] names;
	HashSet<String>[] sets;

	@SuppressWarnings("unchecked")
	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			names=new String[n];
			pow=new int[n];
			sets=new HashSet[n];
			for(int j=0; j<n; j++){
				names[j]=sc.next();
				pow[j]=sc.nextInt();
				sets[j]=new HashSet<String>();
				int m=sc.nextInt();
				for(int i=0; i<m; i++){
					sets[j].add(sc.next());
				}
			}
			solve();
		}
	}

	long[] g;
	int ans;

	void solve(){
		HashMap<String, Integer> map=new HashMap<String, Integer>();
		for(int i=0; i<n; i++){
			map.put(names[i], i);
		}
		g=new long[n];
		for(int i=0; i<n; i++){
			for(String s : sets[i]){
				int j=map.get(s);
				g[i]|=1L<<j;
			}
		}

		ans=0;
		mis(1, 1, pow[0]);
		println(ans+"");
	}

	void mis(int k, long choosed, int sum){
		if(k==n){
			// String c=Long.toBinaryString(choosed);
			// for(; c.length()<n; c="0"+c);
			// debug(c, sum);
			ans=max(ans, sum);
			return;
		}

		// debug(k, Long.toBinaryString(covered), Long.toBinaryString(choosed));

		if((choosed&(g[k]|(1L<<k)))!=0){
			mis(k+1, choosed, sum);
			return;
		}

		long rem=0;
		for(int i=k+1; i<n; i++){
			if((choosed&g[i])==0)
				rem|=g[i];
		}

		if((rem>>k&1)==0){
			mis(k+1, choosed|(1L<<k), sum+pow[k]);
			return;
		}
		mis(k+1, choosed, sum);
		mis(k+1, choosed|(1L<<k), sum+pow[k]);
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
#define ls l,mid,now<<1
#define rs mid+1,r,now<<1|1
const int N=310000,M=110000;
int n,m,cnt;
struct node
{
	int l,r;
	friend bool operator < (const node &r1,const node &r2)
	{return r1.r<r2.r;}
}a[N];
vector<int>vec[M];
int b[M*20],pos[M],ed[M],beg[M],nv[M*20];
int val[M*20],bj[M*80],ans[M];
void pushdown(int now)
{
	bj[now<<1]+=bj[now];
	bj[now<<1|1]+=bj[now];
	bj[now]=0;
}
void modify(int l,int r,int now,int pos,int v)
{
	if(l==r)
	{
		val[l]+=bj[now]*nv[l];
		bj[now]=0;nv[l]=v;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	if(mid>=pos)modify(ls,pos,v);
	else modify(rs,pos,v);
}
void insert(int l,int r,int now,int lq,int rq)
{
	if(lq<=l&&r<=rq)
		{bj[now]++;return;}
	int mid=(l+r)>>1;
	if(mid>=lq)insert(ls,lq,rq);
	if(mid<rq) insert(rs,lq,rq);
}
void down(int l,int r,int now)
{
	if(l==r)
	{
		val[l]+=bj[now]*nv[l];
		return;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	down(ls);down(rs);
}
int main()
{
	//freopen("tt.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+1+n);
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j+=i)
			vec[j].push_back(i);
	for(int i=1;i<=m;i++)
	{
		beg[i]=cnt+1;
		for(int j=0;j<vec[i].size();j++)
			b[++cnt]=vec[i][j];
		ed[i]=cnt;
	}
	for(int i=1,now=1,t=0;i<=m;i++)
	{
		while(t<ed[i])
		{
			t++;
			if(pos[b[t]])
				modify(1,cnt,1,pos[b[t]],0);
			modify(1,cnt,1,t,1);
			pos[b[t]]=t;
		}
		while(now<=n&&a[now].r==i)
		{
			insert(1,cnt,1,beg[a[now].l],ed[a[now].r]);
			now++;	
		}
	}
	down(1,cnt,1);
	for(int i=1;i<=cnt;i++)
		ans[b[i]]+=val[i];
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}


Measured memory_bytes: 55296
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

pair<char, int> c[4][13];
signed main(void)
{
	while(1) {
		char t;
		cin >> t;
		if(t == '#') break;
		REP(i, 4) REP(j, 13) {
			string a;
			cin >> a;
			int tmp = -1;
			if('2' <= a[0] && a[0] <= '9') tmp = a[0] - '0' - 1;
			else if(a[0] == 'A') tmp = 13;
			else if(a[0] == 'T') tmp = 9;
			else if(a[0] == 'J') tmp = 10;
			else if(a[0] == 'Q') tmp = 11;
			else if(a[0] == 'K') tmp = 12;
			//cout << tmp << " ";
			c[i][j] = {a[1], tmp};
		}
		//cout << endl;

		int fir = 0, ns = 0, ew = 0;
		REP(i, 13) {
			char l = c[fir][i].first;
			bool tr = false;
			int ma = 0, id = -1;
			REP(j, 4) {
				//cout << c[j][i].first << " " << c[j][i].second << endl;
				if(c[j][i].first == t && (!tr || (tr && ma < c[j][i].second))) {
					tr = true;
					ma = c[j][i].second;
					id = j;
				} else if(!tr && c[j][i].first == l && ma < c[j][i].second) {
					ma = c[j][i].second;
					id = j;
				}
			}
			if(id == 0 || id == 2) ns++;
			else ew++;
			//cout << "win:" << id << endl;
			fir = id;
		}
		//cout << endl;
		if(ns > ew) cout << "NS " << ns-6 << endl;
		else cout << "EW " << ew-6 << endl;
	}

	return 0;
}

Measured memory_bytes: 3080
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef string str;
typedef std::pair<ll,ll> pl;
typedef std::map<string, ll> msl;
typedef std::map<ll, ll> mll;
typedef std::vector<ll> vl;
const long double EPS = 1e-9;
 
#define rep(i, n) for(ll (i) = 0; (i) < (n) ; (i)++ )
#define For(i, a, b) for(ll (i) = (a); (i) < (b) ; (i)++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define tol(c) char((c)+0x20)
#define tou(c) char((c)-0x20)
#define pb push_back
#define mp make_pair
#define pr(a) cout << (a)
#define prl(a) cout << (a) << endl
#define prl2(a,b) cout << (a) << " " << (b) << endl
#define prs(a) cout << (a) << " "
#define yn(condition) if ((condition)) prl("Yes"); else prl("No");
#define YN(condition) if ((condition)) prl("YES"); else prl("NO");
#define rpr(i,n,ans) rep((i),(n)) prs((ans[(i)]))
#define cpr(i,n,ans) rep((i),(n)) prl((ans[(i)]))
#define in1(a) cin >> (a)
#define in2(a,b) cin >> (a) >> (b)
#define in3(a,b,c) cin >> (a) >> (b) >> (c)
#define in4(a,b,c,d) cin >> (a) >> (b) >> (c) >> (d)
#define rin1(i,n,a) rep((i),(n)) cin >> (a[(i)])
#define rin2(i,n,a,b) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)])
#define rin3(i,n,a,b,c) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)]) >> (c[(i)])
#define e1 first
#define e2 second
#define ctol(c) ll((c)) - ll('0')
#define ltos(n) to_string((n))
#define items(kv, v) for(auto &(kv): (v))
#define ndig(N, n) ctol(ll(ltos((N))[ll(ltos((N)).length()) - (n)]))
#define beto(a,b,c) (a) < (b) && (b) < (c)
#define betc(a,b,c) (a) <= (b) && (b) <= (c)
#define rsort(a,n) sort(a,a+n,greater<>())
 
const ll mod = 1e9 + 7;
const ll INF = mod * mod;
const ll MAX_N = 100;
 
int main(void){
    ll a,b,c,x;
    ll answer = 0;
    
    in4(a,b,c,x);
    rep(i,a+1) rep(j,b+1) rep(k,c+1) if (i*500+j*100+k*50 == x) answer++;

    prl(answer);
 
    return 0;
}

Measured memory_bytes: 256
A,B = map(int,input().split())

def f(n):
    if n%4 == 0:
        return n
    elif n%4 == 1:
        return 1
    elif n%4 == 2:
        return n+1
    else:
        return 0
        
aor = f(A-1)
bor = f(B)

print(aor^bor)

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

int main() {
  int N;
  cin >> N;
  vector<vector<int>> data(N, vector<int>(2));
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> data.at(i).at(j);
    }
  }
  
  int sum = 0;
   for (int i = 0; i < N; i++) {
      sum += data.at(i).at(1) - data.at(i).at(0) +1;
  }
 cout << sum << endl;
}


Measured memory_bytes: 256