akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef pair<int,int> pii;

#define mod 1000000007;

main(){
  string w; cin >> w;
  map<char,int> mp;
  rep(i,w.size()) mp[w[i]]++;

  for(auto itr : mp){
    if(itr.second % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
#!/usr/bin/python3
#coding: utf-8

import math

N = int(input())
P = [[int(x) for x in input().split()] for _ in range(N)]


def calc(path):
    r = 0
    for i in range(len(path) - 1):
        p1 = P[path[i-1]]
        p2 = P[path[i]]
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        r += math.sqrt(dx*dx + dy*dy)
    return r

ret = 0
numret = 0
def rec(path, rest):
    if not rest:
        global ret
        global numret
        ret += calc(path)
        numret += 1
        return
    for i in range(len(rest)):
        rec(path + [rest[i]],  rest[:i] + rest[i+1:])

rec([], [i for i in range(N)])
print(ret/numret)


Measured memory_bytes: 9204
#n=int(input())
#li=input().split()
#d=["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"]
#import numpy as np
import math
#li=list(map(int,input().split()))
#S=input()

lis=[]
for i in range(6):
    lis.append(int(input()))
m=math.ceil(lis[0]/min(lis[1:]))
print(m+4)


Measured memory_bytes: 2940
def flog():
    n = int(input())
    h = list(map(int, input().split()))

    dp = [0]*n
    dp[1] = abs(h[1] - h[0])
    for i in range(2, n):
        dp[i] = min(dp[i-2]+abs(h[i] - h[i-2]), dp[i-1]+abs(h[i]-h[i-1]))

    print(dp[-1])


if __name__ == '__main__':
    flog()


Measured memory_bytes: 13928
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define LL long long
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define MP make_pair
int n,c,d;

set<pii>se[N];
bool use[N];
int pos[N];
void no(int v){
	puts("No");exit(0);
}
void dfs(int u){
	for(set<pii>::iterator it=se[u].begin();it!=se[u].end();++it){
		int v=(*it).first;
		if(use[v]&&pos[v]!=pos[u]+(*it).second)no( v);
		else if(use[v])continue;
		else {

			use[v]=true;pos[v]=pos[u]+((*it).second);
			dfs(v);
		}
	}
}


int main(){
	int m;
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		se[l].insert(MP(r,x));
		se[r].insert(MP(l,-x));
	}
	//for(int i=1;i<=n;++i){
		//for(set<pii>::iterator it=se[i].begin();it!=se[i].end();++it){
			//cout<<(*it).first<<' '<<(*it).second<<endl;
		//}
	//}
	for(int i=1;i<=n;++i){
		if(!use[i]){
			use[i]=true;pos[i]=0;dfs(i);
		}
	}
	puts("Yes");
}


Measured memory_bytes: 27008
n, m = map(int, input().split())
stores = []
for i in range(n):
  stores.append(tuple(map(int, input().split())))

stores.sort(key=lambda sotre:sotre[0])

ans = 0
for a, b in stores:
  buy = min(b, m)
  m -= buy
  ans += a * buy
  if m == 0:
    break
print(ans)

Measured memory_bytes: 18136
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<int> a(n + 1, 0);
  rep(i, 0, n - 1) {
    int t;
    cin >> t;
    a[t]++;
  }

  rep(i, 1, n + 1) cout << a[i] << endl;
}


Measured memory_bytes: 3968
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<iostream>  
#include<string>  
#include<vector>  
#include<stack>  
#include<bitset>  
#include<cstdlib>  
#include<cmath>  
#include<set>  
#include<list>  
#include<deque>  
#include<map>  
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=1<<29;
const ll Maxn=1e6;

int a[4][4];

int main(){
	int a,b,c,d,e,f,g,h,i;
	int flag=0;
	scanf("%d %d %d",&a,&b,&c);
	scanf("%d %d %d",&d,&e,&f);
	scanf("%d %d %d",&g,&h,&i);
	if(d+b-a==e) flag++;
	if(c+e-b==f) flag++;
	if(e+g-d==h) flag++;
	if(f+h-e==i) flag++;
	if(flag==4) printf("Yes\n");
	else printf("No\n");
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

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

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll ans = 1;
    for(ll i=0; i<k; i++){
        ans *= ((n-i) % MOD);
        ans = ans % MOD;
    }
    ans = (ans * finv[k]) % MOD;
    return ans;
}

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    ll all_sum;

    // 前処理
    COMinit();

    all_sum = (modpow(2, n, MOD) + MOD -1) % MOD;
    ll com_a = COM(n, a);
    ll com_b = COM(n, b);

    ll ans = (all_sum + 2 * MOD - com_a - com_b) % MOD;

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

Measured memory_bytes: 12160
N, K = map(int, input().split())
V = list(map(int, input().split()))
revV = list(reversed(V))

N = N + 1 # 選択しなかった場合を追加
res = 0
AB = []
if N < K:
	AB = V
	k = min(K-len(AB), len(AB))
	for idx in range(k):
		if AB[idx] < 0:
			AB[idx] = 0
	res = max(res, sum(AB))
else:
	for a in range(N):
		for b in range(N):
			if a + b <= K:
				AB = V[:a] + revV[:b]
				AB.sort()
				k = min(K-len(AB), len(AB))
				for idx in range(k):
					if AB[idx] < 0:
						AB[idx] = 0
				res = max(res, sum(AB))
print(res)

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n,k,ans=0;
    string s;
    cin>>n>>k>>s;
    REP(i,0,n-1){
        if(s[i]==s[i+1]) ans++;
    }
    cout<<min(n-1,ans+2*k)<<endl;
    return 0;
}


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

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

