akhauriyash/Code-Regression huggingface dataset:
def examA():
    H, W = LI()
    S = [LSI() for _ in range(H)]
    Alpha = [chr(ord('A') + i) for i in range(26)]
    for i in range(H):
        for j in range(W):
            if S[i][j]=="snuke":
                ans = str(Alpha[j]) + str(i+1)
    print(ans)
    return

def examB():
    N = I()
    ans = []
    cur = int((N*2-1)**0.5)+1
    ansC = (cur+1)*cur//2
    neg = ansC-N
    if neg>cur:
        cur -=1
        ansC = (cur + 1) * cur // 2
        neg = ansC - N
    for i in range(1,cur+1):
        if i!=neg:
            ans.append(i)
    for v in ans:
        print(v)
#    print(cur,neg)
    return

def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    que = deque()
    que.append(e)
    len = [10**9]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowlen = len[now]
        for ne in fordfs[now]:
            if len[ne] == 10**9:
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examC():
    N, M = LI()
    V = [[]for _ in range(N+M)]
    for i in range(N):
        L = LI()
        for k in range(1,L[0]+1):
            V[i].append(L[k]+N-1)
            V[L[k]+N-1].append(i)
    length = bfs(N+M,0,V)
    ans = "YES"
    for i in length[:N]:
        if i==10**9:
            ans = "NO"
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); maxX = max(X)+1
    dx = defaultdict(int)
    dm = [set()for _ in range(M)]
    d = defaultdict(int)
    for x in X:
        dx[x] +=1
        d[x%M] +=1
        dm[x%M].add(x)
    ans = 0
#    print(d); print(dx); print(dm)
    ans +=d[0]//2
    d[0] = 0
    for i in range(1,1+M//2):
        cur = min(d[i],d[M-i])
        ans +=cur
        d[i] -=cur; d[M-i] -=cur
#    print(ans); print(d)
    for i in d.keys():
        for j in dm[i]:
            cur = min(dx[j]//2,d[i]//2)
            d[i] -= cur * 2
            ans += cur
            if d[i]<=1:
                break
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()


Measured memory_bytes: 96688
n, m = map(int, input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
total = [0] * (n + 1)
ans = 0

# 安い店から選ぶ方法が最適
shop = [tuple(map(int, input().split())) for _ in range(n)]
shop.sort()

for i in range(1, n + 1):
    a_i, b_i = shop[i - 1]
    # 累積和を作っておく
    # b[i]: i番目の店まで利用した際に購入できる栄養ドリンクの最大本数
    # total[i]: i番目の店まで利用した際に支払うお金の最大値
    b[i] = b[i - 1]
    total[i] = total[i - 1]
    b[i] += b_i
    total[i] += a_i * b_i

    # a[i]: i番目の店の栄養ドリンクの単価
    a[i] = a_i

for i in range(1, n + 1):
    if m <= b[i]:
        m = m - b[i - 1]
        # 足りない分を追加で計算
        ans = total[i - 1] + a[i] * m
        break
print(ans)

Measured memory_bytes: 26748
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int n, t, h;
    t=0;
    h=0;
    n = sc.nextInt();
    String a,b;
    for(int i=0;i<n;i++){
    a=sc.next();
    b=sc.next();
    if(a.compareTo(b)>0)t+=3;
    else if(a.compareTo(b)<0)h+=3;
    else {
        t++;
        h++;
    }
    }
    System.out.println(t+" "+h);
    }
    
}


Measured memory_bytes: 29924
n, q = map(int,input().split())
s = input()

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

#print(ac_list)

w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]

#print(w)

for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])

Measured memory_bytes: 17412
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define pri(n) printf("%d",n)
#define lpri(n) printf("%lld",n)
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define F first
#define S second
const ll mod=998244353;

int main()
{
    int t=1;
    //cin>>t;

    while(t--)
    {
        int n,w;
        cin>>n>>w;

        ll wt[n+5];
        ll val[n+5];

        ll dp[n+5][w+5];
        for(int i=0;i<=n;i++)
        for(int j=0;j<=w;j++)
        dp[i][j]=0;

        for(int i=1;i<=n;i++)
        {
            cin>>wt[i];
            cin>>val[i];
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=w;j++)
            {
                if(j-wt[i]>=0)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-wt[i]]+val[i]);
                else
                dp[i][j]=dp[i-1][j];
            }
        }

        cout<<dp[n][w];
    }
}

Measured memory_bytes: 80256
import java.io.*;
import java.util.*;

