akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const int N=2e6+20;
const ll inf=2e15;
ll n,a,b,x,y;
bool check(ll mid)
{
	return a<=mid*x&&b<=mid*y;
}
int main()
{
	while(cin>>n)
	{
		cin>>a>>b; 
		for(int i=2;i<=n;i++)
		{
			scanf("%lld%lld",&x,&y);
			//x/y -> kx/ky
			ll l=1,r=1e18/max(x,y);
			while(l<=r)
			{
				ll mid=(l+r)>>1;
				if(check(mid))
					r=mid-1;
				else
					l=mid+1;
			}
			a=(r+1)*x,b=(r+1)*y;
		}
		cout<<a+b<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define N 100000
using namespace std;
int n;
long long s1,s2;
int a1[N+5],a2[N+5];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a1[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&a2[i]);
	for(int i=1;i<=n;i++)
	{
		if(a1[i]<a2[i])
		{
			int x=a2[i]-a1[i];
			if(x%2)
				x++,s2++;
			s1+=x/2;
		}
		else
			s2+=a1[i]-a2[i];
	} 
	if(s2<=s1)
		printf("Yes\n");
	else
		printf("No\n");
}

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

int main() {
	int n, q;
	string s;
	cin >> n >> q >> s;
	pair<int, int> l[100000];
	for (int i = 0; i < q; i++)
		cin >> l[i].first >> l[i].second;
	for (int i = 0; i < n - 1; i++)
		if (s[i] == 'A' && s[i + 1] == 'C')
			s[i + 1] = 'c';
	long long count = 0;
	int p[100000];
	for (int i = 0; i < n; i++) {
		if (s[i] == 'c')
			count++;
		p[i] = count;
	}
	for (int i = 0; i < q; i++)
		cout << p[l[i].second - 1] - p[l[i].first - 1] << endl;
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

    int a, b;
    cin >> a >> b;
    if (a % 2 == 0 && b % 2 == 0) {
        cout << "No" << endl;
    } else if (a % 2 == 1 && b % 2 == 0) {
        cout << "No" << endl;
    } else if (a % 2 == 0 && b % 2 == 1) {
        cout << "No" << endl;
    } else if (a % 2 == 1 && b % 2 == 1) {
        cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
    #include <algorithm>
    int A, B, C, K;
    int main() {
    	std::cin >> A >> B >> C >> K;
    	std::cout << A + B + C + std::max({ A, B, C }) * ((1 << K) - 1) << '\n';
    	return 0;
    }

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> all(m, vector<int>());
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    all[y].push_back(x);
  }
  int res = n;
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    sort(all[i].begin(), all[i].end());
    for (int x : all[i]) {
      if (x <= i + cnt) {
        cnt += (x == i + cnt);
        continue;
      }
      res = min(res, x);
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 11532
process.stdin.resume();
process.stdin.setEncoding('utf8');
// Your code here!
 
const Main = (p)=>{
	// 1行目がinput[0], 2行目がinput[1], …に入る
	p = p.split("\n");
	let N = parseInt(p[0]);
	let kehin=[];
	for(let i=0;i<N;i++){
	    kehin[p[i+1]]=1;
	}
	//文字列から10進数に変換するときはparseIntを使います
	//出力
	console.log(Object.keys(kehin).length);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 85048
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;

int x, a;

int main(){
	scanf("%d%d", &x, &a);
	if(x < a)
		puts("0");
	else
		puts("10");
	return 0;
}



Measured memory_bytes: 256
import collections

n, k = map(int, input().split())
A = list(map(int, input().split()))

B = collections.Counter(A)
V = []

for key, val in B.items():
    V.append(val)

V = sorted(V, reverse=True)

if len(V) <= k:
    ans = 0
else:
    ans = sum(V[k:])
print(ans)

Measured memory_bytes: 32540
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<int> a;
    set<int> st;
    set<int>::iterator it;
    st.clear();
    for(int i=0; i<n; ++i) {
        int k; cin>>k;
        a.push_back(k);
    }
    sort(a.begin(),a.end());
    for(int i=0; i<n; ++i) {
        st.insert(a[i]);
        it = st.find(a[i]);
        it++; if(it!=st.end()) st.erase(it);
    }
    cout<<st.size()<<endl;
        


    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

std::vector<bool> is_prime;
std::vector<int> prime;
template<typename T> void segment_sieve(const T a, const T b) {
	prime = std::vector<T>();
	if (a >= b) {
		is_prime = std::vector<bool>();
		return;
	}
	T lim = ceil(sqrt(b));
	is_prime = std::vector<bool>(b - a, true); // is_prime[i-a] = true ⇔ iが素数
	std::vector<bool> is_prime_small(lim, true);
	for (T i = 2; i < lim; i++) {
		if (is_prime_small[i]) {
			for (T j = i * i; j < lim; j += i) is_prime_small[j] = false; // [2, √b)の篩
			for (T j = std::max(i, (a + i - 1) / i) * i; j < b; j += i) is_prime[j - a] = false; // [a, b)の篩
		}
	}
	for (T i = 0; i < b - a; i++) {
		if (is_prime[i]) prime.emplace_back(i + a);
	}
}

signed main() {
	int x;
	cin >> x;

	segment_sieve(x, 100100);

	col(prime[0]);
	return 0;
}


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

const int MAXN = 8005;

int N;
char s[MAXN];
int x, y;
bitset <2 * MAXN> dp[2];

int main() {
	scanf("%s%d%d", s, &x, &y);
	N = strlen(s);
	s[N++] = 'T';
	
	for (int i = 0; i < 2; i++)
		dp[i].set(MAXN);
		
	int dir = 0, last = -1;
	for (int i = 0; i < N; i++) 
		if (s[i] == 'T') {
			int shift = i - last - 1;
			if (last == -1)
				dp[dir] <<= shift;
			else
				dp[dir] = (dp[dir] << shift) | (dp[dir] >> shift);
			last = i;
			dir ^= 1;  
		}
	
	puts(dp[0].test(MAXN + x) && dp[1].test(MAXN + y) ? "Yes" : "No");
	
	return 0;
}

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

int main() {
	string s,t;
	cin>>s>>t;
	
	int memo[s.length()+1][t.length()+1];
	
	for(int i=0; i<=s.length(); i++) {
		for(int j=0; j<=t.length(); j++) {
			if(i==0 || j==0) {
				memo[i][j] = 0;
			} else if(s[i-1] == t[j-1]) {
				memo[i][j] = 1+memo[i-1][j-1];
			} else {
				memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
			}
		}
	}
	
	int index = memo[s.length()][t.length()];
	char lcs[index+1];
	lcs[index] = '\0';
	
	int i=s.length();
	int j=t.length();
	while(i>0 && j>0) {
		if(s[i-1] == t[j-1]) {
			lcs[index-1] = s[i-1];
			i--;
			j--;
			index--;
		} else if(memo[i-1][j] > memo[i][j-1]) {
			i--;
		} else {
			j--;
		}
	}
	
	cout<<lcs;
	
	return 0;
}

Measured memory_bytes: 38780
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
using namespace std;
constexpr int64_t MOD = 1000000007;

inline int64_t pat(int64_t fn, int64_t idx) {
  int64_t res = 0;
  for (int i = 1; i <= idx; i++) {
    res += fn / i;
    res %= MOD;
  }
  return res;
}

inline int64_t factorial(int64_t K) {
  int64_t res = 1;
  for (int i = 1; i <= K; i++) {
    res *= i;
    res %= MOD;
  }
  return res;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

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

  int32_t N;
  cin >> N;
  vector<int64_t> dx(N-1);
  int64_t prev = 0;
  cin >> prev;
  for (int i = 0; i < N-1; i++) {
    int64_t cur = 0;
    cin >> cur;
    dx[i] = cur - prev;
    prev = cur;
  }

  int64_t factN = factorial(N-1);
  vector<int64_t> pattern(N-1,0);
  pattern[0] = factN;
  int64_t res = factN * dx[0];
  res %= MOD;
  for (int i = 1; i < N - 1; i++) {
    pattern[i] = pattern[i-1] + factN * modinv((i+1), MOD);
    pattern[i] %= MOD;
    res += dx[i] * pattern[i];
    res %= MOD;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1792
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i!=n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
signed gcd(int a, int b){return b?gcd(b,a%b):a;}

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    string s;
    cin >> s;
    rep(i,3)
    {
        if(s[i]==s[i+1])
        {
            cout << "Bad" << endl;
            return;
        }
    }

    cout << "Good" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

int main(){

  int a; cin >> a;
  string s; cin >> s;

  if (a >= 3200) cout << s << endl;
  else cout << "red" << endl;

  
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  dic[i+1] = 0
for ai in a:
  dic[ai] += 1
cnt = 0
for di in dic:
  cnt += dic[di] * (dic[di] - 1) // 2
for i in range(n):
  print(cnt - dic[a[i]] * (dic[a[i]] - 1) // 2 + (dic[a[i]] - 2) * (dic[a[i]] - 1) // 2)

Measured memory_bytes: 40960
#define _overload(_1, _2, _3, _4, name, ...) name
#define _rep1(Itr, N) _rep3(Itr, 0, N, 1)
#define _rep2(Itr, a, b) _rep3(Itr, a, b, 1)
#define _rep3(Itr, a, b, step) for (i64 (Itr) = a; (Itr) < b; (Itr) += step)
#define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)

#include "bits/stdc++.h"
using i64 = long long;
using namespace std;

const i64 mod = (i64)(1e9) + 7;

long long pow_mod(long long n, long long m) {
    //n ** m;
    long long ret = 1;

    while (m) {
        if (m & 1) {
            ret = ret * n % mod;
        }

        n = n * n % mod;
        m = m >> 1;
    }

    return ret;
}
//===

int main() {
    i64 n;
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    i64 ans = pow_mod(10, n);
    ans -= pow_mod(9, n) * 2 % mod;
    ans += pow_mod(8, n);
    ans %= mod;
    ans += mod;
    ans %= mod;

    cout << ans << endl;

    return 0;
};


Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define POSSIBLE(c) coc(c, "POSSIBLE", "IMPOSSIBLE")
#define Possible(c) coc(c, "Possible", "Impossible")
#define possible(c) coc(c, "possible", "impossible")
#define inf INT_MAX
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))


typedef long long lint;

lint dx[8] = { 0,1,1,1,0,-1,-1,-1 },
dy[8] = { 1,1,0,-1,-1,-1,0,1 };

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


int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	string s; cin >> s; s.pop_back();
	if (s.length() % 2)s.pop_back();
	string t = s.substr(0, s.length()/2);
	lint ctr = s.length();
	while (t.length() != 0) {
		if (s == t + t) {
			co(ctr);
			gc();
			return 0;
		}
		t.pop_back();
		s.pop_back();
		s.pop_back();
		ctr -= 2;
	}
	co(0);
	gc();
}

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

int main(){
  int m,f,r;
  while(1){
    cin>>m>>f>>r;
    if(m==-1&&f==-1&&r==-1)break;
    if(m==-1||f==-1)cout<<"F"<<endl;
    else if(m+f>=80)cout<<"A"<<endl;
    else if(m+f>=65)cout<<"B"<<endl;
    else if(m+f>=50)cout<<"C"<<endl;
    else if(m+f>=30){
      if(r>=50)cout<<"C"<<endl;
      else cout<<"D"<<endl;
    }else cout<<"F"<<endl;
  }return 0;
}



Measured memory_bytes: 3068
#include <iostream>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main()
{
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    ll a[1001], b[1001], c[1001];
    for(int i = 0; i < x; i++){
        cin >> a[i];
    }
    for(int i = 0; i < y; i++){
        cin >> b[i];
    }
    for(int i = 0; i < z; i++){
        cin >> c[i];
    }
    sort(a, a + x);
    sort(b, b + y);
    sort(c, c + z);
    set<P> st;
    st.insert(make_pair(a[x - 1] + b[y - 1] + c[z - 1], (x - 1) * 1000000 + (y - 1) * 1000 + (z - 1)));
    for(int i = 0; i < k; i++){
        auto itr = st.end();
        itr--;
        cout << (*itr).first << endl;
        ll n = (*itr).second;
        ll s = n / 1000000;
        ll t = (n % 1000000) / 1000;
        ll u = n % 1000;
        if(s > 0){
            st.insert(make_pair(a[s - 1] + b[t] + c[u], n - 1000000));
        }
        if(t > 0){
            st.insert(make_pair(a[s] + b[t - 1] + c[u], n - 1000));
        }
        if(u > 0){
            st.insert(make_pair(a[s] + b[t] + c[u - 1], n - 1));
        }
        st.erase(itr);
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stdlib.h>

using namespace std;

int main() {
    int w,h,n;
    cin >> w >> h >> n;
    int x,y,a;
    int x1 = 0,y1 = 0;
    int x2 = w,y2 = h;
    for(int i = 0; i < n; i++) {
        cin >> x >> y >> a;
        if(a == 1) {
            x1 = max(x,x1);
        }else if(a == 2) {
            x2 = min(x,x2);
        }else if(a == 3) {
            y1 = max(y,y1);
        }else if(a == 4) {
            y2 = min(y,y2);
        }
    }
    cout << max(0,x2-x1)*max(0,y2-y1);
    return 0;
}



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

int main(){
 int W, H, x, y, r;
 cin >> W >> H >> x >> y >> r;
 if ( 0 <= x - r && x + r <= W && 0 <= y - r && y + r <= H ){
  cout << "Yes" << endl;
 } else {
  cout << "No" << endl;
 }
 return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<double, double> P;
//typedef pair<ll, P> T;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define revrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define f first
#define s second
#define pb push_back

const ll mod = 1000000007;
const ll INF = 100000000000010000;

//ll bit[200010];
//ll kai[1000010];

//void pres(double A, ll x = 20) { printf("%.20f\n", x); }

/*ll sum(ll i)
{
	i += 1;
	ll t = 0;
	while (i > 0)
	{
		t = max(bit[i], t);
		i -= i & -i;
	}
	return t;
}

void update(ll i, ll x)
{
	i += 1;
	while (i <= 200005)
	{
		bit[i] = max(bit[i], x);
		i += i & -i;
	}
}*/

void test() {
	cout << "888888888888888888888888" << endl;
}

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll y) {
	if (y == 0) return 1;
	if (y % 2 == 1) {
		return x * pow_mod(x, y - 1) % mod;
	}
	else {
		ll half = pow_mod(x, y / 2);
		return half * half % mod;
	}
}

ll div_mod(ll x) {
	return pow_mod(x, mod - 2);
}

/*ll com(ll x, ll y) {
	return kai[x] * div_mod(kai[y] * kai[x - y] % mod) % mod;
	//毎回オーダーlog(n)かかる
}

void kaijo() {
	kai[0] = 1;
	for (ll i = 1; i <= 1000005; i++) {
		kai[i] = kai[i - 1] * i % mod;
	}
}*/

ll N, K;
ll a[55][55];
ll bit[71][55][55];
ll pile[55][55];
ll tmp[55][55];
ll ans;
ll two;
map<ll, ll> mp;

void solve() {
	cin >> N >> K;
	rep(i, N)rep(j, N) cin >> bit[0][i][j];
	two = 1;
	for (int i = 1; i < 63; i++) {
		two *= 2;
		mp[two] = i;
		rep(j, N)rep(k, N)rep(l, N) {
			(bit[i][j][k] += bit[i - 1][j][l] * bit[i - 1][l][k] % mod) %= mod;
		}
	}
	rep(i, N) pile[i][i] = 1;
	while (K > 0) {
		rep(i, N)rep(j, N) {
			tmp[i][j] = pile[i][j];
			pile[i][j] = 0;
		}
		rep(i, N)rep(j, N)rep(k, N) {
			(pile[i][j] += tmp[i][k] * bit[mp[K & -K]][k][j] % mod) %= mod;
		}
		K -= K & -K;
	}
	rep(i, N)rep(j, N) (ans += pile[i][j]) %= mod;
	cout << ans << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	ll N;
	cin >> N;
}

Measured memory_bytes: 1792
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    int sum = A + B + C;
    cout << sum - max({A, B, C}) << endl;
    return 0;
}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int main() {
	int n;
	
	while (cin >> n, n) {
		vector< int > cnt(10, 0);
		
		for_(i,0,n) {
			int a;
			cin >> a;
			++cnt[a];
		}
		
		for_(i,0,10) {
			if (cnt[i] == 0) cout << "-";
			for_(j,0,cnt[i]) cout << "*";
			cout << endl;
		}
	}
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
int N,M;
vector<int> g[1010];
int col[1010];
bool used[1010];
bool flag;
void dfs(int v,int c){
	used[v]=true;
	col[v]=c;
	for(int i=0;i<g[v].size();i++){
		int u = g[v][i];
		if(used[u]){
			if(col[u]==col[v]){
				flag = false;
			}
		}else{
			dfs(u,-c);
		}
	}
}
bool solve(){
	cin >> N >> M;
	if(N+M==0)return false;
	for(int i=0;i<N;i++)g[i].clear();
	for(int i=0;i<M;i++){
		int u,v;
		cin >> u >> v;
		u--;v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	flag = true;
	memset(col,0,sizeof(col));
	memset(used,false,sizeof(used));
	dfs(0,1);
	if(!flag){
		cout << 0 << endl;
		return true;
	}
	int a=0,b=0;
	for(int i=0;i<N;i++){
		if(col[i]==1)a++;
		else b++;
	}
	vector<int> ans;
	if(a%2==0)ans.pb(a/2);
	if(b%2==0)ans.pb(b/2);
	
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout << ans.size() << endl;
	for(int i=0;i<ans.size();i++)cout << ans[i] << endl;
	return true;
}
int main(){
	while(solve()){}
	return 0;
}


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

char d(char c,int diff) {
    int ord = c - 'a';
    ord += diff;
    ord %= 26;
    return 'a' + ord;
}

int main() {
    string message;
    int n;
    while(cin>>n, n) {
        vector<int> a(n),b(n);
        cin>>message;

        for(int i=0; i<n; ++i) {
            cin>>a[i]>>b[i];
            a[i]--,b[i]--;
        }
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        for(int i=0; i<n; ++i) {
            message[a[i]] = d(message[a[i]],b[i]-a[i]);
            message[b[i]] = d(message[b[i]],b[i]-a[i]);
            swap(message[a[i]],message[b[i]]);
        }
        cout<<message<<endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main()
{
  int N, M;
  cin >> N >> M;
  vector<tuple<long long, int, int>> input(M);
  vector<string> IDs(M);
  vector<int> state_count(pow(10, 5), 1);

  rep(i, M)
  {
    int p;
    long long y;
    cin >> p >> y;
    input[i] = make_tuple(y, p, i);
  }
  sort(input.begin(), input.end());

  for (auto x : input)
  {
    int state_index = get<1>(x) - 1;
    int index = get<2>(x);
    string city_num = to_string(state_index + 1);
    string count_num = to_string(state_count[state_index]);
    string ID;
    rep(i, 6 - city_num.size())
    {
      ID += '0';
    }
    ID += city_num;
    rep(i, 6 - count_num.size())
    {
      ID += '0';
    }
    ID += count_num;

    IDs[index] = ID;
    state_count[state_index]++;
  }

  rep(i, M)
  {
    cout << IDs[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 10496
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

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

//START OF CODE ->->->->->->->

void solve()
{
    int a,b,c;
    cin>>a>>b>>c;

    cout<<max((int)0,c - (a-b))<<endl;
}

//END OF CODE ->->->->->->->->

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

    while(t--)
    {
        solve();
    }
    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);
    int m = sc.nextInt();
    int d = sc.nextInt();
    Main takahashiCalendar = new Main();
    System.out.println(takahashiCalendar.calc(m, d));
  }
  
  public int calc(int m, int d) {
    int sekinohi = 0;
    for(int day = 22 ; day <= d ; day++) {
      int d1 = day % 10;
      int d10 = day / 10;
      if (d1 >= 2 && d10 >= 2 && (d1 * d10) <= m) {
        sekinohi++;
      }
    }
    return sekinohi;
  }
}

Measured memory_bytes: 23124
#include "bits/stdc++.h"
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
const int MOD=1000000007;
#define endl "\n"
#define fst first
#define snd second
const int UNDEF = -1;
const int INF=1<<30;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;typedef vector<ll> vll;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi> vvi;
#ifdef ONLINE_JUDGE
#define assert(...) /* nothing */
#endif
#define DEBUG_CAT
#ifdef DEBUG_CAT
#define dbg(...)   printf( __VA_ARGS__ )
#else 
#define dbg(...)   /****nothing****/
#endif
void solve(long long N, long long K){
	printf("%lld\n",N-K+1);
}

int main(){	
	long long N;
	long long K;
	scanf("%lld",&N);
	scanf("%lld",&K);
	solve(N, K);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int h[n];
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    
    int ans = 0;
    int curMax = 1;
    for (int i = 0; i < n; i++) {
        if (h[i] >= curMax) {
            ans++;
            curMax = h[i];
        }
    }

    cout << ans;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    int i;
    int w[N];
    int s1=0;
    int s2=0;
    int sum[N];
    int count =0;
    for(i=0;i<N;i++)
    {
        cin >> w[i] ;
    }
    //sort(w,w+N);
    while(count <N){
    for(i=0;i<N;i++)
    {
        if(i<=count){
        s1 += w[i];
        }
        else
        {
            s2+= w[i];
        }
    }
    sum[count] = abs(s1-s2);
    count ++;
    s1=0;
    s2=0;
    }
    sort(sum,sum+N);
    cout << sum[0] << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
inf = float("INF")
dp = [[inf] * (n + 1) for _ in range(n)]
for i in range(n - 1): a[i + 1] += a[i]
a.insert(0, 0)
f = [[0] * (n + 1) for i in range(n)]
for i in range(n):
    fi = f[i]
    for k in range(i + 1, n + 1):
        fi[k] = a[k]-a[i]
def time(l, m, r, res, x, fl):
    sumlm = fl[m]
    summr = f[m][r]
    c = 0
    while sumlm or summr or c:
        lm = sumlm % 10
        mr = summr % 10
        res += lm * mr + c
        if res >= x:
            return x
        c =  (lm + mr + c > 9)
        sumlm //= 10
        summr //= 10
    return res
for i in range(n):
    dp[i][i + 1] = 0

for Ra in range(1,n+1):
    for l in range(n-Ra+1):
        r = l+Ra
        dpl = dp[l]
        x = dpl[r]
        fl = f[l]
        for m in range(l+1, r):
            x = time(l, m, r,dpl[m] + dp[m][r], x, fl)
        dpl[r] = x

print(dp[0][n])



Measured memory_bytes: 9836
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
const int MOD = 1000000007;
int INF = numeric_limits<int>::max() / 2;

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


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

  int N, K;
  cin >> N >> K;
  int A[N];
  rep(i,N) cin >> A[i];
  sort(A, A+N);

  COMinit();

  int ans = 0;
  for(int i=0;i<N;i++){
    if(i < (K-1)) continue;
    ans += COM(i, K-1) * A[i];
    ans %= MOD;
  }
  for(int i=0;i<N;i++){
    if((N-K) < i) continue;
    ans += MOD;
    int W = (COM(N-i-1, K-1) * A[i]);
    W %= MOD;
    ans -= W;
    ans %= MOD;
  }

  cout << ans << endl;

}

Measured memory_bytes: 13056
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for i in range(Q)]

qs = [[] for _ in range(N)]
for i,(l,r) in enumerate(LR):
    qs[l-1].append((i,r-1))

from collections import defaultdict
hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1,-1,-1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bit = BinaryIndexedTree(N)

ans = [None] * Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l], -1)
    for i,r in qs[l]:
        ans[i] = r-l+1 + bit.sum(l,r+1)

print(*ans, sep='\n')

Measured memory_bytes: 299912
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        boolean[] ok = new boolean[n];
        for (int i = 0; i < k; i++) {
            int max = sc.nextInt();
            for (int j = 0; j < max; j++) {
                int num = sc.nextInt() - 1;
                ok[num] = true;
            }
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!ok[i]) count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 46460
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <time.h>
using namespace std;


int main(){
	string S;
	cin >> S;

	if (S.size() == 2)
		cout << S << endl;
	else{
		for (int i = 2; i >= 0; --i){
			cout << S[i];
		}
		cout << endl;
	}
		
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

ll gcd(ll x, ll y){
    if (y == 0) return x;
    return gcd(y, x % y);
}

ll lcm(ll x, ll y){
    ll d = gcd(x, y);
    return x * y / d;
}

int main() {
    ll n, m;
    cin >> n >> m;
    VL a(n);
    REP(i,n) a[i] = in() / 2;
    ll x = 1;
    REP(i,n){
        x = lcm(x, a[i]);
        if (x > m){
            cout << 0 << endl;
            return 0;
        }
    }
    REP(i,n){
        ll d = x / a[i];
        if (d % 2 == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << m / x - m / (2 * x) << endl;
    return 0;
}


Measured memory_bytes: 1024
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

is_broken = [False for _ in range(N + 1)]
for _ in range(M):
    a = int(input())
    is_broken[a] = True

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

for i in range(1, N + 1):
    if is_broken[i]:
        continue
    if i == 1:
        dp[i] += dp[i - 1]
    else:
        dp[i] += dp[i - 1] + dp[i - 2]

    dp[i] = dp[i] % MOD

print(dp[N])


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

int main()
{
  long long X, K, D;

  cin >> X >> K >> D;

  X = abs(X);

  long long count = X / D;

  if (count >= K)
  {
    cout << X - (D * K) << endl;
  }
  else
  {
    X %= D;
    long long sub = K - count;
    if (sub % 2 == 0)
    {
      cout << X << endl;
    }
    else
    {
      cout << abs(X - D) << endl;
    }
  }
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
ll w[101];
ll val[101];
ll dp[101][100001];
ll func(ll n,ll W)
{
    if(n==0 || W==0)
    return 0;
    if(dp[n][W]!=-1)
    return dp[n][W];
    if(W>=w[n-1])
    return dp[n][W]=max(val[n-1]+func(n-1,W-w[n-1]),func(n-1,W));
    else
    return dp[n][W]=func(n-1,W);
}
int main() {
	ll n,W;
	cin>>n>>W;

	for(int i=0;i<n;i++)
	{
	    cin>>w[i];
	    cin>>val[i];
	}
	memset(dp,-1,sizeof(dp));

	cout<<func(n,W)<<"\n";
	return 0;
}


Measured memory_bytes: 82496
#include <iostream>
#include <vector>
#include <string>

using ll = long long int;
using namespace std;

#define FOR(i,N) for(int i=0;i<N;i++)

int main() {
    int N;
    cin >> N;
    
    int ns = 1;
    FOR(i, N) {
        int k;
        cin >> k;
        if (k == ns) {
            ns++;
        }
    }

    if (ns == 1) {
        cout << "-1";
    }
    else {
        cout << N - (ns - 1);
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
class Dice {
    public:
        int num[6];
        void turn (char c) {
            int temp;
            if(c == 'E') {
                temp = num[0];
                num[0] = num[3];
                num[3] = num[5];
                num[5] = num[2];
                num[2] = temp;
            }
            else if(c == 'N') {
                temp = num[0];
                num[0] = num[1];
                num[1] = num[5];
                num[5] = num[4];
                num[4] = temp;
            }
            else if(c == 'S') {
                temp = num[0];
                num[0] = num[4];
                num[4] = num[5];
                num[5] = num[1];
                num[1] = temp;
            }
            else if(c == 'W') {
                temp = num[0];
                num[0] = num[2];
                num[2] = num[5];
                num[5] = num[3];
                num[3] = temp;
            }
            else if(c == 'R') {
                temp = num[1];
                num[1] = num[2];
                num[2] = num[4];
                num[4] = num[3];
                num[3] = temp;
            }
        };
};
int main(void){
    Dice dice;
    for(int i = 0;i < 6;i++)
        scanf("%d", &dice.num[i]);
    int n;
    cin >> n;
    while(n--) {
        int top, front;
        cin >> top >> front;
        
        if(dice.num[3] == top)
            dice.turn('E');
        else if(dice.num[2] == top)
            dice.turn('W');
        while(dice.num[0] != top)
            dice.turn('N');
        while(dice.num[1] != front)
            dice.turn('R');
        cout << dice.num[2] << endl;
    }
    
}



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

int main() {
  int n;
  cin>>n;
  vector<int> vec(200010);
  vector<int> veC(200010);

  
  
  for(int i = 2; i <= n; i++)
    cin >> vec[i];
  
  for(int i = 2; i <= n; i++)
      veC[vec[i]]++;
  
  for(int i = 1; i <= n; i++)
    cout << veC[i] << endl;
}


Measured memory_bytes: 4848
#include <iostream>
    #include <string>
    using namespace std;
     
    int main() {
        string s;
        cin >> s;
        int value = 700;
        if (s[0] == 'o') value += 100;
        if (s[1] == 'o') value += 100;
        if (s[2] == 'o') value += 100;
        cout << value << endl;
    }

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(N):
  ans += B[A[i] - 1]
  if i != 0 and A[i - 1] == A[i] - 1:
    ans += C[A[i] - 2]
print(ans)

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

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> q;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve(){
	llint n;
	cin >> n;
	llint dp[n+1];
	memset(dp,0,sizeof(dp));
	for(llint i=1;i<=n;i++){
		llint t=i;
		for(llint j=2;j<=n;j++){
			while(t%j==0){
				dp[j]++;
				t/=j;
			}
		}
	}
	llint ans=1;
	for(llint i=2;i<=n;i++){
		ans*=(dp[i]+1);
		ans%=mod;
	}
	cout << ans << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int n; cin >> n;
	vector<int> a(n), l(n);
	for (int i = 0; i < n; ++i) {
		int tmp;
		cin >> tmp;
		a[i] = -tmp;
	}
	l[0] = a[0];
	int length = 1;
	for (int i = 1; i < n; ++i) {
		if (l[length - 1] <= a[i]) l[length++] = a[i];
		else *upper_bound(l.begin(), l.begin() + length, a[i]) = a[i];
	}
	cout << length << endl;

	return 0;
}

Measured memory_bytes: 1532
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;


typedef vector<ll> Vec;
typedef vector<Vec> Mat;
ll const MOD = 1e9+7;
Mat operator * (Mat const& A, Mat const& B) {
  Mat ret(A.size(), Vec(B[0].size()));
  rep(i,A.size())rep(k,B.size())rep(j,B[0].size())ret[i][j]=(ret[i][j]+A[i][k]*B[k][j])%MOD;
  return ret;
}
Mat pow(Mat A, ll n) {
  Mat ret(A.size(),Vec(A.size()));
  rep(i,A.size())ret[i][i]=1;
  for(;n>0;n>>=1) {
    if(n&1)ret=ret*A;
    A=A*A;
  }
  return ret;
}

void Main() {
  ll n,m;
  cin >> n >> m;
  Mat a;a.resize(n,Vec(n,0));
  rep(i,n)rep(j,n) R a[i][j];
  a=pow(a,m);
  ll ans=0;
  rep(i,n)rep(j,n) {
    ans+=a[i][j];
    ans%=MAX;
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 384
#include <iostream>
#include <limits.h>

using namespace std;

int main(){
  int n, max=0, min=INT_MAX;
  cin >> n;
  for(int i=0;i<n;i++){
    int a; cin >> a;
    if(max<a){max=a;}
    if(min>a){min=a;}
  }
  cout << max - min << endl;
}

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

int main()
{
	int a;
	while (cin >> a, a) {
		bool b[258][258];
		for (int c = 0; c < a; c++) {
			string s; cin >> s;
			for (int d = 0; d < a; d++) {
				b[c][d] = s[d] == '1';
			}
		}
		int MAX = 0;
		for (int e = 0; e < a; e++) {
			for (int f = 0; f < a; f++) {
				for (int h = -1; h < 2; h++) {
					for (int i = -1; i < 2; i++) {
						if (h||i) {
							int g = 0;
							for (int j = 0; e + h*j >= 0 && e + h*j < a&&f + i*j >= 0 && f + i*j < a; j++) {
								if (b[e + h*j][f + i*j]) { g++; MAX = max(MAX, g); }
								else g = 0;
							}
						}
					}
				}
			}
		}
		cout << MAX << endl;
	}
}

Measured memory_bytes: 3192
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;
unsigned long long mod = 1000000000 + 7;

int int_vector_find(std::vector<int> vec, int num) {
	auto itr = std::find(vec.begin(), vec.end(), num);
	int index = std::distance(vec.begin(), itr);

	if (index != vec.size()) {
		return 1;
	}
	else {
		return 0;
	}
}

int h, w;
char table[1010][1010];
int dp[1010][1010];

int main() {
	std::cin >> h >> w;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			std::cin >> table[i][j];
		}
	}
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (table[i][j] == '#') {
				dp[i][j] == 0;
			}
			else if (i == 1 && j == 1) {
				dp[i][j] = 1;
			}
			else if (i == 1){
				dp[i][j] = dp[i][j - 1];
			}
			else if (j == 1) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mod;
			}
		}
	}
	std::cout << dp[h][w] << std::endl;
}

Measured memory_bytes: 5248
/* 
	Author: ankrypt
*/

#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;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define fi(a, b, c, d) for(int a = b; i < c; i += d)
#define fl(a, b, c, d) for(ll a = b; i < c; i += d)
#define quit exit(0)

ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
string S, R, T;


int main() {
	cin >> S;
	cin >> R >> T;
	if(S[S.size() - 1] == R[0] && R[R.size() - 1] == T[0]) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}
	return 0;
}
/*
	Powered by Buggy Plugin
*/




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

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define FI first
#define SE second
using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
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(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}

double cross(const Pd &o, const Pd &a, const Pd &b){
  return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}

vector<Pd> convex_hull(vector<Pd> vec){
  int n = vec.size(), k = 0;
  if(n < 3)return vec;

  vector<Pd> ch(2 * n);
  sort(vec.begin(), vec.end());

  // lower
  for(int i = 0; i < n; i++){
    while(k >= 2 && cross(ch[k-2], ch[k-1], vec[i]) < 0.)k--;
    ch[k++] = vec[i];
  }

  // upper
  for(int i = n - 1, t = k + 1; i > 0; --i){
    while(k >= t && cross(ch[k-2], ch[k-1], vec[i-1]) < 0.)k--;
    ch[k++] = vec[i-1];
  }

  ch.resize(k - 1);
  return ch;

}

bool comp(const Pd &a, const Pd &b){
  if(a.SE != b.SE)return a.SE < b.SE;
  return a.FI < b.FI;
}

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<Pd> vec(n);
  rep(i, n){
    cin >> vec[i].FI >> vec[i].SE;
  }
  auto v = convex_hull(vec);
  auto vv = v;
  sort(all(vv), comp);
  int i = 0;
  for(; i < sz(v); i++)if(v[i] == vv[0])break;
  cout << sz(v) << endl;
  FOR(j, i, sz(v))cout << v[j].FI << " " << v[j].SE << endl;
  rep(j, i)cout << v[j].FI << " " << v[j].SE << endl;
	return 0;
}



Measured memory_bytes: 9084
n, c = input().split()
n = int(n)
c = int(c)
x = [0]
v = [0]
gs1 = [0]
gs2 = [0]
gs3 = [0]
gs4 = [0]
s = 0
for i in range(n):
    xx, vv = input().split()
    xx = int(xx)
    vv = int(vv)
    x.append(xx)
    v.append(vv)
    s += vv
    f = s - xx
    gs1.append(max(gs1[-1], f))
    f = s - 2 * xx
    gs2.append(max(gs2[-1], f))
s = 0
for i in range(-1, -n - 1, -1):
    s += v[i]
    f = s - (c - x[i])
    gs3.append(max(gs3[-1], f))
    f = s - 2 * (c - x[i])
    gs4.append(max(gs4[-1], f))
ans = 0
for i in range(n + 1):
    ans = max(ans, gs1[i] + gs4[n - i], gs2[i] + gs3[n - i])
print(ans)

Measured memory_bytes: 23620