#ifdef MY_DEBUG_FLAG
void debug() { cerr << '\n'; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << " " << I; debug(F...); }
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") ==", debug(__VA_ARGS__)
#else
#define db(...)
#endif

#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr)
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define dec(i,n,a) for(int i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()

constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 1e5 + 10;
constexpr int mod = 1000000007;

int a[16][16];

ll prize[1 << 16], dp[1 << 16];

int main() {
	int n; scanf("%d", &n);
	rep(i,0,n) rep(j,0,n) scanf("%d", &a[i][j]);

	for(int mask = 1; mask < (1 << n); mask++) {
		for(int i = 0; i < n; i++)
			if(mask&(1 << i))
				for(int j = 0; j < i; j++)
					if(mask&(1 << j))
						prize[mask] += a[i][j];
	}

	for(int mask = 0; mask < (1 << n); mask++) {
		for(int sub = mask; sub > 0; sub = (sub-1)&mask)
			dp[mask] = max(dp[mask], dp[sub ^ mask] + prize[sub]);
	}

	printf("%lld\n", dp[(1 << n)-1]);
}


Measured memory_bytes: 4840
from collections import defaultdict, Counter
mod = 10**9+7
n, k = map(int, input().split())
ans = 0
for i in range(k, n+2):
    ans+=(n*(n+1) - (n-i)*(n-i+1) - i*(i-1) + 2)//2
    # print(ans)
print(ans%mod)


Measured memory_bytes: 9464
#include <iostream>

using namespace std;

int main(){
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	if(max(A, C) < min(B, D)){
		cout << min(B, D) - max(A, C) << endl;
	}
	if(max(A, C) >= min(B, D)){
		cout << 0 << endl;
	}

	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <fstream>
    #include <iomanip>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <climits>
    #define sync                                                                   \
            ios_base::sync_with_stdio(0);                                                \
            cin.tie(0);                                                                  \
            cout.tie(0)
    #define ss second
    #define ff first
    #define ll long long
    #define mp make_pair
    #define endl "\n"
    #define pb push_back
    #define ld long double
    #define M_PI 3.14159265358979323846
    #define puss vector
    #define ull unsigned long long
    #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
    #define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
    #define die {cout<<-1; return 0;}
    double EPS = 0.00001;
    const ll INF = 1000000007;
    using namespace std;


    int main() {
            sync;
            int n,k;
            cin>>n>>k;
            vector< int > cnt(n, INF);
            set<int>a;
            FOR(i, 0, n){
                int x;
                cin>>x;
                a.insert(x-1);
                if (cnt[x-1]==INF)
                    cnt[x-1]=1;
                else
                    cnt[x-1]++;
            }
    if ((int)a.size()<=k) cout<<0;
    else{
        sort(cnt.begin(), cnt.end());
        int ans=0;
        for (int i=0;i<a.size()-k;i++)
            ans+=cnt[i];
        cout<<ans;
    }
    }


Measured memory_bytes: 10368
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n;
bool mark[610][610];
void work(int d)
{
	int k=0;
	while (d%4==0)
	{
		d/=4;
		k++;
	}
	if (d&1)
	{
		for (int i=0;i<2*n;i++)
		{
			for (int j=0;j<2*n;j++)
			{
				if (((i>>k)+(j>>k))&1)
				{
					mark[i][j]=true;
				}
			}
		}
	}
	else
	{
		for (int i=0;i<2*n;i++)
		{
			for (int j=0;j<2*n;j++)
			{
				if ((i>>k)&1)
				{
					mark[i][j]=true;
				}
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	int d;
	scanf("%d",&d);
	work(d);
	scanf("%d",&d);
	work(d);
	int cnt=0;
	for (int i=0;i<2*n;i++)
	{
		for (int j=0;j<2*n;j++)
		{
			if (!mark[i][j])
			{
				cnt++;
				printf("%d %d\n",i,j);
				if (cnt==n*n)
				{
					return 0;
				}
			}
		}
	}
    return 0;
}
//才喜门堆巷积，可惜迤逦销残。
//——周邦彦《红林檎近(双调·第二)》

Measured memory_bytes: 1280
N, T = map(int, input().split())
a_arr = list(map(int, input().split()))
mini = 10**9
diff = []
for a in a_arr:
    if a < mini:
        mini = a
    diff.append(a - mini)
max_diff = max(diff)
ans = 0
for d in diff:
    if d == max_diff:
        ans += 1
print(ans)

Measured memory_bytes: 15020
import sys
input = sys.stdin.readline


def read():
    N, K, S = map(int, input().strip().split())
    return N, K, S


def solve(N, K, S):
    ans = [0 for i in range(N)]
    for i in range(K):
        ans[i] = S
    for i in range(K, N):
        ans[i] = S % 10**9 + 1
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 13828
#include <string>
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>      // std::setprecision

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif


using namespace std;

using ll = long long int; 
using pdi = pair<double, int>;

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };

struct Point{
  ll x,y,r;
  Point(ll x, ll y, ll r=0):x(x),y(y),r(r){}
};

vector<Point> Points;
int N;

string s;
void input(){
  #ifdef __LOCAL
    fs::path p = __FILE__;
    fs::path input,output;
    input = output = p.parent_path();
    input += string("/input/") + string(p.stem()) + string(".txt");
    output += string("/output/") + string(p.stem()) + string(".txt");
    freopen(input.c_str(), "r", stdin);
    freopen(output.c_str(), "w", stdout);
  #endif
  fast_io();
  ll xs,ys,xt,yt;
  cin >> xs >> ys >> xt >> yt;
  cin >> N;
  Points.emplace_back(xs,ys,0);
  for (int i = 0; i < N; i++)
  {
    ll x,y,r;
    cin >> x >> y >> r;
    Points.emplace_back(x,y,r);
  }
  Points.emplace_back(xt,yt,0);
}

double dist(const Point& a, const Point& b){
  double r = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  return max(r-a.r-b.r,0.0);
}

int solve(){
  vector<vector<double> > Mat(N+2,vector<double>(N+2,0.0));
  for (int i = 0; i <= N; i++)
    for (int j = i+1; j <= N+1; j++)
      Mat[i][j] = Mat[j][i] = dist(Points[i],Points[j]);
  
  int s=0,t=N+1;
  priority_queue<pdi,vector<pdi>,greater<pdi> > pq;
  vector<bool> seen(N+2,false);
  pq.emplace(0.0, s);
  while(!pq.empty()){
    double d;
    int now;
    tie(d,now) = pq.top();
    if(now==t) break;
    seen[now] = true;
    pq.pop();
    if(d>Mat[now][0]) continue;
    for (int i = 1; i < N+2; i++)
    {
      if(i==now) continue;
      double nd = d+Mat[now][i];
      if(nd>Mat[i][0]) continue;
      if(nd==Mat[i][0] && seen[i]) continue;
      Mat[i][0]=nd;
      Mat[0][i]=nd;
      seen[i] = true;
      pq.emplace(nd,i);
    }
  }
  cout << fixed << setprecision(10) << Mat[s][t] << endl;

  return 0;
}

int main()
{
  input();
  solve();
  return 0;
}


Measured memory_bytes: 14076
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
int main(){
	int n=read();
	for(int i=1;i<=n;i++)if(read()&1){
		puts("first"); return 0;
	}
	puts("second");
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;
const int maxn = 1e5 + 5;

int k,n;
int a[maxn];
int cha[maxn];
long long ans;

int main()
{
	cin >> k >> n;
	for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
	sort(a + 1,a + 1 + n);
	if(k >= n){
		printf("0\n");
		return 0;
	}
	for(int i = n;i >= 1; i--) {
		cha[i] = a[i] - a[i - 1];
	}//cha[1] = a[1]

//for(int i = 1;i <= n; i++) cout << a[i] << "a[i] ";
//cout << endl;
//for(int i = 1;i <= n; i++) cout << cha[i] << "cha_cur  ";
//cout << endl;
	sort(cha + 2,cha + 1 + n);
//for(int i = 1;i <= n; i++) cout << cha[i] << "cha[i]pai ";
//cout << endl;
	int cur = n - k;
	for(int i = 2;i <= cur + 1; i++) {
		ans += cha[i];
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 1024
N, M = map(int, raw_input().split())
B = [1]*N
R = [True]+[False]*(N-1)
for i in range(M):
    x, y = map(int, raw_input().split())
    x -= 1
    y -= 1
    B[y] += 1
    if R[x]:
        R[y] = True
    B[x] -= 1
    if B[x]==0:
        R[x] = False
print sum(map(int, R))


Measured memory_bytes: 8180
from numba import njit
from math import gcd

K = int(input())

@njit
def solve():
    ans = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                ans += gcd(gcd(a, b), c)
    return ans

print(solve())

Measured memory_bytes: 111600
#include <stdio.h>
 
using namespace std;
 
 
int main(){
    int a,b,count,s;
 
    while(scanf("%d %d",&a,&b)!=EOF){
        count=0;
        s=a+b;
        while(s!=0){
            s/=10;
            count++;
        }
        printf("%d\n",count);
    }
 
    return 0;
}


Measured memory_bytes: 2736
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<vector<int>>c(3,vector<int>(3));
  vector<int>x(3),y(3);
  x.at(0)=0;
  for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>c.at(i).at(j);
  for(int i=0;i<3;i++)y.at(i)=c.at(0).at(i)-x.at(0);
  for(int i=0;i<3;i++)x.at(i)=c.at(i).at(0)-y.at(0);
  bool good =true;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(x.at(i)+y.at(j)!=c.at(i).at(j)){
        good=false;
      }
    }
  }
  if(good)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

int main(){
    double a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    vector<double> x, y;

    for(int i=0; i<=f; i++){
        for(int j=0; j<=f; j++){
            if(100*a*i + 100*b*j <= f) x.push_back(100*a*i + 100*b*j);
        }
    }

    for(int i=0; i<=f; i++){
        for(int j=0; j<=f; j++){
            if(c*i + d*j <= f) y.push_back(c*i + d*j);
        }
    }

    double ans = 0;
    int s = 0, w = 0;
    if(min(100*a, 100*b) <= f) w = min(100*a, 100*b);
    for(int i=0; i<x.size(); i++){
        for(int j=0; j<y.size(); j++){
            if(x[i] != 0 && y[j]/(x[i]+y[j]) <= e/(100+e) && x[i]+y[j] <= f){
                if(ans < y[j]/(x[i]+y[j])){
                    ans = y[j]/(x[i]+y[j]);
                    s = y[j];
                    w = x[i];
                }
            }
        }
    }
    cout << s+w << " " << s << endl;
    return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
int n,k;
  cin >> n>>k;
  vector<int> a(n,0);
  for(int i=0;i<n;i++)
    cin >> a[i];
  vector<int> dp(n,INT_MAX);
  dp[0]=0;
  for(int i=0;i<n;i++)
  {
    for(int j=i+1;j<=i+k;j++)
    {
      if(j<n)
      dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
    }
  }
  cout<< dp[n-1];
}

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

int minSteps(int height[], int n)
{
  int dp[100005] = {0};
  dp[2] = abs(height[1] - height[0]);
  
  for(int i=3;i<=n;i++)
  {
    dp[i] = min((abs(height[i-1]-height[i-2]) + dp[i-1]),(abs(height[i-1]-height[i-3])+dp[i-2]));
  }
  
  return dp[n];
}

int main()
{
  int n;
  cin>>n;
  
  int height[n];
  
  for(int i=0;i<n;i++)
    cin>>height[i];
  
  cout<<minSteps(height,n);
}


Measured memory_bytes: 1024
/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 100010;

ll n, A[maxn], B[maxn];
map<ll, vi> g;
map<ll, ll> in, out;
set<ll> vis;

void dfs(ll x) {
    vis.insert(x);
    for (auto y : g[x]) if (vis.count(y) == 0) dfs(y);
}

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

    cin >> n;
    fori (i, n) cin >> A[i];
    fori (i, n) cin >> B[i];

    ll brk = 0, xr = 0;
    fori (i, n) {
        xr ^= A[i];
        if (A[i] != B[i]) {
            ++brk;
            g[A[i]].eb(B[i]);
            g[B[i]].eb(A[i]);
            ++out[A[i]];
            ++in[B[i]];
        }
    }
    if (brk == 0) return cout << "0\n", 0;

    ll comp = 0, st = -1;
    for (auto x : g) {
        if (out[x.F] < in[x.F]) {
            if (in[x.F] - out[x.F] == 1 && st == -1 && x.F == xr) st = x.F;
            else return cout << "-1\n", 0;
        }
        if (vis.count(x.F) == 0) ++comp, dfs(x.F);
    }
    if (vis.count(xr) == 0) ++comp;

    cout << brk + comp - 1 << '\n';

}


Measured memory_bytes: 37124
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( int &x, char c = getchar(), bool f = 0 ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) f = c=='-' ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
	if (f) x = -x ;
}
const int maxn = 105 ;
int n, m, a[maxn][5], f[maxn][5] ;
int main() {
	int i, j ;
	Read(n) ;
	for ( j = 0 ; j < 2 ; j ++ )
		for ( i = 1 ; i <= n ; i ++ )
			Read(a[i][j]) ;
	for ( i = n ; i ; i -- )
		f[i][1] = f[i + 1][1] + a[i][1] ;
	for ( i = n ; i ; i -- )
		f[i][0] = max(f[i + 1][0], f[i][1]) + a[i][0] ;
	cout << f[1][0] << endl ;
	return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }

template <ll M = MOD> struct modint {
    ll val;
    modint(const ll x = 0) : val(x) {
        val = x;
        while(val < 0) val += M;
        while(val > M) val -= M;
    }

    modint operator+(const modint a) const { return modint(*this) += a; }
    modint operator-(const modint a) const { return modint(*this) -= a; }
    modint operator*(const modint a) const { return modint(*this) *= a; }
    modint operator/(const modint a) const { return modint(*this) /= a; }
    modint operator-() const { return modint(M-val); }
    modint inv() const {
        ll u = 1, v = 0, s = 0, t = 1, m = M, x = val;
        while (x) {ll q = m/x; swap(s -= q*u, u); swap(t -= q*v, v); swap(m -= q*x, x); }
        if(s < 0) s += M;
        return modint(s);
    }
    modint pow(ll n) const {
        ll u = 1, xx = val;
        while (n > 0){ if (n&1) u = u * xx % M; xx = xx * xx % M; n >>= 1; }
        return modint(u);
    }
    modint& operator+=(const modint a){ val += a.val; if(val >= M) val -= M; return *this; }
    modint& operator-=(const modint a){ val -= a.val; if(val < 0) val += M; return *this; }
    modint& operator*=(const modint a){ val = val * a.val % M; return *this; }
    modint& operator/=(const modint a){ val = val * a.inv().val % M; return *this;}

    modint& operator=(const int& x){
        val = x;
        while(val < 0) val += M;
        while(val > M) val -= M;
        return *this;
    }
};

using mint = modint<MOD>;

int main() {
    int n; string s;
    cin >> n >> s;
    auto dp = make_v(n, n+1, mint(0));
    dp[0][0] = 1;
    for (int i = 0; i < n-1; ++i) {
        if(s[i] == '<'){
            for (int j = 0; j <= i; ++j) {
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j];
            }
        }else {
            for (int j = i; j >= 0; --j) {
                dp[i+1][j] = dp[i+1][j+1] + dp[i][j];
            }
        }
    }
    cout << accumulate(dp.back().begin(),dp.back().end(), mint(0)).val << "\n";
    return 0;
}

Measured memory_bytes: 70656
#include <cstdio>
#include <iostream>
#include <set>

using namespace std;

int graph[500][500];
set<int> s;

int n, m;

void rec(int depth, int fr)
{
	if (depth == 3) return;

	s.insert(fr);

	for (int i = 0; i < n; ++i) {
		if (i == fr) continue;
		if (graph[fr][i]) {
			rec(depth + 1, i);
		}
	}
}

int main()
{
	while (cin >> n >> m, n || m) {
		for (int i = 0; i < 500; ++i) for (int j = 0; j < 500; ++j) {
			graph[i][j] = 0;
		}

		for (int i = 0; i < m; ++i) {
			int a, b; cin >> a >> b;
			a--; b--;
			graph[a][b] = graph[b][a] = 1;
		}

		s.clear();

		rec(0, 0);

		cout << s.size() - 1 << endl;
	}
}

Measured memory_bytes: 2184
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int A, B;

void recur(int nA, int nB, string s)
{
	if (nA == A && nB == B){
		printf("%s\n", s.c_str());
		return;
	}
	else if (max(nA, nB) >= 5 && min(nA, nB) <= 3) return;
	
	if (nA < A && (nA <= nB || nA - nB <= 3)){
		recur(nA + 1, nB, s + "A");
	}
	
	if (nB < B && (nB <= nA || nB - nA <= 3)){
		recur(nA, nB + 1, s + "B");
	}
}

int main()
{
	scanf("%d %d", &A, &B);
	
	recur(0, 0, "");
	
	return (0);
}

Measured memory_bytes: 1044
n, k = map(int, input().split())
num_list = list(map(int,input().split()))
sum = 0
smallest = 1000
smallest_i = 0
for j in range(k):
    smallest = 1000
    for v, i in enumerate(num_list):
        if i < smallest:
            smallest = i
            smallest_i = v
    sum += smallest
    num_list[smallest_i] = 1000

print(sum)





Measured memory_bytes: 9192
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	Scanner reader=new Scanner(System.in);
	int N= reader.nextInt();
	int tab[];
	int can=0;
	for(int i=1;i<=N;i++) {
		can=can+i;
		
	}
	System.out.print(can);
	}

}


