akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    priority_queue<int> que;
    rep(i, N) {
        int a; cin >> a;
        que.push(a);
    }
    while(M--) {
        int k = que.top(); que.pop();
        k /= 2;
        que.push(k);
    }
    int ans = 0;
    while(!que.empty()) {
        ans += que.top(); que.pop();
    }
    cout << ans << endl;
    

    return 0;
}


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

#define endl '\n'
#define rep(n)      for (int i = 0 ; i < n ; i++)
#define all(a)      a.begin(),a.end()
#define NumofDigits(n)    ((long long)log10(n)+1)
#define Unique(n)         (n).erase(unique(all(n)), (n).end())



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

void readFromText ()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif // ONLINE_JUDGE
}

void time()
{
#ifndef ONLINE_JUDGE
    cout << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
#endif
}

const double Pi = acos(-1.0);

const int MAX = 2e5 ;
int sum [MAX+1];
int freq [MAX+1];

int main()
{
    quick(); // readFromText();
    int a , b , c , d ; cin >> a >> b >> c >> d ; bool state = false ;
    while (true) {
        c-=b;
        if (c<=0){state=true;break;}
        a-=d;
        if (a<=0)break;
    }
    if (state)cout << "Yes" ;
    else cout << "No" ;
    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, c) for(long long i=0; i<(long long)c; i++)
const int INF=1001001001;
int main() {
	string n;

	cin>>n;
	if (n[0]>'Z') cout <<"a"<<endl;
	else cout <<"A"<<endl;
	return 0;
}


Measured memory_bytes: 3592
#include<stdio.h>
#include<math.h>
int isprime(int x)
{
	int i=3;
	if(x==2){return 0;}
	if(x<2 || x%2==0){return -1;}
	while(i<=sqrt(x))
	{
		if(x%i==0){return -1;}
		i+=2;
	}
	return 0;
}
int main(void)
{
	int n,m,i,c=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&m);
		if(!isprime(m)){c++;}
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 596
#include<stdio.h>

void swap(int *a,int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int selectionSort(int *A,int N){
    int i,j,minj;
    int count=0;
    for(i=0;i<N-1;i++){//i?????´??????????????°
        minj=i;
        for(j=i;j<N;j++){//????°???????????????????
            if(A[j]<A[minj]){
                minj=j;
            }
        }
        if(A[minj]!=A[i]){
            swap(&A[i],&A[minj]);
            count++;
        }
    }
    return count; 
}

int main(){
    int A[100];
    int i,N,count;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    count = selectionSort(A,N);
    for(i=0;i<N;i++){
        if(i==0){
            printf("%d",A[i]);
        }else{
            printf(" %d",A[i]);
        }
    }
    printf("\n%d\n",count);
    return 0;
}

Measured memory_bytes: 1848
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep0(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define rrep(i,n) for (int i=(int)(n)-1; i>=0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;
using llGraph = vector<vl>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;

template<typename T>
struct is_vector : false_type{};

template<typename T>
struct is_vector<vector<T>> : true_type{};

template<typename T>
ostream &operator << (ostream &ostr, const vector<T> &vec) {
  if (vec.empty()) {
    return ostr;
  }
  ostr << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) {
    if (is_vector<T>()) ostr << "\n" << *itr;
    else ostr << ' ' << *itr;
  }
  return ostr;
}

template<typename T>
bool CompareBySecond(pair<T, T> a, pair<T, T> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

template<typename T>
T GCD(T a, T b) {
  T c = a % b;
  while (c != 0) { a = b; b = c; c = a % b; }
  return b;
}


/* -------- <templates end> -------- */


template<typename T>
bool CompareBySlope(pair<T, T> a, pair<T, T> b) {
// counterclockwise from 12 o'clock direction
  if (a.first * b.first < 0) {
    return a.first < b.first;
  } else if (a.first == 0) {
    if (a.second > 0) {
      return true;
    } else {
      return a.first < b.first;
    }
  } else if (b.first == 0) {
    if (b.second > 0) {
      return false;
    } else {
      return a.first < b.first;
    }
  }
  return a.second * b.first < a.first * b.second;
}

void solve() {
  int n; cin >> n;
  vector<pll> G;
  rep(i,n) {
    ll x, y; cin >> x >> y;
    if (x != 0 || y != 0) G.push_back(pii(x, y));
  }
  sort(ALL(G), CompareBySlope<ll>);
  int sz = G.size();
  ll sq_ans = 0;
  rep(i,sz) {
    ll Xsum = 0, Ysum = 0;
    for (int j=i; j<i+sz; ++j) {
      Xsum += G[j%sz].first;
      Ysum += G[j%sz].second;
      sq_ans = max(sq_ans, Xsum*Xsum + Ysum*Ysum);
    }
  }
  cout << sqrtl(sq_ans) << endl;
}


/* -------- <programs end> -------- */


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    unsigned long long int ans=0;
    cin >> ans;
    for(int i=1;i<n;i++){
        long long int tmp;
        unsigned long long int prev;
        cin >> tmp;
        if(ans > 1000000000000000000 && tmp==0)
            ans*=tmp;
        else{
            prev=ans;
            ans*=tmp;
            if(prev>ans && tmp!=0){
                ans=1000000000000000001;
            }
        }
    }
    if(ans > 1000000000000000000){
            cout << -1 << endl;
            return 0;
    }
    cout << ans << endl;
    return 0;
    
}


Measured memory_bytes: 3632
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

char s1[1000];
int w[150],t[150],tt[150];
int ans,maxn,maxx,tot,ans2,ans22,anss,maxxx,maxnn,tott,minnn;
int main()
{
	int minn=0x7fffffff,minnn=0x7fffffff;
	scanf("%s",s1);
	int  n=strlen(s1);
	for(int i=0;i<n;i++)
	{
		w[s1[i]]++;
		if(w[s1[i]]>=2)t[++tot]=i;//maxn=w[s1[i]],
	}
	for(int j=1;j<=tot;j++)
	{
		ans=0,maxx=0;
		//whbrjpjyhsrywlqjxdbrbaomnw
		for(int i=0;i<n;i++)
		{
			if(s1[i]!=s1[t[j]])ans++;
			if(ans>maxx)maxx=ans;
			if(s1[i]==s1[t[j]])ans=0;
		}
		if(maxx<minn)minn=maxx;
	}
	ans2=(n+1)>>1;
	ans=min(ans2,minn);
	
	memset(w,0,sizeof(w));
		for(int i=0;i<n;i++)
	{
		w[s1[i]]++;
		if(w[s1[i]]>=maxnn)maxnn=w[s1[i]],tt[++tott]=i;
	}
	for(int j=1;j<=tott;j++)
	{
		anss=0,maxxx=0;
		//whbrjpjyhsrywlqjxdbrbaomnw
		for(int i=0;i<n;i++)
		{
			if(s1[i]!=s1[tt[j]])anss++;
			if(anss>maxxx)maxxx=anss;
			if(s1[i]==s1[tt[j]])anss=0;
		}
		if(maxxx<minnn)minnn=maxxx;
	}
	
	ans=min(ans,minnn);
	
	printf("%d\n",ans);
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
int n, a[maxn];
map<int,int> mp; int k;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
cin>>n>>k;
  for (int i=0; i<n; i++) {
    cin>>a[i];
  	mp[a[i]]++;
  }
  if (int(mp.size())<=k) out(0);
  vector<pair<int,int>> v;
  for (auto p: mp) v.push_back({p.second,p.first});
  sort(v.begin(),v.end());
  int ans = 0;
  for (int i=0; i<int(v.size())-k; i++) {
    ans += v[i].first;
  }
  cout<<ans;
  

  return 0;
}


Measured memory_bytes: 12660
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        s_list: [String; n],
    }
    let ans = if s_list.iter().any(|s| s == "Y") { "Four" } else { "Three" };
    println!("{}", ans);
}


