akhauriyash/Code-Regression huggingface dataset:
N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
time = 0
passenger = 0
count = 0

T.sort()

for t in T:

    if passenger == 0:
        #乗客が０なので一人目としてストックし、バスを確保
        time = t
        passenger = 1
        count += 1

    #２人目以降、定員以内
    elif 1 <= passenger < C:
        if t - time <= K:
            #乗って問題がないので追加
            passenger += 1
        else:       
            #一人目が時間オーバーになるのでバスを出して一人目になる
            count += 1
            passenger = 1
            time = t
            
    #２人目以降、定員オーバー
    else:
        #定員オーバーになるのでバスを出して一人目になる
        count += 1
        passenger = 1
        time = t
        
print(count)


Measured memory_bytes: 7508
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define pf push_front
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){return (int)s.size();}
const long long INF = 1LL << 60;

int main(){
    cout << fixed << setprecision(20);
    string s; cin >> s;
    int si = SIZE(s);
    ll ans = 0;
    vc<ll> a(200010); a[0]++;
    ll next = 1, cur = 0;
    for(int i = si-1; i >= 0; i--){
        cur = (cur+(s[i]-'0')*next)%2019;
        next = next*10%2019;
        ans += a[cur];
        a[cur]++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4932
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int a,b,c,d,e;
  int answer=0;
  cin>>a>>b>>c>>d>>e;
  answer+=(c-a)*60;
  if(b>=d){
  answer-=b-d;}
  else{
  answer+=d-b;}
  cout<<answer-e<<endl;
  }

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <tuple>
#include <cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

int N;
int a[310];
long double E[310][310][310]; //dp[a][b][c]:1貫の皿a枚,2貫の皿b枚,3貫の皿c枚のときの期待値(空の皿はない)

int main(void) {
    cin >> N;
    int count[3];
    count[0] = 0;
    count[1] = 0;
    count[2] = 0;
    
    REP(i, 1, N) {
        cin >> a[i];
        count[a[i]-1]++;
    }
    
    E[1][0][0] = 1.;
    E[0][1][0] = 2.;
    E[0][0][1] = 3.;
    
    REP(n, 2, N) {
        for (int i=n+1; i>=1; i--) {
            for(int j=n+2; j>=i+1; j--) {
                double pat1 = 0., pat2 = 0., pat3 = 0.;
                if (i-1 >= 1) {
                    /* 1貫の皿に最初当たる場合 */
                    pat1 = ((i-1) / (double)n) * (E[i-2][j-i-1][n+2-j] * (n / double(n-1)) + 1);
                }
                if (j-i-1 >= 1) {
                    /* 2貫の皿に最初当たる場合 */
                    pat2 = ((j-i-1) / (double)n) * (E[i][j-i-2][n+2-j] + 1);
                }
                if (n+2-j >= 1) {
                    /* 3貫の皿に最初当たる場合 */
                    pat3 = ((n+2-j) / (double)n) * (E[i-1][j-i][n+1-j] + 1);
                }
                E[i-1][j-i-1][n+2-j] = pat1 + pat2 + pat3;
            }
        }
    }
    
    printf("%.12Lf\n", E[count[0]][count[1]][count[2]]);
    return 0;
}




Measured memory_bytes: 450688
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
 ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    set<int> s;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    int a = n;
    while (1) {
        int c = a;
        bool ok = 1;
        while (c > 0) {
            int di = c % 10;
            if (s.count(di)) {
                ok = 0;
                break;
            }
            c /= 10;
        }
        if (ok) {
            cout << a << endl;
            break;
        }
        a++;
    }
	return 0;
}

Measured memory_bytes: 3144
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();
		sc.close();
		System.out.println((a+b)*h/2);
	}
}

Measured memory_bytes: 21716
#include <iostream>
using namespace std;
using ll = long long;

const int mod = 1e+9 + 7;

