akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int mod=1e9+7;
const int maxn=1e6+20;

int n,dp[maxn],s[maxn],s1[maxn];
int ans;

inline void init()
{
	n=read();
	dp[1]=1; s[1]=s1[1]=1;
	REP(i,2,n)
	{
		dp[i]=1;
		if(i-3>=1)dp[i]=(dp[i]+(ll)(i-2)*s[i-3]-s1[i-3]+mod)%mod;
		s[i]=(s[i-1]+dp[i])%mod; s1[i]=(s1[i-1]+(ll)i*dp[i])%mod;
	}
	ans=(ans+1)%mod;
	REP(i,1,n-1)ans=(ans+(ll)dp[i]*(n-1)%mod*(n-1))%mod;
	REP(i,1,n)ans=(ans+(ll)dp[i]*(n-1))%mod;
	printf("%d\n",ans);
}

int main()
{
	init();
	return 0;
}



Measured memory_bytes: 11904
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
#define fir first
#define sec second
#define Mp make_pair
const int MAXN = 2e5 + 5;

int a[MAXN];
ll lval[MAXN],rval[MAXN];

struct Edge
{
	int u,v;
	ll w;
};
inline bool cmp(const Edge &p,const Edge &q){ return p.w<q.w;}
vector<Edge> e;

int fa[MAXN];
inline void init(int n){ for(int i=1; i<=n; ++i) fa[i]=i;}
int find(int u){ return fa[u]==u? u: fa[u]=find(fa[u]);}
void connect(int u,int v){ fa[find(u)]=find(v);}

void gao(int l,int r)
{
	if(l==r) return;
	int mid = (l+r)>>1;
	
	ll lmn = lval[l];
	int lpos = l;
	for(int i=l; i<=mid; ++i)
		if(lmn > lval[i])
			lmn = lval[i], lpos = i;
	ll rmn = rval[r];
	int rpos = r;
	for(int i=mid+1; i<=r; ++i)
		if(rmn > rval[i])
			rmn = rval[i], rpos = i;
	
	for(int i=l; i<=mid; ++i)
		e.push_back((Edge){ i, rpos, lval[i] + rmn});
	for(int i=mid+1; i<=r; ++i)
		e.push_back((Edge){ lpos, i, lmn + rval[i]});
	
	gao(l,mid); gao(mid+1,r);
}

int main(void)
{
	int n;
	ll d;
	scanf("%d%lld",&n,&d);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	
	for(int i=1; i<=n; ++i)
		lval[i] = a[i] - d*i,
		rval[i] = a[i] + d*i;
	
	gao(1,n);
	sort(e.begin(),e.end(),cmp);
	
	ll ans=0;
	init(n);
	for(int i=0; i<(int)e.size(); ++i)
	{
		int u=e[i].u, v=e[i].v;
		ll w=e[i].w;
		if(find(u) == find(v)) continue;
		ans += w;
		connect(u,v);
	}
	printf("%lld",ans);
	return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int n, a, b;
  cin >> n >> a >> b;
  cout << ((b-a-1)%2==1?"Alice": "Borys") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long A, long long B){
  if((A==1 and B==2) or (B==1 and A==2))
    std::cout << 3 << std::endl;
  else if((A==2 and B==3) or (B==2 and A==3))
    std::cout << 1 << std::endl;
  else
    std::cout << 2 << std::endl;
}

int main(){
  long long A;
  scanf("%lld",&A);
  long long B;
  scanf("%lld",&B);
  solve(A, B);
  return 0;
}



Measured memory_bytes: 256
#include<iostream>