public class Main {
  private static int solve(int n, int[] as) {
    int count = 0;
    int next = 1;
    for (int i = 0; i < n; i++) {
      if (as[i] == next) {
        next++;
      } else {
        count++;
      }
    }
    if (count == n) {
      return -1;
    }
    return count;
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    int n = reader.nextInt();
    int[] as = reader.nextInt(n);
    out.println(solve(n, as));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 47700
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define dunk(a) cout << (a) << endl
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;

int main() {
	double a, b, h, m; cin >> a >> b >> h >> m;

	double ans = 0;
	double pi = 3.141592653589793238;
	double wa = 2 * pi / 720;
	double wb = 2 * pi / 60;
	double mi = 60 * h + m;
	double al = mi / 720;
	double be = m / 60;
	double the;

	if (abs(al - be) <= 1 - abs(al - be)) the = abs(al - be);
	else the = 1 - abs(al - be);

	ans = sqrt(a * a + b * b - 2 * a * b * cos(2 * pi * the));


	cout << fixed << setprecision(15) << ans << endl;
	return 0;
}


Measured memory_bytes: 4200
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//#define int ll

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


//std::ios::sync_with_stdio(false);
int c=0;
vector<vi>adj(200005);
int st[2000005];
int a[200005],ans[200005];
int update(int s,int e,int node,int pos,int val){
	if(s>pos||e<pos){
		return 0;
	}
	if(s==e){
		st[node]=val;
		return 0;
	}
	int mid=(s+e)/2;
	update(s,mid,2*node,pos,val);
	update(mid+1,e,2*node+1,pos,val);
	st[node]=max(st[2*node],st[2*node+1]);
	return 0;
}
int query(int s,int e,int node,int l,int r){
	if(s>r||e<l){
		return 0;
	}
	if(l<=s&&r>=e){
		return st[node];
	}
	int mid=(s+e)/2;
	return max(query(s,mid,2*node,l,r),query(mid+1,e,2*node+1,l,r));
}
int dfs(int u,int p){
	int q=query(0,c-1,1,0,a[u]-1);
	ans[u]=1;
	if(p!=-1){
		ans[u]=max(ans[u],ans[p]);
	}
	int i,prev=query(0,c-1,1,a[u],a[u]);
	ans[u]=max(ans[u],q+1);
	update(0,c-1,1,a[u],q+1);
	rep(i,adj[u].size()){
		if(adj[u][i]!=p)
			dfs(adj[u][i],u);
	}
	update(0,c-1,1,a[u],prev);
	return 0;
}
map<int,int>mapi;
map<int,int>::iterator it;
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int n,i,u,v;
	cin>>n;
	rep(i,n){
		cin>>a[i];
		mapi[a[i]]=1;
	}
	c=0;
	rep(i,n-1){
		cin>>u>>v;
		u--;
		v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(it=mapi.begin();it!=mapi.end();it++){
		it->ss=c++;
	}
	rep(i,n){
		a[i]=mapi[a[i]];
	}
	dfs(0,-1);
	rep(i,n){
		cout<<ans[i]<<endl;
	}
	return 0;
} 


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

using namespace std;

string s,rev,sub;

int main() {
	cin>>s;
	rev=s;
	reverse(rev.begin(),rev.end());
	if(rev!=s) puts("No");
	else {
		rev=sub=s.substr(0,(s.length()-1)/2);
		reverse(rev.begin(),rev.end());
		if(rev!=sub) puts("No");
		else {
			rev=sub=s.substr((s.length()+1)/2,(s.length()-1)/2);
			reverse(rev.begin(),rev.end());
			puts(rev==sub ? "Yes":"No");
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main()
{
    int i, ans, a, b, c,d;
    
    cin >> a >> b >> c;
    ans = 0;
    d=0;
    for(i=a; i<=b; i++)
    {
        if(ans== c % i )
        d++;
    }
    cout << d << endl;
}


Measured memory_bytes: 3116
_ = gets.to_i
a = gets.split(" ").map(&:to_i)
mul = 1
if a.include?(0)
  mul = 0
else
  a.each do |i|
    if mul <= 10**18
      mul *= i
    else
      break
    end
  end
end
print mul > 10**18 ? -1 : mul

Measured memory_bytes: 21700
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}



template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}



vector<long> dp(1000000, -1);
long n,y;


int main() {


  cin >> n >> y;

  vector<long> w(n);
  vector<long> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> w[i] >> v[i] ;
  }

  long ans = 0;

  vector<vector<long>> dp(n+1,vector<long>(y+1,0));


  for (int i = 1; i < n + 1; ++i){
    for(int j=1;j<y+1;j++){
      if (j >=w[i-1]){
        dp[i][j] = max(dp[i-1][j-w[i-1]] + v[i-1], dp[i-1][j] );
      }else{
        dp[i][j] = dp[i-1][j];
      }
    }
  }

  ans = dp[n][y];



  cout << ans;
}























Measured memory_bytes: 88064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
static class Program{
	const int mod=1000000007;
	const long o=1;
	static void Main(){
		Sc sc=new Sc();
		int n=sc.I;
		int[] a=sc.Ia;
		long ans=0;
		long[] h=new long[n+1];
		for(int i=0;i<n;i++) {h[a[i]]=i;}
		St stmax=new St(0,n-1,0);
		St stmin=new St(0,n-1,1);
		for(int i=1;i<=n;i++) {
			long q=stmax.Get(0,(int)h[i]).n;
			long p=stmin.Get((int)h[i],n-1).n;
			p=p==-1?n:p;
			ans+=(h[i]-q)*(p-h[i])*i;
			stmax.Ud((int)h[i],h[i]);
			stmin.Ud((int)h[i],h[i]);
		}
		Console.WriteLine(ans);
	}
}
public class St{
	public class Mo{
		public int n;
		public long d;
		public Mo(long d,int n){this.d=d;this.n=n;}
	}
	public Mo[] dat;
	private int m=1,f;
	private Mo du;
	private Func<Mo,Mo,bool> compare;
	public St(int f,int n,int mm){
		this.f=f;
		n+=f^1;
		if(mm==0){du=new Mo(long.MinValue,-1);compare=CoMax;}
		else{du=new Mo(long.MaxValue,-1);compare=CoMin;}
		while(m<n){m*=2;}
		dat=new Mo[m+n-1];
		for(int i=0;i<m+n-1;i++){dat[i]=du;}
	}
	private bool CoMax(Mo x,Mo y){return x.d>y.d;}
	private bool CoMin(Mo x,Mo y){return x.d<y.d;}
	public void Ud(int q,long b){
		q+=m-1-f;
		if(dat[q]==du){
			int z=q;
			dat[q]=new Mo(b,q-(m-1-f));
			while(q>0&&compare(dat[z],dat[(q-1)/2])){
				dat[(q-1)/2]=dat[z];
				q=(q-1)/2;
			}
		}
		else{
			//b+=dat[q].d;
			dat[q].d=du.d;
			dat[q]=new Mo(b,q-(m-1-f));
			q=(q-1)/2;
			while(q>=0){
				Mo o=compare(dat[2*q+1],dat[2*q+2])?dat[2*q+1]:dat[2*q+2];
				if(dat[q]==o){break;}
				dat[q]=o;
				q=(q-1)/2;
			}
		}
	}
	private Mo Fdg(int a,int b,int k,int l,int r){
		if(r<a||b<l){return du;}
		if(a<=l&&r<=b){return dat[k];}
		Mo p=Fdg(a,b,k*2+1,l,(l+r)/2);
		Mo q=Fdg(a,b,k*2+2,(l+r+1)/2,r);
		return compare(p,q)?p:q;
	}
	public Mo Get(int a,int b){return Fdg(a,b,0,f,m-(f^1));}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()).Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
}

Measured memory_bytes: 41112
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int n,j,flag,count=0,sub;
  int *A;

