akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
#define For(i,x,y) for(int i = x; i <= y; ++i)
#define FOR For
#define rev_For(i,x,y) for(int i = x; i >= y; --i)
#define REV_FOR rev_For
#define ll long long
#define Size(v) ((int)v.size())
#define _section "\n--------------------\n"
#define fi first
#define se second
#define pb push_back
using namespace std;
// using namespace __gnu_pbds;


int n, m, x;
const int nax = 15;
int a[nax][nax], price[nax];
const int INF = 1e18;

void input() {
	cin >> n >> m >> x;
	FOR (i, 1, n) {
		cin >> price[i];
		FOR (j, 1, m) cin >> a[i][j];
	}
}

void solve() {

	int ans = INF;

	// choose some subset of books
	for (int id = 1; id < (1 << n); ++id) {
		vector<int> selection;
		FOR (i, 0, nax) {
			if (id & (1 << i)) selection.pb(i + 1);
		}

		int temp = 0;
		for (auto & c : selection) {
			temp += price[c];
		}

		vector<int> cnt;
		cnt.resize(m + 1);

		for (auto & c : selection) {
			for (int j = 1; j <= m; ++j) {
				cnt[j] += a[c][j];
			}
		}

		bool ok = true;

		for (int j = 1; j <= m; ++j) {
			if (cnt[j] < x) {
				ok = false;
				break;
			}
		}

		if (ok) ans = min(ans, temp);
	}

	if (ans == INF) {
		cout << -1;
		return;
	}
	cout << ans;
}

signed main() {
#ifdef _DEBUG
	// freopen("INPUT.inp", "r", stdin);
	//freopen("OUTPUT.out", "w", stdout);
	clock_t start, end;
	start = clock();
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//------------------------------------------------------------------------------------
//----------------------------------MAIN PROGRAM--------------------------------------
	int t = 1;
	while (t--) {
		input();
		solve();
	}
//--------------------------------------END-------------------------------------------
//------------------------------------------------------------------------------------
#ifdef _DEBUG
	end = clock();
	cerr << "\n----------\nTime Elapsed: " << fixed << double(end - start) / double(CLOCKS_PER_SEC) << setprecision(6) << '\n';
#endif
	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;



int main(){
    ll h, w, n;
    cin >> h >> w >> n;
    map<P, int> mp;
    vector<P> v;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        v.emplace_back(a, b);
        mp[P(a, b)]++; 
    }
    
    vector<ll> ans(10);
    rep(i, n) {
        int ix = v[i].first;
        int iy = v[i].second;
        for (int dx = -2; dx<=0; dx++) {
            for (int dy=-2; dy<=0; dy++) {
                int sx = ix + dx;
                int sy = iy + dy;
                if (sx<0 || sy<0 || sx>=h-2 || sy>=w-2) continue;
                ll sum = 0;
                bool ok = true;
                rep(xx, 3) rep(yy, 3) {
                    P now = P(sx+xx, sy+yy);
                    if (mp[now]>0) {
                        sum++;
                        if (now<P(ix, iy)) ok = false;
                    }
                }
                if (ok) ans[sum]++;
            }
        }
    }
    ans[0] = (h-2)*(w-2);
    rep1(i, 9) {
        ans[0] -= ans[i];
    }
    rep(i, 10) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 160224
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define acc(v) accumulate(v.begin(), v.end(), 0)

using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
	ll ans = 0;
	int n;
	cin >> n;
	printf("%.8f\n", pow(1.0 * n / 3, 3));
}


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

typedef long long int64;

int main()
{
    int64 N, T;
    cin >> N >> T;
    vector<int64> t(N), d;
    for (int i = 0; i < N; i++)
        cin >> t[i];
    int64 ans = 0;
    for (int i = 1; i < N; i++)
    {
        int64 d = t[i] - t[i - 1];
        if (d < T)
            ans += d;
        else
            ans += T;
    }
    cout << ans + T << endl;
}

