akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007
bool range_validation(int y,int x,int h,int w){
    return y>=0 && y<h && x>=0 && x < w;
}
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n;
  ll k;
  
  cin >> n;
  cin >> k;
  
  ll count[100001] = {0LL};
  
  int a,b;
  REP(i,n){
    cin >> a >> b;
    count[a] += b;
  }
  ll num = 0;
  REP(i,100001){
    num += count[i];
    if(num >= k){
      cout << i << endl;
      break;
    }
  }
  
  return 0;
}


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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 100050;

int n, a[maxn], cnt[maxn], tmp[maxn], mx, ans, num, num2;
int id[maxn], id2[maxn];

bool cmp(int a, int b){return cnt[a] > cnt[b];}
int main()
{
	sf("%d",&n);
	fo(i,1,n) sf("%d",&a[i]);
	for(int i = 1; i <= n; i += 2) cnt[a[i]] ++, num ++;
	fo(i,1,maxn-1) id[i] = i;
	sort(id+1, id+maxn-1+1, cmp);
	fo(i,1,maxn-1) {tmp[i] = cnt[i]; cnt[i] = 0;}
	for(int i = 2; i <= n; i += 2) cnt[a[i]] ++, num2 ++;
	fo(i,1,maxn-1) id2[i] = i;
	sort(id2+1, id2+maxn-1+1, cmp);
	ans = inf;
	fo(i,1,2) fo(j,1,2) if(id[i] != id2[j]) gmin(ans, num-tmp[id[i]]+num2-cnt[id2[j]]);
	pf("%d\n",ans);	
}

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