  scanf("%d",&n);
  A = (int *)malloc(sizeof(int) * n);
  if(A == NULL) exit(0);

  for(j = 0;j < n;j++){
    scanf("%d",&A[j]);
  }

  flag = 1;

  while(flag == 1){
    flag = 0;
    for(j = n-1;j >= 1;j--){
      if(A[j] < A[j-1]){
	sub = A[j-1];
	A[j-1] = A[j];
	A[j] = sub;
	flag = 1;
	count++;
      }
    }
  }

  for(j = 0;j < n;j++){
    printf("%d",A[j]);
    if(j != n-1) printf(" ");
  }
  printf("\n");
  printf("%d\n",count);

  free(A);

  return 0;
}

Measured memory_bytes: 604
#!/usr/bin/env python
import sys

def function(x):
    return x*x

def calculate(d, max):
    val = d
    result = 0
    while val < max:
        result += function(val) * d
        val += d
    return result

if __name__ == '__main__':
    for line in sys.stdin:
        print(calculate(int(line), 600))

Measured memory_bytes: 7556
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = numeric_limits<ll>::max();
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<pll> inxy(n);
    for (int i = 0; i < n; ++i) {
        cin >> inxy[i].first >> inxy[i].second;
    }

    vector<pll> xy;
    xy.reserve(n * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            xy.emplace_back(inxy[i].first, inxy[j].second);
        }
    }
    sort(xy.begin(), xy.end());
    ll ret = INF;
    for (int i = 0; i < n * n; ++i) {
        for (int j = i + 1; j < n * n; ++j) {
            ll inside = 0;
            for (int l = 0; l < n; ++l) {
                if (xy[i].first <= inxy[l].first && inxy[l].first <= xy[j].first) {
                    if ((xy[i].second <= inxy[l].second && inxy[l].second <= xy[j].second) ||
                        (xy[j].second <= inxy[l].second && inxy[l].second <= xy[i].second))
                        inside++;
                }
            }
            if (inside >= k)
                chmin(ret, abs(xy[i].first - xy[j].first) * abs(xy[i].second - xy[j].second));
        }
    }
    cout << ret << "\n";

    return 0;
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        UnionFind uf = new UnionFind(n);
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            int num = in.nextInt() - 1;
            p[i] = num;
        }
        for (int i = 0; i < m; i++) {
            uf.unite(in.nextInt() - 1, in.nextInt() - 1);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if(i == p[i] || uf.find(p[i]) == uf.find(i)) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

class UnionFind {
    int[] parent;
    int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(rank[x] < rank[y]) {
            parent[x] = y;
        }else {
            parent[y] = x;
            if(rank[x] == rank[y]) {
                rank[x] ++;
            }
        }
    }

    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    public void show() {
        for (int i = 0; i < parent.length; i++) {
            find(i);
        }
        System.out.println(Arrays.toString(parent));
    }
}

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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n;
char ch[5001];
string s,sam;