Measured memory_bytes: 4352
MOD = 10**9 + 7
N, K = map(int, input().split())
ans = 0

def calcu(x):
    small = (x*(x-1))/2
    large = small + x*(N-x+1)
    return large-small+1

for i in range(K, N+2):
    ans += calcu(i)
    ans %= MOD

print(int(ans))

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

int main(){
  int N,t;
  
  cin >> N;
  t=N;
  
  int f=0;
  
  for(int i=0;i<9;i++){
    f = f+ (t%10);
    t=t/10;
  }
  
  if(N%f==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}

Measured memory_bytes: 3608
n = int(input())
h = list(map(int, input().split()))
cost = [float('inf')] * n
cost[0] = 0
for i in range(n - 2):
  cost[i + 1] = min(cost[i + 1], cost[i] + abs(h[i + 1] - h[i]))
  cost[i + 2] = min(cost[i + 2], cost[i] + abs(h[i + 2] - h[i]))
cost[n - 1] = min(cost[n - 1], cost[n - 2] + abs(h[n - 1] - h[n - 2]))
print(cost[n - 1])


Measured memory_bytes: 13908
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> A(N),cusum(N+1,0);
    for(int i = 0; i < N;i++){
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    for(int i = 0; i < N;i++){
        cusum[i+1] = cusum[i] + A[i];
    }
    ll res = 0;
    for(int i = 0; i < N - 1;i++){
        ll tmp = cusum[i+1];
        if(A[i+1] <= tmp*2){
            res++;
        }else{
            res = 0;
        }
    }
    res++;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1792
char *t[]={".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};main(n,s,x,c){for(scanf("%d",&n),getchar();x=-1,n;puts(""),n--)while((c=getchar())!='\n'&&~c)if(c-=48)s=c-1,x++;else if(~x)putchar(t[s][x%strlen(t[s])]),x=-1;}

Measured memory_bytes: 588
N, W = map(int, input().split())
dp = [0] + [W+1] * (N*100)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(i*100, -1, -1):
        if dp[j+v] > dp[j] + w:
            dp[j+v] = dp[j] + w

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break


Measured memory_bytes: 5868
#include<stdio.h>

int main(void){
	int a=0;
	int b=0;
	int c=0;
	int x=0;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(a>c){
		x=a;
		a=c;
		c=x;
	}
	if(a>b){
		x=b;
		b=a;
		a=x;
	}
	if(b>c){
		x=c;
		c=b;
		b=x;
	}
	printf("%d %d %d\n",a,b,c);
	
return 0;
}



Measured memory_bytes: 2100
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=4e2+7;
const int mod=9901;
using namespace std;
int p[MX],k[MX];
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
map<string,int>mp;
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  string s,t;
  cin>>s>>t;
  int a,b;
  cin>>a>>b;
  mp[s]=a,mp[t]=b;
  string u;
  cin>>u;
  mp[u]--;
  cout<<mp[s]<<" "<<mp[t]<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
  int X, Y;
  cin >> X >> Y;
  
  for (int i=0; i<=X; i++) {
   	if (i*2 + (X-i)*4 == Y) {
      cout << "Yes"; 
      return 0;
    }
  }
  
  cout << "No";
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){

  int a,b;
  cin >> a >> b;
  
  int ans = 0;
  
  if(2*b >= a){
	cout << ans << endl;
  }else{
    ans = a-(2*b);
    cout << ans << endl;
  }
  
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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

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

int H, W;

int main() {
    cin >> H >> W;

    unsigned long long n = (unsigned long long) H * W;
    unsigned long long ans;

    if (H == 1 || W == 1) {
        ans = 1;
    } else if (n % 2 == 0) {
        ans = n / 2;
    } else {
        ans = n / 2 + 1;
    }

    cout << ans << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<sstream>
#include<list>
#include<climits>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define nrep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;


int main(){
	int n;cin>>n;
	vi a(n);
	rep(i,n){
		int t;cin>>t;
		a[t-1]=i;
	}
	int mx=1;
	int temp=1;
	nrep(i,1,n){
		if(a[i]>a[i-1])temp++;
		else temp=1;
		mx=max(mx,temp);
	}
	cout<<n-mx<<endl;
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 #define ll  long long int
 string x;
int dp[3001][3001],ans=0;
 
//vector<vector<string> >dp;
 int fn(int i,int j, string &s,string &t )
 {
     if(i==0||j==0)
     return 0;
     
     if(dp[i][j]!=-1)
    {
        
        return dp[i][j];
    }
     if(s[i-1]==t[j-1])
     {
        x+=s[i-1];
       ans= fn(i-1,j-1,s,t)+1;
         dp[i][j]=ans; 
         return ans;
     }
   
     ans= max(fn(i-1,j,s,t),fn(i,j-1,s,t));
   
     dp[i][j]=ans;
     return ans;
 }
 int main()
 {
     string s,t,a;
     cin>>s>>t;
    for(int i=0; i<=s.size(); i++)
    for(int j=0; j<=t.size(); j++)
    dp[i][j]=-1;
    
   int i=s.size(),j=t.size();
   int y=fn(i,j,s,t);
 // cout<<dp[i][j];
   while(i>0&&j>0)
   {
       if(s[i-1]==t[j-1])
       {
           a+=s[i-1];
           i--; j--;
       }
       else
       if(dp[i-1][j]>dp[i][j-1])
       {
           i--;
       }
       else
       j--;
   }
   reverse(a.begin(),a.end());
   cout<<a;
 
 }

Measured memory_bytes: 40456
H,W = list(map(int, input().split()))

S = [[1 if s=='#' else -1 for s in input()] for _ in range(H)]

def surround(matrix, fill=0):
  if not isinstance(matrix, list):
    raise
  if not all([isinstance(rows, list) for rows in matrix]):
    raise
  if not all([len(rows)==len(matrix[0]) for rows in matrix]):
    raise
  r = len(matrix)
  c = len(matrix[0])
  new_matrix = [[fill]*(c+2)] + [[fill]+rows+[fill] for rows in matrix] + [[fill]*(c+2)]
  return new_matrix

S = surround(S, 0)
# 黒: 1 白:-1 枠:0

from itertools import product
to_visit = set(list(product(range(1,H+1), range(1, W+1))))


from collections import deque

answer = 0
while to_visit:
  h,w = to_visit.pop()

  dq = deque([(h,w)])
  reachable = set([(h,w)])
  blacks = 0
  whites = 0
  if S[h][w]==1:
    blacks += 1
  else:
    whites += 1

  while dq:
    h,w = dq.pop()
    nexts = [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]
    for nxt in nexts:
      if nxt in reachable:
        continue
      else:
        if S[h][w] + S[nxt[0]][nxt[1]]==0:
          to_visit.remove(nxt)
          dq.append(nxt)
          reachable.add(nxt)
          if S[nxt[0]][nxt[1]]==1:
            blacks +=1
          else:
            whites +=1

  answer += blacks * whites
print(answer)

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

int main()
{
	int a, b;
	cin >> a >> b;
	if (a < b)
		cout << "a < b" << endl;
	else if (a > b)
		cout << "a > b" << endl;
	else
		cout << "a == b" << endl;
	return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define upd(x,y) x=x+y>=mu?x+y-mu:x+y;
const int mu=1000000007;
int n,a[22][22],dp[22][1<<21];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		for (int j=0;j<n;j++) scanf("%d",&a[i][j]);
	dp[0][0]=1;
	for (int i=0;i<n;i++)
		for (int j=0;j<(1<<n);j++){
			if (!dp[i][j]) continue;
			for (int k=0;k<n;k++)
				if (a[i+1][k] && (j&(1<<k))==0) 
					upd(dp[i+1][j|(1<<k)],dp[i][j]);
		}
	printf("%d\n",dp[n][(1<<n)-1]);
} 

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

using namespace std;
using ll =long long;
using db = double;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;

//ここから書き始める

int main()
{
	cout << setprecision(10);
	ll n; cin >> n;
	vector<ll> h(n);
	rep(i,n) cin >> h[i];

	ll dp[100100];
	rep(i,100100) dp[i] = INF;
	dp[0] = 0 ;
	rep(i,n){
		chmin(dp[i+1] ,dp[i]+ abs(h[i] - h[i+1]));
		chmin(dp[i+2] ,dp[i]+ abs(h[i] - h[i+2]));
	}
	cout << dp[n-1] << endl;

}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll dp[5005*5000];
ll ma[5005];

void chmax(ll &a,ll b){
  if(a<b) a=b;
}

int main(){
  int N;
  cin>>N;
  int ga,gb,gc;
  cin>>ga>>gb>>gc;
  int sa,sb,sc;
  cin>>sa>>sb>>sc;

  for(int i=0;i<=5001*5000;i++) dp[i]=i;
  for(int i=0;i+sa<=5000*5001;i++){
    chmax(dp[i+sa],dp[i]+ga);
  }
  for(int i=0;i+sb<=5000*5001;i++){
    chmax(dp[i+sb],dp[i]+gb);
  }
  for(int i=0;i+sc<=5000*5001;i++){
    chmax(dp[i+sc],dp[i]+gc);
  }

  for(int i=0;i<=N;i++) ma[i]=i;
  for(int i=0;i+ga<=N;i++){
    chmax(ma[i+ga],ma[i]+sa);
  }
  for(int i=0;i+gb<=N;i++){
    chmax(ma[i+gb],ma[i]+sb);
  }
  for(int i=0;i+gc<=N;i++){
    chmax(ma[i+gc],ma[i]+sc);
  }

  

  /*for(int i=gc;i<=5000*5001;i++){
    chmax(dp[i],dp[i-gc]+sc);
  }*/

  //for(int i=0;i<=N;i++) cout<<i<<" "<<dp[i]<<endl;

  ll ans=N;
  chmax(ans,dp[ma[N]]);
  /*for(int i=0;i*ga<=N;i++){
    for(int j=0;i*ga+j*gb<=N;j++){
      int n=N-(i*ga+j*gb);
      ll tmp=i*sa+j*sb;
      chmax(ans,dp[ma[n]]);
    }
  }*/

  cout<<ans<<endl;

  return 0;
}


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

vector<int>p;//ノードxの親
vector<int>rank;//ノードxの高さ

void shokika(int size){
  rank.resize(size,0);
  p.resize(size,0);
  for(int i=0;i<size;i++){
    p[i]=i;
    rank[i]=0;
  }
}

int find(int x){//代表
  if(x==p[x])
    return x;
  return p[x]=find(p[x]);//一回でいけるように//経路圧縮
}

int same(int x,int y){//xとyの一致
  if(find(x)==find(y))   //代表が同じ
    return 1;
  else
    return 0;
}

void unite(int x,int y){//ｘとyの合併
  x=find(x);//xの代表
  y=find(y);//yの代表

  if(rank[x]>rank[y])
    p[y]=x;//親を変える
  else
    p[x]=y;//親を変える

  if(rank[x]==rank[y])
    rank[y]++;//　rank[y]=rank[x]+1;
}


int main(){
  int n,a,b,q;
  int t;
  cin>>n>>q;

  shokika(n);

  for(int i=0;i<q;i++){
    cin>>t>>a>>b;
    if(t==0) unite(a,b);
    else if(t==1) {
      if(same(a,b)) cout<<1<<endl;
      else cout<<0<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3196
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include<bits/stdc++.h>
#include<chrono>
#include<unordered_map>
#include<random>
#include<complex> 
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned ll 
#define endl '\n'
#define mk make_pair
void fast_in_out() {
	std::ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
}
int dx[] = { 0,0,-1,1,-1,1,-1,1,0 };
int dy[] = { -1,1,0,0,-1,-1,1,1,0 };
int lx[] = { 2, 2, -1, 1, -2, -2, -1, 1 };
int ly[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
const ld eps = 1e-9;
const int N = 1e6 + 50, M = 1e5 + 10, mod = 1e9 + 7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll t = gcd(a, b); return t ? (a / t * b) : 0; }
int prm[N];
unordered_map<int, int>mp;
void sieve() {
	for (int i = 2; i < N; i += 2)
		prm[i] = 2;
	for (int i = 3; i < N; i += 2) {
		if (!prm[i]) {
			for (int j = i; j < N; j += i) {
				prm[j] = i;
			}
		}
	}
}
ll fast_power(ll base, ll power) {
	ll result = 1;
	power %= mod;
	while (power > 0) {

		if (power & 1) {
			result = (result * base) % mod;
		}
		base = (base * base) % mod;
		power >>= 1;
	}
	return result;
}
int main() {
	fast_in_out();
//	cout << fixed << setprecision(6);
	int n; cin >> n;
	sieve();
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		unordered_map<int, int>mp2;
		int x = v[i];
		while (prm[x]) {
			int p = prm[x];
			mp2[p]++;
			x /= p;
		}
		for (auto e : mp2)
			mp[e.first] = max(mp[e.first], e.second);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		unordered_map<int, int>mp2;
		int x = v[i];
		while (prm[x]) {
			int p = prm[x];
			mp2[p]++;
			x /= p;
		}
		ll xx = 1;
		for (auto e : mp) {
			int y = 0;
			if (mp2.find(e.first) != mp2.end())
				y = mp2[e.first];
			xx *= fast_power(e.first, e.second - y);
			xx %= mod;
		}
		ans += xx;
		ans %= mod;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4608
#include <stdio.h>

int main(void)
{
	int i, j, N, l[3];
	
	scanf("%d", &N);
	
	for (i = 0; i < N; i++){
		for (j = 0; j < 3; j++){
			scanf("%d", &l[j]);
		}
		
		if ((l[0] * l[0]) == (l[1] * l[1]) + (l[2] * l[2]) || (l[1] * l[1]) == (l[0] * l[0]) + (l[2] * l[2]) || (l[2] * l[2]) == (l[0] * l[0]) + (l[1] * l[1])){
				printf("YES\n");
			}
			
		else {
			printf("NO\n");
		}
	}
	
	return (0);
}

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

struct Node {
  int key;
  Node *next, *prev;
};

Node *nil;

Node* listSerch(int key) {
  Node *cur = nil -> next;
  while (cur != nil && cur -> key != key) {
    cur = cur -> next;
  }
  return cur;
}

void init() {
  nil = (Node *)malloc(sizeof(Node));
  nil -> next = nil;
  nil -> prev = nil;
}

void printList() {
  Node *cur = nil -> next;
  int isf = 0;
  while(1) {
    if(cur == nil) break;
    if(isf++ > 0) printf(" ");
    printf("%d", cur -> key);
    cur = cur -> next;
  }
  printf("\n");
}

void deleteNode(Node *t) {
  if(t == nil) return;
  t -> prev -> next = t -> next;
  t -> next -> prev = t -> prev;
  free(t);
}

void deleteFirst() {
  deleteNode(nil -> next);
}

void deleteLast() {
  deleteNode(nil -> prev);
}
  
void deleteKey(int key) {
  deleteNode(listSerch(key));
}

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x -> key = key;
  x -> next = nil -> next;
  nil -> next -> prev = x;
  nil -> next = x;
  x -> prev = nil;
}
  
int main() {
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  
  init();
  for (i = 0; i < n; i++) {
    scanf("%s%d", com, &key);
    if (com[0] == 'i') {insert(key); np++; size++;}
    else if (com[0] =='d') {
      if(strlen(com) > 6) {
        if(com[6] == 'F') deleteFirst();
        else if (com[6] == 'L') deleteLast();
      } else {
        deleteKey(key); nd++;
      }
      size--;
    }
  }
  
  printList();
  
  return 0;
}


Measured memory_bytes: 34368
s = input()
t = list(input())
import sys
ans = []
for i in range(len(s)):
  S = list(s)
  if S[len(s)-len(t)-i] == t[0] or '?':
    m = int(len(s)-len(t)-i)
    #print(m)
    if m >= 0:
      for j in range(len(t)):
        if S[m+j] == t[j] or S[m+j] == '?':
          S[m+j] = t[j]
          if j == len(t)-1:
            #print(S)
            for i in range(len(S)):
              if S[i] == '?':
                S[i] = 'a'
            ans.append(''.join(S))
            break
        else:
          S = list(s)
          break
if ans == []:
  print('UNRESTORABLE')
else:
  ans.sort()
  print(ans[0])

Measured memory_bytes: 3064
# frozen_string_literal: true

a = gets.split.map(&:to_i)
min = 198

[*0..2].permutation(3).each do |i|
  tmp = (a[i[0]] - a[i[1]]).abs + (a[i[1]] - a[i[2]]).abs
  min = tmp if min > tmp
end

puts min

Measured memory_bytes: 1788
s=input()
a=int(s[:2])
b=int(s[2:])

if (1<=a<=12 and 1<=b<=12):
    print('AMBIGUOUS')
elif (1<=a<=12 and (b>12 or b==0)):
    print('MMYY')
elif ((a>12 or a==0) and 1<=b<=12):
    print('YYMM')
else:
    print('NA')

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

int main() {
	long long a, b, c, k;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &k);
	printf("%lld", (a - b) * (k & 1 ? -1 : 1));
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n];
        if (n == 1) {
            System.out.println(0);
        } else if (n >= 2) {
            int[] len = new int[n - 1];
            for (int i = 0; i < h.length; i++) {
                h[i] = sc.nextInt();
            }
            for (int i = 0; i < len.length; i++) {
                if (h[i] >= h[i + 1]) {
                    len[i] = 1;
                } else {
                    len[i] = 0;
                }
            }
            List<Integer> memory = new ArrayList<>();
            int counter = 0;
            for (int i = 0; i < len.length; i++) {
                if (len[i] == 1) {
                    counter++;
                }
                if (len[i] == 0 || i == len.length - 1) {
                    memory.add(counter);
                    counter = 0;
                }
            }
            int max = memory.get(0);
            for (int i : memory) {
                if (i > max) {
                    max = i;
                }
            }
            System.out.println(max);
        }
        sc.close();
    }
}

Measured memory_bytes: 51148
#include<bits/stdc++.h>
#define N 2005
using namespace std;
string s,t,ans;
int dp[N][N];

void dfs(int y,int x){
  if(!y||!x)return;
  if(dp[y][x]-dp[y-1][x-1]==1&&dp[y][x]-dp[y-1][x]==1&&dp[y][x]-dp[y][x-1]==1){
    ans+=s[y-1];
    dfs(y-1,x-1);
    return;
  }
  if(dp[y][x-1]==dp[y][x])dfs(y,x-1);
  else dfs(y-1,x);
}

int main(){
  //IAIDDAII

    while(cin>>s){
      //s.resize(8);
      //for(int i=0;i<8;i++) s[i]='A'+(rand())%10;
      t=s;
    reverse(t.begin(),t.end());
    memset(dp,0,sizeof(dp));
    int n=s.size(),m=t.size();
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
	if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;
	else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
      }
    }
    ans="";
    dfs(n,m);
    if(ans.size()%2==0){
      ans=ans.substr(0,ans.size()/2);
      string tmp=ans;reverse(tmp.begin(),tmp.end());
      ans=ans+tmp;
    }
    else {
      string tmp=ans.substr(0,ans.size()/2);
      reverse(tmp.begin(),tmp.end());
      ans=ans.substr(0,ans.size()/2)+ans[ans.size()/2]+tmp;
    }
    string temp=ans;
    reverse(temp.begin(),temp.end());
    assert(ans==temp);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 18700
using System;
class abc145_c{
  public static void Main(){
    int n = int.Parse(Console.ReadLine());
    String[] str;
    vec[] pos = new vec[n];
    for(int i=0; i<n; i++){
      str = Console.ReadLine().Split(' ');
      pos[i] = new vec();
      vec v = new vec(int.Parse(str[0]), int.Parse(str[1]));
      pos[i] = v;
    }
    double sum = 0;
    for(int i=0; i<n; i++){
      for(int j=i; j<n; j++){
        sum += Math.Sqrt(Math.Pow((pos[i].X-pos[j].X),2)+Math.Pow((pos[i].Y-pos[j].Y),2));
      }
    }
    Console.WriteLine(sum*2/n);
  }
}

class vec{
  int x, y;
  public vec(){}
  public vec(int tx, int ty){
    x = tx;
    y = ty;
  }
  public int X{
    get{return x;}
    set{x = value;}
  }
  public int Y{
    get{return y;}
    set{y = value;}
  }
}


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

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

    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> L(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
    }

    char A[4] = {'0', '1', '2', '3'};

    int mini = 1e9;
    for(int i = 0; i < (int)(pow(4, n)); i++){
        string s = "";
        int t = i;
        while(true){
            s += A[t % 4];
            t /= 4;
            if(t == 0) break;
        }
        reverse(s.begin(), s.end());
        int ss = s.size();
        for(int j = 0; j < n - ss; j++){
            s = '0' + s;
        }
        int na = 0, nb = 0, nc = 0, sc = 0;
        for(int j = 0; j < s.size(); j++){
            if(s[j] == '0');
            else if(s[j] == '1'){
                sc += (na == 0 ? 0 : 1);
                na += L[j];
            }else if(s[j] == '2'){
                sc += (nb == 0 ? 0 : 1);
                nb += L[j];
            }else if(s[j] == '3'){
                sc += (nc == 0 ? 0 : 1);
                nc += L[j];
            }
        }
        if(na > 0 and nb > 0 and nc > 0){
            int cost = abs(na - a) + abs(nb - b) + abs(nc - c) + sc * 10;
            mini = min(mini, cost);
        }
    }

    cout << mini << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int a[100000+10];
long long ans;
int main(){
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
        ans = 0;
        int tmp = 1;
        for(int i = 1; i <= n; i++)
        {
            int value = a[i]/tmp;
            if(a[i]%tmp == 0)value--;
            if(a[i] >= tmp)
            {
                ans += value;
              //  printf("a[%d]=%d :value:%d tmp:%d ans:%d\n", i, a[i], value, tmp, ans);
                if(a[i] == tmp || i == 1)tmp++;
            }
        }

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

Measured memory_bytes: 768
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define For(i,j,k)	for(int i=j;i<=k;++i)
#define Dow(i,j,k)	for(int i=k;i>=j;--i)
#define ll long long
#define int ll
#define pb push_back


using namespace std;

inline ll read()
{
    ll t=0,dp=1;char c=getchar();
    while(!isdigit(c))	{if(c=='-')	dp=-1;c=getchar();}
    while(isdigit(c))	t=t*10+c-48,c=getchar();
    return t*dp;
}
inline void write(ll x){if(x<0)	{putchar('-');x=-x;}	if(x>=10)	write(x/10);putchar(x%10+48);}
inline void writeln(ll x){write(x);puts("");}
inline void write_p(ll x){write(x);putchar(' ');}
/*------------------------------------------------------------------------------------------------------*/

const int N=1e5+5;	
int n;
struct node{int v,num;}	p[N];
int ans[N];
inline bool cmp(node x,node y){return x.v!=y.v?x.v>y.v:x.num<y.num;}
signed main()
{
	n=read();
	For(i,1,n)	p[i].v=read(),p[i].num=i;
	sort(p+1,p+n+1,cmp);
	int now=1,to=p[1].num;
//	For(i,1,n)	cout<<p[i].v<<' '<<p[i].num<<endl;
	For(i,2,n+1)
	{
		ans[to]+=(p[i-1].v-p[i].v)*now,now++;
		to=min(to,p[i].num);
	}
//	ans[to]=(p[n].v-p[n+1].v)*now,now++;
	For(i,1,n)	writeln(ans[i]);
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 1e9

using namespace std;

typedef int long long ll;
typedef int long l;
typedef pair<int, int> Pii;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s, w;
    cin >> s >> w;
    if (s > w) {
        cout << "safe";
    } else {
        cout << "unsafe";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,m,p[11],ans = 0;
	vector<int> s[11];
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		int k;
		cin >> k;
		for(int j = 0;j < k;j++){
			int v;
			cin >> v;
			s[i].pb(v - 1);
		}
	}
	for(int i = 0;i < m;i++) cin >> p[i];
	for(int i = 0;i < (1 << n);i++){
		bool flag = true;
		//cout << i << endl;
		for(int j = 0;j < m;j++){
			int cnt = 0;
			for(int v : s[j]){
				//cout << v << endl;
				if((i >> v) & 1) cnt++;
			}
			//cout << j << ":" << cnt << endl;
			if(cnt % 2 != p[j]) flag = false;
		}
		if(flag) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N,Q;
const int W=700;
int c[5<<17];
int ans[5<<17];
int cnt[5<<17];
main()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)cin>>c[i];
	vector<vector<pair<int,pair<int,int> > > >qs((N+W-1)/W);
	for(int i=0;i<Q;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		qs[l/W].push_back(make_pair(r,make_pair(l,i)));
	}
	int L=0,R=0;
	int all=0;
	for(int i=0;i<qs.size();i++)
	{
		while(L<i*W&&L<N)
		{
			if(!--cnt[c[L++]])all--;
		}
		while(i*W<R)
		{
			if(!--cnt[c[--R]])all--;
		}
		sort(qs[i].begin(),qs[i].end());
		for(int j=0;j<qs[i].size();j++)
		{
			int r=qs[i][j].first;
			while(R<r)
			{
				if(!cnt[c[R++]]++)all++;
			}
			int l=qs[i][j].second.first;
			while(L<l)
			{
				if(!--cnt[c[L++]])all--;
			}
			while(L>l)
			{
				if(!cnt[c[--L]]++)all++;
			}
			ans[qs[i][j].second.second]=all;
		}
	}
	for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}

Measured memory_bytes: 18644
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
        int n;
        cin >> n;
        int d[n];
        int res = 0;

        for (int i = 0; i < n; i++)
                cin >> d[i];

        sort(d, d + n);

        int comp = 99999;
        for (int i = n - 1; i >= 0; i--) {
                if (comp > d[i]) {
                        res++;
                        comp = d[i];
                }
        }
        cout << res << endl;
}

Measured memory_bytes: 256
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n,m = na()
ar = na()
sm = sum(ar)
cnt = 0
for A in ar:
    if A*4*m >= sm:
        cnt += 1
print('Yes' if cnt >= m else 'No')


Measured memory_bytes: 3060
INF = float('inf')
MAX_N = 110
MAX_V = 100100

# input
N, W = map(int, input().split())
weight, value = [0]*N, [0]*N

for i in range(N):
    tmp_w, tmp_v = map(int, input().split())
    weight[i] = tmp_w
    value[i] = tmp_v

dp = [[INF for _ in range(MAX_V)] for _ in range(MAX_N)]
dp[0][0] = 0


for i in range(N):
    for sum_v in range(MAX_V):
        # i番目の品物を選ぶ場合
        if sum_v - value[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i])
        # i番目の品物を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


answer = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        answer = sum_v

print(answer)

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

using namespace std;

#define REP(var, n)  for (int var = 0; var < (n); var++)
#define RREP(var, n)  for (auto var = n - 1; var != static_cast<int>(-1); var--)
#define FOR(var, a, b)  for (auto var = (a); var < (b); var++)
#define RFOR(var, a, b)  for (auto var = b - 1; var != a; var--)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;

#define all(c) begin(c),end(c)

#define D(x) do { std::cerr << x << " "; } while (0)
#define D2(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)


template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    if (!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}


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

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

const int MOD = (int) 1e9 + 7;
const int INF = 1 << 29;

void solve() {
    int n;
    cin >> n;
    vi ary(n);
    REP(i, n) cin >> ary[i];

    vi dp(n, INF);
    REP(i, n) {
        auto it = lower_bound(all(dp), ary[i] - 1);
        if (distance(begin(dp), it) == ary[i] - 1)
            *it = ary[i] - 1;
    }

    int res = distance(lower_bound(all(dp), INF), end(dp));
    if(res == n) res = -1;
    cout << res << endl;
}


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

//    cout << solve() << endl;
    solve();
//    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main(int argc,char* argv[]){
    int n,ans=1;
    cin>>n;
    vector<string> s(n);

    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s.begin(),s.end());
    for(int i=1;i<n;i++){
        if(s[i]!=s[i-1]){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 9512
n = int(input())
h = list(map(int,input().split()))
count = 0
key = h[0]
max_count = []
for i in range(1,n):
    if h[i] <= key:
        count += 1
        key = h[i]
    else:
        key = h[i]
        max_count.append(count)
        count = 0
max_count.append(count)
print(max(max_count))


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

const long long MOD = 1000000007;
int main() {
    long long a, b, x;
    cin >> a >> b >> x;

    long long N = max(0LL, (x - b) / (a - b));
    x %= MOD;
    N %= MOD;
    b %= MOD;
    cout << (x + N * b) % MOD << endl;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= i; j++){
            if(i % j == 0 && i % 2 != 0){
                cnt++;
            }
            if(cnt == 8){
                ans++;
            }
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    double an=0;
    CASET{
        double x;
        string s;
        R(x,s);
        if(s[0]=='J')an+=x;
        else an+=x*380000;
    }
    W(an);
    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 <iomanip>
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<long 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; }
#define INF 1LL<<60

int main() {
    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;
    REP(i, N) {
        cout << S[i] << T[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3520
<?php
	$chars = array_fill(97, 26, 0);

	while (!feof(STDIN)) {
		$str = trim(fgets(STDIN));

		$str = strtolower($str);
		$arr = str_split($str);
		foreach ($arr as $char) {
			if (ctype_alpha($char)) {
				$chars[ord($char)]++;
			}
		}
	}

	foreach ($chars as $key => $val) {
		echo chr($key) . " : $val\n";
	}

Measured memory_bytes: 6772
#include <stdio.h>

using namespace std;

int main() {
    int n, l[100];
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
    scanf("%d",&l[i]);        
    }
    int max=0, sum=0;
    for(int i = 0; i < n; i++)
    {
if (max<l[i])max=l[i];
sum+=l[i];
    }
    //printf("%d",sum);
    printf("%s\n",(sum-max >max)?"Yes":"No");

    
    return 0;
}


Measured memory_bytes: 888
def abc(N, A):
    # 答えの準備
    ans = [0] * N
    
    # 繰返し足し算
    for i in range(0, N - 1):
        ans[A[i] - 1] += 1
    
    # 答え
    return(ans)


# バッチスタート
if __name__ == "__main__":
    # 標準入力処理
    # 1行目の入力を数値として扱う
    N = int(input())
    
    # 2行目の入力を数値のリストとして扱う
    A = list(map(int, input().split()))
    
    # 関数呼び出し
    f = abc(N, A)
    
    # 答えの出力
    for fi in f:
        print(fi)


Measured memory_bytes: 32284
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<long long int>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vvl vector<vector<ll> >
#define vvi vector<vector<int> >
#define pl pair<ll,ll>
#define pb push_back
#define PI 3.14159265
#define mod 998244353
#define pb push_back
#define mp make_pair
#define fri(s,n) for(int i=s;i<n;i++)
#define frj(s,n) for(int j=s;j<n;j++)
#define T(i) int i=1;cin>>i;while(i--)
#define vsi vector<set<int> >
#define pii pair<int,int>
#define inf 1e9
#define vpii vector<pair<int,int> >


ll power(ll a,ll b){
    if(b==0)
        return 1;
    if(b&1)
        return a*power(a,b-1);
    ll temp=power(a,b/2);
    return temp*temp;
    }
bool mycompare(ll a,ll b){
    return a>b;
    }
double dp[301][301][301];
double trials(int x,int y,int z,int n){
    if(x<0 || y<0 || z<0)
        return 0.0;
    if(x==0 && y==0 && z==0)
        return 0.0;
    //cout<<x<<" "<<y<<" "<<z<<"\n";
    if(dp[x][y][z]>0.0)
        return dp[x][y][z];
    return dp[x][y][z]=(n+x*trials(x-1,y,z,n)+y*trials(x+1,y-1,z,n)+z*trials(x,y+1,z-1,n))/(x+y+z);
    }
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fast;
    int n;
    cin>>n;
    int x=0,y=0,z=0;
    fri(0,n){
        int temp;
        cin>>temp;
        if(temp==1)
            x++;
        else if(temp==2)
            y++;
        else
            z++;
        }
    memset(dp,-1.0,sizeof dp);
    //vector<vector<vector<double> > > dp(x+1,vector<vector<double> >(y+1,vector<double>(z+1,-1.0)));
    cout<<setprecision(15)<<trials(x,y,z,n);


}


Measured memory_bytes: 216892
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int R;
    while (cin >> R) {
        string re = "AGC";
        if (R < 1200) {
            re = "ABC";
        } else if (R < 2800) {
            re = "ARC";
        }
        cout << re << endl;
    }
}

Measured memory_bytes: 892