int main()
{
    int N,Y;
    cin >> N >> Y;
    int flag=0;
    for(int i=0;i<=N;i++){
        for(int j=0;i+j<=N;j++){
            int k=N-i-j;
            if(10000*i+5000*j+1000*k==Y){
                flag=1;
            }
            if(flag){
                cout << i << " " << j << " " << k << endl;
                break;
            }
        }
        if(flag){
            break;
        }        
    }
    if(!flag){
        cout << "-1 -1 -1\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 10e15+9
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, p, q;
int k, a, b;

int main(){
	while (cin >> n >> p >> q&&n + p + q){
		p = p / 100 * 60 + p % 100, q = q / 100 * 60 + q % 100;
		vector<bool> v(q - p);
		vector< vector<bool> > vv(n, v);
		REP(i, n){
			cin >> k;
			REP(j, k){
				cin >> a >> b;
				a = a / 100 * 60 + a % 100, b = b / 100 * 60 + b % 100;
				a -= p;
				b -= p;
				FOR(l, a, b){
					vv[i][l] = 1;
				}
			}
		}
		FOR(i, 1, n){
			REP(j, vv[0].size()){
				vv[0][j] = vv[0][j] && vv[i][j];
			}
		}
		int ans = 0, cnt = 0;
		REP(i, vv[0].size()){
			if (vv[0][i] == 0)	cnt++;
			else{
				ans = max(ans, cnt);
				cnt = 0;
			}
		}
		ans = max(ans, cnt);
		cout << ans << endl;
	}
}

Measured memory_bytes: 1208
#include <iostream>
#include <vector>

using namespace std;

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

	return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

int main(){
  int N;
  LINT x;
  cin>>N>>x;
  LINT a[N];
  REP(i, N)cin>>a[i];
  LINT cost[N][N]; //b_i(k)
  LINT ans=0, sum;
  REP(i, N) {
    cost[i][0]=a[i];
    ans += a[i];
  }

  for(int k=1; k<N; ++k){
    REP(i, N){
      cost[i][k]=min(cost[i][k-1], a[(N+i-k)%N]);
    }
    sum=0;
    REP(i, N) {
      sum += cost[i][k];
    }
    sum += k*x;
    ans = min(ans, sum);
  }
  cout<<ans<<endl;


  return 0;
}


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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0]*(N+1)

    b = 0
    for i, a in enumerate(A):
        b += a - 1
        b %= K
        B[i+1] = b

    Q = {}
    X = 0

    for i, b in enumerate(B):
        if i>=K:
            Q[B[i-K]] -= 1

        if b in Q:
            X += Q[b]
            Q[b] += 1
        else:
            Q[b] = 1

    print(X)


if __name__ == '__main__':
    main()


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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<llong int, int> P;
typedef struct data{
	int now;
	int cost;
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};


int main(){
	llong int n, h;
	vector<P> atack;
	cin >> n >> h;
	for(llong int i = 0; i < n; i++){
		llong int a, b;
		cin >> a >> b;
		atack.pb(P(a,0));
		atack.pb(P(b,1));
	}
	sort(atack.begin(), atack.end(), greater<P>());
	llong int ans = 0, sum = 0, index = 0;
	while(sum < h){
		if(atack[index].second == 1){
			ans++;
			sum += atack[index].first;
			index++;
		}else if(atack[index].second == 0){
			ans += (h-sum)/atack[index].first + ((h-sum)%atack[index].first?1:0);
			sum = h+1;
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;

    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }

    return 0;
}


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

public class Main{ 
	
	static class FastReader{ 
		BufferedReader br; 
		StringTokenizer st; 

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

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

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

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

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

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

	public static void main(String[] args) 
	{ 
        FastReader sc = new FastReader(); 
        //PrintWriter out = new PrintWriter(System.out); 

        char[] a = sc.nextLine().toCharArray();
        char[] b = sc.nextLine().toCharArray();

        int[][] dp = new int[a.length+1][b.length+1];

        for(int i=1;i<=a.length;i++){
        	for(int j=1;j<=b.length;j++){
        		if(a[i-1]==b[j-1])
        			dp[i][j] = dp[i-1][j-1]+1;
        		else
        			dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        	}
        }

        int x = a.length, y = b.length;
        StringBuilder ans = new StringBuilder();
        //dp[x][y];
        while(x>0 && y>0){
        	if(a[x-1] == b[y-1]){
        		ans.append(""+a[x-1]);
        		x--;
        		y--;
        	}
        	else{
        		if(dp[x][y]==dp[x-1][y]) x--;
	        	 else y--;
        	}
        }

        System.out.println(ans.reverse().toString());
        
	}
}


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

bool is_minus(long i) {
	return (i < 0);
}

int main()
{
	//input
	int N; cin >> N;
	vector<long> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	vector<long> B;

	//compute
	long long ans = 0;
	size_t n_count = count_if(A.begin(), A.end(), is_minus);

	if (n_count % 2 == 0) {
		for (int i = 0; i < N; i++) {
			ans = ans + abs(A[i]);
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			ans = ans + abs(A[i]);
			B.push_back(abs(A[i]));
		}
		long min = *min_element(B.begin(), B.end());
		ans = ans - 2 * min;
	}

	//output
	cout << ans << endl;
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> b( n-1 );
    int C=0;
    for(int i=0 ; i<n-1 ; i++)
    {
        cin>>b[i];

    }
    C+=( b[0] + b[n-2] );
    for(int i=1;  i<n-1 ; i++)
    {
        C+=min( b[i] , b[i-1] );
    }
    cout<<C<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<=(n);++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const double Pi = acos(-1);
const ll mod=1e9+7;

int main(){
    ll n;
    cin >>n;
    ll a;
    ll ans = 1;
    double l=0;
    rep(i,n) {
        cin >>a;
        ans *= a;
        l += log10(double(a));
        if(ans>1000000000000000000 || l>18){
            ans=-1;
        }
    }
    if(ans<0) ans=-1;
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 3976
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

vll dx = {1, 0, -1, 0};
vll dy = {0, 1, 0, -1};

ll mod = 1e9 + 7;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k;
    cin >> n >> k;
    vll a(n);
    REP(i, n) cin >> a[i];

    vll mem(n);
    REP(i, n){
        REP(j, n){
            if(a[i] < a[j]) mem[i]++;
        }
    }
    ll res = 0;
    REP(i, n){
        for(ll j = i + 1; j < n; j++){
            if(a[i] > a[j]){
                res++;
            }
        }
    }
    res *= k;
    res %= mod;

    vll tmp(n);
    REP(i, n){
        tmp[i] = ((((k * (k - 1)) / 2) % mod) * mem[i]) % mod;
    }
    REP(i, n){
        res += tmp[i];
        res %= mod;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;

ll d[100001],f[100001];//d 全て
signed main() {
	int a, b; cin >> a >> b;
	ll s = 0;
	for (int c = 0; c < a; c++) {
		int e;
		cin >> e;
		f[c + 1] = f[c] + max(0, e);
		d[c + 1] = d[c] + e;
	}
	ll MAX = 0;
	for (int i = 0; i <=a-b; i++) {
		MAX = max(MAX, f[a] - ((f[i + b] - f[i]) - max((ll)0, d[i + b] - d[i])));
	}
	cout << MAX << endl;
}

Measured memory_bytes: 1920
def solve():
    N, X = [int(_) for _ in raw_input().split()]
    L = [int(_) for _ in raw_input().split()]
    ans = 1
    D = 0
    for i in range(N):
        D += L[i]
        if D > X:
            break
        else:
            ans += 1
    print ans

if __name__ == '__main__':
    solve()


Measured memory_bytes: 28012
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

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

int dp[12][100010];
int solve(int N, VI& d, VI& p, int X){
  fill((int*)dp, (int*)dp+11*100010, -1);
  dp[0][0] = 0;
  REP(i,N){
	REP(x,X+1){
	  if(dp[i][x] < 0) continue;
	  dp[i+1][x] = max(dp[i+1][x], dp[i][x]);
	  
	  for(int tx=x,j=0;tx<=X;tx+=p[i],++j){
		dp[i+1][tx] = max(dp[i+1][tx], dp[i][x]+d[i]*j);
	  }
	}
  }
  
  return dp[N][X];
}

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

  int N, D, X; cin >> N >> D >> X;
  VVI p(D, VI(N));
  REP(d,D) REP(i,N) cin >> p[d][i];
  REP(d,D) p[d].PB(1);

  REP(d,D-1){
	X = solve(N+1, p[d+1], p[d], X);
  }
  cout << X << endl;
  
  return 0;
}

Measured memory_bytes: 5616
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        int num3 = sc.nextInt();
        int total = sc.nextInt();
        int result = 0;

        for(int i = 0; i <= num1; i++) {
            for(int j = 0; j <= num2; j++) {
                for(int k = 0; k <= num3; k++) {
                	if (500 * i + 100 * j + 50 * k == total) {
                		result++;
                	}
                }
            }
        }
        System.out.println(result);
    }
}

Measured memory_bytes: 22996
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
bool solve(void){
	string S,T,U;
	cin>>S;if(S=="0"){return false;}
	cin>>T>>U;
	REV(S);REV(T);REV(U);
	//繰り上がりは0か1か
	llint dp=1,ep=0;
	for(int i=0;i<S.size();i++){
		llint ddp=0,eep=0;
		for(int x=0;x<10;x++){
			if(S[i]!='?'&&S[i]-'0'!=x){continue;}
			if(i+1==S.size()&&x==0){continue;}
			for(int y=0;y<10;y++){
				if(T[i]!='?'&&T[i]-'0'!=y){continue;}
				if(i+1==T.size()&&y==0){continue;}
				int ds=(x+y)%10;
				if(U[i]=='?'||U[i]-'0'==ds){
					if(x+y>=10){eep+=dp;}
					else{ddp+=dp;}
				}
				int es=(x+y+1)%10;
				if(U[i]=='?'||U[i]-'0'==es){
					if(x+y+1>=10){eep+=ep;}
					else{ddp+=ep;}
				}
			}
		}
		dp=ddp%mod;
		ep=eep%mod;
		//cerr<<dp<<" "<<ep<<endl;
	}
	cout<<dp<<endl;
	return true;
}

int main(void){
	while(solve()){}
	return 0;
}


Measured memory_bytes: 3084
#include<iostream>

int main()
{
	double V,y;

	while(std::cin>> V)
	{
		y=V*V/19.6;

		for(int i=0;;++i)
		{
			if(5*i-5>=y)
			{
				std::cout << i << '\n';
				break;
			}
		}
	}
}

Measured memory_bytes: 1224
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){

  int n,p,i;

  while(1){
    cin >> n >>p;
    if(n+p==0) break;
    int candidate[n],bowl;

    //init 
    for(i=0;i<n;i++) candidate[i]=0;
    bowl = p;

    for(i=0; i<1000000; i++){
      if(bowl > 0){
	candidate[i%n]++;
	bowl--;
      }else{
	bowl=candidate[i%n];
	candidate[i%n]=0;
      }
      if(candidate[i%n]==p) break;
    }
    printf("%d\n",i%n);
  }
  return 0;
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;    
lli hsh[1000004];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n,temp1,temp2,t,x,y,m,k,a,b,c,temp;
	
	cin>>n;
	
	vector<lli >v(n);
	
	for(int i =0;i<n;i++)
	{
		cin>>v[i];
		hsh[v[i]]++;
	}
	
	int count =0;
	for(int i =0;i<n;i++)
	{
		
			int sqr=sqrt(v[i]);
			bool yes=true;
			
			for(int j =1;j<=sqr;j++)
			{
				if(v[i]%j==0)
				{
					if(hsh[j]!=0)
					{
						if(j==v[i])
						{
							if(hsh[j]>1)
							{
								yes = false;
								break;	
							}
						}
						else
						{
							yes=false;
							break;
						}
					}
					if(hsh[v[i]/j]!=0)
					{
						if(v[i]/j==v[i])
						{
							if(hsh[v[i]/j]>1)
							{
								yes = false;
								break;	
							}
						}
						else
						{
							yes=false;
							break;
						}
					}
				}
			}
			if(yes)
			{
			
				count++;
			}
		}
		
		cout<<count;
	}
	
	

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

typedef long long ll;
typedef vector < int > vi;
typedef pair <int , int > pi;

#define F first
#define S second
#define pb push_back
#define mp make_pair
#define fr(i,a,b) for(int i=a;i<b;i++)


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int count=2;
    ll max=arr[n-1];
    int i=2;
    while(count<n&&n-count>1)
    {
        max+=2*arr[n-i];
        count+=2;i++;
    }
    if(n-count==1)
    {
        max+=arr[n-i];
    }
    cout<<max;
    
    
    return 0;
}


Measured memory_bytes: 4428
#include <bits/stdc++.h>
using namespace std;
int main(){
    long double n,m,d;
    cin >> n >> m >> d;
    long double oaite = 2*(n-d);
    if(d==0) cout << setprecision(20) << (m-1)/(n) << endl;
    else  cout << setprecision(20) << (oaite*(m-1))/(n*n) << endl;
}

Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> hs(N);
  for(int i = 0; i < N; ++i) {
    cin >> hs[i];
  }
  sort(hs.begin(), hs.end());
  ll mn = 1e10;
  for(int i = 0; i + K - 1 < N; ++i) {
    chmin(mn, hs[i + K - 1] - hs[i]);
  }
  cout << mn << endl;
  return 0;
}

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