Measured memory_bytes: 1792
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def prime_factorize(n):
    '''
    素因数分解のリストを返す。n == 1のとき[]になるので注意。
    :param n:int
    素因数分解する自然数
    :return: list
    素因数分解した結果。

    例
    n : 10
    primes : [[2, 1], [5, 1]]
    '''
    primes = {}
    for i in range(2, int(n ** (1 / 2)) + 1):
        if n % i != 0:
            continue
        num = 0
        while n % i == 0:
            num += 1
            n //= i
        primes[i] = num
    if n != 1:
        primes[n] = 1
    return primes

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
pairwise = False
prime_key = set(prime_factorize(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in prime_factorize(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')


Measured memory_bytes: 189612
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod = 1e9;
using namespace std;
const ll INF = 1LL << 50;//注意！
int main() {
	int a, b, q;
	cin >> a >> b >> q;
	vector<ll>s(a), t(b), x(q);
	repp(i, 0, a)cin >> s[i];
	repp(i, 0, b)cin >> t[i];
	repp(i, 0, q)cin >> x[i];
	vector<ll>minv(q);
	s.push_back(-INF); t.push_back(-INF);
	s.push_back(INF); t.push_back(INF);
	sort(s.begin(), s.end()); sort(t.begin(), t.end());
	repp(i, 0, q) {
	//iteratorを書くと煩雑になるのでautoを使っている
		auto pos_sr = lower_bound(s.begin(), s.end(), x[i]);
		auto pos_tr = lower_bound(t.begin(), t.end(), x[i]);
		auto pos_sl = pos_sr - 1;
		auto pos_tl = pos_tr - 1;
		ll d1 = abs(*pos_sr - x[i]), d2 = abs(*pos_sl - x[i]);
		ll d3 = abs(*pos_tr - x[i]), d4 = abs(*pos_tl - x[i]);
		minv[i] = min({ d1 + abs(*pos_tr - *pos_sr),d1 + abs(*pos_tl - *pos_sr),d2 + abs(*pos_tr - *pos_sl),d2 + abs(*pos_tl - *pos_sl),d3 + abs(*pos_sl - *pos_tr),d3 + abs(*pos_sr - *pos_tr),d4 + abs(*pos_sl - *pos_tl),d4 + abs(*pos_sr - *pos_tl) });
	}
	repp(i, 0, q) {
		cout << minv[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 4448
s = input()[::-1]
while len(s) > 0 :
    if s[:7] == 'remaerd':
        s = s[7:]
    elif s[:6] == 'resare':
        s = s[6:]
    elif s[:5] == 'maerd':
        s = s[5:]
    elif s[:5] == 'esare':
        s = s[5:]
    else:
        break
print(('NO','YES')[len(s)==0])

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

import math

a, b, x = map(int, input().split())

v = a * a * b

if x < v/2:  # over 45
    c = x * 2 / (a * b)
    print(90 - math.degrees(math.atan2(c, b)))
else:
    x = v - x
    c = x * 2 / (a * a)
    print(math.degrees(math.atan2(c, a)))

Measured memory_bytes: 3060
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;


int main() {
	long long A;
    string B;
    cin >> A >> B;
    cout << (A * (B[3] - '0') + A * (B[2] - '0') * 10 + A * (B[0] - '0') * 100) / 100 << endl;
	
}

Measured memory_bytes: 3612
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

_ = ri()
li = rl()
cnt = 0
max_ = 0
for i in li:
  if i >= max_:
    cnt += 1
    max_ = i
print(cnt)







Measured memory_bytes: 27060
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}




int main() {
  ll X;
  cin >> X;
  ll now = 100;
  ll y = 0;
  while(now < X) {
    now*=1.01;
    y++;

  }
  cout << y << endl;
  return 0;
}


Measured memory_bytes: 3196
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
  int p, q, r; 
  cin >> p >> q >> r;
  int tmp = p;// max
  if(tmp<q) tmp = q;
  if(tmp<r) tmp = r;

  int ans = p + q + r -tmp;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static Scanner sc = new Scanner(System.in);
	static final long Mod = 1000_000_007L;
	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}

	void solve() {
		String S = next();
		sc.close();
		int Slen = S.length();
		int winsum = 0;
		for(int i=0;i<Slen;i++) {
			winsum += S.substring(i, i+1).equals("o")?1:0;
		}

		String res = "NO";
		if(15-Slen+winsum>=8)res = "YES";

		out.println(res);
	}
	private long max(long a, long b) {
		return Math.max(a, b);
	}
	private long min(long a, long b) {
		return Math.min(a, b);
	}
	private static int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)a[i] = nextInt();
		return a;
	}
	private static long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)a[i] = nextLong();
		return a;
	}
	private static int nextInt() {
		return Integer.parseInt(next());
	}
	private static long nextLong() {
		return Long.parseLong(next());
	}
	private static String next() {
		return sc.next();
	}
	static long gcd(long m,long n) {
		if (m<n) return gcd(n,m);
		if (n==0)return m;
		return gcd(n,m%n);
	}

}

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        String s = in.ns();
        String t = in.ns();
        if(t.substring(0,s.length()).equals(s))out.println("Yes");
        else out.println("No");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32716
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;


