akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    string o,e; cin>>o>>e;
    rep(i,e.size()) cout<<o[i]<<e[i];
    if(o.size()>e.size()) cout<<o[o.size()-1];
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount
           
#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


const int coin[] = { 500, 100, 50, 10, 5, 1 };
int min_coin(int change)
{
    int res = 0;
    rep (i, 6)
    {
	int c = change / coin[i];
	res += c;
	change -= c * coin[i];
    }
    return res;
}
bool pint_eq(const pint& a, const pint& b)
{
    return a.first == b.first;
}
int main()
{
    int p, n[6];
    while (scanf("%d", &p), p)
    {
	rep (i, 6)
	    scanf("%d", n + i);
	reverse(n, n + 6);

	vector<pint> d[7];
	d[0].push_back(pint(p,0));

	int res = 1 << 25;
	rep (i, 6)
	{
	    rep (j, d[i].size())
	    {
		int left = d[i][j].first;
		int use = d[i][j].second;
		for (int c = min(n[i], max(0, left / coin[i]));
		     c <= n[i] && c * left - c * coin[i] >= -500; ++c)
		{
		    d[i + 1].push_back(pint(left - c * coin[i], use + c));
		}
	    }
	    sort(all(d[i + 1]));
	    d[i + 1].erase(unique(all(d[i + 1]), pint_eq), d[i + 1].end());
	    rep (j, d[i + 1].size())
	    {
		int left = d[i + 1][j].first;
		int use = d[i + 1][j].second;
		if (left <= 0)
		    min_swap(res, use + min_coin(-left));
	    }
	}
	printf("%d\n", res);
    }
}

Measured memory_bytes: 1052
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

count = 0
move = []
for w_i in range(w-1):
    for h_i in range(h):
        if a[h_i][w_i] % 2:
            a[h_i][w_i] -= 1
            a[h_i][w_i+1] += 1
            count += 1
            move.append([h_i+1, w_i+1, h_i+1, w_i+2])

for h_i in range(h-1):
    if a[h_i][w-1] % 2:
        a[h_i][w-1] -= 1
        a[h_i+1][w-1] += 1
        count += 1
        move.append([h_i+1, w, h_i+2, w])

print(count)
for i in range(len(move)):
    print(*move[i])


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

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    bool alice,bob;
    alice=bob=false;
    int time=0;
    for(int i=0;i<=100;++i){
        if(i==a) alice=true;
        if(i==c) bob=true;
        if(alice && bob) time++;
        if(i==b) alice=false;
        if(i==d) bob=false;
    }
    if(time!=0) time--;
    cout<<time<<endl;
    return 0;
}

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

#define LL long long
LL n,ans=0,freq[100100],a[100100],bil;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>bil;
        freq[bil]++;
    }
    for(int i=1;i<=100000;i++){
        ans=max(ans,freq[i]+freq[i+1]+freq[i-1]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4392
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  string s;std::cin >> s;
  ll n = s.size();
  ll l = 0, r = n;
  while(r-l>1){
    bool f = false;
    ll mid = (l+r)/2;
    for(int i=0;i<2;i++){
      ll a = i, b = mid;
      if(a%2!=b%2) b--;
      for(int j=0;j<n;j++){
        if(s[j]=='1') a++, b++;
        else if(s[j]=='0') a--, b--;
        else a--, b++;

        if(a<0) a+=2;
        if(b>mid) b-=2;
        if(b<a) goto nxt;
      }
      f = true;
      nxt:;
    }
    if(f) r = mid;
    else l = mid;
  }
  std::cout << r << '\n';
  return 0;
}


Measured memory_bytes: 4568
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    for(int i=0;i<N;i++){
      A[i] = sc.nextInt();
    }
    Arrays.sort(A);
    int c = A[0];
    int count = 0;
    int ans =0;
    for(int i=0;i<N;i++){
      if(c==A[i]){
        count++;
      }else{
        c = A[i];
        if(count%2==1){
          ans++;
        }
        count=1;
      }
    }
    if(count%2==1){
      ans++;
    }
     System.out.println(ans);
  }
}