Measured memory_bytes: 19924
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <stack>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int n;
ll a[200020];

bool check(ll k){
  stack<pair<ll,int>> st;
  for(int i=0;i<n-1;i++){
    if(a[i]>=a[i+1]){
      while(st.size()&&st.top().first>a[i+1]){
        st.pop();
      }

      if(st.size()&&st.top().first==a[i+1]){
        st.top().second++;
      }else{
        st.push(make_pair(a[i+1],1));
      }

      while(st.top().second==k){
        ll z=st.top().first;
        if(z==1) return false;

        st.pop();
        if(st.size()&&st.top().first==z-1){
          st.top().second++;
        }else{
          st.push(make_pair(z-1,1));
        }
      }
    }
  }
  return true;
}

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

  bool inc=true;
  for(int i=0;i<n-1;i++){
    if(a[i]>=a[i+1]) inc=false;
  }
  if(inc){
    cout<<1<<endl;
    return 0;
  }

  ll l=1,r=n;
  while(r-l>1){
    ll mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid;
  }

  cout<<r<<endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <string>
#define shosu(x) fixed<<setprecision(x)
using namespace std;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,P> pip;
typedef long long ll;
const int inf=1<<30;
const double pi=acos(-1);

int n;
vi sosu;

int nibu(int s,int t,int x){
	if(t-s==1) return s;
	int k=(s+t)/2;
	if(sosu[k]>x) return nibu(s,k,x);
	else return nibu(k,t,x);
}