// https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

int keta = 3;

string fill0(int num, int keta) {
	ios::fmtflags curret_flag = cout.flags();

	ostringstream ss;
	ss << setw(keta) << setfill('0') << num;
	string s(ss.str());
	cout.flags(curret_flag);
  return s;
}

bool f(string &s, string &digit) {
  int cur = 0;
  for(char c : s) {
    if(c == digit[cur]) {
      cur++;
    }
    if(cur >= digit.size()) {
      return true;
    }
  }
  return false;
}

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  int ans = 0;
  for(int i=0;i<1000;i++) {
    string digit = fill0(i, keta);
    if(f(s, digit)) ans++;
  }

  cout << ans << endl;
  return 0;
}


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

using namespace std;

#define int long long
#define tie() ios_base :: sync_with_stdio(0); cin.tie(0) ; cout.tie(0)
#define err(x) cerr << #x << " is : " << x << endl
#define mem(a , v)   memset(a , v , sizeof a)
#define all(v) v.begin() , v.end()

const int N = 1e5 + 20;
const int mod = 1e9 + 7;

int32_t main()
{
      tie();
      int t = 1;
      //cin >> t;
      while(t--)
      {
            int n , a , b;
            cin >> n >> a >> b;
            if((a + b) == 0)
            {
                  cout << 0 << endl;
                  return 0;
            }
            int whole = (n / (a + b)) * a , some = min(a , (n % (a + b)));
            cout << whole + some << endl;
      }
      return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    vector<int> way;
    int N;
    cin >> N;
    way.push_back(0);
    for(int i =0; i < N; i++){
        int tmp;
        cin >> tmp;
        way.push_back(tmp);
    }
    way.push_back(0);
    N = N+2;

    long sum = 0;;
    for(int i =0; i < N+1; i++){
        sum += abs(way[i] - way[i+1]);
    }
    

    for(int i = 1; i < N-1 ; i++){
        //        cout << sum << "-" << abs( way[i] - way[i-1]) << "-" << abs(way[i] - way[i+1]) << "+" <<  way[i] <<endl;
        cout << sum - abs( way[i] - way[i-1]) - abs(way[i] - way[i+1]) + abs(way[i-1] - way[i+1]) << endl;
    }
    return 0;
}


