akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  t <- getLine
  let ans = fmap (\c -> if c == '?' then 'D' else c) t
  putStrLn ans


Measured memory_bytes: 11800
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool ok[13][13],dp[4100];
int main(){
	cin>>n>>m;
	vector<string>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<50000;i++){
		random_shuffle(a.begin(),a.end());
		memset(ok,1,sizeof(ok));
		for(int i=0;i<m;i++)for(int j=i+1;j<m;j++)for(int k=0;k<n&&ok[i][j];k++)if(a[k][i]!=a[n-1-k][j])ok[i][j]=0;
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(int i=0;i<(1<<m);i++)if(dp[i])
			for(int j=0;j<m;j++)if((i&(1<<j))==0)
				for(int k=j+1;k<m;k++)if(ok[j][k]&&(i&(1<<k))==0)
					dp[i|(1<<j)|(1<<k)]=1;
		bool final_=0;
		if(m%2==0) final_=dp[(1<<m)-1];
		else for(int i=0;i<m;i++) final_|=dp[(1<<m)-1-(1<<i)];
		if(final_){
			puts("YES");return 0;
		}
	}
	puts("NO");
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	double p[n];
	for(int i = 0;i<n;i++){
	    cin>>p[i];
	}
	double dp[n+1][n/2+2];
	for(int i=0;i<=n;i++){
	    dp[i][0] = 1;
	}
	for(int i=1;i<=n/2+1;i++){
	    dp[0][i] = 0;
	}
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n/2+1;j++){
	        if(j > i) dp[i][j] = 0;
	        else dp[i][j] = p[i-1]*dp[i-1][j-1] + (1-p[i-1])*dp[i-1][j];
	    }
	}
	cout<<fixed<<setprecision(10)<<dp[n][n/2+1];
	return 0;
}

Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
int k, a, b;
int main()
{
	cin >> k >> a >> b;
	for (int i = a; i <= b; i++)
	{
		if (i % k == 0)
		{
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3632
#n=int(input())
n,d=map(int,input().split())
#l=list(map(int,input().split()))
xl=[list(map(int,input().split())) for i in range(n)]

ans=0
import math
for i in range(n):
    for j in range(n):
        if i>=j:
	        continue
        total=0
        for k in range(d):
            total+=(xl[i][k]-xl[j][k])**2
        total=math.sqrt(total)
        if total==int(total):
            ans+=1
print(ans)



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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    int d, x;
    cin >> d >> x;

    vector<int> a(n);
    for(int in=0;in<n;in++) {
        cin >> a.at(in);
    }

    int ans = 0;
    for(int in=0;in<n;in++) {
        for(int jn=0;jn<d;jn++) {
            // cout << 1+jn*a.at(in) << " ";
            if(1+jn*a.at(in)<=d) ans++;
            else break;
            // cout << endl;
        }
    }

    ans += x;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    ll n, a, b; cin >> n >> a >> b;
    if (b < a) {
        cout << 0 << endl;
    } else if (a == b) {
        cout << 1 << endl;
    } else if (n == 1) {
        cout << 0 << endl;
    } else {
        cout << (b*(n-2)) - (a*(n-2)) + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int n,a[maxn],b[maxn];

inline bool jud(int x)
{
	for(int i=1;i<=2*n-1;i++) b[i]=(a[i]>=x);
	for(int l=n,r=n;l>=2;l--,r++)
	{
		if(b[l]==b[l-1]) return b[l];
		if(b[r]==b[r+1]) return b[r];
	}
	return b[1];
}

int main()
{
	n=read(); rep(i,1,2*n-1) a[i]=read();
	int l=1,r=200005,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(jud(mid)) l=mid+1,ans=mid; else r=mid-1;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5248
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int>v(N);
    for(int i = 0; i < N; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double ans = v[0];
    for(int i = 1; i < N; i++){
        ans += v[i];
        ans /= 2;
    }
    cout << ans;
    return 0;
} 


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

int main(){
	int H,W,K;
	cin >> H >> W >> K;
	vector<string> s(H);
	for(auto &i:s)cin >> i;
	int ans[H][W];
	
	string w;
	for(int i=0;i<W;i++)w.push_back('.');
	int h=0;
	while(s[h]==w)h++;
	
	int c=0;
	for(int i=0;i<W;i++){
		if(s[h][i]=='#')c++;
		ans[h][i]=c;
	}
	for(int i=0;s[h][i]=='.';i++)ans[h][i]++;
	
	for(int i=0;i<h;i++)for(int j=0;j<W;j++)ans[i][j]=ans[h][j];
	
	for(h=h+1;h<H;h++){
		if(s[h]==w){
			for(int i=0;i<W;i++)ans[h][i]=ans[h-1][i];
			continue;
		}
		for(int i=0;i<W;i++){
			if(s[h][i]=='#')c++;
			ans[h][i]=c;
		}
		for(int i=0;s[h][i]=='.';i++)ans[h][i]++;
	}
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++)cout << ((j>0)?(" "):("")) << ans[i][j];
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1280
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#define N 0
#define INF 0x3f3f3f3f
#define LL long long
#define mz(x) ms(x,0)
#define ms(x,y) memset(x,y,sizeof(x))
#define mc(x,y) memcopy(x,y,sizeof(y))
#define MOD 1000000007

using namespace std ;

int a[5][5] ;
bool mark[5][5] ;
map<int, pair<int, int> > mp ;

int main()
{
	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++)
		{
			scanf("%d", &a[i][j]) ;
			mp[a[i][j]] = make_pair(i, j) ;
		}
			
	int n ;
	scanf ("%d", &n) ;
	for (int i=0; i<n; i++)
	{
		int b ;
		scanf ("%d", &b) ;
		
		map<int, pair<int, int> >::iterator it = mp.find (b) ;
		if (it != mp.end())
			mark[it->second.first][it->second.second] = true ;
	}
	
	bool flag = false ;
	for (int i=0; i<3; i++)
	{
		int sum = 0 ;
		for (int j=0; j<3; j++)
			if (mark[i][j])
				sum++ ;
		
		if (sum == 3)
		{
			flag = true ;
			break ;
		}
	}
	
	for (int j=0; j<3; j++)
	{
		int sum = 0 ;
		for (int i=0; i<3; i++)
			if (mark[i][j])
				sum++ ;
		
		if (sum == 3)
		{
			flag = true ;
			break ;
		}
	}
	
	if (mark[0][0] == true && mark[1][1] == true && mark[2][2] == true)
		flag = true ;
		
	if (mark[0][2] == true && mark[1][1] == true && mark[2][0] == true)
		flag = true ;
		
	if (flag)
		cout << "Yes" << endl ;
	else
		cout << "No" << endl ;
	

	return 0 ;
}

Measured memory_bytes: 3120
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cassert>

//std::cout << std::fixed << std::setprecision(10)
//std::ios::sync_with_stdio(false);
//constexpr long long MOD = 1000000007;

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

int main()
{
  int A, B;
  std::cin >> A >> B;
  int limit = 10000;
  int ans = -1;
  for(int i = 1; i <= limit; ++i)
  {
    int a = 0.08*i, b = 0.1*i;
    if(a == A && b == B)
    {
      ans = i;
      break;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String r = sc.next();
    String g = sc.next();
    String b = sc.next();
    int num = Integer.parseInt(r+g+b);
    String ans = num%4==0? "YES" : "NO";
    System.out.println(ans);
  }
}



Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define DEBUG(debug_x) cerr <<#debug_x<<": "<<debug_x<<endl;
#define DEBUG2(debug_x, debug_y) cerr <<#debug_x<<":"<<debug_x<<" "<<#debug_y<<":"<<debug_y<<endl;
#define DEBUG3(debug_x, debug_y, debug_z) cerr <<#debug_x<<":"<<debug_x<<" "<<#debug_y<<":"<<debug_y<<" "<<#debug_z<<":"<<debug_z<<endl;
#define DEBUGVC(debug_x) cerr <<#debug_x<<": "; for(auto a:debug_x) cerr << a <<" "; cerr << endl;
#define DEBUGMP(debug_x) cerr <<#debug_x<<":"<<endl; for(auto a:debug_x) cerr << a.first <<" "<< a.second << endl;
#define MAX_N (200005)
#define INF (1LL << 60)
const int MOD = (int)1e9;
typedef pair<int,int> Pii;
typedef pair<double,double> Pdd;
 
signed main() {
    int N, L;
    cin >> N >> L;
    vector<int> a(N);
    for(int i=0; i<N; i++) cin >> a[i];

    int j=-1;
    for(int i=0; i<N-1; i++){
        if(a[i]+a[i+1]>=L) j=i+1;
    }
    if(j==-1){
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    for(int i=N-1; i>j; i--) cout << i << endl;
    for(int i=1; i<=j; i++) cout << i << endl;

}

Measured memory_bytes: 1664
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  long a, b; rd(a, b);

  import std.math;
  auto c=max(a, b);
  writefln("%.18f", PI*4/3.0*c*c*c);

}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}



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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1.0E-14;

int main() {
    long double a,b,c;
    cin >> a >> b >> c;
    if(sqrt(a)+sqrt(b)+EPS<sqrt(c)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
  ll n,maxn=0,next=0,maxin=0;cin>>n;
  vector<ll> v(n);

  rep(i,n){
    cin>>v[i];
    
    if(maxn<=v[i]){
      next=maxn;
      maxn=v[i];
      maxin=i;
    }else if(next<=v[i])next=v[i];
  }

  for(int i=0;i < n;i++)
  {
    if(i==maxin)cout<<next<<endl;
    else cout<<maxn<<endl;
  }
}


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

int main(void) {
	double x[30];
	double y[30];
	int i, size = 0;
	double S;
	char c;
	
	while(scanf("%lf%c%lf\n", &x[size], &c, &y[size])==3) {
		size++;
	}
	x[size] = x[0];
	y[size] = y[0];
	size++;
	
	S = 0;
	for(i=0;i<size;i++) {
		S = S + x[i] * y[i+1] - x[i+1] * y[i];
	}
	printf("%.6lf\n", fabs(S)/2);
	
	return 0;
}

Measured memory_bytes: 660
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " <<
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  stack<char> stack;
  int ans = 0;
  string s;
  cin >> s;
  stack.push(s[0]);
  FOR(i, 1, s.length()){
    if(!stack.empty()) {
      if (stack.top() == s[i]) {
        stack.push(s[i]);
      } else if (stack.top() != s[i]) {
        ans += 2;
        stack.pop();
      }
    }
    else{
      stack.push(s[i]);
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 512
function main(input) {
  var N = input[0]-0; 9
  var nums = ["7","5","3"];
  console.log(calc(N,nums,[], false));
}

function calc(N, nums, arr, ngs){
  var ans = 0;
  var base = arr.join("");
  for(var i=0;i<nums.length;i++){
    var n = (base+nums[i]);
    var cnc = arr.concat(nums[i]);
    if(n-0<=N){
      if(ngs){
        ans++;
        ans += calc(N,nums, cnc,true);
      }else if((cnc.indexOf("3")>=0 && cnc.indexOf("5")>=0 && cnc.indexOf("7")>=0)){
        ans++;
        ans += calc(N,nums, cnc,true);
      }else {
        ans += calc(N,nums, cnc,false);
      }
    }
  }
  return ans;
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"))


Measured memory_bytes: 10464
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
satisfy=0
for i in range(N-1):
    if A[i+1]==A[i]+1:
        satisfy+=C[A[i]-1]
    satisfy+=B[i]
satisfy+=B[N-1]
print(satisfy)


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

using namespace std;
using i64 = long long;

const i64 inf = std::numeric_limits<i64>::max();

void solve(long long N){
    cout << N * N * N << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
}


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

int main(){
    int n, ans = 0;
    cin >> n;
    int a[n], b[n], c[n-1];
    rep(i,n)    cin >> a[i];
    rep(i,n)    cin >> b[i];
    rep(i,n-1)  cin >> c[i];

    rep(i,n)    ans += b[i];
    rep(i,n-1){
        if(a[i] + 1 == a[i+1])
            ans += c[a[i]-1];
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define int         ll int
#define float       double
#define	endl		'\n'
#define mii         map<int,int>
#define msi         map<string,int>
#define mis         map< int, string>
#define mpi         map<pair< int, int>, int>
#define pii         pair< int, int>
#define vi          vector< int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
 
#define N  100005
signed main()
{
	fast;
	int n;
	cin>>n;
	int x=n%500;
	x=x/5;
	int y=n/500;
	cout<<x*5+y*1000<<endl;
}

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

using namespace std;

int n,k;

void solve(){
    int i,j;
    string str;
    cin >> n >> k;
    int ans = 0;
    for(i = 0;i < n;i++){
        cin >> j;
        if(k <= j) ans++;
    }
    cout << ans << endl;
}

int main(){
    solve();
}


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

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

  int n;
  cin >> n;

  unordered_map<string, int> count;

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

  int m;
  cin >> m;

  for (int i = 0; i < m; ++i) {
    string s; cin >> s;
    count[s]--;
  }

  int res = 0;
  for (auto p: count) {
    res = max(res, p.second);
  }

  cout << res << "\n";
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
const char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(i, vec) for(auto &(i) : (vec))


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

const std::map<char, short> dic{
  {'N', 0}, {'W', 1}, {'E', 2}, {'S', 3}
};

int main(void){
  string s; cin >> s;
  Vint CNT(4, 0);
  vREP(ele, s) CNT.at(dic.at(ele))++;
  bool flag1, flag2;
  flag1 = (CNT.at(0) == 0) == (CNT.at(3) == 0);
  flag2 = (CNT.at(1) == 0) == (CNT.at(2) == 0);
  cout << ((flag1 and flag2) ? "Yes" : "No") << BR;
  return 0;
}

Measured memory_bytes: 256
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    L = sorted(il())[::-1]
    print(sum(L[0:K]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<stdio.h>
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m))
	{
		int ans = 0;
	    if(n == 0 && m == 0)
	    {
	        break;
	    }  
	    for(int i = 1; i < n-1; i++)
	    {
	    	for(int j = i + 1; j < n; j++)
	    	{
	    		for(int k = j + 1; k < n + 1; k++)
	    		{
	    			if(m == i + j + k)
	    			{
	    				ans++;
					}
				}
			}
		}
		printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 2684
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long[] a = sc.LongArray();

        long answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[a[i] - 1] == i + 1)
            {
                answer++;
            }
        }

        answer /= 2;

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 36248
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];

            int sum = 0;
            for (int i = 0; i < n; i++) {
                int ai = in.nextInt();
                a[i] = ai;
                sum += ai;
            }

            int y = (int) Math.ceil((sum * 1.0d) / n);

            int cost1 = 0;
            for (int i = 0; i < n; i++) {
                cost1 += (y - a[i]) * (y - a[i]);
            }


            int cost2 = 0;
            for (int i = 0; i < n; i++) {
                cost2 += ((y + 1) - a[i]) * ((y + 1) - a[i]);
            }

            int cost3 = 0;
            for (int i = 0; i < n; i++) {
                cost3 += ((y - 1) - a[i]) * ((y - 1) - a[i]);
            }

            out.println(Math.min(Math.min(cost1, cost2), cost3));
        }

    }
}


Measured memory_bytes: 9680
#include<iostream>
#include<set>
using namespace std;
#define INF 30000
int main(){
	while(1){
		int n,m;
		cin>>n;
		if(n==0)break;
		cin>>m;
		int cost[100][100];
		for(int i=0;i<100;i++){
			for(int j=0;j<100;j++){
				cost[i][j]=INF;
			}
		}
		for(int i=0;i<m;i++){
			int a,b,c;
			char t;
			cin>>a>>t>>b>>t>>c;
			c=c/100-1;
			cost[a][b]=c;
			cost[b][a]=c;
		}
		int v[100]={0};
		v[0]=1;
		int ans=0;
		while(1){
			bool flag=true;
			for(int i=0;i<n;i++){
				if(v[i]==0){
					flag=false;
					break;
				}
			}
			if(flag==true)break;
			int min=INF;
			int to;
			for(int i=0;i<n;i++){
				if(v[i]==1){
					for(int j=0;j<n;j++){
						if(v[j]==0){
							if(min>cost[i][j]){
								min=cost[i][j];
								to=j;
							}
						}
					}
				}
			}
			v[to]=1;
			ans+=min;
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
	IOS;
	int w,a,b;
	cin>>w>>a>>b;
	if(a+w<b)
	return cout<<b-a-w,0;
	if(b+w<a)
	return cout<<(a-b-w),0;
	else
	return cout<<0,0;
}

Measured memory_bytes: 256
/*
	Author: Ritik Patel
	
	Idea: 
*/


//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&&

// #define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
// #pragma GCC optimize "trapv" // abort() on (signed) integer overflow.

//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&&

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

/*#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
template<typename T, typename V = __gnu_pbds::null_type>
using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; 
*/
//find_by_order()->returns an iterator to the k-th largest element(0-based indexing)
//order_of_key()->Number of items that are strictly smaller than our item

//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&&

#define int long long int
#define all(i) i.begin(), i.end()
#define sz(a) (int)a.size()
 
// const ld PI  = 3.141592;
const int dx4[4] = {0, 1, 0, -1};
const int dy4[4] = {-1, 0, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
 
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&&
 
#define XOX
vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z));
    return res;
}
 
void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}
 
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
#else
#define debug(...) 42
#endif
 
 
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&&

const int MOD = (int)1e9 + 7;
void solve(){
    string s, t; cin >> s >> t;
    int ans = 0;
    int n = sz(s);
    for(int i = 0; i < n; ++i){
        if(s[i] != t[i])
            ans++;
    }
    cout << ans << '\n';
}



int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); 
    int T = 1; 
    // cin >> T;
    for(int i = 1; i <= T; ++i){
        // brute();
        solve();
    }
    return 0;
}

/*
Sample inp
*/

Measured memory_bytes: 3896
def main():
    mod = 998244353
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    a = [i for i in a if i <= s]
    dp = [0 for i in range(s+1)]
    half = pow(2, mod-2, mod)
    for i in a:
        dp2 = [j for j in dp]
        dp2[i] = (dp2[i]+pow(2, n-1, mod)) % mod
        for j in range(s-i+1):
            dp2[j+i] = (dp2[j+i]+dp[j]*half) % mod
        dp = dp2
    print(dp[s])


main()


Measured memory_bytes: 9440
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	string s;
	cin>>s;
	if(s[0]=='7' || s[1]=='7' || s[2]=='7')
	 cout<<"Yes";
	else
	 cout<<"No";
	return 0;
	
}

Measured memory_bytes: 3588
#include <stdio.h>
int main(void){
  int h,w,flag;
  scanf("%d %d",&h,&w);
  char grid[h][w] ={'a'};
  char dummy;
  for(int i = 0;i < h;i++){
    scanf("%c",&dummy);
    for(int j = 0;j < w;j++){
      scanf("%c",&(grid[i][j]));
    }
  }
    flag = 0;
    for(int i = 0;i < h;i++){
    for(int j = 0;j < w;j++){
      if(grid[i][j] == '#'){
        if(i != 0){
          if(grid[i-1][j]=='#')continue;
        } 
        if(i != h-1){
          if(grid[i+1][j]=='#')continue;
        }
        if(j != 0){
          if(grid[i][j-1]=='#')continue;
        }
        if(j != w-1){
          if(grid[i][j+1]=='#')continue;
        }
        flag = 1;
        h = i;
        w = j;
        break;
      }
    }
    if(flag)break;
  }
  if(flag){
    printf("No");
  }else{
    printf("Yes");
  }
}

Measured memory_bytes: 128
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using ll = long long int;
const ll MOD = 1e9 + 7;

ll count(ll n) {
    ll ans = 1;
    while (n > 0)
    {
        ans *= n;
        ans %= MOD;
        n--;
    }
    return ans;
}

int main() {
  ll n, m;

  cin >> n >> m;


    ll ans = 0;
  if (abs(n - m) > 1) {
      ans = 0;
  } else if (abs(n - m) == 1) {
      ans = count(n);
      ans %= MOD;
      ans *= count(m);
      ans %= MOD;
  } else {
      ans = count(n);
      ans %= MOD;
      ans *= count(m);
      ans %= MOD;
      ans *= 2;
      ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
  int a; cin >> a;
  cout << a+a*a+a*a*a << endl;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vi A(N),B(N);
  rep(i,0,N) cin>>A[i];
  rep(i,0,N) cin>>B[i];
  int sum1=0,sum2=0;
  rep(i,0,N){
    if(A[i]>B[i]){
      sum1+=A[i]-B[i];
    }
    else{
      sum2+=(B[i]-A[i])/2*2;
    }
  }
  string ans="No";
  if(sum1<=sum2/2) ans="Yes";
  cout<<ans<<endl;
  }


Measured memory_bytes: 384
/* long long or int & the MAX_INT or MIN_INT */
/* the size of a[] & inline */
/* xx 396 */

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

const int MAX_N=1e5+10;

int H[MAX_N],N;
int now=0,ans=0;

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>N; for(int i=1;i<=N;i++) cin>>H[i];
	H[0]=0;
	for(int i=1;i<=N;i++){
		if(H[i]<=H[i-1]){
			now++; ans=max(ans,now);
		}
		else now=0;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005
/*
step1: a が偶数列：　何回2で和れるかを調べる 個数が違ったら0 cnt 回割り切れた
    while True
step2: aが奇数列になっている。奇数列の中で、最小公倍数を求める lcm_odd
step3: lcm_odd * (2**cnt) = 最小公倍数になる
step4: (m//lcm_odd_min + 1) // 2
*/

vector<pair<ll, int>> fac;
void PrimeFactorInit(ll x){ // 素因数と個数のペアを返す.
    if(x >= 2){
        for(ll i = 2; i <= x; i++){
            if(i * i > x)break;
            if(x % i == 0){
                int cnt = 0;
                while(x % i == 0){
                    cnt++;
                    x /= i;
                }
                pair<ll, int> p;
                p.first = i;
                p.second = cnt;
                fac.push_back(p);
            }
        }
        if(x > 1){
            pair<ll, int> p;
            p.first = x;
            p.second = 1;
            fac.push_back(p);
        }
    }
}

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

    int cnt = 0;
    int ng = 0;//ng が立っていたら揃っていない。
    while(true){
        ng = 0;
        rep(i,n){
            if(a[i] % 2 == 0){
                a[i] /= 2;
            }else{
                ng++;
                // break;
            }
        }
        if(ng >= 1){
            if(ng == n){
                ng = 0;
            }
            break;
        }
        cnt++;
    }
    cnt--;

    if(ng > 0){
        cout << 0 << endl;
        return 0;
    }

    sort(a,a+n);

    ll ans = 0;

    map<ll,ll> mp;
    ll lcm = 1;
    rep(i,cnt){
        lcm *= 2;
    }
    rep(i,n){
        if(i >= 1 && a[i] == a[i-1])continue;
        fac.clear();
        PrimeFactorInit(a[i]);
        rep(j,fac.size()){
            int tmp = fac[j].second - mp[fac[j].first];
            if(tmp > 0){
                rep(k,tmp){
                    lcm *= fac[j].first;
                    if(lcm > m){
                        cout << 0 << endl;
                        return 0;
                    }
                }
            }
            mp[fac[j].first] = max((ll)fac[j].second, mp[fac[j].first]);
        }
    }

    

    
    // cout << "OK" << endl;
    /*
    for(auto p : mp){
        rep(i,p.second){
            lcm *= p.first;
            if(lcm > m){
                cout << 0 << endl;
                return 0;
            }
        }
    }
    */

    ans = (m/lcm + 1) / 2;

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




Measured memory_bytes: 4416
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int a = 0;
		int b = 0;
		int c = 0;
		int d = 0;
		int e = 0;
		int k = 0;
		Scanner sc = new Scanner(System.in);
		a = Integer.parseInt(sc.next());
		b = Integer.parseInt(sc.next());
		c = Integer.parseInt(sc.next());
		d = Integer.parseInt(sc.next());
		e = Integer.parseInt(sc.next());
		k = Integer.parseInt(sc.next());

		if (e - a <= k)
			System.out.println("Yay!");
		else
			System.out.println(":(");
	}
}

Measured memory_bytes: 21844
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int d = sc.nextInt();
		int[] location = new int[h * w + 1];
		for (int i = 0; i < h; i++) {
		    for (int j = 0; j < w; j++) {
		        location[sc.nextInt()] = i * w + j;
		    }
		}
		long[] costs = new long[h * w + 1];
		for (int i = d + 1; i <= h * w; i++) {
		    int a = location[i];
		    int b = location[i - d];
		    int cost = Math.abs(a / w - b / w) + Math.abs(a % w - b % w);
		    costs[i] += costs[i - d];
		    costs[i] += cost;
		}
		int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
		    int l = sc.nextInt();
		    int r = sc.nextInt();
		    sb.append(costs[r] - costs[l]).append("\n");
		}
	    System.out.print(sb);
   }
}




