akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    ticket = input()
    N = 4
    num_list = []
    for num in ticket:
        num_list.append(int(num))

    for bit in range(1 << (N-1)):
        sum_value = num_list[0]
        op_list = [None] * N

        for i in range(N-1):
            if bit & (1 << i):
                # +を入れるパターン
                op_list[i] = "+"
                sum_value += num_list[i+1]
            else:
                # -を入れるパターン
                op_list[i] = "-"
                sum_value -= num_list[i+1]

        if sum_value == 7:
            op_list[3] = "="
            for num, op, in zip(num_list, op_list):
                print(num, op, sep="", end="")
            print(7)
            exit()

if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll q;cin>>q;
  for(ll i=0;i<q;i++){
    ll x,y;
    cin>>x>>y;
    if(x>y)swap(x,y);
    long double k=sqrt(x*y-0.75)-x+0.5;
    cout<<(ll)(x-1+k+(x*y-1)/(x+k))-(x!=y)<<endl;
  }
}


Measured memory_bytes: 3604
(* O(|s|) *)
let s = read_line ()
let i = ref @@ String.length s - 1
let ws = [|"dream"; "dreamer"; "erase"; "eraser"|]
let f b w =
  if b then b
  else let m = String.length w in if String.sub s (max 0 @@ !i - m + 1) m = w then (i := !i - m; true) else b
let _ =
  while !i >= 0 do if not @@ Array.fold_left f false ws then (print_endline "NO"; exit 0) done;
  print_endline "YES"

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
int dp[41][405][405];

