akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.op(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res


n, k = LI()
L = LI()
min_ST = SegmentTree(L, INF, min)
max_ST = SegmentTree(L, -INF, max)
cnt = 1
for i in range(n - k):
    if min_ST.query(i, i + k) == L[i] and max_ST.query(i + 1, i + k + 1) == L[i + k]:
        continue
    else:
        cnt += 1

ret = -INF
increasing_block_num = 0
max_len = 0
for j in range(n):
    if L[j] >= ret:
        max_len += 1

    else:
        if max_len >= k:
            increasing_block_num += 1
        max_len = 1
    ret = L[j]

if max_len >= k:
    increasing_block_num += 1

if increasing_block_num:
    print(cnt - (increasing_block_num - 1))
else:
    print(cnt)

Measured memory_bytes: 75552
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define INF 1e7

int main()
{
  vector<int> v;
  set<int> cost;
  int n;
  cin>>n;
  REP(i,n){
    int tmp;
    cin>>tmp;
    v.push_back(tmp);
  }

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

  FOR(i,-100, 101) {
    int tmpcost = 0;
    REP(j,v.size()) tmpcost += (v[j] - i) * (v[j] - i);
    cost.insert(tmpcost);
  }

  cout<<*cost.begin()<<endl;

  return 0;
}


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

using namespace std;

const long long ARR = 55;
long long n, a, ans;
long long x[55];
long long d[55][55][2505];

int main()
{
    scanf("%lld%lld", &n, &a);
    for(long long i = 1; i <= n; i++)
    {
        scanf("%lld", &x[i]);
    }
    d[0][0][0] = 1;
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = 0; j <= i; j++)
        {
            for(long long k = 0; k <= n * 50; k++)
            {
                if(k >= x[i] && j > 0)
                {
                    d[i][j][k] = d[i - 1][j - 1][k - x[i]] + d[i - 1][j][k];
                }
                else
                {
                    d[i][j][k] = d[i - 1][j][k];
                }
            }
        }
    }
    for(long long j = 1; j <= n; j++)
    {
        ans += d[n][j][j * a];
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 53504
N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
ssc = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        ssc.append(len(subs))
        subs = s
        continue
    subs += s
ss.append(subs)
ssc.append(len(subs))
suma = [0]
for sc in ssc:
    suma.append(suma[-1] + sc)

#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = suma[r] - suma[l]
    max_c = max(max_c, c)

print(max_c)


Measured memory_bytes: 8764
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;cin>>n;
    string s;
    int l,r;
    vpii p,m;
    rep(i,n){
        cin>>s;
        l=0;r=0;
        rep(j,s.size()){
            if(s[j]=='(')l++;
            else{
                if(l==0)r++;
                else l--;
            }
        }
        if(l>=r)p.push_back(mp(r,l));
        else m.push_back(mp(l,r));
    }
    sort(all(p));
    sort(all(m));reverse(all(m));
    int res=0;
    rep(i,p.size()){
        res-=p[i].first;
        if(res<0){
            cout<<"No"<<endl;
            return 0;
        }
        res+=p[i].second;
    }
    rep(i,m.size()){
        res-=m[i].second;
        if(res<0){
            cout<<"No"<<endl;
            return 0;
        }
        res+=m[i].first;
    }
    if(res!=0)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 11136
#include<iostream>
#include<cstdio>
using namespace std;
long long fac[8011],inv[8011],mod=1e9+7;
long long pow(long long x,int p)
{
	long long ans=1;
	while(p)
	{
		if(p&1)ans=(ans*x)%mod;
		x=(x*x)%mod;p>>=1;
	}
	return ans;
}
long long C(int a,int b){return (((fac[a]*inv[a-b])%mod)*inv[b])%mod;}
int n,a[201000],b[200100],f[4011][4011];
int main()
{
	fac[0]=1;
	for(int i=1;i<=8001;i++)fac[i]=(fac[i-1]*i)%mod;
	inv[8001]=pow(fac[8001],mod-2);
	for(int i=8000;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%mod;
	scanf("%d",&n);int ans=0;
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),f[2001-a[i]][2001-b[i]]++;
	for(int i=1;i<=4001;i++)
	for(int j=1;j<=4001;j++)f[i][j]=((f[i][j]+f[i-1][j])%mod+f[i][j-1])%mod;
	for(int i=1;i<=n;i++)ans=(ans+f[2001+a[i]][2001+b[i]])%mod;
	for(int i=1;i<=n;i++)ans=(ans-C(a[i]+b[i]+a[i]+b[i],a[i]+a[i])+mod)%mod;
	printf("%d",((long long)ans*inv[2])%mod);return 0;
}

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

int	main()
{
	int	N;
	cin >> N;
	int	digit = N % 10;
	if (digit == 2 || digit == 4 || digit == 5 || digit == 7 || digit == 9)
		cout << "hon" << endl;
	else if (digit == 0 || digit == 1 || digit == 6 || digit == 8)
		cout << "pon" << endl;
	else if (digit == 3)
		cout << "bon" << endl;
}


Measured memory_bytes: 3652
import java.util.Scanner;
import java.lang.Math;

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int k = stdIn.nextInt();
		if (k % 2 == 0) {
			for (int i = 0; i < k / 2; i++) {
				if (a % 2 == 1)
					a = a - 1;
				a = a / 2;
				b = b + a;
				if (b % 2 == 1)
					b = b - 1;
				b = b / 2;
				a = a + b;
			}
		}
		else {
			for (int i = 0; i < k / 2; i++) {
				if (a % 2 == 1) 
					a = a - 1;
				a = a / 2;
				b = b + a;
				if (b % 2 == 1)
					b = b - 1;
				b = b / 2;
				a = a + b;
			}
			if (a % 2 == 1) 
					a = a - 1;
				a = a / 2;
				b = b + a;
		}

		System.out.println(a);
		System.out.println(b);
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
char s[N];
void calc(int l,int r) {
    if(l==0||r==0) return;
    int t=min(l,r),x=t,y=t;
    if(l-t) {
        if((l-t)&1) {
            if((t+1)&1) y=t+(l-t)/2,x=y+1;
            else x=t+(l-t)/2,y=x+1;
        }
        else x=y=t+(l-t)/2;
    }
    else if(r-t) {
        if((r-t)&1) {
            if((t+1)&1) x=t+(r-t)/2,y=x+1;
            else y=t+(r-t)/2,x=y+1;
        }
        else x=y=t+(r-t)/2;
    }
    for(int i=1;i<=l;i++)
        printf("%d ",i==l?x:0);
    for(int i=1;i<=r;i++)
        printf("%d ",i==1?y:0);
}
int main() {
    scanf("%s",s);
    int l=1,r=0;
    for(int i=1;s[i];i++) {
        if(s[i]=='R'&&s[i-1]=='L') {
            calc(l,r),l=1,r=0;
            continue;
        }
        if(s[i]=='R') l++;
        else r++;
    }
    calc(l,r);
    printf("\n");
    return 0;
}

Measured memory_bytes: 512
#ifdef DBG_MACRO_NO_WARNING
#include <dbg.h>
#endif
#include <bits/stdc++.h>
#define all(c) c.begin(), c.end()
#define isz(c) (int)c.size()

using namespace std;
using ll  = long long;
using ii  = pair<int, int>;
using vi  = vector<int>;
using mii = map<int, int>;

const int NMAX = 1e7 + 11; // okay for range <= INT_MAX

bitset<NMAX> is_prime; // is_prime[i], true if number i is prime, else false
vector<int>  primes;   // primes[i], prime at pos i

mii prime_factors(ll n)
{
    mii factors;
    ll  i = 0, pf = primes[i];

    while (pf * pf <= n)
    {
        while (n % pf == 0)
        {
            ++factors[pf];
            n = n / pf;
        }
        pf = primes[++i];
    }

    if (n != 1) // If n is prime then it will stay the same, add n.
        ++factors[n];
    return factors;
}

void sieve(ll sieve_size) // fi primes until upperbound inclusive
{
    is_prime.set(); // set all bits to true
    is_prime[0] = is_prime[1] = 0;

    for (ll i = 2; i <= sieve_size; i++)
        if (is_prime[i])
        {
            for (ll j = i * i; j <= sieve_size; j += i)
                is_prime[j] = 0;
            primes.push_back((int)i);
        }
}

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

    sieve(NMAX);

    ll ans = 0;
    for (int x = 1; x < n; ++x)
    {
        ll   cur     = 1;
        auto factors = prime_factors(x);
        for (auto [k, v] : factors)
            cur *= v + 1;
        ans += cur;
    }

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


Measured memory_bytes: 8680
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int a = Integer.parseInt(s.substring(0, 2));
		int b = Integer.parseInt(s.substring(2));
		
		String ans = "NA";
		if ((a >= 1 && a<= 12) && (b >= 1 && b<= 12)) {
			ans = "AMBIGUOUS";
		} else if (a >= 1 && a<= 12) {
			ans = "MMYY";
		} else if (b >= 1 && b<= 12) {
			ans = "YYMM";
		} 
		System.out.println(ans);
	}
}

