akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, n) for(ll i=0; i<n; i++)
#define all(vec) vec.begin(), vec.end()
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7;
ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}
ll LCM(ll x, ll y) { 
  return x / GCD(x, y) * y;
}

int main(){
  string s; cin >> s;
  if(s == "Sunny") cout << "Cloudy" << endl;
  else if (s == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
}


Measured memory_bytes: 256
// finish date: 2018/01/15
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int i=a;i<b;i++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000

int mul(int a, int b) {
    return (int) (((ll) (a % bigmod) * (b % bigmod)) % bigmod);
}

ll nCk(int n, int k) {
    if (k == 0) return 1;
    ll ans = 1;
    FOR(i, 1, k + 1) {
        ans *= n;
        n--;
        ans /= i;
    }
    return ans;
}


ll gcd(ll a, ll b){
    if(a< 0) a = -a;
    if(b < 0) b = -b;
    if(a < b){
        swap(a,b);
    }
    ll r = 1; //0以外であれば何でも
    while(r != 0){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int N;
    ll T, ans;
    cin >> N;
    cin >> ans;

    rep(i, N - 1) {
        cin >> T;
        ans *= (T / gcd(T, ans));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
for i in range(1, N):
    if i == 1:
        dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    else:
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])


Measured memory_bytes: 13980
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

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

using namespace std;

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template <typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

int main(){
	//source
	int n=inputValue();
	vector<int> p;
	inputVector(&p,n);
	int max_value=0;
	int sum=0;
	rep(i,n){
		max_value=max(max_value,p[i]);
		sum+=p[i];
	}
	sum-=max_value/2;
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin >> S;
  int N = (int)(S.size());
  int only = 0;
  int sum = 0;
  for(int i = 0; i < N; ++i){
    if(S[i] == '1')only++;
    else if(S[i] !='0')only += 2;
    sum += int(S[i] - '0');    
  }
  if(only == 1)
    cout << 10 << endl;
  else cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  vector<int> values(n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &values[i]);
  vector<lint> sums;
  for (int i = 0; i < n; ++i) {
    lint sum = 0;
    for (int j = i; j < n; ++j) {
      sum += values[j];
      sums.push_back(sum);
    }
  }
  int maxb = __lg(*max_element(sums.begin(), sums.end()));
  lint result = 0LL;
  for (int b = maxb; b >= 0; --b) {
    lint target = result | (1LL<<b);
    int many = 0;
    for (lint s : sums)
      if ((s & target) == target)
        ++many;
    if (many >= k)
      result = target;
  }
  printf("%lld\n", result);

  return 0;
}


Measured memory_bytes: 6388
#include<stdio.h>
int main(void){
	char y[10];
	int i,kazu[10],yy,m,d;
	scanf("%s",&y);
	for(i=0;i<10;i++){
		if(i!=4&&i!=7){
			if(y[i]=='0'){
				kazu[i]=0;
			}else if(y[i]=='1'){
				kazu[i]=1;
			}else if(y[i]=='2'){
				kazu[i]=2;
			}else if(y[i]=='3'){
				kazu[i]=3;
			}else if(y[i]=='4'){
				kazu[i]=4;
			}else if(y[i]=='5'){
				kazu[i]=5;
			}else if(y[i]=='6'){
				kazu[i]=6;
			}else if(y[i]=='7'){
				kazu[i]=7;
			}else if(y[i]=='8'){
				kazu[i]=8;
			}else if(y[i]=='9'){
				kazu[i]=9;
			}
		}
	}
	yy=kazu[0]*1000+kazu[1]*100+kazu[2]*10+kazu[3];
	m=kazu[5]*10+kazu[6];
	d=kazu[8]*10+kazu[9];
	
	if(yy>2019){
		printf("TBD\n");
	}else if(yy==2019&&m>4){
		printf("TBD\n");
	}else if(yy==2019&&m==4&&d>30){
		printf("TBD\n");
	}else{
		printf("Heisei\n");
	}
	return 0;
}

Measured memory_bytes: 256
#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> // double
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define rep1(i,n) for(in6 i = 1; i < (in6)(n); i++)
#define repc(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 20000000

int main() {
  kyun;
  int n,m;
  cin >> n >> m;
  vpi data(n);
  rep(i,n) cin >> data[i].first >> data[i].second;
  vii dp(n+1,vi(m+1));
  rep(i,m+1) dp[0][i] = 0;
  rep(i,n) {
      rep(j,m+1) {
          if(j < data[i].second) dp[i+1][j] = dp[i][j];
          else dp[i+1][j] = max(dp[i][j-data[i].second]+data[i].first,dp[i][j]);
      }
  }
  cout << dp[n][m];
  hinata;
}


Measured memory_bytes: 6840
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	REP(i,10){
		string S=in<string>();
		if(S=="-") break;
		int M=in();
		REP(i,M){
			int H=in();
			auto pre = S.substr(0,H);
			auto suf = S.substr(H);
			S = suf+pre;
		}
		out(S);
	}
	return 0;
}



Measured memory_bytes: 3172
n = int(input())
a = list(map(int, input().split()))
a.insert(n,0)
a.insert(0,0)
sum_ = 0
b_list = []
for i in range(n+1):
    sum_ += abs(a[i+1]-a[i])
for i in range(1,n+1):
    b = abs(a[i+1]-a[i-1])
    b_list.append(b)
for i in range(1,n+1):
    ans = sum_ - (abs(a[i]-a[i-1])+abs(a[i+1]-a[i])) + b_list[i-1]
    print(ans)

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

int main(){
  double a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<fixed<<setprecision(10)<<(double)a*b/2<<' ';
  if(c==a/2 && d==b/2){
    cout<<1;}else{
    cout<<0;}
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>

using namespace std;

class Dice{
	int face[6] ;
	map<string,int> dir;
	
public:
	Dice(){
		dir["top"]    = 1 ;
		dir["south"]  = 2 ;
		dir["east"]   = 3 ;
		dir["west"]   = 4 ;
		dir["north"]  = 5 ;
		dir["bottom"] = 6 ;
	}
	Dice(int sai[6]){
		for(int i=0 ; i<6 ; i++){
			face[i] = sai[i] ;
		}
		dir["top"]    = 1 ;
		dir["south"]  = 2 ;
		dir["east"]   = 3 ;
		dir["west"]   = 4 ;
		dir["north"]  = 5 ;
		dir["bottom"] = 6 ;
	}
	void set_face(int sai[6]){
		for(int i=0 ; i<6 ; i++){
			face[i] = sai[i] ;
		}
	}
	void show(string d){
		if(d == "all"){
			for(int i=0 ; i<6 ; i++){
				cout << face[i] << " " ;
			}
			cout << endl;
			return ;
		}else{
			cout << face[dir[d]-1] << endl;
		}
	}
	int get(string d){
		return face[dir[d]-1] ;
	}
	void move(const string str){//動かす
		for(int i=0 ; i<str.size() ; i++){
			turn(str[i]);//char
		}
	}
	void turn(char d){//回す//direction:方向
		map<char, int> mp;
		mp['S'] = 0 ;
		mp['E'] = 1 ;
		mp['W'] = 2 ;
		mp['N'] = 3 ;
		
		static const int index[4][6] ={
			{5,1,3,4,6,2},//south
			{4,2,1,6,5,3},//east
			{3,2,6,1,5,4},//west
			{2,6,3,4,1,5},//north
		};
		
		int copy[6] ;
		for(int i=0 ; i<6 ; i++){
			copy[i] = face[i] ;
		}
		//これは止めて、代入演算子＝をオーバーライドしてもいいかもしれない。しかして、それをやると実行時のメモリが微増するはずだ。
		
		for(int i=0 ; i<6 ; i++){//permutation:置換
			face[i] = copy[index[mp[d]][i]-1] ;
		}
		
		//show("all");//check
	}
	void rotate(void){//回転//SWNの操作で、上から見てCCW:counter clock wise：反時計回りでの90度回転。
		turn('S');
		turn('W');
		turn('N');
	}
	bool adjust(int top,int south){//位置合わせ
		for(int i=0;i<6;i++){
			if(get("top") == top){
				break;
			}
			//cout << "zigzag:" << i << endl ;//check
			turn(i%2==0 ? 'S' : 'E');//三項演算子
		}
		for(int i=0;i<4;i++){
			//cout << "rotate:" << i << endl ;//check
			rotate();
			if(get("south") == south){
				return true ;
			}
		}
		
		return false ;
	}
	bool operator == (Dice obj){
		for(int i=0 ; i<6 ; i++){
			for(int j=0 ; j<4 ; j++){
				bool flg = true ;
				for(int k=0 ; k<6 ; k++){
					if(this->face[k] == obj.face[k]){
						flg &= true ;
					}else{
						flg &= false ;
					}
				}
				if(flg){
					return true ;
				}
				this->rotate();
			}
			this->turn(i%2==0 ? 'S' : 'E');
		}
		return false ;
	}
	/*
	bool operator == (Dice obj){//演算子のオーバーライド
		if(obj.adjust(this->get("top"),this->get("south"))){
			for(int i=0 ; i<6 ; i++){
				if(this->face[i] != obj.face[i]){
					return false ;
				}
			}
			return true ;
		}
		
		return false ;
	}
	*/
};
int main(void){
	// ITP1_11_D　全部異なる
	int nn ;
	cin >> nn ;
	Dice *d ;
	d = new Dice[nn] ;
	
	for(int i=0 ; i<nn ; i++){
		int sai[6] ;
		cin >> sai[0] >> sai[1] >> sai[2] >> sai[3] >> sai[4] >> sai[5] ;
		d[i].set_face(sai);
	}
	
	if(nn==2){
		cout << (d[0]==d[1] ? "No" : "Yes") << endl ;
		return 0 ;
	}
	
	bool flg = true ;
	for(int i=0 ; i<nn ; i++){
		for(int j=i+1 ; j<nn-1 ; j++){
			flg &= (d[i]==d[j] ? false : true) ;
		}
	}
	cout << (flg ? "Yes" : "No") << endl ;
}

Measured memory_bytes: 1288
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int H,W; cin >> H >> W;
  vector<string> maze(H);
  rep(i,H) {
    cin >> maze[i];    
  }
  vvi up(H, vi(W));
  vvi down(H, vi(W));
  vvi right(H, vi(W));
  vvi left(H, vi(W));
  rep(i, H) {
    rep(j,W) {
      if (maze[i][j] == '#') {
        up[i][j] = down[i][j] = right[i][j] = left[i][j] = 0;
        continue;
      }
      if (i) {
        if (maze[i-1][j] == '#') up[i][j] = 0;
        else up[i][j]=up[i-1][j]+1;
      } 
     if (j) {
        if (maze[i][j-1] == '#') left[i][j] = 0;
        else left[i][j] = left[i][j-1]+1;
      }
   }
  }
  for (int i=H-1; i>=0; i--) {
    for (int j=W-1; j>=0; j--) {
      if (j<W-1) {
        if (maze[i][j + 1] == '#') right[i][j] = 0;
        else right[i][j] = right[i][j+1] + 1;
      }
       if (i<H-1) {
        if (maze[i+1][j] == '#') down[i][j] = 0;
        else down[i][j] = down[i+1][j] + 1;
      }
    }
  }
  int ans = 0;
  rep(i,H) {
    rep(j,W) {
      if (maze[i][j] == '#') continue;
      int foo = up[i][j]+down[i][j]+right[i][j]+left[i][j]+1;
      ans = max(ans, foo);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 67200
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let (K, X) = read!(i64, i64);

    println!(
        "{}",
        (X - K + 1..X + K)
            .map(|i| i.to_string())
            .collect::<Vec<_>>()
            .join(" ")
    )
}


Measured memory_bytes: 4352
A,B,K = map(int, input().split())
divisor = []
count = 0 #約数の数を調べる

for i in range(1,101):
  if A % i == 0 and B % i == 0:
    count += 1
    divisor.append(i)

target_num = count - K
print(divisor[target_num])

Measured memory_bytes: 2940
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

N, M, *AB = map(int, read().split())
graph = [[] for _ in range(N + 1)]
for A, B in zip(*[iter(AB)] * 2):
    graph[A].append(B)
    graph[B].append(A)

answer = [-1] * (N + 1)
queue = deque([1])
answer[1] = 0
while queue:
    room = queue.popleft()
    for i in graph[room]:
        if answer[i] != -1:
            continue
        answer[i] = room
        queue.append(i)

print('Yes')
print('\n'.join(map(str, answer[2:])))


Measured memory_bytes: 54056
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;

int32_t main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
       string s;
       cin >> s;
       int n=s.size();
       int i,ans=0;
       for(i=0; i<n/2; i++){
           if(s[i]!=s[n-i-1]){
               ans++;
           }
       }
       cout << ans;
}


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

ll N, Q;
ll W[100000], U[100000], V[100000], A[100000], B[100000];
vector<ll> E[100000];
ll x[100000][3], y[100000];
ll depth[100000], parent[20][100000], mx[20][100000];

void dfs(ll v, ll p, ll d) {
  parent[0][v] = p;
  depth[v] = d;
  for(ll u : E[v]) if(u != p) dfs(u, v, d + 1);
}

ll subtree_size(ll v, ll p) {
  vector<ll> child;
  for(ll u : E[v]) if(u != p) child.push_back(subtree_size(u, v));
  sort(child.begin(), child.end(), greater<ll>());
  REP(i, 0, 3) x[v][i] = i < child.size() ? child[i] : 0;
  for(ll u : E[v]) if(u != p) mx[0][u] = x[v][0] != y[u] ? x[v][0] : x[v][1];
  y[v] = W[v];
  REP(i, 0, child.size()) y[v] += child[i];
  return y[v];
}

ll query(ll u, ll v) {
  if(depth[u] > depth[v]) swap(u, v);
  REP(i, 0, 20) if(((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
  if(u == v) return u;
  for(ll i = 19; i >= 0; i--) if(parent[i][u] != parent[i][v]) {
    u = parent[i][u];
    v = parent[i][v];
  }
  return parent[0][u];
}

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> W[i];
  REP(i, 0, N - 1) {
    cin >> U[i] >> V[i]; U[i]--; V[i]--;
    E[U[i]].push_back(V[i]);
    E[V[i]].push_back(U[i]);
  }
  cin >> Q;
  REP(i, 0, Q) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }

  dfs(0, -1, 0);
  subtree_size(0, -1);
  REP(i, 0, 19) REP(j, 0, N) parent[i + 1][j] = parent[i][j] >= 0 ? parent[i][parent[i][j]] : -1;
  REP(i, 0, 19) REP(j, 0, N) if(parent[i][j] >= 0) mx[i + 1][j] = max(mx[i][j], mx[i][parent[i][j]]);

  REP(q, 0, Q) {
    ll a = A[q], b = B[q], lca = query(a, b);
    ll ans = 0;
    if(lca == a || lca == b) {
      if(lca == b) swap(a, b);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] >= depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      ans = max(ans, y[0] - y[lca]);
    } else {
      ans = max(ans, x[a][0]);
      ans = max(ans, x[b][0]);
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][a] >= 0 && depth[parent[i][a]] > depth[lca]) {
          ans = max(ans, mx[i][a]);
          a = parent[i][a];
        }
      }
      for(ll i = 19; i >= 0; i--) {
        if(parent[i][b] >= 0 && depth[parent[i][b]] > depth[lca]) {
          ans = max(ans, mx[i][b]);
          b = parent[i][b];
        }
      }
      vector<ll> r;
      r.push_back(y[a]);
      r.push_back(y[b]);
      r.push_back(-1);
      sort(r.begin(), r.end(), greater<ll>());
      REP(i, 0, 3) if(r[i] != x[lca][i]) ans = max(ans, x[lca][i]);
      ans = max(ans, y[0] - y[lca]);
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 37372
fun main(args: Array<String>) {
  val (K, S) = readLine()!!.split(" ").map(String::toInt)
  var ans = 0

  (0..K).forEach { X -> 
    (0..K).forEach { Y ->
      if (0 <= S-X-Y && S-X-Y <= K) {
        ans = ans + 1
      }
    }
  }
  println(ans)
}

Measured memory_bytes: 40408
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, m, n) for (int i = m; i<n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
#define SUM(x) accumulate(x.begin(), x.end(),0);
#define vint(v,n) vector<int> v(n); REP(i,n) scanf("%lld", &v[i]);
#define vstr(v,n) vector<string> v(n); REP(i,n) scanf("%lld", &v[i]);
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n % 2 == 0 || n % 3 == 0) return false;
    // n は 2 と 3 のいずれの倍数でもないことが保証された
    // これより n は (6の倍数)-1 か (6の倍数)+1 である

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }

    return true;
}
int k=0,n=0, m=0, l=0,r=0,a=0, b=0, c=0, d=0,e=0,ans=0,ans2=0,x=0,y=0;
string s,t,S;
signed main() {
    cin >> n >> d >> x;
  REP(j,n){
  int i=1;
    cin >>a;
  while (1)
    {
        i += a;
        if(i >d)break;
        ans++;
    }
  }
  cout <<ans+x+n;
}