#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[0] != s[1] || s[1] != s[2]) {
    	cout<<"Yes\n";
    } else {
    	cout<<"No\n";
    }
}

Measured memory_bytes: 256
K, N = (int(n) for n in input().split(' '))
A = [int(n) for n in input().split(' ')]

min_dist = K
for i, Ai in enumerate(A):
  clockwise = (A[(i - 1) % N] - Ai) % K
  counter_clockwise = (K - (A[(i + 1) % N] - Ai)) % K
  if clockwise < min_dist:
    min_dist = clockwise
  if counter_clockwise < min_dist:
    min_dist = counter_clockwise

print(min_dist)

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

const int mod = 1'000'000'007;
class mint {
public:
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    operator ll () const { return x; }
    operator string () const { return to_string(x); }
};

mint dp[201][201];

int main() {
    int n;
    cin >> n;
    vector<int> c;
    for (int i=0; i<n; ++i) {
        char t; cin >> t;
        if (t == 'U') c.push_back(1);
        else if (t == 'D') c.push_back(-1);
    }
    n = c.size();

    dp[0][0] = 1;
    rep(i,n) rep(j,n+1) {
        if ( ! dp[i][j]) continue;
        if (c[i] < 0) {
            if (j > 0) dp[i+1][j] += dp[i][j] * mint(j);
            if (j > 0) dp[i+1][j-1] += dp[i][j] * mint(j) * mint(j);
        } else {
            dp[i+1][j+1] += dp[i][j];
            if (j > 0) dp[i+1][j] += dp[i][j] * mint(j);
        }
    }
    cout << dp[n][0] << endl;
    return 0;
}


Measured memory_bytes: 3488
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int s;
    cin >> s;
    int prev = s/100;
    int next = s%100;
    if(prev < 13 && prev > 0){
        if(next < 13 && next > 0)out("AMBIGUOUS");
        else out("MMYY");
    } 
    else if(next < 13 && next > 0){
        if(prev < 13 && prev > 0) out("AMBIGUOUS");
        else out("YYMM");
    }
    else out("NA");
}


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

import sys
input=sys.stdin.readline

n=int(input())
arr=list(map(int,input().split()))
ans=0
for i in range(1,n):
    if arr[i]<arr[i-1]:
        ans+=arr[i-1]-arr[i]
        arr[i]=arr[i-1]
print(ans)

Measured memory_bytes: 92168
#include<stdio.h>
#include<string.h>

#define N 1005

int LCS(char *, char *);
int Max(int, int);

int main () {
  int n = 0, i;
  char str1[150][N], str2[150][N];

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++) {
    scanf("%s",str1[i]);
    scanf("%s",str2[i]);
  }

  for(i = 0 ; i < n ; i++) printf("%d\n",LCS(str1[i],str2[i]));  

  return 0;
}

int LCS(char *str1, char *str2) {
  int m = strlen(str1) + 1, n = strlen(str2) + 1, i, j, max = 0;
  int c[N][N];

  for(i = 1 ; i < m ; i++) c[i][0] = 0;
  for(j = 0 ; j < n ; j++) c[0][j] = 0;



  for(i = 1 ; i < m ; i++) {
    for(j = 1 ; j < n ; j++) {
      if(str1[i - 1] == str2[j - 1]) c[i][j] = c[i - 1][j - 1] + 1;

      else c[i][j] = Max(c[i - 1][j],c[i][j - 1]);

      max = Max(max,c[i][j]);

    }
  }

  return max;
}