bool check(int k)
{
    int dem=1,vt=0;
    vector<pair<string,int> > a;
    string s1;
    for (int i=1;i<=k;++i)
    {
        char c=ch[i];
        s1.push_back(ch[i]);
    }
    a.push_back({s1,1});
    for (int i=k+1;i<=n;++i)
    {
        dem++;
        s1.erase(s1.begin());
        s1.push_back(ch[i]);
        a.push_back({s1,dem});
    }
    sort(a.begin(),a.end());
    while (vt<a.size())
    {
        int j=vt;
        while (vt<a.size()-1 && a[j].first==a[vt+1].first)
        {
            if (a[j].second+k<=a[vt+1].second)
                return true;
            vt++;
        }
        vt++;
    }
    return false;
}

void process()
{
    int l=1,r=n/2,mid,kq=0;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (check(mid))
        {
            l=mid+1;
            kq=mid;
        }
        else r=mid-1;
    }
    cout<<kq;
}

int main()
{
    scanf("%d",&n);
    cin>>s;
    s="1"+s;
    for (int i=1;i<=n;++i)
        ch[i]=s[i];
    process();
    return 0;
}


Measured memory_bytes: 6580
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))


a.sort()
if a[-1] < k:
    print('IMPOSSIBLE')
    sys.exit(0)

seta = set(a)
if k in seta:
    print('POSSIBLE')
    sys.exit(0)
change = True
while change:
    change = False
    setb = seta.copy()
    sorteda = sorted(seta)
    mini = sorteda[0] if sorteda[0] != 0 else sorteda[1]
    for i in range(1, len(sorteda)):
        setb.add(sorteda[i] % mini)
    if setb != seta:
        change = True
        seta = setb

mini = sorted(seta)[1]
a.reverse()

for i in a:
    if (k - i) % mini == 0:
        print('POSSIBLE')
        sys.exit(0)
print('IMPOSSIBLE')

Measured memory_bytes: 18664
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
const ll N = 200030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;

int main()
{

set<int> s;
int n;
cin>>n;
bool b=false;
rep(i,0,n)
{
	int y;
	cin>>y;
	if(s.find(y)!=s.end())
	b=true;
	s.insert(y);
}
if(b)
cout<<"NO";
else
cout<<"YES";



}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
// g++ Main.cpp -std=gnu++1y -O2 -I/opt/boost/gcc/include -o main && ./main
// g++ Main.cpp -std=gnu++1y -O2 -I/opt/boost/gcc/include -o main && ./main

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vll = vector<vl>;
using vii = vector<vi>;
using pii = pair<int, int>;

using vc = vector<char>;
using vcc = vector<vc>;
using vb = vector<bool>;
using vbb = vector<vb>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using vd = vector<double>;
using vdd = vector<vd>;

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i, a, b) for(int (i) = a; (i) < (b);(i)++)
#define MAX(a, b) ((a > b) ? a : b)
#define MIN(a, b) ((a > b) ? b : a)

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


