akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node find(Node u,int k){
  while(u!=NIL && k!=u->key){
    if(k<u->key) u=u->left;
    else u=u->right;
  }
  return u;
}

Node treeMinimum(Node x){

  while(x->left!=NIL){
    x=x->left;
  }
  return x;

}

Node treeMaximum(Node x){

  while(x->right!=NIL){
    x=x->right;
  }
  return x;

}

Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
  if(k<u->key){
    return treeSearch(u->left,k);
  }
  else return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL)
    return treeSuccessor(x->right);
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right==NIL)
    y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent=y->parent;
  if(y->parent==NIL) root=x;
  else if(y==y->parent->left) y->parent->left=x;
  else y->parent->right=x;

  if(y!=z) z->key=y->key;
  free(y);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }else{
      x=x->right;
    }
  }

  z->parent=y;
  if(y==NIL){
    root=z;
  }else{
    if(z->key<y->key){
      y->left=z;
    }else{
      y->right=z;
    }
  }


}

void inorder(Node u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

 
  return 0;
}



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

int main(){
  int a[4];
  int b[4];
  while(cin>>a[0]){
    for(int i=1;i<4;i++){
      cin>>a[i];
    }
    for(int j=0;j<4;j++){
      cin>>b[j];
    }
    int hit=0,blow=0;
    for(int i=0;i<4;i++){
      if(a[i]==b[i])hit++;
    }
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
	if(i!=j){
	  if(a[i]==b[j]){
	    blow++;
	  }
	}
      }
    }
    cout<<hit<<" "<<blow<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define  FasterIO    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  bug(a,b)    cout<<a<<"\t"<<b<<"\n";
#define  endl        "\n";
#define  pi          2*acos(0.0)
#define  inf         LONG_MAX
#define  size        1e5

int main(){
    FasterIO;
    //testCase
    int a,b;        cin>>a>>b;
    cout<<(a*b)<<endl;
    return 0;
}



Measured memory_bytes: 3624
#include<stdio.h>

main(){
  int i,j,A[100],N,count=0,swap;

  scanf("%d",&N);
  for(i=0 ; i<N ; i++)   scanf("%d",&A[i]);
  
  for(i=0 ; i<N-1 ; i++){
    for(j=N-1 ; j>i ; j--){
      if(A[j] < A[j-1]){
	swap = A[j];
	A[j] = A[j-1];
	A[j-1] = swap;
	count++;
      }
    }
  }
  
  for(i=0 ; i<N ; i++){
    printf("%d",A[i]);
    if(i<N-1) printf(" ");
  }
  printf("\n%d\n",count);
  
  return 0;
}

Measured memory_bytes: 604
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 2 * 10 ** 6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = comb(H + W - 2, H - 1)
for x in range(H - A, H):
    ans -= comb(x + B - 1, B - 1) * comb(H - 2 - x + W - B, W - B - 1)
    ans %= mod
print(ans)


Measured memory_bytes: 182836
#include <bits/stdc++.h>
//https://qiita.com/ysuzuki19/items/d89057d65284ba1a16ac
#define debug(var)                  \
    do {                            \
        std::cout << #var << " : "; \
        view(var);                  \
    } while (0)
template <typename T>
void view(T e) { std::cout << e << std::endl; }