Measured memory_bytes: 3608
#include<iostream>

using namespace std;

int main(){
	int l, r, d;
	
	cin>>l>>r>>d;
	
	int awal = l/d, akhir = r/d;
	awal *= d;
	akhir *= d;
	
	if(awal < l) awal += d;
	
	cout<<(akhir-awal)/d + 1<<"\n";
	
	return 0;
}

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

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	vector<int> ans(n,0);
	long long int ansr=1;
	for(int i = 0;i<n;i++){
		cin>>a[i];
		ans[a[i]]++;
	}
	if(n%2==1)ans[0]++;
	for(int i = 1-n%2;i<n;i+=2){
		if(ans[i]!=2){
			cout<<0<<endl;
			return 0;
		}
		if(i!=0)ansr*=2;
		ansr%=1000000007;
	}
	cout<<ansr<<endl;
	return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
} Accelerate_Cin;

signed main() {
  int N;
  string s;
  int Q;
  cin >> N >> s >> Q;

  while (Q--) {
    int k;
    cin >> k;

    int d = 0, dm = 0, m = 0, l = 0, r = 0, ans = 0;
    for (;;) {
      while (r < N && r - l < k) {
        if (s[r] == 'D') d++;
        if (s[r] == 'M') dm += d, m++;
        if (s[r] == 'C') ans += dm;
        r++;
      }

      if (l == N) break;

      if (s[l] == 'D') d--, dm -= m;
      if (s[l] == 'M') m--;
      l++;
    }

    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 1948
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<functional>
#include<queue>
#include<stack>
using namespace std;
int H, W, p[3000][3000], L[3000], R[3000]; string S[3000]; stack<int>T;
int solve(vector<int>U) {
	for (int i = 0; i < U.size(); i++) {
		while (!T.empty() && U[T.top()] >= U[i])T.pop();
		if (T.size() >= 1)L[i] = (T.top() + 1); else L[i] = 0;
		T.push(i);
	}
	while (!T.empty())T.pop();
	for (int i = U.size() - 1; i >= 0; i--) {
		while (!T.empty() && U[T.top()] >= U[i])T.pop();
		if (T.size() >= 1)R[i] = (T.top()); else R[i] = U.size();
		T.push(i);
	}
	int maxn = 0;
	for (int i = 0; i < U.size(); i++)maxn = max(maxn, U[i] * (R[i] - L[i] + 1));
	return maxn;
}
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++)cin >> S[i];
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) { if (S[i][j] == S[i + 1][j])p[i][j + 1] = 0; else p[i][j + 1] = 1; }
	}
	for (int i = 0; i < H - 1; i++) {
		for (int j = 1; j <= W; j++)p[i][j] += p[i][j - 1];
	}
	int ret = W;
	for (int i = 0; i < W; i++) {
		vector<int>V;
		for (int j = 0; j < H - 1; j++) {
			int L = i, R = W + 1, M, maxn = i;
			for (int k = 0; k < 17; k++) {
				M = (L + R) / 2;
				int T = p[j][M] - p[j][i];
				if (T == 0 || T == (M - i)) { maxn = max(maxn, M); L = M; }
				else R = M;
			}
			V.push_back(maxn - i);
		}
		ret = max(ret, solve(V));
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 28928
//ABC122A
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	char a, b;
	cin >> a;
	if(a == 'A'){
		b = 'T';
	}else if(a == 'T'){
		b = 'A';
	}else if(a == 'G'){
		b = 'C';
	}else if(a == 'C'){
		b = 'G';
	}
	cout << b << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int isprime(int);
int main(){
  int a,i,n,cnt=0;
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&a);
  
    if(isprime(a)){
      cnt++;
    }
    
  }
  printf("%d\n",cnt);




  return 0;
}
int isprime(int a){
  int x;
  static int i; 
  if (a < 2)
    return 0;
  else if(a==2)return 1;
    
  if(a%2==0){
    return 0;
  }
  for(i=3;i*i<=a;i++){
    if(a%i==0) return 0;
  }
  return 1;
}

  