const int MOD = 1e9 + 7;

vector<pii> prime_factorization(int n){ // 素因数分解をしたvector<素数, 指数>を返す
  vector<pii> res;
  int tmp, root_n = floor(sqrt(n));
  if(n % 2 == 0){
    tmp = 1;
    n /= 2;
    while(n % 2 == 0){
      n /= 2;
      tmp++;
    }
    res.push_back(make_pair(2, tmp));
  }
  ll i = 3;
  while(i <= root_n && i <= n){
    if(n % i == 0){
      tmp = 1;
      n /= i;
      while(n % i == 0){
        n /= i;
        tmp++;
      }
      res.push_back(make_pair(i, tmp));
    }
    i += 2;
  }
  if(n != 1) res.push_back(make_pair(n, 1));
  return res;
}
vector<pli> prime_factorization(ll n){ // 素因数分解をしたvector<素数, 指数>を返す
  vector<pli> res;
  int tmp, root_n = floor(sqrt(n));
  if(n % 2 == 0){
    tmp = 1;
    n /= 2;
    while(n % 2 == 0){
      n /= 2;
      tmp++;
    }
    res.push_back(make_pair(2, tmp));
  }
  ll i = 3;
  while(i <= root_n && i <= n){
    if(n % i == 0){
      tmp = 1;
      n /= i;
      while(n % i == 0){
        n /= i;
        tmp++;
      }
      res.push_back(make_pair(i, tmp));
    }
    i += 2;
  }
  if(n != 1) res.push_back(make_pair(n, 1));
  return res;
}

// n は 2以上の素数表を返す
vb Primes(int n){
  vector<bool> res(n + 1, true);
  res.at(0) = false; res.at(1) = false;
  for(int i = 2; i <= sqrt(n); i++){
    if(res.at(i)){
      for(int j = 2 * i; j <= n; j += i){
        res.at(j) = false;
      }
    }
  }
  return res;
}
// ===================================================

ll power_mod(ll k, int n, int mod){
  if(n == 0) return 1;
  ll tmp = power_mod(k, n / 2, mod);
  tmp = (tmp * tmp) % mod;
  if(n % 2 == 0) return tmp;
  return (k * tmp) % mod;
}


int main(){
  int n; cin >> n;
  vi A(n); REP(i, n) cin >> A.at(i);
  sort(A.begin(), A.end());
  if(n % 2 == 0){ // case 1 : n is even
    for(int i = 0; i < n; i++){
      if((i / 2) * 2 + 1 != A.at(i)){
        cout << 0 << endl;
        return 0;
      }
    }
  }
  else{ // case 2 : n is odd
    for(int i = 0; i < n; i++){
      if( ((i + 1) / 2) * 2 != A.at(i)){
        cout << 0 << endl;
        return 0;
      }
    }
  }
  cout << power_mod(2, n / 2, MOD) << endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define int long long
#define rep(i,N) for(int i=0;i<(N);i++)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;

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

__attribute__ ((constructor))
void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
}

signed main(){
    ll x;
    cin >> x;
    ll a = x / 11;
    if(11*a != x){
        if(x-11*a<=6)
            cout << a*2 + 1 << endl;
        else
            cout << a*2 + 2 << endl;
    }else
        cout << a*2 << endl;
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N + 1);
  a.push_back(-1);  // dummy for one-based.
  for (int i = 1; i <= N; ++i) cin >> a[i];
  int now = 1, len = 0;
  while (true) {
    if (now == -1) {  // found loop.
      len = -1;
      break;
    }
    if (now == 2) break;
    int next = a[now];
    a[now] = -1;  // visited.
    now = next;
    ++len;
  }
  cout << len << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;