Measured memory_bytes: 93844
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author toshibablack
 */

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#include "string.h"

#define ll long long int
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<n;++i)
#define FOREACH(x, a) for(auto& (x) : (a))
#define ALL(a) (a).begin(),(a).end()
#define COUT(x) out << (x) << endl;
#define M0(x) memset(x,0,sizeof(x))
#define MINF(x) memset(x,0x3f,sizeof(x))
#define MMINUS(a) memset(a,0xff,sizeof(a))

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;


class BFrog2 {
public:
    int N, K;
    int h[100010];
    ll dp[250000];

    void solve(std::istream& in, std::ostream& out) {
        in >> N >> K;
        FOR(i, 1, N+1) in >> h[i];
        MINF(dp);
        dp[1] = 0;
        for (int i = 1; i < N; ++i) {
            for (int s = 1; s <= K; ++s) {
                int next = i+s;
                dp[next] = min(dp[next], dp[i] + abs(h[i]-h[next]));
            }
        }
        COUT(dp[N]);
    }
};


int main() {
    BFrog2 solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <set>
using namespace  std;

#define int long long int

constexpr int INF = std::numeric_limits<int>::max();

vector<bool> memo(1000001, false);

int f(int a) {
    if (a % 2 == 0) {
        return a / 2;
    } else {
        return 3 * a + 1;
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int ans = 0;
    int prev = 0;
    while (N--) {
        int h; cin >> h;
        if (prev < h) {
            ans += h - prev;
        }
        prev = h;
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int N, n[4], op1 = 0, op2 = 0, op3 = 0, s = 0;
	string ans;

	cin >> N;

	n[0] = N / 1000;
	n[1] = N / 100 % 10;
	n[2] = N / 10 % 100 % 10;
	n[3] = N % 1000 % 100 % 10;

	s = n[0];

	for (int o1 = 0; o1 < 2; o1++) {
		for (int o2 = 0; o2 < 2; o2++) {
			for (int o3 = 0; o3 < 2; o3++, s = n[0]) {
				if (o1)s += n[1];
				else s -= n[1];
				if (o2)s += n[2];
				else s -= n[2];
				if (o3)s += n[3];
				else s -= n[3];

				if (s == 7) {
					if (o1) ans += "+";
					else ans += "-";
					if (o2) ans += "+";
					else ans += "-";
					if (o3) ans += "+";
					else ans += "-";

					cout << n[0] << ans[0] << n[1] << ans[1] << n[2] << ans[2] << n[3] << "=7";
					return 0;
				}
			}
		}
	}

	return 0;
}

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n, k;
  cin >> n >> k;
  
  if(k % 2 == 1){
    ll a = 0;
    for(int i = 1; i <= n; i++){
      if(i % k == 0) a++;
    }
    cout << a * a * a << '\n';
  }
  else{
    ll a = 0, b = 0;
    for(int i = 1; i <= n; i++){
      if(i % k == 0) a++;
      else if(i % k == k / 2) b++;
    }
    cout << a * a * a + b * b * b << '\n';
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 1e6 + 5;
const int logn = log2(maxn) + 1;
const int mod = 1e9 + 7;

struct Point{
    ii a;
    int id;
    Point(){};
    Point(ii a , int id):a(a),id(id){};
    bool operator < (const Point & other){
        if(a.first == other.a.first){
            if(a.first == 0)return a.second < other.a.second;
            return a.second > other.a.second;
        }
        if(a.second == other.a.second){
            if(a.second == 0)return a.first > other.a.first;
            return a.first < other.a.first;
        }
    }
};
int r , c , n;

int Type(ii a){
    if(a.first == 0)return 0;
    if(a.first == r)return 2;
    if(a.second == c)return 1;
    return 3;
}
vector<Point> val[4];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(taskname".INP", "r")) {
        freopen(taskname".INP", "r", stdin);
        freopen(taskname".OUT", "w", stdout);
    }
    cin >> r >> c >> n;
    for(int i = 1 ; i <= n ; ++i){
        ii a;cin >> a.first >> a.second;
        ii b;cin >> b.first >> b.second;
        if((a.first == 0 || a.first == r || a.second == 0 || a.second == c) &&
           (b.first == 0 || b.first == r || b.second == 0 || b.second == c)){
            val[Type(a)].pb(Point(a,i));
            val[Type(b)].pb(Point(b,i));
           }
    }
    stack<int> s;
    for(int i = 0 ; i < 4 ; ++i){
        sort(val[i].begin(),val[i].end());
//        cout << val[i].size() << endl;
        for(auto & c : val[i]){
            if(s.size() && s.top() == c.id)s.pop();
            else s.push(c.id);
        }
    }
    cout << (s.size() ? "NO" : "YES");
}


Measured memory_bytes: 3820
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] num = new int[3];
		for (int i = 0; i < 3; i++) {
			num[i] = sc.nextInt();
		}
		int temp;

		for (int i = 0; i < num.length; i++) {
			for (int j = num.length - 1; j > i; j--) {
				if (num[j] < num[j - 1]) {
					temp = num[j-1];
					num[j-1] = num[j];
					num[j] = temp;
				}
			}
		}

		System.out.println(num[0] + " " + num[1] + " " + num[2]);

		sc.close();
	}

}