Measured memory_bytes: 2684
#include <iostream>

using namespace std;
const int maxn=50+1;
int main()
{  int a[maxn];
   int b[maxn];
    int n;
    while(cin>>n)
    {
          for(int i=0;i<n;i++)
          {

              cin>>a[i];
          }

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

              cin>>b[i];
          }
          int sum=0;

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

              if(a[i]>b[i])
              {

                  sum+=a[i]-b[i];
              }
          }
          cout<<sum<<endl;

    }
    return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  string s, t;
  cin >> s >> t;
  bool can = (s.size() + 1 == t.size());
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != t[i]) can = false;
  }

  if (can) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;

/** Problem0533 : Contest **/
int main()
{
	vector<int> W(10), K(10);
	rep(i, 10) cin>>W[i];
	rep(i, 10) cin>>K[i];
	sort(W.begin(), W.end(), greater<int>());
	sort(K.begin(), K.end(), greater<int>());
	int sw=0, sk=0;
	rep(i, 3) { sw+=W[i]; sk+=K[i]; }
	cout << sw << " " << sk << endl;
}

Measured memory_bytes: 1216
package main

import (
	. "fmt"
	"io"
	"os"
	"sort"
)

type event struct{ p, i, d int }
type events []event

func (p events) Len() int           { return len(p) }
func (p events) Less(i, j int) bool { return p[i].p < p[j].p }
func (p events) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, _w io.Writer) {
	buf := make([]byte, 4096)
	_i := len(buf)
	rc := func() byte {
		if _i == len(buf) {
			_r.Read(buf)
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}
	ri := func() (x int) {
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		return
	}
	r, c, n := ri(), ri(), ri()
	border := func(x, y int) bool { return x == 0 || x == r || y == 0 || y == c }
	getP := func(x, y int) int {
		if y == 0 || x == r {
			return x + y
		}
		return 2*r + 2*c - x - y
	}
	es := events{}
	for i := 0; i < n; i++ {
		x1, y1, x2, y2 := ri(), ri(), ri(), ri()
		if border(x1, y1) && border(x2, y2) {
			p1, p2 := getP(x1, y1), getP(x2, y2)
			if p1 > p2 {
				p1, p2 = p2, p1
			}
			es = append(es, event{p1, i, 1}, event{p2, i, -1})
		}
	}
	sort.Sort(es)
	s := []int{}
	for _, e := range es {
		if e.d == 1 {
			s = append(s, e.i)
		} else {
			if s[len(s)-1] != e.i {
				Fprint(_w, "NO")
				return
			}
			s = s[:len(s)-1]
		}
	}
	Fprint(_w, "YES")
}

func main() { run(os.Stdin, os.Stdout) }


Measured memory_bytes: 16256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"basic.hpp"
#else
template <class... T> void printl(T&&...){ }
template <class... T> void printc(T&&...){ }
template <class... T> void prints(T&&...){ }
#endif

vector<int> as;
map<int, set<int>> mp;
int func(int win){
    auto& s = mp[win];
    vector<int> rets;
    for(int i : s){
        rets.push_back(func(i));
    }
    sort(rets.begin(), rets.end());
    int prev = -1;
    prints(win, rets);
    for(int i : rets){
        if(prev >= i){
            i = prev + 1;
        }
        prev = i;
    }
    return prev + 1;
}

int main(){
    int n; cin >> n;
    as.resize(n + 10);
    for(int i=2;i<n+2;i++){
        cin >> as[i];
        mp[as[i]].insert(i);
    }
    cout << func(1) << '\n';
    return 0;
}


Measured memory_bytes: 22528
H,W=map(int,input().split())
S=[[s for s in input().split()] for i in range(H)]
alpha=['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']
for i in range(H):
    for j in range(W):
        #print(S[i][j],1)
        if S[i][j]=="snuke":
            s=i
            t=j
            break
print(alpha[t]+str(s+1))




Measured memory_bytes: 38256
#include "bits/stdc++.h"
using namespace std;

const int N=2e5+20;

int n,a[N],inf;
long long k;
vector <int> dp[N];

void go(int node,int steps=1)
{
	if(steps>=1000000) return;
	dp[node].push_back(steps);
	int child=a[node];
	go(child,steps+1);
}

int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	k++;
	go(1);
	for(int i=1;i<=n;i++)
	{
		for(auto j:dp[i])
			if(j==k) return 0 * printf("%d",i);
		if(dp[i].size()>1 and k>=dp[i][0])
		{
			assert(dp[i][0]!=dp[i][1]);
			if((k-dp[i][0])%(dp[i][1]-dp[i][0])==0)
				return 0 * printf("%d",i);
		}
	}
	printf("%d",inf);
}