int main(){
    int n, ma, mb;
    cin >> n >> ma >> mb;
    int a[50], b[50], c[50];
    for(int i = 0; i < n; ++i)
        cin >> a[i] >> b[i] >> c[i];
    for(int i = 0; i <= 40; ++i){
        for(int j = 0; j <= 400; ++j){
            for(int k = 0; k <= 400; ++k){
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;
    int ans = INF;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= 400; ++j){
            for(int k = 0; k <= 400; ++k){
                if(dp[i][j][k] == INF)      continue;
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
                if((j != 0 && k != 0) && j*mb == k*ma){
                    ans = min(ans, dp[i+1][j][k]);
                }
                if(j+a[i] <= 400 && k+b[i] <= 400){
                    dp[i+1][j+a[i]][k+b[i]] = min(dp[i][j][k]+c[i], dp[i+1][j+a[i]][k+b[i]]);
                    if((j+a[i])*mb == (k+b[i])*ma){
                        ans = min(ans, dp[i+1][j+a[i]][k+b[i]]);
                    }
                }
            }
        }
    }

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

Measured memory_bytes: 26496
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
signed main(){
    int a,b;cin >>a  >> b;
    if(a%3 == 0|| b%3 == 0 ||(a+b)%3 == 0)cout << "Possible" <<endl;
    else cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.lang.Math;
import java.math.*;

public class Main {
    public final static long MOD = 1000000007;

    public static void main(String[] args) {
        FS reader = new FS();
        // write reader
        long H = reader.nextLong();
        long ans = 0;
        long monster = 1;
        while (H>0) {
            ans += monster;
            monster *= 2;
            H /= 2;
        }
        System.out.println(ans);
    }

    // Read Class
    static class FS {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
    
        private int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
        private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
        private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public int nextInt() {
            return (int)nextLong();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if(b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
    }
}



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

long long n, maxn = 0;
vector<string> s, res;
map<string, long long> mp;

int main() {
  cin >> n;
  s.resize(n);
  for(int i = 0; i < n; ++i) {
    cin >> s[i];
    ++mp[s[i]];
  }
  for(auto now : mp) maxn = max(maxn, now.second);

  for(auto now : mp)
    if(now.second == maxn) res.push_back(now.first);
  sort(res.begin(), res.end());
  for(auto t : res) cout << t << endl;
  return 0;
}

Measured memory_bytes: 28404
# coding: utf-8
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


def main():
    x = ni()
    now = 100
    cnt = 0
    while 1:
        if now >= x:
            print(cnt)
            return
        now = int(now*1.01)
        cnt += 1
    return


if __name__ == '__main__':
    main()

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

int main(){
    int n,x=0,i;
    cin>>n;
    while(n--){
        x=0;
        string a,b,c="";
        cin>>a>>b;
        if(a.length()>80||b.length()>80){
            cout<<"overflow"<<endl;
            continue;
        }
        if(a.length()>b.length())swap(a,b);
        b='0'+b;
        while(a.length()<b.length())
            a='0'+a;
        char m;
        for(i=a.length()-1;i>0;i--){
            m=('0'+(a[i]-'0'+b[i]-'0'+x)%10);
            x=(a[i]-'0'+b[i]-'0'+x)/10;
            c=m+c;
        }
        if(x>0){
            m=('0'+x);
            c=m+c;
        }
        if(c.length()>80)
            cout<<"overflow"<<endl;
        else cout<<c<<endl;
    }
}

Measured memory_bytes: 1216
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<fstream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

    // input
    ll N;
    cin >> N;

    vector<ll> A(N);
    FOR(i, 0, N){
        cin >> A.at(i);
    }

    vector<ll> B(N);
    FOR(i, 0, N){
        cin >> B.at(i);
    }

    ll sumA = 0;
    for(ll a : A){
        sumA += a;
    }

    ll sumB = 0;
    for(ll b : B){
        sumB += b;
    }

    ll diff = sumB - sumA;
    if(diff<0){
        p_no();
        return 0;
    }

    // できるとしたらこの回数
    ll a_num = diff;
    ll b_num = diff;

    FOR(i, 0, N){
        ll a = A[i];
        ll b = B[i];

        if(a==b) continue;

        // 同じになるか、超すまでaに2を足す
        if(b>a){
            ll diff = b-a;
            ll add_num = (diff+1) / 2;
            a_num -= add_num;
            a += 2 * add_num;
        }

        // 同じになるまでbに1をたす
        if(a>b){
            b_num -= a-b;
            b = a;
        }
    }

    if(a_num==0 && b_num==0){
        p_yes();
    }else if(a_num>0 && b_num>0 && b_num==a_num*2){
        p_yes();
    }else{
        p_no();
    }
    
    return 0;
}

Measured memory_bytes: 384
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func main() {
	sc := NewScanner()
	N := sc.nextInt()
	d := len(strconv.Itoa(N))
	if d < 3 {
		fmt.Println(0)
		return
	}
	arr := []int{}
	var dfs func(nums []int, n, digit int)
	dfs = func(nums []int, n, digit int) {
		if n == digit {
			set := make(map[int]bool)
			for _, v := range nums {
				set[v] = true
			}
			if len(set) == 3 {
				arr = append(arr, toNum(nums))
			}
			return
		}
		nums = append(nums, 3)
		dfs(nums, n+1, digit)
		nums = nums[:len(nums)-1]

		nums = append(nums, 5)
		dfs(nums, n+1, digit)
		nums = nums[:len(nums)-1]

		nums = append(nums, 7)
		dfs(nums, n+1, digit)
		nums = nums[:len(nums)-1]
	}
	for i := 3; i <= d; i++ {
		dfs([]int{}, 0, i)
	}
	ans := 0
	for _, v := range arr {
		if v <= N {
			ans++
		}
	}
	fmt.Println(ans)
}

func toNum(nums []int) int {
	res := 0
	for _, n := range nums {
		res *= 10
		res += n
	}
	return res
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl 
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl 
#define no cout<<"no"<<endl
#define vec(a,y,x)  vector<vector<char>> a (y,vector<char>(x))
const vector<int> dx={1,0,-1,0};
const vector<int> dy={0,1,0,-1};

int main(){
  int k;
  cin>>k;
  vector<vector<vector<int>>> nan(k+1, vector<vector<int>>(k+1, vector<int>(k+1)));
  for(int i=1;i<=k;i++){
    for(int j=i;j<=k;j++){
      for(int l=j;l<=k;l++){
        nan.at(i).at(j).at(l)=gcd(i,gcd(j,l));
      }
    }
  }
  int sum=0;
  rep(i,k){
    rep(j,k){
      rep(l,k){
        
        vector<int> vece(3);
        vece.at(0)=i+1;
        vece.at(1)=j+1;
        vece.at(2)=l+1;
        sort(all(vece));
        sum+=nan.at(vece.at(0)).at(vece.at(1)).at(vece.at(2));
      }
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 36464
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N = 3005;
double dp[N][N];
double p[N];
ll n;
double Func(ll coins, ll heads) {
	if (heads == 0)
		//if head become zero and we have some coins so, probability of atleast 0 head is 1
		return 1;
	if (coins == 0)
		//head are required are greater than 0 and coins are zero thus prob =0
		return 0;
	if (dp[coins][heads] > -1) {
		return dp[coins][heads];
	}
	double op1 = p[coins] * Func(coins - 1, heads - 1);
	double op2 = (1 - p[coins]) * Func(coins - 1, heads);
	dp[coins][heads] = op1 + op2;
	return dp[coins][heads];
}
int main() {

	memset(dp, -1, sizeof dp);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	cout << fixed << setprecision(10) << Func(n, (n + 1) / 2) << endl;
}


Measured memory_bytes: 70912
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

LL ans;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s,a,b;
	cin>>n>>s;
	map<pair<string,string>,int > m;
	for(int i=0;i<(1<<n);++i) {
		a=b="";
		for(int j=0;j<n;++j)
			if(i&(1<<j)) {
				a+=s[j];
			}
			else b+=s[j];
		m[mp(a,b)]++;
	}
	for(int i=0;i<(1<<n);++i) {
		a=b="";
		for(int j=n-1;j>=0;--j)
			if(i&(1<<j)) {
				b+=s[j+n];
			}
			else a+=s[j+n];
		ans+=m[mp(a,b)];
	}
	cout<<ans<<endl;

}

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

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ans += r - l + 1;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    ll n,k,q;
    cin >> n >> k >> q;
    vector<int> v(n,0);
    REP(i,q) {
        int x;
        cin >> x;
        v[x-1]++;
    }

    string ans;
    REP(i,n) {
        if (k - q + v[i] > 0) {
            ans += "Yes\n";
        } else {
            ans += "No\n";
        }
    }

    cout << ans;

    return 0;
}

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

using namespace std;

#define int long long

int n, l;
vector<int> a;

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>l>>n;
	int L = l;
	a.resize(n);
	for(int i = 0; i < n; i++) cin>>a[i];
	
	int best = max(a[n-1], l - a[0]);
	//first go positive then negative
	for(int T = 0; T < 2; T++){
		vector<int> pref(n+1);
		for(int i = 0; i < n; i++){
			if(i > 0)pref[i] = pref[i-1] + a[i];
			else pref[i] = a[i];
		}
		
		for(int i = 0; i < n-1; i++){
			//do tak tak from here
			int cur = 2*a[i];
			int mid = i+(n-i-1)/2; 
			cur += (pref[mid] - pref[i])*2;
			cur += (L*(n-mid-1) - (pref[n-1] - pref[mid]))*2;
			if((n-i-1)%2 == 1) cur -= L - a[mid+1];
			else cur -= a[mid];
			
			//cout<<T<<": "<<i<<" "<<cur<<endl;
			best = max(best, cur);
		}
		
		
		reverse(a.begin(), a.end());
		for(int i = 0; i < n; i++) a[i] = L - a[i];
		
	}
	cout<<best<<endl;
	
}

Measured memory_bytes: 3428
import java.util.*;

public class Main {
	static final int r = 1000000000 + 7;
	public static long total(int n) {
		return ((long)n * (long)(n + 1)) / (long)2;
	}
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		sc.close();
		long ans = 0, min = 0, max = 0, total = total(n);
		for (int i = k; i <= n + 1; ++i) {
			min = total(i - 1);
			max = total - total(n - i);
			// System.out.println("[\n" + min + "\n" + max + "\n" + i + " ]");
			ans += max - min + 1;
			ans %= r;
			// System.out.println(ans);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 35928
// 見せてやるぜ、奇跡ってやつをよぉ……
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll r; cin >> r;
    cout << r * r << '\n';
    return 0;
}


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

int main ()
{
    ll x;
    cin>>x;
    ll s=100;
    int countt;
    for(countt=1;s<x;countt++)
        s+=s/100;
    cout<<countt-1<<endl;
	return 0;
}


Measured memory_bytes: 3636
def solve():
    K, N = map(int,input().split())
    An = list(map(int,input().split()))
    dsum = 0
    dmax = 0

    for i in range(N):
        if i == 0:
            d = An[i] + K - An[N-1]
        else:
            d = An[i] - An[i-1]
        if d > dmax:
            dmax = d
        dsum += d
    print(dsum-dmax)

solve()


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

int main() {
    int N;
    cin >> N;
    set<int> d;
    for(int i = 0; i < N; i++){
        int in;
        cin >> in;
        d.insert(in);
    }
    cout << d.size() << endl;
}

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


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

    int N, K;
    cin >> N >> K;
    int h[N];
    rep(i, N) cin >> h[i];
    sort(h, h+N);
    int ans = 1e9;
    for(int i=K-1; i<N; i++){
        ans = min(h[i]-h[i-(K-1)], ans);
    }
    cout << ans << endl;
}


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

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}

int main(void)
{
    const int N_MAX = 200000;
    int N;
    int a[N_MAX];
    int b[N_MAX];
    cin >> N;
    REP(i, N) {
        cin >> a[i];
        a[i]--;
        b[a[i]] = i;
    }
    int dp[N_MAX];
    dp[N - 1] = 1;
    int lon_inc_con_seq = 1;
    RREP(i, N - 1) {
        if (a[i] != N - 1 && i < b[a[i] + 1]) {
            dp[i] = dp[b[a[i] + 1]] + 1;
            amax(lon_inc_con_seq, dp[i]);
        } else {
            dp[i] = 1;
        }
    }
    cout << N - lon_inc_con_seq << endl;
    return 0;
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
	int n=in(),m=in(),x=in(),a,b=0,c=0,i;
	rep(i,m){
		a=in();
		if(a<x)b++;
		else c++;
	}
	print(min(b,c));
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define vul vector<ull>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi2d vector<vi >
#define vl2d vector<vl >
#define vpll vector<pll >

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rz resize
#define fr(i,n) for(i=0;i<(n);i++)
#define frr(i,n) for(i=(n-1);i>=0;i--)
#define fre(i,n) for(i=0;i<=(n);i++)
#define frre(i,n) for (i=(n);i>=0;i--)
#define frab(i,a,b) for(i=(a);i<(b);i++)
#define freab(i,a,b) for(i=(a);i<=(b);i++)
#define frrab(i,a,b) for(i=(b-1);i>=a;i--)
#define frreab(i,a,b) for(i=(b);i>=a;i--)

#define sz(a) int((a).size())
#define mset(a,b) (memset(a,b,sizeof(a)))
#define max3(a,b,c) (max((a),max((b),(c))))
#define min3(a,b,c) (min((c),min((a),(b))))
#define sumv(v) accumulate(all(v),ll(0))
#define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector <ll> sprime;
vector<char> prime (1000000, true);
void sieve(ll n)
{
  //O(nloglogn) time
  sprime.pb(0);
  prime[0] = prime[1] = false;
  ll cnt = 0;
  for (ll i = 2; i <= n; ++i)
  {
    if (prime[i])
    {
      cnt++;
      sprime.pb(i);
      for (ll j = 2 * i; j <= n; j += i)
        prime[j] = false;
    }
  }
}
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll fastpowMOD(ll a, ll p, ll MOD) { if (p == 0) return 1; ll z = fastpowMOD(a, p / 2, MOD); z = (z * z) % MOD; if (p % 2) z = (z * a) % MOD; return z; }
ll fastpow(ll a, ll p) { if (p == 0) return 1; ll z = fastpow(a, p / 2); z = (z * z); if (p % 2) z = (z * a); return z; }

#define mod 1000000007
#define inf LLONG_MAX
#define minf LLONG_MIN
#define pi 3.14
#define ex 2.71

//*********************************************///
const int N = 1e5 + 5;
int i,j;
int n,wt;
vector<int>G[N];
stack<int>s;
bool vis[N];
int dp[N];


void dfs(int u)
{
  for(auto it:G[u])
    if(!vis[it])
    {
      vis[it]=1;
      dfs(it);
    }
  s.push(u);
}

void solve()
{
  int n,m;
  cin>>n>>m;
  freab(i,1,m)
  {
    int x,y;
    cin>>x>>y;
    G[x].pb(y);
  }
  mset(vis,0);
  freab(i,1,n)
    if(!vis[i])
    {
        vis[i]=1;
        dfs(i);
    }
  vector<int>v;
  while(!s.empty())
    v.pb(s.top()),s.pop();
  for(auto it:v)
  {
    for(auto jt:G[it])
      dp[jt]=max(dp[jt],dp[it]+1);
  }
  int mx=-1;
  freab(i,1,n)
    mx=max(dp[i],mx);
  cout<<mx<<endl;


}

int main()
{
  fast;
  int z;
  //cin>>z;
  z=1;
  while(z--)
  {
    solve();
  }
  return 0;
}


Measured memory_bytes: 10028
#include<stdio.h>
int main(void){
  int a[10000],b[500],count=0;
  int i,j,n,k;
  scanf("%d",&n);
   for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d",&b[i]);
  }
  for(j=0;j<k;j++){
    for(i=0;i<n;i++){
      if(a[i]==b[j]){
    count++;
    break;
      }
    }
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 640
#![allow(unused)]

use std::cmp::{max, min};
use std::io::stdin;
use std::str::FromStr;

fn input<T: FromStr>() -> Result<T, T::Err> {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim().parse()
}

fn input_vec<T: FromStr>() -> Result<Vec<T>, T::Err> {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim().split_whitespace().map(|x| x.parse()).collect()
}

use std::collections::HashMap;

fn main() {
    let (n, k): (usize, usize) = {
        let v = input_vec().unwrap();
        (v[0], v[1])
    };

    let ab: Vec<(usize, usize)> = {
        let mut res = Vec::new();
        for i in 0..n {
            let v = input_vec().unwrap();
            res.push((v[0], v[1]));
        }
        res
    };

    // set[i]はiを挿入する数
    let mut set: HashMap<usize, usize> = HashMap::new();

    for (a, b) in ab {
        let h = set.entry(a).or_insert(0);
        *h += b;
    }

    // println!("{:?}", set);
    let mut v = set.iter().collect::<Vec<_>>();
    v.sort();
    let mut accu = 0usize;
    for (a, b) in v {
        if accu + b >= k {
            println!("{}", a);
            break;
        } else {
            accu += *b;
        }
    }
}


Measured memory_bytes: 14240
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

const int NMAX = 1e3 + 3;
lli ar[NMAX][3];
int n, m;

int main(){
	ios_base::sync_with_stdio(false);
		
	cin >> n >> m;
	for(int i=0 ;i<n; i++){
		for(int j=0; j<3; j++)
			cin >> ar[i][j];
	}

	lli res = 0;

	for(int mask=0; mask<(1<<3); mask++){
		vector <lli> loc_res;
		for(int i=0; i<n; i++){
			lli loc_sum = 0;
			for(int j=0; j<3; j++){
				if(mask & (1 << j)) loc_sum += ar[i][j];
				else loc_sum -= ar[i][j];
			}
			loc_res.pb(loc_sum);
		}

		lli local_res = 0;
		sort(ALL(loc_res), greater<lli>());
		for(int i=0; i<m; i++) local_res += loc_res[i];
		res = max(res, local_res);
	}

	cout << res;

	return 0;
}

Measured memory_bytes: 256
pub fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn readn<T: std::str::FromStr>(delimiter: &str) -> Vec<T> {
    let s = read1::<String>();
    s.split(delimiter).map(|e| e.parse().ok().unwrap()).collect::<Vec<T>>()
}

fn dfs(i: usize, c: usize, ans: &mut Vec<usize>, edge: &Vec<Vec<(usize, usize)>>) {
    for e in edge[i].iter() {
        let j = e.0;
        let w = e.1;
        if ans[j] == 2 {
            if w % 2 == 0 {
                ans[j] = c;
                dfs(j, c, ans, edge);
            } else {
                ans[j] = c ^ 1;
                dfs(j , c ^ 1, ans, edge);
            }
        }
    }
}

fn main() {
    let n = read1::<usize>();
    let mut edge = vec![Vec::new(); n];
    let mut ans = vec![2; n];

    for _ in 0..n-1 {
        let uvw = readn::<usize>(" ");
        let u = uvw[0] - 1;
        let v = uvw[1] - 1;
        let w = uvw[2];

        edge[u].push((v, w));
        edge[v].push((u, w));
    }

    ans[0] = 0;
    dfs(0, 0, &mut ans, &edge);

    for c in ans.iter() {
        println!("{}", c);
    }
}

Measured memory_bytes: 17788
#include <stdio.h>
int main()
{
	int N,K,X,Y;
	scanf("%d%d%d%d",&N,&K,&X,&Y);
	if(N<=K) printf("%d",N*X);
	else if(N>K) printf("%d",K*X+(N-K)*Y);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int p[101]={0},t[101];
int main(){
int n,a,b,i,j,c,l,g;
cin>>n>>a>>b>>c;
p[0]=c/a;
for(i=1;i<=n;i++)
{
cin>>t[i];
}
for(i=1;i<=n;i++){
	for(j=i+1;j<=n;j++){
		if(t[i]<t[j]){
			g=t[i];
			t[i]=t[j];
			t[j]=g;
		}
	}
}
g=0;
for(i=1;i<=n;i++){
g+=t[i];
	p[i]=max(p[i-1],(c+g)/(a+b*i));
}
cout<<p[n]<<endl;
return 0;
}

Measured memory_bytes: 3056
#include <stdio.h>

int isPrime(int n);
//int n_prime(int from, int to);
int n_prime(int n);

int main(void){

  int n, p_n, p_2n;

  while(1){
    scanf("%d",&n);
    if(n==0) break;
    /*
    p_n = n_prime(1,n);
    p_2n = n_prime(n+1,2*n) + p_n;
    printf("%d\n",p_2n-p_n);
    */
    printf("%d\n",n_prime(2*n)-n_prime(n));
  }
  return 0;

}

int isPrime(int n){

  int i, len;

  if(n==1 || n==2) return 1;
  if(n%2==0) return 0;
  for(i=3,len=sqrt(n); i<=len; i+=2){
    if(n%i==0) return 0;
  }
  return 1;

}

/*
int n_prime(int from, int to){

  int i, count = 0;

  for(i=from; i<=to; i++){
    if(isPrime(i)) count++;
  }

  return count;

}
*/

int n_prime(int n){

  int i, count = 0;

  for(i=1; i<=n; i++){
    if(isPrime(i)) count++;
  }

  return count;

}

Measured memory_bytes: 408
use rand::{Rng, SeedableRng};
use rand::rngs::SmallRng;
use proconio::input;

#[proconio::fastout]
fn main() {
    input! {
        d: i32,
        c: [i32; 26],
        s: [[i32; 26]; d],
    }
    let mut greedy_result = greedy(d, &c, &s);
    // local_search(d, &c, &s, &mut greedy_result.contests);
    let s: String = greedy_result.contests.iter()
                    .map(|x| (x+1).to_string())
                    .collect::<Vec<String>>()
                    .join("\n");
    println!("{}", s);
}

struct BestResult {
    satification: i32,
    contests: Vec<usize>
}

fn greedy(d: i32, c: &Vec<i32>, s: &Vec<Vec<i32>>) -> BestResult {
    let mut satification = 0;
    let mut last: Vec<i32> = vec![0; 26];
    let mut contests: Vec<usize> = vec![0; d as usize];
    for i in 1..d+1 {
        let mut best_contest: usize = 1;
        let mut best_satification = -1_000_000_000;
        for t in 0..26 {
            let pre_last = last[t];
            last[t] = i;
            last[t as usize] = i as i32;
            let tmp_satification = {
                satification
                + s[(i-1) as usize][t as usize]
                - last.iter().zip(c).map(|(l, c)| c*(i as i32 - l)).sum::<i32>()
            };
            last[t] = pre_last;
            if best_satification < tmp_satification {
                best_contest = t;
                best_satification = tmp_satification;
            }
        }
        satification = best_satification;
        last[best_contest] = i;
        contests[(i-1) as usize] = best_contest;
        // println!("{}", best_contest+1);
    }
    BestResult{
        satification,
        contests
    }
}

fn local_search(d: i32, c: &Vec<i32>, s: &Vec<Vec<i32>>, contests: &mut Vec<usize>) {
    let mut rng = SmallRng::from_entropy();
    let day = rng.gen_range(0, d) as usize;
    let changed_contest = rng.gen_range(0, 26);
    let mut change = s[day][contests[day]];
    // 変更する操作を無かったことにするための差分
    change += match contests[day..d as usize]
                    .iter()
                    .position(|x| *x == contests[day]) {
        Some(x) => - c[contests[day-1]]*(x - day) as i32,
        None => match contests[..day-1 as usize]
                      .iter().rev()
                      .position(|x| *x == contests[day-1]) {
            Some(x) => c[contests[day-1]]*(day - x) as i32,
            None => c[changed_contest] * day as i32
            }
    };
    // 変更後の差分
    change+= s[day-1][changed_contest];
    change -= match contests[day..d as usize]
                    .iter()
                    .position(|x| *x == changed_contest) {
        Some(x) => c[changed_contest]*(x - day) as i32,
        None => 0
    };
    change -= match contests[..day-1 as usize]
                    .iter().rev()
                    .position(|x| *x == contests[day-1]) {
        Some(x) => c[changed_contest]*(day - x) as i32,
        None => c[changed_contest] * day as i32
    };

    if change > 0 {
        contests[day-1] = changed_contest;
    }

}

Measured memory_bytes: 2240
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int r;
    cin >> r;
    cout << 3*r*r << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define _C ios::sync_with_stdio(false);cin.tie(0);
#define xx first
#define yy second
#define ERR 0.00000001
#define INF (ll)1<<62
#define nSize 1000000
#define forn for(int i = 0 ; i < n ; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef complex<double> cp;
typedef vector<cp> polinomio;
typedef long double ld;
const ld PI = acos(-1);


int main()
{_C
	ll n , k;
	ll mx = INF;
	cin >> n >> k;
	vll v(n);
	forn
		cin >> v[i];
	sort(v.begin(),v.end());
	for(int i = k-1 ; i < n ; i++)
	{
		mx = min(v[i]-v[i-k+1],mx);
	}
	cout << mx << '\n';
	#ifdef LOCAL
	//	cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}

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

using namespace std;

int main(void) {
  int h, w;
  cin >> h >> w;

  vector<string> s(h);
  for (int i = 0; i < h; i++) {
    cin >> s[i];
  }

  int a[51][51] = {};
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      for (int k = -1; k <= 1; k++) {
        for (int l = -1; l <= 1; l++) {
          if (k == 0 && l == 0) continue;
          int ni = i + k, nj = j + l;
          if (ni >= 0 && ni < h && nj >= 0 && nj < w) {
            a[i][j] += s[ni][nj] == '#';
          }
        }
      }
      if (s[i][j] == '#') {
        cout << s[i][j];
      } else {
        cout << a[i][j];
      }
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
char a[MAXN];
vector<int> topx[50];
bool del[MAXN];
int las[50],n,sum;
long long ans,tree[MAXN];
void change(int x,int adx){
	while(x<=n){
		tree[x]+=adx;
		x+=x&(x^(x-1));
	}
}
long long query(int x){
	long long res=0;
	while(x){
		res+=tree[x];
		x-=x&(x^(x-1));
	}
	return res;
} 
int main(){
	SF("%s",a);
	n=strlen(a);
	for(int i=0;i<n;i++){
		topx[a[i]-'a'].push_back(i);
	}
	for(int i=0;i<=30;i++)
		las[i]=topx[i].size()-1;
	for(int i=0;i<=30;i++)
		if(topx[i].size()%2==1)
			sum++;
	if(sum>1){
		PF("-1");
		return 0;	
	}
	for(int i=1;i<=n;i++)
		change(i,1);
	for(int i=0;i<n;i++)
		if(del[i]==0){
			int x=a[i]-'a';
			int y=topx[x][las[x]];
			int u=i+1;
			int v=y+1;
			del[i]=1;
			del[y]=1;
			if(u==v){
				ans+=(query(n)-query(u))/2;
			}
			else{
				ans+=query(n)-query(v);
			}
			change(u,-1);
			change(v,-1);
			las[x]--;
		}
	PF("%lld",ans);
} 

Measured memory_bytes: 3192
N = list(map(int, input().split()))
x = [input() for i in range(N[0])]
xi=[]
cnt=0

for i in x:
    
    xi.append([])
    for j in i:

        if j=='.':
            xi[cnt].append(0)
        else:
            xi[cnt].append(1)
    cnt+=1


for i in range(N[0]):
    for j in range(N[1]):
        if xi[i][j]==0:
            continue
        if i!=0 and j!=0 and i!=N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i-1][j]+xi[i][j+1]+xi[i][j-1]
        if i==0 and j!=0 and i!=N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i][j+1]+xi[i][j-1]
        if i!=0 and j!=0 and i==N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i-1][j]+xi[i][j+1]+xi[i][j-1]      
        if i!=0 and j==0 and i!=N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i-1][j]+xi[i][j+1]
        if i!=0 and j!=0 and i!=N[0]-1 and j==N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i-1][j]+xi[i][j-1]

        if i==0 and j==0 and i!=N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i][j+1]
        if i!=0 and j==0 and i==N[0]-1 and j!=N[1]-1 :
            xi[i][j]+=xi[i-1][j]+xi[i][j+1]
        if i==0 and j!=0 and i!=N[0]-1 and j==N[1]-1 :
            xi[i][j]+=xi[i+1][j]+xi[i][j-1]
        if i!=0 and j!=0 and i==N[0]-1 and j==N[1]-1 :
            xi[i][j]+=xi[i-1][j]+xi[i][j-1]


for i in range(N[0]):
    for j in range(N[1]):
        if xi[i][j]==1:
            print('No')
            quit()

print('Yes')



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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef unordered_set<int> si;
typedef pair<int, int> pp;
typedef vector<pp> vpp;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define all(e) (e).begin(), (e).end()
#define pb push_back


template <typename T>
void printV(vector<T> A) {
    if (A.empty()) cerr << "EMTPY\n";
    else { 
        cerr << "[";
        for (int i = 0; i < A.size() -1 ; ++i) {
            cerr << A[i] << ", ";
        }
        if (A.size()) cerr << A.back() << "]\n";
    }
}


template <typename T>
void printVV(vector<vector<T>> A) {
    cerr << "[";
    for (auto v : A) {
        printV<T>(v);
    }
    cerr << "]";
}

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&& ...args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long x; cin >> x;
    for (int i = 0; i <= 6000; ++i) {
        for (int j = 0; j <= 6000; ++j) {
            ll val = 1LL*i*i*i*i*i;
            ll val1 = 1LL*j*j*j*j*j;
            if (val - val1 == x) {
                cout << i << ' ' << j << endl;
                return 0;
            }
            
            if (val + val1 == x) {
                cout << i << ' ' << -j << endl;
                return 0;
            }

            if (val1 - val == x) {
                cout << j << ' ' << i << endl;
                return 0;
            }
            
        }
    }
    return 0;
}



Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 
bool ch[100010];
ll ans[100010];
int main() {
	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		now--;
		ch[now]=true;
	}
	if(ch[0]!=true){
		ans[0]=1;
	}
	if(ch[1]!=true){
		ans[1]=1+ans[0];
	}
	for(ll i=2;i<n;i++){
		if(ch[i]!=true){
			ans[i]=ans[i-1]+ans[i-2];
			ans[i]%=inf;
		}
	}
	cout <<ans[n-1];
	// your code goes here
	return 0;
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) 
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)
#define YES(cond) cond ? OUT("YES") : OUT("NO")
#define Yes(cond) cond ? OUT("Yes") : OUT("No")