Measured memory_bytes: 22996
from itertools import accumulate

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

D = [ai - bi for ai, bi in zip(A, B)]
M = [di for di in D if di < 0]
P = [di for di in D if di > 0]

sum_m = sum(M)
if sum_m == 0:
    print(0)
    exit()

P = accumulate(sorted(P, reverse=True))
for i, pi in enumerate(P):
    if pi + sum_m >= 0:
        print(len(M) + i + 1)
        exit()
print(-1)


Measured memory_bytes: 19068
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int H = Integer.parseInt(sc.next());
			int W = Integer.parseInt(sc.next());

			if (H == 0 && W == 0) {
				break;
			}

			for (int i = 0; i < H; i++) {

				if (i == 0 || i == H - 1) {

					for (int j = 0; j < W; j++) {
						System.out.print("#");
					}
					System.out.print("\n");
				} else {
					System.out.print("#");
					for (int j = 0; j < W - 2; j++) {
						System.out.print(".");
					}

					System.out.print("#");
					System.out.print("\n");
				}
			}
			System.out.print("\n");
		}

	}
}

Measured memory_bytes: 36860
#include <bits/stdc++.h>
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
using namespace std;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

int main()
{
    int h,w;cin>>h>>w;
    int m[h][w];
    queue<pair<int,int>>q;
    REP(i,h)
    {
        string s;cin>>s;
        REP(j,w)
        {
            if(s[j]=='#'){m[i][j]=1;q.push(make_pair(j,i));}
            else m[i][j]=0;
        }
    }
    int ans=0;
    while(!q.empty())
    {
        int x=q.front().first;int y=q.front().second;
        q.pop();
        ans=max(ans,m[y][x]);
        REP(i,4)
        {
            if(y+dy[i]<0||y+dy[i]>=h||x+dx[i]<0||x+dx[i]>=w)continue;
            if(m[y+dy[i]][x+dx[i]]==0)
            {
                m[y+dy[i]][x+dx[i]]=m[y][x]+1;
                q.push(make_pair(x+dx[i],y+dy[i]));
            }
        }
    }
    cout<<ans-1<<endl;
}