//ABC043_b
//空文字列ならなにも行わない
int main(){
  string S;
  cin >> S;

  string res = "";

  REP(i,S.size())
  {
    if(S[i] == 'B')
    {
      //空文字列ならなにも行わない
      if(res.size() == 0)continue;

      string tmp = "";
      REP(i, res.size() -1)
      {
        tmp += res[i];
      }
      res = tmp;
    }
    else
    {
      res += S[i];
    }
  }

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
long long sum[100010];
int a[100010];
int n;
long long ans;
int main(){
	scanf("%d",&n);
	for (int i=0;i<=n;i++) scanf("%d",&a[i]);
	long long s=1;
	sum[n+1]=0;
	for (int i=n;i>=0;i--) sum[i]=sum[i+1]+a[i];
	for (int i=0;i<=n;i++)
	{
		if (s<=sum[i]) ans+=s;
		else ans+=sum[i];
		s-=a[i];
		if (s<0)
		{
			printf("-1\n");
			return 0;
		}
		s=s+s;
		if (s>=1e13) s=1e13;
	}
	 printf("%lld\n",ans);
}

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

int main()
{

int X;
cin >> X;

if  ( X<=599 ){  
 cout<<'8'<<endl;
}
 if  (600<=X  && X<=799 ){  
 cout<<'7'<<endl;
}
 if (800<=X  && X<=999 ){    
 cout<<'6'<<endl;
}
if (1000<=X  && X<=1199){
 cout<<'5'<<endl;
}
 if(1200<=X  && X<=1399 ){  
 cout<<'4'<<endl;
}
 if (1400<=X  && X<=1599 ){  
 cout<<'3'<<endl;
}
 if (1600<=X && X<=1799 ){  
 cout<<'2'<<endl;
}
else if (1800<=X && X<=1999 ){  
 cout<<'1'<<endl;}     
}

Measured memory_bytes: 3592
a=input()
b=input()
c=len(a)
d=len(b)
x=""
if c<=d:
  for i in range(c):
    x=x+a[i]
    x=x+b[i]
  print(x)
if c>d:
  for i in range(d):
    x=x+a[i]
    x=x+b[i]
  x=x+a[len(a)-1]
  print(x)

Measured memory_bytes: 9068
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
#include <list>
#include<numeric>
//AtCoderC++.cpp

using namespace std;

inline int ceiling(int n, int d) {
	return n % d == 0 ? n / d : n / d + 1;
}

int main() {
	string S; cin >> S;
	auto f = S.find('A');
	auto e = S.find_last_of('Z');
	cout << e - f + 1 << endl;
}


Measured memory_bytes: 640
ls = gets.split(" ").map(&:to_i)
#p ls
s_count = 0
f_count = 0

for i in 0..2 do
  if ls[i] == 5
    f_count += 1
  end
  if ls[i] == 7
    s_count += 1
  end
end

if f_count == 2 && s_count == 1
  print("YES\n")
else
  print("NO\n")
end


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

ll fact(ll num){
    ll ret = 1;
    const ll MOD = 1000000007;
    rep1(i, num+1) ret = ((ret%MOD) * i) % MOD;
    
    return ret;
}

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

    ll n, m;
    cin >> n >> m;
    
    if(abs(n-m) > 1){
        cout << 0 << endl;
        return 0;
    }

    const ll MOD = 1000000007;
    ll res = (fact(n) * fact(m)) % MOD;

    if(n==m) res = res * 2 % MOD;
    cout << res << endl;

    return 0;
}

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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define SORT_ASC(c) sort((c).begin(), (c).end())
#define SORT_DESC(c) sort((c).begin(), (c).end(), greater<typeof((c).begin())>())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

void Main()
{
	int n,m;
	cin >> n >> m;
	vector<int> a(m);
	vector<int> b(m);
	vector<vector<int>> c(m);

	REP(i,m){
		cin >> a[i] >> b[i];
		c[i].resize(b[i]);
		REP(j,b[i]){
			cin >> c[i][j];
			c[i][j]--;
		}
	}

	vector<vector<int>> dp(m);
	REP(i,m){
		dp[i].resize(10000);
		REP(j,10000){
			dp[i][j] = 1000000009;
		}
	}
	
	//cerr <<"test"<<endl;
	dp[0][0] = 0;
	int key = 0;
	REP(j,b[0]){
		key += 1<<c[0][j];
	}
	dp[0][key] = a[0];



	for(int i=1;i<m;i++){
		int key = 0;
		REP(j,b[i]){
			key += 1<<c[i][j];
		}
		//dump(i)
		//dump(key)
		REP(j,10000){
			dp[i][j] = dp[i-1][j];
		}
		REP(j,10000){
			//if(j==1){
			//	dump(j)
			//	dump(j|key)
			//}
			dp[i][j|key] = min(dp[i][j|key] , dp[i-1][j] + a[i]);
		}
		//REP(k,8){
		//	dump(dp[i][k])
		//}
	}

	int t=0;
	REP(i,n){
		t += 1<<i;
	}
	if(dp[m-1][t] == 1000000009){
		cout << -1 << endl;
	}
	else{
		cout << dp[m-1][t] << endl;
	}

	return;
}

