akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int max = 99;
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int temp = sc.nextInt();
			ans += temp;
			if (temp > max) {
				max = temp;
			}
		}
		ans -= max/2;
		System.out.println(ans);
	}
}

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

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        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() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)1<<60
int dp[(1<<16)];
int sum[(1<<16)];

int calculate(vector<vector<int> >& score, int mask)
{
	int ans = 0;
	for(int i = 0; i < 17; i++)
	{
		for(int j = i + 1; j < 17; j++)
		{
			if(((mask & (1<<i))!=0) && ((mask & (1<<j))!=0))
				ans += score[i][j];	
		}
	}
	return ans;
}
void prepareSum(vector<vector<int> >&score, int n)
{
	for(int i = 1; i < (1 << n); i++)
		dp[i] = inf;
	//summing up the values for each and every subset
	for(int submask = 1; submask < (1<<n); submask++)
		sum[submask] = calculate(score, submask);
}

int solve(vector<vector<int> >&score, int mask)
{
	if(mask == 0)return 0;
	if(dp[mask]!=inf)
		return dp[mask];
	int ans = 0;
	for(int submask = mask; submask!=0; submask = (submask-1)&mask)//generating all the subsets of the mask
		ans = max(ans ,sum[submask]+solve(score,mask^submask));//xoring the submask and mask
	return dp[mask] = ans;
}
signed main()
{
	int n;
	cin >> n;
	vector<vector<int> >score(n, vector<int>(n));
	//memset(dp, inf, sizeof dp);
	for(int  i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> score[i][j];
	prepareSum(score, n);
	cout << solve(score, (1<<n)-1);
}

Measured memory_bytes: 4536
#include<bits/stdc++.h>
typedef long long ll;
const int MN=2004,MM=2004,MOD=1e9+7;
int N,M,S[MN],T[MM];
ll ans=1,dp[MN][MM];
inline ll exp(ll b,ll e) {
    ll ans=1;
    while(e)  {
        if(e&1) ans=(ans*b) %MOD;
        b=(b*b)%MOD;
        e>>=1;
    }
    return ans;
}
int main() {
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i)
        scanf("%d",&S[i]);
    for(int i=1;i<=M;++i)
        scanf("%d",&T[i]);
    for(int i=0;i<=N;++i)
        for(int j=0;j<=M;++j)
            dp[i][j]=1;
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=M;++j) {
            dp[i][j] = ((dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD+MOD)%MOD;
            if(S[i]==T[j]) {
                ans=(ans+dp[i][j])%MOD;
                dp[i][j] = (dp[i][j]+dp[i-1][j-1]) % MOD;
            }
        }
    }
    printf("%lld\n",dp[N][M]);
}

Measured memory_bytes: 31616
import sys

N = int(input())

v = list(map(int, input().split()))
v.sort(reverse=True)

sum = 0
while v:
    if len(v)==1:
        print(v[0])
        sys.exit()
    s = (v.pop(-1) + v.pop(-1)) / 2
    v.append(s)
    v.sort(reverse=True)





Measured memory_bytes: 2940
#考察OK、３５分。

n, k = map(int, input().split())
r,s,p = map(int, input().split())
t = tuple(input())

#並び替え
l = [[] for _ in range(k)]
for num, i in enumerate(t):
    q = num % k
    l[q].append(i)

points = []    
for num1, i in enumerate(l):
    points.append([])
    for num2, j in enumerate(i):
        if num2 == 0:
            if j == 'r':
                points[num1].append(p)
            elif j == 's':
                points[num1].append(r)
            else:
                points[num1].append(s)
        else:
            if j == i[num2-1]:
                if points[num1][num2-1] == 0:
                    if j == 'r':
                        points[num1].append(p)
                    elif j == 's':
                        points[num1].append(r)
                    else:
                        points[num1].append(s)
                else:
                    points[num1].append(0)
            else:
                if j == 'r':
                    points[num1].append(p)
                elif j == 's':
                    points[num1].append(r)
                else:
                    points[num1].append(s)
