akhauriyash/Code-Regression huggingface dataset:
N, K = [int(i) for i in input().strip().split(" ")]

a = 0
for i in range(N):
  p = i + 1
  j = 0
  while p < K:
    p = p * 2
    j = j + 1

  a = a + (1 / N * 0.5 ** j)

print(a)

Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

int main() {
	ios_base::sync_with_stdio( false );

	string S;
	cin >> S;

	vector<string> a;
	a.emplace_back( 1, S[0] );

	string t;
	for( int i = 1; i < S.size(); ++i ) {
		t += S[i];

		if( t != a.back() ) {
			a.push_back( t );
			t = "";
		}
	}

	cout << a.size();

	return 0;
}


Measured memory_bytes: 11016
/* * * * * * * * * * * **
*                      *
*	   saurabh8522	   *
*	  I will handle	   *
*		   IT.		   *
*                      *
* * * * * * * * * * * **/
#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ld long double
#define zero(a) memset((a),0,sizeof((a)))
#define one(a) memset((a),1,sizeof((a)))
#define minus(a) memset((a),-1,sizeof((a)))
#define all(g) g.begin(),g.end()
#define ppb pop_back
using namespace std;
typedef long long int ll;
#define MOD 1000000007
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll modpow(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
ll numdigit(ll n){return floor(log10(n)) + 1;}
bool isPowerTwo (ll x) { return x && (!(x&(x-1))); } 
int  main(){
	FastRead;
	ll t=1;
	// cin>>t;
	while(t--){
		ll h,w;
		cin>>h>>w;
		vector<string>v(h);
		for(int i=0;i<h;i++){
			cin>>v[i];
		}
		int dp[h][w];
		zero(dp);
		for(int i=0;i<w;i++){
			if(v[0][i]=='.'){
				dp[0][i]=1;
			}
			else{
				dp[0][i]=0;
				break;
			}
		}
		for(int i=0;i<h;i++){
			if(v[i][0]=='.'){
				dp[i][0]=1;
			}
			else{
				dp[i][0]=0;
				break;
			}
		}
		for(int i=1;i<h;i++){
			for(int j=1;j<w;j++){
				if(v[i][j]=='.'){
					dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
				}
				else{
					dp[i][j]=0;
				}
			}
		}
		cout<<dp[h-1][w-1]<<endl;
	}
}

Measured memory_bytes: 5248
def runlength(S):
    d = []
    cnt = 1
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            d.append(cnt)
            cnt = 1
        else:
            cnt += 1
    else:
        d.append(cnt)
    return d


def main():
    S = input()

    d = runlength(S)
    ans = [0] * len(S)
    pre = 0
    for i in range(0,len(d),2):
        tmp = d[i] + d[i+1]
        if d[i] % 2 == 0:
            ans[pre+d[i]-1] = tmp // 2
            ans[pre+d[i]] = tmp - ans[pre+d[i]-1]
        else:
            ans[pre+d[i]] = tmp // 2
            ans[pre+d[i]-1] = tmp - ans[pre+d[i]]

        pre += tmp

    print(*ans)






if __name__ == "__main__":
    main()

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

// colours
#define RESET   "\033[0m"
#define BLACK   "\033[30m"
#define RED     "\033[31m"
#define GREEN   "\033[32m"
#define YELLOW  "\033[33m"
#define BLUE    "\033[34m"
#define MAGENTA "\033[35m"
#define CYAN    "\033[36m"
#define WHITE   "\033[37m"

// debugging : values of variables
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << YELLOW << "debug statement : " << *it << " = " << a << RESET << endl;
    err(++it, args...);
} 

void testCase(){
    long long K;
    cin>>K;
    long long P = 100;
    int i = 0;
    while(P < K){
        P *= 1.01;
        i++;
    }
    cout<<i<<endl;
}

int main(){
    int t;
    t = 1;
    // cin>>t;
    while(t--){
        testCase();
    }
}

Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int num;
string X;
string Y;
char c1,c2;
int longest;
int L[1010][1010];
int main()
{
    cin>>num;
    for(int i=0;i<num;i++)
    {
        longest=0;
        cin>>X>>Y;
        for(int m=0;m<=X.size();m++)
            for(int n=0;n<=Y.size();n++)
            {
                if(m<=0||n<=0)
                    L[m][n]=0;
                else if(X[m-1]==Y[n-1])
                    L[m][n]=1+L[m-1][n-1];
                else
                    L[m][n]=max(L[m][n-1],L[m-1][n]);
            }
        for(int a=0;a<=X.size();a++)
            for(int b=0;b<=Y.size();b++)
            {
                if(L[a][b]>longest)
                    longest=L[a][b];
            }
        cout<<longest<<endl;
    }
    return 0;
}


