akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let mut a: Vec<u64> = sc.vec(n);
    let mut xor = 0;
    for &a in a.iter() {
        xor ^= a;
    }

    for i in 0..n {
        a[i] &= !xor;
    }

    let mut rank = 0;
    for pos in (0..62).rev() {
        if let Some(i) = (rank..n).find(|&i| a[i] & (1 << pos) != 0) {
            a.swap(rank, i);
            assert_ne!(a[rank] & (1 << pos), 0);
            for i in 0..n {
                if i == rank {
                    continue;
                }
                if a[i] & (1 << pos) != 0 {
                    a[i] ^= a[rank];
                }
            }
            rank += 1;
        }
    }

    let mut sum1 = 0;
    for i in 0..rank {
        sum1 ^= a[i];
    }
    assert_eq!(sum1 & xor, 0);

    let ans = sum1 * 2 + xor;
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 2816
//include for verify
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
#include<cassert>
#include<iostream>
#include<climits>
using namespace std;
 
const int N = (1<<20);//number of element
const int M = 2*N;//required memory 
const int MAX_VALUE=INT_MAX;//maximum possible value;
int segt[M];//init with MAX_VALUE
int inp[N];
 
void update(int value,int pos,int n){
  int index=n-1+pos;
  segt[index]=value;//[pos,pos]
  while(index>0){
    index=(index-1)/2;
    segt[index]=segt[index*2+1]+segt[index*2+2];
  }
}
 
//children of now
//left now*2+1
//right now*2+2
//find[ql,qr] from [l,r] (definition of l and r is different from ant books)
int query(const int l,const int r,const int index,int q){
  if (l == r && segt[index] == q){
    return l;
  }
  int left=index*2+1,right=index*2+2;
  int midr=(l+r)/2,midl=midr+1;
  if (q <= segt[left])return query(l,midr,left,q);
  else if (q > segt[left])return query(midl,r,right,q-segt[left]);
  assert(false);
}
//end of library
 
void init(int n){
  for(int i=0;i<n;i++)segt[i]=0;
  for(int i=0;i<n;i++)update(0,i,n);
}

void del(int n,int i,map<int,int> &M){
  int pos=query(0,n-1,0,i);
  update(0,pos,n);
  M.erase(inp[pos]);
}

void insert(int n,int i,const int lim,map<int,int> &M){
  update(1,i,n);
  if (segt[0] == lim+1)del(n,1,M);
}

int getn(int n){
  for(int i=0;;i++)if ((1<<i) > n)return (1<<i);
}

main(){
  int q,lim;
  while(cin>>q>>lim){
    if (q == 0 && lim == 0)break;
    int p=0;
    map<int,int> M;
    int n=getn(q);
    init(n);
    for(int i=0;i<q;i++){
      int inq,x;
      cin>>inq>>x;
      if (inq == 0){
	if (M.find(x) != M.end()){
	  assert(false);
	  cout <<"Error 0" << endl;
	}else {
	  M[x]=p;
	  inp[p]=x;
	  insert(n,p,lim,M);
	  p++;
	}
      }else if (inq == 1){
	if (x > (int)M.size()){
	  assert(false);
	  cout <<"Error 1" << endl;
	}else {
	  del(n,x,M);
	}
      }else if (inq == 2){
	if (x > (int)M.size()){
	  assert(false);
	  cout <<"Error 2" << endl;
	}else {
	  int index=query(0,n-1,0,x);
	  cout << inp[index] << endl;
	}
      }else if (inq == 3){
	if (M.find(x) == M.end()){
	  assert(false);
	  cout <<"Error 3" << endl;
	}else {
	  int pos=M[x];
	  M.erase(x);
	  update(0,pos,n);
	}
      }else assert(false);
    }
    cout<<"end" << endl;
  }
  return 0;
}

Measured memory_bytes: 7708
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	ll x,cost;
};
int main() {

	ll n;
	int k;
	cin>>n>>k;
	ll a=k,b=1;
	while(a<=n){
		a*=k;
		b++;
	}
	cout<<b<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys
from collections import deque
import math

input = sys.stdin.readline


def solve():
    N, K = map(int, input().split())
    answer = 0
    for k in range(K, N + 2):
        answer += k * (N - k + 1) + 1
    return answer % (10 ** 9 + 7)


if __name__ == '__main__':
    answer = solve()
    print(answer)


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

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

	string s;
	cin>>s;
	if(s.at(2)==s.at(3)&&s.at(4)==s.at(5))cout<<"Yes\n"s;
	else cout<<"No\n"s;
}

Measured memory_bytes: 256
import java.util.Scanner;

class NodeRef{
    Node node;
}

enum Color{
    RED,
    BLACK
}