res = 0
for i in points:
    res += sum(i)

print(res)

Measured memory_bytes: 24528
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int64):: n,k,i,a,b
    integer(int64):: cnt(100000)

    cnt(:) = 0
    read*, n,k
    do i=1,n
        read*, a,b
        cnt(a) = cnt(a) + b
    end do

    do i=2,100000
        cnt(i) = cnt(i-1)+cnt(i)
    end do

    do i=1,100000
        if (cnt(i) >= k) then
            print'(i0)', i
            stop
        end if
    end do
end program name

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(int N, const vector<ll>& xs)
{
    return 0;
}

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

    string S;
    cin >> S;

    auto ans = string(S.size(), 'x');

    cout << ans << '\n';

    return 0;
}


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

int main(){
  int a, b; cin >> a >> b;
  int x = 0;
  while(true){
    if(floor(x * 0.08) == a && floor(x * 0.1) == b){
      cout << x << endl;
      break;
    }
    if(floor(x * 0.1) > 100){
      cout << -1 << endl;
      break;
    }
    ++x;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
int sum_ex(int);
int input(){
    int N;
    cin >> N;
    return N; 
}
vector<int> input(int N){
    vector<int> vec(N);
    for(auto& v : vec)
        cin >> v;
    return vec;
}

void Cont(){
    mp::cpp_int X;//101~10^18
    cin >> X;
    mp::cpp_int yokin = 100;
    int year = 0;
    while(X > yokin){
        yokin = yokin + yokin/100;
      //  cout << yokin << "\n";
        year++;
    }
    cout << year << "\n";
}

int main()
{
	std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Cont();
}

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

int main() {
  int x_1, y_1, x_2, y_2;
  scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
  
  int a= x_2-x_1, b=y_2-y_1;
  
  printf("%d %d %d %d\n", x_2-b, y_2+a, x_2-a-b, y_2+a-b);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    ll ary[3*n];
    rep(i,3*n) cin >> ary[i];

    sort(ary, ary+3*n, greater<ll>());

    ll ans = 0;
    rep(i,n)
    {
        ans += ary[i*2+1];
    }
    cout << ans << endl;

    
    
}




Measured memory_bytes: 2560
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)

l = deque([1])
visit = [0]*(n+1)
visit[1] = 1
while True:
    check = True
    for nex in e[l[-1]]:
        if visit[nex]:
            continue
        l.append(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        break
while True:
    check = True
    for nex in e[l[0]]:
        if visit[nex]:
            continue
        l.appendleft(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        print(len(l))
        print(*l)
        exit()

Measured memory_bytes: 28328
n, k = [int(i) for i in input().split()]
h_list = []
for i in range(n):
    h_list.append(int(input()))
h_list = sorted(h_list)
cur = max(h_list)
for i in range(n-k+1):
    cur = min(cur, h_list[i+k-1]-h_list[i])
print(cur)

Measured memory_bytes: 8280
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num1,num2,tmp;
    cin>>num1;
    vector <int> a1,a2;
    for(int i=0;i<num1;i++) {cin>>tmp;a1.push_back(tmp);}
    cin >>num2;int b[num2];
    for(int i=0;i<num2;i++)
    {
        cin>>tmp;
        if(find(a1.begin(),a1.end(),tmp)!=a1.end())
            a2.push_back(tmp);
    }
     cout<<a2.size()<<endl;

return 0;
}


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

int main() {
   unsigned int K;
   string S;
   cin >> K >> S;
   if(K >= S.size()){
   cout << S <<endl;
   }
   if(K < S.size()){
   cout << S.substr(0, K) + "..." <<endl;
   }
  
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define int long long

using namespace std ;

const int N = 1e5 + 5  ;

int a[N] ;
int d[N] ;

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

    int n ;
    cin >> n ;


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


    for(int i =0 ; i <=n ; ++i )
    {
        d[i] =INT_MAX ;
    }
    d[0] = 0 ;
    for(int i = 0 ; i < n-1 ; ++i )
    {
        d[i+1] = min(d[i] + abs(a[i+1] - a[i]) , d[i+1]);
        if (i +2 < n )
            d[i +2] = min(d[i+2] , d[i] + abs(a[i+2]- a[i])) ;

    }



    cout << d[n-1] << endl ;



}


Measured memory_bytes: 5196
#include<stdio.h>
#include<iostream>
using namespace std;

int X;
int main (){
    cin >> X;
    int k = 1;
    int o = 1;
    int n = 1;
    int j = 1;
    int O = 1;
    while( k * k <= X ){
        k++;
    }
    while( o * o * o <= X){
        o++;
    }
    while( n * n * n * n<= X){
        n++;
    }
    while( j * j * j * j * j <= X){
        j++;
    }
    while( O * O * O * O * O * O <= X){
        O++;
    }
    int hoge = max((k-1)*(k-1),(o-1)*(o-1)*(o-1));
    hoge = max(hoge,(n-1)*(n-1)*(n-1)*(n-1));
    hoge = max(hoge,(j-1)*(j-1)*(j-1)*(j-1)*(j-1));
    hoge = max(hoge,(O-1)*(O-1)*(O-1)*(O-1)*(O-1)*(O-1));
    cout << hoge << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    k = int(input())
    s = input().rstrip()

    if k >= len(s):
        print(s)
    else:
        print(s[:k] + "...")


if __name__ == "__main__":
    resolve()



Measured memory_bytes: 61648
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<typename T>
struct edge {
    int src, to;
    T cost;
};
template<typename T>
bool operator< (const edge<T> &e1, const edge<T> &e2) {
  return e1.cost < e2.cost;
}
template<typename T>
bool operator== (const edge<T> &e1, const edge<T> &e2) {
  return e1.src == e2.src && e1.to == e2.to && e1.cost == e2.cost;
}
struct UnionFind
{
    vector<int> par, sz;
    UnionFind(int n) : par(n), sz(n, 1) {
        for (int i = 0; i < n; ++i) par[i] = i;
    }
    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        sz[y] = 0;
    }
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return sz[root(x)];
    }
};
template<typename T>
T kruskal(vector<edge<T>> &es, int V, vector<edge<T>> &tr) {
    UnionFind uf(V);
    T ret = 0;
    for (auto &e : es) {
        if (!uf.issame(e.src, e.to)) {
            ret += e.cost;
            tr.push_back(e);
            uf.merge(e.src, e.to);
        }
    }
    return ret;
}
template<typename T>
using Graph = vector<vector<edge<T>>>;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n, m; cin >> n >> m;
  vector<edge<int>> edges, edges2;
  for(int i=0;i<m;++i) {
    int s, d, c; cin >> s >> d >> c;
    s--; d--;
    edges.push_back({s, d, c});
  }
  sort(edges.begin(), edges.end());
  vector<edge<int>> tr1;
  int w = kruskal(edges, n, tr1);
  int cnt = 0;
  int su = 0;
  for(auto &e: tr1) {
    auto it = find(edges.begin(), edges.end(), e);
    edges.erase(it);
    vector<edge<int>> tr2;
    int w2 = kruskal(edges, n, tr2);
    if(w != w2) {
      cnt++;
      su += e.cost;
    }
    edges.insert(it, e);
  }
  cout << cnt << " " << su << endl;;
}