Measured memory_bytes: 3832
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <deque>
using namespace std;

#define rep(i, n) for (int i=0; i<int(n); i++)
using ll = long long;
ll cnt[100001];


int main() {
	int n;
	ll k;
	cin >> n >> k;
	rep(i, n) {
		int a;
		int b;
		cin >> a >> b;
		cnt[a] += b;
	}
	for (int x=1; x<=100000; x++) {
		if (k<=cnt[x]) {
			cout << x << endl;
			break;
		}
		k -= cnt[x];
	}
	return 0;
}

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


par = [-1]*(n)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
      if par[x] > par[y]:x,y = y,x
      par[x] += par[y]
      par[y] = x
def size(x):
    return -par[find(x)]


for i in range(m):
  x,y,z = map(int,input().split())
  unite(x-1,y-1)


ans = 0
# print(par)
for i in range(n):
  if par[i] <0:
    ans += 1
print(ans)

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

int main(){
  int N,A,B;
  cin>>N>>A>>B;
  bool ans =true;
  for(int i=A;i<=B;i++){
    if(i%N==0){
      ans=false;
      cout<<"OK"<<endl;
      break;
    }
  }
  if(ans){
    cout<<"NG"<<endl;
  }
}

Measured memory_bytes: 3552
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 100000;
int main(){
    
    
    int n;
    ll ans=0;
    vector<vector<ll>>  v(maxn);
    vector<string> vs;
    
    cin >> n;
    
    rep(i,n){
        string s;
        cin >> s;
        vs.push_back(s);
    }
    
    rep(i,n){
        string s = vs[i];
        rep(j,s.size()){
            v[i].push_back((int)s[j]-(int)'a');
        }
        sort(all(v[i]));
    }
    
    sort(all(v));
    reverse(all(v));
    vector<ll> t;
    t = v[0];
    ll streak=1;
    
    rep(i,n){
        if(i>0){
            if(t==v[i]){
                streak++;
            }else{
                ans+=streak*(streak-1)/2;
                streak=1;
                t=v[i];
            }
        }
    }
    
    ans+=streak*(streak-1)/2;
    
    cout << ans<<endl;
    
    return 0;
}