int main(){
	vector<bool> used(50105,1);
	for(int i=2;i<50100;i++){
		if(used[i]){
			sosu.push_back(i);
			for(int j=i+i;j<=50100;j+=i) used[j]=0;
		}
	}
	while(cin>>n){
		int tmp=nibu(0,sosu.size(),n);
		if(sosu[tmp]==n) cout<<sosu[tmp-1]<<' '<<sosu[tmp+1]<<endl;
		else cout<<sosu[tmp]<<' '<<sosu[tmp+1]<<endl;
	}
}

Measured memory_bytes: 1280
#include<stdio.h>
#include<algorithm>
using namespace std;
#include<math.h>
int main(){
	int a[3];
	int n;
	scanf("%d",&n);
	while(n>0){
		scanf("%d %d %d",&a[0],&a[1],&a[2]);
		sort(a,a+3);
		
		if(a[0]*a[0] +a[1]*a[1]==a[2]*a[2]){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
		n--;
	}
	
}

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

using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;

#define out(a) cout << a << endl
#define out1(a) cout << a
#define in(a) cin >> a
#define in2(a, b) cin >> a >> b
#define in3(a, b, c) cin >> a >> b >> c
#define rep(i, N) for (ll i = 0; i < (ll)N; i++)
#define rep1(i, N) for (ll i = 1; i <= (ll)N; i++)
#define repi(i, j, N) for (ll j = (ll)i + 1; j < (ll)N; j++)
#define all(v) v.begin(), v.end()

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

constexpr int inf = 1e9;
constexpr ll linf = 1e18;
constexpr ll mod = 1e9 + 7;

void solve();

int main()
{
    solve();
}

void solve()
{
    string s;
    in(s);
    int flag = 1;
    if (s.length() % 2 == 1)
    {
        flag = 0;
    }
    else
    {
        rep(i, s.length())
        {
            if (i % 2 == 0 && s[i] != 'h')
            {
                flag = 0;
                break;
            }
            else if (i % 2 == 1 && s[i] != 'i')
            {
                /* code */
                flag = 0;
            }
        }
    }
    if (flag)
    {
        out("Yes");
    }
    else
    {
        out("No");
    }
}

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

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

  int l[n];
  int r[n];
  int people = 0;
  for(int i=0;i<n;i++){
    cin >> l[i] >> r[i];
    people += r[i] - l[i] + 1;
  }

  cout << people << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
void test_cases(){
    int n, x, m;
    cin >> n >> x >> m;
    int ans = x;
    set<int> s;
    s.insert(x);
    int i = 1;
    vector<int> v;
    v.push_back(0);
    v.push_back(x);
    while(i < n){
        x = (x * x) % m;
        if(x <= 1){
            break;
        }
        if(s.find(x) != s.end()){
            break;
        }
        s.insert(x);
        ans += x;
        v.push_back(x);
        i++;
    }
    if(x == 1){
        ans += (n - i);
    }
    else if(x > 1 && i < n){
        int k;
        for(k = 0; k <= i; k++){
            if(v[k] == x) break;
        }
        int len = i - k + 1;
        vector<int> pref(len + 1);
        pref[0] = 0;
        for(int j = k; j <= i; j++){
            pref[j - k + 1] = pref[j - k] + v[j];
        }
        int j = (n - i) / len;
        ans = ans + pref[i - k + 1] * j;
        j = (n - i) % len;
        ans += pref[j];
    }
    cout << ans << endl;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
//    cin >> tt;
    while(tt--){
        test_cases();
    }
    return 0;
}


Measured memory_bytes: 6368
<?php /*atcoder.php*/

$at = new Atcoder();
$at->main();
unset($at);

class Atcoder{
	private function arrayIn(){
		$buf = explode(" ", fgets(STDIN));
		return $this->killNewLine($buf);
	}
	private function killNewLine($buf = null){
		$buf = str_replace("\r\n", "", $buf);
		$buf = str_replace("\n", "", $buf);
		$buf = str_replace("\r", "", $buf);
		return $buf;
	}

	public function main(){
		$s[] = $this->arrayIn();
		$s[] = $this->arrayIn();
		$s[] = $this->arrayIn();

		$flg = array(0, 0, 0, 0);

		foreach($s as $a){
			foreach($a as $v){
				if(1 == $v){$flg[0]++;}
				if(2 == $v){$flg[1]++;}
				if(3 == $v){$flg[2]++;}
				if(4 == $v){$flg[3]++;}
			}
			unset($v);
		}
		unset($a);

		foreach($flg as $v){
			if(3 <= $v){
				echo "NO\n";
				return false;
			}
		}
		unset($v);
		echo "YES\n";
	}
}
?>


Measured memory_bytes: 4604
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin,v.end()
using namespace std;
typedef pair<string,int>P;

int n;
string s[10009];

int s1(char c){
  string t[n];
  r(i,n)t[i]=s[i];
  r(i,n){
    r(j,t[i].size()){
      if(t[i][j]=='?')t[i][j]=c;
    }
  }
  vector<P>v;
  r(i,n)v.push_back(P(t[i],i));
  sort(v.begin(),v.end());
  r(i,n){
    if(v[i].second==n-1)return i;
  }
}

int s2(char c){
  string t[n];
  r(i,n)t[i]=s[i];
  r(i,n){
    r(j,t[i].size()){
      if(t[i][j]=='?')t[i][j]=c;
    }
  }
  vector<P>v;
  r(i,n)v.push_back(P(t[i],i));
  stable_sort(v.begin(),v.end());
  r(i,n){
    if(v[i].second==0)return i;
  }
}

main(){
  cin>>n;n++;
  r(i,n)cin>>s[i];
  int a1=s1('a');
  int a2=s1('z');
  swap(s[0],s[n-1]);
  int a3=s2('a');
  int a4=s2('z');
  //cout<<a1<<' '<<a3<<' '<<a2<<' '<<a4<<endl;
  int a=min({a1,a2,a3,a4});
  int b=max({a1,a2,a3,a4});
  for(int i=a;i<=b;i++){
    if(i!=a)cout<<' ';
    cout<<i+1;
  }
  cout<<endl;
}

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

#define pr16 

#ifdef pr16
  #define pr(x)                 cerr << #x << ": " << x << endl;
  #define pr2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  #define pr3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  #define pr4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  #define pr5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  #define pr6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  #define prdd(a,r,c) for(long long i=0;i<(r);i++) { for(long long j = 0;j<(c);j++) cerr<<a[i][j]<<" "; cerr<<endl; } cerr<<endl;
  #define prc(a) tr(a, it) cerr<<*(it)<<" "; cerr<<endl
  #define pra(a,n) for(long long i=0; i<(n); i++) cerr<<((a)[i])<<" "; cerr<<"\n"
  #define prdd(a,r,c) for(long long i=0;i<(r);i++) { for(long long j = 0;j<(c);j++) cerr<<a[i][j]<<" "; cerr<<endl; } cerr<<endl; 
  #define prddd(a,x,y,z) for(long long i=0;i<x;i++) {cerr<<"layer "<<i<<":\n";prdd(a[i],y,z)}
 
#else
  #define pr(x)
  #define pr2(x, y)
  #define pr3(x, y, z)
  #define pr4(a, b, c, d)
  #define pr5(a, b, c, d, e)
  #define pr6(a, b, c, d, e, f)
  #define prc(a)
  #define pra(a,n)
  #define prdd(a, r, c)
  #define prddd(a,x,y,z)
#endif



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n;
    cin>>n;
    long long a[n];
    for(long long i = 0; i< n; i ++) {
    	cin >> a[i];
    }

    long long cash = 1000, stock = 0;

    for(long long i = 0; i< n; i ++) {
    	if (i == n-1 or a[i] >= a[i+1]) {
    		cash += stock * a[i];
    		stock = 0;
    	} else {
    		long long ext = cash / a[i];
    		stock += ext;
    		cash -= ext * a[i];
    	}
    	pr2(stock, cash)
    }

    cout << cash;

    return 0;
}

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

