akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long Int;

Int cnt[108000];
string s;
Int n, l;
vector<Int> trees;
Int grundy;
class Trie{
public: 
	Trie* child[2];
	Trie(){
		child[0] = child[1] = 0;
	}
};

Trie t;

void dfs(Trie *t, Int d){
	if(t == 0){
		trees.push_back(d);
	}
	else{
		dfs(t->child[0], d+1);
		dfs(t->child[1], d+1);
	}
}

int main(){
	cin >> n >> l;
	for(Int i = 0;i < n;i++){
		cin >> s;
		Trie *now = &t;
		for(Int j = 0;j < s.size();j++){
			Int nxt = s[j] - '0';
			if(now->child[nxt] == 0){
				now->child[nxt] = new Trie();
			}
			now = now->child[nxt];
		}
	}
	dfs(&t, 0);

	for(Int i = 0;i < trees.size();i++){
		if(trees[i] > l)continue;
		Int x = l - trees[i] + 1;
		grundy ^= x & -x;
	}
	if(grundy != 0)cout << "Alice" << endl;
	else cout << "Bob" << endl;
	return 0;
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

int bubbleSort(vector<int> &A, int N){
    int flag = 1;   // 逆の隣接要素が存在する
    int count = 0;  // 本来不要
    while(flag){
        flag = 0;
        for(int i=N-1; i>=0; i--){
            if(A[i] < A[i-1]){
                swap(A[i], A[i-1]);
                flag = 1;
                count += 1; // 本来不要
            }
        }
    }
    return count;   // 本来不要
}

int selectionSort(vector<int> &A, int N){
    int count = 0;  // 本来不要
    for(int i=0; i<N; i++){
        int minj = i;
        for(int j=i+1; j<N; j++){
            if(A[j] < A[minj]) minj = j;
        }
        if(i != minj) count += 1;   // 本来不要
        swap(A[i], A[minj]);
    }
    return count;   // 本来不要
}

int main()
{
    int N; cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        int Ai; cin >> Ai;
        A[i] = Ai;
    }
    int count = selectionSort(A, N);
    for(int i=0; i<N; i++){
        cout << A[i];
        if(i != N-1) cout << " ";
    }
    cout << endl;
    cout << count << endl;
}   


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

int main() {
  string N ;
  cin >> N;
  
if (N[0] == N[1] && N[1] == N[2] || N[1] == N[2] && N[2] == N[3]  ) {
cout << "Yes" << endl;
}
else   {
 cout << "No" << endl;
}


return 0;
}




Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e18);
const ll mod = ll(1e9+7);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")
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 dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b){
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b & 1LL) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

//modの値の確認をすること
int main(){
    ll a,b,c,d,k;
    cin >> a >> b >> c >> d >> k;
    ll x = a * 60 + b,y = c * 60 + d;
    pf(y - x - k);
    return 0;
}


Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
typedef pair<int, int> P;
typedef pair<int, int> R1;
typedef pair<P, R1> R2;
struct RMQ {
	P *data;
	int size;
	RMQ(int n) {
		size = 1;
		while (size < n) size *= 2;
		data = new P[size * 2 - 1];
		for (int i = 0; i < size * 2 - 1; i++) data[i] = P(1 << 30, -1);
	}
	void update(int k, P p) {
		k += size - 1;
		data[k] = p;
		while (k > 0) {
			k = (k - 1) / 2;
			data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
		}
	}
	P query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return P(1 << 30, -1);
		if (a <= l && r <= b) return data[k];
		P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};
int p[200000];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> p[i];
	RMQ odd(N), even(N);
	for (int i = 0; i < N; i++) {
		if (i & 1) odd.update(i, P(p[i], i));
		else even.update(i, P(p[i], i));
	}
	P mv = even.query(0, N, 0, 0, odd.size);
	priority_queue<R2, vector<R2>, greater<R2>> Q;
	Q.emplace(mv, R1(0, N));
	vector<int> ans;
	while (!Q.empty()) {
		R2 r = Q.top(); Q.pop();
		ans.push_back(r.first.first);
		P t1, t2;
		if (r.second.first & 1) {
			t1 = even.query(r.first.second, r.second.second, 0, 0, even.size);
		}
		else {
			t1 = odd.query(r.first.second, r.second.second, 0, 0, odd.size);
		}
		ans.push_back(t1.first);
		if (r.second.first < r.first.second) {
			if (r.second.first & 1)  t2 = odd.query(r.second.first, r.first.second, 0, 0, even.size);
			else t2 = even.query(r.second.first, r.first.second, 0, 0, odd.size);
			Q.emplace(t2, R1(r.second.first, r.first.second));
		}
		if (t1.second + 1 < r.second.second) {
			if (t1.second & 1)  t2 = even.query(t1.second + 1, r.second.second, 0, 0, even.size);
			else t2 = odd.query(t1.second + 1, r.second.second, 0, 0, odd.size);
			Q.emplace(t2, R1(t1.second + 1, r.second.second));
		}
		if (r.first.second + 1 < t1.second) {
			if (r.first.second & 1) t2 = even.query(r.first.second + 1, t1.second, 0, 0, even.size);
			else t2 = odd.query(r.first.second + 1, t1.second, 0, 0, odd.size);
			Q.emplace(t2, R1(r.first.second + 1, t1.second));
		}
	}
	cout << ans[0];
	for (int i = 1; i < ans.size(); i++) cout << " " << ans[i];
	cout << endl;
}

