akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for ucx in range(lcx + k - 1, n):
        for lcy in range(n - k + 1):
            for ucy in range(lcy + k - 1, n):
                # print(li, ui, lj, uj)
                # print(acm[ui][uj], acm[ui][lj - 1], acm[li - 1][uj], acm[li - 1][lj - 1])
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm[lcx - 1][lcy - 1] >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  int n;
  cin >> n;
  int now_h;
  cin >> now_h;
  int count = 0;
  int ans = 0;
  rep(i,n-1){
    int h;
    cin >> h;
    if(now_h >= h){
      count++;
    }else{
      count = 0;
    }
    ans = max(count, ans);
    now_h = h;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
struct Node{
   int parent,left,right,sibling,depth,height;
};
const int NIL = -1;

int  setHeight(Node A[],int n){
   int h1 = 0, h2 = 0;
   if(A[n].left != NIL )
   		h1= setHeight(A, A[n].left)+1;
   	if(A[n].right != NIL )
   		h2 = setHeight(A, A[n].right) + 1;
   	return A[n].height = ( h1 > h2 ? h1 : h2 );
}

void setDepth(Node A[],int n,int d){
    
    A[n].depth=d;
	if ( A[n].left != NIL ) setDepth ( A, A[n].left,d+1);
	if ( A[n].right != NIL ) setDepth ( A, A[n].right,d+1);
}
void print(Node A[],int i){
	cout<<"node "<<i;
	cout<<": parent = "<<A[i].parent;
	cout<<", sibling = "<<A[i].sibling;
    
    int degree=0;
    if ( A[i].right != NIL ) degree++;
    if ( A[i].left != NIL ) degree++;
    cout<<", degree = "<<degree<<", ";
    
    cout<<"depth = "<< A[i].depth << ", " ;
    cout<<"height = "<< A[i].height << ", ";
    if(A[i].parent == NIL ) cout<<"root";
    else if ( A[i].right == NIL && A[i].left == NIL ) cout<<"leaf";
    else cout<<"internal node";
    cout<<endl;
}


main(){
	int n;
	cin>>n;
	Node *A = new Node[n];
   int v,left,right;
   for(int i=0;i<n;i++) { 
   		A[i].left = A[i].right = A[i].parent = A[i].sibling=NIL;
   		A[i].height = A[i].depth = 0;
   }
   for(int i=0;i<n;i++){
   		cin>>v>>left>>right;
   		A[v].left=left;
   		A[v].right=right;
   		if(left != NIL)	{ 
   			A[left].parent = v;
   			A[left].sibling = right;
   		}
   		if(right != NIL) {
   		 	A[right].parent = v;
   		 	A[right].sibling=left;
   		}

   }
   int root=0;
   for ( int i = 0; i < n; i++ ) {
   	   if ( A[i].parent == NIL ) root = i;
   }
   setDepth(A, root, 0 );
   setHeight(A, root);
   for(int i=0;i<n;i++) print(A,i);
	return 0;
}


Measured memory_bytes: 3092
#include<stdio.h>
#define N 25
#define NIL -1

typedef struct{

  int pid;//親のID
  int leftc;//自分の子供の一番左の子
  int rights;//自分のすぐ右隣の兄弟
  
}Rooted;

int sibling(int);
int degree(int);
int depth(int);
int height(int);
int type(int);

Rooted data[N];

int main(){

  int i,j,t,n,l,r,id,root;

  scanf("%d",&n);//接点の数

  for(i=0;i<N;i++){
    data[i].pid=NIL;
    data[i].leftc=NIL;
    data[i].rights=NIL;
  }

  for(i=0;i<n;i++){

    scanf("%d%d%d",&id,&l,&r);

    data[l].pid=id;
    data[r].pid=id;
    data[id].leftc=l;
    data[l].rights=r;

  }//for


  for(i=0;i<n;i++){

    printf("node %d: ",i);

    printf("parent = %d, ",data[i].pid);

    printf("sibling = %d, ",sibling(i));

    printf("degree = %d, ",degree(i));

    printf("depth = %d, ",depth(i));

    printf("height = %d, ",height(i));
    
    t=type(i);
    if(t==-1) printf("root\n");
    else if(t==0) printf("leaf\n");
    else printf("internal node\n");

  }//for

  return 0;
  
}

int sibling(int i){

  if(data[i].pid==NIL) return NIL;
  
  if(data[data[i].pid].leftc==i){

    return data[i].rights;
    
  }else{

    return data[data[i].pid].leftc;
    
  }
  
}

int degree(int i){
  
  int deg=0,j;

  for(j=0;j<N;j++){

    if(data[j].pid==i){
      deg++;
    }
    
  }
 
  return deg;
  
}

int depth(int i){

  int dep=0;

  while(data[i].pid!=NIL){

    i=data[i].pid;
    dep++;
    
  }//while

  return dep;
  
}

int height(int i){

  int h=-1;
  int temp,j;

  for(j=0;j<N;j++){

    if(data[j].pid==i){

      temp=height(j);

      if(temp>h){
	h=temp;
      }
      
    }//if
    
  }//for

  h++;
  return h;

}

int type(int i){
  if(data[i].pid==-1) return -1;
  else if(height(i)==0) return 0; 
  else return 2;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using longlong=long long;

int main(){
    std::cin.tie(nullptr);std::cin.sync_with_stdio(false);
    std::string s;std::cin>>s;
    bool a=false,b=false,c=false;
    for(char x:s){
        if(x=='a')a=true;
        if(x=='b')b=true;
        if(x=='c')c=true;
    }
    std::cout<<(a&&b&&c?"Yes":"No")<<std::endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    for (int i = 1; i < n-1; i++) {
        if (p[i-1] < p[i] && p[i] < p[i+1] || p[i-1] > p[i] && p[i] > p[i+1]) ans++;
    }
    cout << ans << endl;
    return 0;
}


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

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

int main() {

    int n; cin >> n;
    set<string> se;

    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        se.insert(s);
    }

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

Measured memory_bytes: 19252
temp1 = input()
r1 = temp1.split()
for j in range(len(r1)):
    r1[j] = int(r1[j])
temp2 = input()
r2 = temp2.split()
for j in range(len(r2)):
    r2[j] = int(r2[j])
temp3 = input()
r3 = temp3.split()
for j in range(len(r3)):
    r3[j] = int(r3[j])

r_d1 = [i for i in range(3)]
r_d2 = [i for i in range(3)]
for i in range(3):
    r_d1[i] = r2[i]-r1[i]
    r_d2[i] = r3[i]-r1[i]
if r_d1.count(r_d1[0]) == 3:
    flag = 1
else:flag = 0

if r_d2.count(r_d2[0]) == 3:
    flag = flag*1
else:flag = flag*0

if flag == 1:
    print("Yes")
else:print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
ll t;
ll n,m;
ll f[100005];
int main() {
slld(n);slld(m);
f[0]=1;
for(ll i=1;i<=100000;i++)
    f[i]=(f[i-1]*i)%MOD;
if(abs(n-m)>1)
    pss("0\n");
else
{
    ll ans=((f[n]*f[m])%MOD);
    if(n==m)ans*=2;
    plld(ans%MOD);
}
    return 0;
           } 


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.length();
    bool ok = true;
    for(int i=0;i<(n-1)/2&&ok;++i) {
        if(s[i] != s[(n-1)/2-1-i]) {
            ok = false;
        }
        if(s[(n+1)/2+i] != s[n-1-i]) {
            ok = false;
        }
    }
    for(int i=0;i<n&&ok;++i) {
        if(s[i] != s[n-1-i]) ok = false;
    }

    cout << (ok?"Yes":"No") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} // input vector
#include <iomanip>

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

double x1, x2, x3, y1, y2, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

double a, b, c, r, d, x;
a = hypot(x1-x2,y1-y2);
b = hypot(x2-x3,y2-y3);
c = hypot(x3-x1,y3-y1);
r = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/(a+b+c);
d = max(a,max(b,c));
x = d/(2+d/r);

cout << fixed << setprecision(15);
cout << x << "\n";

return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	if(s.length()+1==t.length()){
		for(int i=0;i<s.length();i++){
			if(s[i]!=t[i]){
				cout<<"No\n";
				return 0;
			}
		}
		cout<<"Yes\n";
		return 0;
	}
	cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3568
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

ll mod(ll a) {
	if (a > 0) return a % MOD;
	if (a % MOD == 0) return 0;
	ll x = -a / MOD + 1;
	a += x * MOD;
	return a % MOD;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
template <typename T> void dump(T x) { cout << x << endl; }
void dumpf(double x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
// ll dx[4] = {1, 0, -1, 0};
// ll dy[4] = {0, 1, 0, -1};
// ll pas[5001][5002];
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll use[10] = {INF, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[10002];

int main() {
	IOS();
	ll n, m;
	cin >> n >> m;
	map<ll, ll> mp;
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		for (int j = 0; j < k; ++j) {
			int a;
			cin >> a;
			mp[a]++;
		}
	}
	ll ans = 0;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		if (it->second == n) ans++;
	}
	dump(ans);
}

Measured memory_bytes: 384
/*************************************************************************
  >         File: D.cc
  >       Author: Riho.Yoshioka
  >         Mail: riho.yoshioka@yandex.com
  > Created Time: Sun 21 Aug 2016 09:00:08 PM CST
*************************************************************************/
#include <bits/stdc++.h>
using LL = long long;
const int N = 1e5 + 5;
int visited[N], p[N], tot;

void Prime() {
  for (int i = 2; i < N; i++) {
    if (!visited[i]) p[tot++] = i;
    for (int j = 0; j < tot && i * p[j] < N; j++) {
      visited[i * p[j]] = p[j];
      if (i % p[j] == 0) break;
    }
  }
}

template<class T>
void in(T& x) {
  char c;
  while (!isdigit(c = getchar()) && c != '-');
  bool flag = (c == '-');
  if (flag) c = getchar();
  x = c - '0';
  while (isdigit(c = getchar())) x = x * 10 + c - '0';
  if (flag) x *= -1;
}

template<class T>
void out(T x) {
  if (x < 0) putchar('-'), x *= -1;
  static int length = 0, bit[20];
  for (; x > 0; x /= 10) bit[length++] = x % 10;
  if (!length) bit[length++] = 0;
  while (length--) putchar(bit[length] + '0');
  putchar('\n');
}

std::vector<LL> numbers;
std::map<LL, LL> match;

inline int Count(LL x) {
  return std::upper_bound(numbers.begin(), numbers.end(), x) - std::lower_bound(numbers.begin(), numbers.end(), x);
}

int main() {
  Prime();
  int n;
  in(n);
  int zero = 0;
  for (int i = 0; i < n; i++) {
    LL x;
    in(x);
    LL now = 1, pair = 1;
    for (int j = 0; j < tot && 1LL * p[j] * p[j] * p[j] <= x; j++) if (x % p[j] == 0) {
      int cnt = 0;
      while (x % p[j] == 0) {
        x /= p[j];
        cnt++;
      }
      cnt %= 3;
      for (int i = 0; i < cnt; i++) now *= p[j];
      for (int i = 0; i < (3 - cnt) % 3; i++) pair *= p[j];
    }
    if (x == 1 && now == 1) {
      zero++;
    } else if (x == 1) {
      numbers.emplace_back(now);
      match[now] = pair;
    } else if (x != 1) {
      int rt = sqrt(x + 0.5);
      if (1LL * rt * rt == x) {
        now *= x;
        pair *= rt;
      } else {
        if (x >= N) continue;
        now *= x;
        pair *= x * x;
      }
      numbers.emplace_back(now);
      match[now] = pair;
    }
  }
  std::sort(numbers.begin(), numbers.end());
  int nouse = 0;
  for (auto it = numbers.begin(); it != numbers.end(); ) {
    auto number = *it;
    nouse += std::min(Count(number), Count(match[number]));
    it = std::upper_bound(numbers.begin(), numbers.end(), number);
  }
  out(n - zero - nouse / 2 + (zero > 0));
  return 0;
}


Measured memory_bytes: 6644
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(i) i.begin(),i.end()
template<typename T=ll>
using v =vector<T>;
template<typename T=ll>
using vv = vector<v<T>>;
using p = pair<ll,ll>;
const ll INF = (ll)1e9;
template<typename T> T chmin(T &a,T b){a=min(a,b);}
template<typename T> T chmax(T &a,T b){a=max(a,b);}

int main(){
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    cout << (k%2==0?a-b:b-a);    

    return 0;
}

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

int main(){
  int a,b,c,d,e,Amax,Amin,k;
  cin >> a >> b >> c >> d >> e >> k;
  Amax=max(a,max(b,max(c,max(d,e))));
  Amin=min(a,min(b,min(c,min(d,e))));
  if(Amax-Amin<=k)cout << "Yay!" <<endl;
  else cout << ":(" << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long 
#define vi vector<int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pb push_back
#define f(i,a,b) for(i=a;i<b;i++)
using namespace std;

int main()
{
    int a,b,t;
    cin>>a>>b>>t;
    cout<<(t/a)*b;
}

Measured memory_bytes: 3632
#include <iostream>
#include <functional>
#include <algorithm>
#include <utility>
using namespace std;

int main(){
	int N, M;
	cin >> N >> M;
	int A[N], B[N];
	for(int i=0;i<N;i++){
		cin >> A[i] >> B[i];
	}
	pair<long int,long int> buy[N];
	for(int i=0;i<N;i++){
		buy[i].first = A[i];
		buy[i].second = B[i];
	}
	sort(buy, buy+N);
	long int sum = 0;
	for(int i = 0;i<N;i++){
		if(M <= 0) break;
		if(M > buy[i].second){
			M -= buy[i].second;
			sum += buy[i].first * buy[i].second; 
		}
		else{
			sum += M * buy[i].first;
			M = 0;
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 2560
import Control.Applicative

f :: Int -> Int -> String
f a b
    | a > b  = "a > b"
    | a < b  = "a < b"
    | a == b = "a == b"

main :: IO ()
main = do
    [a,b]  <- map read . words <$> getLine
    putStrLn $ f a b
    


Measured memory_bytes: 3664
#include "bits/stdc++.h"
#define int long long
#define mii map<int,int>
#define inf 1000000007 //10^9+7
#define for(i,n) for(int i=0;i<n;i++)
#define sort(vec) sort(vec.begin(),vec.end());
#define rever(vec) reverse(vec.begin(),vec.end());
#define unsort(vec) sort(vec); rever(vec);
#define in(a,b,vec,n) a n; cin>>n; vector<b>vec(n);
#define gcd __gcd
using namespace std;

signed main() {
  int n,h,w;
  cin>>n>>h>>w;
  int a=n-w+1;
  int b=n-h+1;
  cout<<a*b<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  double x;
  cin >> x;
  long long max_x = pow(x * 2, 0.20) + 1;
  long long i = 10e6;
  while(true){
    long long a = (long long)pow(i,5);
    long long c = x-a;
    long long b = pow((double)c,0.2);
    int bi = (int) b;
    if(pow(b,5)+a == x){
      cout << i << " " << -bi << endl;
      break;
    }
    i--;
  }
}


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

int main(void){
    int h = 0, n = 0;
    int a = 0;

    scanf("%d%d", &h, &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &a);
        h -= a;
        if(h <= 0){
            printf("Yes\n");
            return 0;
        }
    }

    printf("No\n");


    return 0;

} 


Measured memory_bytes: 256
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}

const int64 MOD = 1e9 + 7;

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

  int64 n, m; cin >> n >> m;

  bool broken[101010] = {};
  vector<int64> a(m);
  rep(i, m) {
    cin >> a[i];
    broken[a[i]] = true;
  }

  for (int i = 0; i < m - 1; ++i) {
    if (a[i + 1] - a[i] == 1LL) {
      print(0); return 0;
    }
  }

  int64 dp[101010] = {};

  if (broken[1]) {
    dp[1] = 0LL;
  } else {
    dp[1] = 1LL;
  }

  dp[0] = 1LL;

  for (int i = 2; i <= n; ++i) {
    if (broken[i]) {
      dp[i] = 0LL;
    } else {
      dp[i] = dp[i - 1] + dp[i - 2];
      dp[i] %= MOD;
    }
  }

  int64 ans = dp[n] % MOD;
  print(ans);

  return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string reduce(string s)
{
	auto pos = s.find("()");
	if (pos == string::npos) {
		return s;
	}
	return reduce(s.erase(pos, 2));
}

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

	string T = reduce(S);
	int l = count(T.begin(), T.end(), '(');
	int r = count(T.begin(), T.end(), ')');
	
	string ans;
	ans.append(r, '(').append(S).append(l, ')');
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 100005
#define maior 100000
using namespace std;

int dp[MAXN];
int n;
vector<int> v;

int solve(int i)
{
	if(dp[i] >= 0)
	{
		return dp[i];
	}

	int res1 = abs(v[i] - v[i-1]) + solve(i - 1);
	int res2 = abs(v[i] - v[i-2]) + solve(i - 2);

	dp[i] = min(res1, res2);

	return dp[i];

}





int main()
{
    
	int num;
	cin >> n;
	
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; ++i)
	{
		cin >> num;
		v.push_back(num);
	}

	dp[0] = 0;
	dp[1] = abs(v[0] - v[1]); 

	cout << solve(n - 1) << endl;



    return 0;
}

Measured memory_bytes: 8772
import numpy as np
import itertools

a = int(input())

odd_list = np.arange(1, a+1, 2)
even_list = np.arange(2, a+1, 2)
count = 0
for odd, even in itertools.product(odd_list, even_list):
    #print(odd,even)
    count += 1
    
print(count)

Measured memory_bytes: 12488
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		long c = Long.parseLong(str[1]);
		long k = Long.parseLong(str[2]);

		Person p[] = new Person[n];
		for (int i = 0; i < n; i++) {
			long t = Long.parseLong(br.readLine());

			p[i] = new Person(t, t + k);
		}

		Arrays.sort(p);
		long ans = 0;

		for (int i = 0; i < n;) {
			long end = p[i].end;
			long count = 1;
			int j = i + 1;

			while (count < c && j < n) {

				if (p[j].end >= end && p[j].start <= end) {
					count++;
					j++;
				} else {
					break;
				}
			}
			ans++;
			i = j;
		}

		System.out.println(ans);
	}
}

class Person implements Comparable<Person> {
	long start;
	long end;

	public Person(long start, long end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Person p) {
		return Long.compare(this.end, p.end);
	}
}


Measured memory_bytes: 46684
#include <iostream>

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << "Draw";
		return 0;
	}
	if (a == 1 && b != 1) {
		cout << "Alice";
		return 0;
	}
	if (a != 1 && b == 1) {
		cout << "Bob";
		return 0;
	}
	if (a > b) {
		cout << "Alice";
	} else {
		cout << "Bob";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long n,w;
    cin >> n >> w;
    vector<long long> weight(n);
    vector<long long> value(n);
    vector<vector<long long>> maximum(n+1, vector<long long> (w+1));

    for (long long i = 0; i < n; i++){
        cin >> weight.at(i) >> value.at(i);
    }
    
    for (long long i = 0; i < w; i++){
        maximum.at(0).at(i) = 0;
    }
    for (long long i = 0; i < n; i++){
        maximum.at(i).at(0) = 0;
    }
    for (long long i = 0; i < n; i++){
        for (long long j = 0; j < w; j++){
            if(j+1 - weight.at(i) >= 0) {
                maximum.at(i+1).at(j+1) = max(maximum.at(i).at(j+1 - weight.at(i)) + value.at(i), maximum.at(i).at(j+1));          
            }
            else {
                maximum.at(i+1).at(j+1) = maximum.at(i).at(j+1);
            }
        }
    }
    printf("%lld\n",maximum.at(n).at(w));
}