int main() 
{
	int n, k;
    cin >> n >> k;
    auto h = vector<int>(n);
    for(int i = 0; i < n; ++i)
        cin >> h[i];
    auto dp = vector<int>(n, 0);
    dp[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; ++i)
    {
        auto curr = abs(h[i] - h[i - 1]) + dp[i-1];
        for(int j = 2; j <= k; j++)
        {
            if(i - j < 0)
                break;
            auto cand = abs(h[i] - h[i - j]) + dp[i - j];
            if (curr > cand)
                curr = cand;
        }
        dp[i] = curr;
    }
    cout << dp[n - 1];
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>

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

	int N;
	string S;

	cin >> N >> S;

	if(N % 2 == 1) {
		cout << "No";
		return 0;
	}

	for(int i = 0; i < N / 2; i++) {
		if(S[i] != S[i + N / 2]) {
			cout << "No";
			return 0;
		}
	}

	cout << "Yes";
}


Measured memory_bytes: 256
import sys


fin = sys.stdin.readline

N = int(fin())
b_list = [int(elem) for elem in fin().split()]

if any(b > i + 1 for i, b in enumerate(b_list)):
    print(-1)
    exit(0)

procedure = []
for i in range(N):
    b = b_list[i]
    distance = i + 1 - b
    procedure.insert(i - distance, b)