Measured memory_bytes: 12020
N = int(input())
A = list(map(int,input().split()))

Amax = max(A)
Amin = min(A)
ans = []
if Amax >= -Amin:
    im = A.index(Amax)+1
    i = 2
    while i <= N:
        if A[i-2] > A[i-1]:
            ans.append(str(im) + " " + str(i))
            A[i-1] += Amax
            if Amax < A[i-1]:
                im = i
                Amax = A[i-1]
        else:
            i += 1
else:
    im = A.index(Amin)+1
    i = N-1
    while i >= 1:
        if A[i-1] > A[i]:
            ans.append(str(im) + " " + str(i))
            A[i-1] += Amin
            if Amin > A[i-1]:
                im = i
                Amin = A[i-1]
        else:
            i -= 1
print(len(ans))
for out in ans:
    print(out)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main(){
    bool prime[1000000];
    int n;
    for(long int i=2;i<1000000;i++){
        bool isprime=true;
        for(long int j=2;j<=sqrt(i);j++){
            if(i%j==0){
                isprime=false;
                break;
            }
        }
        prime[i]=isprime;
    }
    while(cin >> n){
        int cnt = 0;
        for(int i=2;i<=n;i++){
            if(prime[i]) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    rep(i, n) scanf("%d", &a[i]);

    map<int, int> cnt;
    rep(i, n) {
        cnt[a[i]]++;
        cnt[a[i] + 1]++;
        cnt[a[i] - 1]++;
    }

    int ans = 0;
    for (auto x : cnt) {
        ans = max(ans, x.second);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8024
#include<cstdio>
using namespace std;
int main()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(a+b<c+d)
	{
		printf("Right\n");
		return 0;
	}
	if(a+b>c+d)
	{
		printf("Left\n");
		return 0;
	}
	printf("Balanced\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,T;
    cin >> N >> T;
    vector<int> vec(N);
    int i;
    for (i = 0; i < N; i++){
        int C,ti;
        cin >> C >> ti;
        if (ti <= T) vec.at(i) = C;
        else vec.at(i) = 9999;
    }
    int minn = *min_element(vec.begin(),vec.end());
    if (minn == 9999) cout << "TLE" << endl;
    else cout << minn << endl;
}

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

int main() {
    int a,b;
    cin >>a>>b;
    if (a > b) { cout << "a > b" << endl; }
    else if (a < b) { cout << "a < b" << endl; }
    else { cout << "a == b"<<endl; }
    return 0;
}           

Measured memory_bytes: 1160
N = int(input())
A = [[0,1] for _ in range(31)]
a = 1
for i in range(1,31):
    a *= -2
    A[i][0] = A[i-1][0] + min(0,a)
    A[i][1] = A[i-1][1] + max(0,a)
a = 1
for i in range(0,31):
    a *= -2
    A[i][0] += a
    A[i][1] += a
A = [[1,1]] + A
A = A[:32]

def main():
    if N==0:
        return '0'
    s = ''
    n = N
    flg = False
    for i in range(31, -1, -1):
        if A[i][0]<=n and n<=A[i][1]:
            s += '1'
            n -= (-2)**i
            flg = True
        else:
            if flg:
                s += '0'
    return s

print(main())


Measured memory_bytes: 38384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s[k - 1] += 'a' - 'A';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
	string line;
	cin >> line;
	
	int n = line.size();
	
	vector<pair<char, int> > table;
	
	char now = line[0];
	int cnt = 0;
	rep(i, n)
	{
		cnt += now == line[i];
		
		if(now != line[i] || i + 1 == n)
		{
			table.push_back(mp(now, cnt));
			now = line[i];
			cnt = 1;
		}
	}
		
	if(now != line[n-2]) table.push_back(mp(now, 1));
	
	int res = 0;
	REP(i, 1, table.size() - 1)
	{
		if(table[i].first == 'O')
		{
			int num = table[i].second;
			
			if(table[i-1].first == 'J' && num <= table[i-1].second && 
			   table[i+1].first == 'I' && num <= table[i+1].second) chmax(res, num);				
		}
	}
	
	cout << res << endl;
}

Measured memory_bytes: 9520
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int h,w;
int x,y,dir;
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
string mp[101],str="NESW";;
ll n;

void solve(){
  ll dis[4][101][101],cost=0;
  memset(dis,-1,sizeof(dis));

  while(n!=0){
    if(dis[dir][y][x]!=-1&&n%(cost-dis[dir][y][x])!=0){
      n%=(cost-dis[dir][y][x]);
      memset(dis,-1,sizeof(dis));
    }

    dis[dir][y][x]=cost;
    
    x+=dx[dir];
    y+=dy[dir];
    if(x<0||y<0||x>=w||y>=h||mp[y][x]=='#'){
      x-=dx[dir];
      y-=dy[dir];
      dir=(dir+1)%4;
    }
    else n--,cost++;
  }
  cout <<y+1<<" "<<x+1<<" "<<str[dir]<<endl;
}


int main(){
  while(1){
    cin >>h>>w>>n;
    if(!h&&!w&&!n)break;
    for(int i=0;i<h;i++) cin >> mp[i];
    
    for(int i=0;i<h;i++)
      for(int j=0;j<mp[i].size();j++)
	if(mp[i][j]!='.'&&mp[i][j]!='#'){
	  x=j,y=i;
	  if(mp[i][j]=='N')dir=0;
	  if(mp[i][j]=='E')dir=1;
	  if(mp[i][j]=='S')dir=2;
	  if(mp[i][j]=='W')dir=3;
	}

    solve();
  }
  return 0;
}

Measured memory_bytes: 1568
#include <stdio.h>
int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}
int main()
{
 int n,b,i,count=0,j,flag=0,a5[100000];
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
   
    scanf("%d",&a5[i]);
    
  }
qsort(a5, n, sizeof(int), cmpfunc);
  for(i=0;i<n;)
  {
      if(a5[i]==a5[i+1])
      {
          i+=2;
          
      }else{
          count++;
          i++;
      }
  }
  printf("%d",count);

    return 0;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int n=0,w=0,S=0,e=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='N')n=1;
		if(s[i]=='W')w=1;
		if(s[i]=='S')S=1;
		if(s[i]=='E')e=1;
	}
	if(n==S&&w==e){cout<<"Yes"<<endl;return 0;}
	cout<<"No"<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int i = Integer.parseInt(scan.nextLine().replace(" ", ""));
        if(isSquareNumber(i)) System.out.println("Yes");
        else System.out.println("No");

        scan.close();
        
    }

    static boolean isSquareNumber (int number) {
        double sqrtOfNumber = Math.sqrt(number);
        return (isInteger(sqrtOfNumber));
    }

    static boolean isInteger (double number) {
        return (number == Math.floor(number));
    }

}