Measured memory_bytes: 12304
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt(),W = sc.nextInt();

		for(int i = 0; i < H; i++) {
			String line = sc.next();
			System.out.println(line);
			System.out.println(line);
		}
	}
}

Measured memory_bytes: 26324
N, M = [int(i) for i in input().split()]
ABList = [[int(i) for i in input().split()] for _ in range(N)]
ABList.sort(key=lambda x: x[0], reverse=False)

ans = 0
for AB in ABList:
    drink = min(AB[1], M)
    M -= drink
    ans += drink * AB[0]
    if M == 0:
        break

print(ans)


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


int main(void) {
	int N;
	cin >> N;
	for (int i = 0;i < 26;i++) {
		for (int j = 0;j < 15;j++) {
			if (4 * i + 7 * j == N) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

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

int main() {
  int x,n;
  cin >> x >> n;
  
  set<int> s;
  for (int i=0; i<n; i++) {
    int a;
    cin >> a;
    s.insert(a);
  }
  
  int mindiff = 101;
  int result = -1;
  for (int i=0; i<=101; i++) {
    if (s.find(i) == s.end()) {
      int diff = abs(x - i);
      if (diff < mindiff) {
        mindiff = diff;
        result = i;
      }
    }
  }
  cout << result << endl;
  
  return 0;
}

Measured memory_bytes: 3640
"""
"""
from math import factorial
from collections import defaultdict


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


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


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


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


cache = {}


def fac(x):
    return factorial(x)


def choose_combination(n, r):
    if r > n:
        return 0
    # return int((fac(n) / fac((n - r))) * (1 / fac(r)))
    # return (fac(n) // fac((n - 2)) * (1 / 2))
    # return fac((n // n - 2)) * (1 / 2))
    return (n * (n-1)) // 2


def solve(n, array):
    counts = defaultdict(int)
    for x in array:
        counts[x] += 1
    total_ways = 0
    for x, count in counts.items():
        total_ways += choose_combination(counts[x], 2)
    for k in array:
        ways = choose_combination(counts[k] - 1, 2)
        print(total_ways + ways - choose_combination(counts[k], 2))


N = read_int()
array = read_array()
solve(N, array)


Measured memory_bytes: 26888
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int[] x = new int[10];
		for (int i = 1; i <= 5; ++i) {
			x[i] = sc.nextInt();
		}

		for (int i = 1; i <= 5; ++i) {
			if (x[i] == i) {
				continue;
			}

			System.out.println(i);
			return;
		}
	}

}


Measured memory_bytes: 35680
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
         String s = scan.next();
         int count=0;
         if(s.charAt(2)==s.charAt(3)){
             count++;
         }
         if(s.charAt(4)==s.charAt(5)){
            count++;
        }
        if(count==2){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
        }
    }

Measured memory_bytes: 21716
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define PRINT1(table, D0) REP(d0, D0) cout<<table[d0]<<" "; cout<<"\n";
#define PRINT2(table, D0, D1) REP(d0, D0) { REP(d1, D1) cout<<table[d0][d1]<<" "; cout<<"\n"; }
#define PRINT3(table, D0, D1, D2) REP(d0, D0) { REP(d1, D1) { REP(d2, D2) cout<<table[d0][d1][d2]<<" "; cout<<"\n"; } cout<<"\n"; }
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }

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