class Node{
    Node left;
    Node right;
    Node next;
    int data;
    int lis;
    int height;
    int size;
    Color color;

    public static Node newNode(int data){
        Node n = new Node();
        n.left = null;
        n.right = null;
        n.data = data;
        n.lis = -1;
        n.height = 1;
        n.size = 1;
        n.color = Color.RED;
        return n;
    }
}

// BST
public class Main {
    public Node addNode(int data, Node head){
        Node tempHead = head;
        Node n = Node.newNode(data);
        if(head == null){
            head = n;
            return head;
        }
        Node prev = null;
        while(head != null){
            prev = head;
            if(head.data < data){
                head = head.right;
            }else{
                head = head.left;
            }
        }
        if(prev.data < data){
            prev.right = n;
        }else{
            prev.left = n;
        }
        return tempHead;
    }

    class IntegerRef{
        int height;
    }

    public int height(Node root){
        if(root == null){
            return 0;
        }
        int leftHeight  = height(root.left);
        int rightHeight = height(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static void preOrder(Node node) {
        if(node != null) {
            System.out.print(" " + node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public static void inOrder(Node node) {
        if(node != null) {
            inOrder(node.left);
            System.out.print(" " + node.data);
            inOrder(node.right);
        }
    }

    public Node search(Node root, int key){
        if(root == null){
            return null;
        }
        if(root.data == key){
            return root;
        }else if(root.data < key){
            return search(root.right, key);
        }else{
            return search(root.left, key);
        }
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = "";
        int key;

        Node head = null;
        Main bt = new Main();
        for(int i = 0; i < n; i++) {
            s = sc.next();
            if(s.equals("insert")){
                key = sc.nextInt();
                head = bt.addNode(key, head);
            } else if(s.equals("print")) {
                inOrder(head);
                System.out.println();
                preOrder(head);
                System.out.println();
            } else if(s.equals("find")) {
                key = sc.nextInt();
                Node t = bt.search(head, key);
                if(t != null) {
                    System.out.print("yes\n");
                } else {
                    System.out.print("no\n");
                }
            }
        }
    }
}



Measured memory_bytes: 212772
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, d = map(int, input().split())
    ans = 0
    for _ in range(n):
        x, y = map(int, input().split())
        ans += x ** 2 + y ** 2 <= d ** 2
    print(ans)
resolve()

Measured memory_bytes: 68748
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
#define MOD 1000000007
#define ll long long

vector<int> a;

void makeA(int M){
	for(int i = 2; i * i <= M; ++i){
		if(M % i != 0) continue;
		int num = 0;
		while(M % i == 0){
			M /= i;
			num++;
		}
		a.push_back(num);
	}
	if(M != 1)a.push_back(1);
	return;
}

const int MAX = 210000;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i = 2; i < MAX; i++){
		fac[i] = fac[i-1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
		finv[i] = finv[i-1] * inv[i] % MOD;
	}
}

ll COM(int n, int k) {
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main(void){
	int N, M;
	cin >> N >> M;
	makeA(M);
	COMinit();
	ll ans = 1;
	for(auto x : a){
		ll tmp = COM(x + N - 1, N - 1);
		ans *= tmp;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5120
import heapq, sys
def input():
    return sys.stdin.readline()[:-1]

n, m, s, t = map(int, input().split())

yen_edge = [[] for _ in range(n)]
snuke_edge = [[] for _ in range(n)]

for _ in range(m):
	u, v, a, b = map(int, input().split())
	yen_edge[u - 1].append([v - 1, a])
	yen_edge[v - 1].append([u - 1, a])
	snuke_edge[u - 1].append([v - 1, b])
	snuke_edge[v - 1].append([u - 1, b])

class DijkstraList():
    #隣接リスト版
    #同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
    def __init__(self, adj, start):
        self.list = adj
        self.start = start
        self.size = len(adj)

    def solve(self):
        self.dist = [10**30 for _ in range(self.size)]
        self.dist[self.start] = 0
        #self.prev = [-1 for _ in range(self.size)]
        self.q = []
        self.cnt = 0

        heapq.heappush(self.q, (0, self.start))

        while self.q and self.cnt < self.size:
            u_dist, u = heapq.heappop(self.q)
            if self.dist[u] < u_dist:
                continue
            for v, w in self.list[u]:
                if self.dist[v] > u_dist + w:
                    self.dist[v] = u_dist + w
                    #self.prev[v] = u
                    heapq.heappush(self.q, (self.dist[v], v))

            self.cnt += 1

        return

    def distance(self, goal):
        return self.dist[goal]

yen = DijkstraList(yen_edge, s - 1)
snuke = DijkstraList(snuke_edge, t - 1)
yen.solve()
snuke.solve()
ans_list = []

for i in range(n):
	ans_list.append(yen.distance(i) + snuke.distance(i))

ans = []

ans.append(10 ** 15 - ans_list[n - 1])

for i in range(1, n):
	if ans_list[n - i - 1] > ans_list[n - i]:
		ans_list[n - i - 1] = ans_list[n - i]
	ans.append(10 ** 15 - ans_list[n - i - 1])

for i in range(n - 1, -1, -1):
	print(ans[i])

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

#define MOD 1000000007

void solve(long long N, string S){

	map<int, long long> m;
	for (int i=0; i<N; i++) {
		m[S[i]-'a']++;
	}
	long long res = 1;
	// for (int i='a'-'a'; i<='z'-'a'; i++) {
	// 	cout << m[i] << "\n";
	// }
	for (int i='a'-'a'; i<='z'-'a'; i++) {
		if (m[i] != 0) res = res * (m[i]+1) % MOD;
	}
	cout << res-1 << "\n";
}

int main(){
	string S;
	long long N;
	scanf("%lld",&N);
	cin >> S;
	solve(N, S);
	return 0;
}


Measured memory_bytes: 512
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
    	InputStream inputStream = System.in;
    	OutputStream outputStream = System.out;
    	Scanner sc = new Scanner(inputStream);
    	PrintWriter out = new PrintWriter(outputStream);
      	int X = Integer.parseInt(sc.next());
      	int A = Integer.parseInt(sc.next());
      	int B = Integer.parseInt(sc.next());
    	if(0 <= A - B){
        	out.println("delicious");
        }else if(Math.abs(A - B) <= X){
        	out.println("safe");
        }else{
        	out.println("dangerous");
        }
   		out.close();
    }
}

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

#define int long long
const int MOD = 1000000007LL;

signed main(){

    int n; cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];
    vector<vector<int> > dp(n + 1, vector<int> (3, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 3; j++){
            if(j != 0) dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + a[i]);
            if(j != 1) dp[i + 1][1] = max(dp[i + 1][1], dp[i][j] + b[i]);
            if(j != 2) dp[i + 1][2] = max(dp[i + 1][2], dp[i][j] + c[i]);
        }
    }

    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;

    return 0;
}


Measured memory_bytes: 8064
#include<iostream>
using namespace std;
typedef long long ll;
int t;
string s;

int main()
{
    ll a,b,n,x,mx=0,d,lop;
    cin>>a>>b>>n;

    if(n>=b){
        x=b-1;
        lop=(n-b)/2;
    }
    else x=n,lop=(b-n)/2;

    while(x>lop){
        d = ((a*x)/b)-(a*(x/b));
        if(d>mx){
            mx=d;
            break;
        }

        x--;
    }
    cout<<mx<<endl;

    return 0;
}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
//Yes,No
int main(){
    string s;cin >> s;
    set<char> st;
    rep(i,s.size())st.insert(s[i]);
    if(st.size()==3)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import math

n = int(input())
N = n

if(n == 1):
    print(0)
    exit()

yakusu = []
multi = []

i = 2

while(i <= math.ceil(math.sqrt(N))):
    
    if(n % i == 0):
        if(i in yakusu):
            multi[yakusu.index(i)] += 1
        else:
            yakusu.append(i)
            multi.append(1)
        n = int(n / i)
        continue
    
    if(n == 1):
        break
    
    i += 1
    
else:
    yakusu.append(n)
    multi.append(1)

if(len(yakusu) == 0):
    print(1)
    exit()
    
# print(yakusu)
# print(multi)

ans = 0

for j in range(len(multi)):
    h = (-1 + int(math.sqrt(1 + 8 * multi[j]))) / 2
    ans += int(h)

print(ans)

Measured memory_bytes: 9276
#include<cstdio>
#include<cstring>
#include<functional>
using namespace std;
int main(void)
{
	int c1,c5,c10,c50,c100,c500,sum,flg;
	scanf("%d %d %d %d %d %d",&c1,&c5,&c10,&c50,&c100,&c500);
	sum=c1*1+c5*5+c10*10+c50*50+c100*100+c500*500;
	if(sum>=1000)	{
		flg=1;
	}
	else {
		flg=0;
	}
	printf("%d\n",flg);
	return 0;
}


Measured memory_bytes: 1028
/*
	author: Ibrahim-Elsayed (Codeforces Handle)
	date: 9/17/2020
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const double PI = acos(-1);

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

	int n;
	cin >> n;
	vector<int> arr(n);
	for(int& el : arr) cin >> el;
	vector<int64_t> dp(n); // dp[i] is minimum total cost to reach the end starting from idx i;
	dp[n - 1] = 0;
	for(int i = n-2; i >= 0; i--) {
		dp[i] = dp[i + 1] + abs(arr[i] - arr[i+1]);
		if(i+2 < n) {
			dp[i] = min(dp[i], dp[i + 2] + abs(arr[i] - arr[i+2]));
		}
	}
	cout << dp[0];

	return 0;
}



Measured memory_bytes: 4480
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<30
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;

int main(){
  int r,c;
  while(true){
    cin >> r >> c;
    if(r+c == 0)break;
    (r*c)%2==0 ?cout << "yes" << endl:cout << "no" << endl;
  }
return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
            using namespace std;
             
            int main() {
              int a,b;
              cin >> a >> b;//.at(0) >> s.at(1) >> s.at(2) >> s.at(3);
              //sort(s.begin(),s.end());
              
              //for(int i=0; i<6; i++)
              //if(s.at(i)=='1') ans++;
              if(b==1)cout << 0 << endl;
              else cout << a-b << endl;
              return 0;
            }

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

int main() {
    int n; cin >> n;
    long long mod = pow(10, 9) + 7;
    long long x = 1, y = 1, z = 1;
    for (int i=0; i<n; i++) {
        x = x * 10 % mod;
        y = y * 9 % mod;
        z = z * 8 % mod;
    }
    long long ans = (x - 2*y + z + 2*mod) % mod;
    cout << ans << endl; 
}

Measured memory_bytes: 3616
/*
    Problem 5
    https://atcoder.jp/contests/abc095/tasks/arc096_a
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <bitset>

using namespace std;
/* typedef */
typedef long long ll;
/* constant */
const ll MAX = 100000000000;
/* global variables */
/* function */
/* main */
int main(){
    ll A, B, C, X, Y;
    cin >>  A >> B >> C >> X >> Y;
    ll ans = MAX;

    ans = min(ans, C * max(X, Y) * 2);
    ans = min(ans, A * X + B * Y);
    ans = min(ans, C * X * 2 + B * ((Y - X > 0) ? Y - X : 0));
    ans = min(ans, C * Y * 2 + A * ((X - Y > 0) ? X - Y : 0));

    cout << ans << '\n';
}


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

#define ll long long
#define int long long
#define MOD 1000000007
#define MAX 100001
#define debugStart cout << "\n[DEBUG START]\n"
#define debugStop cout << "\n[DEBUG STOP]\n"
#define KHATAM cout << std::endl;
// #define MAX_H 100001
// #define MAX_W 100001 

auto solve ( const int input[][2], int N, int W ) -> int {

        int DP[N+1][W+1];
        memset(DP, 0, sizeof(DP));
        for ( int i = 1; i <= N; ++i  ) {

                for ( int weight = 1; weight <= W; ++weight ) {
                        DP[i][weight] = DP[i-1][weight];
                        if ( (weight - input[i-1][0]) >= 0 ) {
                                DP[i][weight] = std::max(DP[i][weight], input[i-1][1] + DP[i-1][weight -input[i-1][0] ] );
                        }
                }
        }
        return DP[N][W];
}

signed
main() {

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int T = 1; 
        // cin >> T;
        for ( int testcase = 1; testcase <= T; ++testcase ) {

                int N, W;
                std::cin >> N >> W;
                int input[N][2];
                for ( int i = 0; i < N; ++i ) {
                        std::cin >> input[i][0] >> input[i][1];
                }
                std::cout << solve( input, N, W ) << '\n';
        }
        return 0;
}

Measured memory_bytes: 79232
#pragma region pre
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
using ll = long long;
constexpr double INF{ 1e9 };
constexpr int MOD{ 1000000000 + 7 };
#define rep(i,n) for (int i = 0; i < n; ++i)
constexpr array<int, 4> dy{ -1, 1, 0, 0 };
constexpr array<int, 4> dx{ 0, 0, -1, 1 };

//constexpr int div_ru(int a, int b)
//{
//    return (a - b + 1) / b;
//}
//ll pow_mod(ll b, ll e, ll m)
//{ // https://atcoder.jp/contests/atc002/tasks/atc002_b
//    ll r = 1;
//    for (; e > 0; e >>= 1)
//    {
//        if (e & 1)
//            r = (r * b) % m;
//        b = (b * b) % m;
//    }
//    return r;
//}
class UnionFindTree
{
private:
    vector<int> par_;
    vector<int> rank_;

public:
    UnionFindTree(int);
    ~UnionFindTree();
    int root(int);
    bool same(int, int);
    void unite(int, int);
    int size();
};

UnionFindTree::UnionFindTree(int n) : par_(n), rank_(n)
{
    iota(par_.begin(), par_.end(), 0);
}

UnionFindTree::~UnionFindTree()
{
}

int UnionFindTree::root(int x)
{
    return par_[x] == x ? x : par_[x] = root(par_[x]);
}

bool UnionFindTree::same(int x, int y)
{
    return root(x) == root(y);
}

void UnionFindTree::unite(int x, int y)
{
    x = root(x);
    y = root(y);
    if (x == y)
        return;
    else if (rank_[x] < rank_[y])
        par_[x] = y;
    else
    {
        par_[y] = x;
        if (rank_[x] == rank_[y])
            rank_[x]++;
    }
}

int UnionFindTree::size()
{
    const int n = par_.size();
    int n_node = 0;
    for (int i = 0; i < n; ++i) {
        if (i == root(i))
            n_node++;
    }

    return n_node;
}

#pragma endregion

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

    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    int min_cost = INF;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            const int p = x[i] - x[j];
            const int q = y[i] - y[j];

            if (p == 0 && q == 0) {
                continue;
            }

            int cost = n;

            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {

                    if (k == l) {
                        continue;
                    }

                    const int diff_x = x[k] - x[l];
                    const int diff_y = y[k] - y[l];

                    if (p == diff_x && q == diff_y) {
                        cost--;
                    }
                }
            }
            min_cost = min(cost, min_cost);
        }
    }