Measured memory_bytes: 80256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC043A
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, n, s;

            n =int.Parse(Console.ReadLine());

            s = 0;
            for ( i = 1; i <= n; i++)
                s = s + i;

            Console.WriteLine(s);

            Console.ReadKey();
        }
    }
}


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

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

int N = 0;

void maxHeap(vl& a, int x){
	int l = x*2;
	int r = x*2+1;
	int largest = 0;
	if(l <= N && a[l] > a[x]){
		largest = l;
	}else{
		largest = x;
	}
	if(r <= N && a[r] > a[largest]) largest = r;
	if(largest != x){
		ll y = a[x];
		a[x] = a[largest];
		a[largest] = y;
		maxHeap(a, largest);
	}
}

void increaseKey(vl& a, int i, ll key){
	if(a[i] >= key) return;
	a[i] = key;
	while(i >1 && a[i/2] < a[i]){
		int y = a[i];
		a[i] = a[i/2];
		a[i/2] = y;
		i /= 2;
	}
}

void insert(vl& a, ll key){
	N++;
	a[N] = -1e10;
	increaseKey(a, N, key);
}

ll extract(vl& a){
	ll root = a[1];
	a[1] = a[N];
	N--;
	maxHeap(a, 1);
	return root;
}

int main(){
	vl a(2000001);
	string s;
	ll k;
	while(1){
		cin >> s;
	if(s[0] == 'i'){
		cin >> k;
		insert(a, k);
	}
	if(s == "extract"){
		cout << extract(a) << endl;
	}
	if(s == "end"){
		return 0;
	}
}
}