Measured memory_bytes: 7104
#include <iostream>
#include <array>

int main() {
	std::string s;
	std::cin >> s;

	// 2種類のみの場合は抜く
	std::array<size_t, 'z' - 'a' + 1> appeared{};
	for (size_t i = s.length() - 1; i >= 3; --i) {
		if (s[i] == s[i - 2] && s[i - 1] == s[i - 3]) {
			s.erase(i - 1, 2);
		}
	}

	for (size_t i = 0; i < s.length(); ++i) {
		appeared[s[i] - 'a']++;
	}
	size_t appeared_char_var = 0;
	for (size_t a : appeared) {
		if (a) {
			appeared_char_var++;
		}
	}

	if (appeared_char_var == 2) {
		std::cout << "Second" << std::endl;
		return 0;
	}

	size_t end = s.length() - 2;
	size_t c = 0;

	do {
//		std::cerr << end << std::endl;
		if (s.length() <= end + 1) {
			end = s.length() - 2;
			continue;
		}
		// その文字が抜けるとき
		if (s[end - 1] != s[end + 1]) {
			c++;
			if (end >= 3 && s[end - 3] == s[end - 1] && s[end - 2] == s[end + 1]) {
				s.erase(end - 1, 3);
			} else if (end + 3 < s.length() && s[end - 2] == s[end + 1] && s[end - 1] == s[end + 2]) {
				s.erase(end, 3);
			} else if (end + 3 < s.length() && s[end - 1] == s[end + 2] && s[end + 1] == s[end + 3]) {
				s.erase(end, 3);
			} else {
				s.erase(end, 1);
			}
			end++;
		} else {
			end--;
		}
	} while (1 <= end);
	if (c & 1) {
		std::cout << "First" << std::endl;
	} else {
		std::cout << "Second" << std::endl;
	}
}


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

using namespace std ;

int main ()
{
    int A , B ;

    cin >> A >> B ;


    if (A >= 1 && A <= 13 && B >= 1 && B <= 13 )
    {
        if (A == B)
            cout << "Draw";

        else if (A == 1)
        {
            A = A + B ;

        }
        else if (B == 1)
        {
            B = B + A ;
        }

        if (A > B)
            
            cout << "Alice";
        
        else if (B > A)
        
            cout << "Bob";

    }
    else
        cout << "Please enter a valid number";
}

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

int main(){
   ll n,i;


   cin>>n;
   ll a[n+9],b[n+9];


    for(i=1;i<=n;i++){
    cin>>a[i];
   }
  sort(a+1,a+1+n);
  ll s=0,p=0,q=0;
  for(i=n;i>1;i--){
    if(a[i]==a[i-1] && a[i]!=p){


        if(s==0) {
            p=a[i];
            s=1;
        }
        if(s==1 && a[i]!=p){
            q=a[i];
            break;
        }
    }
  }
  ll x=0;
   for(i=n;i>1;i--){
    if(a[i]==a[i-1] && a[i]==a[i-2]&& a[i]==a[i-3]){

       x=a[i];
       break;
    }
  }
  if(x==0 && p*q==0){
    cout<<0<<endl;
  }
 else if(p*q>x*x){
    cout<<p*q<<endl;
  }
  else cout<<x*x<<endl;

}



Measured memory_bytes: 4328
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