int main(){

  int x, y;
  while(1){
    std::cin >> x >> y;
    if(x ==0 && y == 0) break;
    if(x < y){
      std::cout << x << ' ' << y << std::endl;
    }else{
      std::cout << y << ' ' << x << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3064
n = int(input())
l = [int(x) for x in input().split()]
a = 0
b = 0
for i in range(n):
  if i % 2 == 0:
    a += max(l)
    l.remove(max(l))
  elif i % 2 == 1:
    b += max(l)
    l.remove(max(l))
print(a-b)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<complex>
using namespace std;

int main(){
  while(true){
    int n,x; cin >> n >> x;
    if(n == 0 && x == 0) break;
    int ans = 0;
    for(int i = 1; i <= n; i++){
      for(int j = i+1; j <= n; j++){
        for(int k = j+1; k <= n; k++){
          int now = i+j+k;
          if(now == x) ans++;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

int main(void){
	ll n;
	cin >> n;
	Vec a(n);
	rep(i, n) cin >> a[i];

	ll ans = 0;
	rep(i, n){
		if (i % 2 == 0 && a[i] % 2 == 1) ans++;
	}
	co(ans);

	return 0;
}


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

int main() {
	char s;
	for (int i = 0; i < 19; i++) {
		cin >> s;
		if (s == ',') {
			cout << ' ';
		}
		else {
			cout << s;
		}
	}
	cout << endl;
}

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

int main()
{    
    string s;
    cin >> s;
    s.replace(0, s.size(),s.size(),'x');

    cout << s << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, C; cin >> n >> C;
    int m = 1e5 + 2;
    vector<vi> ctbl(C, vi(m));
    rep(i, n){
        int s, t, c; cin >> s >> t >> c;
        c--;
        ctbl[c][s]++;
        ctbl[c][t]--;
    }

    vi tbl(m);
    rep(i, C){
        rep(j, m){
            int cur = ctbl[i][j];
            if(cur == 1){
                tbl[j]++;
            }
            else if(cur == -1){
                tbl[j+1]--;
            }
        }
    }

    int res = 0;
    rep(i, 1, m){
        tbl[i] += tbl[i - 1];
        chmax(res, tbl[i]);
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 12416
#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(){
	int a,b,c,d; cin>>a>>b>>c>>d;
	bool ok=true;
	if(abs(a-b)>d) ok=false;
	if(abs(b-c)>d) ok=false;
	if(abs(a-c)<=d) ok=true;
	cout<<(ok ? "Yes":"No")<<endl;
	
	return 0;
}

Measured memory_bytes: 3596
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
S = input()
lr = [LIST() for _ in range(Q)]

accum = []
count = 0

for i in range(len(S)-1):
	accum.append(count)
	if S[i] == "A" and S[i+1] == "C":
		count += 1
accum.append(count)
# print(accum)
for l, r in lr:
	print(accum[r-1]-accum[l-1])


Measured memory_bytes: 31540
n, k = map(int, input().split())
ans = 0
i=0
pre = 0
tmp = 0
if n >= k:
    ans += (n-k+1)
    pre = k
    i = 1
    tmp = (pre+1)//2
else:
    pre = n+1
    tmp = k
    i=0
    while n < tmp:
        tmp = (tmp+1)//2
        i+=1
    ans += (pre-tmp)*((0.5)**i)
    pre = tmp
    i+=1
    tmp = (pre+1)//2
while pre != tmp:
    # i回コインで面出す必要あり 
    ans += (pre-tmp)*((0.5)**i)
    pre = tmp 
    i+=1
    tmp = (pre+1)//2
print(ans/n)

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

using namespace std;

const int N = 500000;

int n;
int L[N + 1];
int R[N + 1];
char s[N + 1];

int main() {
	cin >> n;
	cin >> s;
	for(int i = 0; i < n; i++) L[i] = (i < 1 ? 0 : L[i - 1]) + (s[i] == 'W');
	for(int i = n; i; i--) R[i - 1] = R[i] + (s[i - 1] == 'E');
	int res = min(L[n - 1], R[1]);
	for(int i = 1; i < n - 1; i++)
		res = min(res, R[i + 1] + L[i - 1]);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int i;
  for(i=0;i<s.size();i++){
    s.at(i)=(s.at(i)-'A'+n)%26+'A';
    cout << s.at(i);
  }
}
  

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

//#define int             long long
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
//mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 

int32_t main()
{
    //c_p_c();
    int n,w;
    cin>>n>>w;
    vi a(n+1);
    vi v(n+1);
    int maxvalue=n*1000;
    int dp[n+1][maxvalue+1];
    for(int i=1;i<=n;i++){
        cin>>a[i]>>v[i];
    }
    //for(int i=1;i<=n;i++)cout<<a[i]<<" "<<v[i]<<endl;
   
   for(int i=0;i<=maxvalue;i++)dp[1][i]=inf;
   dp[1][0]=0;
   dp[1][v[1]]=a[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=maxvalue;j++){
            if(v[i]<=j){
                dp[i][j]=dp[i-1][j];
                dp[i][j]=min(dp[i][j],a[i]+dp[i-1][j-v[i]]);
            }else dp[i][j]=dp[i-1][j];
           //cout<<dp[i][j]<<" ";
        }//cout<<endl;
    }
    int ans=0;
    for(int i=0;i<=maxvalue;i++){
        if(dp[n][i]<=w)
        ans=i;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 81736
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int N, Q;
    while (cin >> N >> Q, N) {
        vector<string> era(N);
        vector<int> s(N), t(N);
        for (int i = 0; i < N; i++) {
            int eby;
            cin >> era[i] >> eby >> t[i];
            s[i] = t[i] - eby + 1;
        }
        for (int i = 0; i < Q; i++) {
            int x; cin >> x;
            bool unknown = true;
            for (int j = 0; j < N; j++) {
                if (s[j] <= x && x <= t[j]) {
                    cout << era[j] << " " << x - s[j] + 1 << endl;
                    unknown = false;
                    break;
                }
            }
            if (unknown) cout << "Unknown" << endl;
        }
    }
    return 0;
}


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

using namespace std;

#define MAX 252521

class Union_Find {
  public:
    int par[MAX], rnk[MAX], sz[MAX], gnum;
    
    Union_Find(int N) {
        gnum = N;
        for (int i = 0; i < N; i++) {
            par[i] = i;
            rnk[i] = 0;
            sz[i] = 1;
        }
    }

    int find(int x)
    {
        if (par[x] == x) {
            return x;
        }
        return par[x] = find(par[x]);
    }

    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y) return;
        
        if (rnk[x] < rnk[y]) {
            par[x] = y;
            sz[y] += sz[x];
        } else {
            par[y] = x;
            sz[x] += sz[y];
            if (rnk[x] == rnk[y]) {
                rnk[x]++;
            }
        }
        gnum--;
    }

    bool same(int x, int y)
    {
        return (find(x) == find(y));
    }

    int size(int x)
    {
        return sz[find(x)];
    }

    int groups()
    {
        return gnum;
    }
};

struct edge {
    int u, v, cost;    
};

bool comp(const edge& a, const edge& b)
{
    return a.cost < b.cost;
}

using ll = long long;

edge es[MAX];

ll solve(int N)
{
    Union_Find uf(N);
    sort(es, es + N - 1, comp);

    ll res = 0;
    for (int i = 0; i < N - 1; i++) {
        edge& e = es[i];
        if (!uf.same(e.u, e.v)) {
            res += (ll)uf.size(e.u) * uf.size(e.v) * e.cost;
            uf.unite(e.u, e.v);
        }
    }
    return res;
}

int main()
{
    int N, a, b, c;
    cin >> N;    
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b >> c;
        es[i] = {a, b, c};
    }
    cout << solve(N) << endl;
    return 0;
}

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

import math

divide = ["dream", "dreamer", "erase", "eraser"]

s = str(input())
s = s[::-1]

divide = [i[::-1] for i in divide]

can = True
i = 0
while i < len(s):
    # print("here")
    can2 = False
    for j in divide:
        # print("here2")
        # print("i: ", i, "len(j): ", len(j), "s[i:len(j)]", s[i:len(j)+i])
        if s[i:len(j)+i] == j:
            # print("here3")
            # print(s[i:len(j)])
            can2 = True
            i += len(j)
    if not can2:
        # print("here4")
        can = False
        break

if can:
    print("YES")
else:
    print("NO")


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

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

    vector<int> k(m), p(m);
    vector<vector<int> > v(m);

    for(int i = 0; i < m; i++){
        cin >> k.at(i);
        v.at(i).resize(k.at(i));
        for(int j = 0; j < k.at(i); j++){
            int s;
            cin >> s;
            v.at(i).at(j) = s-1;
        }
    }
    for(int i = 0; i < m; i++) cin >> p.at(i);

    int ans = 0;
    for(int i = 0; i < (1<<n); i++){
        int ok = 1;
        for(int j = 0; j < m; j++){
            int on = 0;
            for(int sw = 0; sw < k.at(j); sw++){
                if((i >> v.at(j).at(sw))&1) on++;
            }
            if(on % 2 != p.at(j)) ok = 0;
        }
        ans += ok;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <utility>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <climits>

using namespace std;

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 N, M;
	cin >> N >> M;

	vector<int*> c = vector<int*>(N, nullptr);

	for (int i = 0; i < M; i++)
	{
		int si, ci;
		cin >> si >> ci;

		if (c[si - 1])
		{
			if (*c[si - 1] != ci)
			{
				cout << "-1" << endl;
				return 0;
			}
		}

		c[si - 1] = new int(ci);
		}

	for (int i = 0; i < N; i++) {
		if (c[i]) {
			if (N != 1 && i == 0 && *c[i] == 0) {
				cout << "-1" << endl;
				return 0;
			}
			cout << *(c[i]);
		} else {
			if (i == 0 && N != 1) {
				cout << '1';
			} else {
				cout << '0';
			}
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	string s;
	cin>>s;
	ll ans1=0;
	ll ans2=0;
	for(ll i=0;i<s.size();i++){
		if(s[i]=='0'){
			ans1++;
		}
		else{
			ans2++;
		}
	}
	cout << min(ans1,ans2)*2;
	// your code goes here
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	int w2,h2,n;cin>>w2>>h2>>n;
	vi x(n),y(n),a(n);
	rep(i,n)cin>>x[i]>>y[i]>>a[i];
	int w1=0,h1=0;
	rep(i,n){
		if(a[i]==1)w1=max(w1,x[i]);
		if(a[i]==2)w2=min(w2,x[i]);
		if(a[i]==3)h1=max(h1,y[i]);
		if(a[i]==4)h2=min(h2,y[i]);
	}
    if(w2>=w1&&h2>=h1)cout<<(w2-w1)*(h2-h1)<<endl;
    else cout<<0<<endl;
}

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

using namespace std;
const int maxn = 100010;
vector<int> g[maxn];

int dfs(int u,int par) {
	int cnt = 0;
	for(auto v: g[u]) if(v != par) cnt += dfs(v, u);
	if(cnt == 0) return 1;
	if(cnt == 1) return 0;
	return 100;
}

int main() {
	int n; scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	puts(dfs(1, 1) == 0 ? "Second" : "First");
	return 0;
}


Measured memory_bytes: 5888
while True:
    a,op,b=map(str,input().split())
    a=int(a)
    b=int(b)
    i=0
    if op=="+":
        print(a+b)
    elif op=="-":
        print(a-b)
    elif op=="*":
        print(a*b)
    elif op=="/":
        print(int(a/b))
    elif op=="?":
        break
    i+=1


Measured memory_bytes: 5592
#include <stdio.h>

#define seki(x,y) ((x) * (y))

int main(void)
{
    int x,y;

    for (x = 1; x < 10; x++){
        for (y = 1; y < 10; y++){
            printf("%dx%d=%d\n", x, y, seki(x,y));
        }

    }

    return (0);
}


Measured memory_bytes: 1916
#include <string>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <math.h>

double myabs(double a) {
	return sqrt(a*a);
}


int main()
{
	int a, b, c;
	std::cin >> a >> b >> c;
	if (a*c <= b) std::cout << c;
	else {
		std::cout<< floor(b/a);
	}
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
int main(){
    ll n,k;
    cin>>n>>k;
    ll i;
    ll snack[n] = {0};
    for(i=0;i<k;i++){
        ll d,j;
        cin>>d;
        for(j=0;j<d;j++){
            ll k;
            cin>>k;
            snack[k-1]++;
        }
    }
    ll count = 0;
    for(i=0;i<n;i++){
        if(snack[i]==0){
            count++;
        }
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;
using i64=long long int;

int main() {
    string S;
    cin >> S;

    int i = 0;
    i64 ans = 0;
    i64 bcon = 0;
    while (i < S.size()-1) {
        if (S[i] == 'B') {
            bcon++;
            if (S[i+1] == 'W') {
                ans += bcon;
                S[i+1] = 'B';
                bcon--;
            }
        } else {
            bcon = 0;
        }
        ++i;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
    long count[5] = {0,0,0,0,0};
    long a;
    cin >> a;
    string b;
    for (long i = 0; i < a; ++i) {
        cin >> b;
        if(b[0] == 'M'){
            count[0]++;
        }else if(b[0] == 'A'){
            count[1]++;
        }else if(b[0] == 'R'){
            count[2]++;
        }else if(b[0] == 'C'){
            count[3]++;
        }else if(b[0] == 'H'){
            count[4]++;
        }
    }
    long sum = 0;
    for (long j = 0; j < 5; ++j) {
        for (long i = j+1; i < 5; ++i) {
            for (long k = i+1; k < 5; ++k) {
                sum += count[j] * count[i] * count[k];
            }
        }
    }
    printf("%ld\n",sum);
    return 0;
}

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

int calc(int n) {
    int num = 0;
    while (n > 0) {
        num += n % 10;
        n /= 10;
    }
    return num;
}

int main() {
    int n;
    cin >> n;
    int min = INT_MAX;
    for (int i = 1; i < n / 2 + 1; i++) {
        int cnt = calc(i) + calc(n - i);
        if (cnt < min) min = cnt;
    }
    cout << min << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    private struct Pair { public int x, y; }
    private static int[] dx = { 0, 1, 0, -1 };
    private static int[] dy = { 1, 0, -1, 0 };
    public static void Main()
    {
        int N = NextInt();
        int[] H = LineInt();
        int y = H[0];
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (y <= H[i]) { ans++;y = H[i]; }
        }
        Console.WriteLine(ans);
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 13396
import java.util.*;

public class Main {
    public static void main(String[] args) {
		Scanner sca01 = new Scanner(System.in);
		int x = sca01.nextInt();

		if(x == 1){
			System.out.println("0");
		}else {
			System.out.println("1");
		}
	}
}

Measured memory_bytes: 27016
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=3010;
const int mod=998244353;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int qpow(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}
	return ret;
}

int f[N][N],a,b,c,d;

int getf(int n,int m) {
	if(f[n][m]!=-1) return f[n][m];
	if(n==a) return f[n][m]=qpow(a,m-b);
	if(m==b) return f[n][m]=qpow(b,n-a);
	return f[n][m]=(1ll*getf(n-1,m)*m+1ll*getf(n,m-1)*n-1ll*(n-1)*(m-1)%mod*getf(n-1,m-1)%mod+mod)%mod;
}

int main() {
	memset(f,-1,sizeof(f));
	cin>>a>>b>>c>>d;
	cout<<getf(c,d);
	return 0;
}


Measured memory_bytes: 39404
from math import gcd
def prime_factorize(n):
    a = []
    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 set(a)
  
n = int(input())
a = list(map(int, input().split()))
dic = {}
g = a[0]
flg = True
for i in range(n):
  g = gcd(g, a[i])
  if flg:
    tmp = prime_factorize(a[i])
    for j in tmp:
      if j in dic:
        flg = False
      else:
        dic[j]=1
        
if flg:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")


Measured memory_bytes: 180464
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a,b,c,d;
	cin>>b>>a>>d>>c;
	int num1=ceil(d/float(a));
	int num2=ceil(b/float(c));
	if(num1<=num2)
	 cout<<"Yes";
	else
	 cout<<"No";
	return 0;
	
}

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

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl

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

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

    // input
    int N;
    cin >> N;

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

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

    ll max_score = 0;

    // i : 曲がる場所
    FOR(i, 0, N){
        ll sum = 0;
        FOR(j, 0, N){
            if(j < i){
                sum += A[j];
            }
            else if(j > i){
                sum += B[j];
            }
            else{
                sum += A[j];
                sum += B[j];
            }
        }
        max_score = max(max_score, sum);
    }

    p(max_score);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  
  string s;
  cin>>s;
  
  if(n%2!=0)
    cout<<"No"<<endl;
  else
  {
    int k=n/2;
    if(s.substr(0,k)==s.substr(k,k))
      cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int n,A[20];

int solve(int i,int m);

int main(void){

	int q,i,M;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){ scanf("%d",&A[i]); }
	
	scanf("%d",&q);
    for(i=0;i<q;i++){
		scanf("%d",&M);
		if(solve(0,M) == 1){
			printf("yes\n");
		}else{
			printf("no\n");
		}
	}
	
return 0;
}

int solve(int i,int m){
	if(m == 0) return 1;
	if(i >= n) return 0;
	
	if(solve(i+1,m) || solve(i+1,m-A[i])) return 1;
	
	return 0;
}



Measured memory_bytes: 2104
def run_length(s) -> list:
  res = [[s[0], 1]]
  for i in range(1, len(s)):
    if res[-1][0] == s[i]:
      res[-1][1] += 1
    else:
      res.append([s[i], 1])
  return res

R = run_length(input())
print(len(R) - 1)

Measured memory_bytes: 13300
<?php
# スペース区切りの整数の入力
fscanf(STDIN, "%d %d", $s, $c);

# 出力
$s_c = $s * 2;
$num = 0;
if($c >= $s_c){
  $num = $s;
  $num += floor(($c - $s_c) / 4);
}else{
  $num = floor($c /2);
}  

echo $num;

Measured memory_bytes: 4604
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  
  int N;
  string S;
  cin >> N >> S;

  string ans = "";
  int l = 0,store = 0;
  for(int i = 0;i < N;i++) {
    if(S.at(i) == ')') {
      if(store == 0) l++;
      else store--;
    }else {
      store++;
    }
  }

  for(int i = 0;i < l;i++) ans.push_back('(');
  ans += S;
  for(int i = 0;i < store;i++) ans.push_back(')');

  cout << ans << endl;
}


Measured memory_bytes: 256
package main

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

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var A,B int64 
	fmt.Fscan(reader, &A, &B)
	if (A+B) % 2 == 0 {
		fmt.Fprintln(writer,(A+B)/2)
	} else {
		fmt.Fprintln(writer,"IMPOSSIBLE")
	}
}

Measured memory_bytes: 640
N = int(input())
S = input()
r = []
g = []
b = []
R,G,B = 0,0,0
for s in S:
    if s =='R':
        R += 1
    if s == 'G':
        G += 1
    if s == 'B':
        B += 1
    r.append(R)
    g.append(G)
    b.append(B)
ans = 0
for i in range(len(S)):
    for j in range(i+1,len(S)):
        T = ["R","G","B"]
        if S[i] != S[j]:
            T.remove(S[i])
            T.remove(S[j])
            t = T[0]
            if 0<=2*j-i<len(S) and S[2*j-i]==t:
                ans -=1
            if t =="R":
                # ans += r[i]
                ans += (r[-1]-r[j])
            if t =="G":
                # ans += g[i]
                ans += (g[-1]-g[j])
            if t =="B":
                # ans += b[i]
                ans += (b[-1]-b[j])
print(ans)

Measured memory_bytes: 69120
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
int c(int x){
    if(x==1) x+=13;
    return x;
}
signed main(){
    int a,b;
    cin>>a>>b;
    if(a==1)a+=13;
    if(b==1)b+=13;
    if(a==b)cout<<"Draw"<<endl;
    else if(a>b)cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
    
}

Measured memory_bytes: 256
l = list(map(int, input().split()))
a = l[0]
b = l[1]
c = l[2]
k = l[3]
sum = 0
if k <= a:
    sum = sum + k
else:
    sum = sum + a
    if k-a <=b:
        sum = sum
    else:    
        if k-a-b<c:
            sum = sum - (k-a-b)
        else:
            sum = sum - c
print(sum)            

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

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

    int ans = (n-m) * 100 + m * 1900;
    ans *= pow(2, m);

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

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
   int H,N;
   scanf("%d %d",&H,&N);

   int A[N];
   int i;
   int sum=0;
   for(i=0;i<N;i++){
      scanf("%d",&A[i]);
      sum+=A[i];
   }
   if(sum>=H){
      printf("Yes\n");
   }else{
      printf("No\n");
   }
   return 0;
}


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VLL a(n);
  rep(i,n) cin >> a[i];
  sort(all(a));
  ll ans = 0;
  rep(i,n){
    FOR(j,i+1,n){
      int tmp = a[i] + a[j];
      int idx = lower_bound(all(a), tmp) - a.begin();
      //cerr << tmp << " " << idx << endl;
      ans += max<ll>(0,idx-j-1);
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
a, b, m = map(int,input().split())
a_l = list(map(int,input().split()))
b_l = list(map(int,input().split()))
m_l = []
for i in range(m):
    m_l.append(list((map(int,input().split()))))

m_l.sort(key=lambda x: x[2])
a_l_s = sorted(a_l)
b_l_s = sorted(b_l)
ans = a_l_s[0] + b_l_s[0]

for j in range(m):
    price = a_l[m_l[j][0]-1] + b_l[m_l[j][1]-1] - m_l[j][2]
    if price < ans:
        ans = price

print(ans)

Measured memory_bytes: 40864
/*
	************	************    ************	***      ***	************	***               ***
	************	************    ************	****     ***	************	 ***             ***
	***      ***	***      ***    ***      ***	*****    ***	***      ***	  ***           ***
	***      ***	***      ***    ***      ***	******   ***	***      ***	   ***         ***
	************	************    ************	*** ***  ***	************	    ***       ***
	************	************    ************	***  *** ***	************	     ***     ***
	***				***   ***       ***      ***	***   ******	***      ***	      ***   ***
	***				***    ***      ***      ***	***    *****	***      ***	       *** ***
	***				***     ***     ***      ***	***     ****	***      ***	        *****
	***				***      ***    ***      ***	***      ***	***      ***	         ***
*/

#define named(blockname) goto blockname; \
                         blockname##_skip: if (0) \
                         blockname:

#define break(blockname) goto blockname##_skip
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define readarr(a,n) for (int i=0; i<n; i++) {cin>>a[i];}
#define printarr(a,n) for (int i=0; i<n; i++) {cout<<a[i]<<' ';}
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define vint vector <int>
#define pb push_back
#define pf push_front
#define endl "\n"

signed main() {
	
	fast ;
	
	ll q ;
	// cin >> q ;
	q = 1 ;
	while(q--)
	{
		ll n,k ;
		cin >> n >> k ;
		ll a[n] ;
		readarr(a,n) ;
		ll dp[n] ;
		dp[0] = 0 ;
		// dp[1] = abs(a[1]-a[0]) ;
		for (ll i = 1; i < n; i++)
		{
			dp[i] = dp[i-1]+abs(a[i]-a[i-1]) ;
			for (ll j = 2; j <= k; j++)
			{
				if (i-j>=0)
					dp[i] = min(dp[i], dp[i-j]+abs(a[i]-a[i-j])) ;
			}
			
		}
		cout << dp[n-1] ;
	}
	
	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

template <class Key, class T>
using gp_hash_table = __gnu_pbds::gp_hash_table<Key, T>;

#ifdef ENABLE_DEBUG
template <typename T>
void debug(T value) {
  cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                              \
  do {                                          \
    cerr << " \033[33m (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ":\033[0m ";        \
    debug(__VA_ARGS__);                         \
    cerr << endl;                               \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

// auto mod int

i64 MOD = 1'000'000'007;

struct mint {
  long long x;
  mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD - a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 K;
  cin >> K;
  MOD = K;
  int i = 1;
  mint m = 7;
  gp_hash_table<int, bool> seen;
  for (;; ++i) {
    if (m.x == 0) {
      cout << i << endl;
      return 0;
    }
    if (seen[m.x]) {
      cout << -1 << endl;
      return 0;
    }
    seen[m.x] = true;
    m = m * 10 + 7;
  }
}


Measured memory_bytes: 40340
int main()
{
	int N,M,m[1001],d[1001],p,i;
	for(;scanf("%d%d",&N,&M),N;)
	{
		memset(m,0,sizeof(m));
		for(i=0;i<N;i++)scanf("%d",&m[i]);
		for(i=0;i<M;i++)scanf("%d",&d[i]);
		for(i=p=0;p<N-1;i++)
			p=p+d[i]+m[p+d[i]];
		printf("%d\n",i);
	}
	return 0;
}

Measured memory_bytes: 608
// スタックサイズ: 100MB

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }




int main() {
	fastio;

	ll p, q, r;
	cin >> p >> q >> r;
	cout << min({ p + q, q + r, r + p }) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
const ll ATCODER_AMARI = 1000000007; //10^9 + 7
const ll INF = 10000000000000;

//階乗関数　ATCODER_AMARIに注意
ll factorial(ll k){
  ll sum = 1;
  for(int i = 1 ; i < k + 1; i++) {
    sum *= i;
    //sum = sum % ATCODER_AMARI;
  }
  return sum;
}

int main() {
  ll n;cin >> n;
  vector<ll> a(n); rep(i,n) cin >> a.at(i);

  int sum = 0;
  rep(i,n) {
    sum = sum ^ a.at(i);
  }

  rep(i,n) {
    ll ans = sum ^ a.at(i);
    cout << ans << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 4744
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define double long double
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;



signed main(){
    IOS;
    int x, y;
    cin >> x >> y;
    int flag = ((y >= 2*x) && (4*x >= y) && (y % 2 == 0));
    if (flag ) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int N;  cin >> N;
    for (int i = 0; i < 2; i++){
        if (N % 10 == 9){
            cout << "Yes" << endl;
            return 0;
        }else{
            N /= 10;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <map>
 
using namespace std;
typedef long long ll;

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

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

ll ans,mx,sum,mn=1e8;
int main(){
	ll n;
	cin>>n;
	ll a[n];
	for(ll i=0; i<n; i++){
		cin>>a[i];
	}
	ans=a[0];
	for(ll i=1; i<n; i++){
		ans=lcm(ans,a[i]);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int A = sc.nextInt();
       int B = sc.nextInt();

       int K = (A+B)/2;
       if((A+B)%2==1) {
           System.out.print("IMPOSSIBLE");
    	   
       }else {
           System.out.print(K);
    	   
       }
       
   }
}


Measured memory_bytes: 22612
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		FastReader in = new FastReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		long sum = 0;
		long max = 0;
		for (int i = 0; i < n; i++) {
			int x = in.nextInt();
			sum += x;
			max = Math.max(max, x);
		}
		out.println(sum - (max/2));
		out.flush();
		out.close();

	}

	static class FastReader {
		StringTokenizer st;
		BufferedReader br;

		public FastReader(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public FastReader(FileReader fileReader) {
			br = new BufferedReader(fileReader);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}

}

Measured memory_bytes: 21332