Measured memory_bytes: 3892
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
from fractions import gcd
from functools import reduce
MOD = 10**9 + 7
import math
class Factorizer:
    def __init__(self):
        self.primes_ceil = 5
        self.primes = [2,3]

    def find_primes(self, primes_ceil):
        if primes_ceil <= self.primes_ceil:
            return self.primes

        prev_primes_ceil, self.primes_ceil = self.primes_ceil, primes_ceil
        r, m = prev_primes_ceil//6, prev_primes_ceil%6
        if m <= 1:
            i = r*6 + 1
            mod_flag = True
        else:
            i = r*6 + 5
            mod_flag = False

        while i < self.primes_ceil:
            sieve = True
            for p in self.primes:
                if p*p > i:
                    break
                elif i % p == 0:
                    sieve = False
                    break
            if sieve:
                self.primes.append(i)
            if mod_flag:
                i += 4
                mod_flag = False
            else:
                i += 2
                mod_flag = True

        return self.primes

    def __call__(self, n):
        if (self.primes_ceil-1)**2 < n:
            self.find_primes(int(math.sqrt(n))+1)
        factors = []
        powers = []
        for p in self.primes:
            if p * p > n:
                break
            elif n % p == 0:
                n //= p
                k = 1
                while n % p == 0:
                    n //= p
                    k += 1
                factors.append(p)
                powers.append(k)
        if n > 1:
            factors.append(n)
            powers.append(1)
        return factors, powers

