akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, num = 1;
  cin >> n;
  
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (a == num) num++;
  }
  
  if (num == 1) cout << -1 << endl;
  else cout << n - num + 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int x;
    cin >> x;
    if(x == 1) cout << 0 << endl;
    else cout << 1 << endl;
    return 0;
}


Measured memory_bytes: 3624
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))

solved = [False] * (n + 1)
wa = [0] * (n + 1)

for i in range(m):
    p_str, s = input().split()
    p = int(p_str)
    if s == "AC":
        solved[p] = True
    else:
        if not solved[p]:
            wa[p] += 1


ac = 0
pe = 0

for i in range(1, n+1):
    if solved[i]:
        ac += 1
        pe += wa[i]

print(ac, pe)

Measured memory_bytes: 75160
#include<stdio.h>
char S[9005],T[9005],a;
int i,j,k,s=0,rl=0;
int main()
{
	gets(S);
	for(i=0,j=0;S[i];j++)
	{
		T[j]=S[i];
		i=i+(S[i]=='e'?3:7);
	}
	for(k=1;k<j;k++)
	{
		if(T[k-1]==T[k])
		{
			if(rl<k-s)
			{
				a=T[k];
				rl=k-s;
			}
			s=k;
		}
	}
	if(rl<k-s)
		a=T[k-1];
	puts(a=='e'?"egg":"chicken");
	return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    int w, h, n;
    cin >> w >> h >> n;
    int xmax = w, xmin = 0;
    int ymax = h, ymin = 0;

    rep(i, n){
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) xmin = max(xmin, x);
        else if (a == 2) xmax = min(xmax, x);
        else if (a == 3) ymin = max(ymin, y);
        else if (a == 4) ymax = min(ymax, y);
    }

    cout << max(xmax-xmin, 0) * max(ymax-ymin, 0) << endl;


    return 0;
}


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

#define int long long

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

#define endl '\n'
#define all(v) v.begin(), v.end()

#define lcm(a, b)  ((a) * ((b) / __gcd((a), (b)) ))
#define print_(x)  cout << #x << " : " << x << endl;
#define dvec(vct)  for(auto i : vct) cout << i << " "; cout << endl;
#define darr(a, n) for(int i = 0; i < n;) cout << a[i++] <<' '; cout<< '\n';



int32_t main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL);
    int x, y, z;
    cin >> x >> y >> z;
    swap(x, y);
    swap(x, z);
    cout << x << " " << y << " " << z << endl;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef double frac;
typedef complex<frac> Pt;
struct less_c{
    bool operator() (const Pt& a, const Pt& b){
	    return a.real()!=b.real() ? a.real()<b.real() : a.imag()<b.imag();
    }
};
frac cross(Pt a, Pt b){ //外積
    return a.real()*b.imag()-a.imag()*b.real();
}

bool in_convex(vector<Pt> p, Pt q){
    vector<Pt> pp=p;
    pp.push_back(q);
    
    int n=pp.size();
    sort(pp.begin(),pp.end(),less_c());
    vector<Pt> ch(2);
    for(int i=0; i<2; i++) ch[i]=pp[i];
    for(int i=2; i<n; i++){
        for(int j=ch.size()-1; j>0; j--){
            if(cross(pp[i]-ch[j],ch[j-1]-ch[j])<0){
                ch.erase(ch.begin()+j);
            }else{
                break;
            }
        }
        ch.push_back(pp[i]);
    }
    
    int half=ch.size()-1;
    ch.push_back(pp[n-2]);
    for(int i=n-3; i>=0; i--){
        for(int j=ch.size()-1; j>half; j--){
            if(cross(pp[i]-ch[j],ch[j-1]-ch[j])<0){
                ch.erase(ch.begin()+j);
            }else{
                break;
            }
        }
        ch.push_back(pp[i]);
    }
    ch.pop_back();

    sort(ch.begin(),ch.end(),less_c());
    sort(p.begin(),p.end(),less_c());
    return ch==p;
}