Measured memory_bytes: 18228
#include<bits/stdc++.h>
using namespace std;
auto ____ = [] () {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); };
const int MAXN = 55;
int n,A[MAXN];
int main(){
    ____();
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> A[i];
    int tot = 0;
    for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) tot += A[i] * A[j];
    cout << tot << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass : Scanner
{
    static void Main()
    {
        var (A, B, C, D) = ReadTuple<long,long,long,long>();

        long ac = (A - 1) / C;
        long bc = B / C;
        long abc = bc - ac;
        long ad = (A - 1) / D;
        long bd = B / D;
        long abd = bd - ad;
        long lcm = LCM(C, D);
        long alcm = (A - 1) / lcm;
        long blcm = B / lcm;
        long ablcm = blcm - alcm;
        WriteLine(B-A+1-abc-abd+ablcm);
    }
    public static long GCD(long a, long b)
        => a == 0 ? b : GCD(b % a, a);
    public static long LCM(long a, long b)
        => a / GCD(a, b) * b;
}



class Scanner
{
    public static string RString() => Console.ReadLine();
    public static int RInt() => ReadTuple<int>();
    public static long RLong() => ReadTuple<long>();
    public static double RDouble() => ReadTuple<double>();

    public static string[] RStrings() => Console.ReadLine().Split();
    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();