int main() {
	//ios::sync_with_stdio(false);
	ll N;
	string s;
	while(cin>>N>>s) {
		ll v = 0;
		string a, b;
//		DD(s);
		REP(i, N) {
			v += s[i]=='(' ? 1 : -1;
			if(v<0) {
				a+="(";
				v = 0;
			}
//			DD(v);
		}
		REP(i, v) b+=")";
		cout<<a+s+b<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
require 'prime'
N, M = gets.split.map(&:to_i)

n = M
[1].product(*M.prime_division.map{|p,e| e.times.inject([1]){|a,| a<<a[-1]*p } }){|a|
	d = a.inject(:*)
	n = d if N <= d && d < n
}
p M/n


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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Ostream,typename Container>
Ostream& operator<<(Ostream& os,const Container& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

int main()
{
	for(int n,m,l,s,t;cin>>n>>m>>l>>s>>t && n|m|l|s|t;){
		s--;
		vvi d(n,vi(n,INF));
		rep(i,n) d[i][i]=0;
		rep(i,m){
			int u,v,w; cin>>u>>v>>w; u--,v--;
			d[u][v]=d[v][u]=w;
		}
		vi rs(l),es(l);
		rep(i,l) cin>>rs[i]>>es[i],rs[i]--;
		
		rep(k,n) rep(i,n) rep(j,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		
		vvi dp(1<<l,vi(l,INF));
		rep(i,l) dp[1<<i][i]=d[s][rs[i]]+es[i];
		
		repi(i,1,1<<l) rep(j,l) if(i>>j&1) rep(k,l) if(!(i>>k&1))
			dp[i|1<<k][k]=min(dp[i|1<<k][k],dp[i][j]+d[rs[j]][rs[k]]+es[k]);
		
		int res=0;
		rep(i,1<<l) rep(j,l)
			if(dp[i][j]+d[rs[j]][s]<=t)
				res=max(res,__builtin_popcount(i));
		cout<<res<<endl;
	}
}

Measured memory_bytes: 8116
#include <cstdio>
#include <iostream>

int R,C;	// (1 ??? R ??? 10, 1 ??? C ??? 10 000)
const int MAX_ROW = 10;
const int MAX_COL = 10000;
bool is_flipped[MAX_ROW + 1][MAX_COL + 1];

void flip(int row)
{
	for(int c=0;c<C;c++)
		is_flipped[row][c] = !is_flipped[row][c];
}
int solve()
{
	int min_score = R*C;
	for(int i=0;i<1<<R;i++)
	{
		for(int r=0;r<R;r++)
			if((i>>r)&1) flip(r);
		int score = 0;
		for(int c=0;c<C;c++)
		{
			int column_sum = 0;
			for(int r=0;r<R;r++)
				if(is_flipped[r][c]) column_sum++;
			score += std::min(column_sum, R-column_sum);
		}
		min_score = std::min(min_score,score);
		for(int r=0;r<R;r++)
			if((i>>r)&1) flip(r);
	}
	return R*C-min_score;
}

int main()
{
	scanf("%d %d", &R, &C);
	int input;
	while(C!=0 || R!=0)
	{
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
			{
                scanf("%d", &input);
				is_flipped[r][c] = input==1;
			}
        printf("%d\n", solve());
        scanf("%d %d", &R, &C);
    }
	return 0;
}

Measured memory_bytes: 3256
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> D(N);
  for (int i = 0; i < N; i++)
  {
     cin >> D[i];
  }
  sort(D.begin(), D.end());

  int P = D[N/2-1];
  int Q = D[N/2];

  std::cout << Q - P << endl;
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

#define MAX 30

int main(void) {
	int w, n;	// cüÆ¡üÌ
	int a, b;	// ¡_Ìn_ÆI_
	int result[MAX];
	int i, t;
	char c;

	scanf("%d", &w);
	scanf("%d", &n);

	for(i = 0; i < w; i++) {
		result[i] = i+1;
	}

	for(i = 0; i < n; i++) {
		scanf("%d", &a);
		scanf("%1c", &c);
		scanf("%d", &b);

		t = result[a-1];
		result[a-1] = result[b-1];
		result[b-1] = t;
	}

	for(i = 0; i < w; i++) {
		printf("%d\n", result[i]);
	}

	return 0;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define X real()
#define Y imag()
#define value(x,y,w,h) (x >= 0 && x < w && y >= 0 && y < h)
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)

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

typedef long long ll ;
typedef deque<int> di ;
typedef deque<ll> dl ;
typedef map<string,int> dict;
typedef complex<double> comd;
typedef pair<int,int> pii;

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

double CalcDist(comd p1, comd p2){
  return sqrt(pow(p1.X - p2.X,2.0) + pow(p1.Y -p2.Y,2.0));
}

template <typename T>
void out(deque < T > d)
{
  for(size_t i = 0; i < d.size(); i++)
  {
    debug(d[i]);
  }
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  char c;
  int w,q,a,b,s = 0;
  map<int,pii> m;
  while(cin >> w >> q){
    if(w + q == 0)break;
    vector<int> vi(w+1,0);
    rep(_,q){
      cin >> c;
      if(c == 's'){
//         rep(i,vi.size()){
//           cout << vi[i];
//         }
//         cout << endl;
        cin >> a >> b;
        bool f = false;
        for(auto it = find(all(vi),0); it != vi.end(); ++it,it = find(it,vi.end(),0)){
          if(f) break;
          if(it + b < vi.end()){
            rep(i,b){
              if(*(it+i) != 0) break;
              if( i+1 == b ){
                fill(it,it+b,1);
                f =true;
                s = it - vi.begin();
                break;
              }
            }
          }
        }
        if(f){
          m[a] = make_pair(s,b);
          cout << s << endl;
        }
        else cout << "impossible"<<endl;
      }
      else{
        cin >> a;
        fill(vi.begin() + m[a].first,vi.begin() + m[a].first + m[a].second, 0) ;
//         rep(i,vi.size()){
//           cout << vi[i];
//         }
//         cout << endl;
      }
    }
    cout << "END"<< endl;
  }

  return 0;
}

Measured memory_bytes: 3180
while True:
    n,k=map(int,input().split())
    if (n,k)==(0,0):
        break
    a=[int(input()) for i in range(n)]
    b=sum(a[0:k])
    c=[b]
    for i in range(n-k):
        b+=a[i+k]-a[i]
        c.append(b)
    print(max(c))


Measured memory_bytes: 11740
import java.util.Scanner;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        double W = sc.nextDouble();
        double H = sc.nextDouble();
        double x = sc.nextDouble();
        double y = sc.nextDouble();

        double area = W*H/2;
        int isMulti = 0;
        if (x == W/2 && y == H/2) {
            isMulti = 1;
        }

        System.out.println(String.format("%.6f", area) + " " + isMulti);
    }

}

Measured memory_bytes: 23252
#include<stdio.h>

int check(int p,int n,int k,int T[])
{
	int i=0;
	for(int j=0;j<k; j++)
	{
		int s = 0;
		while(s +T[i] <= p)
		{
			s +=T[i];
			i++;
			if(i == n)
			{
				break;
			}
		}
	}
	return i;
}

int main()
{
	int n,k,i;
	scanf("%d %d",&n,&k);
	int T[n];
	
	for(i =0;i<n;i++)
	{
		scanf("%d",&T[i]);
	}
	
	int right = 100000 * 10000, left = 0, mid;
	
	while( right - left >1)
	{
		mid = (right+left)/2;
		int maxT = check(mid,n,k,T);
		if(maxT>=n)
		{
			right = mid;
		}
		else
		{
			left = mid;
		}
	}
	
	printf("%d\n", right);
	
	return 0;
}
		
	


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

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

    int W[N];
    int sum = 0;
    for(int i = 0; i < N; i++) {
        cin >> W[i];
        sum += W[i];
    }
    int ans = 99999;
    for(int i = 1; i < N; i++) {
        int x=0;
        for(int j = 0; j < i; j++) {
            x += W[j];
        }
        int y = sum - x;
        ans = min(ans, abs(x - y));
    }
    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    
    
	 long long n,i,j,k,sum=0,count=0,ans=0,x,y,l,r,m;
     cin>>n>>m;
     long long a[n+1];
     vector<long long>v[n+1];
     for(i=1;i<=n;i++)
     {
         cin>>a[i];
     }
     long long b[m],c[m];
     for(i=0;i<m;i++)
     {
         cin>>b[i]>>c[i];
         v[b[i]].push_back(c[i]);
         v[c[i]].push_back(b[i]);
     }
     for(i=1;i<=n;i++)
     {
         count=0;
         for(j=0;j<v[i].size();j++)
         {
             if(a[i]<=a[v[i][j]])
             count=1;
         }
         if(count==0)
         ans++;
     }
     cout<<ans;
    
    
}

Measured memory_bytes: 11824
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define M1 1000000007
#define M2 998244353

#define fl(i,a,b)  for(ll i=a;i<b;i++)
#define bfl(i,a,b) for(ll i=b-1;i>=a;i--)
#define f(i,n)     for(int i=0;i<n;i++)
#define bf(i,n)    for(int i=n-1;i>=0;i--)


#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define bn "\n"

//------------------------------------------------------------------------ 
// #define V(a) vector<a>
// #define vt() vector< tuple < int ,int ,int > > ;
// #define vector< int ,int > pv;
// vector< pair <int,int> > vect;


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

ll modI(ll a,ll m);
ll gcd(ll a,ll b);
ll powM(ll x,ll y,ll m);
ll swap(ll a,ll b);

void swap(ll& a,ll& b)
{
    ll tp=a;
    a=b;
    b=tp;
}

ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    ll ans=1,r=1;
    x%=m;
    while(r>0&&r<=y)
    {
        if(r&y)
        {
            ans*=x;
            ans%=m;
        }
        r<<=1;
        x*=x;
        x%=m;
    }
    return ans;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

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

// variable = Expression1 ? Expression2 : Expression3
// max = (n1 > n2) ? n1 : n2; 
// (n>m) ? cout<<"True"<<endl:cout<<"false"<<endl ;

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

// int n;cin>>n;int a[n];for(int i=0;i<n;i++)cin>>a[i];    
// for(int i=0;i<n;i++)cout<<a[i];
// int a,b;cin>>a>>b;   

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

// vector< tuple < int ,int ,int > > tv;
// vector< int ,int > pv;


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


int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	int tt=1;
   // cin>>tt;
	while(tt--)
	{
	    
	   long double a,b;
	   cin>>a>>b;
	   long double z=a*b;
	   ll d=(z*10)/10;
	   cout<<d<<bn;
	   
	   
	    
	}
	
	return 0;
}