int main(){
	int n;  cin >> n;
    for(int i=0; i<n; i++){
        int x, y;
        vector<Pt> p(3);
        for(int j=0; j<3; j++){
            cin >> x >> y;
            p[j]={frac(x),frac(y)};
        }
        Pt k, s;
        cin >> x >> y;  k={frac(x),frac(y)};
        cin >> x >> y;  s={frac(x),frac(y)};
        
        cout << (in_convex(p,k)!=in_convex(p,s) ? "OK" : "NG") << endl; 
    }
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
//HDU 627235
//USACO bc083db
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define Forn(i, n) for(int i=1; i<=(n); i++)
#define forn(i, n) for(int i=0; i<(n); i++)
#define foreach(it, a) for(__typeof((a).begin()) it=(a).begin(); it!=(a).end(); it++)
 
/*
    快读有锅 
*/

const int mod=1e9+7;

ll L, R, dp[65][2][2][2];

void print(int S)
{
    forn(i, 10) cout<<(S>>i&1);
    puts("");
}

int voilet(int L, int R)
{
    int ret=0;
    for(int i=L; i<=R; i++)
        for(int j=L; j<=R; j++)
            if(i%j==(i^j))
            {
/*                if((i&j)==j&&__builtin_clz(i)==__builtin_clz(j)) continue;
                print(i);
                print(j);
                print(i%j);
                puts("");*/
                ret++;
            }
    return ret;
}

inline int calc(int x)
{
    int ret=0;
    forn(S, 1<<x)
        ret+=1<<__builtin_popcount(S);
    return ret;
}

ll dfs(int d, int b, int t, int l)
{
    if(d<0) return 1;
    ll &ret=dp[d][b][t][l];
    if(~ret) return ret;
    ret=0;
    forn(nb, 2) for(int nt=nb; nt<2; nt++)
    {
        if(!l&&nb!=nt) continue;
        int th=(R>>d&1);
        int bh=(L>>d&1);
        if(t&&nt>th) continue;
        if(b&&nb<bh) continue;
        ret+=dfs(d-1, b&&(nb==bh), t&&(nt==th), l||nt);
        ret%=mod;
    }
    return ret;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%lld%lld", &L, &R);
    printf("%lld\n", dfs(63, 1, 1, 0));
    return 0;
}

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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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(a > b) { a = b; return true; } return false; }

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    string s; cin >> s;
    cout << "ABC" << s << endl;    
}

Measured memory_bytes: 3648
import java.io.*;

class Main {
  public static void main(String[] args) {
    for (int i = 1; i <= 9; i++) {
      for(int j = 1; j <= 9; j++) {
        System.out.println(i + "x" + j + "=" + (i*j));
      }
    }
  }
}

Measured memory_bytes: 24064
# https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
rr = range


def read_ints():
    return list(map(int, read().split()))


K, T = read_ints()
A = read_ints()
if T == 1:
    # コーナーケース
    print(K - 1)
    exit()

# 差が最も少なくなるように二分割すれば良い
# 二分探索でもいいが線形探索で愚直に合計値を計算しても十分間に合う
A.sort()
ans = 2**31
for i in rr(1, T):
    r = sum(A[:i])
    l = sum(A[i:])
    ans = min(ans, abs(r - l))
print(max(ans - 1, 0))


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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n,p[10000001];

void init()
{
    for (int i=2;i*i<=1e7;++i)
    {
        if (!p[i])
        {
            p[i]=i;
            for (int j=i*i;j<=1e7;j+=i)
                if (!p[j]) p[j]=i;
        }
    }
    for (int i=2;i<=1e7;++i)
        if (!p[i]) p[i]=i;
}

long long solve(int x)
{
    if (x==1) return 1;
    if (p[x]==x) return 2;
    long long kq=1;
    while (x>1)
    {
        int dem=0,r=p[x];
        while (x%r==0)
        {
            dem++;
            x/=r;
        }
        kq*=(dem+1);
    }
    if (x>1) kq*=2;
    return kq;
}

void process()
{
    long long kq=0;
    for (int i=1;i<=n;++i)
    {
        kq+=(solve(i)*i);
    }
    cout<<kq;
}

int main()
{
    scanf("%d",&n);
    init();
    process();
    return 0;
}


