akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>

typedef long long llong;

constexpr int kMaxN = 2e5 + 10;

struct Edge {
  int n1, n2;
  llong cost;
};

int costa[kMaxN];
std::vector<Edge> edges;

Edge NewEdge(int n1, int n2, llong costd) {
  Edge e;
  e.n1 = n1;
  e.n2 = n2;
  e.cost = costd * std::abs(n1 - n2) + costa[n1] + costa[n2];
  return e;
}

void MakeEdge(int low, int upp, llong costd) {
  if (upp - low <= 1) {
    return;
  }
  int mid = (low + upp) / 2;
  MakeEdge(low, mid, costd);
  MakeEdge(mid, upp, costd);

  int min1i = -1;
  llong min1 = 0;
  for (int i = low; i < mid; ++i) {
    llong v = costa[i] - i * (costd);
    if (min1i == -1 || v < min1) {
      min1 = v;
      min1i = i;
    }
  }

  int min2i = -1;
  llong min2 = 0;
  for (int i = mid; i < upp; ++i) {
    llong v = costa[i] + i * (costd);
    if (min2i == -1 || v < min2) {
      min2 = v;
      min2i = i;
    }
  }

  for (int i = low; i < mid; ++i) {
    edges.push_back(NewEdge(i, min2i, costd));
  }

  for (int i = mid; i < upp; ++i) {
    edges.push_back(NewEdge(min1i, i, costd));
  }
}

int union_set_id[kMaxN];

int UnionSetGetRoot(int i) {
  if (i != union_set_id[i]) {
    union_set_id[i] = UnionSetGetRoot(union_set_id[i]);
  }
  return union_set_id[i];
}

void UnionSetUnion(int a, int b) {
  a = UnionSetGetRoot(a);
  b = UnionSetGetRoot(b);
  if (a != b) {
    union_set_id[a] = b;
  }
}

bool CompareEdge(Edge const &e1, Edge const &e2) { return e1.cost < e2.cost; }

int main() {
  int n, d;
  scanf("%d %d", &n, &d);

  for (int i = 0; i < n; ++i) {
    scanf("%d", costa + i);
    union_set_id[i] = i;
  }

  MakeEdge(0, n, d);

  // printf("edge count %zd\n", edges.size());

  // for (auto const &edge : edges) {
  //   printf("edge(n1,n2,cost): %d %d %lld\n", edge.n1, edge.n2, edge.cost);
  // }

  std::sort(edges.begin(), edges.end(), CompareEdge);

  llong total = 0;
  int edge_count = 0;
  for (auto const &edge : edges) {
    if (UnionSetGetRoot(edge.n1) != UnionSetGetRoot(edge.n2)) {
      total += edge.cost;
      UnionSetUnion(edge.n1, edge.n2);
      edge_count += 1;
    }
    if (edge_count == n - 1) {
      break;
    }
  }

  printf("%lld\n", total);
  return 0;
}

Measured memory_bytes: 69472
import math
import queue
import bisect
import heapq
import time
import itertools

mod = 1e9

def main():
    n = int(input())
    x = n//1.08
    if int(x*1.08)==n:
        print(int(x))
    elif int((x+1)*1.08)==n:
        print(int(x+1))
    else:
        print(":(")
    return

if __name__=='__main__':
    main()

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define endl '\n'
using namespace std;

vector <int> v = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

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

    int k;
    cin >> k;
    cout << v[k - 1] << endl;


    return 0;
}


Measured memory_bytes: 892
let _ =
  let s = Scanf.scanf "%s\n" (fun s -> s) in
  let l = String.length s in
  let resa, resb = ref 0, ref 0 in
  let flaga, flagb = ref 0, ref 1 in
  let ia = int_of_char '0' in
  for i = 0 to l - 1 do
    let d = (String.get s i |> int_of_char) - ia in
    if d <> !flaga then resa := !resa + 1;
    if d <> !flagb then resb := !resb + 1;
    flaga := 1 - !flaga;
    flagb := 1 - !flagb;
  done;
  min !resa !resb |> print_int


Measured memory_bytes: 2560
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    private static FastScanner sc = new FastScanner();
    private static boolean DEBUG_FLG = false;

    public static void main(String[] args) {
    	long r = sc.nextLong();
    	long D = sc.nextLong();
    	long x = sc.nextLong();
    	for(int i=0; i<10; i++) {
    		x = r * x - D;
    		System.out.println(x);
    	}
    }

    static void debug(long... args) {
    	if(!DEBUG_FLG) return;
    	boolean flg = false;
    	for(long s : args) {
    		if(flg) System.out.print(" ");
    		flg = true;
    		System.out.print(s);
    	}
    	System.out.println();
    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}


Measured memory_bytes: 20692
#include <bits/stdc++.h>
#define pb push_back
#define tam 220000
#define offset 100000
#define se second
#define fi first
#define forr(i,p,n) for(ll i=p;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
typedef pair<ll,ll> ii;
using namespace std;
ll val[tam];