Measured memory_bytes: 3748
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

X = input()

while True:
    i = 2
    flag = True
    while i * i <= X:
        if X % i == 0:
            flag = False
            break
        i += 1
    if flag:
        print X
        exit()
    else:
        X += 1

Measured memory_bytes: 4396
macro_rules! get_tuple {
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };

    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get_tuple!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (x, y, z) = get_tuple!(usize, usize, usize);

    println!("{} {} {}", z, x, y)
}


Measured memory_bytes: 2128
#include<iostream>
using namespace std;
int a[200010],b[200010];
long long n,sum1,sum2;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  cin>>b[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i]>b[i])
		  sum2+=a[i]-b[i];
		else sum1+=(b[i]-a[i])/2;
	}
	if(sum2<=sum1)
	  cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int H, A;
    cin >> H >> A;
    write((H + A - 1) / A);
}

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

using namespace std;

int main(int argc, char const *argv[])
{
    vector<long> vec(1);

    cin>>vec[0];

    for(int i=1;;++i){
        long tmp;
        if(vec[i-1]%2==0){
            tmp=vec[i-1]/2;
        }else{
            tmp=vec[i-1]*3+1;
        }
        vec.emplace_back(tmp);
        for(int k=0;k<i;++k){
            if(vec[k]==vec[vec.size()-1]){
                cout<<i+1<<endl;
    return 0;
            }
        }
    }



}



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