ll fact(int x){
    if(x == 0) return 1;
    return x * fact(x-1) % mod;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    ll ans = 0;
    if(abs(n - m) <= 1){
        ans = fact(n) * fact(m) % mod;
        if(n == m) ans = ans * 2 % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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


vector<ll> a, p;
ll f(ll n, ll x){
    if(n == 0){
        if(x <= 0) return 0;
        else return 1;
    }

    if(x <= a[n-1] + 1){
        return f(n-1, x-1);
    }else{
        return p[n-1] + 1 + f(n-1, x - a[n-1] -2);
    }
}

void solve() {
    ll N, X; cin >> N >> X;
    a.resize(N+1); p.resize(N+1);
    a[0] = 1; p[0] = 1;
    rep(i, N){
        a[i+1] = 2*a[i] + 3;
        p[i+1] = 2*p[i] + 1;
    }

    cout << f(N, X) << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#define rep(i,n) for (int i = 0;i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
int n;
cin >> n;
vector<ll> cnt(100005);
rep(i,n){
    int a;
    cin >> a;
    cnt[a]++;
}
ll total = 0;
rep(i,100005)total += i*cnt[i];
int q;
cin >> q;
    
rep(i,q){
    int b,c=0;
    cin >> b >> c;

    total += (c-b)*cnt[b];
    cnt[c] += cnt[b];
    cnt[b] = 0;
    cout << total << endl;
}
}

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

using namespace std;
using ll = long long;

int n, px, x;
ll a, b, ans = 0;

int main() {
  cin >> n >> a >> b >> px;
  for (int i = 1; i < n; ++i, px = x) {
    cin >> x;
    ans += min(a * (x - px), b);
  }
  cout << ans << "\n";
  return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(x) cout << x << endl;

int main() {
    int n; cin >> n;
    int m;
    map<string, int> list;
    rep(i, n){
        string s; cin >> s;
        if(list.count(s)){
            list[s] += 1;
        }else{
            list.insert(make_pair(s, 1));
        }
        m = max(m, list[s]);
    }
    for(auto l : list){
        if(l.second == m) OP(l.first);
    }
}


Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

const ll INF = 1e18;
vector<vector<ll>> nxt;
// a->bの最短経路復元
// for (ll cur = a; cur != b; cur = nxt[cur][b]) {
//
// }
void warshall_floyd(vector<vector<ll>>& d) {
  ll n = SZ(d);
  nxt = vector<vector<ll>>(n, vector<ll>(n));
  REP(i, n) REP(j, n) { nxt[i][j] = j; }

  REP(i, n) REP(j, n) REP(k, n) if (d[j][k] > d[j][i] + d[i][k]) {
    d[j][k] = d[j][i] + d[i][k];
    nxt[j][k] = nxt[j][i];
  }
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector<vector<ll>> to(n, vector<ll>(n, INF));

  REP(i, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    to[a][b] = c;
    to[b][a] = c;
  }
  warshall_floyd(to);
  set<P> st;

  REP(a, n) REP(b, n) {
    for (ll cur = a; cur != b; cur = nxt[cur][b]) {
      ll cv = cur, nv = nxt[cur][b];
      if (cv > nv) {
        swap(cv, nv);
      }
      st.insert({cv, nv});
    }
  }

  cout << m - SZ(st) << endl;
}

Measured memory_bytes: 384
/// @file a3.cpp
#include <cstdio>
#include <iostream>

/// @brief Counts flipped cards.
int main() {
    int N, M;
    long sum;

    scanf("%d %d", &N, &M);

    if (N > M) {
        std::swap(N, M);
    }

    if (M == 1) {
        sum = 1;  // For (N=1, M=1).
    } else if (M == 2) {
        if (N == 1) {
            sum = 0;
        } else {  // For (N=2, M=2).
            sum = 0;
        }
    } else {
        if (N == 1) {
            sum = M - 2;
        } else if (N == 2) {
            sum = 0;
        } else {
            sum = (long)(N - 2) * (M - 2);
        }
    }

    printf("%ld\n", sum);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

  int n=0, cnt=0;
  cin >> n;
  vector<int> d(n);

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

  sort(d.begin(), d.end());

  cnt = d[((n+1)/2)] - d[((n+1)/2)-1];
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 640
s = {}
for i in ['a','b','c']:
    s[i] = input()

turn = 'a'
while(True):
    if len(s[turn])==0:
        break
    else:
        next_turn = s[turn][0]
        s[turn] = s[turn][1:]
        turn=next_turn
print("{}".format(turn.upper()))

Measured memory_bytes: 3060
/* *****fireice**** */

#include<bits/stdc++.h>

#define ll long long int
#define ld long double
#define vi vector<int>
#define vc vector<char>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define el '\n'
#define N 1000000007
#define re return
#define F first
#define S second
#define L length
#define deb(x) cout<<#x<<" "<<x<<el;
#define mp make_pair
#define PI 3.14159265
#define all(a) (a).begin(),(a).end()
#define forup(i,n) for(int i=0;i<n;i++)
#define forf(i,x,n) for(int i=x;i<n;i++)
#define ford(i,n) for(int (i)=(n)-1;i>=0;(i)--)
#define take(a,n) forup(i,n) cin>>a[i];
using namespace std;

int gcdExtended(int a, int b, int *x, int *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

ll modInverse(int a, int m)
{
    int x, y;
    int g = gcdExtended(a, m, &x, &y);
        // m is added to handle negative x
    ll res = ((ll)x%m + (ll)m) % m;

    return res;
}

ll poww(ll x,ll n)
{
    if(n==0)
        return 1;
    else if(n==1) return x;
    else if(n%2 == 0)        //n is even
        return poww(x*x,n/2);
    else                              //n is odd
        return x*poww(x*x,(n-1)/2);
}

ll modularExponentiation(ll x,ll n,ll M)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

template<typename T>
T maxx(T a,T b)
{
  if(a<b) re b;
  re b;
}
template<typename T, typename... Args>
T maxx(T a,T b, Args... args)
{
    re(maxx(maxx(a,b),args...));
}

template<typename T>
T minn(T a,T b)
{
  if(a<b) re a;
  re b;
}
template<typename T, typename... Args>
T minn(T a,T b, Args... args)
{
    re(minn(minn(a,b),args...));
}

template<typename T>
void read(T& a)
{
  cin>>a;
}
template<typename T, typename... Args>
void read(T& a,Args&... args)
{
  cin>>a; read(args...);
}

template<typename T>
void write(T a)
{
  cout<<a<<' ';
}
template<typename T, typename... Args>
void write(T a,Args... args)
{
  cout<<a<<' '; write(args...);
}

inline ll min(ll a,ll b)
{
  if(a<b) re a;
  else re b;
}
inline ll max(ll a,ll b)
{
  if(a<b) re b;
  else re a;
}

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

    if (a == b)
        return a;

    if (a > b)
        return gcd(a-b, b);
    else return gcd(a, b-a);
}

ll ncr(int n,int r)
{
  ll ans=1;
  r=min(r,n-r);
  forup(i,r)
  {
    ans=(ans*(n-i)/(i+1))%N;
  }
  re ans;
}

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

  int t=1;
  //cin>>t;
  while(t--)
  {
    ll n,m,k;
    cin>>n>>k;
    if(n>=10) cout<<k;
    else cout<<k+100*(10-n);

  }


  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <variant>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m,x;
  cin>>n>>m>>x;
  vecint c(n);
  vector<vecint> a(n, vecint(m));
  REP(i,n) {
    cin>>c[i];
    REP(j,m) cin>>a[i][j];
  }
  int INF = 1e9;
  int res = INF;
  REP(i,1<<n) {
    vecint u(m, 0);
    int cost = 0;
    REP(j,n) {
      if ((i>>j)&1) {
        cost += c[j];
        REP(k,m) {
          u[k] += a[j][k];
        }
      }
    }
    bool ok = true;
    REP(j,m) {
      if (u[j] < x) ok = false;
    }
    if (ok) res = min(res, cost);
  }
  if (res < INF) {
    cout<<res<<endl;
  } else {
    cout<<-1<<endl;
  }
  return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
inline char gc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <class T> inline void read(T &n) {
  n = 0; RI ch = gc(), f;
  while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
  f = (ch == '-' ? ch = gc(), -1 : 1);
  while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
  n *= f;
}

int a[205], G[205][205];
queue <int> q;

int main() {
    
  int n; read(n);
  for (RI i = 1; i <= n; ++i)
    for (RI j = 1; j <= n; ++j) {
      char ch = gc();
      while (ch != '0' && ch != '1') ch = gc();
      if (ch == '1') G[i][j] = 1;
    }
  int ans = 0;
  for (RI i = 1; i <= n; ++i) {
    memset(a, 0, sizeof(a));
    a[i] = 1;
    q.push(i);
    while (!q.empty()) {
      int t = q.front(); q.pop();
      for (RI i = 1; i <= n; ++i)
        if (G[t][i]) {
          if (!a[i]) a[i] = a[t] + 1, q.push(i);
          else if (abs(a[i] - a[t]) != 1) return puts("-1"), 0;
        }
    }
    for (RI j = 1; j <= n; ++j)
      ans = max(ans, a[j]);
  }
  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <queue>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <set>
#define INF 1000000000000
using namespace std;
using ll = long long;
int main(){
    ll n;
    cin >> n;
    ll sum = 0;
    vector<ll> a(n+2);
    ll temp =0;
    a[0]=0;
    a[n+1]=0;
    for(ll i=1;i<n+2;i++){
        cin >> a[i];
        sum+=abs(temp-a[i]);
        temp = a[i];
    }
    for(ll i=1;i<n+1;i++){
        if((a[i-1]<=a[i]&&a[i+1]>=a[i])||(a[i-1]>=a[i]&&a[i+1]<=a[i])){
            cout << sum << endl;
        }else{
            cout << sum-min(abs(a[i]-a[i+1]),abs(a[i]-a[i-1]))*2 << endl;
        }
    }
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl "\n"
#define inf 1000000007
#define FOR(i, a, b) for(int i=a; i<b; i++)
int dp[1000001] = {0};

void solve(){
	int n;
	cin>>n;
	int arr[n];
	FOR(i, 0, n)cin>>arr[i];
	int cnt=0;
	FOR(i, 0, n){
		FOR(j, i+1, n){
			cnt+=(arr[i]*arr[j]);
		}
	}
	cout<<cnt;
}
signed main(){
	#ifdef _DEBUG
		freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	#endif
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
 
}

Measured memory_bytes: 256
#define ll long long
#define ffor(i,a,b) for (int i=(a);i<(b);i++)
#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#define SIZE 100001
#define MOD 1000000007
#define INF 100000000
using namespace std;
int n;
ll a,b;
vector<int> h(SIZE);
int h_max = 0;

bool enough(long int x){
	long long int T = 0;
	rep(i,n){
		long int sa = h[i] - x*b;
		if(sa > 0){
			T += sa/(a-b);
			if(sa%(a-b)!=0) T++;
		}
	}

	if(T > x) return false;
	else return true;
}

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

	cin >> n >> a >> b;

	rep(i,n){
		cin >> h[i];
		if(h[i] > h_max) h_max = h[i];
	}

	long int first = 1;
	long int end = h_max;
	long int mid = (first + end)/2;

	while(true){
		if(enough(mid)){
			end = mid;
		}
		else{
			first = mid + 1;
		}
		mid = (first + end)/2;
		if(first == end) break;
	}
	cout << mid << endl;
	return 0;
}


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

using namespace std;
typedef long long ll;

int N;
int M;
int main(){
  cin >> N >> M;
  pair<ll,ll> a[N];
  for(int i=0;i!=N;i++){
    cin >> a[i].first;
    cin >> a[i].second;
  }
  sort(a,a+N);
  int i=0;
  ll tmp=0;
  ll ans=0;
  while(1){
    if(a[i].second+tmp>M){
      ans+=a[i].first*(M-tmp);
      cout << ans << endl;
      return 0;
    }
    else{
      tmp+=a[i].second;
      ans+=a[i].second*a[i].first;
    }
    i++;
  }
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  vector<double> a;
  a.resize(n);
  int i;
  for(i=0;i<n;i++)
    cin>>a[i];
  sort(a.begin(),a.end());
  double ans = a[0];
  double two = 2.0;
  for(i=1;i<n;i++)
    ans = (ans + a[i])/two;
  cout<<setprecision(12)<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(), v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 1;
vector<int> g[N];
void solve(){
    vector<int> ans(N + 1);
    for(int i = 1; i <= N; i++){
        for(int j = 1; i * j <= N; j++){
            ans[i * j]++;
        }
    }
    int val;
    cin >> val;
    int total = 0;
    for(int i = 1; i <= val; i++){
        total += ans[val - i];
    }
    cout << total << '\n';
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        solve();
    }
}

Measured memory_bytes: 34596
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef long long ll;

ll lx[123456], lv[123456];
vector<ll> rx, rv, lmax = {0}, rmax = {0};

int main() {
  ll n, c;
  cin >> n >> c;
  rx.pb(0);
  rv.pb(0);
  REP(i, n) {
    ll s, t;
    cin >> s >> t;
    rx.pb(s);
    rv.pb(t);
  }
  rx.pb(c);
  rv.pb(0);
  for (int i = n + 1; i >= 0; i--) {
    lx[n - i + 1] = c - rx[i];
    lv[n - i + 1] = (i == n + 1 ? 0 : lv[n - i]) + rv[i];
  }
  REP(i, (signed)rv.size() - 1) rv[i + 1] += rv[i];
  for (int i = 1; i <= n + 1; i++) {
    rmax.pb(max(rmax.back(), rv[i] - rx[i]));
    lmax.pb(max(lmax.back(), lv[i] - lx[i]));
  }
  ll ret = 0;
  REP(i, n + 1) {
    ret = max(ret, rv[i] - rx[i] * 2 + lmax[n - i]);
    ret = max(ret, lv[i] - lx[i] * 2 + rmax[n - i]);
  }
  cout << ret << endl;
}


Measured memory_bytes: 5740
// 問題文
// Nを正の奇数とします。N 枚のコインがあります。 コインには1,2,…,N と番号が振られています。 
// 各i(1≤i≤N)について、コインiを投げると、確率piで表が出て、確率1−pi で裏が出ます。
// 太郎君はN枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。

// 制約
// Nは奇数である。
// 1≤N≤2999
// piは実数であり、小数第2 位まで与えられる。
// 0<pi<1
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1<<30;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};



int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    vector<double> p(n,0);
    rep(i,n) cin>>p.at(i);
    vector<vector<double>> dp(n+1,vector<double>(n+1,0.0));
    dp[0][0]=1.0;//dp[i][j]:=i番目まで、j回表(i-j回裏)

    REP(i,1,n+1)for(int j=0;j<=i;j++){
        if(j>=1) dp[i][j] += p[i-1]*dp[i-1][j-1];
        dp[i][j] += (1.0-p[i-1])*dp[i-1][j];
    }
    double ans =0.0;
    rep(i,n+1){
        if(i>n-i) ans += dp[n][i]; 
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 70784
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


Measured memory_bytes: 65440
use std::io::stdin;

macro_rules! read {
    ($t: ty) => {{
        let mut line = String::new();
        stdin().read_line(&mut line);
        line.trim().parse::<$t>().unwrap()
    }};
    ($($t: ty), *) => {{
        let mut line = String::new();
        stdin().read_line(&mut line);
        let mut iter = line.split_whitespace();
        (
            $(iter.next().unwrap().parse::<$t>().unwrap(), )*
        )
    }}
}
macro_rules! reads {
    ($t:ty) => {{
        let mut v = vec![];
        let mut line = String::new();
        stdin().read_line(&mut line);
        let mut iter = line.split_whitespace();
        while let Some(n) = iter.next() {
            v.push(n.parse::<$t>().unwrap());
        }
        v
    }};
    ($e:expr, $t:ty) => {{
        let mut v = vec![];
        for _ in 0..$e {
            let mut line = String::new();
            stdin().read_line(&mut line);
            v.push(line.trim().parse::<$t>().unwrap());
        }
        v
    }};
}

fn main() {
    let n = read!(u64);
    
    let h = reads!(u64);

    let mut s = 0;
    let mut m = 0;
    for h in h {
        if m <= h {
            m = h;
            s = s + 1;
        }
    }
    println!("{}", s);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
int main()
{
	ios;
	ll n,i,f=0;
	string s;
	cin>>n>>s;
	for(i=0;i<=(n-3);i++)
	{
		if(s.substr(i,3)=="ABC")
			f++;
	}
	cout<<f<<endl;
}

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

 #define     ll      long long 
 #define     forn(n)   for(int i=0;i<n;i++)



 int main()
 {
     ll  a,b;
     cin>>a>>b;
     cout<<a*b<<endl;

      return 0;
 }




Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll a[300005];

int main(){
  cin>>N;
  for(int i=0;i<3*N;i++)cin>>a[i];
  sort(a,a+3*N);
  ll ans=0;
  int r=3*N-1;
  for(int i=0;i<N;i++){
    ans+=a[r-1];
    r-=2;
  }
  cout<<ans<<endl;
  return 0;
}


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

signed main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int r, t;
		cin >> r >> t;
		set<int> st;
		st.insert(t / 30 * 5 + r / 100);
		st.insert((t + 29) / 30 * 5 + r / 100);
		st.insert(t / 30 * 5 + (r + 99) / 100);
		st.insert((t + 29) / 30 * 5 + (r + 99) / 100);
		vector<int> v(begin(st), end(st));
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << "\n "[i + 1 < v.size()];
	}
}

Measured memory_bytes: 3096
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */

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

void solve(istream &cin) {
    ll N, M;
    cin >> N >> M;
    if(!cin) return;
    string s, t;
    cin >> s >> t;
    ll lcm = N * M / gcd(N, M);
    if(N > M) {
        swap(s, t);
        swap(N, M);
    }
    ll i;
    i = 0;
    while(i < N){
        if((M * i) % N == 0){
            ll j = M * i / N;
            if( s[i] != t[j]){
                cout << "-1\n"; return;
            }
        }
        i++;
    }
    cout << lcm << endl;

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    cerr << "DEBUG MODE" << endl;
    string test_cases = "test.txt";
    auto fs = fstream(test_cases, fstream::in);
    while(fs) {
        solve(fs);
    }
#else
    solve(cin);
#endif
    return 0;
}


Measured memory_bytes: 640
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}
func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0
	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}
	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	k := getNextInt(scanner)
	var ans float64
	for i := 1; i <= n; i++ {
		c := 1.0
		ii := i
		for ii < k {
			ii <<= 1
			c *= 2
		}
		ans += 1 / c
	}
	fmt.Fprintln(writer, fmt.Sprintf("%.9f", ans/float64(n)))
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 20;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, s.size()) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  string s; cin >> s;
  int n = s.size();
  vvll dp(n+1);
  REP(i, n+1) {
    dp[i].resize(4, 0);
  }

  string t = "ABC";
  RREP(i, n) {
    RREP(j, 3) {
      if(i == n && j == 3) {
        dp[i][j] = 1;
      } else if(i == n && j < 3) {
        dp[i][j] = 0;        
      } else if(i < n && j == 3) {
        int m1 = 0;
        if(s[i] == '?') m1 = 3;
        else m1 = 1;
        dp[i][j] = (m1 * dp[i+1][j]) % MOD;
      } else {
        int m1 = 0;
        int m2 = 0;
        if(s[i] == '?') {
          m1 = 3;
          m2 = 1;
        } else if(s[i] == t[j]) {
          m1 = 1;
          m2 = 1;
        } else {
          m1 = 1;
          m2 = 0;
        }
        dp[i][j] = ((m1 * dp[i+1][j]) % MOD + (m2 * dp[i+1][j+1]) % MOD) % MOD;
      }
    }
  }

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


Measured memory_bytes: 7424
N, D = map(int, input().split())
count = 0
guard = 1
while guard <= N:
    guard += (D * 2) 
    if guard <= N:
        count += 1
        guard += 1
    else:
        if N - guard < D:
            count += 1
        print(count)
        exit()
print(count)
        

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

int main() {
	long long x, y;
	cin >> x >> y;
	//int ansa = floor(log2(y / x)) + 1;
	int ans = 0;
	while (y >= x) {
		x *= 2;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[110];
int main(){
	int n;
	scanf("%d",&n);
	ll ans = 1;
	for(int i = 0;i<n;i++){
		scanf("%lld",x+i);
		x[i] /= __gcd(x[i],ans);
		ans *= x[i];
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int k;
	int n;
	vector<int> a;
	cin >> k >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a.push_back(x);
	}
	int start = a[0],end=a[n-1];
	for (int i = 0; i < a.size()-1; i++)
		a[i] = a[i + 1] - a[i];
	a.pop_back();
	a.push_back(k - end+start);
	for (int i = 0; i < n; i++)
		a.push_back(a[i]);
/*	for (int i = 0; i < a.size(); i++)
		cout << a[i] << "\t";
*/
	int sum = 0;
	vector<int>count;
	for (int i = 0; i < n-1; i++)
		sum += a[i];
	count.push_back(sum);
	for (int i = n-1; i < a.size(); i++)
	{
		count.push_back(count[count.size() - 1] - a[i - (n-1)] + a[i]);
	}
	int max = count[0];
	for (int i = 0; i < count.size(); i++)
		if (max > count[i])
			max = count[i];
	cout << max;
	
	return 0;
}


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

const int maxn = 2e5+10;
vector<int> adj[maxn];
vector<bool> visited(maxn);
int cnt, res=0;
void dfs(int node) {
    ++cnt;
    visited[node] = true;
    for (int u: adj[node]) {
        if (!visited[u])
            dfs(u);
    }
}
int main() {
    int n, m, a, b;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        cnt=0;
        if (!visited[i]) dfs(i);
        res = max(res, cnt);
    }
    cout << res;
}

Measured memory_bytes: 20844
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[200010];
long long s[200010];
bool cmp(int a,int b)
{
	return a<b;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
//for(int i=1;i<=n;i++) cout<<s[i]<<endl;
	sort(s+1,s+n+1,cmp);
	long long ans=0;
	long  long cnt=1;
//	for(int i=1;i<=n;i++) cout<<s[i]<<' ';
	for(int i=2;i<=n;i++) 
	{
		if(s[i]==s[i-1]) cnt++;
		else ans+=(long long)cnt*(cnt-1)/2,cnt=1;
	}
	ans+=(long long)(cnt-1)*cnt/2;
	for(int i=1;i<=n;i++) if(s[i]==0) ans++;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define mp make_pair
#define F first
#define S second
#define db double
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
using namespace std;
using namespace __gnu_pbds;

// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
 
 ll mod=1e9 +7;
 
ll expo(ll base,ll exponent,ll mod){
    ll ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
 
vector<bool>  prime(90000002,true);
void Sieve() 
{ 
   
    for (int p=2; p*p<=90000001; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=90000001; i += p) 
                prime[i] = false; 
        } 
    } 
}

const ll M=200006;
ll f[M],inv[M];

void compute(){
    f[0]=1;
    rep(i,1,M-1){
        f[i]=(1LL*i*f[i-1])%mod;
    }
    inv[M-1]=expo(f[M-1],mod-2,mod);
    for(ll i=M-2;i>=0;i--){
        inv[i]=(1LL*(i+1)*inv[i+1])%mod;
    }
}
ll C(ll n,ll r){
    return (1LL*((1LL*f[n]*inv[r])%mod)*inv[n-r])%mod;
}

bool mysort(pair<ll,ll>&p1,pair<ll,ll>&p2)
{
  return p1.second<p2.second;
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // compute();
    // Sieve();
    ll tests=1;
    // cin>>tests;
    while(tests--)
    {
      string s;
      cin>>s;
      if(s=="SSS") cout<<0;
      else if(s=="SSR" || s=="SRS" || s=="RSS" || s=="RSR") cout<<1;
      else if(s=="RRS" || s=="SRR") cout<<2;
      else cout<<3;

    }

    return 0;
}

Measured memory_bytes: 14156
import java.util.Arrays;
import java.util.Scanner;

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

        if (total % 10 == 0) {
            Arrays.sort(s);
            for (int i = 0; i < n; i++) {
                if (s[i] % 10 != 0) {
                    total -= s[i];
                    System.out.println(total);
                    return;
                }
            }
            System.out.println(0);
            return;
        }
        System.out.println(total);

    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 5, mod = 1e9 + 7;

ll n, dp[N][N];
pair<ll, ll> p[N];

ll solve(int idx, int mn){
    if(idx == n) return 0;
    if(dp[idx][mn] != -1) return dp[idx][mn];
    int mx = n - (idx - (mn - 1));
    // cout << idx << ' ' << mn << ' ' << mx << '\n';
    ll op1 = solve(idx + 1, mn + 1) + abs(mn - p[idx].second) * p[idx].first;
    ll op2 = solve(idx + 1, mn) + abs(mx - p[idx].second) * p[idx].first;
    return dp[idx][mn] = max(op1, op2);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> p[i].first;
        p[i].second = i + 1;
    }
    sort(p, p + n);
    for(int i = 0; i < n / 2; i++){
        swap(p[i], p[n - 1 - i]);
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 1);


    return 0;

}




Measured memory_bytes: 35248
# DP practice
# https://atcoder.jp/contests/dp/tasks/dp_a

# 入力方法としてはこれが手軽
N = int(input())
h = list(map(int, input().split()))

dp = list()

# N = 0, 1 の時の処理も必要。だが省く
dp.append(0)
dp.append(dp[0] + abs(h[1] - h[0]))

for i in range(2, N):
	dp.append(min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i] - h[i-1])))