    if (n == 1)
        min_cost = 1;
    cout << min_cost << endl;
}
// vector<vector<int>> mm(h, vector<int>(w, -1));


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    H, W = LI()
    maze = SR(H)
    # top, right, bottom, left
    info = [[0 for _ in range(W)] for _ in range(H)]

    # from top to bottom
    for w in range(W):
        current = 0
        for h in range(H):
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from right to left
    for h in range(H):
        current = 0
        for w in range(W)[::-1]:
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from bottom to top
    for w in range(W):
        current = 0
        for h in range(H)[::-1]:
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from  left to right
    for h in range(H):
        current = 0
        for w in range(W):
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == ".":
                ans = max(ans, info[h][w] + 1)
    print(ans)

if __name__ == '__main__':
    main()

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

int main() {
  int N; cin >> N;
  int ans = 0;
  rep(i, 0, N) {
    int a; cin >> a;
    ans += a - 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

	void solve() {
		IOS;
		int s, w;
		cin >> s >> w;
		if (s > w) {
			put("safe");
		} else {
			put("unsafe");
		}
	}
} // namespace idaten

int main() {
	idaten::solve();
	return 0;
}


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

int main() {
  int K,S;
  cin>>K>>S;
  int sum=0;
  rep(i,K+1){
    rep(j,K+1){
      int z = S-i-j;
      if(z>=0&&z<=K) sum++;//x+y+z=Sとなるようなzが存在する
    }
  }

  cout << sum << endl;
     
      
  return 0;
}


Measured memory_bytes: 256
a, b, c = [int(i) for i in input().split()]

cnt = 0

f_a = a
f_b = b
f_c = c

while(a%2==0 and b%2==0 and c%2==0):
    t_a = a
    t_b = b
    t_c = c
    a = (t_b+t_c)/2
    b = (t_c+t_a)/2
    c = (t_a+t_b)/2
    cnt += 1
    if (a == f_a and b == f_b and c == f_c):
        cnt = -1
        break


print(cnt)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
typedef long long ll;
using namespace std;



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

    cout << "Yes" << endl;
}