void solve(void)
{
  int H, N; cin >> H >> N;
  using Pair = pair<ll, ll>;
  vector<Pair> P(N);
  for(auto& p : P) {
    cin >> p.first >> p.second;
  }

  vector<vector<ll>> dp(N+1, vector<ll>(H+1, INF));
  for (int i = 0; i < (int)dp.size(); ++i) {
    dp[i][0] = 0;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= H; ++j) {
      if (j >= P[i].first) {
        dp[i + 1][j] = std::min(dp[i][j], dp[i + 1][j - P[i].first] + P[i].second);
      }
      else {
        dp[i + 1][j] = std::min(dp[i][j], dp[i + 1][0] + P[i].second);
      }
    }
  }

  // dp[0] = 0;
  // ll ans = INF;
  // for (int i = 0; i <= H; ++i) {
  //   if (dp[i] == -1) {
  //     continue;
  //   }
  //   for (const auto& p : P) {
  //     auto next = i + p.first;
  //     if (dp[i+p.first] != -1) {
  //       chmin(dp[i+p.first], dp[i] + p.second);
  //     } else {
  //       dp[i+p.first] = dp[i] + p.second;
  //     }
  //     if (next >= H) {
  //       chmin(ans, dp[i+p.first]);
  //     }
  //   }
  // }

  // cout << ans << CRLF;
  cout << dp[N][H] << CRLF;
  // for (int i = H; i < dp[N-1].size(); ++i) {
  //   if (dp[N-1][i] != INF) {
  //     cout << dp[N-1][i] << CRLF;
  //     return;
  //   }
  // }
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 78592
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;
using Graph = vector<vector<int>>;

static long long INF = (1LL<<62);

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string S; cin >> S;
	if(S[S.size()-1] == 's'){
		S += "es";
	}
	else{
		S += "s";
	}
	printf("%s\n", S.c_str());
	return 0;
}


Measured memory_bytes: 3644
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/05/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  constexpr ll MOD = 1e9+7;
  int n,k; cin>>n>>k;
  array<vector<ll>, 2> dp{vector<ll>(k+1), vector<ll>(k+1)};
  for (int i = 1; i <= n; i++) {
    int a; cin>>a;
    ll sum = 1;
    auto& pdp = dp[(i%2)^1];
    auto& cdp = dp[i%2];
    pdp[0] = 1;
    cdp[0] = 1;
    for (int s = 1; s <= k; s++) {
      (sum += pdp[s])%=MOD;
      cdp[s] = sum;
      if (s-a >= 0)
        (sum += MOD-pdp[s-a])%=MOD;
    }
//    for (auto v : cdp)
//      cerr<<v<<" ";
//    cerr<<endl;
  }
  cout << dp[n%2][k] << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using Graph = vector<vector<int>>;
const int INF = 1000000007;
class UnionFind{
  private:
    vector<int>par;
  public:
    UnionFind(int n):par(n,-1){}
    int root(int x){
      if(par[x] < 0)return x;
      return par[x] = root(par[x]);
    }
    bool unite(int x,int y){
      x = root(x); y = root(y);
      if (x == y) return false;
      if (par[x] > par[y]) swap(x, y);
      par[x] += par[y];
      par[y] = x;
      return true;
    }
    bool same(int x,int y){
      return root(x) == root(y);
    }
    int size(int x) {
      return -par[root(x)];
    }
};
int main(){
  ll d,t,s;
  cin >> d >> t >> s;
  if(s * t >= d)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

template<typename T>
void O(T t){
  cout << t << endl;
}

const ll mod = 1e9+7;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,s;
  cin >> n >> s;
  ll sum = 0;
  ll ans = inf;
  vector<ll> v(n);
  rep(i,n){
    cin >> v[i];
  }
  ll l = 0,r = 0;
  while(r < n){
    sum += v[r];
    ++r;
    while(l < r && sum - v[l] >= s){
      sum -= v[l];
      ++l;
    }
    if(sum >= s){
      ans = min(ans,r-l);
    }
  }
  cout << ((ans == inf) ? 0 : ans)  << endl;
  return 0;
}

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