    public static T1 ReadTuple<T1>()
    {
        var r = RString();
        var r1 = (T1)Convert.ChangeType(r, typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadTuple<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadTuple<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadTuple<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[3], typeof(T4));
        return (r1, r2, r3, r4);
    }
}


Measured memory_bytes: 27424
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
// typedef tuple<int, int, int> T;
#define FOR(i, s, x) for (int i = s; i < (int)(x); i++)
#define REP(i, x) FOR(i, 0, x)
#define ALL(c) c.begin(), c.end()
#define DUMP(x) cerr << #x << " = " << (x) << endl
#define UNIQUE(c) sort(ALL(c)), c.erase(unique(ALL(c)), c.end())

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

template <typename T>
struct RangeSumQuery {
  int N;
  std::vector<T> dat;

  RangeSumQuery(int N) : N(N) {
    assert(N > 0);
    dat.resize(N, 0);
  }

  void add(int k, T val) {
    assert(0 <= k && k < N);
    for (int x = k; x < N; x |= x + 1) {
      dat[x] += val;
    }
  }

  // [0, k)
  T sum(int k) {
    assert(k >= 0);
    T ret = 0;
    for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) {
      ret += dat[x];
    }
    return ret;
  }
  // [l, r)
  T sum(int l, int r) {
    assert(0 <= l && l <= r && r <= N);
    return sum(r) - sum(l);
  }

  T index(int k) {
    assert(0 <= k && k < N);
    return sum(k + 1) - sum(k);
  }
};