Measured memory_bytes: 23668
#include <iostream>
using namespace std;
int main(void){
    
    int N,i,j,count = 0;
    cin >> N;
    
    long long int A[N];
    for(i = 0; i < N; i++){
        cin >> A[i];
    }
    
    for(i = 0; i < 10000; i++){
        for(j = 0; j < N; j++){
            if(A[j] % 2 == 1){
                cout << count << endl;
                return 0;
            }
            A[j] = A[j] / 2;
        }
        count ++;
    }
    return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	var N int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &N)

	var sum float32
	for i := 0; i < N; i++ {
		var c float32
		var str string
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%f %s", &c, &str)
		if str == "JPY" {
			sum = sum + c
		} else {
			sum = sum + c*380000.0
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef struct cc
{
	int a,b,c;
};
typedef pair<int,cc>CP;

cc cst(int a,int b,int c)
{
	cc x;
	x.a=a;
	x.b=b;
	x.c=c;
	return x;
}

int main()
{
	int A,B,C;
	cin>>A>>B>>C;
	int t=0;
	while(true)
	{
		if(A==B&&B==C)
		{
			cout<<t<<endl;
			return 0;
		}
		t++;
		if(A==B&&C<A)
		{
			C+=2;
		}
		else if(B==C&&A<C)
		{
			A+=2;
		}
		else if(C==A&&B<C)
		{
			B+=2;
		}
		else if(A>B&&A>C)
		{
			B++;C++;
		}
		else if(B>A&&B>C)
		{
			A++;C++;
		}
		else
		{
			A++;B++;
		}
	}
}

Measured memory_bytes: 256
import sys

H, W = map(int, input().split())
s_list = [list(input()) for _ in range(H)]


def judge_black(y, x):
    if 0 <= y - 1 < H:
        if s_list[y - 1][x] == '#':
            return True
    if 0 <= x - 1 < W:
        if s_list[y][x - 1] == '#':
            return True
    if 0 <= x + 1 < W:
        if s_list[y][x + 1] == '#':
            return True
    if 0 <= y + 1 < H:
        if s_list[y + 1][x] == '#':
            return True
    return False


for i in range(H):
    for j in range(W):
        if s_list[i][j] == '#':
            if judge_black(i, j) is False:
                print('No')
                sys.exit()
print('Yes')


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
using namespace std;

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

long long calc(long long N, long long A, long long B, long long C, long long D, map<long long, long long>& mp)
{
    if(N == 1) return D;
    if(mp.count(N)) return mp[N];

    long long y, t;
    mp[N] = 1e+18;
    if(1e+18/D > N) mp[N] = N*D;

    for(t = 0, y = N; y%2 != 0; ++y, ++t);
    mp[N] = min(mp[N], (y/2? calc(y/2, A, B, C, D, mp)+A: 0) + t*D);
    for(t = 0, y = N; y%2 != 0; --y, ++t);
    mp[N] = min(mp[N], (y/2? calc(y/2, A, B, C, D, mp)+A: 0) + t*D);

    for(t = 0, y = N; y%3 != 0; ++y, ++t);
    mp[N] = min(mp[N], (y/3? calc(y/3, A, B, C, D, mp)+B: 0) + t*D);
    for(t = 0, y = N; y%3 != 0; --y, ++t);
    mp[N] = min(mp[N], (y/3? calc(y/3, A, B, C, D, mp)+B: 0) + t*D);

    for(t = 0, y = N; y%5 != 0; ++y, ++t);
    mp[N] = min(mp[N], (y/5? calc(y/5, A, B, C, D, mp)+C: 0) + t*D);
    for(t = 0, y = N; y%5 != 0; --y, ++t);
    mp[N] = min(mp[N], (y/5? calc(y/5, A, B, C, D, mp)+C: 0) + t*D);

    return mp[N];
}

int main()
{
    int T;
    cin >> T;

    while(T--){
        long long N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;

        map<long long, long long> mp;
        cout << calc(N, A, B, C, D, mp) << endl;
    }

    return 0;
}

Measured memory_bytes: 4324
# abc 158
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

A, B = map(int, readline().split())


answer = -1
for i in range(1, 2000): # 2000は適当
    if int(i * 0.08) == A and int(i * 0.1) == B:
        answer = i
        break

print(answer)

Measured memory_bytes: 3060
#include <stdio.h>

int main () {

    int i, j, H, W;

    for (; ;) {
        scanf("%d", &H); scanf("%d", &W);
        if (H == 0 && W == 0)
            break;

        for (i = 1; i <= H; i++) {
            for (j = 1; j <= W; j++) {
                if (j > 1 && i > 1 && j < W && i < H) {
                    putchar('.');
                } else {
                    putchar('#');
                }
            }
            puts("");
        }
        
        puts("");

    }

    return 0;

}




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

int main() {
  int N, i;
  cin >> N;

  bool a = false;
  
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s; 
    
    if (s == "Y") {
      a = true;
      break;
    }
   } 
  
   if (a) {
     cout << "Four" << endl;
   }
  
   else {
     cout << "Three" << endl;
   }
}


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

int main() {
//    freopen("in.txt", "r", stdin);

    int N, W, vi, wi, m = -1;
    int f[10002] = {0};
    cin >> N >> W;

    for (int i = 0; i < N; ++i) {
        cin >> vi >> wi;
        for (int j = W; j >= 0; --j) {
            if (j >= wi) {f[j] = max(f[j], f[j - wi] + vi);}
            if (m < f[j]) {m = f[j];}
        }
    }

    cout << m << endl;
}

Measured memory_bytes: 3132
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
#define NUM ((long long)1000000007)
#define int unsigned long long

using namespace std;

int MyPow(int a, int b)
{
    int ans = 1;
    for (size_t i = 0; i < b; i++)
    {
        ans *= a;
    }
    return ans;
}

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

    int d, n;
    cin >> d >> n;

    if (d == 0 && n == 100)
    {
        cout << 101 << endl;
        return 0;
    }
    if (d == 1 && n == 100)
    {
        cout << 10100 << endl;
        return 0;
    }
    if (d == 2 && n == 100)
    {
        cout << 1010000 << endl;
        return 0;
    }
    cout << MyPow(100, d) * n << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ld eps = 1e-9;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
using State = string::const_iterator;
class ParseError {};
int expr(State &begin);
int term(State &begin);
int factor(State &begin);
int number(State &begin);
int expr(State &begin) {
  int ret = term(begin);
  if(*begin == '=') return ret;
  while(1) {
    if(*begin == '+') {
      begin++;
      ret += term(begin);
    } else if(*begin == '-') {
      begin++;
      ret -= term(begin);
    } else {
      break;
    }
  }
  return ret;
}
int term(State &begin) {
  int ret = factor(begin);
  if(*begin == '=') return ret;
  while(1) {
    if(*begin == '*') {
      begin++;
      ret *= factor(begin);
    } else if(*begin == '/') {
      begin++;
      ret /= factor(begin);
    } else {
      break;
    }
  }
  return ret;
}
int factor(State &begin) {
  int ret = 0;
  if(*begin == '=') return ret;
  if(*begin == '(') {
    begin++;
    ret = expr(begin);
    begin++;
  } else {
    ret = number(begin);
  }
  return ret;
}
int number(State &begin) {
  int ret = 0;
  if(*begin == '=') return ret;
  while(isdigit(*begin)) {
    ret *= 10;
    ret += *begin - '0';
    begin++;
  }
  return ret;
}
int main() {
  int n; cin >> n;
  cin.ignore();
  for(int i=0;i<n;++i) {
    string s;
    getline(cin, s);
    State begin = s.begin();
    int ans = expr(begin);
    cout << ans << endl;
  }
}



Measured memory_bytes: 3060
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int nxt[20][202020],nxnx[20][202020];
typedef long long ll;
int d[202020];
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)scanf("%d", &d[i]);
	for (int i = 0; i < 20; i++)
	{
		nxt[i][num] = num, nxnx[i][num] = num;
		for (int j = num - 1; j >= 0; j--)
		{
			if (d[j] & (1 << i))nxt[i][j] = j, nxnx[i][j] = nxt[i][j + 1];
			else nxt[i][j] = nxt[i][j + 1], nxnx[i][j] = nxnx[i][j + 1];
		}
	}
	ll ans = 0;
	for (int i = 0; i < num; i++)
	{
		int mini = 1010101010;
		for (int j = 0; j < 20; j++)mini = min(mini, nxnx[j][i]);
		ans += mini - i;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 32512
#include<iostream>

using namespace std;

int main()
{
	int n;
	int *a;
	long long ans = 0;

	cin >> n;

	a = new int[n];

	for(int i=0;i<n;i++)
	{
		cin >> a[i];
	}

	int sum = 0;
	long long opr1 = 0,opr2 = 0;

	for(int i=0;i<n;i++)
	{
		sum += a[i];
		if(i%2 == 0)
		{
			if(sum > 0)continue;
			opr1 += abs(sum)+1;
			sum = 1;
		}
		else
		{
			if(sum < 0)continue;
			opr1 += abs(sum) + 1;
			sum = -1;
		}
	}

	sum = 0;

	for(int i=0;i<n;i++)
	{
		sum += a[i];
		if(i%2 == 0)
		{
			if(sum < 0)continue;
			opr2 += abs(sum) + 1;
			sum = -1;
		}
		else
		{
			if(sum > 0)continue;
			opr2 += abs(sum) + 1;
			sum = 1;
		}
	}

	ans = min(opr1,opr2);

	cout << ans << endl;

	delete(a);

	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<math.h>

int main()
{
	int h,n;
	int	num;
	scanf("%d%d",&h,&n);
	int i;
	int total=0;
	for (i=1;i<=n;i++)
	{
		scanf("%d",&num);
		total+=num;
	}
	if (total>=h)	printf("Yes");
	else printf("No");
	return 0;
} 
 

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int a, b;
	while (cin >> a&&cin >> b)
	{
		int c = a + b;
		int digit,i;
		for (i = 1, digit = 1;c / i != 0;i *= 10, digit++);
		cout << digit-1 << endl;
	}
	return 0;
}

Measured memory_bytes: 2980
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

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


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n,k;
    cin>>n>>k;
    map<int,int> x;
    forn(i,n){
        int a;
        cin>>a;
        x[a]++;
    }
    vpi y;
    for(auto i:x){
        y.pb(mp(i.se,i.fi));
    }
    sort(all(y));
    int u = y.size();
    if(u<=k)    cout<<0<<endl;
    else{
        int sum=0;
        for(int i=0;i<u-k;i++){
            sum += y[i].fi;
        }
        cout<<sum<<endl;
    }
    return 0;
}



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