def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

def inv_mod(a, p=MOD):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

def lcm(a, b):
    g = gcd(a,b)
    return a*b//g

def lcm_list(numbers):
    return reduce(lcm, numbers)

N = int(input())
A = inpl()
M = max(A)
fct = Factorizer()
P = fct.find_primes(M+1)
L = len(P)
pn = dict()
for i in range(L):
    pn[P[i]] = i
factors = [0] * L
for i in range(N):
    f, p = fct(A[i])
    for k in range(len(f)):
        m = pn[f[k]]
        factors[m] = max(factors[m], p[k])
K = 1
for l in range(L):
    K *= pow(P[l],factors[l],MOD)
    K %= MOD
ans = 0
for i in range(N):
    ans += K * inv_mod(A[i])
    ans %= MOD
print(ans)


Measured memory_bytes: 80984
n=int(input())
dp=[float("INF")]*(n+1)
dp[0]=0
temp=6
cnt=0
while temp<=n:
  cnt+=1
  dp[temp]=1
  temp*=6
l=[0,0]
l[0]=cnt
temp=9
cnt=0
while temp<=n:
  cnt+=1
  dp[temp]=1
  temp*=9
l[1]=cnt
for j,v in zip(l,[6,9]):
  for i in range(j+1):
    h=pow(v,i)
    for d in range(h,n+1):
      dp[d]=min(dp[d],dp[d-h]+1)
print(dp[-1])

Measured memory_bytes: 6900
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
using namespace std;
#define N 100005
char s[N],t[N];int n,m,q,sums[N],sumt[N];
int main(){
	scanf("%s%s",s+1,t+1);n=strlen(s+1),m=strlen(t+1);
	rep (i,1,n){
		sums[i]=sums[i-1];
		if (s[i]=='B') sums[i]+=2;else sums[i]++;
	}
	rep (i,1,m){
		sumt[i]=sumt[i-1];
		if (t[i]=='B') sumt[i]+=2;else sumt[i]++;
	}
	scanf("%d",&q);
	while (q--){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if ((sums[b]-sums[a-1])%3==(sumt[d]-sumt[c-1])%3) puts("YES");else puts("NO");
	}
	return 0;
}
/*

*/

Measured memory_bytes: 1536
S = str(input())

odd = True
even = True
for i in range(len(S)):
  if i%2 == 0: # odd
    if S[i] not in ["R", "U", "D"]:
      odd = False
      print("No")
      exit()
  else: # even
    if S[i] not in ["L", "U", "D"]:
      even = False
      print("No")
      exit()
      
print("Yes")

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