Measured memory_bytes: 42724
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c; cin >> a >> b >> c;
    if(a == b && b == c)
    {
        if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1) cout << 0 << endl;
        else cout << -1 << endl;
        return 0;
    }
    ll ans = 0;
    if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1) { cout << 0 << endl; return 0; }
    while(true)
    {
        ll x = b + c;
        ll y = c + a;
        ll z = a + b;
        if(x % 2 != 0 || y % 2 != 0 || z % 2 != 0) break;
        a = x / 2;
        b = y / 2;
        c = z / 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; 
using namespace std;
#define int long long
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mll map<ll,ll>
#define mii map<int,int>
#define mp make_pair
#define pb push_back
#define rep(i,b) for(ll (i)=0;i<(b);i++)
#define all(c) (c).begin(), (c).end()
#define F first
#define S second
#define CLR(p) memset(p, 0, sizeof(p))
#define SET(p) memset(p, -1, sizeof(p))
#define DEBUG true
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
//typedef long long int ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
tree_order_statistics_node_update> new_data_set; 
const int MAX=1e6+5;
#define MOD 1000000007
/*std::cout << std::fixed;
std::cout << std::setprecision(6);*/
//(a%mod-b%mod+mod)%mod



/************************************


 
*************************************/

vector<vector<ll>>v;
ll T=0;
ll cnt1=0,cnt0=0;
vector<ll>dep;
bool visited[MAX];
vector<ll>par;
vector<ll>tin,tout;
vector<ll>col;

int countDivisibles(int A, int B, int M) 
{ 
    
    if (A % M == 0) 
        return (B / M) - (A / M) + 1; 
  
    // A is not divisible by M 
    return (B / M) - (A / M); 
} 







signed main(){
    int t=1;
    // cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int a[n+1];
        a[0]=0;
        rep(i,n){
            cin>>a[i+1];
        }
        bool vis[n+1];
        rep(i,n+1)
            vis[i]=true;
        vis[0]=false;
        for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            if(a[x]<=a[y])
                vis[x]=false;
            if(a[y]<=a[x])
                vis[y]=false;
        }
        int cnt=0;
        for(int i=1;i<n+1;i++){
            if(vis[i]==true)
            cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 4508
n,k=[int(x) for x in input().split()]
ans=0
l=[0]*(k+1)
i=k
mod=1000000007
while i>0:
    l[i]=pow(k//i,n,mod)
    j=2*i
    while j<=k:
        l[i]=(l[i]-l[j]+mod)%mod
        j+=i
    i-=1
for i in range(1,k+1):
    ans+=(l[i]*i)%mod
print(ans%mod)


Measured memory_bytes: 11296
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int d[2010];
int main(){
	int n;cin>>n;
	d[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i-3;j++){
			d[i]+=d[j];
			d[i]%=mod;
		}
	}
	cout<<d[n]<<"\n";
	return 0;
} 

Measured memory_bytes: 3632
n, a, b = map(int, input().split())
mod = 10**9 + 7

def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % mod

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * powerDX(denom, mod-2, mod) % mod

ans = powerDX(2, n, mod) - 1
ans -=  combination(n, a, mod)
ans -=  combination(n, b, mod)
ans += 3*mod
ans %= mod
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (int i=0;i<N;i++)
#define loop(i,N,M) for(int i=N;i<M;i++)

//変数
string s;
int K;

//解法
void solve() {

	vector<vector<int>> alpha(26);
	int size = s.size();
	rep(i, size) {
		alpha[s[i] - 'a'].emplace_back(i);
	}

	set<string> st;

	rep(i, 26) {
		int size2 = alpha[i].size();
		rep(j, size2) {

			rep(k, K) {
				string str = "";
				rep(l, k + 1) {
					if (alpha[i][j] + l < size) str += s[alpha[i][j] + l];
				}
				st.insert(str);
			}

		}

		if (st.size() >= K) break;
	}

	auto itr = st.begin();
	rep(i, K - 1) itr++;

	cout << *itr;

	return;
}

int main() {
	//入力
	cin >> s >> K;
	solve();
	cout << endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> X(N);
  for (int i = 0; i < N; i++){
    cin >> X[i];
  }
  int min = 300000;
  int sum = 0;
  for (int i = 1; i < 101; i++){
    sum = 0;
    for (int j = 0; j < N; j++){
      sum += (i - X[j]) * (i - X[j]);
    }
    if (min > sum){
      min = sum;
    }
  }
  cout << min << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
S = list(input().strip())

tmp = S[0]
ans = 0

for i in range(1, N):
    if tmp == S[i]:
        ans += 1
    tmp = S[i]

print(min(ans+2*K, N-1))

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

using namespace std;

const int nmax = 1e9 + 7;
typedef long long ll;

int main(){
  int N; cin >> N;
  string S; cin >> S;
  S = S[N - 1] + S + S[0];

  int ans[N + 2][4];

  for (int i = 0; i < N + 2; i++){
    for (int j = 0; j < 4; j++){
      ans[i][j] = false;
    }
  }
  
  ans[1][0] = 1; ans[2][0] = 1;
  ans[1][1] = 1; ans[2][1] = 0;
  ans[1][2] = 0; ans[2][2] = 1;
  ans[1][3] = 0; ans[2][3] = 0;

  for (int j = 0; j < 4; j++){
    if (S[1] == 'o'){
      if (ans[1][j] == 1){
        ans[0][j] = ans[2][j];
      }else{
        ans[0][j] = 1 - ans[2][j];
      }
    }else{
      if (ans[1][j] == 1){
        ans[0][j] = 1 - ans[2][j];
      }else{
        ans[0][j] = ans[2][j];
      }
    }
  }
  

  for (int i = 2; i < N + 1; i++){
    for (int j = 0; j < 4; j++){
      if (S[i] == 'o'){
        if (ans[i][j] == 1){
          ans[i + 1][j] = ans[i - 1][j];
        }else{
          ans[i + 1][j] = 1 - ans[i - 1][j];
        }
      }else{
        if (ans[i][j] == 1){
          ans[i + 1][j] = 1 - ans[i - 1][j];
        }else{
          ans[i + 1][j] = ans[i - 1][j];
        }
      }
    }
  }

  bool flag = false;
  for (int j = 0; j < 4; j++){
    if (ans[0][j] == ans[N][j] && ans[1][j] == ans[N+1][j]){
      flag = true;
      for (int i = 1; i <= N; i++){
        if (ans[i][j] == 1){
          cout << "S";
        }else{
          cout << "W";
        }
      }
      cout << endl;
      break;
    } 
  }
  
  if (flag == false){
    cout << -1 << endl;
  }
  
  

  return 0;
}


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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N - 1);
    vector<int> B(N,0);

    rep(i, N - 1)
    {
        cin >> A[i];
    }
    rep(i,N - 1){
        B[A[i] - 1] += 1;
    }
    rep(i,N){
        cout << B[i] << endl;
    }
}


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


int main() {
    int n;
    cin >> n;
    vector<int> x(n,0);
    rep(i,n)cin >> x[i];
    int max_e = *max_element(x.begin(),x.end());
    ll ans = INF;
    rep(i,max_e+1){//ありうる値の全探索
        ll dist = 0;
        rep(j,n){
           dist += pow(x[j] - i,2);
        }
        ans = min(ans,dist);
    }
    cout << ans;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a.at(i);
  int cnt = 0;
  int num = 1;
  for (int i = 0; i < N; i++){
    if (a.at(i) == cnt+1) cnt++;
  }
  if (cnt==0) cout << -1 << endl;
  else cout << N-cnt << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>

int main(){
    int i,j;
    int h,w;
    //char st[301,301];

    for(;;){
        std::cin>>h>>w;

        if(h==0 && w==0){
            //printf("\n");
            break;
        }
        else {
            for(i=1;i<=h;i++){

                for(j=1;j<=w;j++){
                    
                    //st[i,j]='#';
                    //std::cout<<st[i,j];
                    printf("#");
                    if(j==w){
                        printf("\n");
                        break;
                    }
                }
            
            }
            printf("\n");
        }

    }
    return 0;
}


Measured memory_bytes: 3084
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
typedef pair<int,int> P;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define rep(i, n) for (lint i = 0; i < (n); i++)
#define INF INT_MAX
#define all(x) (x).begin(),(x).end()
#define pb push_back
lint d[205][205]={0};
lint n,m,r;
vector<lint> vr;
lint res=INF;
int main(){
    cin>>n>>m>>r;
    rep(i,n){
        rep(j,n){
            if(i!=j){
                d[i][j]=INF;
            }
        }
    }
    vr.resize(r);
    rep(i,r) {
        cin>>vr[i];
        vr[i]--;
    }   
    rep(i,m){  
        lint a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        d[a][b]=c;
        d[b][a]=c;
    }     
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
             for(int j=0;j<n;j++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }  
        }
    }
    sort(vr.begin(),vr.end());
    do{
        lint sum=0;
        for(int i=0;i<r-1;i++){
            sum+=d[vr[i]][vr[i+1]];
        }
        res=min(res,sum);
    }while (next_permutation(vr.begin(), vr.end()));
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <map>
#include <array>
#include <cassert>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair

template <typename T>
bool uax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template <typename T>
bool uin(T& a, T b) { if (b < a) { a = b; return true; } return false; }

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef list<int> li;
typedef vector<li> vli;
typedef vector<vpi> vvpi;
typedef long long i64;

const int inf = 1e9;

void solve_a() {
  int a,b,c;
  cin >> a >> b >> c;
  i64 k;
  cin >> k;
  // a, b, c = a-b
  // b+c, a+c, a+b = b-a
  // 2a+b+c, 2b+a+c, 2c+a+b = a-b
  // 2a+3b+3c, 3a+2b+3c, 3a+3b+2c = b-a
  a = (k & 1) ? b - a : a - b;
  cout << a << endl;
}

void solve_b() {
  int n; cin >> n;
  vi a(n); forn(i, n) cin >> a[i];
  vi b(n + 1, 0);
  for(int x: a) b[x] = b[x-1] + 1;
  cout << n - *max_element(all(b)) << endl;
}

int main() {
#ifdef HOME
  freopen("input.txt", "rt", stdin);
#endif
  solve_b();
  return 0;
}


Measured memory_bytes: 1792
N, K = list(map(int, input().split()))
H = list(map(int, input().split()))

H.sort(key=lambda x: -x)

c = min(K, N)

i = 0
while 0 < c:
    H[i] = 0
    c -= 1
    i += 1

ans = 0
for j in range(i, N):
    ans += H[j]

print(ans)

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

using namespace std;

int main(){
    string s;
    cin>>s;
    sort(s.begin(),s.end());


    string first;
    string second;

    int flag=0;
    for(auto x:s){

        if(flag==0){
        first+=x;
        flag=1;
        }

        else if(flag==1){
         second+=x;
         flag=0;
        }
    }


    if(first==second){
     cout<<"Yes";
    }
    else{
        cout<<"No";
    }


return 0;
}



Measured memory_bytes: 256
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=50+10;
const int inf=0x3f3f3f3f;

int n;

struct V {
	vector<int> E[N];
	int deg[N];
	void addEdge(int u,int v) {
		E[u].emplace_back(v),++deg[v];
	}

	void init() {
		for (int i=1;i<=n;++i) E[i].clear(),deg[i]=0;
	}

	int fa[N];
	void dfs(int u,int f) {
		fa[u]=f;
		for (int v:E[u]) if (v!=f) dfs(v,u);
	}
} A,B,G;

int check(int u) { return A.fa[u]==B.fa[u]; }
int calc() {
	int res=0;
	for (int i=1;i<=n;++i) if (!check(i)) ++res;
	G.init();
	for (int i=1;i<=n;++i) {
		if (check(i)) {
			if (!check(A.fa[i])) return inf;
			else continue;
		}
		if (!check(A.fa[i])) G.addEdge(i,A.fa[i]);
		if (!check(B.fa[i])) G.addEdge(B.fa[i],i);
	}
	queue<int> Q; int cnt=0;
	for (int i=1;i<=n;++i) if (!G.deg[i]) Q.push(i);
	while (!Q.empty()) {
		int u=Q.front(); Q.pop(); ++cnt;
		for (int v:G.E[u])
			if (!--G.deg[v]) Q.push(v);
	}
	return cnt==n?res:inf;
}

int main() {
	int T=read();
	while (T--) {
		n=read(); A.init(),B.init();
		for (int i=1;i<n;++i) {
			int u=read(),v=read();
			A.addEdge(u,v),A.addEdge(v,u);
		}
		for (int i=1;i<n;++i) {
			int u=read(),v=read();
			B.addEdge(u,v),B.addEdge(v,u);
		}
		int ans=inf;
		for (int i=1;i<=n;++i) {
			A.dfs(i,0),B.dfs(i,0),ans=min(ans,calc());
			if (A.deg[i]!=1) continue;
			for (int j=1;j<=n;++j) {
				if (i==j) continue;
				A.dfs(j,i),A.fa[i]=0,ans=min(ans,calc()+1);
			}
		}
		if (ans==inf) puts("-1");
		else printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3728
#include<bits/stdc++.h>
using namespace std;
int a[2005];
int main()
{
    int n,z;
    cin>>n>>a[0]>>z;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    if(n==1)cout<<abs(z-a[1]);
    else cout<<max(abs(z-a[n]),abs(a[n]-a[n-1]));
    return 0;
}


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

int vinarySearch(int a[], int n, int key){
	int left = 0, right = n;
	while(left < right){
		int mid = (left+right)/2;
		if(a[mid] == key)
			return key;
		else if(key < a[mid])
			right = mid;
		else
			left = mid+1;
	}
	return -1;
}

int main(){
	int n, s[100000], q, t[50000], cnt = 0;
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> s[i];
	cin >> q;
	for(int i = 0; i < q; i++)
		cin >> t[i];
	for(int i = 0; i < q; i++){
		if(vinarySearch(s, n, t[i]) == t[i])
			cnt++;
	}
	cout << cnt << endl;
}


Measured memory_bytes: 3664
#include <iostream>

using namespace std;

int main()
{
	int H, W;
	string s[50];
	string s2[50];

	cin >> H >> W;
	for ( int i = 0; i < H; i++ ) {
		cin >> s[i];
	}

	for ( int i = 0; i < H; i++ ) {
		for ( int j = 0; j < W; j++ ) {
      if ( s[i].substr(j,1) == "#" ) {
        s2[i] += "#";
        continue;
      }
			int cnt = 0;
			if ( j-1 >= 0 && i-1 >= 0 ) { if (s[i-1].substr(j-1,1) == "#") cnt++; }	// j-1, i-1
			if ( i-1 >= 0 )             { if (s[i-1].substr(j,1) == "#") cnt++; }	// j,   i-1
			if ( j+1 < W && i-1 >= 0 )  { if (s[i-1].substr(j+1,1) == "#") cnt++; }	// j+1, i-1
			if ( j-1 >= 0 )             { if (s[i].substr(j-1,1) == "#") cnt++; }	// j-1, i
			// j,   i	自分は入れない
			if ( j+1 < W )              { if (s[i].substr(j+1,1) == "#") cnt++; }	// j+1, i
			if ( j-1 >= 0 && i+1 < H )  { if (s[i+1].substr(j-1,1) == "#") cnt++; }	// j-1, i+1
			if ( i+1 < H )              { if (s[i+1].substr(j,1) == "#") cnt++; }	// j,   i+1
			if ( j+1 < W && i+1 < H )   { if (s[i+1].substr(j+1,1) == "#") cnt++; }	// j+1, i+1
			s2[i] += std::to_string(cnt);
		}
	}

	for ( int i = 0; i < H; i++ ) {
		cout << s2[i] << endl;
	}

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

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

  set<int> num;
  num.insert(1);
  int x = 6;
  while(x <= n){ num.insert(x); x *= 6; }
  x = 9;
  while(x <= n){ num.insert(x); x *= 9; }

  vi dp(n+1,INF); //iを作るために必要な最小回数
  dp[0] = 0;
  for(int i = 0; i <= n; i++){
    for(auto x : num) if(i+x <= n) chmin(dp[i+x],dp[i]+1);
  }
  cout << dp[n];
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FOR(i, n) for(int i = 0; i < (n); i ++)
#define COUT(val) cout << (val) << "\n";
using namespace std;

int main(void){
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    FOR(i, n) cin >> h[i];
    
    vector<int> dp(100000, 1e9);
    dp[0] = 0;
    for(int i = 1; i < n; i ++){
        for(int j = 1; j <= k; j ++){
            if(i-j < 0) break;
            dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
        }
    }
    
    COUT(dp[n-1]);
}

Measured memory_bytes: 1024
N,M = map(int,input().strip().split())


def and_array(As,Bs):
    res = []
    for a in As:
        if a in Bs:
            res.append(a)

    return res


tmp = list(map(int, input().strip().split()))[1:]
for i in range(0,N - 1):
    tmp = and_array(tmp, list(map(int, input().strip().split()))[1:])

print(len(tmp))


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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  else return 0;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key%M; }
int h2(int key){ return 1+(key%(M-1)); }

int find(char str[]){

    long long key, i, h;
    key = getKey(str);
    for (i=0;;i++){
        h=(h1(key)+i*h2(key))%M;
        if (strcmp(H[h],str)==0) return 1;
        else if (strlen(H[h])==0) return 0;
    }
    return 0;

}

int insert(char str[]){

    long long key, i, h;
    key=getKey(str);
    for (i =0; ; i++){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return 1;
        else if(strlen(H[h])==0){
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;

}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}


Measured memory_bytes: 17064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define PI 3.141592653589793
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){ 
    ll N;
    cin >> N;
    pair<ll, ll> robot[N];
    for(int i = 0; i < N; i++){
        ll Xtmp,Ltmp;
        cin >> Xtmp;
        cin >> Ltmp;
        robot[i].first = Xtmp+Ltmp;//右
        //if(robot[i].first > 1000000000) robot[i].first = 1000000000;
        robot[i].second = Xtmp-Ltmp;//左
        if(robot[i].second < 0) robot[i].second = 0;
    }
    sort(robot, robot+N);
    
    ll t = 0;
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        if( t <= robot[i].second){
            ans++;
            t = robot[i].first;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF (1<<25)
 
int main(){
	int n , v[20] , X[41] , Y[41] , top;
	while(scanf("%d\n",&n)&& n){
		int dp2[21] = {0};
		for(int i = 0 ; i < n ; i++) scanf("%d",&v[i]);
		sort(v,v+n,greater<int>());
		for(int i = n-1 ; i >= 0 ; i--) dp2[i] = dp2[i+1] + v[i];
		
		int ans = INF;
		
		top = 0;
		X[top] = Y[top] = 0;
		while(~top){
			int pos = X[top] , sum = Y[top]; top--;
			if(pos==n) ans = min(ans,sum);
			else{
				if( sum >= dp2[pos] && ans <= sum-dp2[pos] ) continue; // ツ枝ツ偲ォ
				X[++top] = pos+1 , Y[top]   = sum+v[pos];
				X[++top] = pos+1 , Y[top]   = abs(sum-v[pos]);
			}
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 0
from fractions import gcd
N, K = map(int, input().split())
A = list(map(int, input().split()))
if K in A:
  print('POSSIBLE')
elif K > max(A):
  print('IMPOSSIBLE')
else:
  A_gcd = A[0]
  for i in range(1, N):
    A_gcd = gcd(A_gcd, A[i])

  if K % A_gcd == 0:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
    

Measured memory_bytes: 16100
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define Cout(n) cout<<(n)<<endl
#define INF 1000000000000000000LL

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << ", ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

int main()
{
	string s;
	cin >> s;
	if(SIZE(s)%2==0 ^ s[0]==s[SIZE(s)-1]) cout << "Second\n";
	else cout << "First\n";
	return 0;
}


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

int main(){
  int N; cin >> N;
  ll A[N+1], B[N];
  rep(i,N+1) cin >> A[i];
  rep(i,N) cin >> B[i];

  ll cnt = 0;
  rep(i,N){
    if (B[i]>A[i]){
      B[i] -= A[i];
      if (B[i]>A[i+1]){
        cnt += A[i]+A[i+1];
        A[i+1] = 0;
      }
      else {
        cnt += A[i]+B[i];
        A[i+1] -= B[i];
      }
    }
    else cnt += B[i];
  }

  cout << cnt << endl;


  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int A[10005],B[10005];
int h,n;

int buf[10005];
int i;

int DP(int x){
  int i,a,minf;
  if(x<=0) return 0;
  if(buf[x]!=-1)return buf[x];
  else{
    minf=1000000000;
    
    for(i=0;i<n;i++){
      a = DP(x-A[i])+B[i];
      
      if(minf > a) {minf =a;}
    }
     buf[x]=minf;
     return minf;
  }
}

int main(){
  scanf("%d %d",&h,&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&A[i],&B[i]);
  }
  for(i=0;i<10005;i++){
    buf[i]=-1;
  }
  printf("%d",DP(h));
  return 0;
}
  
// 参考　cslg093119134様：　
//　https://atcoder.jp/contests/abc153/submissions/9822382

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
const long long INF = 1LL << 60;
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; }

int main(){
    int N;
    cin >> N;
    vector<long long> A(N);
    rep(i, N){
        cin >> A.at(i);
        if(A.at(i)==0){
            cout << 0 << endl;
            return 0;
        }
    }
    sort(A.rbegin(),A.rend());

    long long ans = 1;
    rep(i, N){
        if(A.at(i) > 1000000000000000000/ans){
            cout << -1 << endl;
            return 0;
        }else{
            ans *= A.at(i);
        }
    }
    cout << ans << endl;

    return 0;  
}

Measured memory_bytes: 4024
#include <iostream>
 
using namespace std;
 
int value[3][101];
int sum[3][101];
 
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> value[1][i];
	for (int i = 1; i <= n; i++) cin >> value[2][i];
	for (int i = 0; i <= 2; i++) sum[i][0] = 0;
	for (int i = 0; i <= n; i++) sum[0][i] = 0;
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= n; j++)
			sum[i][j] = max(sum[i][j - 1], sum[i - 1][j]) + value[i][j];
	cout << sum[2][n] << endl;
}//parshant

Measured memory_bytes: 256
#include<stdio.h>
int f(int a,int b){
  if(b==0)return a;
  return f(b,a%b);
}
int main(){
  int a,b,g;
  while(scanf("%d %d",&a,&b)!=EOF){
    if(a<b)g=f(b,a);
    else   g=f(a,b);
    printf("%d ",g);
    b/=g;
    printf("%d\n",a*b);
  }
  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;
const int inf=1e18;

int32_t main(){
	IOS;
	string s;
	cin>>s;
	string ans[8];
	ans[7]="SUN";
	ans[6]="MON";
	ans[5]="TUE"; 
	ans[4]="WED"; 
	ans[3]="THU"; 
	ans[2]="FRI";
	ans[1]="SAT";
	ans[0]="asdsadsa";
	for(int i=0;i<8;i++){
		if(ans[i]==s){
			cout<<i<<endl;
		}
	}
} 

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long ll;
const ll N = 200005, inf = 3e9;
ll n, m, pre[N], target[N], last[N], t, a[N], cnt, minn[N], f[N], ans;
priority_queue <ll, vector<ll>, greater<ll> > q;
bool wulala;
void add(ll x, ll y)
{
	t++;
	pre[t] = last[x];
	target[t] = y;
	last[x] = t;
}

bool vis[N];
void dfs1(ll x, ll fa)
{
	f[x] = fa;
	vis[x] = 1;
	minn[fa] = min(minn[fa], a[x]);
	for (ll ptr = last[x]; ptr; ptr = pre[ptr])
	{
		ll xx = target[ptr];
		if (!vis[xx])
			dfs1(xx, fa);
	}
}

void dfs2(ll x, ll fa)
{
	vis[x] = 1;
	if (wulala == 0 || a[x] != minn[fa]) q.push(a[x]);
	if (wulala == 1 && a[x] == minn[fa]) wulala = 0;
	for (ll ptr = last[x]; ptr; ptr = pre[ptr])
	{
		ll xx = target[ptr];
		if (!vis[xx])
			dfs2(xx, fa);
	}
}

int main()
{
	cin >> n >> m;
	for (ll i = 1; i <= n; i++) cin >> a[i];
	for (ll i = 1; i <= m; i++)
	{
		ll x, y;
		cin >> x >> y;
		x++, y++;
		add(x, y);
		add(y, x);
	}
	for (ll i = 1; i <= n; i++) minn[i] = inf;
	for (ll i = 1; i <= n; i++)
	{
		if (!f[i])
		{
			cnt++;
			dfs1(i, i);
			memset(vis, 0, sizeof(vis));
			wulala = 1;
			dfs2(i, i);
			memset(vis, 0, sizeof(vis));
		}
	}
	if (cnt == 1)
	{
		cout << 0 << endl;
		return 0;
	}
	ll now = 0;
	while (!q.empty() && now < cnt - 2)
	{
		now++;
		ans += q.top();
		q.pop();
	}
	if (now < cnt - 2)
	{
		cout << "Impossible" << endl;
		return 0;
	}
	for (ll i = 1; i <= n; i++)
		if (f[i] == i) ans += minn[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 10232
#include <stdio.h>
#define N 10000

int main(){
  int n, a[N], i, x=0;
  scanf("%d", &n);
  for(i=1;i<=n;i++){
    scanf("%d", &a[i]);
    while(a[i]%2 == 0){
      a[i] /= 2;
      x++;
    }
  }
  printf("%d\n", x);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
//combination(Nが小さい時はこれを使う)
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
int COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

//繰り返し二乗法（Nが大きい時の場合のcombination)
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= (i % mod); res %= mod;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
//UnionFind
class UnionFind {
protected:
	int* par, * rank, * size;
public:
	UnionFind(unsigned int size) {
		par = new int[size];
		rank = new int[size];
		this->size = new int[size];
		rep(i, size) {
			par[i] = i;
			rank[i] = 0;
			this->size[i] = 1;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		if (rank[n] < rank[m]) {
			par[n] = m;
			size[m] += size[n];
		}
		else {
			par[m] = n;
			size[n] += size[m];
			if (rank[n] == rank[m])rank[n]++;
		}
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
int dight(int n) {
	int ans = 1;
	while (n >= 10) {
		n /= 10;
		ans++;
	}
	return ans;
}
int dight_sum(int n) {
	int sum = 0;
	rep(i, 20)sum += (n % (int)pow(10, i + 1)) / (pow(10, i));
	return sum;
}
signed main() {
	string s;
	cin >> s;
	int ans = 0;
	rep(i, 3) {
		if (s[i] == '1')ans++;
	}
	cout << ans << endl;
	ggr
}


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

using namespace std;
template <typename T> void print(T vec) {for(auto d: vec) cout<<d<<' ';cout<<'\n';}
template<typename T> void print2D(T mat) {for(auto vec:mat) print(vec);}



void vacation(vector<vector<int>> &vac) {

    for(int i = 1; i < vac.size(); i++) {
        vac[i][0] += max(vac[i-1][1], vac[i-1][2]);
        vac[i][1] += max(vac[i-1][2], vac[i-1][0]);
        vac[i][2] += max(vac[i-1][0], vac[i-1][1]);
    }
}


int main() {
    int n;
    cin>>n;
    vector<vector<int>> A(n, vector<int>(3));
    for(int i = 0; i< n;i++) cin>>A[i][0]>>A[i][1]>>A[i][2];
    vacation(A);
    cout<<*max_element(A[n-1].begin(), A[n-1].end())<<'\n';
    return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
const int MAX_C = 2010;
long long Com[MAX_C][MAX_C] = {0};

int main(){
  int N; cin >> N; int a[N];
  rep(i, N){
    cin >> a[i];
  }
  sort(a, a+N);
  int ans = a[N/2] - a[(N-2)/2];
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = 2e9;
const int MAX_HW = 100;

int W, B;
int h, w;
vector<string> field;

int main() {
  cin >> W >> B; W--; B--;
  h = w = MAX_HW;

  for (int i = 0; i < MAX_HW; i++) {
    string tmp(MAX_HW, (i<MAX_HW/2)?'#':'.');
    field.pb(tmp);
  }
  int y = 0, x = 0;
  for (int i = 0; i < W; i++) {
    field[y][x] = '.';
    x += 2;
    if (x >= MAX_HW) {
      x = 0; y += 2;
    }
  }
  y = MAX_HW/2+1, x = 0;
  for (int i = 0; i < B; i++) {
    field[y][x] = '#';
    x += 2;
    if (x >= MAX_HW) {
      x = 0; y += 2;
    }
  }
  cout << MAX_HW << " " << MAX_HW << endl;
  for (int i = 0; i < MAX_HW; i++) {
    cout << field[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int main(){
	int n;
	cin>>n;
	vi a(n);
	rep(i, n) cin>>a[i];
	ll ans = 0LL;
	if(n == 1){
		ans = a[0]/2;
	}
	else{
		rep(i,n-1){
			if((a[i]&1) && a[i+1]>0){
				a[i]++;
				a[i+1]--;
			}
			ans += a[i]/2;
		}
		ans += a[n-1]/2;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 640
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
import Data.Array.IArray
--import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
dictCompare :: [a -> a -> Ordering] -> a -> a -> Ordering
dictCompare [] _ _ = EQ
dictCompare (f:fs) x y = let c = f x y in if c==EQ then dictCompare fs x y else c
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
binMaybe :: (a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
binMaybe _ Nothing my = my
binMaybe _ mx Nothing = mx
binMaybe f (Just x) (Just y) = Just (f x y)
-- end of templete



f n m ds cs = runST $ do
    let da = listArray (1,n) ds :: Array Int Int
    arr <- newArray (0,n) Nothing :: ST s (STArray s Int (Maybe Int))
    writeArray arr 0 $ Just 0
    forM cs $ \c -> do
        forM [n,n-1 .. 1] $ \i -> do
            binMaybe min <$> fmap (+(c * (da!i))) <$> readArray arr (i-1) <*> readArray arr i >>= writeArray arr i
    fromMaybe (-1) <$> readArray arr n

main = do
    [n, m] <- getInts
    ds <- replicateM n getInt
    cs <- replicateM m getInt
    print $ f n m ds cs


Measured memory_bytes: 298052
#include<bits/stdc++.h>
using namespace std;
const unsigned int MOD = 1000000007;
#define ll long long
#define PI 3.1416
string day[]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
vector<string>v;
void dfs(string str,string t="",int cnt=0){
    if(cnt==2){
        v.push_back(t);
        return;
    }else{
        for(int i=0;i<str.size();i++){
            dfs(str,t+str[i],cnt+1);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int t,x;
    while(cin>>t>>x){
        cout<<fixed<<setprecision(10)<<(float)t/x<<endl;
    }
    return 0;
}


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

int main(){
    ll n,a,b;
    cin>>n>>a>>b;
    if(a==0)cout<<'0'<<endl;
    else{
        ll c=a+b;
        ll num,ans,ex;
        num=n/c;
        if(n-c*num<a)ex=n-c*num;
        else ex=a;
        ans=a*num+ex;
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 256