int binpow(int a, int b)
{
    int ans = 1;
    if (b == 0)
        return 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

//read question carefully!

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        string s, s1;
        cin >> s >> s1;
        int n = s.size();
        int n1 = s1.size();
        int ct = 0, maa = 0;
        for (int i = 0; i <= n - n1; ++i)
        {
            ct = 0;
            for (int j = 0; j < n1; ++j)
            {
                if (s[i + j] == s1[j])
                {
                    // cout << j << "\n";
                    ct++;
                    maa = max(maa, ct);
                }
            }
        }
        // cout << n1 << " " << maa << "\n";
        cout << n1 - maa << "\n";
    }
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)
int penalty[100010];
bool is_ansered[100010];
int main(){
    int n, m;
    cin>>n>>m;
    rep(i,0,m){
        int p;
        string s;
        cin >> p >> s;
        if(s == "AC"){
            is_ansered[p] = true;
            continue;
        }
        if(!is_ansered[p]){
            penalty[p]++;
        }
    }
    long long num_anser=0, num_penalty=0;
    rep(i,1,n+1){
        if(is_ansered[i]){
            num_anser++;
            num_penalty+=penalty[i];
        }
    }
    cout << num_anser << " " << num_penalty << endl;
    return 0;
}

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


d = {}
for i in a:
    if i not in d:
        d[i] = 0
    d[i] += 1