int main() {
    string S; cin >> S;
    int arr[26] = {0};
    string ans = "yes";
    for (int i = 0; i < S.size(); i++) {
        if (arr[S[i] - 'a'] == 0) {
            arr[S[i] - 'a'] = 1;
        } else {
            ans = "no";
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
abcd = input().strip()
n = len(abcd)-1

for i in range(2**n):
  t = ''
  for j in range(n):
    t += abcd[j]
    if (i >> j)&1:
      t += "+"
    else:
      t += "-"
  else:
    t += abcd[n]
  if eval(t)==7:
    print('{}=7'.format(t))
    exit(0)

Measured memory_bytes: 3064
#include <stdio.h> 

int main(void)
{	
	int n, i, date[100];

	scanf("%d",&n);

	for(i=0; i<n; i++)
	{
		scanf("%d",&date[i]);
	}

	for(i=n-1; i>0; i--)
	{
		printf("%d ",date[i]);
	}

	printf("%d\n",date[0]);

	return 0;
}

Measured memory_bytes: 596
A = int(input())
B = int(input())
C = int(input())
X = int(input())

cnt=0

for i in range(A+1):
    
    for j in range(B+1):
        
        for z in range(C+1):
            
            if i*500+j*100+50*z == X:
                cnt+=1
            
            
print(cnt)

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

int main(){
    while(1){
        int a, b, c, n, list[1001][4], parts[301], judge, defect;

        cin >> a >> b >> c >> n;
        if(a == 0 && b == 0 && c == 0){
            break;
        }

        for(int i = 1; i <= a + b + c; i++){
            parts[i] = 2;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 4; j++){
                cin >> list[i][j];
            }
            if(list[i][3] == 1){
                for(int k = 0; k < 3; k++){
                    parts[list[i][k]] = 1;
                }
            }
        }

        for(int i = 0; i < n; i++){
            if(!list[i][3]){
                judge = 0;
                for(int j = 0; j < 3; j++){
                    if(parts[list[i][j]] == 1){
                        judge++;
                    } else{
                        defect = j;
                    }
                }
                if(judge == 2){
                    parts[list[i][defect]] = 0;
                }
            }
        }

        for(int i = 1; i <= a + b + c; i++){
            cout << parts[i] << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1176
#include<iostream>
#include<climits>
#include<cstring>
using namespace std;

int tabFrog2(int arr[], int n, int k) {
	int dp[100005];
	memset(dp, -1, sizeof dp);

	dp[n - 1] = 0;

	for (int i = n - 2; i >= 0; i--) {
		dp[i] = INT_MAX;
		for (int jump = 1; jump <= k; jump++) {
			if (i + jump < n)
				dp[i] =  min(dp[i], abs(arr[i] - arr[i + jump]) + dp[i + jump]);
		}
	}
	return dp[0];
}

int main() {
	int n, k;
	cin >> n >> k;
	int arr[100005];

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	//cout << recFrog2(arr, n, 0, k, mem) << "\n";
	cout << tabFrog2(arr, n, k);

	return 0;
}


Measured memory_bytes: 4416
#include<iostream>
    using namespace std;
     
     
    int main()
    {
    	int A, B, C, D;
    	cin >> A >> B >> C >> D;
    	if (A >= B) {
    		cout << B*C + (A - B)*D << endl;
    	}else
    	{
    		cout << A*C<< endl;
    	}
    	return 0;
    }

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

const int A = 100005;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  vector<int> cnt(A, 0);
  int rm = 0;
  rep(i, n) if (cnt[a[i]]++ > 0) ++rm;
  int op = (rm + 1) / 2;
  int ans = n - 2 * op;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3996
#include<iostream>
#include<vector>
using namespace std;
//type
typedef long long ll;
//using pii = pair<int, int>;
//using vi = vector<int>;
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
//manip
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//output
#define out(a) cout << a << endl
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl
#define outp(v) rep(i, SZ(v)) cout << v[i].F << " " << v[i].S << endl
#define outc(s, t) cout << fixed << setprecision(10) << (double)(t - s) / CLOCKS_PER_SEC << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
#define brep(i, n) for (int i = n - 1; i >= 0; --i)
//algorithm (have library)
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0, while r < n

int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    string s; cin >> s;
    rep(i, SZ(s)) {
        if (s[i] == ',') cout << " ";
        else cout << s[i];
    }
    cout << endl;
    
}
//cast caution



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if(a + b >= 10) cout << "error" << endl;
    else cout << a + b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if((a==b && c!=a )|| (b==c && a != c) || (a==c && b!=c))cout<<"Yes\n";
    else cout<<"No\n";


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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; }
int main(){
    ll n,a,b; cin>>n>>a>>b;
    ll res=0;
    res+=a*(n/(a+b));
    res+=min(a,n%(a+b));
    cout<<res<<endl;
    return 0;
}

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int m,d,ret=0; cin>>m>>d;
	for (int i=1; i<=d; i++) {
		int x=i/10, y=i%10;
		if(x>=2&&y>=2&&x*y<=m)	
			ret++;
	}
	cout<<ret<<"\n";
	return 0;
}

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


#define li          long long int
#define uli         unsigned long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

string s;

int main() {
    cin>>s;
    li res=0;
    rep(i,sz(s)/2){
        if(s[i]!=s[sz(s)-1-i]){
            res++;
        }
    }
    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 3600
# coding: utf-8
# Here your code !
while True:
    
    a,op,b = input().split()
    a = int(a)
    b  = int(b)

    if op == "+":
        print(a + b)
    elif op == "-":
        print(a - b)
    elif op == "*":
        print(a * b)
    elif op == "/":
        print(a // b)
    else:
        break

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

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

int main() {
	int N;
	cin >> N;
	int mx = -1, sum = 0;
	for(int i = 0; i < N; i++) {
		int p;
		cin >> p;
		mx = max(mx, p);
		sum += p;
	}
	cout << (sum - mx / 2) << endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.stream.LongStream;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = in.nextLongArray(n);

            long sum = Arrays.stream(a).sum();
            long[] sumArray = ArrayUtils.calcCumulativeSum0First(a);

            long ans = Long.MAX_VALUE;
            for (int i = 1; i < n; i++) {
                ans = Math.min(ans, Math.abs(sum - 2 * sumArray[i]));
            }

            out.println(ans);
        }

    }

    static class InputReader {
        BufferedReader in;
        StringTokenizer tok;

        public String nextString() {
            while (!tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(in.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return tok.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

        public long nextLong() {
            return Long.parseLong(nextString());
        }

        public long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public InputReader(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
            tok = new StringTokenizer("");
        }

    }

    static class ArrayUtils {
        public static long[] calcCumulativeSum0First(long[] array) {
            int n = array.length;
            long[] ret = new long[n + 1];
            for (int i = 0; i < n; i++) {
                ret[i + 1] = array[i];
                ret[i + 1] += ret[i];
            }
            return ret;
        }

    }
}



Measured memory_bytes: 47828
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] ans = new int[N];
    for(int i = 0; i < M; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      ans[a]++;
      ans[b]++;
    }
    for(int i = 0; i < N; i++) {
      System.out.println(ans[i]);
    }
  }
}

Measured memory_bytes: 23124
import java.util.*;

public class Main {
    int n, m;
    ArrayList<ArrayList<Integer>> es;
    int[] cs;

    public static void main(String[] args) {
        Main m = new Main();
        m.read();
        m.solve();
    }

    private void read() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        es = new ArrayList<>(n);
        cs = new int[n];
        for (int i = 0; i < n; i++) {
            es.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            es.get(a).add(b);
            es.get(b).add(a);
        }
    }

    private void solve() {
        // judge
        long ans;
        if (check(0, 1)) {
            int b = 0;
            for (int c: cs)
                if (c == 1) b++;
            ans = (long) b * (n - b) - m;
        }
        else {
            ans = (long) n * (n - 1) / 2L;
            ans -= m;
        }
        System.out.println(ans);
    }

    private boolean check(int v, int c) {
        if (cs[v] != 0)
            return c == cs[v];
        cs[v] = c;
        boolean ans = true;
        for (int nxt: es.get(v)) {
            ans &= check(nxt, -c);
        }
        return ans;
    }

}


Measured memory_bytes: 104864
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
struct state{
	int x, y;
} a[100005];
bool cmp(state a, state b){
	return a.y == b.y ? a.x < b.x : a.y < b.y;
}
int32_t main(){
	int n, m;
	cin >> n >> m;
	int mn = 1e9;
	for(int i = 1; i <= m; ++i){
		cin >> a[i].x >> a[i].y;
		mn = min(mn, a[i].y);
	}
	sort(a +1, a + 1 + m, cmp);
	int ans = 1;
	for(int i = 1; i <= m; ++i)
		if(a[i].x >= mn) ans++, mn = a[i].y;
	cout << ans << endl;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String[] line = stdin.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        String s = stdin.readLine();
        
        char[] t = s.toCharArray();
        t[k - 1] = Character.toLowerCase(t[k - 1]);
        System.out.println(new String(t));
    }
}