template<class T> T gcd(const T x,const T y){if(!y){return x;}return gcd(y,x%y);}
template<class T> T lcm(const T x,const T y){return x/gcd(x,y)*y;};
template<class T> T modpow(T x,T n,const T mod) {
  T res=1;while(n>0){if(n%2)res=res*x%mod;x=x*x%mod;n/=2;};return res;
}
template<class T> T modinv(T x,const T mod){return modpow(x,mod-2,mod);}
template<class T> bool alltrue(const T &a){return all_of(ALL(a),[](bool x){return x;});}
template<class T> bool anytrue(const T &a){return any_of(ALL(a),[](bool x){return x;});}
template<class T> bool contain(const T &a,const T &b){for(auto x:b){if (a.find(x)==a.end()){return false;}}return true;}
template<class T> bool mmax(T &m,const T q){ if (m < q) {m = q; return true;} else return false; }
template<class T> bool mmin(T &m,const T q){ if (m > q) {m = q; return true;} else return false; }
template<class T> int siz(const T &a) {return (int)a.size();}
template<class T> set<T> devisers(T n) {
  set<T> res;for(T i=1;i<(T)sqrt(n)+1;i++){if(n%i==0){res.insert(i);res.insert(n/i);}}return res;
}
template<class T> void concat(T &a, const T &b){a.insert(a.end(),b.begin(),b.end());}
template<class T> void getand(const T &a,const T &b,T &c) {
  set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> void getor(const T &a,const T &b,T &c) {
  set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> void getdiff(const T &a,const T &b,T &c) {
  set_difference(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> T deg2rad(T deg) {return deg*2*M_PI/360;}
template<class T> T rad2deg(T rad) {return rad*360/(2*M_PI);}

typedef long long ll;
typedef pair<ll, ll> P;

const ll MOD=1e9+7;
const ll MAX=5e6;

vector<ll> Zalgo(const string &s) {
  ll N=siz(s);
  vector<ll> z(N,0);
  z[0]=N;
  ll i=1,j=0;
  while (i<N) {
    while (i+j<N && s[j]==s[i+j]) j++;
    z[i]=j;
    if (j==0) { i++;continue; }
    ll k=1;
    while (i+k<N && z[k]+k<j) {
      z[i+k]=z[k];
      k++;
    }
    i+=k;j-=k;
  }
  return z;
}

int main() {
  int N;cin>>N;
  string S;cin>>S;
  vector<vector<ll>> z(N-1);
  REP(i,N-1) {
    z[i] = Zalgo(S.substr(i));
  }

  ll ans = 0;
  REP(i,N-1) {
    FOR(j,1,siz(z[i])) {
      mmax(ans,min(j,z[i][j]));
    }
  }
  OUT(ans);

  return 0;
}

Measured memory_bytes: 98048
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
#include <iomanip>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 2;
const int MOD = 1000000007;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
	int N;
	cin >> N;
	vi A(N);
	REP(i, N) {
		cin >> A[i];
	}

	sort(ALL(A));
	if (N % 2) {
		if (A[0] != 0) {
			cout << 0 << endl;
			return 0;
		}
		FOR(i, 1, N / 2) {
			REP(j, 2) {
				if (A[2*i+j-1] != 2*i) {
					cout << 0 << endl;
					return 0;
				}
			}
		}
	}
	else {
		FOR(i, 0, N/2-1) {
			REP(j, 2) {
				if (A[2*i+j] != 2*i+1) {
					cout << 0 << endl;
					return 0;
				}
			}
		}
	}

	int ans = 1;
	REP(i, N / 2) {
		ans = (ans * 2) % MOD;
	}

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

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

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}

int main(int, char**)
{
	ll D, G;
	cin >> D >> G;
	vector<ll> p(D), c(D);
	for (ll i = 0; i < D; ++i)
	{
		cin >> p[i] >> c[i];
	}
	ll min_count = LONG_LONG_MAX;
	for (ll i = 0; i < (1ll << D); ++i)
	{
		ll score = 0;
		ll count = 0;
		for (ll j = 0; j < D; ++j)
		{
			if ((i & (1ll << j)) != 0)
			{
				score += 100ll * (j + 1) * p[j];
				score += c[j];
				count += p[j];
			}
		}
		if (G <= score)
		{
			min_count = min(min_count, count);
			continue;
		}
		bool found = false;
		for (ll j = D - 1; j >= 0 && !found; --j)
		{
			if ((i & (1ll << j)) == 0)
			{
				for (ll k = 0; k < p[j]; ++k)
				{
					score += 100ll * (j + 1);
					++count;
					if (G <= score)
					{
						min_count = min(min_count, count);
						found = true;
						break;
					}
				}
			}
		}
	}
	cout << min_count << endl;
	return 0;
}


Measured memory_bytes: 256
yen = list(map(int,input().split()))
N = int(input())
lista = [4*yen[0], 2*yen[1], yen[2]]

yen1 = min(lista)
if 2*yen1 <= yen[3]:
    print(N*yen1)
else:
    if N%2 == 0:
        print(int((N//2)*yen[3]))
    else:
        print(int( (N//2)*yen[3] + yen1))


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

#define fr(i,b,e) for(int i=(b); i!=(e); ++i)
#define rep(i,e) for(int i=0; i!=(e); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long int li;
typedef long long int ll;
using graph = vector<vector<int>>;
using edgedp = vector<vector<pair<int,ll>>>;
constexpr int INF=1000000;
//constexpr int MOD=998244353;
constexpr int MOD=1e9+7;

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

    ll n,d;
    cin >> n >>d;
    ll x,y;
    ll cnt=0;
    fr(i,0,n){
        cin >> x >> y;
        if((x*x+y*y)>d*d){
        }else{
            ++cnt;
        }
    }
    cout << cnt << "\n";
}   

Measured memory_bytes: 3652