int main()
{
	//cin.tie(nullptr);
	//ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

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

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

	vector<ll> w(W+1);

	while (N--) {
		ll wi, vi;
		cin >> wi >> vi;
		for (ll x = W-wi; x >= 0; --x)
			w[x+wi] = max(w[x+wi], w[x] + vi);
	}
	
	cout << *max_element(w.begin(), w.end()) << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()

#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)

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

vector<int> primes;

#define MAX 300000

void calcprimes()
{
	for (int n = 2; n < MAX; n++) {
		if (!(n%7 == 1 || n%7 == 6)) continue;
		bool prime = true;
		for (int d = 2; d*d <= n; d++) {
			if (!(d%7 == 1 || d%7 == 6)) continue;
			if (n%d == 0) {
				prime = false;
				break;
			}
		}
		if (prime)
			primes.push_back(n);
	}
}

int main(void)
{
	int n;
	calcprimes();
	while (cin >> n, n != 1) {
		int t = n;
		printf("%d:", t);
		rep(i, primes.size()) {
			int d = primes[i];
			if (!(d <= t)) break;
			if (t%d==0)
				printf(" %d", d);
		}
		puts("");
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  double x;
  string u;

  double ans = 0;

  for (int i = 0; i < N; i++) {
    cin >> x >> u;
    if (u == "JPY") ans += x;
    else ans += x * 380000.0;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import math
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
S=[''.join(sorted(input())) for _ in range(N)]
S.sort()

r=1
ans=0

for i in range(1,N):
    if(S[i-1]==S[i]):
        r+=1
    elif(r>1):
        ans+=math.factorial(r)//(math.factorial(r-2)*math.factorial(2))
        r=1

if(r>1):
    ans+=math.factorial(r)//(math.factorial(r-2)*math.factorial(2))

print(ans)


Measured memory_bytes: 11512
A,B,K=map(int,input().split())
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
        return divisor_list
C=gcd(A,B)
D=make_divisor_list(C)
D.sort()
D.reverse()
print(D[K-1])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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;i >= n;i--)
#define INF 999999

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b, k;
	cin >> a >> b >> k;
	if (a+k>b || b-a+1<2*k){
		REP(i, b-a+1){
			cout << a+i << endl;
		} return  0;
	}
	REP(i, k){
		cout << a+i << endl;
	}
	REPR(i, k){
		cout << b-i << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << ", " << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define f first
#define s second
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a * c, a * d, b * c, b * d});
}

Measured memory_bytes: 3648
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)


Measured memory_bytes: 121436
program main;
var b : array[1..200000] of longint;
    n,i,l : longint;
begin
    readln(n);
    for i := 1 to n do
        b[i]:=0;
    for i := 1 to n-1 do begin
        read(l);
        inc(b[l]);
    end;
    for i := 1 to n do
        writeln(b[i]);
end.

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9 + 7;

int now[100010];