print(*procedure, sep="\n")

Measured memory_bytes: 3064
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
#include <fstream>
#include <cmath>
#include <iomanip>      // std::setprecision

#include <chrono>
#include <thread>
#include <stack>
#include <memory.h>
#include <numeric>
#include <iostream>
#include<climits>

//  vector<vector<int>> b(row_size, vector<int>(col_size,n));   //  n->initialized value

#define MOD 1000000007LL
#define ff first
#define fs second
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vll vector<long long>
#define vvi vector< vector <int> >
#define vpii vector< pair<int, int> >
#define pii pair<int,int>
#define mii map<int, int>
#define mp make_pair
#define tc                int T;cin>>T;while(T--)
#define fast_io            ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long int

using namespace std;
double dp[3001][3001];
double solve(vector<double> & p, int n, int x) {
    if (x <= 0)return 1;
    if (n == 0)return 0;
    if (dp[n][x] > -0.9)return dp[n][x];
    return  dp[n][x] = p[n] * solve(p, n - 1, x - 1) + (1 - p[n]) * solve(p, n - 1, x);
}
int main() {
    fast_io;
    int n; cin >> n;
    memset(dp, -1, sizeof dp);

    vector<double> p(n + 1);

    for (int i = 1; i <= n; ++i)cin >> p[i];
    cout << fixed << setprecision(10) << solve(p, n, ((n + 1) / 2));
    return 0;
}