int main(){

    int n;
    cin >> n;
  
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int ans = 0;
    for (int i = 1; i < n - 1; i++) if((a[i-1] > a[i]) ^ (a[i] < a[i+1])) ans++;
  
    cout << ans << endl;
  
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s-1);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

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

    vector<int> w(n);
    int sum = 0;
    REP(i,n) {
        cin >> w[i];
        sum += w[i];
    }

    int mini = 1e9;
    int a = 0;
    REP(i,n) {
        a += w[i];
        mini = min(mini, abs(a - (sum - a)));
    }

    cout << mini << endl;
    return 0;
}


Measured memory_bytes: 256
import sys

N,Y = input().split()
N = int(N)
Y = int(Y)
A = [0]*3

for i in range(N+1):
    A[0] = i
    for j in range(N-i+1):
        A[1] = j
        A[2] = N - i - j
        if 10000*A[0] + 5000*A[1] + 1000*A[2] == Y:
            print(str(A[0]) + " " + str(A[1]) + " " + str(A[2]))
            sys.exit()
print("-1 -1 -1")


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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  uint64_t g = gcd(m,n);
  if(m%g==0) return (m/g)*n;
  if(n%g==0) return (n/g)*m;
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/* 
  //エラトステネスのふるい
  int maxNum = 100000;
  char isNotPrime[maxNum+1] = {};
  isNotPrime[0]=isNotPrime[1]=1;
  for(int i=2;i<maxNum;i++){
    if(isNotPrime[i]==1) continue;
    int num = i+i;
    while(num<=maxNum){
      isNotPrime[num]=1;
      num += i;
    }
  }
*/
// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

// 降順ソート vector<int> v;
// sort(v.begin(),v.end(),greater<int>());

// keyが降順ソートされるmap
// map<int, int, std::greater<int>> edges;