int Max(int x, int y) {
  if(x >= y) return x;
  else return y;
}



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

int n, k;

int main()
{
    scanf( "%d%d", &n, &k );
    
    if( k == 0 ) {
    	printf( "%lld\n", ll(n) * n ); return 0;
	}
    
    ll ans = 0;
    for( int i = k+1; i <= n; i ++ )
    {
        ans += ( n / i ) * ( i - k );
        int tmp = ( n % i ) - k + 1; 
        if( tmp > 0 ) ans += tmp;
    }

    printf( "%lld\n", ans );

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();
		long k = sc.nextLong();
		
		long ans = Math.min(n%k, Math.abs(n%k-k));
		System.out.println(ans);
	}
}


Measured memory_bytes: 23636
from collections import Counter
from itertools import combinations


n = int(input())
lst_s = [input()[0] for _ in range(n)]
lst_march = [s for s in lst_s if s in "MARCH"]
cnt_s = Counter(lst_march)
lst_num = list(cnt_s.values())
cmb_num = list(combinations(lst_num, 3))
ans = sum(c[0] * c[1] * c[2] for c in cmb_num)
print(ans)

Measured memory_bytes: 59480
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

int main() {
	int D, N;
	cin >> D >> N;
	if (D == 0) {
		cout << N + N / 100 << endl;
	}else if (D == 1) {
		cout << N * 100  + (N / 100) * 100 << endl;
	}
	else {
		cout << N * 10000 + (N / 100) * 10000<< endl;
	}
}


Measured memory_bytes: 256
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <limits.h>
#include <iostream>
#define REP(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
const int inf=1<<30;
const int INF=INT_MAX;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int d[]={0,1,0,-1,0};//int nx=x+d[i],ny=y+d[i+1]

int par[100001];
int size[100001];