Measured memory_bytes: 70912
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
a, b = get_ints()
if a <= 0 and b >= 0:
    print("Zero")
elif a > 0 and b > 0:
    print("Positive")
else:
    if (b-a)&1:
        print("Positive")
    else:
        print("Negative")

'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Measured memory_bytes: 67104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  int sum = 0;
  for(int i = a; i <= b; i++) {
  string p = to_string(i);
    if(p.at(0) == p.at(4) && p.at(1) == p.at(3)) {
      sum ++;
    }
  }
  cout<< sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT64_MAX;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;
using Vi = vector<long long int>;
typedef pair<int, int> P; typedef pair<ll, ll> PLL;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
typedef vector<vector<ll> > matrix;
void princ(auto x){cout<<x<<" ";}; void print(auto x){cout<<x<<"\n";};
///////////////////////////////////////////////////////////////////////////////////

ll n,m;


int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>n>>m;
    ll ans = 0;
    ans += n*(n-1)/2;
    ans += m*(m-1)/2;
    print(ans);
    return 0;
}

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var W = input[1];
            var Vmax = Enumerable.Repeat(long.MinValue, W + 1).ToArray();
            Vmax[0] = 0;
            for (int i = 0; i < N; i++)
            {
                input = ReadArrayInt();
                var w = input[0];
                var v = input[1];
                for (int j = W; j >= w; j--)
                {
                    if (Vmax[j-w] != long.MinValue)
                    {
                        if (Vmax[j - w] + v > Vmax[j]) Vmax[j] = Vmax[j - w] + v;
                    }
                }
            }

            Console.WriteLine(Vmax.Max());
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define pb push_back