int main()
{
    ll N,X;
    cin>>N>>X;
    ll tot=0,ant=0,act;
    forr(i,0,N)
    {
        cin>>act;
        if (ant+act>X)
            tot+=max(0ll,ant+act-X),act-=min(act,ant+act-X);
        //cout<<ant<<" ";
        ant=act;
    }
    cout<<tot<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int judge(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans+=x%10;
        x/=10;
    }
    return ans;
}
int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if((judge(i)>=a&&judge(i)<=b)||(judge(i)>=b&&judge(i)<=a))ans+=i;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
using ll = long long;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
int main(){
  ll a,b;
  cin >> a >> b;
  ll c = abs(a + b);
  if(c % 2 != 0){
    cout << "IMPOSSIBLE";
  }else{
    cout << c/2;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

template <class T>
vector<T> sumup(const vector<T>& a) {
  int N = a.size();
  vector<T> res(N + 1);
  for (int i = 0; i < N; i++) res[i + 1] = res[i] + a[i];
  return res;
}

template <class T>
ll invs(vector<T>& A) {
  ll res = 0;
  int N = A.size();
  if (N > 1) {
    vector<T> L(A.begin(), A.begin() + N / 2);
    vector<T> R(A.begin() + N / 2, A.end());
    res += invs(L);
    res += invs(R);
    for (int i = 0, j = 0; i < L.size(); i++) {
      while (j < R.size() && R[j] < L[i]) ++j;
      res += j;
    }
    merge(L.begin(), L.end(), R.begin(), R.end(), A.begin());
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  ll K;
  while (cin >> N >> K) {
    vector<ll> A(N);
    for (ll& x : A) {
      cin >> x;
      x -= K;
    }
    auto S = sumup(A);
    ll res = 1ll * N * (N + 1) / 2 - invs(S);
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, a, b) for(__typeof(b) i = a; i < b; ++i)
#define Rep(i, a, b) for(__typeof(a) i = a; i > b; --i)

int dp[1005][1005]; char c[1005][1005];

signed main() {
	int n, m; cin >> n >> m;
	rep(i, 0, n) {
		rep(j, 0, m) {
			cin >> c[i][j];
		}
	}
	if(c[0][0] == '.') dp[1][1] = 1;
	rep(i, 1, n + 1) {
		rep(j, 1, m + 1) {
			if(c[i - 1][j - 1] == '.') {
				dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
				dp[i][j] %= 1000000007;
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

Measured memory_bytes: 8464
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include <assert.h>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//cout<<setprecision(20)
//cin.tie(0);
//ios::sync_with_stdio(false);
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int LBI(vector<int>&ar,llint in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
int UBI(vector<int>&ar,llint in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	int a,b;cin>>a>>b;
	if(a>b){a--;}
	cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    int water = 0, sugar = 0;
    double nax = 0.0;
    int answ = 0, anss = 0;
    rep(i, 31) {
        rep(j, 31) {
            for (int k = 0; k <= 3000; k += C) {
                water = i * 100 * A + j * 100 * B;
                int wg = water / 100;
                if (wg * E < k) continue;
                int rest = wg * E - k;
                chmin(rest, F - water - k);
                sugar = k + D * (rest / D);
                if (water + sugar > F) continue;
                double concent = (double)100 * sugar / (double)(water + sugar);
                if (nax < concent) {
                    answ = water;
                    anss = sugar;
                    nax = concent;
                }
            }
        }
    }

    if (answ == 0) {
        answ = 100 * min(A, B);
    }

    cout << answ + anss << " " << anss << endl;
    return 0;
}

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

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

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

// rambda
//第一要素が同一ならば第二要素の小さい方を返す
// return get<0>( x ) == get<0>( y ) ? get<1>( x ) < get<1>( y ) : get<0>( x ) > get<0>( y );
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

int main(void) {
    llint n, k;
    cin >> n >> k;

    vector<llint> a(n);
    vector<llint> p;
    vector<llint> m;
    llint cntminus = 0;
    for(llint in=0;in<n;in++) {
        cin >> a[in];
        if (a[in]>=0) {
            p.push_back(a[in]);
        }
        else {
            m.push_back(a[in]); 
            cntminus++;
        }
    }

    llint ans = 1LL;
    if(n==k) {
        for(llint ik=0;ik<k;ik++) {
            ans *= a[ik];
            ans %= MOD;
        }
        if(ans<0) ans += MOD;
        cout << ans << endl;
        return 0;
    }
    else if(cntminus==n&&k%2==1) {
        sort(a.begin(), a.end(), greater<llint>());
        for(llint ik=0;ik<k;ik++) {
            ans *= a[ik];
            ans %= MOD;
        }
        if(ans<0) ans += MOD;
        cout << ans << endl;
        return 0;
    }
    else {
        sort(p.begin(), p.end(), greater<llint>());
        sort(m.begin(), m.end());

        vector<llint> s;
        llint st = 0;
        if(k%2==1) {
            s.push_back(p[0]);
            k--;
            for(int i=0;i<static_cast<int>(p.size())-1;i++) {
                p[i] = p[i+1];
            }
            st = 1;
        }

        vector<tuple<llint, llint, llint>> pm2;
        for(llint i=0;i<static_cast<int>(p.size()-st)/2;i++) {
            pm2.push_back(make_tuple(p[2*i]*p[2*i+1], p[2*i], p[2*i+1]));
        }
        for(llint i=0;i<static_cast<int>(m.size())/2;i++) {
            pm2.push_back(make_tuple(m[2*i]*m[2*i+1], -m[2*i], -m[2*i+1]));
        }

        sort(begin(pm2), end(pm2), greater<tllint>());
        for(int i=0;i<k/2;i++) {
            int mul1 = get<1>(pm2[i]);
            int mul2 = get<2>(pm2[i]);
            s.push_back(mul1);
            s.push_back(mul2);
        }
        for(auto is:s) {
            ans *= is;
            ans %= MOD;
        }
        if(ans<0) ans += MOD;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 12240
N,M,X=map(int,input().split())

L=[]
for i in range(N):
    l=list(map(int,input().split()))
    L.append(l)
#print(L)

ans=10**9
for i in range(2**N):
    I=i
    cost=0
    LIST=[]
    for j in range(N):
        if I//(2**(N-1-j))==1:
            LIST.append(L[j])
        I%=(2**(N-1-j))
    #print(LIST)
    for j in range(len(LIST)):
        cost+=LIST[j][0]
    if cost<ans:
        Sum=[0 for i in range(M)]
        for j in range(len(LIST)):
            for k in range(M):
                Sum[k]+=LIST[j][k+1]
        #print(Sum,cost,min(Sum))
        if min(Sum)>=X:
            ans=cost
if ans==10**9:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 68916
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
struct edge { int u, v, i; };
ostream& operator<<(ostream& os, const edge& e) {
    os << "(" << e.u << ", " << e.v << ")";
    return os;
}
template <bool Directed> struct graph {
    int n;
    vector<vector<int>> adj;
    graph(int n) : n(n), adj(n + 1) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        if(not Directed) adj[v].push_back(u);
    }
};
template <bool Directed> vector<int> bfs(graph<Directed>& g, int s, const function<void(int)>& f = [](int) {}) {
    vector<int> d(g.n + 1, -1), p(g.n + 1);
    d[s] = 0, p[s] = -1;
    queue<int> q({s});
    while(not q.empty()) {
        int u = q.front(); q.pop();
        f(u);
        for(auto v : g.adj[u]) {
            if(d[v] == -1) {
                d[v] = d[u] + 1, p[v] = u;
                q.push(v);
            }
        }
    }
    return d;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph<1> g(3 * n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, n + v);
        g.add_edge(n + u, 2 * n + v);
        g.add_edge(2 * n + u, v);
    }
    int s, t;
    cin >> s >> t;
    auto d = bfs(g, s);
    cout << (d[t] == -1 ? -1 : d[t] / 3) << endl;
    return 0;
}


Measured memory_bytes: 19072
#include <bits/stdc++.h>
using namespace std;
static const int MAX = 0;
int ans = 0;

int main(){
	int N,T;
	cin >> N >>T;
	vector<int> c(N),t(N);
	for(int i=0;i<N;i++) cin>> c[i] >> t[i];
	int ans = 1001;
	for(int i=0;i<N;i++){
		if(t[i] <= T) ans = min(ans,c[i]);
	}
	if(ans == 1001) cout << "TLE" <<endl;
	else cout << ans <<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;

vector<int>a(3005);
bool f[3005][3005]={};
int dp[3005][3005];
int d(int l,int r){
    if(f[l][r]){return dp[l][r];}
    f[l][r]=1;
    if(l==r){return dp[l][r]=a[l];}
    return dp[l][r]=max(a[l]-d(l+1,r),a[r]-d(l,r-1));
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    rep(i,1,n+1){
        cin>>a[i];
    }
    int ans = d(1,n);
    cout<<ans<<endl;
}

Measured memory_bytes: 79744
from collections import deque

S = list(input())
s = deque(S)
q = int(input())
Q = [list(input().split()) for _ in range(q)]

rev = 0
for i in range(q):
    if len(Q[i]) == 1:
        rev += 1
        rev %= 2
    else:
        if rev == 0:
            if Q[i][1] == "1":
                s.appendleft(Q[i][2])
            else:
                s.append(Q[i][2])
        else:
            if Q[i][1] == "2":
                s.appendleft(Q[i][2])
            else:
                s.append(Q[i][2])

s = list(s)
if rev == 0:
    for i in range(len(s)):
        print(s[i],end="")
else:
    for i in reversed(range(len(s))):
        print(s[i],end="")
print()


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

const int INF = 1001001001;

int a[12][12];

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> c(n);
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }
  
  int ans = INF;
  rep(s,1<<n) {
    int cost = 0;
    vector<int> d(m);
    rep(i,n) {
      if (s>>i&1) {
        cost += c[i];
        rep(j,m) d[j] += a[i][j];
      }
    }
    bool ok = true;
    rep(j,m) if (d[j] < x) ok = false;
    if (ok) ans = min(ans, cost);
  }
  if (ans == INF) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))

//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g,c;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[100010];//適宜変える
	int id[100010];//適宜変える
}G;

G g;
void readgraph(){
	//適宜変える
	ll n;
	scanf("%lld",&n);
	ll m=0;
	rep(x,0,n){
		int k;
		scanf("%d",&k);
		while(k--){
			ll y;
			scanf("%lld",&y);
			g.e[m].s=x;
			g.e[m].g=y;
			g.e[m].c=0;
			m++;
		}
	}
	g.vcnt=n;
	g.ecnt=m;

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵
}

//Euler Tour
#define VCNT 100000
int ein[VCNT+10],eout[VCNT+10];
int vin[VCNT+10],vout[VCNT+10];
int ETe[2*VCNT+10],ETv[2*VCNT+10];
int ETcnt=0;
#undef VCNT
void ETdfs(int v){
	vin[v]=ETcnt;
	ETv[ETcnt]=v;
	rep(i,g.id[v],g.id[v+1]){
		ein[i]=ETcnt;
		ETe[ETcnt]=i;
		ETcnt++;
		ETdfs(g.e[i].g);
		eout[i]=ETcnt;
		ETe[ETcnt]=i+g.ecnt;
		ETcnt++;
		ETv[ETcnt]=v;
	}
	vout[v]=ETcnt;
}
void makeET(int root){
	ETdfs(root);
	ETv[ETcnt]=root;
}

//深さ
#define VCNT 100010
int dep[VCNT];
#undef VCNT
void depsdfs(int v){
	rep(i,g.id[v],g.id[v+1]){
		dep[g.e[i].g]=dep[v]+1;
		depsdfs(g.e[i].g);
	}
}

//sparse table
int cum[20][200010];
void makeST(int n){
	rep(i,0,19)rep(j,0,n)cum[i+1][j]=min(cum[i][j],cum[i][min(j+(1<<i),n-1)]);
}

//ST+ETでLCA
int lcasub(int l,int r){
//	if(l==r)return INF;
	if(r<l){int t=l;l=r;r=t;}
	int cnt=r-l;
	int k=31-__builtin_clz(cnt);
	return min(cum[k][l],cum[k][r-(1<<k)]);
}
int lca(int u,int v){
	if(u==v)return dep[u];
	return lcasub(vin[u],vin[v]);
}

//トポソ
int idx[100010];
int c(const void*a,const void*b){
	if(dep[*(int*)a]>dep[*(int*)b])return -1;
	return 1;
}

ll crr[100010];
ll upd[100010];
int st[1010];
int updcnt;
void distdfs(int v){
	rep(i,g.id[v],g.id[v+1]){
		crr[g.e[i].g]=crr[v]+g.e[i].c;
		distdfs(g.e[i].g);
	}
}
void update(){
	rep(i,0,g.vcnt-1){
		int v=idx[i];
		int e=ETe[vout[v]]-g.ecnt;//vと親を結ぶ辺のindex
		g.e[e].c+=upd[v];
		upd[ETv[vout[v]+1]]+=upd[v];
		upd[v]=0;
	}
	distdfs(0);
}

int main(){
	readgraph();
	makeET(0);
	dep[0]=1;depsdfs(0);
	rep(i,0,g.vcnt)dep[i]--;
	rep(i,0,g.vcnt)idx[i]=i;
	qsort(idx,g.vcnt,sizeof(int),c);
	rep(i,0,g.ecnt*2)cum[0][i]=dep[ETv[i]];
	makeST(g.ecnt*2);

	int sqN=sqrt(g.vcnt);
	int q;
	scanf("%d",&q);
	while(q--){
		int t;
		scanf("%d",&t);
		if(t==0){
			int v,w;
			scanf("%d%d",&v,&w);
			if(upd[v])upd[v]+=w;
			else{
				upd[v]=w;
				st[updcnt++]=v;
				if(updcnt==sqN){
					//ならす
					update();
					updcnt=0;
				}
			}
		}else{
			int v;
			scanf("%d",&v);
			ll ans=crr[v];
			rep(i,0,updcnt)ans+=upd[st[i]]*lca(v,st[i]);
			printf("%lld\n",ans);
		}
//		rep(i,0,g.vcnt)printf("%d ",crr[i]);puts("");
//		rep(i,0,g.vcnt)printf("%d ",upd[i]);puts("");
//		puts("");
	}
}


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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if (A * B * C == 175)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

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

A = []
for i in range(K):
    a = int(input())
    b = list(map(int, input().split()))
    for n in b:
        if n not in A:
            A.append(n)
count = 0

for i in A:
    count += 1

print(N - count)

Measured memory_bytes: 9200
#include <cstdio>

const int N = 1000000;
const int MOD = 1e9 + 7;

int inv(int a)
{
    return a == 1 ? 1 : 1LL * (MOD - MOD / a) * inv(MOD % a) % MOD;
}

int solve(int n)
{
    if (n == 2) {
        return 1;
    }
    static int fact[N];
    fact[0] = 1;
    for (int i = 1; i < n; ++ i) {
        fact[i] = 1LL * fact[i - 1] * i % MOD;
    }
    int result = 1LL * n * fact[n - 1] % MOD;
    for (int k = 2; k < n; ++ k) {
        if (k + k >= n) {
            int ways = 1LL * fact[k - 1] * inv(fact[k + k - n]) % MOD * fact[k] % MOD;
            result += MOD - ways;
            if (result >= MOD) {
                result -= MOD;
            }
        }
    }
    return result;

}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
}


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

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

   string ans_string;
   for(int i=0;i<s.size();i+=2){
       ans_string += s.at(i);
   }

   cout << ans_string <<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#define INF (1<<30)
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<long long> dp(n+1, INF);
	vector<int> c(m, 0);
	for (int i = 0; i < m;i++) {
		cin >> c[i];
	}
	dp[0] = 0;
	for (int i = 1; i <= n;i++) {
		for (auto val : c) {
			if (i - val < 0) continue;
			dp[i] = min(dp[i], dp[i - val] + 1);
		}
	}
	cout << dp[n] << endl;
}

Measured memory_bytes: 3316
#include<iostream>

using namespace std;

int main(){
  unsigned long long int x, ans=0;
  cin >> x;
  ans += (x/11)*2;
  if(1<=x%11 && x%11<=6)ans++;
  if(7<=x%11 && x%11<=10)ans+=2;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int  H, W;
	
	while(1)
	{
		cin >> H;
		cin >> W;
		
		if( (0 == H) && (0 == W) )
		{
			break;
		}
		
		for(int i = 0; i < H; i++)
		{
			for(int j = 0; j < W; j++)
			{
				if(0 == (i + j) % 2)
				{
					cout << "#";
				}
				else
				{
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

const int MAX_N = 100050;
int n;
ll a[3*MAX_N];

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> n;
	rep(i,1,3*n+1) {
		cin >> a[i];
	}
	vl red;
	ll r = 0;
	priority_queue<ll> q;
	rep(i,1,n+1) {
		r += a[i];
		q.push(-a[i]);
	}
	red.pb(r);
	rep(k,n+1,2*n+1) {
		ll x = -q.top();
		r -= x;
		q.pop();
		ll y = a[k];
		if(y > x) {
			r += y;
			q.push(-y);
		} else {
			r += x;
			q.push(-x);
		}
		red.pb(r);
 	}
 	priority_queue<ll> qq;
 	vl blue;
 	ll b = 0;
 	rep(i,2*n+1, 3*n+1) {
 		b += a[i];
 		qq.push(a[i]);
 	}
 	blue.pb(b);
 	per(k,n+1,2*n+1) {
 		ll x = qq.top();
 		b -= x;
 		qq.pop();
 		ll y = a[k];
 		if(y > x) {
 			b += x;
 			qq.push(x);
 		} else {
 			b += y;
 			qq.push(y);
 		}
 		blue.pb(b);
 	}
 	reverse(all(blue));
 	ll ret = -1e18;
 	rep(i,0,sz(red)) {
 		ret = max(red[i] - blue[i], ret);
 	}
 	cout << ret << '\n';
	return 0;
}


Measured memory_bytes: 6516
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f;
const double pi=3.1415926535897932384626;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const ll mod=1e9+7;
const int maxn=2e3+5;
ll s,f[maxn];
int main() {
	s=read();
	f[3]=1;
	for(int i=4;i<=s;i++) f[i]=(f[i-1]+f[i-3])%mod;
	printf("%lld\n",f[s]);
	return 0;
}


Measured memory_bytes: 3756
#include<stdio.h>
#include<math.h>
#include<stdlib.h>


void Koch(double x1,double y1,double x2,double y2,int dim);
main(){
  int n;
  double M=100.0,m=0.0;

  scanf("%d",&n);

  Koch(0,0,100,0,n);

  printf("%f %f\n",M,m);
  return 0;
}


void Koch(double x1,double y1,double x2,double y2,int dim)
{
  double x3,y3,x4,y4,x5,y5;
  double y;

  double s = sin(M_PI/3);
  double c = cos(M_PI/3);

  if(dim <= 0){
    if(y1 < 0){
      y = -y1;
      printf("%f %f\n",x1,y);
    }
    else printf("%f %f\n",x1,y1);
    return;
  }
  x3 = (2*x1 + x2) / 3;
  y3 = (2*y1 + y2) / 3;
  x5 = (x1 + 2*x2) / 3;
  y5 = (y1 + 2*y2) / 3;
  x4 = x3 + (x5-x3)*c + (y5-y3)*s;
  y4 = y3 - (x5-x3)*s + (y5-y3)*c;
  Koch(x1,y1,x3,y3,dim-1);
  Koch(x3,y3,x4,y4,dim-1);
  Koch(x4,y4,x5,y5,dim-1);
  Koch(x5,y5,x2,y2,dim-1);
}

Measured memory_bytes: 636
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
b = gets.chomp.split(" ").map(&:to_i)

diff = a.map.with_index{|x,i| x - b[i]}.sort#.inject(&:+)


minus = diff.select{|x| x < 0}
plus = diff.select{|x| x >= 0}

sum = minus.inject(&:+)
sum_p = plus.inject(&:+)
if sum.nil?
  puts "0"
  exit
end

if sum_p.nil?
  puts "-1"
  exit
end

if sum + sum_p < 0
  puts "-1"
  exit
end

i = 0
while sum < 0
  i += 1
  sum += diff[-i]
end

puts minus.size + i

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

double a[100000];
int main(){
	int n;scanf("%d",&n);
	vector<double>v;
	rep(i,n){
		scanf("%lf",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	rep(i,n){
		int low=lower_bound(v.begin(),v.end(),a[i])-v.begin();
		int up=upper_bound(v.begin(),v.end(),a[i])-v.begin();
		printf("%d\n",low*3+(up-low)-1); 
	}	
}

Measured memory_bytes: 4508
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <math.h>
using namespace std;
using s64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

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

    s64 mod = 1e9+7;
    s64 dp[109][4][4][4];
    int A = 0; int G = 1; int C = 2; int T = 3;

    rep(i0,N+1)
        rep(i1,4)
            rep(i2,4)
                rep(i3,4)
                    dp[i0][i1][i2][i3] = 0;

    rep(i,4)
        rep(j,4)
            rep(k,4)
            {
                if(i==A && j==G && k==C) continue;
                if(i==G && j==A && k==C) continue;
                if(i==A && j==C && k==G) continue;

                dp[3][i][j][k] = 1;
            }
    
    rep2(i0,3,N)
        rep(i1,4)
            rep(i2,4)
                rep(i3,4)
                    rep(i4,4)
                    {
                        if(i2==A && i3==G && i4==C) continue;
                        if(i2==A && i3==C && i4==G) continue;
                        if(i2==G && i3==A && i4==C) continue;
                        if(i1==A && i2==G && i4==C) continue;
                        if(i1==A && i3==G && i4==C) continue;

                        dp[i0+1][i2][i3][i4] += dp[i0][i1][i2][i3];
                        dp[i0+1][i2][i3][i4] %= mod;
                    }

    s64 ret = 0;
    rep(i,4)
        rep(j,4)
            rep(k,4)
            {
                ret += dp[N][i][j][k];
                ret %= mod;
            }

    cout << ret << endl;
    return 0;
}

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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 200007;

int n,val[_],los[_]={0},nlos=0;
int stk[_]={0},ps[_]={0},top;

inline void push(int x)
{
	if(top && stk[top]==x)ps[top]++;
	else top++,stk[top]=x,ps[top]=1;
}

inline int able(int m)
{
	top=0;
	for(int i=1;i<=nlos;i++)
	{
		int loc=los[i];
		while(top && stk[top]>loc)top--;
		push(loc);
		while(top && stk[top]>0 && ps[top]>=m)top--,push(stk[top+1]-1);
		if(top<=0 || !stk[top])return 0;
	}
	return 1;
}

int main()
{
	n=ty();
	for(int i=1;i<=n;i++)val[i]=ty();
	for(int i=2;i<=n;i++)if(val[i]<=val[i-1])los[++nlos]=val[i];

	int l=1,r=n;
	while(r>l){int mid=(l+r)>>1;if(able(mid))r=mid;else l=mid+1;}
	printf("%d\n",r);

	return 0;
}


Measured memory_bytes: 1792
N, M, Q = map(int, input().split())
lis = []
for i in range(Q):
    a = list(map(int, input().split()))
    lis.append(a)


big_lis = []


def dfs(string, n, m):
    if n == (N - 1):
        for i in range(m, M + 1):
            big_lis.append(string + [i])
    else:
        for i in range(m, M + 1):
            dfs(string + [i], n + 1, i)


dfs([], 0, 1)

MAX_A = 0
for small_lis in big_lis:
    D = 0
    for j in range(Q):
        if small_lis[int(lis[j][1]) - 1] - small_lis[int(lis[j][0]) - 1] == int(lis[j][2]):
            D += int(lis[j][3])
    MAX_A = max(MAX_A, D)
print(MAX_A)


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

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  if((A<=C && C<=B)||(B<=C && C<=A)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, L):
    l2p = defaultdict(set)
    p2l = defaultdict(set)
    for i, l in enumerate(L):
        p2l[i+1] = set(l)
        for j in l:
            l2p[j].add(i+1)
    
    
    q = [1]
    p_done = set(q)
    l_done = set()
    while q:
        p = q.pop()
        for l in p2l[p]:
            if l in l_done:
                continue
            l_done.add(l)
            for p2 in l2p[l]:
                if p2 in p_done:
                    continue
                p_done.add(p2)
                q.append(p2)
    return 'YES' if set(range(1, N+1)) == p_done else 'NO'



def main():
    N, M = read_int_n()
    L = [read_int_n()[1:] for _ in range(N)]
    print(slv(N, M, L))


if __name__ == '__main__':
    main()


Measured memory_bytes: 120408
#import<iostream>
long long r,d,i,b,c;main(){std::string s;std::cin>>s;for(;i<s.size();d=b^c?0:d){b=s[i]==66,c=s[i+1]>66;s[i++]<66?d++:r+=b&c?d:0;}std::cout<<r;}

Measured memory_bytes: 640
from bisect import bisect_left as bl 
from copy import deepcopy as dc
from time import time
from random import randint
start=time()
D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for _ in range(D)]

T=[randint(1,26) for _ in range(D)]

last=[[0] for _ in range(26)]
score=[0]*D
for i in range(D):
    contest=T[i]-1
    if i == 0:
        score[i]=S[i][contest]
    else:
        score[i]=score[i-1]+S[i][contest]
    last[contest].append(i+1)
    for j in range(26):
        blank=i+1-last[j][-1]
        score[i]-=blank*C[j]

def research(day,query,border):
    global last,T,score
    T2=T[:]
    last2=[[0] for _ in range(26)]
    for i in range(D):
        contest=T[i]-1
        last2[contest].append(i+1)
    score2=score[:]
    T2[day-1]=query+1
    for i in range(26):
        ind=bl(last2[i],day)
        last2[i]=last2[i][:ind]

    for i in range(day-1,D):
        contest=T2[i]-1
        if i == 0:
            score2[i]=S[i][contest]
        else:
            score2[i]=score2[i-1]+S[i][contest]
        last2[contest].append(i+1)
        for j in range(26):
            blank=i+1-last2[j][-1]
            score2[i]-=blank*C[j]
    if score2[-1]>=border:
        T=T2[:]
        last=dc(last2)
        score=score2[:]
    return

while time()-start<=1.5:
    research(randint(1,D),randint(0,25),score[-1])

for i in range(D):
    print(T[i])


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

typedef long long tint;
 
#define forsn(i, s, n) for(int i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend() 
#define NACHO ios::sync_with_stdio(0); cin.tie(NULL);
#define dbg cout << "hu" << endl;
 
const int INF = 11000000;
const int MOD = 1000000007;

int main(){
	int n, k; cin >> n >> k;
	vector<int> a (n);
	vector<long double> v (n);
	forn(i, n){
		cin >> a[i];
		v[i] = (double(a[i]*(a[i]+1))/2.000)/a[i];
	}
	int cont = 0;
	long double ret = 0.00000;
	long double maxi = -1.0000;
	forn(i, n){
		ret+=v[i];
		cont++;
		if(cont == k){
			maxi = max(maxi, ret);
			ret-=v[i-k+1];
			cont--;
		}
	}
	cout << fixed << setprecision(7) << maxi << endl;
}



Measured memory_bytes: 4096
#include<iostream>
using namespace std;
 
int main()
{
	int A,B,C,D;
  	cin>>A>>B>>C>>D;
  	while(A>0 && C>0)
    {
    	A=A-D;
      	C=C-B;
    }
  if(C<=0)
  {
  cout<<"Yes"<<endl;
  }
  else
    cout<<"No"<<endl;
  
return 0;
}

Measured memory_bytes: 3620
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static long Mod = 998244353;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            (long N, long K) = Slice<long,long>();
            var Di = Sarray();
            for (var i = N; i < 1000000; ++i)
            {
                var S = i.ToString();
                var flg = true;
                foreach(var s in S )
                {
                    if (Di.Contains(s - '0'))
                        flg = false;
                }
                if(flg)
                {
                    WriteLine(i);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 30328
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
char arr[10];
int main()
{
    scanf("%s",arr);
    if(arr[0]==arr[1]&&arr[1]==arr[2])
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
int n, d[101010], dp[101010];
const int INF = INT_MAX; 
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++)cin >> d[i];
    for(int i = 1;i <= n;i++)dp[i] = INF;
    dp[1] = 0;
    for(int i = 1;i <= n - 1;i++){
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(d[i] - d[i + 1]));
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(d[i] - d[i + 2]));
    }
    cout << dp[n] << endl;
}




Measured memory_bytes: 1024
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<stack>
#include<queue>
#include<sstream>
#include<string>
#include<bitset>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i);

using namespace std;

int main(){

	while(1){
		int e;
		cin >> e;
		if(e==0)break;

		int ans=1<<28;

		rep(z,101){
			rep(y,1001){
				int x = e - ((z*z*z)+(y*y));
				if(x<0) continue;
				ans=min(ans,x+y+z);
			}
		}
	
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));

int main() {
	int n;
	cin >> n;
	vector<list<pair<int, ll>>>t(n);
	rep(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		t[a].push_back(make_pair(b, c));
		t[b].push_back(make_pair(a, c));
	}
	int q, k;
	cin >> q >> k;
	k--;
	list<int> s;
	s.push_back(k);
	vector<ll>dist(n, -1);
	dist[k] = 0;
	while (!s.empty()) {
		int node = s.front();
		s.pop_front();

		for (auto it = t[node].begin(); it != t[node].end(); it++) {
			int i = it->first;
			int c = it->second;
			if (c != 0 && dist[i] == -1) {
				dist[i] = dist[node] + c;
				s.push_back(i);
			}
		}
	}
	//vector<ll>ans(n);
	rep(i, q) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << dist[x] + dist[y]<<endl;
		//ans[i] = dist[x] + dist[y];

	}
	//rep(i, q)cout << ans[i] << endl;




	return 0;
}





Measured memory_bytes: 16128
def printhash(x):
	l = ''
	for i in range(x):
		if i%2 == 0:
			l += '#'
		else:
			l += '.'
	return l
	
def printdot(x):
	l = ''
	for i in range(x):
		if i%2 == 1:
			l += '#'
		else:
			l += '.'
	return l
		
while True:
	try:
		line = input()
		if line != '0 0':
			dim = line.split(' ')
			dim = list(map(int, dim))
			
			for i in range(dim[0]):
				if i%2 == 0:
					print(printhash(dim[1]))
				else:
					print(printdot(dim[1]))
			print('')
			
		else:
			break
		
	except EOFError:
		break



Measured memory_bytes: 5616
#include <stdio.h>

int main() {

  int room[4][3][10] = {0};
  int b, f, r, v;
  int n;
  int i = 0, j, k;

  scanf("%d", &n);

  while(i < n) {
    scanf("%d %d %d %d", &b, &f, &r, &v);
    room[b-1][f-1][r-1] += v;
    i++;
  }

  for(i = 0; i < 4; i++) {
    for(j = 0; j < 3; j++) {
      for(k = 0; k < 10; k++)
	printf(" %d", room[i][j][k]);
      printf("\n");
    }
    if(i != 3)
      printf("####################\n");
  }

  return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000
/*
#define M 1000000007

//// extended gcd
ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;y=0;
	}
	return d;
}

//// mod inverse
ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

//// mod combination ex.( num of route (0,0)->(x,y)=mod_comb(x+y,x,M)
ll mod_comb(int n,int k,int p){
	if(n<0||k<0||n<k)return 0;
	return ((fact[n]*finv[k])%p)*finv[n-k]%p;
}
*/
//// mod power
ll mod_pow(ll x,ll n,ll mod){
	ll res=1;
	while(n>0){
		if(n&1)res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}

const int mod = 1000000007;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  mint operator^(const mint& a)const{ mint b(mod_pow(x,a.x,mod)); return b; }
  mint operator/(const mint& a)const{ return mint(*this)*(a^(mod-2)); }
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}

mint dp[1111][1111];
mint fact[11111];
mint finv[11111];
ll a,b,c,d;

int main(){
	cin.sync_with_stdio(false);
	fact[0].x=fact[1].x=1;
	finv[0].x=finv[1].x=1;
	repl(i,1,10000){
		fact[i+1]=fact[i]*mint(i+1);
		finv[i+1]=mint(1LL)/fact[i+1];
	}
	ll n;
	cin>>n>>a>>b>>c>>d;
	dp[0][a-1].x=1;
	rep(i,n+1)repl(j,a,b+1){
		dp[i][j]+=dp[i][j-1];
		for(int k=c;i+j*k<=n&&k<=d;k++){
			dp[i+j*k][j]+=dp[i][j-1]*fact[n-i]*finv[n-i-k*j]*finv[k]*(finv[j]^k);
		}
	}
	cout<<dp[n][b].x<<endl;
	return 0;
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
typedef long long int ll;
#define vaibhavv06               \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define int long long
#define MM(a,b) memset(a,b,sizeof(a))
const ll MOD = 1000000007;
using namespace std;

int32_t main(){
    vaibhavv06;
    
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	int a,b;
	cin>>a>>b;
	s.erase(a);
	s.erase(b);
	cout<<*s.begin()<<endl;
}


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

int main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int n; cin >> n;
        int ar[201] = {};
        for (int i = 0; i < n; i++) {
                cin >> ar[i];
        }
        int an = 0;
        for (int i = 0; i < n - 2; i++) {
                vector<int> v;
                for (int j = i; j < 3+i; j++){
                        v.push_back(ar[j]);
                }
                sort(v.begin(), v.end());
                if (v[1] == ar[i+1]) an++;
        }
        cout << an;
return 0;
}


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

using namespace std;

bool ok(const string& x, int N, int M, const vector<int>& s, const vector<int>& c)
{
	if (x.size() != N) {
		return false;
	}
	for (int i = 0; i < M; ++i) {
		if (x[s[i]] - '0' != c[i]) {
			return false;
		}
	}
	return true;
}

int main()
{
	int N, M;
	cin >> N >> M;
	vector<int> s(M), c(M);
	for (int i = 0; i < M; ++i) {
		cin >> s[i] >> c[i];
		--s[i];
	}

	int ans = -1;
	for (int x = 0; x < 1000; ++x) {
		if (ok(to_string(x), N, M, s, c)) {
			ans = x;
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
p_list = list(map(lambda x: (int(x) + 1) / 2, input().split()))

sum_k = 0
for i in range(k):
    sum_k += p_list[i]
sum_max = sum_k
for i in range(k, n):
    sum_k -= p_list[i-k]
    sum_k += p_list[i]
    if(sum_k > sum_max):
        sum_max = sum_k
print(sum_max)


Measured memory_bytes: 23588