void init(int n) {
  for (int i = 0; i < n; i++) {
    par[i] = i;
    size[i] = 1;
  }
}
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (size[x] < size[y]) {
    par[x] = y;
    size[y] += size[x];
  } else {
    par[y] = x;
    size[x] += size[y];
  }
}
bool same(int x, int y) {
  return find(x) == find(y);
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int m;
  long long n;
  long long fu[100001];
  int a[100001], b[100001];
  cin >> n >> m;
  init(n);
  REP(i, m) {
    cin >> a[i] >> b[i];
  }
  fu[m] = n * (n - 1) / 2;
  for(int i = m - 1; i >= 0; --i) {
    if(same(a[i], b[i])) {
      fu[i] = fu[i + 1];
    } else {
      fu[i] = fu[i + 1] - size[find(a[i])] * (long long)size[find(b[i])];
      unite(a[i], b[i]);
    }
  }

  for(int i = 1; i <= m; ++i) {
    cout << fu[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>


int main(){
  int N, M; cin >> N >> M;
  int  A[N]; rep(i,N) cin >> A[i];
  sort(A, A+N);

  vector<pii> v(M);
  rep(i,M) cin >> v[i].second >> v[i].first;
  sort(all(v));
  reverse(all(v));

  int prev=0, now = 0;
  ll ans = 0;
  rep(i,M){
    ll C = v[i].first;
    int B = v[i].second;
    now = lower_bound(A+prev, A+N, C) - A;
    now = prev + min(B,now-prev);
    ans +=  (now-prev)*C;
    // cout << now << endl;
    prev = now;
  }
  for (int i=now;i<N;i++){
    ans += A[i];
  }
  cout << ans << endl;



  // cout << fixed << setprecision(10);
  
  return 0;
}


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

int main()
{
  int x,y,z;
  cin >> x >> y >> z;
  bool flag = true;
  int i = 1;
  while(flag){
    int l = y*i + z*(i+1);
    if(l <= x) i++;
    else {
      i--;
      flag = false;
    }
  }
  cout << i << endl;
}


Measured memory_bytes: 256
class Value_UnionFind():

    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)

def main(n, m):
    Union = Value_UnionFind(n)
    for _ in range(m):
        x = list(map(str, input().split()))
        q = x[0]
        if q == "!":
            a, b, w = map(int, x[1:])
            Union.unit(a-1, b-1, w)
        if q == "?":
            a, b = map(int,x[1:])
            if Union.root(a-1) != Union.root(b-1):
                print("UNKNOWN")
            else:
                print(Union.differ(a-1, b-1))



while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    main(n,m)


Measured memory_bytes: 11276
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
ll n, l, mins=inf, ans;
ll sums=0;

int main(){
	IOS
	cin >> n >> l;
	for(int i=1;i<=n;i++){
		sums+=(l+i-1);
	}
	for(int i=1;i<=n;i++){
		ll temp=sums-(l+i-1);
		if(abs(sums-temp)<mins){
			ans=temp;
		}
		mins=min(mins, abs(sums-temp));
	}	
	cout << ans << '\n';
}


Measured memory_bytes: 3624
import kotlin.comparisons.*
import java.util.*

const val MOD = 1000000007L

fun readI() = readLine()!!.toInt()
fun readL() = readLine()!!.toLong()
fun readD() = readLine()!!.toDouble()
fun readIs() = readLine()!!.split(' ').map(String::toInt)
fun readLs() = readLine()!!.split(' ').map(String::toLong)
fun readDs() = readLine()!!.split(' ').map(String::toDouble)

fun main(args: Array<String>) {
  val (n, m) = readIs()
  val a = readIs().sorted().toIntArray()
  val cx = TreeMap<Int, Long> { x, y -> y - x }
  repeat(m) {
    val (b, c) = readIs()
    cx[c] = cx.getOrElse(c) { 0L } + b
  }
  var i = 0
  esc@for ((c, x) in cx) {
    for (j in 1..x) {
      if (n <= i || c <= a[i]) break@esc
      a[i++] = c
    }
  }
  var ans = 0L
  a.forEach { ans += it }
  println(ans)
}


Measured memory_bytes: 81944
import java.util.*;
class Main {
 	public static void main(String[] args) {
      Scanner s = new Scanner(System.in);	
      int k = s.nextInt();
      int x = s.nextInt();
      if (k * 500 >= x) {
      	System.out.println("Yes");
      } else {
       	System.out.println("No"); 
      }
    } 
}

Measured memory_bytes: 20052
#include<algorithm>
#include<iostream>
#include<math.h>

#define TORIDASI(size,data) if(str.substr(i,size) == data){\
i+=size;\
}
#define SUSUMU(doredake,mozi) for(int ssm = 0;ssm < doredake;ssm++){\
	str += mozi;\
}

using namespace std;

int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	string str = "";
	SUSUMU(tx - sx, "R");
	SUSUMU(ty - sy, "U");
	SUSUMU(tx - sx, "L");
	SUSUMU(ty - sy, "D");
	str += "D";
	SUSUMU(tx - sx + 1, "R");
	SUSUMU(ty - sy + 1, "U");
	str += "LU";
	SUSUMU(tx - sx + 1, "L");
	SUSUMU(ty - sy + 1, "D");
	str += "R";
	cout << str << endl;
}

Measured memory_bytes: 256
S = gets.chop(&:to_s)
s1 = S[0,2].to_i
s2 = S[2,3].to_i
if s1 == 0 || s2 == 0
  if 1 <= s1 && s1 <= 12
    puts "MMYY"
  elsif 1 <= s2 && s2 <= 12
    puts "YYMM"
  else
    puts "NA"
  end
elsif s1 <= 12 && s2 <= 12
  puts "AMBIGUOUS"
elsif s1 >= 13 && s2 <= 12
  puts "YYMM"
elsif s1 <= 12 && s2 >= 13
  puts "MMYY"
else
  puts "NA"
end

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

const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
    }
    
    vector<ll> rui(n);
    for(int i = n - 2; i >= 0; i--) {
        rui[i] = (rui[i+1] + a[i+1]) % mod;
    }
    
    ll ans = 0;
    rep(i,n) {
        ans = (ans + a[i] * rui[i]) % mod;
    }
    
    cout << ans << endl;
    
    
    
    return 0;
}




Measured memory_bytes: 5628
C=[0 for i in range(2)]
C=input().split()
n=(int)(C[0])
x=(int)(C[1])