Measured memory_bytes: 22868
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
a = nl()
p1 = 0
p2 = 0
p3 = 0
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 4 == 0:
            p3 += 1
        else:
            p2 += 1
    else:
        p1 += 1
if p1 <= p3:
    print('Yes')
else:
    if p1 == p3 + 1 and p2 == 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 14628
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf 10000000000000000 //10^16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define P pair<int,int>
#define prique priority_queue<P,vector<P>,greater<P>>
using namespace std;
signed main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a > b) swap(a, b);
	if (a < c&&c < b) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())

tmp = int(input())
res = 0
if n == 1:
    print(tmp)
else:
    for i in range(n-1):
        tmp2 = int(input())
        res = lcm(tmp, tmp2)
        tmp = res
    print(res)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int MOD=1000000007;
using namespace std;
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main(){
    vector<string> s(3);
    rep(i,0,3) cin>>s[i];
    
    int now=0;
    while(s[now].size()>0){
        int next=(int)s[now][0]-'a';
        s[now].erase(s[now].begin());
        now=next;
    }
    cout<<(char)('A'+now)<<endl;
}


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

int main()
{
  int N, M;
  cin >> N >> M;
  int tmp = 0;
  for (int i = 0; i < M; i++)
  {
    int n;
    cin >> n;
    tmp += n;
  }
  if (tmp <= N)
  {
    cout << N - tmp << endl;
  }
  else
  {
    cout << -1 << endl;
  }
}

Measured memory_bytes: 3608
#include <iostream>

int main()
{
  int a[5];
  int k;
  std::cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> k;
  
  for (int i=0 ; i<5 ; i++) {
    for (int j=0 ; j<5 ; j++) {
      if (abs(a[i] - a[j]) > k) {
        std::cout << ":(" << std::endl;
        return 0;
      }
    }
  }
  
  std::cout << "Yay!" << std::endl;
}


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

int main(){
 while(1){
 int H,W;
 cin >>H>>W;
 if(H ==0 && W==0)break;
 for(int i=0;i<H;i++){
 for(int j=0;j<W;j++){
 if((i+j)%2==0)cout<<"#";
 else cout<<".";
 }
cout<<endl;
}
cout<<endl;
}

}


Measured memory_bytes: 3088
// ABC 159-D
// 2020.3.24 bal4u

#include <stdio.h>

typedef long long ll;

#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int in() {   // 非負整数の入力
	int n = 0; int c;
	c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
	//(c & 0xf)：字符0-9 Ascii码0x30-0x39 与0xf（即00001111）按位与运算 只保留个位数（0x0-0x9）
}