int main(void){
  int n;
  fill(now,now+100010,-1);
  cin >> n;
  int res = 0;
  for(int i = 0;i < n;++i){
    int a;
    cin >> a;
    int ok = res;
    int ng = -1;
    while(abs(ok - ng) > 1){
      int mid = (ok + ng)/2;
      if(now[mid] < a){
        ok = mid;
      }else{
        ng = mid;
      }
    }
    if(ok == res){
      ++res;
    }
    now[ok] = a;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 640
from operator import itemgetter
from sys import stdin

n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]

for i in range(n):
	data[i].append(int(i+1))
    
for j in range(n):
	data[j][1]= int(data[j][1])

data2 = sorted(data, key=itemgetter(1),reverse=True)
data3 = sorted(data2, key=itemgetter(0))
for k in range(n):
	print(data3[k][2])


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


int main() {
	
	string s;
	cin >> s;
	int len = s.length();
	
	int i=0;
	while(1){
		bool flag = 1;
		s.pop_back();
		s.pop_back();
		i+=2;
		
		for(int j=0; j<(len-i)/2; j++){
			if(s.at(j) != s.at(j+(len-i)/2)) {
				flag = 0;
			}
		}
		
		if (flag) {
			cout << len - i << endl;
			break;
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	if(n>=m){
		cout << "0" << endl;
		return 0;
	}

	vector<int> x(m);
	vector<int> a; 
	rep(i,m) cin >> x[i]; 
	sort(all(x));
	loop(i, 1, m){
		a.push_back(x[i]-x[i-1]);
	}
	sort(all(a), greater<int>());
	lli sum = *max_element(all(x)) - *min_element(all(x));
	lli big=0;
	rep(i,n-1){
		big += a[i];
	}
	cout << sum - big << endl;
	return 0;
}

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

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

bool is(int x) {
	int rt=int(sqrt(x)+1e-6);
	return rt*rt==x;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n,d; cin>>n>>d;
	int a[n][d];
	for (int i=0; i<n; i++)
		for (int j=0; j<d; j++)
			cin>>a[i][j];
	int ret=0;
	for (int i=0; i<n; i++)
		for (int j=i+1; j<n; j++) {
			int cur=0;
			for (int k=0; k<d; k++) {
				int d=a[i][k]-a[j][k];
				cur+=d*d;
			}
			if(is(cur)) ret++;
		}
	cout<<ret<<"\n";
	return 0;
}

Measured memory_bytes: 256
//Mitesh Agrawal
#include <bits/stdc++.h>
using namespace std;
 
#define next _next
 
int next[200005][26], mini[26], l;
int dp[200005];
int ans[200005];

int find(int idx){
	if(idx == l + 1)
		return dp[idx] = 0;
	if(dp[idx] != 0)
		return dp[idx];
	dp[idx] = 1 + find(next[idx][0]);
	ans[idx] = 0;
	for(int i = 1; i < 26; i++){
		if(find(next[idx][i]) + 1 < dp[idx]){
			dp[idx] = 1 + find(next[idx][i]);
			ans[idx] = i;
		}
	}
	return dp[idx];
}
 
int main(){
	int i, j, k, m;
	string s, t;
	cin >> s;
	l = s.size();
	for(i = 0; i < 26; i++)
		mini[i] = l + 1;
	for(i = l - 1; i >= -1; i--){
		for(j = 0; j < 26; j++)
			next[i + 1][j] = mini[j];
		if(i >= 0)
			mini[s[i] - 'a'] = i + 1;
	} 
    int it = 0;
    while(1){
    	if(!find(it))
    		break;
    	printf("%c", ans[it] + 'a');
    	it = next[it][ans[it]];
    }
    return 0;
}

Measured memory_bytes: 22660
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    N = input_int()
    h_list = LII_split()

    dp = [-1 for _ in range(N)]
    dp[0] = 0  #

    for i in range(N - 1):

        cost_1 = dp[i] + abs(h_list[i] - h_list[i + 1])
        if dp[i + 1] == -1 or dp[i + 1] > cost_1:
            dp[i + 1] = cost_1

        if i < N - 2:
            cost_2 = dp[i] + abs(h_list[i] - h_list[i + 2])
            if dp[i + 2] == -1 or dp[i + 2] > cost_2:
                dp[i + 2] = cost_2
    print(dp[N - 1])

resolve()

Measured memory_bytes: 20900
#include <bits/stdc++.h>
using namespace std;
//FAZAL_AHMAD
#define rep(i,a,b) for(long long i = (a); i < (b); i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define pb push_back
using ll = long long;

long long MOD=1e9+7;
ll lcm(ll a,ll b){

	return (a*b)/(__gcd(a,b));
}
vector<int> dp(2001,-1);
int helper(int s){
	
	if(dp[s]!=-1){
		return dp[s];
	}
	if(s==0){
		return 1;
	}
	ll ans=1;
	ll temp=0;
	for(int i=3;i<=s;i++){
		temp=(temp+helper(s-i))%MOD;
	}
	ans=ans*temp;
	dp[s]=ans;
	return ans;
}

void solve()
{
int s;
cin>>s;
cout<<helper(s);


}



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


		solve();
	cout<<endl;

}






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


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

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define w(x)  int x; cin>>x; while(x--)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define watch4(x,y,z,q) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<" and "<<(#q)<<" is "<<(q)<<"\n"
#define MOD 1000000007
#define INF 1000000007;
#define F first
#define S second
#define pb(x) push_back(x);


#define ll  long long
#define all(c) (c).begin(),(c).end()
#define endl "\n"

typedef vector<int> vl;
typedef vector< vl > vvl;
typedef pair< int, int> pll;
typedef map< int, int> mll;


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif





void c_p_c()
{
#ifndef ONLINE_JUDGE
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void parray(int a[],int n){
    for(int i=0;i<n;i++){
    cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main() {
    int i,n,m,k,c=0,sum=0;
    c_p_c();
    // cout<<"the defufe";
    // cin>>n;
    // int temp = sqrt(n);
    // cout<<temp*temp<<endl;
    cin>>n>>m;

    if(m==100)
    	m++;
    if(n==0)
    	cout<<m<<endl;
    else{

    	cout<<m;
    	for (int i = 0; i < 2*n; ++i)
    	{
    		/* code */
    		cout<<0;
    	}
    	cout<<endl;
    }
    return 0;
}



Measured memory_bytes: 3632