B=[]
cnt=0
while n>0:

	A=[0 for i in range(n)]
	A=input().split()

	max=0

	for i in range(len(A)-1):
		for j in range(i+1, len(A)):
			if max<(int)(A[i])+(int)(A[j]) and (int)(A[i])+(int)(A[j])<=x:
				max=(int)(A[i])+(int)(A[j])
	if max>0:
		B.append(max)
	else:
		B.append("NONE")

	C=[0 for i in range(2)]
	C=input().split()
	n=(int)(C[0])
	x=(int)(C[1])

	cnt+=1

for i in range(cnt):
	print(B[i])


Measured memory_bytes: 5664
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int n;
    cin >> n;
    rep(i, 25) {
        rep(j, 14) {
            if(4*i + 7*j == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(a)			a.begin(), a.end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define	MAX_QWORD		((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, ll>	P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	int D, G;
	cin >> D >> G;
	static int p[10];
	static int c[10];
	REP(i, D) cin >> p[i] >> c[i];

	static ll dp[11][1005];
	fill((ll*)dp, (ll*)dp + 11 * 1005, (ll)-1);
	dp[0][0] = 0;
	REP(i, D) {
		REP(prgCnt, p[i] + 1) {
			ll sumPtn = prgCnt * 100 * (i + 1);
			if (prgCnt == p[i]) {
				sumPtn += c[i];
			}
			REP(j, 1001) {
				if (0 <= dp[i][j]) {
					dp[i + 1][j + prgCnt] = max(dp[i + 1][j + prgCnt], dp[i][j] + sumPtn);
				}
			}
		}
	}

	int ans = INF;
	REP(j, 1001) {
		if (G <= dp[D][j]) {
			ans = j;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 384
#import <stdio.h>
#import <Foundation/Foundation.h>
char buf[1000];
int main(int argc, const char * argv[]) {
    scanf("%s", buf);
    NSString *weather = [NSString stringWithUTF8String:buf];
    if ([weather isEqualToString:@"Sunny"]) {
        printf("Cloudy\n");
    } else if ([weather isEqualToString:@"Cloudy"]) {
        printf("Rainy\n");
    } else {
        printf("Sunny\n");
    }
    return 0;

}

Measured memory_bytes: 9952
import java.util.Scanner;

public class Main {

    public Main() {
    }

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

    private Scanner sc;

    private void solve() {
        sc = new Scanner(System.in);
        String f = sc.nextLine();
        String[] arr = f.split(" ");
        MyStack stack = new MyStack();
        for (String s : arr) {
            try {
                int n = Integer.parseInt(s);
                stack.push(n);
            } catch (Exception e) {
                int n1 = (int) stack.pop();
                int n2 = (int) stack.pop();
                stack.push(calc(n1, n2, s));
            }
        }
        System.out.println(stack.pop());
    }

    private int calc(int n1, int n2, String o) {
        if ("+".equals(o)) {
            return n2 + n1;
        } else if ("-".equals(o)) {
            return n2 - n1;
        } else {
            return n2 * n1;
        }
    }

}

class MyStack {
    int tail;
    Object[] arr;

    public MyStack() {
        this.tail = -1;
        arr = new Object[100];
    }

    public void push(Object o) {
        tail++;
        arr[tail] = o;
    }

    public Object pop() {
        if (isEmpty()) {
            return null;
        } else {
            Object r = arr[tail];
            arr[tail] = null;
            tail--;
            return r;
        }
    }

    public boolean isEmpty() {
        if (tail == -1) {
            return true;
        } else {
            return false;
        }
    }

}

Measured memory_bytes: 26256
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

s = s()

flag = 0
if s[0] == "A":
	flag += 1 
cnt1 = 0
for i in range(2,len(s)-1):
	if s[i] == "C":
		cnt1 += 1
if cnt1 == 1:
	flag += 1
cnt2 = 0
for i in range(1,len(s)):
	if s[i].islower():
		cnt2 += 1
if cnt2 >= len(s) -2:
	flag += 1

if flag == 3:
	print("AC")
else:
	print("WA")

Measured memory_bytes: 9152
#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;

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

  string res = "No";

  for(ll i = 0; i * 4 <= N; ++i)
  {
    for(ll j = 0; j*7 + i * 4 <= N; ++j)
    {
      if(i*4 + j*7 == N)
      {
        res = "Yes";
        break;
      }
    }
  }

  cout << res << endl;



  return 0;

}

Measured memory_bytes: 256
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  [x,y] <- getl $ take 2 . sort . split toInt
  when (x /= 0 || y /= 0) $ do
    n <- getl toInt
    rs <- rgetl n toInt
    mapM_ putStrLn $ solve x y rs
    main
    
solve :: Int -> Int -> [Int] -> [String]
solve x y rs = map f rs
  where
    f r = if x ^ 2 + y ^ 2 < 4 * r ^ 2 then "OK" else "NA"

toInt :: String -> Int
toInt s = read s

split :: (String -> a) -> String -> [a]
split f = map f . words

getl :: (String -> a) -> IO a
getl f = f <$> getLine

rgetl :: Int -> (String -> a) -> IO [a]
rgetl n f = map f <$> replicateM n getLine

Measured memory_bytes: 4064
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(x,y) '(' << x << ',' << y << ')'
ll MOD = 1000000007;
ll INF = 214748364700000000;
double EPS = 1e-12;
double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

ll N,M,L;
Graph G(310);
pair<ll,ll> fuel[310][310];

void dijkstra(ll s,ll e = L){
    rep(i,N){
        fuel[s][i].first = INF;
        fuel[s][i].second = -1;
    }
    ll cnt = 0;
    map<pair<ll,ll>,ll> mp;
    priority_queue<tuple<ll,ll,ll>> Q;
    bool done[310];
    fill(done,done+310,false);
    done[s] = true;
    Q.emplace(0,e,s);
    while(Q.size()){
        cnt++;
        if(cnt > 3*N){
            break;
        }
        ll C,E,X;
        tie(C,E,X) = Q.top();
        Q.pop();
        ll n = G[X].size();
        done[X] = true;
        rep(i,n){
            ll Y = G[X][i].first,D = G[X][i].second;
            if(done[Y]) continue;
            if(E >= D){
                if(fuel[s][Y].first > -C){
                    Q.emplace(C,E-D,Y);
                    fuel[s][Y].first = min(fuel[s][Y].first,-C);
                    fuel[s][Y].second = E-D;
                }else if(fuel[s][Y].first == -C && fuel[s][Y].second < E-D){
                    Q.emplace(C,E-D,Y);
                    fuel[s][Y].second = E-D;
                    fuel[s][Y].first = min(fuel[s][Y].first,-C);
                }
            }else{
                if(fuel[s][Y].first > -C+1){
                    Q.emplace(C-1,L-D,Y);
                    fuel[s][Y].first = min(fuel[s][Y].first,-C+1);
                    fuel[s][Y].second = L-D;
                }else if(fuel[s][Y].first == -C+1 && fuel[s][Y].second < L-D){
                    Q.emplace(C-1,L-D,Y);
                    fuel[s][Y].second = L-D;
                    fuel[s][Y].first = min(fuel[s][Y].first,-C+1);
                }
            }
        }
    }
    return ;
}

int main(){
   cin >> N >> M >> L;
   rep(i,M){
       ll a,b,c;cin >> a >> b >> c;
       a--;b--;
       if(c > L) continue;
       G[a].emplace_back(b,c);
       G[b].emplace_back(a,c);
   }
   rep(i,N){
       dijkstra(i);
   }
   ll q;cin >> q;
   vector<ll> ans(q);
   rep(i,q){
       ll s,t;cin >> s >> t;
       s--;t--;
       ans[i] = fuel[s][t].first;
       if(fuel[s][t].first == INF) ans[i] = -1;
   }
   rep(i,q){
       cout << ans[i] << endl;
   }
}


Measured memory_bytes: 5220
//wawando's template

#include <iostream>
#include <string>
#include <fstream>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <set>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>  //clock_t , clock() , CLOCKS_PER_SEC
#include <cstring>
#include <cctype>
#include <climits> // LLONG_MAX , LLONG_MIN , INT_MAX , INT_MIN

//MACROS
#define pb              push_back
#define mp              make_pair
#define INF             1000000000     //1 billion safer for floyd warshall, avoid overflow

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false); cin.tie(0);

  int N,M;
  vector<vi> bulbs;
  vi p;

  cin >>N >>M;
  bulbs.assign(M, vi());
  for(int i = 0; i < M; i++) {
    int k;
    cin >>k;
    for(int j = 0; j < k; j++) {
      int s;
      cin >>s;
      bulbs[i].pb(s-1);
    }
  }
  for(int i = 0; i < M; i++) {
    int pi;
    cin >>pi;
    p.pb(pi);
  }
  int ans = 0;
  for(int mask = 0; mask < (1 << N); mask++) {
    bool isOn = true;
    for(int i = 0; i < M; i++) {
      int onCount = 0;
      for(int j = 0; j < (int)bulbs[i].size(); j++) {
        if(mask & (1 << bulbs[i][j]))
          onCount++;
      }
      isOn &= (onCount % 2 == p[i]);
    }
    ans += (isOn ? 1 : 0);
  }
  cout <<ans <<endl;
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;
//const int mod = 998244353;


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

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

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n;
  cin >> n;
  multiset<ll> st;
  rep(i, n) {
    ll a;
    cin >> a;
    if(st.size() == 0 || a <= *st.begin()) {
      st.insert(a);
    }
    else {
      auto it = st.lower_bound(a);
      --it;
      st.erase(it);
      st.insert(a);
    }
  }
  cout << st.size() << endl;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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


int n,m,a[10],dp[10005];
int c[10]={0,2,5,5,4,5,6,3,7,6};

void solve() {
    cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> a[i];
	dp[0]=1;
	for(int i = 0; i < m; i++){
		for(int j = c[a[i]]; j <= n;j++)
			dp[j] = max(dp[j],dp[j-c[a[i]]]+1);
	}
	sort(a,a+m);
	m--;
	while(n>0){
		if(n-c[a[m]] >= 0 && dp[n]==dp[n-c[a[m]]]+1){
			n -= c[a[m]];
			cout<<a[m];
		}else m--;
	}
    cout << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  
  int count = 0;
  for (int i=a; i<=b; i++) if (c%i == 0) count++;
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3132
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

A,B,C = I()
cnt = 0
for i in range(1000):
    if A != B and B != C and A != C:
        A += 1
        B += 1
        C += 1
        if max(A,B,C) == A:
            A -= 1
        elif max(A,B,C) == B:
            B -= 1
        else:
            C -= 1
        cnt += 1
    if A == B and B == C and A == C:
        print(cnt)
        exit()
    if A == B or B == C or A == C:
        d = abs(max(A,B,C)-min(A,B,C))
        if [A,B,C].count(max(A,B,C)) == 2:
            if d%2 == 0:
                print(cnt+d//2)
                exit()
            else:
                print(cnt+d//2+2)
                exit()
        else:
            print(cnt+d)
            exit()

Measured memory_bytes: 10096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
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; }
const int INF = 1<<30;

int main(){
    ll n, d, a, cnt = 0;
    cin >> n >> d >> a;
    vector<pii> P(n);
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        P[i] = {a, b};
    }
    sort(all(P));
    vector<ll> X(n), H(n);
    for(int i = 0; i < n; i++){
        X[i] = P[i].fi;
        H[i] = (P[i].se + a - 1) / a;
    }
    // cout << endl;
    queue<pll> que;
    ll cur = 0;
    for(int i = 0; i < n; i++){
        if(H[i] <= 0) continue;
        ll p = X[i] + 2 * d;
        int idx = upper_bound(all(X), p) - X.begin() - 1;
        while(!que.empty() && que.front().fi < i){
            cur -= que.front().se;
            que.pop();
        }
        H[i] -= cur;
        if(H[i] <= 0) continue;
        que.push({idx, H[i]});
        cur += H[i];
        cnt += H[i];
        // cout << X[i] << " " << p << " " << idx << endl;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 6528
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);

        int[] list = {sc.nextInt(), sc.nextInt(), sc.nextInt()};
        Arrays.sort(list);
        int add = 2 * list[2] - (list[0] + list[1]);
        int ans = add / 2;
        if (add % 2 == 1) {
            ans += 2;
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 21844