void out(ll n) { // 非負整数の表示（出力）
	int i; char b[30];

	if (!n) pc('0');
	else {
		//		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

int f[200005];
int A[200005];

int main()
{
	int i, N, a, ma;
	ll s;

	N = in();
	ma = 0;
	for (i = 0; i < N; ++i) {
		A[i] = a = in(), f[a]++;
		if (a > ma) ma = a;
	}
	s = 0; for (i = 1; i <= ma; ++i) s += (ll)f[i] * (f[i] - 1) >> 1;// >> 1:右移运算符 将其二进制右移1位 即/2
	for (i = 0; i < N; ++i) out(s - (f[A[i]]-1));
	return 0;
}

Measured memory_bytes: 3584
import java.util.*;

public class Main {
    private static long[] dp = new long[100100];
    private static final long INF = 1L << 60;
    private static final long MOD = 1000000007L;
    public static void main(String[] args) throws Exception {
        Arrays.fill(dp,0);
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int W = Integer.parseInt(sc.next());
        boolean brokenSteps[] = new boolean[100100];
        Arrays.fill(brokenSteps,false);
        for(int i=0;i<W;i++){
            brokenSteps[Integer.parseInt(sc.next())] = true;
        }
        dp[0] = 1;
        long res = 1;
        for(int i=0;i<=N;i++){
            for(int j=i+1;j<=Math.min(N,i+2);j++){
                if(!brokenSteps[j]){
                    dp[j] += dp[i];
                    dp[j] %= MOD;
                }
            }
        }
        System.out.println(dp[N]);
    }
}

Measured memory_bytes: 45716
#pragma GCC optimize("O3")
#include <iostream>
#include <climits>
#include <stdlib.h>

using namespace std;


typedef struct child {
    int cur;
} child;

string s;
child children[100000];
int len, rest, steps=0;
int sums[100000] = {};

void print(void) {
    for (int i = 0; i < len; i++) {
        cout << sums[i];
        if (i != len-1) cout << " ";
    }
    cout << endl;
}

void calc(void) {
    child *p;
    for (int i = 0; i < len; i++) {
        p = &children[i];
        sums[p->cur]++;
    }
}

void step(void) {
    child *p;
    int startpos, stoppos, diff;
    char prev;
    for (int i = 0; i < len; i++) {
        p = &children[i];
        if (i == 0) {
            prev = 'R';
        } else if (prev == s[p->cur]) {
            diff = abs(p->cur-stoppos);
            if (prev == 'R') {
                p->cur += diff;
                if (diff%2) {
                    p->cur--;
                }
            } else {
                p->cur -= diff;
                if (diff%2) {
                    p->cur++;
                }
            }
        } else if (prev == 'R') {
            prev = 'L';
        } else {
            prev = 'R';
        }
        startpos = p->cur;
        if (s[p->cur] == 'R') {
            while (s[++p->cur] != 'L');
            stoppos = p->cur;
            if ((p->cur-startpos)%2) --p->cur;
        } else {
            while (s[--p->cur] != 'R');
            stoppos = p->cur;
            if ((startpos-p->cur)%2) ++p->cur;
        }
    }
}

int main(void) {

    cin >> s;
    len = s.length();

    for (int i = 0; i < len; i++) {
        children[i].cur = i;
    }

    step();
    calc();
    print();
    
    return 0;
}


Measured memory_bytes: 1408
#include<iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    ll n = s.size();
    ll count = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != t[i]) {
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3820
#include <iostream>

#include <map>
#include <string>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cinttypes>


using namespace std;

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



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

		if (a & 1)
			continue;

		if (a % 3 != 0 && a % 5 != 0)
		{
			cout << "DENIED" << endl;
			return 0;
		}
	}

	cout << "APPROVED" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int MOD=1e9+7;
typedef pair<int,int> pii;
typedef long long ll;
template<typename A,size_t N,typename T>
void Fill(A (&array)[N],const T &val)
{
    std::fill( (T*)array,(T*)(array+N),val );
}

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

int main(void)
{
    ll a,b,ans;
    cin >> a >> b;
    ans=a*b/gcd(a,b);
    cout << ans << endl;

}

Measured memory_bytes: 256
def number(a):
    m=10**10
    MAX=int(a**0.5)+1
    for i in range(1,MAX):
        if(a%i==0):
            b=len(str(i))
            c=len(str(a//i))
            m=min(m,max(b,c))
    return m

N=int(input())
print(number(N))

Measured memory_bytes: 38896
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    dic = defaultdict(int)
    n = inp()
    a = inpl()
    ans = 0
    for i in range(n):
        ans += dic[i-a[i]]
        dic[a[i]+i] += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 62836
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF=1LL<<60;

int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int a;
	cin>>a;
	if(a%2==0)cout<<a*a/4<<endl;
	else cout<<a/2*(a/2+1)<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;

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;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main( ){
    int n;
    cin>>n;
    int k;
    cin>>k;
    vi a(n);
    rep(i,0,n)cin>>a[i];
    int cnt=0;
    if(n==k)cnt=1;
    else{
        n-=k;
        cnt++;
        cnt+=n/(k-1);
        if(n%(k-1))cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}




Measured memory_bytes: 640
#include <iostream>
#include <string.h>
using namespace std;

int main(){
    int a[]={4,6,9,11};
    int x,y;
    cin >> x >> y;
    int frg1=3;
    int frg2=3;

    if(x==2)frg1=1;
    if(y==2)frg2=1;

    for(int i=0;i<4;i++){
        if(x==a[i])frg1=2;
        if(y==a[i])frg2=2;
    }
    if(frg1==frg2)cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-2)
    if c*(c+1) < a*b and c+1 != b:
        ans[-1] +=1
for i in ans:
    print(i)


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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;

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

  string s;
  cin >> s;
  int count=0;
  string ans="CODEFESTIVAL2016";
  for(int i=0;i<16;i++){
    if(s[i]!=ans[i]) count++;

  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n, k;
    cin >> n >> k;

    int r = 0;
    vector<int> s(n + 1);
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        s[i + 1] = s[i] + (p + 1);
    }

    for (int i = k; i <= n; i++) {
        r = max(r, s[i] - s[i - k]);
    }

    cout << fixed << setprecision(12) << r * 0.5 << endl;

    return 0;
}

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

unsigned long long cal(int x)
{
    unsigned  long long ans = 1,y = 2;
    while(x)
    {
        if(x%2)ans*=y;
        y*=y;
        x/=2;
    }
    return ans;
}

int main()
{
    int n,p;
    int a[100];
    cin>>n>>p;
    int x=0,y=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]%2)x++;
        else y++;
    }

    unsigned long long ans = 0;
    ans = cal(y)*(cal(x)/2ll);
    if(p==0&&x==0)ans = cal(y);
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
N=int(input())
s=[list(input()) for _ in range(N)]
b=0
cnt=0
for i in range(N):
    s[i].sort()
s.sort()
for i in range(N-1):
    if s[i]==s[i+1]:
        b=b+1
    if not(s[i]==s[i+1])and(s[i]!=0):
        cnt=cnt+(b*(b+1))//2
        b=0
    #print(b)
cnt=cnt+(b*(b+1))//2
print(cnt)


Measured memory_bytes: 24652
use std::io::*;

struct Stdio {
    sin : Stdin,
    sout : Stdout,
    buf : Vec<String>,
    len : usize,
    cnt : usize,
}

impl Stdio {
    fn new() -> Stdio  {
        Stdio {
            len : 0,
            cnt : 0,
            sin : stdin(),
            sout : stdout(),
            buf : Vec::new(),
        }
    }
    
    fn read_line(&mut self) {
        let mut s = String::new();
        let mut loc = self.sin.lock();
        loc.read_line(&mut s).unwrap();
        self.buf = s.trim().split_whitespace().map(|s| s.to_string()).collect();
        self.len = self.buf.len();
        self.cnt = 0;
    }

    fn read_i32(&mut self) -> i32 {
        if self.len == self.cnt {
            self.read_line();
        }
        let ret = self.buf[self.cnt].parse::<i32>().ok().unwrap();
        self.cnt += 1;
        ret
    }

    fn read_string(&mut self) -> String {
        if self.len == self.cnt {
            self.read_line();
        }
        let ret = self.buf[self.cnt].clone();
        self.cnt += 1;
        ret
    }
    fn write(&mut self , s : &str) {
        write!(self.sout ,"{}" ,s).unwrap();
    }
}

fn main() {
    let mut stdio = Stdio::new();
    let n :usize = stdio.read_i32() as usize;
    let mut a = vec![0;n];
    for i in 0..n {
        a[i] = stdio.read_i32();
    }
    let max = a.iter().max().unwrap();
    let min = a.iter().min().unwrap();
    stdio.write(&(max-min).to_string());


}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int fa[100050];

struct fuck
{
	int u,v,w;
	bool operator < (const fuck &a) const
	{
		return w < a.w;
	}
}Q[100050];

int n;
long long m;

int find_fa(int pos)
{
	return fa[pos] == pos ? pos : fa[pos] = find_fa(fa[pos]);
}

int main()
{
	int q;
	scanf("%d%lld%d",&n,&m,&q);
	for(int i = 1;i <= q; ++ i)
		scanf("%d%d%d",&Q[i].u,&Q[i].v,&Q[i].w),Q[i].u ++,Q[i].v ++;
	sort(Q + 1,Q + 1 + q);
	for(int i = 1;i <= n; ++ i) fa[i] = i;
	int fuck = 1;
	for(int i = 1;i <= q; ++ i)
	{
		if(!Q[i].w)
		{
			int u = find_fa(Q[i].u),v = find_fa(Q[i].v);
			fa[u] = v;
		}
		else
		{
			fuck = 0;
			if(find_fa(Q[i].u) == find_fa(Q[i].v))
			{
				printf("No\n");
				return 0;
			}
		}
	}
	int cnt = 0;
	for(int i = 1;i <= n; ++ i) if(fa[i] == i) cnt ++;
	long long cmax = n - cnt + cnt * 1ll * (cnt - 1) / 2;
	if(cmax >= m && n - fuck <= m) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String s1 =s.next();
        int res=0;
        for(int i=0;i<3;i++){
            if(s1.charAt(i)=='R')
                res++;
        }
        if(res==2){
            int flag=0;
            for(int i=0;i<2;i++){
                if(s1.charAt(i)=='R'&&s1.charAt(i+1)=='R')
                    flag=1;
            }
            if(flag==0)
                res=1;
        }
        System.out.println(res);
    }
    static int gcd(int a, int b)
    {
        if(b==0) {
            return a;
        }
        return gcd(b,a%b);
    }
    private static boolean isPrime(int n) {
        if (n == 2)
            return true;
        else if ((n % 2 == 0 && n > 2) || n < 2)
            return false;
        else {
            for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }


    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

Measured memory_bytes: 26632
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);
		int ans=0;
		while(s.hasNext()){
			String b=s.next();
			boolean now=true;
			for(int i=0;i<b.length();i++){
				if(b.charAt(i)!=b.charAt(b.length()-1-i))now=false;
			}
			if(now)ans++;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 11000
use strict;
use warnings;

chomp(my $ab = <>);

my ($a, $b) = split(/ /, $ab);

my $price;

if ( int($a/0.08) < int($b/0.1) ){
  $price = int $a/0.08;
  while( int($price*0.1)<$b ){
    $price++;
  }
} else {
  $price = int $b/0.1;
  while( int($price*0.08)<$a ){
    $price++;
  }
}

if( int($price*0.08)==$a && int($price*0.1)==$b){
  print "$price\n";
} else{
  print "-1\n";
}


Measured memory_bytes: 640
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define ANS(ans) cout<<(ans)<<endl;
typedef vector<int> VI;


//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)


int main() {
	string s, t;
	cin >> s >> t;

	int flag = 0;
	int i = 0;

	while (flag == 0 && i < s.length()) {

		if (s == t) {
			flag = 1;
		}
		else {
			s += s[0];
			s.erase(s.begin());
		}
		i++;
	}

	if (flag == 1) {
		cout << "Yes" << endl;
	}
	else if (flag == 0) {
		cout << "No" << endl;
	}

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
 
const int N=3e5+5,MAX=3e7,MOD=1e9+7;
 
using namespace std;
 
int n;
int main()
{
  

    	int n;
    	ll k;

    	scanf("%d %lld",&n,&k);

    	std::vector<int> a(n);
    	for(int i=0;i<n;i++){
    		scanf("%d",&a[i]);
    	}
    	ll ans = 0;

    	ll wa1 = k*(k+1)/2; 
    	ll wa2 = k*(k-1)/2;

    	wa1%=MOD;
    	wa2%=MOD;
    	for(int i=0;i<n;i++){
    		ll curr1 = 0;
    		for(int j=i+1;j<n;j++){
    			curr1+=(a[j]<a[i]);
    		}

    		curr1 = curr1*wa1;

    		curr1%=MOD;
    		ll curr2 = 0;
    		for(int j=i-1;j>=0;j--){
    			curr2+=(a[j]<a[i]);
    		}

    		curr2 = curr2 * wa2;

    		curr2%=MOD;

    		ans+=curr1+curr2;

    		ans%=MOD;
    	}

    	printf("%lld\n",ans );
 	
}

Measured memory_bytes: 256
n = int(input())

for i in range(1,n+1):
    if (i % 3) == 0:
        print(" " + str(i), end="")
        continue
    x = i
    while x > 0:
        if (x % 10) == 3:
            print(" " + str(i), end="")
            break
        x //= 10

print()

Measured memory_bytes: 7956
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	string s; cin>>s;
	int n=s.size();
	map<char,int> mp;
	rep(i,0,n) mp[s[i]]++;
	rep(i,0,26){
		if(!mp['a'+i]){
			cout<<char('a'+i)<<endl;
			return 0;
		}
	}
	cout<<"None"<<endl;
	
	return 0;
}

Measured memory_bytes: 3716
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <math.h>
#define int long long
#define ll long long
using namespace std;
//#pragma endregion

signed main()
{
	//int x;

	//int N;
	//int n;
	//int m;
	int k;
	string s;
	//string t;
	//int m1, m2;
	//int a, b, c, k;

	//int k, d;
	int all = 0;
	//int a, b;
	//int a[30000] = { 0 };

	int b = 0;

	//int box[10000] = { 0 };

	bool flag = true;

	//string str;

	cin >> k;
	cin >> s;

	//n = N % 10;

	b = s.length();

	//cout << endl;
	//for (int i = 0; i <= (k - 2); i++)
	//{
	//	b = a[b];
	//	//cout << b << "\n";
	//}
	/*if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
	{
		cout << "hon\n";
	}
	else if (n == 0 || n == 1 || n == 6 || n == 8)
	{
		cout << "pon\n";
	}
	else
	{
		cout << "bon\n";
	}*/

	if (k >= b)
	{
		cout << s << "\n";
	}
	else
	{
		for (int i = 0; i < k; i++)
		{
			cout << s[i];
		}
		cout << "...\n";
	}
	
	//cout << b << "\n";

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/
}


Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int x = 0;
		int y = 0;
		while (true) {

			x = sc.nextInt();
			y = sc.nextInt();

			if (x == 0 && y == 0) {
				break;
			}

			if (x < y) {
				System.out.println(x + " " + y);
			} else {
				System.out.println(y + " " + x);
			}

		}

		sc.close();

	}

}