bool isEven(int a, int b){
  if(a * b % 2 == 0) return true;
  return false;
}
int main()
{
  int a, b;
  cin >> a >> b;
  if (isEven(a, b))
  {
    cout << "Even" << endl;
  }
  else
  {
    cout << "Odd" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=500+10;
int a[maxn][maxn];
int i,j,k,l,t,n,m,d,h,w;
int main(){
	scanf("%d%d%d%d",&n,&m,&h,&w);
	d=2000;
	fo(i,1,n)
		fo(j,1,m)
			a[i][j]=d;
	fo(i,1,n/h)
		fo(j,1,m/w)
			a[h*i][w*j]=-(h*w-1)*d-1;
	t=0;
	fo(i,1,n)
		fo(j,1,m)
			t+=a[i][j];
	if (t<=0){
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	fo(i,1,n){
		fo(j,1,m) printf("%d%c",a[i][j],j==m?'\n':' ');
	}
}

Measured memory_bytes: 2432
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using D = double;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_num(LL n) { int ret = 0; while (n > 0) { ret ++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define RALL(qpqpq)           (qpqpq).rbegin(),(qpqpq).rend()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define RFOR(i,tptpt,ypypy)  for(LL i=(tptpt);i>=(ypypy);i--)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n, t[101], v[101], s[101], p[101010];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
		t[i] *= 2;
		s[i + 1] = s[i] + t[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> v[i]; 
		v[i] *= 2;
	}
	for (int i = 0; i <= s[n + 1]; i++) {
		for (int j = 1; j <= n + 1; j++) {
			if (s[j] >= i) { 
				p[i] = v[j - 1];
				break; 
			}
		}
		for (int j = 1; j <= n + 1; j++) {
			int dst = abs(s[j] - i);
			p[i] = min(p[i], dst + min(v[j - 1], v[j]));
		}
	}
	int sum = 0;
	for (int i = 0; i <= s[n + 1]; i++)sum += p[i];
	cout << fixed << setprecision(13) <<(double)sum/4<< endl;
}

Measured memory_bytes: 384
ss=input()
kk=int(input())

def c(s,k):
    for i in range(len(ss)):
        if int(s[i])==1:
            k-=1
            if k==0:
                return int(s[i])
        else:
            return int(s[i])
    return 0

print(c(ss,kk))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e6;
const int INF=1e9;
int main(){
	double W,H,x,y;cin>>W>>H>>x>>y;
	cout<<W*H/2<<" ";
	if(x==W/2&&y==H/2) cout<<1<<endl;
	else cout<<0<<endl;
}

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

int main() {
  int n;cin>>n;
  vector<int> a(n);
  rep(i,n){
    cin>>a[i];
    a[i]--;
  }
  int ans=a[0];
  rep(i,n){
    if(ans==1){
      cout<<i+1<<endl;
      return 0;
    }
    ans=a[ans];
  }
  cout<<-1<<endl;
}

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

using namespace std;

typedef long long LL;

LL calc(const vector<int>& v,const vector<int>& st)
{
    LL rtn = 0;
    for(int i = 1; i<st.size(); ++i)
    {
        LL tmp = 0;
        for(int j = st[i-1]; j<st[i] ; ++j)
        {
            tmp *= 10;
            tmp += v[j];
        }
        rtn += tmp;
    }
    LL tmp = 0;
    for(int j = st.back(); j<v.size() ; ++j)
    {
        tmp *= 10;
        tmp += v[j];
    }
    rtn += tmp;
    return rtn;
}

int main()
{
    LL val = 0;
    vector<int> v;
    while( 1 )
    {
        char c = getchar();
        if( c > '9' || c < '0' ) break;
        v.push_back(c-'0');
        val *= 10;
        val += ( c - '0' );
    }
    LL ans = val;
    vector<int> st(v.size(),0);
    for(int i = v.size()-1; i>=1; --i)
    {
        st[i] = 1;
        vector<int> go = st;
        do
        {
            vector<int> tmp;
            tmp.push_back(0);
            for(int i = 1; i<go.size(); ++i)
                if( go[i] ) tmp.push_back(i);
            ans += calc(v,tmp);
        } while( next_permutation(go.begin()+1,go.end()) );
    }
    printf("%lld\n",ans);
    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    int N = S.size();

    vector<char> s;
    rep(i, N) {
        if (S[i] != 'x') s.push_back(S[i]);
    }

    vector<char> t = s;
    reverse(t.begin(), t.end());
    if (s != t) {
        puts("-1");
        return 0;
    }

    int l = 0, r = N - 1;
    int ans = 0;
    while (l <= r) {
        if (S[l] == S[r]) {
            l++, r--;
        } else if (S[l] == 'x') {
            l++;
            ans++;
        } else if (S[r] == 'x') {
            r--;
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    a=sum(A)
    count=0
    for i in range(M):
        if A[i]>=a/(4*M):
            count+=1
    if count<M:
        print(NO)
    else:
        print(YES)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
// Devarshi

/*
We will not return to the countless mistakes of the past
I will not relive the failures of the man I once was

Only through dedication will I destroy all preconception

No longer will I let myself be truly satisfied with the standard
We will not return to the countless mistakes of the past

Only through dedication will I destroy all preconception

Let this be
Be the day
Day of my
My declaration
Let this be the day of my declaration

Join me,
Walk with me

Shatter the bonds that tie us
To what we strive to never be

Join me,
Walk with me
*/
#include<bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn=1000001;


int main(){

int a,b;
cin>>a>>b;

cout<<a*b-(a+b-1);

return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }

int main() {
    init();

    int n; cin >> n;
    map<ll, ll> m;
    ll ans = 0;
    eFOR(i, 1, n) {
        int a; cin >> a;
        ans += m[i-a];
        ++m[i + a];
    }
    print(ans);

    return 0;
}

Measured memory_bytes: 26360
N = gets.to_i
as = N.times.map{gets.to_i}
if as[0] != 0
    puts -1
    exit
end

last = as[-1] == 0 ? nil : as[-1]
now = as[-1]
ans = 0
(N-2).downto(0).each do |i|
    unless last
        if as[i] == 0
            next
        else
            last = as[i]
            now = as[i]
            next
        end
    end
    if as[i] == now - 1
        if as[i] == 0
            ans += last
            last = nil
        else
            now = as[i]
        end
    elsif as[i] < now - 1
        puts -1
        exit
    else
        ans += last
        last = as[i]
        now = as[i]
    end
end

puts ans


Measured memory_bytes: 5812
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = []
for i in range(H):
    grid.append(list(input()))


tate = [[0]*W for i in range(H)]
yoko = [[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if grid[i][j] == ".":
            cnt += 1
            yoko[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for j in range(W-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,yoko[i][j])
            yoko[i][j] = cnt
        else:
            cnt = 0

            
            
for j in range(W):
    cnt = 0
    for i in range(H):
        if grid[i][j] == ".":
            cnt += 1
            tate[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for i in range(H-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,tate[i][j])
            tate[i][j] = cnt
        else:
            cnt = 0

ans = 0

for i in range(H):
    for j in range(W):
        tmp = tate[i][j] + yoko[i][j] - 1
        ans = max(ans,tmp)

print(ans)

Measured memory_bytes: 247048
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
template<class T>
void puta(T&&t){cout<<t<<endl;}
template<class H,class...T>
void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}

int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vl a(n);
	rep(i,n){
		cin>>a[i];
		a[i]-=i+1;
	}
	sort(all(a));
	ll ans=0;
	rep(i,n){
		ans+=abs(a[i]-a[n/2]);
	}
	cout<<ans<<endl;;
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<utility>
#include<functional>
#include<algorithm>
#include<bitset>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#define int long long
using namespace std;
int n,m,x[1005][3],mx;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)
			cin>>x[i][j];
	for(int mask=0;mask<8;mask++)
	{
		vector<int>all;
		for(int i=1;i<=n;i++)
		{
			int t=mask;
			int val=0;
			for(int j=0;j<3;j++)
			{
				if(t&1)
					val+=x[i][j];
				else
					val-=x[i][j];
				t/=2;
			}
			all.push_back(val);
		}
		sort(all.begin(),all.end());
		reverse(all.begin(),all.end());
		int cur=0;
		for(int i=0;i<m;i++)
			cur+=all[i];
		mx=max(mx,cur);
	}
	cout<<mx;
	return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = long.Parse(Console.ReadLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = long.Parse(Console.ReadLine());
        }


        long Max = a.Max();
        long Second = 0;
        IEnumerable<long> tmp1 = a.Where(value => value < Max);
        IEnumerable<long> tmp2 = a.Where(value => value == Max);
        if (tmp1.Count() == 0)
        {

            Second = Max;
        }
        else if (tmp2.Count() > 1)
        {
            Second = Max;
        }
        else
        {

            Second = tmp1.Max();
        }

        for (int i = 0; i < n; i++)
        {
            if (a[i] == Max)
            {
                Console.WriteLine(Second);
            }
            else
            {
                Console.WriteLine(Max);
            }
        }
    }
}


Measured memory_bytes: 18132
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;

int main(){
    string s;
    cin >> s;
    int n = s.length();
    int ind = n-1;
    llong ans = 0;
    REPR(i,n-1){
        if(s[i] == 'B'){
            ans += ind - i;
            ind --; 
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;cin >> s;
	string ans="";
	for(int i=0;i<(1<<3);++i){
		int sum=s.at(0)-'0';
		rep(j,3){
			if(i&(1<<j)) sum+=s.at(j+1)-'0';
			else sum-=s.at(j+1)-'0';
		}
		if(sum==7){
			ans+=s.at(0);
			rep(j,3){
				if(i&(1<<j)) ans+='+';
				else ans+='-';
				ans+=s.at(j+1);
			}
			ans+="=7";
			break;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
		//Implement solution here.
		int n = ni();
		int k = ni();
		char[] ca = next().toCharArray();
		int[] cnta = new int[n];

		int cnt = 1;
		int aidx = 0;
		for(int i = 1; i < ca.length; i++) {
			if(ca[i] != ca[i-1]) {				
				cnta[aidx] = cnt;
				aidx++;
				cnt = 1;
			} else {
				cnt++;
			}
		}
		cnta[aidx] = cnt;
//		Arrays.stream(cnta).forEach(v -> System.out.print(v +","));
//		System.out.println();	
		
		boolean isz =  ca[0] == '0';
		int tmp = 0;
		int result = 0;
		int scnt = 0;
		for(int i = 0; i < cnta.length; i++) {
			if(cnta[i] == 0) break;
			if(isz) {
				tmp += cnta[i];				
				if(scnt >= k) {
					tmp -= cnta[i - (2*k)];
					if(i - (2*k) > 0) tmp -= cnta[i - (2*k) - 1];
				}
				scnt++;
			}else {
				tmp += cnta[i];				
			}
			isz = !isz;
			result = Math.max(result, tmp);
		}
		System.out.println(result);
	}

	//Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

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

int main() {
  // ここにプログラム
  int n, h, w, a, b;
  int ans = 0;
  cin >> n >> h >> w;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    if (h <= a && w <= b) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <functional>
using namespace std;
using ll = long long;

int main() {
	string S_, T;
	cin >> S_;
	cin >> T;
	string Q = "?";
	string A = "a";
	
	for (int i = S_.size() - 1; i >= 0; i--) {
		int c = 0;
		if (i < T.size() - 1) {
			cout << "UNRESTORABLE" << endl;
			return 0;
		}
		if (S_[i] == T[T.size() - 1] || Q[0]) {
			for (int j = 0; j < T.size(); j++) {
				if ((S_[i - j] != T[T.size() - 1 - j]) && (S_[i - j] != Q[0])) c = 1;
			}
			if (c == 0) {
				for (int j = 0; j < T.size(); j++) { S_[i - j] = T[T.size() - 1 - j]; }
				for (int i = S_.size() - 1; i >= 0; i--) {
					if (S_[i] == Q[0]) S_[i] = A[0];
				}
				cout << S_ << endl;
				return 0;
			}
		}
	}
	cin >> S_;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  char s[11];
  int i;
  
  for(i=0;i<11;i++){
    scanf("%c",&s[i]);
  }
  
  s[3]='8';
  
  for(i=0;i<11;i++){
    printf("%c",s[i]);
  }
  
  return 0;
}
  

Measured memory_bytes: 1576
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
k = 0
for i in range(n):
  if b[i] < a[i]:
    k += b[i]
  elif b[i] < a[i]+a[i+1]:
    k += b[i]
    a[i+1] = a[i] + a[i+1] - b[i]
  else:
    k += a[i] + a[i+1]
    a[i+1] = 0
print(k)

Measured memory_bytes: 18396
X = int(input())

if 400 <= X and X <= 599:
  print(8)
elif 600 <= X and X <= 799:
  print(7)
elif 800 <= X and X <= 999:
  print(6)
elif 1000 <= X and X <= 1199:
  print(5)
elif 1200 <= X and X <= 1399:
  print(4)
elif 1400 <= X and X <= 1599:
  print(3)
elif 1600 <= X and X <= 1799:
  print(2)
elif 1800 <= X and X <= 1999:
  print(1)

Measured memory_bytes: 9192
#include <stdio.h>
#include <vector>
#include <map>
#include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;

const long long M = 1e9 + 7;

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n, k;
  cin >> n >> k;
  int maxi = -1;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (a[i] > maxi) {
      maxi = a[i];
    }
  }
  int gcd = a[0];
  for (int i = 1; i < n; ++i) {
    gcd = __gcd(gcd, a[i]);
  }
  // cout << gcd << endl;
  if (k % gcd != 0) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  k /= gcd;
  sort(a.rbegin(), a.rend());
  a[0] /= gcd;
  if (a[0] >= k) {
    cout << "POSSIBLE" << endl;
    return 0;
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pic pair<int,char>
#define pci pair<char,int>
#define pll pair<ll,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define vic vector<pic>
#define vci vector<pci>
#define vlc vector<plc>
#define vcl vector<pcl>
#define pb push_back
const ll MOD=1e9+7;
const ll MAXN=1e5+3;
const ll MAXM=1e5+3;
double a;
double b1=1.0,b2=0.0;
int n;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        b2+=(double)1.0/a;
    }
    b1=b1/b2;
    cout<<fixed<<setprecision(10)<<b1<<endl;
return 0;
}


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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (n - 1); i > (a - 1); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define updiv(a, b) ((a + b - 1) / b)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, 1, -1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main(void) {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;
  vector<int> h(n + 1, 0), dp(n + 1, INF);
  rep(i, 0, n) cin >> h[i];

  dp[0] = 0;
  rep(i, 0, n) rep(j, 1, k + 1) chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
  cout << dp[n - 1] << '\n';
  return 0;
}

Measured memory_bytes: 4704
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    double x1, y1, x2, y2;

    cin >> x1 >> y1 >> x2 >> y2;

    cout << fixed << setprecision(5) << sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)) << endl;
    return 0;
}


Measured memory_bytes: 3220
MOD = 1000000007

def fact(n)
  (1..n).inject(1){ |ans,x| ans*x % MOD }
end

def pow(n, k)
  ans = 1
  while k > 0
    ans = ans*n % MOD if k.odd?
    n = n*n % MOD
    k >>= 1
  end
  ans
end

def comb(n, k)
  fact(n) * pow(fact(n-k),MOD-2) % MOD * pow(fact(k),MOD-2) % MOD
end

x, y = gets.chomp.split.map(&:to_i)

sum = x+y
x -= sum/3
y -= sum/3

if sum%3 != 0 || x < 0 || y < 0
  puts(0)
  exit
end


puts(comb(x+y, x))

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

using namespace std;

bool OK(unordered_map<char, int>& A, unordered_map<char, int>& B) {
    for (auto a : A) {
        if (B[a.first] != a.second) return false;
    }
    for (auto b : B) {
        if (A[b.first] != b.second) return false;
    }
    return true;
}

int main() {
    int N;
    cin >> N;
    unordered_map<string, int64_t> S;
    for (int i = 0; i < N; i++) {
        string A;
        cin >> A;
        unordered_map<char, int> B;
        for (char c : A) B[c]++;
        vector<string> V;
        for (auto kv : B) V.push_back(kv.first + to_string(kv.second));
        sort(V.begin(), V.end());
        string s = "";
        for (string v : V) s += v;
        S[s]++;
    }

    int64_t result = 0;
    for (auto kv : S) {
        result += (kv.second - 1) * kv.second / 2;
    }

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 12964
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;
const int MAX = 100010;
long long n,m,dist[MAX],used[MAX],a[MAX],color[MAX];
struct edge{long long to,cost;};
pair<pair<int,int>,long long> E[MAX];
vector<edge> G[MAX];

void dfs(int s,int x,int y){
    a[s] = y; dist[s] = x;used[s] = true;
    for(int i=0;i<G[s].size();i++){
        if(!used[G[s][i].to]) dfs(G[s][i].to,x+1,G[s][i].cost-y);
    }
}

bool bip(int i, int col) {
    if (color[i] == col) return true;
    if (color[i] != 0) return false;
    bool ok = true;
    color[i] = col;
    for (int u = 0;u<G[i].size();u++)
        ok &= bip(G[i][u].to, 3 - col);
    return ok;
}

bool check(){
    for(int i=0;i<m;i++){
        if(a[E[i].first.first]+a[E[i].first.second]!=E[i].second){
            return false;
        }
    }
    return true;
}

vector<edge> c,d;
long long dep[MAX],ml=0,l;
void cycle(int s,int dist){
	dep[s] = dist;
	for(edge e : G[s]){
		if(dep[e.to]==-1) {
			c.push_back(e);
			cycle(e.to,dist+1);
		}else if(dep[e.to]<dep[s]-1 && !(ml & 1)){
			ml = dep[s]+1-dep[e.to];
			if(ml & 1){
				c.push_back(e);
				l = e.to;
				for(int j =0; j<c.size();j++){
					edge p = c[j];
					d.push_back(p);
				}
			}
		}
	}
	if(!(ml & 1)){
		c.pop_back();
	}
}

int main(){
    int i;
    cin >> n >> m;
    for(i=0;i<m;i++){
        long long u,v,s;
        cin >> u >> v >> s;
        u--; v--;
        edge e; e.to = v; e.cost = s;
        G[u].push_back(e);
        e.to = u; e.cost = s;
        G[v].push_back(e);
        pair<int,int> p = make_pair(u,v);
        E[i] = make_pair(p,s);
    }
    long long min1 = 1000000000,min2 = 10000000000;
    dfs(0,0,0);
    for(i=0;i<n;i++){
        if(dist[i]%2==1){
            min1 = min(min1,a[i]);
        }else{
            min2 = min(min2,a[i]);
        }
    }
    if(bip(0,1)){
        if(!check()){
            cout << 0 << endl;
            return 0;
        }
        if(min1<=0){
            cout << 0 << endl;
        }else if(min1>0 && min2>=0){
            cout << min1-1 << endl;
        }else if(min1>=0 && min2<0){
            if(min1+min2<=0){
                cout << 0 << endl;
            }else{
            	cout << min1+min2-1 << endl;
            }
        }
    }else{
		for(i=0;i<n;i++){
        	dep[i] = -1;
   			used[i] = false;
   		}
    	cycle(0,0);
    	int x = 1,k = d.size() - ml;
    	long long sum = 0;
    	for(i=d.size()-1;i>=k;i--){
    		sum += x*d[i].cost;
    		x *= -1;
    	}
    	if(sum%2==1){
    		cout << 0 << endl;
    		return 0;
    	}
    	dfs(l,0,sum/2);
    	for(i=0;i<n;i++){
    		min1 = min(min1,a[i]);
    	}
    	if(check() && min1>0){
        	cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 22900
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 1000
//<<fixed << setprecision(9)
 
int main()
{
    int n,i,j,t,a;
    boost;
    int m;
    cin>>n>>m;
    int arr[n];
    rep(i,0,n)cin>>arr[i];
    pii crr[m];
    rep(i,0,m)
    {
        cin>>crr[i].S>>crr[i].F;
    }
    sort(arr,arr+n);
    sort(crr,crr+m);
    i=0;j=m-1;
    ll sum=0;
    while(i<n && j>=0)
    {
        if(arr[i]>=crr[j].F)
        {
            break;
        }
        else
        {
            arr[i]=crr[j].F;
            crr[j].S--;
            if(crr[j].S==0)
            {
                j--;
            }
            i++;
        }
    }
    for(auto z:arr)
    {
       // cout<<z<<"\n";
         sum+=z;
    }
    cout<<sum;
    return 0;
}



Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>vi;
vector<ll> :: iterator vt;
ll arr[200009];
int main()
{
    ll n,t,mul=1,i,j,flag =0,maxi=LONG_LONG_MIN,mini=LONG_LONG_MAX,sum=0,c=0;
    map<char,ll>mp;
    map<char,ll> :: iterator mt;
    string s, ss;

    cin>>n;
    for(i = 0 ; i<n ; i++)
    {
        cin>>t;
        sum+=--t;
    }
    cout<<sum<<endl;



    return 0;
}


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

int main(){
  ll x,i,a,b;
  cin >> x;
  a=100;
  for(i=1;i<=3760;i++){
    b=a+a/100;
    if((b>=x)&&(x>a)){
      cout << i;
    }
    a=b;
  }
}

Measured memory_bytes: 3632
float q;
A,B,C,D,E,F,R;
M(a,b,c,d,e,f){
	e=c-a;
	f=d-b;
	q=fabs(-f*a+e*b)/hypot(e,f);
	if(a*e+b*f<0&&c*e+d*f>0&&q<=R)
		if(q<R)
			return 2;
		else
			return 1;
	return 0;
}
I(){
	q=E*B-F*A;
	return(C*F-D*E)*q>0&q*(A*D-B*C)>0;
}
main(v,w,o,c){
	for(;scanf("%d%d%d%d%d%d%d%d%d",&A,&B,&C,&D,&E,&F,&v,&w,&R),A;){
		A-=v,B-=w;
		C-=v,D-=w;
		E-=v,F-=w;
		o=(A*A+B*B>R*R)+(C*C+D*D>R*R)+(E*E+F*F>R*R);
		if(!o)
			puts("b");
		else if(o==3){
			c=M(C,D,E,F)|M(E,F,A,B)|M(A,B,C,D);
			if(c&2)
				puts("c");
			else if(c&1){
				if(I())
					puts("a");
				else
					puts("c");
			}else{
				if(I())
					puts("a");
				else
					puts("d");
			}
		}else
			puts("c");
	}
	return 0;
}

Measured memory_bytes: 0