template <typename T>
void view(const std::vector<T>& v) {
    for (const auto& e : v) {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}

template <typename T>
void view(const std::vector<std::vector<T>>& vv) {
    for (const auto& v : vv) {
        view(v);
    }
}

using namespace std;
//yosupo
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

int main() {
    int N;
    cin >> N;
    V<int> A(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    long long ans = 1000;
    for (int i = 0; i < N - 1; ++i) {
        if (A[i] < A[i + 1]) {
            ans = ans / A[i] * A[i + 1] + ans % A[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for(long long (i)=0;(i)<(n);(i)++)
#define ll long long
#define pr_qu priority_queue
#define vec(name,size,common) vector<ll> (name)((size),(common))
 
 
 
 
 
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  a = a*b;
  c = c*d;
  if(a>=c){
    cout<<a;
  }else{
    cout<<c;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[107][17];
int main()
{
    //freopen("a.in","r",stdin);
    int n;
    cin>>n;
    cin>>a[1];
    for(int i=2;i<=n;++i)
    {
        cin>>a[i];
        if(a[i-1][strlen(a[i-1])-1]!=a[i][0]){cout<<"No";return 0;}
        for(int j=1;j<i;++j)
        if(strcmp(a[i],a[j])==0){cout<<"No";return 0;}
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [AB[i][0] for i in range(n)]
B = [AB[i][1] for i in range(n)]
# A = [(AB[i][0], i) for i in range(n)]
# B = [(AB[i][1], i) for i in range(n)]

A.sort()
B.sort()

if n % 2 == 1:
    print(B[n // 2] - A[n // 2] + 1)


if n % 2 == 0:
    # x = abs(A[n // 2 - 1] + B[n // 2])
    # y = abs(A[n // 2] + B[n // 2 - 1])
    # print(x, y)
    # print(abs(x - y) + 1)

    # print(x, y)
    a = A[n // 2] + A[n // 2 - 1]
    b = B[n // 2] + B[n // 2 - 1]
    print(b - a + 1)
    # print(a, b)
    # print(B[n // 2] - A[n // 2 - 1] + 1)


Measured memory_bytes: 39572
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    readint;
    auto a = readints;
    auto b = readints;
    auto c = readints;

    int ans = 0;
    for (int i = 0; i < a.length; i++) {
        ans += b[a[i] - 1];

        if (i + 1 < a.length) {
            int x = a[i]; // 食べた料理
            int y = a[i + 1]; // 次に食べる料理
            if (y == x + 1) {
                ans += c[a[i] - 1];
            }
        }
    }
    writeln(ans);
}


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

int main() {
  int N, K;
  int c = 1;
  cin >> N >> K;
  for(int i;i < N;i++){
  	if(K < c){
  		c += K;
  	}
  	else{
  		c *= 2;
  	}
  }
  cout << c << endl;
}

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

int gra[101][101];
int dis[101];
int used[101];
int tt[101][2];
int n, a, b, c;



int main(){
	cin>>n;
	int minp, point,minv;
	for(int i=0; i<n; i++){
 		for(int j=1; j<=n; j++){
 			gra[i][j] = 99999;
		}
 	}
 	for(int i=0; i<n; i++){
 		cin>>a>>b;
		for(int j=1; j<=b; j++){
  			cin>>c;
 			gra[a][c]=1;
 		}
 	}
 	point = 1, gra[1][1] = 0;
 	for(int i=1; i<=n; i++){
 		dis[i] = gra[1][i];
	}
	for(int i=0; i<n-1; i++){
		used[point] = 1;
		minv = 99999;
		for(int j=1; j<=n; j++){
			if(gra[point][j]==1 && used[j]==0 && dis[point]+1<dis[j]){
				dis[j] = dis[point] + 1;
			}
			if(dis[j]<minv && dis[j]!=99999 && used[j]==0){
				minv = dis[j], minp = j;
			}			
		}
		point = minp;		
	}
 	cout<<"1 "<<dis[1]<<"\n"; 	
 	for(int i=2; i<=n; i++){
 		cout<<i<<" ";
 		if(dis[i]==99999)cout<<"-1\n";
		else cout<<dis[i]<<"\n";
	}
 
 return 0;
}


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

int main()
{
    string s;
    cin >> s;
    int ans = 0;
    int nowpoint = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
        {
            ans++;
            nowpoint = max(ans, nowpoint);
        }
        else
        {
            ans = 0;
        }
    }
    cout << nowpoint << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <functional>
#include <math.h> 
#define enld '\n'
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
// constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
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(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N,K;
  cin >> N >> K;
  vector<vector<int>> G(10);
  for(int i=0; i<N; i++){
    int x,id;
    cin >> x >> id;
    id--;
    G[id].emplace_back(x);
  }
  for(int i=0; i<10; i++){
    sort(G[i].rbegin(),G[i].rend());
    for(int j=1; j<G[i].size(); j++){
      G[i][j] += G[i][j-1];
    }
    for(int j=0; j<G[i].size(); j++){
      G[i][j] += j*(j+1);
    }
  }
  vector<int> dp(K+1,0);
  for(int i=0; i<10; i++){
    vector<int> ndp = dp;
    for(int j=0; j<K; j++){
      for(int k=0; k<G[i].size(); k++){
        if(j+k+1 > K) break;
        chmax(ndp[j+k+1],dp[j]+G[i][k]);
      }
    }
    dp = ndp;
  }
  cout << dp[K] << "\n";
  return 0;
}


Measured memory_bytes: 3228
#include<stdio.h>

int isPrime(int a){int i;for(i=2; i*i<=a; i++) if(a%i==0) return 0; return (a>1?1:0);}

int main(){
  int n, i, ans=0;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    int num;
    scanf("%d",&num);
    ans += isPrime(num);
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 2048
N = int(input())
A = list(map(int, input().split()))
cnt = 1
ans = 0
for i in range(N):
  if(A[i] < 0):
    cnt = cnt * (-1)
  elif(A[i] == 0):
    cnt = cnt * 0
if(cnt >= 0):
  for i in range(N):
    ans += abs(A[i])
else:
  for i in range(N):
    A[i] = abs(A[i])
  A.sort()
  for i in range(N):
    ans += A[i]
  ans -= A[0] * 2
print(ans)


Measured memory_bytes: 14468
#include <iostream>
#include <algorithm>

#define Nmax int(1e5 + 1)
using namespace std;

typedef long long ll;
struct can {
    ll quantity,price;
} a[Nmax];

ll N,M,i;
ll S,cnt;

inline bool cmp(can a, can b) {
    return ((a.price < b.price) ? true : false);
}

int main() {
    
    cin >> N >> M;
    for(i = 1; i <= N; ++i)
        cin >> a[i].price>> a[i].quantity;
    sort(a + 1, a + N + 1,cmp);
    for(i = 1; i <= N && M > 0; ++i) {
        cnt = min(M,a[i].quantity);
        S += cnt * a[i].price;
        M -= cnt;
    }
    cout << S;
    return 0;
}


Measured memory_bytes: 1792
X, K, D = map(int, input().split())
x = abs(X)
if X == 0:
    cnt = K
    if cnt % 2 == 0:
        ans = 0
    else:
        ans = D
elif x >= D:
    cnt = K - x//D
    if x- K*D >= 0:
        ans = x - K*D
    elif x - K*D < 0 and cnt % 2 == 0:
        ans = abs(x%D)
    else:
        ans = abs(D - x%D)
elif x < D:
    cnt = K
    if cnt % 2 == 0:
        ans = abs(x)
    else:
        ans = abs(x-D)

print(ans)

Measured memory_bytes: 61684
//Even better better solutions q{^.^}p

#define ONLINE_JUDGE //in case i forget to uncomment this, sometimes the grader defines the macro ^.^
#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>
#else
#include "stdc++.h"
#endif

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("/Users/kdkdk/Desktop/input.txt", "r", stdin);
    //freopen("/Users/kdkdk/Desktop/output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    
    
    vector<int> x(n),y(n),h(n);
    vector<pair<int,pair<int,int>> > hxy(n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> h[i];
        hxy[i] = {h[i],{x[i],y[i]}};
    }
    
    sort(hxy.begin(), hxy.end());
    reverse(hxy.begin(),hxy.end());
    
    for(int i = 0; i < n; ++i) {
        h[i] = hxy[i].first;
        x[i] = hxy[i].second.first;
        y[i] = hxy[i].second.second;
    }
    
    
    //max(H−|X−CX|−|Y−CY|,0)
    //H <= |X−CX|−|Y−CY|
    
    vector<vector<int> > height (101,vector<int>(101,0));
    for(int cx = 0; cx <= 100; ++cx) {
        for(int cy = 0; cy <= 100; ++cy) {
            for(int i=0;i<n;++i) {
                if(h[i] != 0 && height[cx][cy] == 0) height[cx][cy] = h[i] + abs(x[i]-cx) + abs(y[i]-cy);
                else if(h[i] != 0 && height[cx][cy] != (h[i] + abs(x[i]-cx) + abs(y[i]-cy))) height[cx][cy] = -1;
                else if(h[i] == 0 && height[cx][cy] > 0 && height[cx][cy] > (abs(x[i]-cx) + abs(y[i]-cy))) height[cx][cy] = -1;
            }
        }
    }
    
    for(int cx = 0; cx <= 100; ++cx) {
        for(int cy = 0; cy <= 100; ++cy) {
            if(height[cx][cy] > 0) {
                cout << cx << " " << cy << " " << height[cx][cy] << endl; return 0;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool f[1000006];
int x;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	f[1]=1;
  	for (int i=2; i<=1e6; i++)
  		if (!f[i]) 
  			for (int j=2*i; j<=1e6; j+=i)
  				f[j]=1;
  	
  	cin>>x;
  	
  	while (f[x]) {
  		x++;
  	}
  	
  	cout<<x<<endl;
  	
  		
  	
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i =a; i < (b);++i)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
main(){
    ll n, k;
    cin >> n >> k;
    ll a[n+1], dp[n+1][k+1], dp_pre[n+1][k+2], pre[n+1];
    memset(dp, 0, sizeof dp);
    memset(dp_pre, 0, sizeof dp_pre);
    pre[0] = 0;
    rep(i, 0, n) cin >> a[i + 1];
    //sort(a + 1, a + n + 1);
    rep(i ,0 ,n)  pre[i+1] = pre[i] + a[i+1];
    rep(i, 0 ,n+1) dp[i][0] = 1, dp_pre[i][1] = 1;
    rep(i, 0, min(pre[1], k) + 1) dp[1][i] = 1;
    rep(i, 1, k + 1) dp_pre[1][i+1] = (dp_pre[1][i] + dp[1][i]) % mod;
    rep(i, 2, n+1){
        rep(j, 1, min(pre[i], k) + 1){
            ll dj =  min((ll)j, pre[i-1]);
            dp[i][j] = ((dp_pre[i-1][dj+1] - dp_pre[i-1][max(0LL, j - a[i])])%mod + mod ) % mod;
            dp_pre[i][j+1] = (dp_pre[i][j] + dp[i][j])%mod;
        }
    }
    
    cout << dp[n][k] << '\n';
}

Measured memory_bytes: 158080
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = 1e18;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    string S, T;
    cin >> S >> T;
    cout << T+S << endl;
}

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

using namespace std;

int main(){

  string name;
  int p,a,b,c,d,e,f,s,m;
  int n;

  cin >> n;
  while(n){

    vector<pair<double,string> > food(n);

    for(int i=0;i<n;i++){
      cin >> name;
      cin >> p >> a >> b >> c >> d >> e >> f >> s >> m;

      double rieki = (double)(f*m*s-p)/((a+b+c)+(d+e)*m);

      food[i].first = rieki;
      food[i].second = name;      
    }

    sort(food.begin(),food.end());
    reverse(food.begin(),food.end());

    vector<string> vc;
    
    for(int i=1;i<n;i++){
      if(food[i].first==food[i-1].first){
	vc.push_back(food[i-1].second);
      }else{
	vc.push_back(food[i-1].second);
	sort(vc.begin(),vc.end());
	for(int j=0;j<vc.size();j++){
	  cout << vc[j] << endl;
	}
	vc.clear();
      }
    }
    if(food[n-1].first==food[n-2].first){
      vc.push_back(food[n-1].second);
      sort(vc.begin(),vc.end());
      for(int i=0;i<vc.size();i++)cout << vc[i] << endl;
    }else{
      sort(vc.begin(),vc.end());
      for(int i=0;i<vc.size();i++)cout << vc[i] << endl;
      cout << food[n-1].second << endl;
    }
    cout <<  "#" << endl;
    cin >> n;
  }
}




Measured memory_bytes: 3132
def dfs(s,N):
    if len(s)==10:
        if "1" in s:
            cal(s,N)
        return
    dfs(s+"0",N)
    dfs(s+"1",N)

def cal(s,N):
    p = 0
    for i in range(N):
        c=0
        for j in range(10):
            c+=F[i][j]*int(s[j])
        p+=P[i][c]
    profit.append(p)
    return

N = int(input())
F=[list(map(int,input().split())) for _ in range(N)]
P=[list(map(int,input().split())) for _ in range(N)]
profit=[]

dfs("",N)
print(max(profit))

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int dp[maxn],a[maxn];
int abs(int n)
{
	return n>=0?n:-n;
}
int main()
{
	int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    dp[1]=dp[0]=0;
    dp[2]=abs(a[2]-a[1]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]));
    }
    cout<<dp[n];
    return 0;
}

Measured memory_bytes: 4424
#include<bits/stdc++.h>
using namespace std;
bool prime[55555] = {1, 1};
int main()
{
    for (int i = 2; i < 55555; ++i){
        if (!prime[i]){
            for (int j = 2; i * j < 55555; ++j)
                prime[i * j] = 1;
        }
    }
    int n;
    scanf("%d", &n);
    for (int i = 2; n; ++i){
        if (!prime[i] && i % 5 == 1){
            printf(--n ? "%d " : "%d\n", i);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
#define INF 10000000000000000LL

class HeapSum {
  int N;
  bool isMin;
  ll sum = 0;
  priority_queue<ll, vector<ll>, greater<ll>> maxque;
  priority_queue<ll, vector<ll>> minque;
public:
  HeapSum(int N, bool isMin):N(N),isMin(isMin){}
  void push(ll v){
    sum += v;
    if(isMin){
      minque.push(v);
      while(minque.size()>N){
        ll a = minque.top(); minque.pop();
        sum -= a;
      }
    }else{
      maxque.push(v);
      while(maxque.size()>N){
        ll a = maxque.top(); maxque.pop();
        sum -= a;
      }
    }
  }
  ll getSum(){ return sum; }
};


int main(){
  int N;
  cin >> N;
  vector<ll> v(3*N);
  rep(i,3*N){
    cin >> v[i];
  }

  vector<ll> memoA(N+1,-INF), memoB(N+1,-INF);
  HeapSum hsA(N,false);
  HeapSum hsB(N,true);
  for(int i=0; i<N-1; i++){
    hsA.push(v[i]);
  }
  for(int i=N-1; i<2*N; i++){
    hsA.push(v[i]);
    memoA[i-N+1] = hsA.getSum();
  }
  for(int i=2*N; i<3*N; i++){
    hsB.push(v[i]);
  }
  for(int i=2*N-1; i>=N-1; i--){
    memoB[i-N+1] = hsB.getSum();
    hsB.push(v[i]);
  }

  ll ret = -INF;
  rep(i,memoA.size()){
    //cout << i << " " << memoA[i] << " " << memoB[i] << endl;
    ret = max(ret, memoA[i]-memoB[i]);
  }
  
  cout << ret << endl;
  
  return 0;
}



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

using namespace std;

int main(){

    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 0;
    for (int i = 1; i < n; i++){
        int cnt = 0;

        for (char c = 'a'; c <= 'z'; c++){
            bool left = false, right = false;

            for (int j = 0; j < i; j++){//左側にあるアルファベット
                if (s[j] == c){
                    left = true;
                }
            }
            for(int j = i; j < n; j++){//右側にあるアルファベット
				if(s[j] == c){
					right = true;
                }
            }
            if (left && right){//両方にあったらcntをインクリメント
                cnt++;
            }
        }
        if (ans < cnt){//最大値を取る
            ans = cnt;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 764
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
caps = [0, 0, 0]
ans = 1
for i in range(n):
    equal = []
    for j in range(3):
        if caps[j] == a[i]:
            equal.append(j)
    l = len(equal)
    if l == 0:
        ans = 0
        break
    ans = ans * l % mod
    caps[equal[0]] += 1
print(ans)

Measured memory_bytes: 52952
#include <iostream>
#include <iomanip>

using namespace std;
int main()
{
    int a,b,d,r;   
    double f;
    cin>>a>>b;
    d=a/b;
    r=a%b;
    f=(double)a/b;
    cout<<d<<" " <<r<<" "<<fixed<<setprecision(5)<<f<<endl;
}


Measured memory_bytes: 3264
# Q(A+B) gives QA blue balls, where Q = N/(A+B)
# then the left over is R = N - Q(A+B) < (A+B)
# from the left over, there are additional min(A, R) blue balls


def get_num_blue(n, a, b):
  if a == 0: return 0
  q, r = divmod(n, a+b)
  return q*a + min(a, r)


n, a, b = map(int, input().split())
print(get_num_blue(n, a, b))

Measured memory_bytes: 3060
s = int(input())

def collatz(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3 * n + 1

coll = s
i = 1
while 1:
    if coll == 1 or coll == 2 or coll == 4:
        print(i  + 3)
        break
    coll = collatz(coll)
    i += 1

Measured memory_bytes: 9084
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    if (a + b - 1 > n || n > (int64_t)a * b) {
        cout << -1 << endl;
    } else {
        vector<int> teeth(b, 0);

        teeth[0] = a;
        if (b > 1) {

            auto p = div(n - a, b - 1);
            rep(i, b - 1)
            {
                if (i < p.rem) {
                    teeth[i + 1] = p.quot + 1;
                } else {
                    teeth[i + 1] = p.quot;
                }
            }
        }

        int j = n;
        for (int l : teeth) {
            j -= l;
            rep(i, l)
            {
                cout << j + 1 + i << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 2816
import sys
def is_unique(seq):
    return len(seq) == len(set(seq))

N = int(input())
W = []
for i in range(N):
    W.append((input()))
if is_unique(W):
    for i in range(N-1):
        if W[i][-1] != W[i+1][0]:
            print("No")
            sys.exit()
    print("Yes")

else:
    print("No")



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

int main() {
  int K,N,a,b,max;
  cin >> K >> N;
  cin >> a >> b;
  max = b - a;
  if(N == 2){
    int f = a + K - b;
    if(f > max){
      max = f;
    }
  }
  if(N > 2){
  for(int i = 1; i < N - 1; i++){
    int c;
    cin >> c;
    if(c - b <= max){
      b = c;
    }
    else if(c - b > max){
      max = c - b;
      b = c;
    }
  }
  int d;
  cin >> d;
  int e = a + K - d;
  if(e > max){
    max = e;
  }  
  }
  cout << K - max << endl;    
}



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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

int main()
{
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    LL x = x2 - x1, y = y1 - y2;
    cout << x2 + y << ' ' << y2 + x << ' ' << x1 + y << ' ' << y1 + x << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define reps(i,j,k) for(int i = j; i < k;++i)
#define rep(i,j) reps(i,0,j)
int main(){
	int N,M,T;
	int stage[10010] = {};
	int sum[10010] = {};
	cin >> N >> M >> T;
	
	rep(i,N){
		int a;
		cin >> a;
		stage[a-M]++;
		stage[a+M]--;
	}
	
	reps(i,1,T+5){
		sum[i] = sum[i-1] + stage[i];
	}
	
	/*rep(i,T+1){
		cout << sum[i] << " ";
	}
	cout << endl;*/
	
	int cnt = 0;
	
	rep(i,T){
		if(sum[i] != 0){
			continue;
		}
		++cnt;
	}
	
	cout << cnt << endl;
	
	
	return 0;
}


Measured memory_bytes: 3184
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
#include <iomanip>
#include <cmath>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    
    string s, t;
    int n;
    cin >> n;
    cin >> s >> t;
    
    for(int i = 0; i < n; i++){
        cout << s[i] << t[i];
    }
    cout << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
/*
 * itikara.cpp
 *
 *  Created on: 2018/05/30
 *      Author: J01003
 */
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	int t,www[1004],p;
char ch[1004],w;
string ohn;
t=0;
while(1){
	t=0;
	cin>>ohn;
	if(ohn[0]=='0'){
		break;
	}
	for(p=0;p<ohn.size();p++){
	t+=ohn[p]-'0';
	}
	cout<<t<<endl;
}
	return 0;
}



Measured memory_bytes: 3144
n,m=map(int,input().split())
g=[[] for _ in range(n)]
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[a-1,b-1,-c] for a,b,c in abc]


# https://img.atcoder.jp/abc061/editorial.pdf
# 上のD問題
# BellmanFord
# ベルマンフォード法
# edges:エッジ、有向エッジ[a,b,c]a->bのエッジでコストc
# num_v:頂点の数
# source:始点
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和をnum_v-1回繰り返す。num_v回目に辺の緩和があればそれは閉路。-1を返す。
  for i in range(num_v-1):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1: return -1
  #閉路に含まれる頂点を探す。
  negative=[False]*n
  for i in range(num_v):
    for edge in edges:
      if negative[edge[0]]:negative[edge[1]]=True
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        negative[edge[1]] = True
  return dist[n-1],negative[n-1]
ans,nega=BellmanFord(abc,n,0)
if nega:
  print('inf')
else:
  print(-ans)


Measured memory_bytes: 75416
#include <stdio.h>
#include <stdlib.h>

typedef struct node_t {
	int key;
	struct node_t *parent;
	struct node_t *left;
	struct node_t *right;
} node;

node* newNode(int);
void print(node *);
void inorder(node *);
void preorder(node *);
void insert(int, node *);
node* find(int, node *);
void free_tree(node *);

int main(void)
{
	int i, m, k;
	char com[10];
	node *tree_root;
	
	tree_root = newNode(0);
	
	scanf("%d",&m);
	for (i=0; i<m; i++) {
		scanf("%s",com);
		if(com[0] == 'p') {
			print(tree_root->left);
		} else {
			scanf("%d",&k);
			if(com[0] == 'i') {
				insert(k, tree_root);
			} else if(com[0] == 'f') {
				if(find(k, tree_root) != NULL) {
					printf("yes\n");
				} else {
					printf("no\n");
				}
			}
		}
	}
	
	free_tree(tree_root);
	
	return 0;
}

node* newNode(int key)
{
	node *tmp;
	
	tmp = (node *)malloc(sizeof(node));
	if (tmp == NULL) exit(0);
	
	tmp->key = key;
	tmp->parent = NULL;
	tmp->left = NULL;
	tmp->right = NULL;
	
	return tmp;
}

void print(node *root)
{
	inorder(root);
	printf("\n");
	preorder(root);
	printf("\n");
}

void inorder(node *node)
{
	
	if(node->left != NULL) inorder(node->left);
	printf(" %d",node->key);
	if(node->right != NULL) inorder(node->right);
}

void preorder(node *node)
{
	printf(" %d",node->key);
	if(node->left != NULL) preorder(node->left);
	if(node->right != NULL) preorder(node->right);
}

void insert(int k, node *tree_root)
{
	node *x, *y, *z;
	
	z = newNode(k);
	y = tree_root;
	x = tree_root->left;
	while (x != NULL) {
		y = x;
		if(z->key < x->key) {
			x = x->left;
		} else {
			x = x->right;
		}
	}
	z->parent = y;
	if(y == tree_root || z->key < y->key) {
		y->left = z;
	} else {
		y->right = z;
	}
}

node* find(int k, node *tree_root) 
{
	node *x;
	
	x = tree_root->left;
	while (x->key != k) {
		if(x->key > k) {
			if(x->left == NULL) return NULL;
			x = x->left;
		} else {
			if(x->right == NULL) return NULL;
			x = x->right;
		}
	}
	return x;
}

void free_tree(node *root)
{
	if(root->left != NULL) free_tree(root->left);
	if(root->right != NULL) free_tree(root->right);
	free(root);
}

Measured memory_bytes: 19364
// AOJ ALDS1_7_C Tree Walk
// 2018.5.1 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

typedef struct { int parent; int left, right; } TREE;
TREE tree[30];

void preorder(int node)
{
	printf(" %d", node);
	if (tree[node].left  >= 0) preorder(tree[node].left);
	if (tree[node].right >= 0) preorder(tree[node].right);
}

void inorder(int node)
{
	if (tree[node].left  >= 0) inorder(tree[node].left);
	printf(" %d", node);
	if (tree[node].right >= 0) inorder(tree[node].right);
}

void postorder(int node)
{
	if (tree[node].left  >= 0) postorder(tree[node].left);
	if (tree[node].right >= 0) postorder(tree[node].right);
	printf(" %d", node);
}

int main()
{
	int n, i, id;
	int root, left, right;

	n = in();
	for (i = 0; i < n; i++) {
		id = in();
		tree[id].left  = left =  in();
		tree[id].right = right = in();
		if (tree[id].left  >= 0) tree[left ].parent = id+1;
		if (tree[id].right >= 0) tree[right].parent = id+1;
	}
	for (root = 0; root < n; root++) {
		if (tree[root].parent == 0) break;
	}

	puts("Preorder");
	preorder(root); putchar('\n');
	puts("Inorder");
	inorder(root); putchar('\n');
	puts("Postorder");
	postorder(root); putchar('\n');
	return 0;
}


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

using namespace std;

int main() {
    int n;
    cin >> n;
    map<long long, int> m;
    bool ans = false;
    for(int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        try {
            m.at(a)++;
            ans = true;
            break;
        } catch (out_of_range) {
            m.insert(make_pair(a, 1));
        }
    }
    if (ans) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <stdio.h>

int main()
{
    int a[1000],b[1000],h,w,n,i,k=0;
    
    scanf("%d %d %d",&n,&h,&w);
    
    for(i=0;i<n;i++)
    {
            scanf("%d",&a[i]);
            scanf("%d",&b[i]);
    }

    for(i=0;i<=n;i++)
    {
        if(a[i]>=h && b[i]>=w)
        {
            k++;
        }
    }
    printf("%d",k);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T &  a, U &  ... b) { cin >> a; IN_(b ...); };
template<typename T                > void OUT(T && a            ) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; }
template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) {
	inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; }
	return s;
}

#define bit(b, i) (((b) >> (i)) & 1)
#define PC __builtin_popcountll
#define BL(a) (a ? 64 - __builtin_clzll(a) : 0)

int main() {
	IN(LL, n, k, s, t);
	vector<LL> a(n);
	cin >> a;
	
	if((s & t) != s) { OUT(0); exit(0); }
	
	{
		vector<LL> b;
		RF(e, a) {
			bool f = true;
			inc(d, 18) {
				f &= ! (bit(t, d) == 0 && bit(e, d) == 1);
				f &= ! (bit(s, d) == 1 && bit(e, d) == 0);
			}
			if(f) { b.PB(e); }
		}
		a = b;
	}
	n = SI(a);
	setmin(k, n);
	s ^= t;
	
	vector<LL> f(n + 1);
	incII(i, 0, n) {
		LL v = 1;
		inc1(j, k) {
			if(j > i) { break; }
			v *= i - (j - 1);
			v /= j;
			f[i] += v;
		}
	}
	
	LL ans = f[n];
	incID(b, 1, 1LL << 18) {
		if((s & b) != b) { continue; }
		
		map<LL, LL> mp;
		RF(e, a) { mp[e & b]++; }
		RF(e, mp) { ans -= (PC(b) % 2 == 0 ? -1 : +1) * (f[e.SE]); }
	}
	
	OUT(ans);
}


Measured memory_bytes: 3640
// -*- mode:c++; coding:utf-8; c-basic-offset:2; -*-
// ALDS1_12_A: Minimum Spanning Tree

#include <algorithm>
#include <cstdio>

using uint = unsigned int;

class Graph {
  const uint n_;
  uint* const g_;
  
public:
  const static uint INFINIT = 2000+1;

  Graph(uint n) : n_(n), g_(new uint[(n_*n_)]) { }

  ~Graph() { delete[] g_; }
  
  uint* operator [](uint i) const { return g_+(n_*i); }

  uint mst()
  {
    uint min[n_];
    std::fill_n(min, n_, INFINIT);
    bool visited[n_];
    std::fill_n(visited, n_, false);
    auto total_weight = 0u;
    auto i = 0u; // 0-start
    visited[i] = true;
    for (auto n = 0u; n < n_-1; ++n) {
      auto cur_min = INFINIT;
      auto es = (*this)[i];
      for (auto j = 0u; j < n_; ++j) {
        if (visited[j]) continue;
        min[j] = std::min(min[j], es[j]);
        if (cur_min > min[j]) {
          cur_min = min[j];
          i = j;
        }
      }
      visited[i] = true;
      total_weight += cur_min;
    }
    return total_weight;
  }
};

const uint Graph::INFINIT;

int main()
{
  uint n;
  std::scanf("%u", &n);

  Graph g(n);

  int e;
  for (auto i = 0u; i < n; ++i) {
    for (auto j = 0u; j < n; ++j) {
      std::scanf("%i", &e);
      g[i][j] = (e != -1) ? static_cast<uint>(e) : Graph::INFINIT;
    }
  }

  auto total_weight = g.mst();
  std::printf("%u\n", total_weight);
}

// eof

Measured memory_bytes: 2692
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();
		int ans = 0;
		for(int i = 0; i < S.length(); i++)
			if(S.charAt(i) != T.charAt(i))
				ans++;
		System.out.println(ans);
	}

}

Measured memory_bytes: 41040
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>

using namespace std;
typedef long long ll;

int gcd(int x, int y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    int r = x % y;
    x = y;
    y = r;
  }
  return x;
}

/*迷路
const int INF = 50;

typedef pair<int,int> P;
char field[52][52];
int d[51][51];
int r,c;
int sx,sy;
int gx,gy;

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

int bfs(){
    queue<P> que;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            d[i+1][j+1] = INF;
        }
    }
    que.push(P(sy,sx));
    d[sy][sx]=0;
while(que.size()){
    P p=que.front();
    que.pop();
    if(p.second==gx&&p.first==gy) break;
    for(int i=0;i<4;i++){
        int nx=p.second+dx[i];
        int ny=p.first+dy[i];

        if(1<=nx&&nx<=c&&1<=ny&&ny<=r&&field[ny][nx]!='#'&&d[ny][nx]==INF){
            que.push(P(ny,nx));
            d[ny][nx] = d[p.first][p.second] + 1;
        }
    }
}
return d[gy][gx];
}
*/

int main(){
    int n,m;
    cin>>n>>m;
    bool b[n+1];
    for(int i = 0; i < n+1; i++){
        b[i] = true;
    }
    for(int i = 0; i<m; i++){
        int c; cin>>c;
        b[c] = false;
    }
    vector<int> dp(n+1,0);
    dp[0] = 1;
    if(b[1]==true) dp[1] = 1;

    for(int i = 2; i<n+1;i++){
        if(b[i-1]==true) dp[i]+=dp[i-1];
        if(b[i-2]==true) dp[i]+=dp[i-2];
        dp[i]%=1000000007;
    }
    cout<<dp[n]<<endl;
    return 0;
}


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

int main(){
	int n;
	scanf("%d", &n);
	vector<int> p(n), q(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &p[i]);
	for(int i = 0; i < n; i++)
		scanf("%d", &q[i]);
	// for(int i = 0; i < n; i++)
	// 	temp[i] = i + 1;
	if(p[0] > q[0]) {
		swap(p, q);
	}
	int ans = 0;
	do {
		if(p == q) {
			break;
		}
		ans++;
	} while(next_permutation(p.begin(), p.end()));
	printf("%d\n", ans);
}


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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)



using namespace std;
typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }

using namespace std;


int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }

    int xmin, xmax, ymin, ymax, n;
    cin >> xmax >> ymax >> n;
    xmin = ymin = 0;

    while(n--) {
        int x, y, a;
        cin >> x >> y >> a;

        switch(a) {
        case 1:
            xmin = max(x, xmin);
            break;
        case 2:
            xmax = min(x, xmax);
            break;
        case 3:
            ymin = max(y, ymin);
            break;
        case 4:
            ymax = min(y, ymax);;
            break;
        }
    }

    cout << (xmin < xmax && ymin < ymax ? (xmax - xmin) * (ymax - ymin) : 0) << endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	if (a.at(a.length() - 1) == b.at(0) && b.at(b.length() - 1) == c.at(0))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
} 

Measured memory_bytes: 3632
#include <bits/stdc++.h> 
#define ll long long
#define M 1000000007
using namespace std;
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    ll n,k,d,x,count=0;
    cin>>n>>k;int arr[n]={0 };
    for(int i=0;i<k;i++)
    {
        cin>>d;
        for(int j=0;j<d;j++)
        {
            cin>>x;arr[x-1]=1;
        }
    }

    for(int i =0;i<n;i++)
    {
        if(arr[i]==0)count++;
    }    
    cout<<count;
}

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

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


int main() {
  const int inf = 100000000;
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i,N){
    cin >> A[i];
  }
  vector<int> num(200000+1);//num[i]はiの個数
  sort(A.begin(),A.end());
  
  for(int i = 0;i<N;i++){
    num[A[i]]++;
  }

  
  int c = 0;//数字の種類の個数
  for(int i= 0;i<=200000;i++){
    if(num[i] != 0) c++;
  }

  
  int ans = 0;
  sort(num.begin(),num.end());
  vector<int> p;
  for(int i =0;i<num.size();i++){
    if(num[i] != 0) p.push_back(num[i]); 
  }
  sort(p.begin(),p.end());

  
  for(int i = 0;i<c-K;i++){
    ans += p[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 2936
#include <iostream>
#include <queue>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>
using namespace std;

double dp[1024];

int main(){
  const int n = getInt();
  const int m = getInt();

  dp[0] = 1.0;
  for(int i = 0; i < n; i++){
    for(int j = 1; i + j <= n && j <= m; j++){
      dp[i + j] += dp[i] / (n - i);
    }
  }

  printf("%.10f\n", dp[n]);

  return 0;
}

Measured memory_bytes: 1232
n,a,b,c = map(int,input().split())
s_list = []
for i in range(n):
    s = input()
    s_list.append(s)

if a+b+c == 0:
    print("No")
    exit()

move = []
if a+b+c == 1:
    for i in range(n):
        if s_list[i] == "AB":
            if a == 0:
                a+=1
                b-=1
                move.append("A")
            else:
                b+=1
                a-=1
                move.append("B")
        if s_list[i] == "BC":
            if b == 0:
                b+=1
                c-=1
                move.append("B")
            else:
                c+=1
                b-=1
                move.append("C")
        if s_list[i] == "AC":
            if a == 0:
                a+=1
                c-=1
                move.append("A")
            else:
                c+=1
                a-=1
                move.append("C")
        if min(a,b,c) < 0:
            print("No")
            exit()

    print("Yes")
    for i in move:
        print(i)            
    
else:
    for i in range(n):
        if i < n-1:
            s_next = s_list[i+1]
        if s_list[i] == "AB":
            if a == 1 and b == 1 and s_next != "AB":
                if s_next == "BC":
                    b+=1
                    a-=1
                    move.append("B")
                else:
                    a+=1
                    b-=1
                    move.append("A")
            else:
                if a < b:
                    a+=1
                    b-=1
                    move.append("A")
                else:
                    b+=1
                    a-=1
                    move.append("B")
        if s_list[i] == "BC":
            if b == 1 and c == 1 and s_next != "BC":
                if s_next == "AB":
                    b+=1
                    c-=1
                    move.append("B")
                else:
                    c+=1
                    b-=1
                    move.append("C")
            else:
                if b < c:
                    b+=1
                    c-=1
                    move.append("B")
                else:
                    c+=1
                    b-=1
                    move.append("C")
        if s_list[i] == "AC":
            if a == 1 and c == 1 and s_next != "AC":
                if s_next == "AB":
                    a+=1
                    c-=1
                    move.append("A")
                else:
                    c+=1
                    a-=1
                    move.append("C")
            else:
                if a < c:
                    a+=1
                    c-=1
                    move.append("A")
                else:
                    c+=1
                    a-=1
                    move.append("C") 

        if min(a,b,c) < 0:
            print("No")
            exit()
    print("Yes")
    for i in move:
        print(i)     

Measured memory_bytes: 16824
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;
using ll=long long;
#define PRI(n) cout << n <<endl;
#define PRI2(n, m) cout << n << " " << m << endl;

#define PRI3(n, m, o) cout << n << " " << m<< " " << o << endl;

#define REP(i, n)  for(int i = 0; i < (int)n; ++i)
#define REP1(i, n)  for(int i = 1; i <= (int)n; ++i)
#define REPT(i, t, n)  for(int i = t; i <= (int)n; ++i)
const char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                           's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const ll MOD = 1e9 + 7;
typedef pair<int, int> Pi;

ll GCD(ll a, ll b) {
    if (b == 0)return a;
    return GCD(b, a % b);
}

ll LCM(ll a, ll b) {
    ll gcd = GCD(a, b);
    return a / gcd * b;
}

int cnt = 0;

ll dp[100010];
ll A[100010];
int N = 0, v = 0;

int main() {
    cin >> N;
    REP(i, N) {
        cin >> A[i];
        dp[i] = 1e18;
    }
    dp[0] = 0;
    REP(i, N) {
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(A[i] - A[i + 1]));
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(A[i] - A[i + 2]));
    }
    cout << dp[N-1] << endl;
    return 0;
}


Measured memory_bytes: 1792