Measured memory_bytes: 35964
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int m = sc.nextInt();
		int aArray[] = new int[a]	;
		int bArray[] = new int[b]	;

		int aMin = Integer.MAX_VALUE;
		for (int i = 0; i < a; i++) {
			aArray[i] = sc.nextInt();
			if (aArray[i] < aMin) aMin = aArray[i];
		}

		int bMin = Integer.MAX_VALUE;
		for (int i = 0; i < b; i++) {
			bArray[i] = sc.nextInt();
			if (bArray[i] < bMin) bMin = bArray[i];
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < m; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int c = sc.nextInt();
			int sum = aArray[x - 1] + bArray[y - 1] - c;
			if (sum < min) min = sum;
		}

		System.out.println(Math.min(aMin + bMin, min));

		sc.close();
	}

}


Measured memory_bytes: 132636
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1001001001;
const long long mod=1e9+7;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    int N,K; cin >> N >> K;
    vector <int> H(N);
    rep(i,N) cin >> H[i];
    
    vector <int> dp(N+1,INF);
    dp[0]=0;
    
    for (int now=0; now<N; now++){
        for (int next=now+1; next<=min(N-1,now+K); next++){
            chmin(dp[next],dp[now]+abs(H[next]-H[now]));
        }
    }
    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;


int main(){
  string S;

  while(cin >> S){

  int ansJ = 0;
  int ansI = 0;

  for(int i = 0;i<S.size()-2;i++){
    if(S.at(i)=='I'){
      if(S.at(i+1)=='O'){
        if(S.at(i+2)=='I'){
          ansI++;
          continue;
        }
      }
    }
    if(S.at(i)=='J'){
      if(S.at(i+1)=='O'){
        if(S.at(i+2)=='I'){
          ansJ++;
        }
      }
    }
    
  }
  cout << ansJ << endl;
  cout << ansI << endl;
  }
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define mREP(i,a,b) for (int i = a; i > (b); --i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int ans[6];
int main(){
  int n,m;
  cin >> n >> m;
  if(m < n)n = m;
  if(m == 1){
    cout << 0 << endl;
    return 0;
  }
  vector<int>v(m);
  vector<int>tmp(m-1);
  rep(i,m){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  ll ans = 0;
  rep(i,m-1){
    ans += abs(v[i]-v[i+1]);
    tmp[i] = abs(v[i]-v[i+1]);
  }
  sort(all(tmp));
  reverse(all(tmp));
  rep(i,n-1){
    ans -= tmp[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   Int v, e;
   std::cin >> v >> e;
   std::vector<Int> ss(e), ts(e), cs(e), fs(e);
   rep(i, e) {
      std::cin >> ss[i] >> ts[i] >> cs[i];
   }
   std::vector<std::vector<Int>> fes(v), bes(v);
   rep(i, e) {
      Int s = ss[i], t = ts[i];
      fes[s].emplace_back(i);
      bes[t].emplace_back(i);
   }
   Int res = 0;
   Int source = 0;
   Int sink = v-1;
   for(;;) {
      std::queue<Int> q;
      std::vector<Int> xs(v);
      std::vector<Int> ps(v, -1), es(v, -1);
      q.emplace(source);
      xs[source] = (Int)1 << 53;
      while( not q.empty() ) {
         Int z = q.front(); q.pop();
         for(Int i : fes[z]) {
            Int s = z, t = ts[i];
            guard( ps[t] == -1 );
            if( cs[i] - fs[i] > 0 ) {
               ps[t] = s;
               es[t] = i;
               xs[t] = std::min(xs[s], cs[i] - fs[i]);
               q.emplace(t);
            }
         }
         for(Int i : bes[z]) {
            Int s = z, t = ss[i];
            guard( ps[t] == -1 );
            if( fs[i] > 0 ) {
               ps[t] = s;
               es[t] = i;
               xs[t] = std::min(xs[s], fs[i]);
               q.emplace(t);
            }
         }
      }
      Int f = xs[sink];
      fprintf(stderr, "f = %ld\n", f);
      if( f == 0 ) break;
      for(Int i = sink; i != source; i=ps[i]) {
         Int k = es[i];
         fprintf(stderr, "k=%ld\n", k);
         fs[k] += (ts[k] == i ? +f : -f);
      }
      res += f;
      rep(i, e) {
         fprintf(stderr, "%ld -> %ld : %ld/%ld\n", ss[i], ts[i], fs[i], cs[i]);
      }
   }
   printf("%ld\n", res);
}



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

Measured memory_bytes: 600
/* "The world is full of obvious things which nobody by any chance ever observes." */


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

typedef long long ll;
#define mod 1000000007
#define pi  3.14159265358979323846
#define pb push_back
#define mk make_pair
#define popcnt(a) _Generic((a), int: __builtin_popcount(a), \  long long: __builtin_popcountll(a))  
#define precise(x) cout<<fixed<<setprecision(10)<<x
#define test cout<<"#";
#define input freopen("input.txt", "r", stdin)
#define output freopen("output.txt", "w", stdout) 

const ll inf = 1e18L + 2;

ll ans[1000001];

ll solve(vector<ll> &v, ll n, ll k)
{
    if(n==1)
        return 0;
    if(ans[n]!=-1)
        return ans[n];

    ans[n] = inf;
    for(ll x = 1; x <= k; x++)
        if((n-x >= 1))
            ans[n] = min(ans[n], solve(v, n-x, k) + abs(v[n-1] - v[n-x-1]));
    return ans[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, k;
    cin>>n>>k;
    vector<ll> v(n);
    memset(ans, -1, sizeof(ans));
    for(ll x = 0; x < n; x++)
        cin>>v[x];
    cout<<solve(v, n, k);
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}


signed main() {
  ll n, a[100001], b[100001], c[100001];
  cin >> n;
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> b[i];
  rep(i, 0, n) cin >> c[i];

  sort(a, a + n);
  sort(b, b + n);
  sort(c, c + n);

  ll e[100001] = {};
  int ai = 0, bi = 0, ci = 0;
  while(bi < n && ci < n) {
    if(c[ci] <= b[bi]) ci++;
    else {
      e[bi] = n - ci;
      bi++;
    }
  }
  rep(i, 1, n) {
    e[i] += e[i - 1];
  }
  ll ans = 0;
  bi = 0;
  while(ai < n && bi < n) {
    if(b[bi] <= a[ai]) bi++;
    else {
      if(bi) ans += e[n - 1] - e[bi - 1];
      else ans += e[n - 1];
      ai++;
    }
  }
  cout << ans << endl;
}


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

int64_t ctoi(char a){
  if(a=='0') return 0;
  else if(a=='1') return 1;
  else if(a=='2') return 2;
  else if(a=='3') return 3;
  else if(a=='4') return 4;
  else if(a=='5') return 5;
  else if(a=='6') return 6;
  else if(a=='7') return 7;
  else if(a=='8') return 8;
  else return 9;
}

int64_t C2(int64_t A){
  return A*(A-1)/2;
}

int main(){
  string S; cin >> S;
  int64_t N = S.size();
  vector<int64_t> T(N);
  T.at(0) = ctoi(S.at(N-1));
  int64_t a = 1;
  for(int64_t i=1; i<N; i++){
    a = (a*10)%2019;
    T.at(i) = (T.at(i-1)+a*ctoi(S.at(N-i-1)))%2019;
  }
  int64_t ans = 0;
  sort(T.begin(), T.end());
  for(int64_t i=0; i<N; i++){
    if(T.at(i)%2019==0) ans++;
  }
  vector<int64_t> vec;
  int64_t j = 1;
  for(int64_t i=1; i<N; i++){
    if(T.at(i)==T.at(i-1)){
      j++;
    }
    else{
      vec.push_back(j);
      j = 1;
    }
  }
  vec.push_back(j);
  for(int64_t i=0; i<vec.size(); i++){
    ans += C2(vec.at(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 5156
# -*- coding: utf-8 -*-

x = input()
y=[]
y=x.split(" ")
N=int(y[0])
M=int(y[1])

z=[]
for i in range(M):
	temp1=input()
	temp2=temp1.split(" ")
	for j in temp2:
		j=int(j)
		z.append(j)

dict={}
for i in range(N):
	i+=1
	dict[i]=0

for i in z:
	dict[i]=dict[i]+1

for i in range(N):
	i+=1
	print(dict[i])
	

Measured memory_bytes: 3064
S = input()
T = input()

add = len(T)
#print(add)
if len(S) > 10 or len(S) < 1:
  print("No")
  exit()

if S != T[:int(len(T)-1)]:
  print("No")
  exit()
if len(S)+1 != len(T):
  print("No")
  exit()
for i in range(len(T)):
  if T[i] not in "abcdefghijklmnopqrstuvwxyz":
    print("No")
    exit()
  else:
    pass

print("Yes")


Measured memory_bytes: 9128