void compress(vector<int> &arr1, vector<int> &arr2) {
  vector<int> tmp;
  for (int x : arr1) tmp.emplace_back(x);
  for (int x : arr2) tmp.emplace_back(x);
  UNIQUE(tmp);
  map<int, int> mp;
  REP(i, tmp.size()) mp[tmp[i]] = i;
  REP(i, arr1.size()) arr1[i] = mp[arr1[i]];
  REP(i, arr2.size()) arr2[i] = mp[arr2[i]];
}

int main() {
  int N;
  cin >> N;
  vector<int> X1(N), X2(N), Y1(N), Y2(N);
  REP(i, N) cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
  compress(Y1, Y2);

  vector<tuple<int, int, int>> events;

  REP(i, N) {
    if (X1[i] > X2[i]) swap(X1[i], X2[i]);
    if (Y1[i] > Y2[i]) swap(Y1[i], Y2[i]);

    if (X1[i] == X2[i]) {
      events.emplace_back(X1[i], 1, i);
    } else {
      events.emplace_back(X1[i], 0, i);
      events.emplace_back(X2[i], 2, i);
    }
  }

  sort(ALL(events));

  ll ans = 0;
  RangeSumQuery<ll> rsq(N);
  for (auto event : events) {
    int t, idx;
    tie(ignore, t, idx) = event;
    if (t == 0) {
      rsq.add(Y1[idx], 1);
    } else if (t == 1) {
      ans += rsq.sum(Y1[idx], min(N, Y2[idx] + 1));
    } else {
      rsq.add(Y1[idx], -1);
    }
  }

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


Measured memory_bytes: 8828
c[];main(n,m,i,j,k){for(;scanf("%d%d",&n,&m)*n;printf("%d\n",j>m?i:j)){for(i=3;j=i--;)for(scanf("%d",&j);j--;c[n-k]=i)scanf("%d",&k);for(i=n;i--;k+=c[i])j+=pow(3,i)*abs(k*2%4-c[i]);j=fmin(j,pow(3,n)+~j);}}

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

typedef long long ll;

ll N, K;

int main() {
  cin >> N >> K;
  if (2 * K - 1 > N)
    cout << -1 << endl;
  else {
    ll L = (N + 1) / 2;
    if (N == 2 * L - 1) {
      for (ll i = 0; i < L; ++i) {
        cout << K + 2 * i << " " << K + 3 * L - 2 - i << " "
             << K + 4 * L - 2 + i << endl;
      }
      for (ll i = 0; i < L - 1; ++i) {
        cout << K + 1 + 2 * i << " " << K + 4 * L - 3 - i << " "
             << K + 5 * L - 2 + i << endl;
      }
    } else {
      for (ll i = 0; i < L; ++i) {
        cout << K + 2 * i << " " << K + (i == 0 ? 2 : 3) * L - i << " "
             << K + 4 * L + i << endl;
      }
      for (ll i = 0; i < L; ++i) {
        cout << K + 1 + 2 * i << " " << K + 4 * L - 1 - i << " "
             << K + 5 * L + i << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 2304
#pragma GCC optimize("Ofast")
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

const long long INF = 1e17+7;
const long long MOD = 1e9+7;
const double PI=acos(-1);

using namespace std;

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	string L="";
	int ans=-1;
	for(int i=0;i<s.size();i++){
		L+=s[i];
		vector<int> a(26,0);
		for(int j=0;j<L.size();j++){
			for(int k=i+1;k<s.size();k++){
				if(L[j]==s[k]){
					a[(int)(L[j]-'a')]=1;
				}
			}
		}
		int cnt=0;
		for(int j=0;j<a.size();j++){
			if(a[j]==1){
				cnt++;
			}
		}
		ans=max(cnt,ans);
	}
	cout << ans << endl;		
				
	return 0;
}


Measured memory_bytes: 3588
#include <stdio.h>

int main(void)
{
    int i, count = 0;
    char yourinput[10];
    char check = '1';

    scanf("%s", yourinput);
    //scanf("%s", &check);

    for (i = 0; yourinput[i] != '\0'; i++)
    {
        if (yourinput[i] == check)
        {
            count++;
        }
    }

    printf("%d", count);

    return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	int ans = 0;
	rep(i, n){
		int in;
		cin >> in;
		if(in < abs(k-in)) ans += in*2;
		else ans += abs(k-in) * 2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N,ans=0;
	int sum1=0,sum2=0,sum3=0;
	char s[100];
	scanf("%d",&N);

	for(int i=0;i<N;i++){
		scanf("%s",s);
		int len=strlen(s);
		for(int j=1;j<len;j++){
			if(s[j-1]=='A'&&s[j]=='B')
				ans++;
		}
		if(s[0]=='B'&&s[len-1]=='A')
			sum3++;
		else if(s[0]=='B')
			sum1++;
		else if(s[len-1]=='A')
			sum2++;
	}
	ans+=min(sum1,sum2);
	if(sum1==0&&sum2==0&&sum3){
		sum3--;
	}
	ans+=sum3;
	cout<<ans<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                                                   //---------------------------------------------------------------
                                                                    
# define ll long long   
# define ld long double                                               
# define mod 1000000007                                                   
# define MAX 100005
# define pi 3.141592653589793238                                                                                  //shortcut keys
                                                                                
# define pb push_back                                                                     
# define mp make_pair 
# define all(x) x.begin(),x.end()                                                      
                                                                  
# define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);        //---------------------------------------------------------------                                       
using namespace std;
int main()
{
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k<=a)cout<<k;
   else if(k<=a+b)cout<<a;
	else cout<<a-(k-(a+b));
	return 0;
}

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

int main(){
    string s;
    cin >> s;
    int cnt = 0;
    for(int i = 0; i < s.size(); i++){
        if(i+1<s.size()){
            if(s[i] != s[i+1]) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(){
    int A,B,C;
    int count = 0;
    cin >> A >> B >> C;
    if(A == B) count++;
    if(B == C) count++;
    if(C == A) count++;
    if(count == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main() {
  long long T,N,ans,b;
  cin >> T>>N;
  ans=0;
  for(int i=0;i<N;i++){
    cin>>b;
    ans+=b;
  }
  if(ans<T){
    cout<<"No"<<endl;
    return 0;
  }

  cout <<"Yes"<< endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int a,b,c;
	string s,t,u;
	cin>>a>>b;
	c=2*b-a;
	cout<<c<<endl;	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向

int n;
string s[100010];
vector<string> march[5];
void input(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> s[i];
}

int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    ll ans = 0;
    for(int i=0;i<n;i++){
        if(s[i][0]=='M') march[0].push_back(s[i]);
        else if(s[i][0]=='A') march[1].push_back(s[i]);
        else if(s[i][0]=='R') march[2].push_back(s[i]);
        else if(s[i][0]=='C') march[3].push_back(s[i]);
        else if(s[i][0]=='H') march[4].push_back(s[i]);
    }
    int sz[5];
    for(int i=0;i<5;i++) sz[i] = march[i].size();
    for(int bit=(1<<3)-1;bit<(1<<5);bit=next_combination(bit)){
        ll tmp = 1;
        for(int i=0;i<5;i++){
            if(bit&(1<<i)) tmp *= sz[i];
        }
        ans += tmp;
    }
    cout << ans << endl;
}

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

#define MAX 1001

int main() 
{
	int m, n, Number;
	int i, j;
	int A[MAX], B[MAX];
	char x[MAX], y[MAX];
	char XX;

	scanf("%d ", &Number);
	while (Number--) {
		scanf("%s %s ", x, y);
		m = strlen(x);
		n = strlen(y);

		for (i = 0; i < n+1; i++)
		{
			B[i] = A[i] = 0;
		}
		for (i = 1; i < m+1; i++)
		{
			XX = x[i-1];
			for (j = 1; j < n+1; j++)
			{
				if (XX == y[j-1])
				{
					B[j] = A[j-1] + 1;
				} else if (A[j] >= B[j-1])
				{
					B[j] = A[j];
				}
				else
				{
					B[j] = B[j-1];
				}
			}
			for (j = 1; j < n+1; j++)
			{
				A[j] = B[j];
			}
		}
		printf("%d\n", A[n]);
	}
	return 0;
}



Measured memory_bytes: 2088
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using vpii = vector<pii>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) cin >> A[i];
  
  vi count(N,-INF);
  rep(i,N) {
    int x=lower_bound(count.begin(),count.end(),A[i])-count.begin();
    count[x-1]=A[i];
  }
  int ans=0;
  rep(i,N) if(count[i]!=-INF) ans++;
  
  cout << ans << endl;
}

Measured memory_bytes: 4048
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
  int n, m;
  cin >> n >> m;
  vector<int> town(n, 0);
  for (int i = 0; i < 2 * m; i++) {
    int a;
    cin >> a;
    a--;
    town[a]++;
  }
  for (int i = 0; i < n; i++) {
    cout << town[i] << endl;
  }
  return 0;
}

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

int main(){
    ll M=1000000007;
    ll n,k;cin>>n>>k;
    ll sum=0;

    vl s(n+1);rep(i,n+1)s[i+1]=s[i]+i+1;//s[0]~s[n]のn+1個

    for(ll i=k;i<n+1;i++){
        sum+=s[n]-s[n-i]-s[i-1]+1;
        if(sum>1000000007)sum=sum%1000000007;
    }

    cout<<sum+1<<endl;
}

Measured memory_bytes: 4752
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,m,i,k,p,r;
cin>>n>>m;long long a[m];
for(i=0;i<m;i++){
cin>>a[i];
}sort(a,a+m);
r=a[m-1];
p=2*(n-r);
k=n-p-1;
if(k<0)
cout<<0;
else
cout<<k;
return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() (int, error) {
	return strconv.Atoi(nextString())
}

func nextFloat64() (float64, error) {
	return strconv.ParseFloat(nextString(), 64)
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func main() {
	scanner.Split(bufio.ScanWords)

	n, _ := nextInt()
	a, _ := nextInt()
	b, _ := nextInt()
	c, _ := nextInt()
	d, _ := nextInt()

	costX := b * int(math.Ceil(float64(n)/float64(a)))
	costY := d * int(math.Ceil(float64(n)/float64(c)))
	fmt.Println(min(costX, costY))
}



Measured memory_bytes: 1124
#include<iostream>
#include<map>
#include<queue>

const int INFTY = 1 << 22;

using namespace std;

class Rooter{
  public:
Rooter(){
  this->cost = INFTY;
  this->done = false;
}
  int cost;
  bool done;
  vector<int> vcon;
};

void BFS( int start, map< int, Rooter > &G ){
  queue< Rooter * > q;

  G[ start ].cost = 1;
  G[ start ].done = true;
  q.push( &G[start] );

  while( !q.empty() ){
    Rooter *r = q.front();
    q.pop();

    for(int i = 0; i < r->vcon.size(); i++){
      if( G[ r->vcon[i]].done ){
	continue;
      }
      G[ r->vcon[i] ].cost = min( G[ r->vcon[i] ].cost , r->cost + 1 );
      q.push( &G[ r->vcon[i] ] );
      G[ r->vcon[i] ].done = true;
    }
  }
}

void ResetGraph( map< int, Rooter > &G, vector<int> &vId ){
  for(int i = 0; i < vId.size(); i++){
    G[ vId[i] ].cost = INFTY;
    G[ vId[i] ].done = false;
  }
}

int main(void){
  int n, p;
  vector< int > vId;
  map< int, Rooter > G;

  cin >> n;
  
  for(int i = 0; i < n; i++){
    int no;
    int cnum;
    Rooter r;

    cin >> no >> cnum;
    vId.push_back( no );
    for(int j = 0; j < cnum; j++){
      int connect;
      cin >> connect;
      r.vcon.push_back( connect );
    }
    G[ no ] = r;
  }

  cin >> p;
  for(int i = 0; i < p; i++){
    int s, d, ttl;

    cin >> s >> d >> ttl;
    ResetGraph( G, vId );
    BFS( s, G );
    if( G[d].cost <= ttl ){
      cout << G[d].cost << '\n';
    }else{
      cout << "NA\n";
    }
  }
  
  return 0;
}

Measured memory_bytes: 924
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>

using namespace std;
int N, Y;

int main() {
  cin >> N >> Y;
  for (int i=0; i<=N; i++) {
    for (int j=i; j<=N; j++) {
      int x = i;
      int y = j-i;
      int z = N-j;
      if (x*10000+y*5000+z*1000 == Y) {
        cout << x << ' ' << y << ' ' << z << endl;
        return 0;
      }
    }
  }
  cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}


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

int main() {
  int n, count=0, out=0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    if (i % 2 == 0) continue;
    for (int j = 1; j<=i; j++) {
      if (i % j == 0) count++;
    }
    if (count == 8) out++;
    count = 0;
  }
  cout << out << endl;
  return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cmath>
using namespace std;
 double angleClock(int hour, int minutes) {
        if(hour == 12){
			hour =0;
		}
		//每分的度数
		int dm = 360/60;
		int d = 0;

		//每小时的度数
		int hm = 360/12;
		double h = 0;

		//时钟偏移量
		double pyl = 0.5;


		h = hour * hm   + minutes * pyl;

		d =  dm * minutes;

		double re =  h - d;
		if(re < 0){
			re = -re;
		}else if (re > 180){
			re = 360 - re;
		}
        if (re > 180){
			re = 360 - re;
		}
        return re;
    }
int main(){
   int a,b;
    int hour,minute;
   scanf("%d %d %d %d",&a,&b,&hour,&minute);
   double d=cos(angleClock(hour,minute)*3.141592653/180)*1.0000;
  double c=sqrt(a*a+b*b-2*a*b*d);
  printf("%.20f",c);
  
    }
     


 

Measured memory_bytes: 4252
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
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 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

a,b,x = I()

if a**2*b <= 2*x:
  ama = a**2*b-x
  ran = 2*ama/(a**2)
  print(90-180/math.pi*math.atan2(a,ran))
else:
  ran = 2*x/(a*b)
  print(90-180/math.pi*math.atan2(ran,b))

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

int main (){
  string s;
  cin>>s;
  int maxn = 0;
  int cur = 0;
  for (int i = 0; i <= s.size(); ++i) {
    if (i < s.size() &&(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')) {
      ++cur;
    } else {
      if (cur > maxn) maxn = cur;
      cur = 0;
    }
  }
  cout<<maxn<<endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace _0219
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == 0) { break; }
                int[] a = new int[10];
                for (int i = 0; i < n; i++)
                {
                    a[int.Parse(Console.ReadLine())]++;
                }
                for (int i = 0; i < a.Length; i++)
                {
                    if (a[i] == 0) { Console.Write("-"); Console.WriteLine(); continue; }
                    for (int k = 0; k < a[i]; k++) { Console.Write("*"); }
                    Console.WriteLine();
                }
            }
        }

    }
}

Measured memory_bytes: 8772
#include <bits/stdc++.h>
using namespace std;
int main(){	
	int N,W,w,v,res=0;
	map<int,int> dp;
	dp[0]=0;
	cin>>N>>W;
	while(N--){
		cin>>w>>v;
		for(auto it=dp.rbegin();it!=dp.rend();++it){
			int ws=it->first,vs=it->second;
			if(ws+w<=W){
				dp[ws+w]=max(dp[ws+w],vs+v);
				res=max(res,dp[ws+w]);
			}
		}
	}
	cout<<res<<endl;
}


Measured memory_bytes: 384