print(dp[N-1])

Measured memory_bytes: 20600
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
#define maxn 5000010

void read(int &x){
	int f=1;x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	x*=f;
} 
struct node{
	int to;
	int nxt;
}edge[maxn];
int tot,head[maxn],maxx,vis[maxn],ans,cnt;
void add(int x,int y){edge[cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt++;}
void dfs(int now,int fa,int stp){
	tot++;
	if(stp==0) return ;
	for(int i=head[now];~i;i=edge[i].nxt){
		if(edge[i].to==fa){
			continue;
		}
		dfs(edge[i].to,now,stp-1);
	}
}
int n,k;
int main(){
	read(n),read(k);
	int u,v,del;
	for(int i=0;i<=n;i++) head[i]=-1;
	for(int i=0;i<n-1;i++){
		read(u),read(v);
		add(u,v);add(v,u);
	}
	ans=0;
	if(k%2==0){//k为偶数，枚举点，跑k/2的边 
		for(int i=1;i<=n;i++){
			tot=0;
			dfs(i,0,k/2);
			ans=max(tot,ans);
		}
	}
	else{//k为奇数，枚举边，跑k/2的点 
		for(u=1;u<=n;u++){
			for(int j=head[u];~j;j=edge[j].nxt){
				tot=0;
				int t=edge[j].to;
				dfs(t,u,k/2);
				dfs(u,t,k/2);
				ans=max(tot,ans);
			}
		}
	}
	cout<<n-ans<<endl;
}



Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>

typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
  
using namespace std;
 
const ll inf = 1e18;
const ll N = 3e5;
const ll bits = 20;
const ld pi = 3.14159265358979323846;
const ll mod = 1e9+7;
const ll p = 29;

vector<array<int,2>> adj[N];
int col[N];

void dfs(int node,int par,int c){
    col[node] = c;
    for(auto temp: adj[node]){
        int nxt = temp[0];
        int w = temp[1];
        if(nxt==par) continue;
        if(w&1){
            dfs(nxt,node,!c);
        }else{
            dfs(nxt,node,c);
        }
    }
}

int main(){

    FASTIO;
    PRECISION; 

    int n,u,v,w;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    dfs(1,0,0);

    for(int i=1;i<=n;i++){
        cout<<col[i]<<"\n";
    }
    
}


Measured memory_bytes: 13056
N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(len(A)-1):
    for j in range(len(A)-1, i, -1):
        if A[j] < A[j-1]:
            tmp = A[j]
            A[j] = A[j-1]
            A[j-1] = tmp
            cnt += 1
print(" ".join(map(str, A)))
print(cnt)


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

typedef pair<int, int> P;

int main(void){
    int n,c,r[200008],v=0;
    vector<P> p[30];
    cin>>n>>c;
    fill(r, r+200008, 0);
    for(int i=0;i<n;i++){
        int s,t,u;
        cin>>s>>t>>u;
        u--;
        p[u].push_back(P(s, t));
    }
    for(int i=0;i<c;i++){
        sort(p[i].begin(), p[i].end());
        int b=0;
        for(int j=0;j<p[i].size();j++){
            int s=p[i][j].first,t=p[i][j].second;
            if(b<s)r[s*2-2]++;
            else r[s*2-1]++;
            r[t*2-1]--;
            b=t;
        }
    }
    for(int i=1;i<200008;i++){
        r[i]+=r[i-1];
        v=max(v,r[i-1]);
    }
    cout<<v<<endl;
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    ll K, num[50];
    cin >> K;
    for(int i = 0;i < 50;i++){
        num[i] = i + K/50;
    }
    K %= 50;
    for(int i = 0;i < K;i++){
        *min_element(num,num+50) += 51;
        for(int j = 0;j < 50;j++)num[j]--;
    }
    cout << 50 << endl;
    for(auto n:num)cout << n << " ";
    cout << endl;
}

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

int foo(int a){
  int sum = 0;
  while(a){
    sum += a%10;
    a /= 10;
  }
  return sum;
}

int main(){
  int mi, N;

  cin>>N;

  for(int i = 1; i < N; i++){
    if(i == 1) mi = foo(i) + foo(N-i);
    mi = min(mi, foo(i)+ foo(N-i));
  }

  cout<<mi<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define fr first
#define sc second
#define r_0 return 0
#define ld long double

using namespace std;

    const ll N = 1e2 + 7;
    const ll mod = 1e9 + 7;
    const ld eps = 1e-9;



void solve(){
    int n;
    cin >> n;
    int x = n / 1000;
    x ++;
    x *= 1000;

    cout << (x - n) % 1000;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt --){
            solve();
    }
}

/**

**/


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

using namespace std;

long long manhatan(pair<long long,long long> a,pair<long long,long long> b) {

    return abs(a.first-b.first) + abs(a.second-b.second);

}

long long solve(long long n,vector<pair<long long,long long> > &points,long long x) {

    long long idx=-1;

    long long cur=-1;

    for(long long i = 0 ; i < n ; i++) {

        long long currr = manhatan(points[x],points[i]);

        if(currr>cur) {

            cur=currr;

            idx=i;

        }

    }

    long long idx2=-1;

    cur=-1;

    for(long long i = 0 ; i < n ; i++) {

        if(i==idx)continue;

        long long currr = manhatan(points[idx],points[i]);

        if(currr>cur) {

            cur=currr;

            idx2=i;

        }

    }

    return manhatan(points[idx],points[idx2]);

}

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    long long n;

    cin >> n;

    vector<pair<long long,long long> > points;

    for(long long i = 0 ; i < n ; i++) {

        long long x;

        cin >> x;

        long long y;

        cin >> y;

        points.push_back({x,y});

    }

    long long res=0;

    for(long long i = 0 ; i < min(n,50LL) ; i++) {

        res=max(solve(n,points,i),res);

    }

    cout << res << '\n';

    return 0;

}



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

using namespace std;

long long dfs(string s, int b, int e, long long c) {
    long long r = s[b] - '0';
    for (int i = b + 1; i < e; i++) {
        r *= 10;
        r += s[i] - '0';
    }

    return (static_cast<int>(s.size()) == e ? c + r : dfs(s, b, e + 1, c) + dfs(s, e, e + 1, c + r));
}

int main() {
    string s;
    cin >> s;
    cout << dfs(s, 0, 1, 0) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <complex>
#include <cctype>
#include <cassert>
#include <sstream>
#include <ctime>
 
using namespace std;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
typedef vector<pii> vp;

#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
const ll MOD = 1000000007ll;

int main() {
	int k, t;
	
	cin >> k >> t;
	vector<int> a(t);
	REP(i, t) scanf("%d", &a[i]);
	
	REP(i, t - 1) {
		sort(ALL(a));
		a[a.size() - 1] -= a[0];
		a.erase(a.begin());
	}
	
	int ans = max(0, a[0] - 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;

namespace abc106
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');
            int a = int.Parse(array[0]);
            int b = int.Parse(array[1]);

            int s = (a - 1) * (b - 1);
            Console.WriteLine(s);
        }
    }
}


Measured memory_bytes: 11220