Measured memory_bytes: 22484
import sys
import math
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    ans = 0
    min_r = N
    max_l = 0

    for i in range(M):
        L, R = map(int, input().split())
        min_r = min(min_r, R)
        max_l = max(max_l, L)

    print(max(min_r - max_l + 1, 0))


if __name__ == '__main__':
    main()


Measured memory_bytes: 40428
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll ar[M],cnt[M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,i,j,ans = 0;
	cin >> n;
	for(i=1;i<=n;++i)
		cin >> ar[i];

	sort(ar+1,ar+1+n);
	ans = ar[n];
	j = n-1;
	for(i=3;i<=n;++i)
	{
		ans += ar[j];
		cnt[j]++;
		if(cnt[j] == 2)
			j--;
	}
	cout << ans << "\n";
}

	

Measured memory_bytes: 5968
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.HashSet;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		Set<Integer> D = new HashSet<>();
		for (int i = 0; i < K; i++) {
			D.add(sc.nextInt());
		}

		int value = N;
		int tmp;
		while (true) {
			tmp = value;
			while (tmp > 0 && !D.contains(tmp % 10)) {
				tmp /= 10;
			}
			if (tmp == 0) {
				break;
			}

			value++;
		}

		System.out.println(value);
	}

	public static class Scanner {
		private BufferedInputStream inputStream;

		public Scanner(InputStream in) {
			inputStream = new BufferedInputStream(in);
		}

		public int nextInt() throws IOException {
			int num = 0;

			int read = skip();
			do {
				num = num * 10 + (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public int[] nextInt(int n) throws IOException {
			int[] array = new int[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextInt();
			}

			return array;
		}

		public long nextLong() throws IOException {
			long num = 0;

			int read = skip();
			do {
				num = num * 10 + (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public long[] nextLong(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextLong();
			}

			return array;
		}

		public String next() throws IOException {
			StringBuilder builder = new StringBuilder();

			int read = skip();
			do {
				builder.append((char) read);
			} while ((read = inputStream.read()) > 0x20);

			return builder.toString();
		}

		private int skip() throws IOException {
			int read;
			while ((read = inputStream.read()) <= 0x20)
				;

			return read;
		}
	}
}


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

int main(){
    int a, b, c, d;
    string abcd;
    cin >> abcd;
    a = abcd[0] - '0';
    b = abcd[1] - '0';
    c = abcd[2] - '0';
    d = abcd[3] - '0';
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                int ans = a;
                char c_i, c_j, c_k;
                if(i == 0){
                    ans += b;
                    c_i = '+';
                }else{
                    ans -= b;
                    c_i = '-';
                }

                if(j == 0){
                    ans += c;
                    c_j = '+';
                }else{
                    ans -= c;
                    c_j = '-';
                }

                if(k == 0){
                    ans += d;
                    c_k = '+';
                }else{
                    ans -= d;
                    c_k = '-';
                }

                if(ans == 7){
                    cout << to_string(a) + c_i + to_string(b) + c_j + to_string(c) + c_k + to_string(d) + "=7"<< endl; 
                    return 0;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<n;i++)

typedef long long lint;
int main (){
    string s;
    cin >> s;
    lint ans = 0;
    int n = s.size()-1;
    for(lint bit=0;bit < (1<<n);bit++){
        int c = 1;
        lint a = 0;
        rep(i,n+1){
            if(bit & (1<<i) || i==n){
                a += stoll(s.substr(i+1-c,c));
                c = 1;
            }else{
                c++;
            }
        }
        // cout << "i : " << bit << "a : " << a << endl; 
        ans += a;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kbd = new Scanner(System.in);
        int n = kbd.nextInt();
        String str = kbd.next();
        String[] strArr = str.split("");
        int k = kbd.nextInt();
        k = k - 1;
        printArr(strArr, k);
    }

    static void printArr(String[] arr, int n) {
        String s = arr[n];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(s)) {
                System.out.print(s);
            } else {
                System.out.print("*");
            }
        }
        System.out.println();
    }
}

Measured memory_bytes: 23892
use std::cmp::{max, min};

// wide-flip.rs --- Wide Flip
// author: Seong Yong-ju <sei40kr@gmail.com>

// tanakah's input macro
// cf https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
      s: chars
    }

    let n = s.len();
    let mut k = n;
    for i in 1..n {
        if s[i - 1] != s[i] {
            k = min(k, max(i, n - i));
        }
    }

    println!("{}", k);
}


Measured memory_bytes: 4352
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main{
	static final Scanner s=new Scanner(System.in);
	static IntStream REPS(int v){return IntStream.range(0,v);}
	static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
	static IntStream INS(int n){return REPS(n).map(i->getInt());}
	static int getInt(){return Integer.parseInt(s.next());}

	static String P="POSSIBLE",I="IM"+P;

	public static void main(String[]$){
		int n=getInt(),k=getInt(),a[]=INS(n).sorted().toArray();

		if(a[n-1]<k) {
			System.out.println(I);
			return;
		}

		if(Arrays.stream(a).allMatch(i->i%a[0]==0)) {
			System.out.println(k%a[0]==0?P:I);
		}else {
			int mod=a[0];
			for(int i:a) {
				if(i%mod!=0)
					mod=Math.min(mod,i%mod);
			}
			System.out.println((a[n-1]-k)%mod==0?P:I);
		}
	}
}


Measured memory_bytes: 48276
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
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 (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

const int INF = 1001001001;
int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    multiset<int> l, r; l.insert(-INF); r.insert(INF);
    ll base = 0, pl = 0;
    rep (_, q) {
    int comm; cin >> comm;
    if (comm == 1) {
        int a, b; cin >> a >> b;
        base += b;
        auto itl = l.end(), itr = r.begin(); itl--;
        int le = *itl, rb = *itr;
        if (a >= le && a <= rb) {
            l.insert(a); r.insert(a);
        } else if (a < le) {
            l.erase(itl, l.end()); r.insert(le);
            l.insert(a); l.insert(a);
            pl += le - a;
        } else {
            itr++; r.erase(r.begin(), itr); l.insert(rb);
            r.insert(a); r.insert(a);
            pl += a - rb;
        }
    } else {
        auto itl = l.end(); itl--;
        cout << *itl << " " << base + pl << "\n";
    }
    }
    eprintf("%d: ", (int)l.size()); for (int i : l) eprintf("%d ", i); eprintf("\n");
    eprintf("%d: ", (int)r.size()); for (int i : r) eprintf("%d ", i); eprintf("\n");
    return 0;
}

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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    ll dp[100];
    dp[0] = 2;
    dp[1] = 1;

    for (int i = 2; i <= 100; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    int n; cin >> n;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 0x7ffffff;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> cur(100005, 1);
	vector<bool> res(100005, false);
	res[0] = true;
	rep(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		cur[x]--;
		cur[y]++;
		if (res[x]) {
			if (cur[x] > 0) res[y] = true;
			else {
				res[x] = false;
				res[y] = true;
			}
		}
	}
	int ans = 0;
	rep(i, n) {
		if (res[i]) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640