Measured memory_bytes: 3040
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int mod=1e9+7;
int n;

int inv(int x)
{
    int r,y;
    for(r=1,y=mod-2;y>0;x=(x*x)%mod,y/=2)
        if(y%2==1)
            r=r*x%mod;
    return r;
}
int power(int x,int y,int p)
{ 
    int res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if((y & 1)==1) 
            res = (res * x) % p; 
        y = y >> 1;  
        x = (x * x) % p;  
    } 
    return res; 
} 
int32_t main() 
{
    IOS
    cin>>n;
    int arr[n];
    map<int,int>mp;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        int temp = arr[i];
        for(int j=2;j*j<=temp;j++)
        {
            int ctr=0;
            while(temp%j==0)
            {
                temp/=j;
                ctr++;
            }
            if(ctr)
                mp[j]=max(mp[j],ctr);
        }
        if(temp!=1)
            mp[temp]=max(mp[temp],1ll);
    }
    int lcm=1;
    for(auto i:mp)
        lcm=(lcm*power(i.first,i.second,mod))%mod;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=(lcm*inv(arr[i]))%mod;
        ans%=mod;
    }
    print(ans);
}   


Measured memory_bytes: 4320
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
  
int main () {
  int a, b ,c;
  cin >> a >> b >> c;
  if(a + b + c < 22) {
    cout << "win";
  }
  else {
    cout << "bust";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

class Radix {
private:
  const char* s;
  int a[128];
public:
  Radix(const char* s = "0123456789ABCDEF") : s(s) {
    int i;
    for(i = 0; s[i]; ++i)
      a[(int)s[i]] = i;
  }
  std::string to(long long p, int q) {
    int i;
    if(!p)
      return "0";
    char t[64] = { };
    for(i = 62; p; --i) {
      t[i] = s[p % q];
      p /= q;
    }
    return std::string(t + i + 1);
  }
  std::string to(const std::string& t, int p, int q) {
    return to(to(t, p), q);
  }
  long long to(const std::string& t, int p) {
    int i;
    long long sm = a[(int)t[0]];
    for(i = 1; i < (int)t.length(); ++i)
      sm = sm * p + a[(int)t[i]];
    return sm;
  }
};

int main(){
    ll N, A, B, C; cin >> N >> A >> B >> C ;
    vll l(N);
    for(int i=0; i<N; i++){
        cin >> l[i];
    }
    ll min = 10000000000000;
    for(int i=0; i<pow(4,N); i++){
        vll a(0), b(0), c(0), d(0);
        Radix r;
        string k = r.to(i, 4);
        if(k.size() == N){
            for(int j=0; j<N; j++){
                if(k[j] == '0'){
                    a.emplace_back(l[j]);
                }else if(k[j] == '1'){
                    b.emplace_back(l[j]);
                }else if(k[j] == '2'){
                    c.emplace_back(l[j]);
                }else{
                    d.emplace_back(l[j]);
                }
            }
        }else{
            int p = k.size();
            string m = "";
            for(int j=0; j<N-p; j++){
                m.push_back('0');
            }
            string h = m + k;
            for(int j=0; j<N; j++){
                if(h[j] == '0'){
                    a.emplace_back(l[j]);
                }else if(h[j] == '1'){
                    b.emplace_back(l[j]);
                }else if(h[j] == '2'){
                    c.emplace_back(l[j]);
                }else{
                    d.emplace_back(l[j]);
                }
            }
        }
        ll res = 0;
        ll s=0, t=0, u=0, v=0;
        for(auto x: a){s+=x;}
        for(auto x: b){t+=x;}
        for(auto x: c){u+=x;}
        for(auto x: d){v+=x;}
        if(s==0||t==0||u==0){
            continue;
        }
        res += abs(A-s);
        res += abs(B-t);
        res += abs(C-u);
        res += (a.size()-1)*10;
        res += (b.size()-1)*10;
        res += (c.size()-1)*10;
        
        if(res < min){min = res;}
    }
    cout << min;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
int main(){
	int i;
	char s[101];
	int length;
	int cnt=0;
	scanf("%s",s);
	length=strlen(s);
	for(i=0;i<length/2;i++){
		if(s[i]!=s[length-i-1]) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 128
n,a,b = map(int,input().split())
s = str(input())
cntab = 0
cntb = 0
for i in range(n):
    if s[i]=="a" and cntab<a+b:
        print("Yes")
        cntab+=1
    elif s[i]=="b" and cntab<a+b and cntb<b:
        print("Yes")
        cntab+=1
        cntb+=1
    else:
        print("No")

Measured memory_bytes: 4016
#include <stdio.h>

int osero(int c,int d, int e, int f){

  int a = c -e;
  int b = d - f;

  printf("%d\n", a * b);

return 0;
}

int main(){
 int H,W,h,w;

  scanf("%d %d",&H,&W);
  scanf("%d %d",&h,&w);

  osero(H,W,h,w);

  return 0;

}

Measured memory_bytes: 128
import java.util.Scanner;

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

   
   int a = stdIn.nextInt();
   int b = stdIn.nextInt();
   int c = stdIn.nextInt();
   
   if (a < b && b < c){
   System.out.println("Yes");
   } else {
   System.out.println("No");
   }
 }
}


Measured memory_bytes: 26160
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
int n;
char a[9];
cin >> n;
while(n--){
scanf("%s",a);
sort(a,a+8);
cout << 9999999*(a[7]-a[0]) + 999990*(a[6] - a[1]) + 99900 * (a[5] - a[2]) + 9000 * (a[4] - a[3]) << endl;
}

return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if(13<=a){
        cout << b << endl;
    }else if(a<=5){
        cout << 0 << endl;
    }else{
        cout << b/2 << endl;
    }
}



Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define clear(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
LL n, x, ans;
LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}
int main(){
#ifdef Qrsikno
	freopen("AGC001_2.in", "r", stdin);
	freopen("AGC001_2.out", "w", stdout);
#endif
	scanf("%lld %lld", &n, &x);
	ans = 3ll * (n - gcd(n, x));
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc020.contest.atcoder.jp/tasks/agc020_a>
問題文============================================================
 N 個のマスに区切られた細長い紙切れの上でゲームを行います。マスには 1 から N までの番号が順に付けられています。
 
 アリスの駒はマス A に、ボリスの駒は別のマス B に置かれています。
 
 二人にはターンが交互に訪れます。アリスが先手です。
 ターンが回ってきたプレイヤーは、
 自分の駒を現在のマス X から左隣のマス X−1 か右隣のマス X+1 のどちらかに動かさなければなりません。
 ただし、駒を紙切れの外に出したり、相手の駒と同じマスに動かしてはいけません。
 また、駒の移動は一ターンに一度だけ行わなければなりません。
 
 駒を動かせなくなった人が負けで、相手の勝ちとなります。
 
 二人とも、勝ちたいと思っています。二人とも最適にプレイするとき、どちらが勝つでしょうか？
=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N,A,B; cin >> N >> A >> B;
    if(abs(A-B)%2 != 0){
        cout<< "Borys" << endl;
    }else{
        cout << "Alice" << endl;
    }
	return 0;
}


Measured memory_bytes: 256
from copy import deepcopy

N,M,Q = map(int,input().split())
l = []
for _ in range(Q):
    l.append(list(map(int,input().split())))

high_score = 0

for a in range(1,M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    for j in range(i,M+1):
                                        score = 0
                                        A = [a,b,c,d,e,f,g,h,i,j]
                                        for li in l:
                                            if A[li[1]-1]-A[li[0]-1] == li[2]:
                                                score += li[3]
                                            if(high_score < score):
                                                high_score = score
print(high_score)

Measured memory_bytes: 9348
while True:
    a = input()
    n,x = map(int,a.split(" "))
    
    if n == x == 0:
        break
    
    count = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if (i+j+k) == x:
                    count += 1
    print(count)


Measured memory_bytes: 5596
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)

using namespace std;
typedef pair<int, int> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int A, B, C, res;
int main(int argc, char **argv) {
    cin >> A >> B >> C;
    int res = C - (A - B);

    res = max(res, 0);
    cout << res << endl;
}

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

int main(){
	string ss,s1,s2;
	int ans=1;
	cin>>ss;
	s1=ss[0];
	for(int i=1;i<ss.length();i++){
		s2=ss[i];
		if(s1==s2){
			s2+=ss[i+1];
			i++;
		} 
		if(i<ss.length()){
			ans++;
			s1=s2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i ++)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

int main() {
    int H,W; cin >> H >> W;
    vector<vector<int>> A(H,vector<int>(W));
    rep(i,H)rep(j,W) cin >> A[i][j];
    vector<vector<int>> B(H,vector<int>(W));
    rep(i,H)rep(j,W) cin >> B[i][j];

    vector<vector<int>> before(W,vector<int>(12800,0));
    vector<vector<int>> now(W,vector<int>(12800,0));
    before[0][6400] = 1;
    rep(i,H) {
        rep(j,W) {
            int a = A[i][j];
            int b = B[i][j];
            rep(k,12800) {
                if (before[j][k] == 0) continue;
                if (0 <= k + a - b && k + a - b < 12800) {
                    if (j + 1 < W) before[j + 1][k + a - b] = 1;
                    if (i + 1 < H) now[j][k + a - b] = 1;
                }
                if (0 <= k + b - a && k + b - a < 12800) {
                    if (j + 1 < W) before[j + 1][k + b - a] = 1;
                    if (i + 1 < H) now[j][k + b - a] = 1;
                }
            }
        }
        if (i == H - 1) break;
        swap(before,now);
        now = vector<vector<int>>(W,vector<int>(12800,0));
    }
    //rep(i,W)for (int j = 6200;j< 6500;j ++) printf("before[%d][%d]   %d   ",i,j,before[i][j]);

    int ans = INF;
    int a = A[H - 1][W - 1],b = B[H - 1][W - 1];
    rep(i,12800) {
        if ((0 <= i + a - b && i + a - b < 12800 && before[W - 1][i + a - b])
            || (0 <= i + b - a && i + b - a < 12800 && before[W - 1][i + b - a])) {
                ans = min(ans,abs(i - 6400));
            }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    string s; cin >> s;
    int st = 0, puyo = 0;
    for (char c: s) {
        if (c == 'S') st++;
        if (c == 'T' && st) st--, puyo++;
    }
    cout << s.size() - puyo * 2 << endl;
    return 0;
}


Measured memory_bytes: 640
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b
  | b = putStrLn "YES"
  | otherwise = putStrLn "NO"

yesNo b
  | b = putStrLn "Yes"
  | otherwise = putStrLn "No"

main = do
  [x, a, b] <- readInt
  putStrLn $ f x (b - a)

f x a
  | a <= 0 = "delicious"
  | x >= a = "safe"
  | otherwise = "dangerous"


Measured memory_bytes: 380
#!/usr/bin/env python3



N = int(input())
H = list(map(int, input().split()))

dp = [float('inf') for i in range(N+1)]

dp[1] = 0
dp[2] = abs(H[1]-H[0])
for i in range(3, N+1):
    dp[i] = min(dp[i-1]+abs(H[i-1]-H[i-2]), dp[i-2]+abs(H[i-1]-H[i-3]))

print(dp[N])


Measured memory_bytes: 13980
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

int main(){
  int n; cin >> n;
  vi a(n);
  rep(i, n) cin >> a[i];
  deque<int> dq;
  rep(i,n) {
    int k = lower_bound(all(dq), a[i]) - dq.begin();
    if(k == 0) dq.push_front(a[i]);
    else dq[k-1] = a[i]; 
  }

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int N = 100000;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int id_f;
int n, l, t;
struct Ants { int pos, dir; } a[N + 5];
struct Node { int pos, dir, id; } Ans[N + 5];

bool operator < (const Node& a, const Node& b) {
    return a.pos < b.pos ? true :
           a.pos == b.pos && a.dir < b.dir ? true :
           a.pos == b.pos && a.dir == b.dir && a.id < b.id;
}

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif 

    scanf("%d%d%d", &n, &l, &t);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].pos, &a[i].dir);
        int nxt_pos = a[i].pos + ((a[i].dir == 1) ? 1 : -1) * t;

        if(i && a[i].dir != a[0].dir) {
            if(a[i].dir == 2) {
                int dis = (a[i].pos - a[0].pos);
                if((t << 1) >= dis) id_f = (id_f + ((t << 1) - dis) / l + 1) % n;
            }else {
                int dis = (a[0].pos - a[i].pos + l);
                if((t << 1) >= dis) id_f = (id_f - ((t << 1) - dis) / l - 1) % n;
            }
        }
        Ans[i] = (Node) { (nxt_pos % l + l) % l, 2 - a[i].dir, i };
    }
    id_f = (id_f + n) % n;

    int d = 0;
    sort(Ans, Ans + n);
    for(int i = 0; i < n; ++i) if(Ans[i].id == 0) {
        d = (i - id_f + n) % n;
        break;
    }

    rotate(Ans, Ans + d, Ans + n);
    for(int i = 0; i < n; ++i) printf("%d\n", Ans[i].pos);

    return 0;
}


Measured memory_bytes: 3200
#include <iostream>

using namespace std;

int main(void)
{
    long long k;

    cin >> k;
    if(k % 2 == 0 || k % 5 == 0){
        cout << -1 << endl;
        return 0;
    }
    
    long long next_inc = 70;
    long long ex = 7;
    int cnt = 1;
    while(ex % k != 0){
        ex %= k;
        ex += next_inc;

        next_inc *= 10;
        next_inc %= k;
        cnt += 1;
    }

    cout << cnt << endl;

    return 0;
}

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

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

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

  ll l, r;
  if (N % 2 == 0) {
    l = A[N / 2 - 1] + A[N / 2];
    r = B[N / 2 - 1] + B[N / 2];
  } else {
    l = A[(N + 1) / 2 - 1];
    r = B[(N + 1) / 2 - 1];
  }

  ll ans = (r - l + 1);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 6368
#x個の列を取り出せる最大の長さf(x)を考える
#dの導入

import bisect
n = int(input())
a = list(map(int, input().split()))

c = [0]*(n+1)

for i in range(n):
    c[a[i]] += 1

d = [0]*(n+1)
for i in range(n+1):###
    d[c[i]] += 1

sum1 = 0
sum2 =sum(d)-d[0]
fx = []
for x in range(1,n+1):
    sum1 += x*d[x]
    sum2 -= d[x]
    fx.append((sum1+x*sum2)//x)
fx.sort()
for i in range(1,n+1):
    j = bisect.bisect_left(fx,i)###
    print(n-j)

Measured memory_bytes: 120476
#include <stdio.h>
#include <inttypes.h>

int N, M;
int A[114514];
int B[114514];

int main(void) {
	int i;
	int64_t asumikana, mizuhasikaori;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d", &B[i]) != 1) return 1;
	}

	asumikana = 0;
	for (i = 0; i < M; i++) {
		asumikana += B[i];
	}
	mizuhasikaori = 0;
	for (i = 0; i < N; i++) {
		mizuhasikaori += A[i];
	}
	printf("%" PRId64 "\n", asumikana * mizuhasikaori);

	return 0;
}



Measured memory_bytes: 2572