akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
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() {
    ll h, w;
    cin >> h >> w;
    vector<string> a(h), b(w);
    vector<ll> c(h, 1), d(w, 1);
    rep1(i, h){
        cin >> a[i];
        if (a[i]==string(w, '.')) c[i] = 0;
        rep1(j, w){
            b[j] += a[i][j];
        }
    }
    rep1(i, w){
        if (b[i]==string(h, '.')) d[i] = 0;
    }
    rep1(i, h){
        rep1(j, w){
            if (c[i] && d[j]) cout << a[i][j];
        }
        if (c[i]) cout << endl;
    }
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int A,B;
    cin >> A >> B;
    if(A == 1 && B != 1){
        cout << "Alice" << endl;
    }
    else if(A != 1 && B == 1){
        cout << "Bob" << endl;
    }
    else if(A > B){
        cout << "Alice" << endl;
    }
    else if(A < B){
        cout << "Bob" << endl;
    }
    else cout << "Draw" << endl;

}

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

int main() {
    int k,x;
        vector <int> a(k);
    cin >> k>>x;
     for (int i=0;i<2*k-1;i++){
         a.at(i)= x-k+1+i;
         cout << a.at(i)<<" ";
     }

    }





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

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define rep3(n)        for(int i=0;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define eb             emplace_back
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define pres(a,x)      a.find(x)!=a.end()
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC
using namespace std;


template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

const int maxn=2000005;
int p[maxn];
int sz[maxn];
int cnt;
void clear(int n=maxn){
    rep(i,0,maxn)p[i]=i,sz[i]=1;
}
int root(int x){
   while(x!=p[x]){
       p[x]=p[p[x]];
       x=p[x];
   }
   return x;  
}
void merge(int x,int y){
    int p1=root(x);
    int p2=root(y);
    if(p1==p2)return;
    cnt--;
    if(sz[p1]>=sz[p2]){
        p[p2]=p1;
        sz[p1]+=sz[p2];
    }
    else{
        p[p1]=p2;
        sz[p2]+=sz[p1];
    }
}

int solve(){
 	int n;cin>>n;
 	rep3(n)cout<<"ACL";
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#include <queue>
#define int long long
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int sz = s.size();
    vector<int> C(sz+1);
    fill(C.begin(), C.end(), 0);
    int u = 0;
    string ud = "";
    for (int i=0; i < sz; i++){
        if (s[i] == 'x') C[u]++;
        else{
            ud += s[i];
            u++;
        }
    }
    string uud = "";
    int SIZE = ud.size();
    for (int i=SIZE-1; i >= 0; i--){
        uud += ud[i];
    }
    if (ud != uud){
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    for (int i=0; i < u-i; i++){
        ans += abs(C[i] - C[u-i]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1488
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=a.copy()
b.insert(0,0)

#連続する重複を除外
arr=np.array(b)
diff=np.diff(arr)
arr2=np.array(a)
aa=arr2[np.nonzero(diff)]

aaa=aa.tolist()
point=[]
cnt=1
if len(aaa)<=2:
    print(1)
else:
    for i in range(len(aaa)-2):
        if (aaa[i+1]-aaa[i])*(aaa[i+2]-aaa[i+1])<0:
            cnt+=1
            point.append(i)
    
    if len(point)>1:
        for i in range(1,len(point)):
            if point[i]-1==point[i-1]:
                point[i]-=1
                cnt-=1
    print(cnt)

Measured memory_bytes: 26592
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
using namespace std;
using ll=long long;
const ll MOD=1000003;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=b-1;i>=a;i--)
#define range(i) (i).begin(),(i).end()
#define rrange(i) (i).rbegin(),(i).rend()
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans%MOD*(b&1?a:1)%MOD;
}
inline constexpr int modf(ll n){
    ll ans=1;
    rep(i,0,n) {ans=ans*(n-i)%MOD;}
    return ans;
}
inline long double median(vector<ll> v){
    ll size=v.size();
    sort(v.begin(),v.end());
    if (size % 2 == 1) return v[(size - 1) / 2];
    else return v[(size / 2) - 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;}
template<class T,class L>ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}

int main(){
  ll n,x;
  cin>>n>>x;
  ll d=0;
  vector<ll> l(n);
  rep(i,0,n) cin>>l[i];
  ll cnt=0;
  while(d<=x&&cnt<n+1){
    d+=l[cnt];
    cnt++;
  }
  cout<<cnt;
}


Measured memory_bytes: 256
M = 1_000_000_007

S = gets.strip

a   = 0
ab  = 0
abc = 0
t   = 1 # total

S.chars.each do |c|
  case c  
  when 'A'
    a = (a + t) % M
  when 'B' 
    ab = (ab + a) % M 
  when 'C'
    abc = (abc + ab) % M  
  else
    abc = (abc * 3 + ab) % M
    ab  = (ab * 3 + a) % M
    a   = (a * 3 + t) % M 
    t   = (t * 3) % M
  end
end
puts abc


Measured memory_bytes: 6908
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define pb push_back
ll power(ll a,ll x){if(x==0) return 1;ll y=power(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
ll inv(ll a){return power(a,mod-2);}

#define N 100005
vector< ll> adj[N];
int vis[N];


void dfs(int curr,int pt){
 
  vis[curr]=1;

   for(auto i: adj[curr]){
      if(vis[i]==0){
        if(i!=pt){
           dfs(i,curr);
        }
       } 
   }

}
 int main(){

 ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
  

  ll n,f;
  cin>>n>>f;
  for(int i=1;i<=f;i++){
     ll x,y,z;
     cin>>x>>y>>z;
        adj[x].push_back(y);
        adj[y].push_back(x);     
   }
   int ct=0;
   memset(vis,0,sizeof(vis));
   for(int i=1;i<=n;i++){
       if(vis[i]==0){
            dfs(i,-1);
            ct++;
       }
   }

   cout<<ct<<endl;

 

}

Measured memory_bytes: 10752
import kotlin.math.*
import java.util.*
import java.io.*
fun main() {
    val A = readLine()!!.split(" ").map { it.toInt() }
    val N = A[0]
    val X = A[1]
    val T = A[2]
    if(N%X == 0){
        println(( N / X ) * T)
    }
    else{
    println((N / X + 1) * T)
    }
}

Measured memory_bytes: 36344
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int t, n;
  int dx[] = {0,1,1,0,-1,-1};
  int dy[] = {1,1,0,-1,-1,0};
  
  while(cin>>t>>n, t||n) {
    bool ba[200][200];
    memset(ba,0,sizeof(ba));
    REP(i,n) {
      int x, y;
      cin >>x>>y;
      ba[x+100][y+100] = 1;
    }
    int sx, sy;
    cin >> sx>>sy;
    typedef pair<int,int> pii;
    typedef pair<int, pii> piii;
    queue<piii> Q;
    Q.push(piii(0,pii(sx+100,sy+100)));

    bool visited[200][200] = {};
    int res = 0;
    while(!Q.empty()) {
      int x = Q.front().second.first;
      int y = Q.front().second.second;
      int d = Q.front().first;

//      cout << x << " " <<y<< endl;

      Q.pop();
      
      if (d > t) break;
      if (visited[x][y]) {
        continue;
      }

      visited[x][y] = 1;
      res++;
      REP(k,6){
        int xx =x+dx[k];
        int yy = y+dy[k];
        
        if (ba[xx][yy]||visited[xx][yy]) continue;
        Q.push(piii(d+1,pii(xx,yy)));
        //   cout << xx << " " <<yy << endl;
      }
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1004
x = int(input())
li = []
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*3 for _ in range(x+1)]
for i in range(x):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i+1][j] = max(dp[i][k]+li[i][j], dp[i+1][j])
print(max(max(dp[x][0], dp[x][1]), max(dp[x][1], dp[x][2])))

Measured memory_bytes: 74072
#include <vector>
#include <list>
#include <map>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <utility>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll mod = 1000000007;

ll solve(void);

int main(void)
{
	while (solve())
	{
	}
	return 0;
}

ll solve(void)
{
	ll n;
	cin >> n;

	for (ll i = 1; i <= 9; i++)
	{
		if (n % i == 0)
		{
			if (n / i < 10)
			{
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 256
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

    vi pos,neg;
    for(int i=0;i<n;++i)
    {
        int x;
        cin>>x;

        if(x<=0)
            neg.pb(x);
        else
            pos.pb(x);
    }

    sort(all(neg));
    sort(all(pos));

    int ans=abs(accumulate(all(neg),0))+accumulate(all(pos),0);
    if(!sz(neg))
    {
        ans-=2*pos[0];
        cout<<ans<<"\n";

        int cur=pos[0];
        for(int i=1;i<sz(pos)-1;++i)
        {
            cout<<cur<<" "<<pos[i]<<"\n";
            cur-=pos[i];
        }

        cout<<pos.back()<<" "<<cur<<"\n";
        return;
    }

    if(!sz(pos))
    {
        ans+=2*neg.back();
        cout<<ans<<"\n";

        int cur=neg.back();
        for(int i=n-2;i>=0;--i)
        {
            cout<<cur<<" "<<neg[i]<<"\n";
            cur-=neg[i];
        }

        return;
    }

    cout<<ans<<"\n";

    int a=neg[0];
    for(int i=1;i<sz(pos);++i)
    {
        cout<<a<<" "<<pos[i]<<"\n";
        a-=pos[i];
    }

    int b=pos[0];
    for(int i=1;i<sz(neg);++i)
    {
        cout<<b<<" "<<neg[i]<<"\n";
        b-=neg[i];
    }

    cout<<b<<" "<<a<<"\n";
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 2804
get~~m:g/\d+/;
my$a=lines;
for 0..$0-$1 X 0..$0-$1 ->($i,$j) {
	my$f=1;
	for ^$1 ->$k {if !$a[$i+$k].substr-eq($a[$0+$k],$j) {$f=0;last;}}
    if $f {say "Yes";exit}
}
say "No"

Measured memory_bytes: 80620
import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun solve() {
    val (N, Q) = rd.readIntArray()
    val hs = IntArray(N){0}
    for (i in 0 until Q) {
        val (a, b) = rd.readIntArray().map{ it-1 }
        hs[a]++
        hs[b]++
    }

    var ans = "YES"
    for (i in 0 until N) {
        if (hs[i]%2 != 0) {
            ans = "NO"
            break
        }
    }

    println(ans)
}


//val rd = debug.Reader("agc", "014", "b", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!!
    } catch (e: Exception) { throw e }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
data class IntPair(val first: Int, val second: Int); data class LongPair(val first: Long, val second: Long)
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
}


Measured memory_bytes: 59476
package main

import "fmt"

func main() {

	var a string
	fmt.Scan(&a)

	if a == "SUN" {
		fmt.Println(7)
	} else if a == "MON" {
		fmt.Println(6)
	} else if a == "TUE" {
		fmt.Println(5)
	} else if a == "WED" {
		fmt.Println(4)
	} else if a == "THU" {
		fmt.Println(3)
	} else if a == "FRI" {
		fmt.Println(2)
	} else if a == "SAT" {
		fmt.Println(1)
	}

}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <numeric>



int main() {
	std::string s;

	std::cin >> s;

	std::sort(s.begin(), s.end());

	if (s.length() != 4) {
		std::cout << "No" << std::endl;
	}

	if (s[0] == s[1] && s[2] == s[3] && s[1] != s[2]) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
	
	return 0;
}

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

int main(void){

    int i,j;
    int N,K;
    int u,l;
    char A[4]; 

    scanf("%s",&A);
    N = atoi(A);
    u=N/100;
    l=N%100;

    if(u<=12&&u>0){
        if(l<=12&&l>0){
            printf("%s","AMBIGUOUS");
        }else{
            printf("%s","MMYY");
        }
    }else{
        if(l<=12&&l>0){
            printf("%s","YYMM");
        }else{
            printf("%s","NA");
        }
    }

    return 0;
}


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

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

#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, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/27  Problem: 074_arc_b / Link: https://abc062.contest.atcoder.jp/tasks/arc074_b?lang=en  ----- */
/* ------問題------

N を 1 以上の整数とします。
長さ 3N の数列 a=(a1,a2,…,a3N) があります。 すぬけ君は、a からちょうど N 個の要素を取り除き、残った 2N 個の要素を元の順序で並べ、長さ 2N の数列 a' を作ろうとしています。 このとき、a' のスコアを (a'の前半N要素の総和)−(a'の後半N要素の総和) と定義します。
a' のスコアの最大値を求めてください。

-----問題ここまで----- */
/* -----解説等-----

priority_queueのやつ
両側から区間を作っていくとできる
dp1[i]:= iまでを使ってできる最大値
dp2[i]:= i以降を使ってできる最小値
探索区間は[N-1,2*N)なのでN-1を忘れない(戒め)

----解説ここまで---- */

LL N;

LL ans = 0LL;

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

	cin >> N;
	VI a(3 * N);
	FOR(i, 0, 3 * N) {
		cin >> a[i];
	}

	VL dp1(3 * N, 0);
	{
		priority_queue<int, VI, greater<int>>pq;
		LL sum = 0;
		FOR(i, 0, 3 * N) {

			sum += a[i];
			pq.push(a[i]);
			if (SZ(pq)== (N + 1)) {
				LL val = pq.top(); pq.pop();
				sum -= val;
			}
			dp1[i] = sum;
		}
		//FOR(i, 0, 3 * N) {
		//	cout << dp1[i] << " ";
		//}cout << endl;
	}
	VL dp2(3 * N, 0);
	{
		priority_queue<int>pq;
		LL sum = 0;
		FORR(i, 3*N-1, 0-1) {

			sum += a[i];
			pq.push(a[i]);
			if (SZ(pq) ==(N + 1)) {
				LL val = pq.top(); pq.pop();

				sum -= val;
			}
			dp2[i] = sum;
		}
		//FOR(i, 0, 3 * N) {
		//	cout << dp2[i] << " ";
		//}cout << endl;
	}
	ans = -LINF;
	FOR(i, N-1, 2 * N) {
		ans = max(ans, dp1[i] - dp2[i+1]);
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 7028
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.container;
import std.bigint;
import std.math;

void main()
{
	readln;
	auto x = readln.chomp.split.map!(to!long).array;
	writeln(x.reduce!(min), " ", x.reduce!(max), " ", x.reduce!("a+b"));
}

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++ i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")

using ll = std::int64_t;
using vint = std::vector<std::int32_t>;
using vll = std::vector<ll>;
using vstr = std::vector<std::string>;
using pint = std::pair<std::int32_t, std::int32_t>;
using usetint = std::unordered_set<std::int32_t>;
using usetstr = std::unordered_set<std::string>;

constexpr std::int32_t INF = 1001001001;

void Main() {
    int n;
    cin >> n;
    int odd = 0;
    int even = 0;
    for(int i = 1; i <= n; ++i){
        if (i % 2 == 1)++odd;
        else ++even;
    }
    cout << (double)odd / (odd + even) << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <functional>
#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;
const int MOD = 1000000007;


typedef long long int ll; 
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

void floatOutPutSetup(){
    cout << fixed;
    cout << setprecision(10);
}

int main(){
    int n,m,t;
    cin>>n>>m>>t;
    vector<int> a(n);
    vector<bool> o(t+1,true);
    o[0]=false;
    rep(i,n){
        cin>>a[i];
    }
    
    rep(i,n){
        int base = a[i];
        // cout<<base;
        rep(j,m){
            o[base-j]=false;
            if(base+j<=t){
                o[base+j+1]=false;
            }
        }
    }



    int ans=0;
    rep(i,t+1){
        if(o[i]){ans++;}
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3120
#include<stdio.h>
#include<math.h>



int main(void){
	
	int n,i,tmp;
	int z,m=0;
	int j=3;
	
	scanf("%d",&n);
	
	int a[10000];
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(i=0;i<=n-1;i++)
	{
		if(a[i]==2){m++;}
		else if(a[i]&1){
		for(j=3;;j+=2)
		 { 
		 	if(j>(int)sqrt(a[i]))
		 	{m++;
		 	break;}
		 	if(a[i]%j==0){break;}
		 	
		 
		}
		}
	}
	printf("%d\n",m);
	return 0;
}


Measured memory_bytes: 2100
import sys

S = input()

# 2^n-1の2進数は全組み合わせを表す
combs = pow(2, len(S) - 1)
if len(S) == 1:
    print(S)
    sys.exit()

total = 0
for i in range(combs):
    # i番目の組み合わせ（2進数）
    comb_i = format(i, '0' + str(len(S)) + 'b')
    if len(comb_i) > 1:
        comb_i = comb_i[1:]

    tmp = S[0]
    for j in range(len(comb_i)):
        b = int(comb_i[j])
        if b == 1:
            tmp += "+"
        tmp += S[j + 1]
    total += eval(tmp)
print(total)



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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define line cout << __LINE__;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
#define sp cout << " ";
#define dbg2(a,b) cerr << #a << " = " << a << " " << #b << " = " << b << '\n';        
#define debug(x) cerr << __LINE__ << ' ' << #x << " = " << x << '\n';

typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;


clock_t time_p = clock();

void ktj(){
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (float)(time_p)/CLOCKS_PER_SEC << "\n";
}

const ll N = 1e5 + 4;
vl g[2 * N];
bool vis[2 * N];
void dfs(ll v, vl &cnt){
  if(vis[v])
    return;
  vis[v] = 1;
  cnt[v / N]++;
  for(auto c : g[v]){
    if(!vis[c]){
      dfs(c,cnt);
    }
  }
}

int main(){
  fastio
  ll n,i,j;
  cin >> n;
  ll x,y;
  forn(0,n,i){
    cin >> x >> y;
    y += N;
    g[x].pb(y);
    g[y].pb(x);
  }
  ll ans = 0;
  forn(0,2 * N,i){
    if(!vis[i]){
      vl cnt(2,0);
      dfs(i,cnt);
      ans += cnt[0] * cnt[1];
    }
  }
  ans -= n;
  cout << ans << '\n';

  ktj();
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  constexpr ModInt() : v(0) {}
  constexpr ModInt(auto x) : v(x >= 0 ? x % P : (P - -x % P) % P) {}
  constexpr ModInt(unsigned v, int) : v(v) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool)*this; }
  M operator*(M r) const { return M(*this) *= r; }
  M operator/(M r) const { return M(*this) /= r; }
  M operator+(M r) const { return M(*this) += r; }
  M operator-(M r) const { return M(*this) -= r; }
  bool operator==(M r) const { return v == r.v; }
  bool operator!=(M r) const { return !(*this == r); }
  M& operator*=(M r) { v = (uint64_t)v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= P) v -= P; return *this; }
  M& operator-=(M r) { if ((v += P - r.v) >= P) v -= P; return *this; }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  M pow(auto n) const {
    if (n < 0) return pow(-n).inv();
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  friend M operator*(auto l, M r) { return M(l) *= r; }
  friend M operator/(auto l, M r) { return M(l) /= r; }
  friend M operator+(auto l, M r) { return M(l) += r; }
  friend M operator-(auto l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend istream& operator>>(istream& is, M& r) { lint x; is >> x; r = x; return is; }
  friend bool operator==(auto l, M r) { return M(l) == r; }
  friend bool operator!=(auto l, M r) { return !(l == r); }
};
using Mint = ModInt<(unsigned)1e9 + 7>;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  string s, t; cin >> s >> t;
  int n = s.size();
  VV<Mint> dp(n + 1, V<Mint>(2));
  VV<Mint> sum(n + 1, V<Mint>(2));
  dp[0][1] = 1;
  for (int i = 0; i < n; ++i) {
    for (int f = 0; f < 2; ++f) for (int d = 0; d < 10; ++d) if (t[i] == '?' or t[i] - '0' == d) {
      if (f == 1 and d > s[i] - '0') continue;
      dp[i + 1][f and d == s[i] - '0'] += dp[i][f];
      sum[i + 1][f and d == s[i] - '0'] += sum[i][f] * 10 + d * dp[i][f];
    }
  }
  cout << sum[n][0] + sum[n][1] << '\n';
}


Measured memory_bytes: 25140
import numpy as np

N, K, Q = map(int, input().split())
A = np.ones(N) * (K-Q)
for _ in range(Q):
    a = int(input())
    A[a-1] += 1

for i in A:
    if i <= 0:
        print('No')
    else:
        print('Yes')


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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)

ll n,m;


int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
   
 cin >> n >> m;
  
  cout << (n*(n-1)+m*(m-1))/2 << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#define ll long long int
#define N 55
using namespace std;
char s[N][N];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int a,b;
 
bool search(int x,int y){
    for(int i=0;i<4;i++){
        int xx = x+dir[i][0];
        int yy = y+dir[i][1];
        if(xx>=0&&xx<a&&y>=0&&y<b){
            if(s[xx][yy]=='#')
                return true;
        }
    }
    return false;
}
int main(){
    cin>>a>>b;
    for(int i=0;i<a;i++)
        for(int j=0;j<b;j++)
            cin>>s[i][j];
    for(int i=0;i<a;i++){
        for(int j=0;j<b;j++){
            if(s[i][j]=='#'){
                bool prime = search(i,j);
                if(!prime){
                    return 0*printf("No\n");
                }
            }
        }
    }
    printf("Yes\n");
    return 0;
}

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, Q = MAP()

# 2次元累積和
# acc[i][j] := 都市iで区間開始前で都市jで区間終了後である列車の数
acc = list2d(N, N, 0)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    acc[l][r] += 1
# 区間開始前かどうかを持つ1次元目は後ろから累積和する
for j in range(N):
    for i in range(N-2, -1, -1):
        acc[i][j] += acc[i+1][j]
for i in range(N):
    acc[i] = list(accumulate(acc[i]))

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    print(acc[p][q])


Measured memory_bytes: 9996
import sys
n = int(input())
kind = set(list("abcdefghijklmnopqrstuvwxyz"))
S = str(input())
kind = set(S)
dic = {}
for k in kind:
    dic[k] = S.count(k)

for i in range(n-1):
    S = str(input())
    kind = set(S) & kind
    for k in kind:
        dic[k] = min(S.count(k),dic[k])

kind = sorted(list(kind))
ans = ""
for a in kind:
    ans += a*dic[a]
print(ans)


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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define REP(i,N) for(int i=0;i<N;i++)

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

    vector<int> l(n,0);
    for(int i=0;i<n;i++){
        cin>>l[i];
    }
    
    vector<int> c(n+1,0);
    int i=1;
    for(i=1;i<=n;i++){
        c[i] = c[i-1] + l[i-1];
        if(x<c[i])
            break;
    }
    cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())

total_set = {0}
for i in range(K):
    d = int(input())
    A_set = set(map(int, input().split()))
    total_set = total_set | A_set

sunuke_set = {i for i in range(N+1)}

answer_set = sunuke_set - total_set
print(len(answer_set))

Measured memory_bytes: 9140
#include <climits>
#include <cmath>
#include <iostream>
#include <cstring>

int32_t memo[110000];
int32_t Solve(uint64_t N) {
  if (N == 0) {
    return 0;
  }
  if (memo[N] != -1) {
    return memo[N];
  } else if (N < 6) {
    return memo[N] = N;
  }

  int32_t ret = N;
  for (uint64_t i = 1; i <= N; i *= 6) {
    ret = std::min(ret, Solve(N - i) + 1);
  }

  for (uint64_t i = 1; i <= N; i *= 9) {
    ret = std::min(ret, Solve(N - i) + 1);
  }

  return memo[N] = ret;
}

int main() {
  int N;
  std::cin >> N;

  std::memset(memo, -1, sizeof memo);

  std::cout << Solve(N) << std::endl;

  return 0;
}


Measured memory_bytes: 3840
#include <iostream>

int main() {
    int N, M;
    std::cin >> N >> M;

    int left, right;

    left = 1;
    right = M;
    while (left < right) {
        std::cout << left << " " << right << "\n";
        left++;
        right--;
    }

    left = M + 1;
    right = M * 2 + 1;
    while (left < right) {
        std::cout << left << " " << right << "\n";
        left++;
        right--;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 2e5 + 12, bs = 500;
const ll inf = 1e9;
const double EPS = 0.000001;

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

	ll a, b, c;
	cin >> c >> b >> a;
	ll k;
	cin >> k;
	while(k && b <= c){
		k -= 1;
		b *= 2;
	}
	while(k && a <= b){
		k -= 1;
		a *= 2;
	}

	if(a > b && b > c){
		cout << "Yes";	
	}
	else{
		cout << "No";
	}
}

Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <complex>
using namespace std;

typedef complex<double> point;
int main(void){
	double x,y;
	int q;
	cin>>x>>y;
	point p1(x,y);
	cin>>x>>y;
	point p2(x,y);
	cin>>q;
	while(q--){
		cin>>x>>y;
		point p(x,y);
		point p1p=p-p1; // vector p1->p
		point p1p2=p2-p1; // vector p1->p2
		double r=abs(p1p);
		double t=arg(p1p)-arg(p1p2);
		point res=polar(r*cos(t),arg(p1p2))+p1;
		res+=res-p;
		printf("%.8lf %.8lf\n",real(res),imag(res));
	}
	return 0;
}

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

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

Node *root, *NIL;

void insert(int k){
	Node *y = NIL;
	Node *x = root;
	Node *z;
	
	z = (Node *)malloc(sizeof(Node));
	
	z->key = k;
	z->left = NIL;
	z->right = NIL;
	
	while(x != NIL){
		y = x;
		if(z->key < x->key){
			x = x->left;
			}else{
				x = x->right;
			}
		}
		
		z->parent = y;
		
		if(y == NIL){
			root = z;
		}else{ 
			if(z->key < y->key) y->left = z;
			else y->right = z;
		}
	}
		
Node* find(Node *u, int k) {
	while(u != NIL && k != u->key) {
		if(k < u->key) u = u->left;
		else u = u->right;
	}
	
	return u;
	
}
		
void inorder(Node *u){
	if(u == NIL) return;
	inorder(u->left);
	cout << " " << u->key;
	inorder(u->right);
}
 
void preorder(Node *u){
	if(u == NIL) return;
	cout << " " << u->key;
	preorder(u->left);
	preorder(u->right);
}
		
int main(){
	int n, a;
	string status;
	
	cin >> n;
	
	for(int i = 0 ; i < n ; i++){
		cin >> status;
		if(status == "insert"){
			cin >> a;
			insert(a);
			}
		else if(status == "print"){
			inorder(root);
			cout << endl;
			preorder(root);
			cout << endl;
			}
		else if(status == "find"){
			cin >> a;
			if(find(root, a) != NIL) cout << "yes" <<endl;
			else cout << "no" <<endl;
			}
		}
	
	return 0;
	
}

Measured memory_bytes: 19960
/*
   Created by Rahul Goel.
*/

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
ll mod = 1000000007;
const int INF = 1e9;
const ll LINF = 1e18;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c) (c).begin(), (c).end()
#define pii pair < ll, ll >
#define vi vector < ll >
#define vb vector < bool >
#define vvi vector < vector < ll > >
#define vvb vector < vector < bool > >
#define vpii vector < pair < ll, ll > >
#define vvpii vector < vector < pair < ll, ll > > >
#define pb push_back
#define f first
#define s second
#define mp make_pair

ll solve(){
    map<string, int> mapper;
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
        mapper[str] = 1;
    }
    cout << mapper.size() << endl;
    return 0;
}

int main(){
    fastio;

    ll t = 1;
    while(t--)
        solve();

    return 0;
}


Measured memory_bytes: 19140
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

const Int MOD = 1e9+7;

Int calc(Int n,vector<Int> a){
  vector<Int> c(5,0),s(5,0);
  for(Int i=0;i<n;i++){
    c[to_string(a[i]).size()]++;
    s[to_string(a[i]).size()]+=a[i];
  }
 
  auto P=make_v<Int>(n+1,n+1);
  fill_v(P,0);
  for(Int i=0;i<=n;i++){
    for(Int j=0;j<=i;j++){
      P[i][j]=1;
      for(Int k=0;k<j;k++)
	P[i][j]=P[i][j]*(i-k)%MOD;
    }
  }
  vector<Int> dp2(n+1,0);
  for(Int i=0;i<=n;i++){
    for(Int j=0;j<=i;j++){
      dp2[i]+=P[i][j];
      dp2[i]%=MOD;
    }
  }
  
  vector<Int> fact(n+1,1);
  for(Int i=0;i<n;i++) fact[i+1]=fact[i]*(i+1)%MOD;
  vector<Int> po(n*4+1,1);
  for(Int i=0;i<n*4;i++) po[i+1]=po[i]*10%MOD;
  
  Int ans=0;
  for(Int d=1;d<=4;d++){
    if(!c[d]) continue;
    c[d]--;
    auto dp=make_v<Int>(n+1,n*4+1);
    fill_v(dp,0);
    dp[0][0]=1;
    for(Int a=1;a<=4;a++){
      for(Int x=0;x<c[a];x++){
	for(Int i=n;i>=0;i--){
	  for(Int j=n*4;j>=0;j--){
	    Int ni=i+1,nj=j+a;
	    if(ni<=n&&nj<=n*4){
	      dp[ni][nj]+=dp[i][j];
	      dp[ni][nj]%=MOD;
	    }
	  }
	}
      }
    }
    c[d]++;
    for(Int i=0;i<n;i++){
      for(Int j=0;j<=4*n;j++){
	Int tmp=dp[i][j]*fact[i]%MOD;
	Int k=n-(i+1);
	tmp*=dp2[k];	
	tmp%=MOD;
	
	tmp*=po[j];
	tmp%=MOD;

	tmp*=s[d];
	tmp%=MOD;
	
	ans+=tmp;
	ans%=MOD;
	
	if(0&&dp[i][j])
	  cout<<i<<":"<<dp[i][j]<<" "<<dp2[k]<<" "<<po[j]<<" "<<s[d]<<":"<<tmp<<endl;	
      }
    }
  }
  return ans;
}

signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  sort(a.rbegin(),a.rend());
  Int ans=calc(n,a);
  //cout<<ans<<endl;
  if(a.back()==0){
    a.pop_back();
    n--;
    ans+=MOD-calc(n,a);
    ans%=MOD;
  }
  cout<<ans<<endl;
  return 0;
}




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

A.insert(0, 0)
A.append(0)

B = []
for i in range(len(A)-1):
    B.append(abs(A[i+1] - A[i]))

total = sum(B)

for i in range(N):
    a = abs(A[i+2]-A[i+1]) + abs(A[i+1]-A[i])
    b = abs(A[i+2]-A[i])
    print(total - a + b)


Measured memory_bytes: 14048
from collections import deque

n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
ans = [-1] * (n - 1)
used = [0]*n
used[0] = 1
que = deque([0])
while que:
    posi = que.popleft()
    for p in graph[posi]:
        if not used[p]:
            que.append(p)
            ans[p-1] = posi+1
            used[p] = 1
print('Yes')
print(*ans, sep='\n')

Measured memory_bytes: 39372
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define all(x) (x.begin()),(x.end())
#define allr(x) (x.rbegin()),(x.rend())
#define sz(x)  ((ll)x.size())
#define FAST_IO ios_base :: sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
#ifdef LOCAL
#include "uj.h"
#endif


void tokenize(string str,const char delim,vector<string> & res){
	stringstream p(str);
	string token;
	while(getline(p,token,delim)){
		res.push_back(token);
	}
	return;
}
// Your workSpace ...
const int inf = 1e9;
int n;
int k;

void test_case(){
  	cin>>n>>k;
  	vector<int> v(n);
  	for(auto & el : v){
  	    cin>>el;
  	}
  	vector<long> dp(n,inf);
  	dp[0] = 0;
  	for(int i = 1;i<n;++i)
		for(int j = i-1;j>=0 && j>=i-k;--j)
		    dp[i] = min(dp[i],dp[j]+abs(v[i]-v[j]));
	cout<<dp[n-1]<<endl;
	return;
}




int main(){
	FAST_IO;
	int tt ;
	tt = 1;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    cin>>tt;
#endif
	for(int i = 0;i<tt;++i)
	    test_case();
#ifndef ONLINE_JUDGE
 	cerr << "Running Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 4532
require 'mathn'

n, d = gets.split.map(&:to_i)
x = []
n.times do
  x << gets.split.map(&:to_i)
end

ans = 0
(0..n -1).to_a.combination(2) do |c|
  i = c[0]
  j = c[1]
  next unless i < j

  dist = 0
  d.times do |k|
    dist += (x[i][k] - x[j][k]) ** 2
  end
  ans += 1 if Math.rsqrt(dist).kind_of?(Integer)
end

puts ans


Measured memory_bytes: 3196
#include <cstdio>
#include <map>
using namespace std;

map<pair<int, int>, int> M;
int prt_rd[222222], prt_rw[222222];

int Find_rd(int val)
{
    if (prt_rd[val] == val)
        return val;
	else
		return prt_rd[val] = Find_rd(prt_rd[val]);
}

int Find_rw(int val)
{
	if (prt_rw[val] == val)
        return val;
	else
		return prt_rw[val] = Find_rw(prt_rw[val]);
}

int main(void)
{
    int N, K, L, p, q, r, s, i, j;

    scanf("%d %d %d" ,&N, &K, &L);
    for (i = 1; i <= N; i++)
        prt_rd[i] = prt_rw[i] = i;

	while (K--)
	{
        scanf("%d %d" ,&p, &q);

		p = Find_rd(p);
		q = Find_rd(q);

        if (p != q)
			prt_rd[q] = p;
	}

	while (L--)
	{
		scanf("%d %d" ,&r, &s);

		r = Find_rw(r);
		s = Find_rw(s);

		if (r != s)
			prt_rw[s] = r;
	}

    for (i = 1; i <= N; i++)
	{
		int p = Find_rd(prt_rd[i]), q = Find_rw(prt_rw[i]);

        M[make_pair(p, q)]++;
	}

	for (i = 1; i <= N; i++)
	{
		int p = Find_rd(prt_rd[i]), q = Find_rw(prt_rw[i]);

        printf("%d " ,M[make_pair(p, q)]);
	}
	return 0;
}

Measured memory_bytes: 13568
#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>=(b)?(a):(b))
int s[100001],n,k;
int main() {
	while(scanf("%d %d",&n,&k),n|k) {
		int ans=0;
		memset(s,0,sizeof(s));
		for(int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]+=s[i-1];
		for(int i=1;i<=(n-k);i++) ans=max(ans,s[i+k-1]-s[i-1]);
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 1424
package main

import (
	"fmt"
	"math"
)

var N, A, B, C int
var RE = 1000000000
var arr []int

func main() {
	fmt.Scan(&N, &A, &B, &C)
	arr = make([]int, N)
	for i := 0; i < N; i++ {
		var tmp int
		fmt.Scan(&tmp)
		arr[i] = tmp
	}
	pattern := make([]int, N, N)
	dfs(0, pattern)
	fmt.Println(RE)
}

// 選択肢 = 4 (A, B, C, 何も選ばない) と、何個の竹があるか (N)
// 4^N バターンについて考えればいい
// 下記でNまでの深さの木を作っている
func dfs(depth int, arr []int) {
	if depth == N {
		calc(arr)
		return
	}
	for i := 0; i < 4; i++ {
		arr[depth] = i
		dfs(depth+1, arr)
	}
}

func calc(v []int) {
	var cost, a, b, c, asum, bsum, csum, tmp int
	for idx, item := range v {
		switch item {
		// A使う
		case 0:
			a++
			asum += arr[idx]
		// B使う
		case 1:
			b++
			bsum += arr[idx]
		// C使う
		case 2:
			c++
			csum += arr[idx]
		// 使わない
		case 3:
			tmp += arr[idx]
		}
	}
	// a, b, c に当てはまるものがない場合は、正当な結果が得られないのでskip
	if a == 0 || b == 0 || c == 0 {
		return
	}
	addSum := (a-1)*10 + (b-1)*10 + (c-1)*10
	cost = addSum + abs(A-asum) + abs(B-bsum) + abs(C-csum)
	if RE > cost {
		RE = cost
	}
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}


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

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

const int MAXN = 1 << 18; // 2.6e5
int N = 200000;
ll seg[2 * MAXN]; // root is seg[1]

void update(int p, ll val)
{
    for (seg[p += N] = val; p > 0; p >>= 1)
        seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}

ll query(int l, int r) // [l, r]
{
    ll res = 0;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            res = max(res, seg[l++]);
        if (!(r & 1))
            res = max(res, seg[r--]);
    }
    return res;
}

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

    int n;
    cin >> n;
    vi a(n),h(n);
    for(int i=0; i<n; i++)
        cin >> h[i];
        
    for(int i=0; i<n; i++)
        cin >> a[i];

    for(int i=0; i<n; i++){
        update(h[i], query(1,h[i]-1)+a[i]);
    }
    cout << query(1,N);
}

Measured memory_bytes: 5888
#include <iostream>
#include <cstdio>
#include <string>
#include <bits/stdc++.h>
#include <set>
#include <list> //list<???> a; a.push_back ,insert(追加したい要素),a.sort(),参照できない
#include <vector> //vector<???> a; a.push_back,sort(a.begin(),a.end());a[i]
//配列 int a[N];a[i]=追加したい要素;sort(a,a+N);a[i]
const int MOD = 1e9+7;
using namespace std;
typedef long  ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const long long mod=1e9+7;


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


  vector<int>oks(N+1,true);
  for(int i=0;i<M;i++){
    int a;cin>>a;
    oks[a]=false;
  }

  vector<long long int>dp(N+1);
  dp[0]=1;
  for(int now=0;now<N;now++){
    for(int next=now+1;next<=now+2;next++){
      if(oks[next]){
        dp[next]+=dp[now];
        dp[next]%=mod;
      }
    }
  }


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

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

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;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}

//vc alp(26) ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  int A,B,C,D;cin>>A>>B>>C>>D;
  cout<<min(A,B)+min(C,D)<<endl;
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  	int x,y;
	cin >> x >> y; 
 	if(x>=0&&y>=0)
      	cout << ((x<y) ? y-x : min(1+x+y,2+x-y))<< endl;
  	else if(x<0 && y < 0) 
      	cout << (abs(x)<abs(y) ? 2+x-y : y-x ) << endl;
  	else if(x<0&&y>=0)
      	cout << (abs(x)<=abs(y) ? 1+y+x  : min(1-y-x, y-x)) << endl;
  	else
      	cout << (abs(x)<=abs(y) ? 1-y-x : 1+x+y) << endl;
}


Measured memory_bytes: 256
def print_node(i, node):
    parent = -1 if node[1] == None else node[1]
    degree = len([x for x in node[0] if x != -1])
    sibling = -1 if node[2] == None else node[2]
    depth = node[3]
    height = node[4]
    t = 'root' if parent == -1 else 'leaf' if height == 0 else 'internal node'
    ans = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i, parent, sibling, degree, depth, height, t)
    print(ans)

n = int(input())

root = set([x for x in range(n)])
T = [None] * n
for x in range(n):
    i, l, r = list(map(int, input().split()))

    # children, parent, sibling, depth, height
    T[i] = [[l, r], None, None, None, None]
    root -= set([l, r])

def set_info(i, depth):
    node = T[i]
    node[3] = depth
    l = None
    r = None
    if node[0][0] != -1:
        l = T[node[0][0]]
        l[1] = i
        set_info(node[0][0], depth + 1)
    if node[0][1] != -1:
        r = T[node[0][1]]
        r[1] = i
        set_info(node[0][1], depth + 1)
    if l != None and r != None:
        l[2] = node[0][1]
        r[2] = node[0][0]

    node[4] = height(i)

def height(i):
    node = T[i]
    l = node[0][0]
    r = node[0][1]
    lh = None
    rh = None
    h = None
    if l != -1:
        lh = height(l)
    if r != -1:
        rh = height(r)
    if lh != None and rh != None:
        h = max(lh, rh)
    elif lh != None:
        h = lh
    elif rh != None:
        h = rh
    if h == None:
        return 0
    else:
        return 1 + h


r = root.pop()
T[r][1] = -1
set_info(r, 0)

for i, n in enumerate(T):
    print_node(i, n)

Measured memory_bytes: 7812