Measured memory_bytes: 59468
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i) = 0; (i) <(n); (i)++) 
#define so(v) sort(v.begin(),v.end())
using ll = long long;
using vi=vector<int>;
using vii=vector<vi>;
const int MAX = 510000;
const int MOD = 1000000007;
ll gcd(ll a, ll b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long com(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
  int n,k;cin>>n>>k;
  double p[n];
  rep(i,n){
      cin>>p[i];
  }
  double kk=0;
  double m=0;
  rep(i,k){
      kk+=(p[i]+1)/2;
  }
  m=kk;
  for(int i=k;i<n;i++){
      kk=kk-(p[i-k]+1)/2+(p[i]+1)/2;
      m=max(m,kk);
  }
  cout<<std::fixed << std::setprecision(15) <<m<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
#define rrep(i,n) for(int i = n-1; i >= 0 ; i--)
typedef long long ll;
constexpr auto INFI = 2147483647;
const ll INFL = 9223372036854775807;

int main(){
    ll number;
    cin >> number;
    vector<char> ans;
    while (number != 0) {
        number--;
        ans.push_back((char)('a' + number%26));
        number /= 26;
    }

    for(int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }
    cout << endl;

  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 2e3 +5;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

LL dp[MAXN][MAXN];

int main(){
  fio();
  int n; cin>>n;
  vector<pair<LL,LL> > v(n+1);
  v[0].fi = 1e18;
  for1(i,n){
	cin>>v[i].fi;
	v[i].se = i;
	}
  sort(v.begin(),v.end(),greater<pair<LL,LL> >());

  for1(i,n){
  	auto u = v[i];
  //	cout<<u.fi<<" ";
  	for(LL j = 0; j<i; j++){
  		LL l = j;
  		LL r = (i-1-j);
  		dp[l+1][r] = max(dp[l+1][r],dp[l][r] + abs(l+1-u.se)*u.fi);
  		dp[l][r+1] = max(dp[l][r+1],dp[l][r] + abs(n- r -u.se)*u.fi);
  	}
  }
 // cout<<endl;
  LL an = 0;
  forn(i,n+1)  an = max(an, dp[i][n-i]);
  cout<<an<<endl;
  return 0;
}


Measured memory_bytes: 26348
#include <iostream>
using namespace std;
int main(){


    int arr[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K;
    cin >> K;
    cout << arr[K - 1];
    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 FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

struct UnionFind
{
    vector<int> d;
    UnionFind(int n = 0) : d(n, -1) {}
    int find(int x)
    {
        if (d[x] < 0)
            return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (d[x] > d[y])
            swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};

int main()
{
    long long N, M;
    cin >> N >> M;
    vector<pair<int, int>> bridges(M);
    rep(i, M)
    {
        cin >> bridges[i].first >> bridges[i].second;
        bridges[i].first--;
        bridges[i].second--;
    }
    REVERSE(bridges);
    UnionFind uf(N);
    vector<long long> ans(M, 0);
    ans[0] = (N - 1) * N;
    rep(i, M - 1)
    {
        int a = bridges[i].first, b = bridges[i].second;
        if (uf.same(a, b))
        {
            ans[i + 1] = ans[i];
        }
        else
        {
            long long sa = uf.size(a), sb = uf.size(b);
            ans[i + 1] = ans[i] - sa * (N - sa) - sb * (N - sb) + (sa + sb) * (N - (sa + sb));
        }
        uf.unite(a, b);
    }
    REVERSE(ans);
    rep(i, M)
    {
        cout << ans[i] / 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 3328
k = int(input())
l = set()


def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    m = int(lunnum[-1])
    if (flag):
        for i in range(0, 10):
            construct(lunnum+str(i), depth-1, i == 0)
    elif (m == 0):
        for i in sorted([m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)
    elif (m == 9):
        for i in sorted([(m - 1) % 10, m]):
            construct(lunnum + str(i), depth - 1, False)
    else:
        for i in sorted([(m - 1) % 10, m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)


construct("0", 10, True)
ls = list(l)
ls.sort()
print(ls[k])


Measured memory_bytes: 72900
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using pq = priority_queue<int>;
template<class T>
using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int under = (1 << 31);
int upper = under - 1;
ll UNDER = (1LL << 63);
ll UPPER = UNDER - 1;
const int MOD = 1e9 + 7;
const long double pi = 3.141592653589793;
int main() {
	int n, k;
	cin >> n >> k;
	V a(n);
	rep(i, n) {
		cin >> a[i];
	}
	ll ans = 0;
	if (n == 1) {
		cout << k << endl;
		return 0;
	}
	rep(i, n - 1) {
		ans += min(k, a[i + 1] - a[i]);
	}
	ans += k;
	cout << ans << endl;
	return 0;
}

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

int main() {
  int n, i, j, k, len = 0, l1, l2, now, tmp;
  string s;
  cin >> n >> s;
  vector<vector<int>> t(26, vector<int>(0));
  for (i = 0; i < n; i++)
    t[s[i]-'a'].push_back(i);
  for (i = 0; i < 26; i++)
    sort(t[i].begin(), t[i].end());
  for (i = 0; i < 26; i++) {
    for (j = 0; j < (int)(t[i].size()-1); j++) {
      for (k = j+1; k < t[i].size(); k++) {
        l1 = t[i][j]; l2 = t[i][k]; now = 0; tmp = len;
        if (l2-l1 <= len) continue;
        if (len > 1 && s.substr(l1, len) != s.substr(l2, len)) continue;
        while (l1+len+now < l2 && l2+len+now < n && s[l1+len+now] == s[l2+len+now]) {
          tmp++; now++;
        }
        len = max(len, tmp);
      }
    }
  }
  cout << len << endl;     
}

Measured memory_bytes: 384
#include <iostream>
#include <bits/stdc++.h>
#define MAX_SIZE 500010
#define INFTY 2000000000
using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k) {
    Node *z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    Node *y = NIL;
    Node *x = root;
    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 preorder(Node* u) {
    if (u == NIL) return;
    cout << " " << u->key;
    preorder(u->left);
    preorder(u->right);
}

void inorder(Node* u) {
    if (u == NIL) return;
    inorder(u->left);
    cout << " " << u->key;
    inorder(u->right);    
}

void postorder(Node* u) {
    if (u == NIL) return;
    postorder(u->left);
    postorder(u->right);
    cout << " " << u->key;
}

void print() {
    inorder(root);
    cout << endl;
    preorder(root);
    cout << endl;
}

int main(){
    int n, k;
    char cmd[10];
    root = NIL;
    cin >> n;
    for (int i=0; i < n; i++) {
        scanf("%s%d\n", cmd, &k);
        // cout << cmd << k << endl;
        if (cmd[0] == 'i') insert(k);
        else if (cmd[0] == 'p') print();
    }
    return 0;
} 


Measured memory_bytes: 26584
const input = require('fs').readFileSync('/dev/stdin', 'utf8');

const list = input.trim().split('\n');
const n = Number(list[0]);
const A = list[1].trim().split(' ');
const q = Number(list[2]);
const mi = list[3].trim().split(' ');

// const dp = {};
// const memo = (i, sum) => {
//   dp[sum] = true;
//   if (i === n) {
//     return;
//   }
//   memo(i + 1, sum);
//   memo(i + 1, sum + Number(A[i]));
// }
// memo(0, 0);

// for (let i = 0; i < q; i++) {
//   console.log(dp[mi[i]] ? 'yes' : 'no');
// }

// const dp = {};
// const memo = (i, m) => {
//   if (m <= 0) {
//     dp[i] = dp[i] || {};
//     return dp[i][m] = m === 0;
//   } 
//   if (i === n) {
//     return false;
//   }

//   dp[i][m] 
//   return memo(i + 1, m) || memo(i + 1, m - Number(A[i]));
// }


class KeyMap {
  constructor() {
    this.map = {};
  }
  get(...args) {
    let map = this.map;
    args.forEach(arg => {
      map[arg] = map[arg] || {};
      map = map[arg];
    });
    return map;
  }
}

const dp = new Map();
const keyMap = new KeyMap();
const memo = (i, m) => {
  if (dp.has(keyMap.get(i, m))) {
    return dp.get(keyMap.get(i, m));
  }
  if (i === n || m === 0) {
    const result = m === 0;
    dp.set(keyMap.get(i, m),result);
    return result;
  }

  const nI = i + 1;
  const nM = m - A[i];
  const result = memo(nI, m) || memo(nI, nM);
  dp.set(keyMap.get(i, m),result);
  return result;
}
for (let i = 0; i < q; i++) {
  console.log(memo(0, Number(mi[i])) ? 'yes' : 'no');
}
// console.log(dp);


Measured memory_bytes: 30248
/* *Your Love Makes me STRONG,
   You'r Hate Makes Me UNSTOPABBLE.*
 
  *HOPE is a good thing,Maybe The BEST of Things.
   And No Good Things Ever Dies.*
  
  *Keep calm,Be patient And Chase Your DREAM*
 12-09-2020-Remember The Date(Div=2)
*/


#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MN7 ios::sync_with_stdio(0);cin.tie(nullptr);
using namespace std;
ll t,n,i,j,k,a,b,c,d,p,q,r,x,y,z,m,cnt,flag;
string s;
void nahid()
{
 cin>>x;
 if(x==0)cout<<1;
 else cout<<0;
 

}
int main()
{ MN7 //cin>>t;while(t--)
  nahid();
}


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

int main(){
  int n,i,k;
  cin>>n;
  for(i=1;i<=46297;i++){
    k=1.08*i;
    if(n==k){
      cout<<i;
      return 0;
    }
  }
  cout<<":(";
}

Measured memory_bytes: 256
#include<stdio.h>
main(void)
{
    int a,b;
 
    scanf("%d %d", &a, &b);
 
    if(a < b){
        printf("a < b\n");
    }
    if(a > b){
        printf("a > b\n");
    }
    if(a==b){
        printf("a == b\n");
    }
     
    return 0;
}

Measured memory_bytes: 580
#include <iostream>
using namespace std;
double V[51];

void swap (double *x, double *y) {
  double temp;

  temp = *x;
  *x = *y;
  *y = temp;
}

void bubble_sort (double array[], int array_size) {
  int i, j;
  for (i = 0; i < array_size - 1; i++){
    for (j = array_size - 1; j >= i + 1; j--){
      if (array[j] < array[j-1]) { swap(&array[j], &array[j-1]); }
    }
  }
}

int main() {
	int N;
	cin >> N;
	for(int k = 0; k < N; k++){
		cin >> V[k];
	}
	bubble_sort(V, N);

	for(int i = 1; i < N; i++){
		double temp = 0;
		temp = V[i];
		V[i] = (temp + V[i-1]) / 2;
	}
	cout << V[N-1];
	return 0;
}

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

#define ii pair<int, int>
#define lli long long int
#define ll pair<lli, lli>
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

int main() {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if (a + b + c > 21)
		puts("bust");
	else
		puts("win");
	return 0;
}

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

int main() {
  string s, t;
  cin >> s >> t;
  bool flag=true;
  int k=s.size();
  for (int i=0; i<k; i++){
    if (s.at(i)!=t.at(i)){
      flag=false;
      break;
    }
  }
  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;

#define fi first
#define se second
typedef long long LL;
typedef long double LD;

int N,K,a[5010]; bool dp[5010][5010];

bool check(int ind){
    if (a[ind]>=K) return 1;
    memset(dp,0,sizeof(dp));

    int i,j;
    dp[0][0]=1;
    for (i=1; i<=N; i++){
        dp[i][0]=1;
        for (j=1; j<=K; j++){
            dp[i][j]=dp[i-1][j];
            if (a[i]<=j && i!=ind) dp[i][j]|=dp[i-1][j-a[i]];
        }
    }

    for (i=K-1; i>=K-a[ind]; i--)
        if (dp[N][i]) return 1;
    return 0;
}

int main(){
    cin >> N >> K;

    int i;
    for (i=1; i<=N; i++) cin >> a[i];

    sort(a+1,a+N+1);

    int l=1,r=N,mid;
    if (check(1)){ cout << 0 << "\n"; return 0; }

    while (l<r){
        mid=(l+r+1)/2;
        if (!check(mid)) l=mid;
        else r=mid-1;
    }

    cout << l << "\n";
    return 0;
}


Measured memory_bytes: 24832
#include <bits/stdc++.h>
#define ll  long long int
#define ull unsigned long long int 
#define pb  push_back
#define mp  make_pair
#define pii pair<int, int>
using namespace std;

const ll mod = 1e9+7;
const int infi = 2e9;
const int N = 1e5;
int n, k;
int arr[N+1] = {0};

int dp[N+1] = {0};
bool check[N+1] = {0};

int dp_recurse(int ind){

	if(check[ind] == 1){
		return dp[ind];
	}

	if(ind == n-1){
		return 0;
	}

	int mini = infi;

	for(int i=ind+1;i<min(n, ind+k+1);i++){
		mini = min(mini, abs(arr[ind]-arr[i]) + dp_recurse(i)); 
	}

	dp[ind] = mini;
	check[ind] = 1;

	return dp[ind];

}

void solve(){
    //solve here//		
	cin >> n >> k;

	for(int i=0;i<n;i++){
		cin >> arr[i];
	}

	cout << dp_recurse(0) << endl;
}


int main(){
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
    }
}



Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int A, B; cin >> A >> B;
    for (int i = 0 ; i < 3000 ; i++) {
        if (i * 8 / 100 == A && i / 10 == B) {
            cout << i << '\n';
            exit(0);
        }
    }
    cout << -1 << '\n';
}


Measured memory_bytes: 256
N = int(input())
C0 = C1 = C2 = C3 = 0
for i in range(N):
    test = input()
    if test == 'AC':
        C0 += 1
    elif test == 'WA':
        C1 += 1
    elif test == 'TLE':
        C2 += 1
    else:
        C3 += 1
print('AC x ' + str(C0))
print('WA x ' + str(C1))
print('TLE x ' + str(C2))
print('RE x ' + str(C3))

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int dp[101][100001];
signed main(){
	int n,k;
	cin>>n>>k;
	int W[n],V[n];
	for(int i=0;i<n;i++)
	{
		cin>>W[i]>>V[i];
	}
	int ans=0;
	for(int i=0;i<n+1;i++)
	{
		for(int j=0;j<100001;j++)
		{
			if(j==0)
				dp[i][j]=0;
			else if(i==0)
				dp[i][j]=INT_MAX;
			else if(V[i-1]>j)
				dp[i][j]=dp[i-1][j];
			else{
				dp[i][j]=min(W[i-1]+dp[i-1][j-V[i-1]],dp[i-1][j]);
			}
			if(dp[i][j]<=k)ans=max(ans,j);
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 79104
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a, b,c,i=0;

		String[] spl = br.readLine().split(" ");
		a = Integer.parseInt(spl[0]);
		b = Integer.parseInt(spl[1]);
		c = Integer.parseInt(spl[2]);
		for (int j = a; j <=b; j++) {

			if(c%j==0)i++;
		}

		System.out.println(i);
	}
}

Measured memory_bytes: 24368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int N;

int main(void) {

    cin >> N;

    bool result = true;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if (a % 2 == 0 && (a % 3 != 0 && a % 5 != 0)) {
            result = false;
            break;
        }
    }

    if (result) {
        cout << "APPROVED" << endl;
    }
    else {
        cout << "DENIED" << endl;
    }


    return 0;
}

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

int main() {
  string S, T;
  cin >> S >> T;
  
  int ans = 0;
  
  for (int i = 0; i < S.size(); i++) {
    if (S[i] != T[i]) ans++;
  }
  
  
  cout << ans << endl;
}

Measured memory_bytes: 3916
//#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>


//using namespace std;

int main()
{

////    freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);


    char str[1100];
    char str2[1000];
    int i, j, w;

    while(gets(str))
//    while(scanf("%s",str))
    {
        scanf("%d", &w);
        int len ;
        len = strlen(str);

        for( i=0, j=0; i<=len-1; i = i+w, j++ )
        {
            str2[j] = str[i];
        }

        for( i=0; i<j; i++ )
        {
            printf("%c", str2[i]);
        }
        printf("\n");

    }

    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF 1e9
#define eps 1e-6
typedef long long ll;
using namespace std;

int a[4], k, ans;

void dfs(int x){
	if(x == k){
		if(a[1] < a[2] && a[2] < a[3]){
			puts("Yes");
			exit(0);
		}
		return;
	}
	for(int i = 1; i <= 3; i++){
		a[i] *= 2;
		dfs(x + 1);
		a[i] /= 2;
	}
}

int main(){

	cin >> a[1] >> a[2] >> a[3] >> k;
	dfs(0);
	puts("No");
	
	return 0;
}


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

a = [s]
ans = 1
while True:
    if s % 2 == 0:
        s = s / 2
    else:
        s = 3 * s + 1
    
    ans += 1

    if a.count(s) == 1:
        print(ans)
        exit()
    else:
        a.append(s)


Measured memory_bytes: 2940
from collections import*
e=defaultdict(list)
d=defaultdict(list)
for k,v in enumerate(input()):
    e[v].append(k)
for k,v in enumerate(input()):
    d[v].append(k)
if set(map(tuple,e.values()))==set(map(tuple,d.values())):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 23472
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int maxn=0x7fffff;
string a,b;
int main(){
	int lena,lenb,i;
	cin>>a>>b;
	lena=a.size()-1;
	lenb=b.size()-1;
	if(lena<lenb){
		cout<<"LESS";
		return 0;
	}
	if(lena>lenb){
		cout<<"GREATER";
		return 0;
	}
	else{
		for(i=0;i<=lena;i++){
			if(a[i]<b[i]){
				cout<<"LESS";
				return 0;
			}
			if(a[i]>b[i]){
				cout<<"GREATER";
				return 0;
			}
		}
	}
	cout<<"EQUAL";
	return 0;
}

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


int main(){
  int H, W, i, j;
  cin >> H >> W;
  char a[H+2][W+2];
  
  for(i = 0; i < H+2; i++){
    for(j = 0; j < W+2; j++){
      a[i][j] ='#';
    }
  }
  for(i = 1; i < H+1; i++){
    for(j = 1; j < W+1; j++){
      cin >> a[i][j];
    }
  }
  for(i = 0; i < H+2; i++){
    for(j = 0; j < W+2; j++){
      cout <<  a[i][j];
    }
    cout << endl;
  }
 
}


Measured memory_bytes: 256
def trial_division(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n /= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n /= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def gcd(x, y):
    if x > y:
        return gcd(y, x)
    # x <= y
    temp = y % x
    if temp == 0:
        return x
    else:
        return gcd(temp, x)


def main():
    a, b = map(int, input().split())
    gcd_ab = gcd(a, b)
    temp_list = trial_division(gcd_ab)
    # print(gcd_ab)
    # print(temp_list)
    temp_set = set(temp_list)
    print(len(temp_set))


if __name__ == '__main__':
    main()
    

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <iomanip>

using namespace std;
typedef long long ll;
const int maxn=1e5+1111;

int arr[maxn];
int dp[maxn];
int main(){
    int n,k;
    scanf("%d",&n);
    dp[1]=0;k=2;
    for(int i=1;i<=n;++i){
        scanf("%d",arr+i);
        if(i>=2&&i<=k){
            dp[i]=abs(arr[i]-arr[1]);
            for(int j=2;j<i;++j){
                dp[i]=min(abs(arr[i]-arr[j]),dp[i]);
            }
        }
        if(i>k){
            dp[i]=dp[i-k]+abs(arr[i]-arr[i-k]);
            for(int j=1;j<k;++j){
                dp[i]=min(dp[i-j]+abs(arr[i]-arr[i-j]),dp[i]);
            }
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}

Measured memory_bytes: 1024
// È¥°É£¡Æ¤¿¨Çð! °ÑAC´ø»ØÀ´£¡
//      ¤Ø¡¡¡¡¡¡¡¡¡¡£¯|
// ¡¡¡¡/£Ü7¡¡¡¡¡¡ ¡Ï£ß/
// ¡¡ /¡¡©¦¡¡¡¡ £¯¡¡£¯								AC		AC		AC		AC
//    ©¦¡¡Z £ß,£¼¡¡£¯¡¡¡¡ /`©c						AC		AC		AC		AC
//    ©¦¡¡¡¡¡¡¡¡¡¡©c¡¡¡¡ /¡¡¡¡¡µ					AC		AC		AC		AC
// ¡¡Y¡¡¡¡¡¡¡¡¡¡`¡¡ /¡¡¡¡/  /						AC		AC		AC		AC
// ¡¡Øé¡ñ¡¡.¡¡¡ñ¡¡¡¡¡´¡¡/¡¡/						AC		AC		AC		AC
// ¡¡()¡¡ ¤Ø¡¡¡¡¡¡¡¡|¡¡£Ü¡´							AC		AC		AC		AC
// ¡¡¡¡>- ._¡¡ ¥£¡¡ ©¦ £¯£¯							AC		AC		AC		AC
// ¡¡ / ¤Ø¡¡¡¡ /¡¡/£¼| £Ü£Ü							AC		AC		AC		AC
// ¡¡ ©c_/¡¡¡¡(_£¯¡¡ ©¦£¯£¯							AC		AC		AC		AC
// ¡¡¡¡ 7¡¡¡¡¡¡¡¡¡¡¡¡¡¡|£¯							AC		AC		AC		AC
// ¡¡¡¡ £¾¨Dr£þ£þ`-¨D£ß/							AC		AC		AC		AC
//**************************************Accepted*****************************************//

#include<bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define Unique(x) x.erase(unique(all(x)),x.end());

using namespace std;

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

const int Days[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};

inline int read()
{
	#define gc getchar
	int ans=0;
	bool f=1;
	char ch=gc();
	
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	
	return f?ans:-ans;
	
	#undef gc
}

typedef long long ll;

#define MOD 1000000007

ll a[200010];
ll ans;

int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	
	int n;cin>>n;
	
	ll sum=0ll;
	
	for(int i=0;i<n;i++)cin>>a[i];
	
	for(int i=0;i<n;i++)sum=(sum+a[i])%MOD;
	
	for(int i=0;i<n;i++)
	{
		sum=(sum-a[i]+MOD)%MOD;
		
		ans=(ans+(a[i]*sum)%MOD)%MOD;
	}
	
	cout<<ans%MOD;
	
	//printf("Time used = %.12f",(double)(clock())/CLOCKS_PER_SEC);
	return 0;
}

/*  GOD BLESS  */


Measured memory_bytes: 5200
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,min=100,max=1,ans=1000000;
  vector<int> vec(100);
  
  cin>>n;
  
  for(int i=0;i<n;i++){
    int x;
    cin >> x;
    vec.at(i)=x;
    if(x<min) min=x;
    if(x>max) max=x;
  }
  
  for(int j=min;j<max+1;j++){
    int sum=0;
    for(int i=0;i<n;i++){
      sum +=(j-vec.at(i))*(j-vec.at(i));
    }
    if(sum<ans){
      ans=sum;
    }
  }
  
  cout << ans <<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>

using namespace std;

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

vector<int> res[1000];

int main(){
    int N;
    cin >> N;
    int k = 1;
    int ok = false;
    while(k*(k-1) <= 2*N){
        if(k*(k-1) == 2*N){
            ok = true;
            break;
        }
        else{
            k++;
        }
    }

    int num = k-1;
    if(ok){
        int count[1000];
        for(int i = 0; i < 1000; i++){
            count[i] = 0;
        }
        for(int i = 0; i < num; i++){
            res[0].push_back(i);
        }
        int ne = num;
        for(int i = 1; i < k; i++){
            for(int j = 0; j < num-i; j++) {
                res[i].push_back(ne);
                ne++;
            }
            for(int j = 0; j < i; j++){
                res[i].push_back(res[j][count[j]]);
                count[j]++;
            }
        }

        cout << "Yes" << endl;
        cout << k << endl;
        for(int i = 0; i < k; i++){
            cout << num << " ";
            for(int j = 0; j < num; j++){
                cout << res[i][j]+1 << " ";
            }
            cout << endl;
        }
    }
    else{
        cout << "No" << endl;
    }




    return 0;

}



Measured memory_bytes: 2304
def main():
    n = int(input())
    S = input()
    l, r = 0, S.count('.')
    ans = l + r
    for i in range(n):
        if S[i] == '#': l += 1
        else: r -= 1
        ans = min(ans, l + r)
    print(ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 9416
Keys=list(map(int,input().split()))
if Keys[0]>=2 and Keys[1]>=2:
    print(Keys[0]*Keys[1]-2*(Keys[0]+Keys[1]-2))
elif Keys[0]==1 and Keys[1]==1 :
    print(1)
else:
    print(max(Keys[0],Keys[1])-2)

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
    int N,i,j,temp,mini;
    int c=0;
    scanf("%d",&N);
    int a[N];

    for(i=0;i<N;i++)
        scanf("%d",&a[i]);
 for(i=0;i<N;i++)
 {
           mini = i;
           if(mini != i)
           {

            temp=a[i];
            a[i]=a[mini];
            a[mini]=temp;

            c++;
           }
     for (j=i;j<N;j++)
     {
         if (a[j] < a[mini])
         {
            mini = j;
         }
     }
      if(mini != i)
           {

            temp=a[i];
            a[i]=a[mini];
            a[mini]=temp;

            c++;
           }
 }
   for(i=0;i<N-1;i++)
    printf("%d ",a[i]);
    printf("%d",a[N-1]);
    printf("\n%d\n",c);
    return 0;


}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int k;
  cin >> k;

  int res = 7%k;
  int ans = 1;

  vi sn(k);

  while (res != 0 and not sn[res]) {
    sn[res] = 1;
    res = (res*10 + 7)%k;
    ++ans;
  }

  if (res != 0) ans = -1;
  cout << ans << '\n';

}

Measured memory_bytes: 7184
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  if(a == b) cout << 'H' << endl;
  else cout << 'D' << endl;
  
  return 0;
}

Measured memory_bytes: 256
using System;

namespace Abc138
{
    public class QuestionB
    {
        public static void Main(string[] args)
        {
            // 整数の入力
            int n = int.Parse(Console.ReadLine());

            // スペース区切りの整数の入力
            string[] input = Console.ReadLine().Split(' ');

            double result = 0;
            foreach(var i in input)
            {
                result += 1.0 / int.Parse(i);
            }

            Console.WriteLine(1/result);
        }
    }
}


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

#define int long long

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

/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/

signed main() {
    int N;
    set<char> s;
    cin >> N;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        s.insert(c);
    }
    if (s.size() == 3) {
        cout << "Three" << endl;
    } else {
        cout << "Four" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int BASE = 1e9 + 7;

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

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

  int open = 0;
  long long ans = 1;
  for (int i = 0; i < n * 2; i++)
    if ((s[i] == 'B') ^ (open % 2)) open++;
    else ans = ans * (open--) % BASE;

  for (int i = 2; i <= n; i++)
    ans = ans * i % BASE;

  cout << (open ? 0 : ans) << endl;
}


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

int main(void){
    int d;
    cin >> d;
    if(d==25) cout << "Christmas" << endl;
    else if(d==24) cout << "Christmas Eve" << endl;
    else if(d==23) cout << "Christmas Eve Eve" << endl;
    else cout << "Christmas Eve Eve Eve" << endl;
}

Measured memory_bytes: 256
N = int(input())
ans = set(["3","5","7"])
list = ["3","5","7"]
x_list = ["3","5","7"]
cnt = 0
f = 0
i = 0

while f == 0:
    for j in range(3):
        num = x_list[i] + list[j]
        if int(num) > N:
            f = 1
            break
        x_list.append(num) 
    i += 1

for i in x_list:
    ans_list = [i for i in str(i)]
    s = set(ans_list)
    if s == ans:
        cnt += 1

print(cnt)


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


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M, K;
    cin >> M >> K;
    if(M == 0) {
        if(K == 0) cout << "0 0" << endl;
        else cout << -1 << endl;
        return 0;
    }
    if(M == 1)  {
        if(K == 0) cout << "0 0 1 1" << endl;
        else cout << -1 << endl;
        return 0;
    }
    int upper = (1 << M) - 1;
    if(upper < K) {
        cout << -1 << endl;
        return 0;
    }
    if(K == 0) {
        RREP(i, upper, 0) {
            if(i != upper) cout << " ";
            cout << i;
        }
        REP(i, 0, upper) {
            cout << " " << i;
        }
        return 0;
    }
    cout << "0 " << K << " 0";
    RREP(i, upper, 1) {
        if(i != K) {
            cout << " " << i;
        }
    }
    cout << " " << K;
    REP(i, 1, upper) {
        if(i != K) {
            cout << " " << i;
        }
    }
    cout << endl;


    


    return 0;
}
// 1 0: {0, 0, 1, 1}
// 1 1: x
// 2 0: {0, 1, 0, 3, 2, 1, 2, 3}
// 2 1: {0, 3, 1, 3, 2, 1}
// 3 7: {0, 7, 0, }


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


int main(){
    int a ,b,c,d;
    cin >> a >> b >> c >> d;
    bool ok = true;
    while(ok){
        c -= b;
        if(c <= 0){
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if(a <= 0){
            cout << "No" << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h> 
using namespace std;   
using ll = long long;
//const int INF = 1e9 + 5;
int main() 
{ 
	int n; cin >> n;
	vector<int > dp(3);
	for(int day = 0; day < n; ++day) {
		vector<int > new_dp(3,0);
		vector<int > c(3);
		for(int i = 0; i < 3; i++) {
			cin >> c[i];
		}	
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(i != j) {
					new_dp[j] = max(new_dp[j], dp[i] + c[j]);
				}
			}
		}
		dp = new_dp;
	}
	cout << max({dp[0], dp[1], dp[2]});
    return 0; 
} 

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

int main(){
  int n;
  cin >> n;

  int count = 0;
  int check;
  string str;

  for (size_t i = 1; i <= n; i++) {
    str = to_string(i);
    check = str.size();
    if(check % 2 != 0){
      count++;
    }
  }

  cout << count <<endl;

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
	int a[100];
	for(int i=0; i<N; i++) cin >> a[i];
 
	int res = 1000000000;
	int tot;
	for(int b=-100; b<=100; b++){
		tot = 0;
		for(int i=0; i<N; i++) tot += (a[i]-b)*(a[i]-b);
		res = min(res, tot);
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

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

using ll = long long int;
using pll = pair<ll, ll>;

const ll MAXN = 100002;
ll dp[MAXN];

const ll mod = 1000000007;

int main()
{
    ll N, M;
    cin >> N >> M;

    rep (i, M)
    {
        ll a;
        cin >> a;

        dp[a] = -1;
    }


    dp[0] = 1;

    rep(i, N) if (dp[i] != -1)
    {
        if (dp[i + 1] != -1)
        {
            dp[i + 1] += dp[i];
            dp[i + 1] %= mod;
        }

        if (dp[i + 2] != -1)
        {
            dp[i + 2] += dp[i];
            dp[i + 2] %= mod;
        }
    }

    cout << dp[N] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

const int N = 1234567;

int a[N], pos[N], pr[N], ne[N];

int main () {
  int n;
  std::cin >> n;
  for (int i = 0; i <= n; ++i) {
    std::cin >> a[i];
    pos[a[i]] = i;
    pr[i] = i - 1;
    ne[i] = i + 1;
  }
  long long ans = 0;
  for (int i = n; i>= 1; --i) {
    int j = pos[i];
    ans += i * 1LL * (j - pr[j]) * (ne[j] - j);
    pr[ne[j]] = pr[j];
    ne[pr[j]] = ne[j];
  }
  std::cout << ans << std::endl;
}


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

int main()
{
	int n, i, a, b;
	int l = 0, r = 0; 
	string s;
	
	cin >> n;
	cin >> s;

	for (i = 0; i < n; i++){
		if (s[i] == '('){
			l += 1;
		} else if (s[i] == ')' &&  l > 0){
			l -= 1;
		} else {
			r += 1;;
		}
	}

	for (a = 0; a < l; a++){
		s = s + ')';
	}
	for (b = 0; b < r; b++){
		s = '(' + s;
	} 

	cout << s << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)

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

int main() {

	int H,W,K;
	cin >> H >> W >> K;
	vector<string> G(H);
	rep(i,H) {
		cin >> G[i];
	}
	int mini = 1e9;
	rep(i,(1<<(H-1))) {
		vector<int> grp(H);
		grp[0] = 0;
		int N = 1;
		rep(j,H-1) {
			if(!((i >> j)&1)) grp[j+1] = grp[j];
			else {
				grp[j+1] = grp[j]+1;
				N++;
			}
		}
		vector<int> nums(N, 0);
		bool gok = true;
		int M = 0;
		rep(j, W) {
			bool ok = true;
			vector<int> one(N, 0);
			rep(k, H) {
				if(G[k][j] == '1') {
					one[grp[k]]++;
					nums[grp[k]]++;
					if(nums[grp[k]] > K) ok = false;
					if(one[grp[k]] > K) gok = false;
				}
			}
			if(!ok) {
				nums = one;
				M++;
			}
		}
		if(gok) chmin(mini, N-1+M);
	}
		//cout << std::bitset<10>(i) << endl;
	cout << mini << endl;
	
  return 0;
}


Measured memory_bytes: 256
import java.util.*;


public class Main {
	public static void main(String[] args) {
		try {
			Scanner sc = new Scanner(System.in);
			while(true){
				int w = sc.nextInt(), h = sc.nextInt();

				if(w==0&&h==0){
					sc.close();
					break;
				}

				int[][] f = new int[h][w];
				int ch = 0, cw = 0;

				for(int i=0;i<h;i++){
					for(int j=0;j<w;j++){
						f[i][j] = sc.nextInt();
						if(f[i][j]==2){
							ch = i;
							cw = j;
						}
					}
				}

				int ret = solve(f,ch,cw,1,11);
				
				System.out.println((ret>10)?-1:ret);
			}
			sc.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int solve(int[][] f, int ch, int cw, int n, int min){
		if(n>10||n>min) return 11;
		int ret = 11;
		
		//up
		if(ch>=1&&f[ch-1][cw]!=1){
			int i = ch-1, j = cw;
			while(true){
				if(i<0){
					ret = 11;
					break;
				} else if(f[i][j]==1){
					f[i][j] = 0;
					ret = solve(f,i+1,j,n+1,min);
					f[i][j] = 1;
					break; 
				} else if(f[i][j]==3){
					ret = n;
					break;
				}
				i--;
			}
		}
		if(ret<min) min = ret;

		//right
		if(cw<f[0].length-1&&f[ch][cw+1]!=1){
			int i = ch, j = cw+1;
			while(true){
				if(j>=f[0].length){
					ret = 11;
					break;
				} else if(f[i][j]==1){
					f[i][j] = 0;
					ret = solve(f,i,j-1,n+1,min);
					f[i][j] = 1;
					break;
				} else if(f[i][j]==3){
					ret = n;
					break;
				}
				j++;
			}
		}
		if(ret<min) min = ret;


		//down
		if(ch<f.length-1&&f[ch+1][cw]!=1){
			int i = ch+1, j = cw;
			while(true){
				if(i>=f.length){
					ret = 11;
					break;
				} else if(f[i][j]==1){
					f[i][j] = 0;
					ret = solve(f,i-1,j,n+1,min);
					f[i][j] = 1;
					break;
				} else if(f[i][j]==3){
					ret = n;
					break;
				}
				i++;
			}
		}
		if(ret<min) min = ret;


		//left
		if(cw>0&&f[ch][cw-1]!=1){
			int i = ch, j = cw-1;
			while(true){
				if(j<0){
					ret = 11;
					break;
				} else if(f[i][j]==1){
					f[i][j] = 0;
					ret = solve(f,i,j+1,n+1,min);
					f[i][j] = 1;
					break;
				} else if(f[i][j]==3){
					ret = n;
					break;
				}
				j--;
			}
		}
		if(ret<min) min = ret;

		return min;
	}
}

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b; cin>>a>>b;
    string ans;
    if(a<=0&&b>=0) ans = "Zero";
    else if(a<0&&abs(-a-b)%2==0) ans = "Negative";
    else ans = "Positive";
    print(ans);
    return 0;
}

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

int main(){
  int n;
  int a[100];

  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a,a+n);
  cout<<abs(a[0]-a[n-1])<<endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define sz(x) ((ll)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

int main() {
  int M1, D1;
  cin >> M1 >> D1;
  int M2, D2;
  cin >> M2 >> D2;

  if (M1 == M2) {
    if (D1 + 1 == D2)
      cout << 0 << endl;
    else
      cout << 1 << endl;
  } else {
    cout << 1 << endl;
  }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (H, W) = readLine()!!.split(" ").map(String::toInt)
    if (H % 3 == 0 || W % 3 == 0) {
        println(0)
    } else {
        val result = split(H, W, 3)
        println(result.max()!! - result.min()!!)
    }
}

private fun split(h: Int, w: Int, n: Int): MutableList<Long> {
    if (n == 1) {
        return mutableListOf(h * w.toLong())
    }
    val a = calc(h, w, n)
    val b = calc(w, h, n)
    return if (a.max()!! - a.min()!! < b.max()!! - b.min()!!) a else b
}

private fun calc(h: Int, w: Int, n: Int): MutableList<Long> {
    val length = Math.round(h / n.toDouble()).toInt()
    val result = split(h - length, w, n - 1)
    result.add(length.toLong() * w)
    return result
}


Measured memory_bytes: 37924
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

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

  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  for (auto &x: h) cin >> x;

  vector<int> dp(N+2);
  dp[1] = abs(h[1] - h[0]);
  for (int i = 2; i < N; i++) {
    int minimum = 1000000007;
    for (int j = i - K; j < i; j++) {
      if (j < 0) continue;
      int x = dp[j] + abs(h[i] - h[j]);
      if (x < minimum) minimum = x;
    }
    dp[i] = minimum;
  }

  cout << dp[N-1] << endl;
  return 0;
}


Measured memory_bytes: 1024