Measured memory_bytes: 50124
// I love
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

const int N = 55;

vector<int> adj[N];

int ans = 0;

int id[N], ch[N], cnt = 0;

void dfs(int i, int p) {
  id[i] = ch[i] = ++cnt;
  for (auto &j : adj[i]) {
    if (j == p) continue;
    if (id[j]) ch[i] = min(ch[i], ch[j]);
    else {
      dfs(j, i);
      ch[i] = min(ch[i], ch[j]);
      if (id[i] < ch[j]) ans++;
    }
  }
}

void MAIN() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, 0);
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3660
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
string s; 
int main(){
    cin>>s;
    //
    if(s.find('F')==std::string::npos){printf("No");return 0;}//如果查不到
    //T的数据,如‘C’
    if(s.find('C')<s.rfind('F')) printf("Yes");
    else printf("No");
    return 0;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

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

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


bool prime[222222];
signed main(){
    int x;cin>>x;
    fill_n(prime,222222,1);
    prime[0]=prime[1]=0;
    for(int i=2;;i++){
        if(!prime[i])continue;
        if(i>=x){
            cout<<i<<endl;
            return 0;
        }
        for(int j=i+i;j<222222;j+=i)prime[j]=0;
    }
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);
#define ll long long int
#define MAXN 100123
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define ps push_back
#define SZ(v) int(v.size())
#define FORINT(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,n) FORINT(i,0,n)
#define INF INT_MAX
#define ms(v,x) memset(v,x,sizeof(v))
using namespace std;

int n,t;
ll soma;

ll resp(int i){
	if(i%3 == 0 || i%5==0) return 0;
	return (ll)i;
}

int main(){_
	cin >> n;
	
	FORINT(i,1,n+1){
		soma+=resp(i);
	}
	cout << soma << endl;

	return 0;
}

Measured memory_bytes: 3668
a,b,c,x,y = gets.split.map(&:to_i)

c1 = a * x + b * y
c2 = [x,y].max * 2 * c
c3 = x * 2 * c + [0, y-x].max * b
c4 = y * 2 * c + [0, x-y].max * a

ans = [c1,c2,c3,c4].min

p ans

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int f(char x){
    return x - '0';
}
int main()
{
    char in, pre_in;
    int sum = 0;
    while (in = getc(stdin))
    {
        if('0' <= in && in <= '9')
            sum += in - '0';
        if(in == '\n') {
            cout << sum << '\n';
            sum = 0;
        }
        if(pre_in == '\n' && in == '0')
            break;
        pre_in = in;
    }
    
  
    return 0;
}


Measured memory_bytes: 3084
# from math import factorial
# from collections import defaultdict, deque
#  from heapq import heappush, heappop, heapify

# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# edges = defaultdict(list)
# for _ in range(N - 1):
#     a, b = [int(i) for i in input().split(" ")]
#     edges[a-1].append(b-1)

N, K = [int(i) for i in input().split(" ")]
Hs = [int(i) for i in input().split(" ")]
print(len([h for h in Hs if K <= h]))


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

int main(int argc, const char * argv[]) {
    // insert code here...

    char X,Y;
    
    cin >> X >> Y;
    
    if(X == Y)
        cout <<  '=' << endl;
    
    if(X>Y){
        cout << '>' << endl;
    }
    if(X<Y){
        cout << '<' << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int MAX=20000+10;
const double eps=1e-6;

ll n,ans=0;
struct NODE{
	ll num,cost;
	double val;
};

int cmp(NODE a,NODE b){
	if(a.num==b.num)
		return a.val<b.val;
	else
		return a.num<b.num;
}

int main(){
    #ifdef ONLINE_JUDGE
    #else
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    #endif
    NODE s[5];
    s[0].val=0.25;
    s[1].val=0.5;
    s[2].val=1;
    s[3].val=2;
    int flag=3;
    for(int i=0;i<=3;i++){
    	ll cost;
    	cin>>cost;
    	s[i].cost=cost;
    	s[i].num=cost*pow(2,flag--);
    }
    cin>>n;
    sort(s,s+4,cmp);
    for(int i=0;i<=3;i++){
    	ll temp=(n/s[i].val);
    	n=n-temp*s[i].val;
    	ans+=temp*s[i].cost;
    	if(n<=0)	break;
    }
    printf("%lld\n",ans);
    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 ll long long
const int MOD = 1000000007;

int main(){
  ll N, M;
  cin >> N >> M;
  vector<bool> issafe;
  issafe.assign(N+1, true);
  rep(i,M){
    int a;
    cin >> a;
    issafe[a] = false;
  }
  
  vector<int> dp(N+1, 0);
  
  dp[0] = 1;
  if (issafe[1]) dp[1] = 1;
  
  for (int i = 2; i<=N; i++){
    if (issafe[i-1]) dp[i] += dp[i-1];
    if (issafe[i-2]) dp[i] += dp[i-2];
    dp[i] %= MOD;
  }
  
  cout << dp[N] << endl;
  
}

Measured memory_bytes: 640
// inputに入力データ全体が入る
function Main(input) {
  var X = input.replace('\n', '');
  
  if (X === "7" || X === "5" || X === "3" ){
    console.log("%s", "YES");
  }else{
    console.log("%s", "NO");
  }

}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
  int sx, sy, tx, ty, dx, dy;
  cin >> sx >> sy >> tx >> ty;
  dx = tx - sx;
  dy = ty - sy;

  string s = "";
  s += string(dy, 'U');
  s += string(dx, 'R');
  s += string(dy, 'D');
  s += string(dx, 'L');
  s += 'L';
  s += string(dy + 1, 'U');
  s += string(dx + 1, 'R');
  s += 'D';
  s += 'R';
  s += string(dy + 1, 'D');
  s += string(dx + 1, 'L');
  s += 'U';
  cout << s << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdio>
#include<set>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++) 
#define lint long long
#define all(x) (x).begin(), (x).end()

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

int main(){
    int A, B, Q; cin>>A>>B>>Q;
    vector<lint> s(A); vector<lint> t(B);
    rep(i, A) cin>>s[i];
    rep(i, B) cin>>t[i];
    rep(i, Q){
        lint x; cin >> x;
        auto itr1 = lower_bound(all(s), x);
        auto itr2 = lower_bound(all(t), x);
        lint sr, sl, tr, tl;
        sr = 1e12; tr = 1e12; sl = -1e12; tl = -1e12;
        if(itr1 != s.end()) sr = *itr1;
        if(itr2 != t.end()) tr = *itr2;
        if(itr1 != s.begin()) sl = *(--itr1);
        if(itr2 != t.begin()) tl = *(--itr2);
        lint ans;
        if ((sl>=tl && sr<=tr) || (sl<=tl && sr>=tr)){
            ans = min(x - min(sl, tl), max(sr, tr) - x);
        }
        else{
            ans = min(x- min(sl, tl), max(sr, tr)-x);
            ans = min(ans, x - 2*max(sl,tl) + min(sr,tr));
            ans = min(ans, 2*min(sr,tr) - x - max(sl,tl));
        }
        cout << ans << endl;
    }

}

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int cnt=0;
  for(int i=0;i<n-2;i++){
    if(s[i]=='A' && s[i+1]=='B' && s[i+2] == 'C'){
      cnt++;
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI = acos(-1.0), EPS = 1e-9;
const long long INF = OO;
const int MAXN = 206, MAXM = 102, Mod = 998244353, MAXLog = 20;

int n;
int memo[MAXN];
int B[MAXN];
int solve(int idx) {
    if (idx == n)
        return 0;
    int &ret = memo[idx];
    if (~ret)
        return ret;
    ret = 0;
    if (idx == 0) {
        for (int i = 0; i <= B[idx]; ++i) {
            ret = max(ret, i + solve(idx + 1));
        }
    } else if (idx == n - 1) {
        for (int i = 0; i <= B[idx - 1]; ++i) {
            ret = max(ret, i + solve(idx + 1));
        }
    }else {
        for (int i = 0; i <= B[idx] && i <= B[idx - 1]; ++i) {
            ret = max(ret, i + solve(idx + 1));
        }
    }

    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(9), cout
            << fixed;


    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        cin >> B[i];
    }
    memset(memo, -1, sizeof memo);
    cout << solve(0) << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

typedef Node * NodePointer;

void insert(int);
void inorderPrint(NodePointer);
void preorderPrint(NodePointer);
NodePointer createNode();

NodePointer root = NULL;

main(){
  int order, key, i;
  char command[7];

  scanf("%d", &order);

  for( i = 0; i < order; i++){
    scanf("%s", command);

    if( strcmp(command, "insert") == 0 ){
      scanf("%d", &key);
      insert(key);
    }
    else if( strcmp(command, "print") == 0 ){
      inorderPrint(root);
      printf("\n");
      preorderPrint(root);
      printf("\n");
    }
  }

  return 0;

}


void insert(int key){
  NodePointer x = root;
  NodePointer y = NULL;
  NodePointer z = createNode();

  z->key = key;

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

  z->parent = y;

  if( y == NULL ) root = z;
  else if( z->key < y->key ) y->left = z;
  else y->right = z;

}


void inorderPrint(NodePointer x){
  
  if( x != NULL ){
    inorderPrint(x->left);
    printf(" %d", x->key);
    inorderPrint(x->right);
  }
  
}


void preorderPrint(NodePointer x){

  if( x != NULL ){
  printf(" %d", x->key);
  preorderPrint(x->left);
  preorderPrint(x->right);
  }

}


NodePointer createNode(){
  NodePointer x;

  x = malloc(sizeof(Node));
  x->key = 0;
  x->parent = NULL;
  x->left = NULL;
  x->right = NULL;

  return x;

}

Measured memory_bytes: 24040
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll  long long
#define mod 1000000007
#define ve vector
#define pi pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define all(v) v.begin(),v.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int inf=1e9+5;


ll power(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b/=2;
	}
	return res;
}



void solve()
{ 
 int n;
 double d;
 cin>>n>>d;
 int ans=0;
 while(n--)
 {
  double x,y;
  cin>>x>>y;
  double res=sqrt(x*x+y*y);
  if(res<=d)ans++;
 }
 cout<<ans<<endl;
    
}

signed main()
{
//#ifndef ONLINE_JUDGE
    //  freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
//#endif
    FAST;
   
    
     int t=1;
  //   cin>>t;
     while(t--)
    	solve();
    return 0;
}



Measured memory_bytes: 3864
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{ 
    static void Main(string[]args)
    {
        Magatro m = new Magatro();
        m.Scan();
        m.Solve();
    }
}

public class Scanner
{
    private StreamReader Sr;
    private string[] S;
    private int Index;

    private const char Separator=' ';

    public Scanner()
    {
        Index = 0;
        S = new string[0];
        Sr = new StreamReader(Console.OpenStandardInput());
    }

    private string[] Line()
    {
        return Sr.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
    public string[] StringArray(int index = 0)
    {
        Next();
        Index = S.Length;
        return S.Skip(index).ToArray();
    }
    public int[] IntArray(int index = 0)
    {
        return StringArray(index).Select(int.Parse).ToArray();
    }
    public long[]LongArray(int index = 0)
    {
        return StringArray(index).Select(long.Parse).ToArray();
    }

    public bool ScanToEnd(ref string s)
    {
        if (Sr.EndOfStream)
        {
            return false;
        }
        else
        {
            s = Sr.ReadLine();
            return true;
        }
    }
}

public class Magatro
{
    private long N;
    private long A, B;

    private long[] X;

    public void Scan()
    {
        Scanner sc = new Scanner();
        N = sc.NextInt();
        A = sc.NextInt();
        B = sc.NextInt();
        X = sc.LongArray();
    }

    public void Solve()
    {
        long ans = 0;
        for (int i = 0; i < N-1; i++)
        {
            ans += Math.Min(B, (X[i+1] - X[i]) * A);
        }

        Console.WriteLine(ans);
    }
}



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

int main() {
  int N;
  cin >> N;
  int a[4];
  a[0] = N%10; N /= 10;
  a[1] = N%10; N /= 10;
  a[2] = N%10; N /= 10;
  a[3] = N%10; N /= 10;

  if (a[0]==a[1] && a[1]==a[2]){ // 012
  	cout << "Yes" <<endl;
  } 
  else if (a[1]==a[2] && a[2]==a[3]){ // 123
  	cout << "Yes" <<endl;
  }
  else{
  	cout << "No" <<endl;
  }
  
}


Measured memory_bytes: 256