l = []
for i in d.keys():
    l.append(d[i])
l = sorted(l)
print(sum(l[:len(l)-k]))


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

int main() {
  int n;
  cin>>n;
  int a[n+1];
  for (int i=1;i<=n;i++){
    cin>>a[i];
    a[i+1]=0;
  }
  int ans=0;
  for (int i=1;i<=n;i+=2){
    if (a[i]%2==1) ans++;
  }
  cout<<ans<<endl;
  return 0;
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5+23;
const int inf = 2e9;
int a[N];
int dp[N];

void solve() {
  // find the longest non-decreasing sequence in reverse
  int n; scanf("%d", &n);
  for (int i = n-1; i >= 0; --i) {
    scanf("%d", a+i);
    dp[i] = inf;
  }
  dp[0] = -inf;
  dp[n] = inf;
  for (int i = 0; i < n; ++i) {
    int j = upper_bound(dp, dp+n+1, a[i]) - dp;
    if (dp[j-1] <= a[i] && a[i] <= dp[j])
      dp[j] = a[i];
  }
  int ans = 0;
  for (int i = 0; i <= n; ++i) {
    if (dp[i] < inf)
      ans = i;
  }
  printf("%d", ans);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


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

signed main(){
  int N;
  cin >> N;
  vector<unsigned long long int>A(N+1000000);
  for(int i=1;i<=N;i++){
    cin >> A[i];
  }
  unsigned long long int count=0;
  int Q;
  cin >> Q;
  vector<int>B(Q+1);
  vector<int>C(Q+1);
  for(int i=1;i<=Q;i++){
    cin >> B[i] >> C[i];
  }
  vector<int>D(100001);
  for(int i=1;i<=N;i++){
    D[A[i]]++;
  }
  for(int i=1;i<=N;i++){
    count+=A[i];
  }
  for(int i=1;i<=Q;i++){
    count+=D[B[i]]*(C[i]-B[i]);
    cout << count << endl;
    D[C[i]]+=D[B[i]];
    D[B[i]]=0;
  }
}


Measured memory_bytes: 13008
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

sumtime = 0

bi = 0
while bi < m and sumtime + b[bi]<=k:
    sumtime += b[bi]
    bi += 1
    
ans = bi
for ai in range(n):
    sumtime += a[ai]
    while bi>=1 and sumtime>k:
        bi -= 1
        sumtime -= b[bi]
    
    if sumtime<=k:
        ans = max(ans, ai+bi+1)
    
    
print(ans)



Measured memory_bytes: 40744
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  string s, t;
  cin >> s >> t;
  char a[s.size()], b[t.size()];
  for(int i=0; i<s.size(); i++) {
    a[i]=s.at(i);
  }
  for(int i=0; i<t.size(); i++) {
    b[i]=t.at(i);
  }
  sort(a, a+s.size());
  sort(b, b+t.size());
  reverse(b, b+t.size());
  for(int i=0; i<100; i++) {
    if(a[i]<b[i]) {
      cout << "Yes" << endl;
      return 0;
    }
    else if(a[i]>b[i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#ABC130-E Common Subsequence
"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7

#dp table
dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(m+2) for _ in range(n+2)]
dp0[0][0] = 1
#process1
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] += dp0[i][j]%mod
        dp1[i][j] += dp0[i][j]%mod
        dp1[i][j+1] += dp1[i][j]%mod
        if s[i] == t[j]:
            dp0[i+1][j+1] += dp1[i][j]%mod


print(dp1[n][m]%mod)


Measured memory_bytes: 104412
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;

template<typename T>
struct BIT {
  int n;vector<T> d;
  BIT(int n  = 0):n(n), d(n+1){}
  void add(int i, T x=1) {
    for(i++; i <= n; i += i & -i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for(i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
};

int main() {
  int N, D, A; cin >> N >> D >> A;
  vector<P> p(N);
  for(int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
  sort(p.begin(), p.end());

  ll ans = 0;
  BIT<ll> bit(N+1);
  for(int i = 0; i < N; i++) {
    ll x = p[i].first;
    ll h = p[i].second;
    h -= bit.sum(i);
    if(h <= 0) continue;
    ll num = (h+A-1)/A;
    ans += num;
    ll damage = num * A;
    bit.add(i, damage);
    int rx = min(x + D*2, 1001001001ll);
    int j = upper_bound(p.begin(), p.end(), P(rx+1, -1)) - p.begin();
    bit.add(j, -damage);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>
int n;
long long a, m, x;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a);
		if (m < a)m = a;
		x += m - a;
	}
	printf("%lld\n", x);
}

Measured memory_bytes: 1724
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# F2上で基底集合Aにxを追加する
# ex: [[1,0,0],[0,1,0]] + [1,1,1] -> [[1,0,0],[0,1,0],[0,0,1]]
# 各要素は十進数で表記．上の例だと A=[4,2], x=7 -> A=[4,2,1]
def F2_update_basis(A,x):
    for a in A:
        x = min(x,x^a)
    if x:
        A.append(x)
    return A

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        if S[j] == '0':
            d = F2_update_basis(d,A[j])
        else:
            num = len(d)
            d = F2_update_basis(d,A[j])
            if len(d) != num:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Measured memory_bytes: 69212
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
	n,a,b = inputMap()
	#print(pow(2, n))

	total = pow(2, n, mod)
	total -= 1
	tmp = combination(n, a, mod)
	if total < tmp:
		total = total + mod - tmp
	else:
		total -= tmp

	tmp = combination(n, b, mod)
	if total < tmp:
		total = total + mod - tmp
	else:
		total -= tmp

	print(total)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

if __name__ == "__main__":
	main()


Measured memory_bytes: 88948