signed main() {
  int n;
  cin >> n;
  
  vector<int> rank;
  rank.push_back(399);
  rank.push_back(799);
  rank.push_back(1199);
  rank.push_back(1599);
  rank.push_back(1999);
  rank.push_back(2399);
  rank.push_back(2799);
  rank.push_back(3199);
  
  map<int,int> numR;
  int a;
  int numOverRed = 0;
  for(int i=0;i<n;i++){
    cin >> a;
    for(int j=0;j<rank.size();j++){
      if(a<=rank[j]){
        numR[j]++;
        break;
      }
      else if(j==rank.size()-1){
        numOverRed++;
      }
    }
  }
  int minNum = numR.size();
  if(minNum==0 && numOverRed>=1){
    minNum = 1;
  }

  int maxNum = rank.size();
  //if( (numOverRed+numR.size()) < maxNum){
    maxNum = numR.size()+numOverRed;
  //}
  
  cout << minNum << " " << maxNum << endl;
  
  return 0;
}



Measured memory_bytes: 3620
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    x1,y1,x2,y2 = _LI()

    p = [SI() for _ in range(H)]

    d = [[INF] * W for _ in range(H)]
    d[x1][y1] = 0

    q = []
    q.append((0,x1,y1))
    while q:
        m,x,y =  heapq.heappop(q)
        if d[x][y] < m: continue
        d[x][y] = m
        for dx,dy in DD:
            for n in range(1,K+1):
                nx = x + dx * n
                ny = y + dy * n
                if not(0<=nx<H and 0<=ny<W): break
                if p[nx][ny] == '@': break
                if d[nx][ny] < m + 1: break
                if d[nx][ny] == m + 1: continue
                d[nx][ny] = m + 1
                q.append((m+1,nx,ny))
    if d[x2][y2] < INF:
        print(d[x2][y2])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Measured memory_bytes: 170884
#include <bits/stdc++.h>
using namespace std;
 
vector<int> vec;
vector<int> dp(100001,-1);
 
int back(int i){
    if(i+1==vec.size()-1) return abs(vec[i+1]-vec[i]);
    if(i+2==vec.size()-1) return abs(vec[i+2]-vec[i]);
    if(dp[i]!=-1) return dp[i];
    
    int two=0,one=0;
    if(i+2<vec.size()){
        two= abs(vec[i+2]-vec[i]) + back(i+2);
    }
    if(i+1<vec.size())
        one= abs(vec[i+1]-vec[i]) + back(i+1);
    
    dp[i]=min(one,two);
    return dp[i];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        vec.push_back(a);
    }
    cout<<back(0);
	return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, Q, S, T;
ll data[200006];
ll sa[200005] = {};
ll sum = 0;
 
inline ll calc(ll x, ll y)
{
    if(x > 0) {
        if(y > 0) return ((x - y) * S);
        else return (x * S - y * T);
    } else {
        if(y > 0) return (x * T - y * S);
        else return ((x - y) * T);
    }
}
int main()
{
    scanf("%lld %lld %lld %lld", &N, &Q, &S, &T);
     
    for(int i = 0; i <= N; i++) {
        scanf("%lld", &data[i]);
    }
    for(int i = 0; i < N; i++) {
        sa[i] = data[i + 1] - data[i];
        if(sa[i] > 0) {
            sum -= S * sa[i];
        } else {
            sum -= T * sa[i];
        }
    }
    while(Q--) {
        ll l, r, x;
        scanf("%lld %lld %lld", &l, &r, &x); l--;
        sum += calc(sa[l], sa[l] + x);
        sa[l] += x;
        if(r < N) {
            sum += calc(sa[r], sa[r] - x);
            sa[r] -= x;
        }
        printf("%lld\n", sum);
    }
    return (0);
}

Measured memory_bytes: 6344
char s[];main(c){double*q=s,b;for(;~scanf("%s%c",s,&c);c&2&&printf("%f\n",*q))sscanf(s,"%lf",q+1)-1?b=*q--,*q=*s&1?*s-47?*q+=*s-45?b:-b:*q/b:*q*b:*++q;}

Measured memory_bytes: 0
#include<iostream>
#include<vector>

template< typename iterator >
void count_sort( iterator first, iterator last )
{
    std::vector<int> C(10000) ;
    std::vector<int> B(last-first) ;
    for( iterator iter = first ; iter != last ; ++iter )
    {
        C.at(*iter) ++ ;
    }
    for( std::size_t i = 1 ; i < C.size() ; ++i )
    {
        C.at(i) += C.at(i-1) ;
    }

    for( iterator iter = last - 1 ; iter >= first ; --iter )
    {
        B.at(C.at(*iter)-1) = *iter ;
        C.at(*iter)-- ;
    }
    for( iterator iter = first ; iter != last ; ++iter )
    {
        *iter = B.at(iter-first) ;
    }
}

int main()
{
    int n ;
    std::cin >> n ;
    std::vector<int> A(n) ;
    for( int i = 0 ; i < n ; ++i )
    {
        std::cin >> A.at(i) ;
    }
    count_sort( A.begin(), A.end() ) ;
    for( int i = 0 ; i < n ; ++i )
    {
        if( i != 0 )
        {
            std::cout << " " ;
        }
        std::cout << A.at(i) ;
    }
    std::cout << std::endl ;
}