Measured memory_bytes: 26380
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n;
  R n;
  ll a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  ll sum=0;
  rep(i,n) {
    if(i==n-1) sum+=a[i]/2;
    else sum+=a[i];
  }
  pr(sum);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

#define INF 0x7fffffff

int main() {
	long long		a,b,c,i,j,k,n,m,x,y,ans1 , ans = 0;
	string	str;

	cin >> n >> x >> y;

	vector< vector<int> > aa(n+1, vector<int>(n+1));
	for(i=1;i<=n-1;i++) {
		for(j=i+1;j<=n;j++) {
			aa[i][j] = j - i;
			if ((i<=x) && (y<=j)) aa[i][j] = j - i - (y-x) + 1;
			if ((x<=i) && (y<=j)) {
				k = (i-x+1+(j-y));
				if ( aa[i][j] > k ) aa[i][j] = k;
			} else if ((x<=i) && (j<=y)) {
				k = (i-x+1+(y-j));
				if ( aa[i][j] > k ) aa[i][j] = k;
			} else if ((i<=x) && (j<=y)) {
				k = (x-i+1+(y-j));
				if ( aa[i][j] > k ) aa[i][j] = k;
			}
		}
	}
/*
	for(i=1;i<=n;i++) {
		for(j=1;j<=n;j++) {
			cout << aa[i][j] << " ";
		}
		cout << endl;
	}
*/
	vector<int> an(n+1);
	for(i=1;i<=n-1;i++) {
		for(j=i+1;j<=n;j++) {
			 an[aa[i][j]]++;
		}
	}
	for(i=1;i<n;i++) {
		cout << an[i] << endl;
	}

}


Measured memory_bytes: 16000