struct UnionFind {
    
    vec par;
    
    UnionFind(ll N) {
        par = vec(N, -1);
    }

    ll root(ll x) {
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    } 

    void unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if(rx == ry) return;
        par[rx] = ry;
    }

    bool same(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }

};

int main()
{
    ll N, M, K;
    cin >> N >> M >> K;
    mat GF(N), GB(N);
    UnionFind T(N);
    ll a, b;
    REP(i,0,M) {
        cin >> a >> b;
        --a; --b;
        GF[a].pb(b);
        GF[b].pb(a);
        T.unite(a, b);
    }
    REP(i,0,K) {
        cin >> a >> b;
        --a; --b;
        GB[a].pb(b);
        GB[b].pb(a);
    }

    map<ll,ll> n_node;
    REP(i,0,N) ++n_node[T.root(i)];

    ll ans;
    REP(i,0,N) {
        ans = n_node[T.root(i)] - 1 - SZ(GF[i]);
        FORR(nv,GB[i]) {
            if(T.same(i, nv)) --ans;
        }
        PS(ans);
    }
    PR("");

    return 0;
}

/*



*/

Measured memory_bytes: 17408
/**
 *    author: gxfireball       
**/
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
using namespace std;

void solve(){
   ll a,b,c,k;
   cin >> a >> b >> c >> k;
 
	if(k <=a){
		cout << k ;
		return;
	}
	else if(k <= a+b){
		cout << a ;
		return;
	}
	else{
		ll temp = k - (a+b);
		cout << a - temp ;
		return;
	}
   
}

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



Measured memory_bytes: 3652
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		ans += a - 1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256