Measured memory_bytes: 18408
#include<stdio.h>
main()
{
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    if

        (A==5 && B== 5 && C==7)
        {

        printf("YES");

    }
    else if

      (A==5 && B== 7 && C==5)
      {
      printf("YES");
    }
    else if

     (A==7 && B== 5 && C==5)
     {
     printf("YES");
    }
    else
        printf("NO");
}


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

  string S ; 
  cin >> S ;
  if(S == "SUN")  cout <<  7 <<endl;
  if(S == "MON")  cout <<  6 <<endl;
  if(S == "TUE")  cout <<  5 <<endl;
  if(S == "WED")  cout <<  4 <<endl;
  if(S == "THU")  cout <<  3 <<endl;
  if(S == "FRI")  cout <<  2 <<endl;
  if(S == "SAT")  cout <<  1 <<endl;
    //SUN,MON,TUE,WED,THU,FRI,SAT 
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from collections import deque


class Graph:
    def __init__(self, n, adj_matrix, default_value=float('inf')):
        self.n = n
        self.adj_matrix = adj_matrix
        self.default_value = default_value

    def show(self):
        for _ in self.adj_matrix:
            print(*_)

    def set_mst(self, start=0):  # minimum spanning tree
        self.mst = []
        T = [start]

        for _ in range(self.n - 1):
            edges = [(cost, u, v) for u in T
                     for v, cost in enumerate(self.adj_matrix[u])
                     if cost != self.default_value and v not in T]

            min_cost, *min_edge = min(edges)
            self.mst.append(tuple(min_edge))
            T.append(min_edge[1])

    def show_mst(self):
        self.set_mst()
        print(sum([self.adj_matrix[u][v] for u, v in self.mst]))

    def dfs(self):
        self.states = [2] * self.n
        self.d = [None] * self.n
        self.f = [None] * self.n
        self.time = 0

        for u in range(self.n):
            if self.states[u] == 2:
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.states[u] = 1
        self.time += 1
        self.d[u] = self.time

        for v, edge in [(v, edge) for v, edge in enumerate(self.adj_matrix[u])
                        if edge]:
            if self.states[v] == 2:
                self.dfs_visit(v)

        self.states[u] = 0
        self.time += 1
        self.f[u] = self.time

    def show_dfs(self, start=0):
        self.dfs()
        for i, (d, f) in enumerate(zip(self.d, self.f)):
            print(i + 1, d, f)

    def bfs(self, start):
        self.states = [0] * self.n
        self.dists = [float('inf')] * self.n

        queue = deque([start])
        self.dists[start] = 0
        while queue:
            u = queue.popleft()
            edges = self.adj_matrix[u]

            for v, edge in [(v, edge) for v, edge in enumerate(edges) if edge]:
                if self.states[v]:
                    continue

                if self.dists[v] > self.dists[u] + 1:
                    self.dists[v] = self.dists[u] + 1
                queue.append(v)

                self.states[v] = 1

        self.dists = [
            -1 if dist == float('inf') else dist for dist in self.dists
        ]

    def show_bfs(self, start=0):
        self.bfs(start=start)
        for i, dist in enumerate(self.dists):
            print(i + 1, dist)


if __name__ == '__main__':
    n = int(input())
    adj_matrix = [[
        int(cost) if int(cost) != -1 else float('inf')
        for cost in input().split()
    ] for i in range(n)]

    g = Graph(n, adj_matrix)
    g.show_mst()



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

int main(void)
{
    string s;
    cin >> s;
    bool flag = false;
    for (int i = 0; i < 2; i++)
    {
        if (s[i] != s[i + 1])
        {
            flag = true;
        }
    }
    if (flag)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second

signed main(){
	int n;
	cin>>n;
	cout<<n/2-(n%2==0)<<endl;
}

Measured memory_bytes: 256
# coding=utf-8
# Date: 2020-01-08
# Author: lee215

import heapq
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


N, D, A = gets()
XH = sorted(getss(N))

bombs = []
res = cur_b = 0
for x, h in XH:
    while bombs and bombs[0][0] < x - D:
        bx, bn = heapq.heappop(bombs)
        cur_b -= bn
    h -= cur_b * A
    if h <= 0: continue
    bn = (h + A - 1) / A if A > 1 else h
    cur_b += bn
    res += bn
    heapq.heappush(bombs, [x + D, bn])
print res


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

int main() {
	string  s, t;
	int ans = 0;
	cin >> s >> t;
	for(int i = 0;i < s.size(); i++){
		if(s[i] != t[i])ans++;
	}
	cout << ans << '\n';
}

Measured memory_bytes: 3844