akhauriyash/Code-Regression huggingface dataset:
class Heap
  attr_reader :nodes, :relational_operator

  def initialize(default = [], direction)
    @nodes = default
    @relational_operator = direction == :max ? :< : :>
  end

  def pop
    popped = nodes.shift
    return popped if nodes.empty?

    nodes.unshift(nodes.pop)

    tmp_index = 0
    while (tmp_index * 2 + 1) < nodes.size
      left_child_index = tmp_index * 2 + 1
      right_child_index = tmp_index * 2 + 2

      if right_child_index >= nodes.size
        if need_swap?(nodes[tmp_index], nodes[left_child_index])
          swap(tmp_index, left_child_index)
          tmp_index = left_child_index
        else
          break
        end
      else
        max_direction_child_index =
            if need_swap?(nodes[right_child_index], nodes[left_child_index])
              left_child_index
            else
              right_child_index
            end

        if need_swap?(nodes[tmp_index], nodes[max_direction_child_index])
          swap(tmp_index, max_direction_child_index)
          tmp_index = max_direction_child_index
        else
          break
        end
      end
    end

    popped
  end

  def push(node)
    tmp_index = nodes.size
    while tmp_index > 0
      parent_index = (tmp_index - 1) / 2

      if nodes[parent_index] && need_swap?(nodes[parent_index], node)
        swap(parent_index, tmp_index)
        tmp_index = parent_index
      else
        break
      end
    end

    @nodes[tmp_index] = node
  end

  private

  def need_swap?(node, other_node)
    node.send(relational_operator, other_node)
  end

  def swap(index, other_index)
    nodes[index], nodes[other_index] = nodes[other_index], nodes[index]
  end
end

class PriorityQueue
  attr_reader :heap

  def initialize(direction, default = nil)
    case direction
    when :max, :min
      @heap = Heap.new(default, direction)
    else
      ArgumentError
    end
  end

  def nodes
    heap.nodes
  end

  def dequeue
    heap.pop
  end

  def enqueue(e)
    heap.push(e)
  end
end


N, M = gets.split.map(&:to_i)
array = gets.split.map(&:to_i).sort!.reverse!
priority_queue = PriorityQueue.new(:max, array)

M.times do
  max = priority_queue.dequeue
  priority_queue.enqueue(max / 2)
end

puts priority_queue.nodes.inject(:+)

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

int main() {int i,j;
	char c;
	for(i=0;i<3;i++)
	  {
	  	  for(j=0;j<3;j++)
	  	    {
	  	    	cin>>c;
	  	    	if(i==j)
	  	    	  cout<<c;
	  	    }
	  }
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
const int MAXL = 128;
const int Q = 850;
int L;
const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
vector<int> cnts(62);
int query(string s){
	cout<<"? "<<s<<endl;
	int v; cin>>v; return v;
}
bool is_subseq(string s){
	return (int)s.size()+query(s)==L;
}
string combine(string a,string b){
	if(!a.size()||!b.size()) return a+b;
	string ret="";
	for(int i=0,j=0,s1=a.size(),s2=b.size();i<s1||j<s2;)
		if(i<s1&&(j==s2||is_subseq(a.substr(0,i+1)+b.substr(j)))) ret+=a[i++];
		else ret+=b[j++];
	return ret;
}
string solve(int l,int r){
	if(l==r) return string(cnts[l],chars[l]);
	int mid=(l+r)>>1;
	return combine(solve(l,mid),solve(mid+1,r));
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	for(int i=0;i<62;i++) cnts[i]=128-query(string(128,chars[i])),L+=cnts[i];
	string ans = solve(0, 61);
	cout << '!' << ' ' << ans << '\n';
}

Measured memory_bytes: 3776
#include <cstdio>
using namespace std;
int n;
int arr[100005];
int cnt[100005];
const long long MOD=998244353;
int main(){
    scanf("%d",&n);
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
        cnt[arr[x]]++;
    }

    if (arr[0]!=0){
        printf("0\n");
        return 0;
    }
    for (int x=1;x<n;x++) if (arr[x]==0){
        printf("0\n");
        return 0;
    }

    long long ans=1;
    for (int x=1;x<n;x++){
        ans=(ans*cnt[arr[x]-1])%MOD;
    }

    printf("%lld\n",ans);
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
	int n,a[21],b[21],c[20],sum=0;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=0;i<n;i++){
		cin>>b[i];
		sum+=b[i];
	}
	for(int i=0;i<n-1;i++)
	cin>>c[i];
	for(int i=0;i<n-1;i++)
	if(a[i]==a[i+1]-1)sum+=c[a[i]-1];
	cout<<sum;
    return 0;
}


Measured memory_bytes: 3624
/* Author : bhavye9499 - Bhavye Anand Gupta */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define endl "\n"
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<ll,ll>
#define showArr(A,a,n) {for(int i=a; i<a+n; i++) cout << A[i] << " "; cout << endl;}
#define showPair(A,a,n) {for(int i=a; i<a+n; i++) cout << A[i].fi << " " << A[i].se << endl;}

const ll MOD = 1e9 + 7;

string s, t;
ll dp[3010][3010], ns, nt;
vector<pii> parent;

ll fun(ll i, ll j);

int main() {
    ios::sync_with_stdio(false);
    memset(dp, -1, sizeof(dp));
    cin >> s >> t;
    ns = s.length();
    nt = t.length();

    fun(0, 0);
    string ans = "";
    ll i = 0, j = 0;
    while(i < ns && j < nt) {
    	if(dp[i][j] == dp[i + 1][j]) {
    		i++;
    	}
    	else if(dp[i][j] == dp[i][j + 1]) {
    		j++;
    	}
    	else {
    		ans += s[i];
    		i++;
    		j++;
    	}
    }

    cout << ans << endl;
}

ll fun(ll i, ll j) {
	if(dp[i][j] != -1)
		return dp[i][j];
	if(i >= ns || j >= nt)
		return dp[i][j] = 0;
	if(s[i] == t[j])
		return dp[i][j] = 1 + fun(i + 1, j + 1);
	else {
		return dp[i][j] = max(fun(i, j + 1), fun(i + 1, j));
	}

}

Measured memory_bytes: 71296
#include <algorithm>
#include <cstdio>
#include <cstring>
const int MAXS = 3005;
int dp[MAXS][MAXS];
char S[MAXS];
char T[MAXS];
char out[MAXS];
int K, M, N;

void restore(int i, int j) {
  if (!i || !j) return;

  if (S[i-1] == T[j-1]) {
    out[dp[i][j]-1] = S[i-1];
    return restore(i-1, j-1);
  }
  return (dp[i-1][j] == dp[i][j])
    ? restore(i-1, j)
    : restore(i, j-1);
}

char* solve() {
  for (int i = 0; i <= N; ++i) dp[i][0] = 0;
  for (int j = 0; j <= M; ++j) dp[0][j] = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      if (S[i-1] == T[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  // Format
  out[dp[N][M]] = '\0';
  restore(N, M);
  return out;
}

int main() {
  scanf(" %s%s", S, T);
  N = strlen(S);
  M = strlen(T);
  puts(solve());
  return 0;
}

Measured memory_bytes: 35456
fun main(args: Array<String>) {
    abc096c()
}

// 上下左右が`.`である`#`のマスが無ければ可
fun abc096c() {
    val (h, w) = readLine()!!.split(" ").map { it.toInt() }

    val sList = (1..h).map { readLine()!!.toCharArray().map { it == '#' }.toBooleanArray() }

    val answer = sList.mapIndexed { si, booleans ->
        booleans.mapIndexed { bi, b ->
            if (b) {
                val above = if (si - 1 >= 0) sList[si - 1][bi] else false
                val below = if (si + 1 <= h - 1) sList[si + 1][bi] else false
                val right = if (bi + 1 <= w - 1) booleans[bi + 1] else false
                val left = if (bi - 1 >= 0) booleans[bi - 1] else false
                above || below || right || left
            } else true
        }
    }.flatten().all { it }.let { if (it) "Yes" else "No" }

    println(answer)
}


Measured memory_bytes: 37944
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int maisu;
  for(int i=0; i<11;i++){
    if(N<=i*1000){
      maisu=i;
      break;
    }
  }

  cout<<maisu*1000-N<<endl;
}

Measured memory_bytes: 3592
n,m,x=map(int, input().split())
L=[]
sum=0
for i in range(n):
	S=list(map(int, input().split()))
	L.append(S)
	sum+=S[0]

import itertools
f=0
ans=sum
for i in itertools.product((1,0), repeat=n):
	X=[0]*(m+1)
	for j in range(n):
		if i[j]==1:
			for k in range(m+1):
				X[k]+=L[j][k]
	if min(X[1:])>=x:
		ans=min(ans,X[0])
		f+=1
if f==0:
	print(-1)
else:
	print(ans)

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

int main() {
  char c;
  cin >> c;
  
  string str = "aeiou"; 
  string msg = "consonant";
  for(int i = 0; i < str.size(); i++) {
    if(str.at(i) == c) {
	  msg = "vowel";
      break;
  	}
  }
  cout << msg << endl;
}


Measured memory_bytes: 3592
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
// #include "prettyprint.hpp"

int main() {
  int a, b;
  cin >> a >> b;

  string A = "", B = "";
  for (int i = 0; i < b; i++) {
    A += to_string(a);
  }

  for (int i = 0; i < a; i++) {
    B += to_string(b);
  }

  if (a < b) {
    cout << A << endl;
  } else {
    cout << B << endl;
  }

  return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ll<<62)-1)
#define cINFINT ((1<<30)-1)


template <typename T>
void calcFactional_mod( size_t size, 
	vector<T>& fac, vector<T>& inv, vector<T>& facInv, T mod )
{
	for( T i = 2; i < size; ++i )
	{
		fac[i] = fac[i - 1] * i % mod; // n! % mod
		inv[i] = mod - inv[mod % i] * ( mod / i ) % mod; // 逆元計算 (n)^-1 % mod
		facInv[i] = facInv[i - 1] * inv[i] % mod; // (n!)^-1 % mod
	}
}
template <typename T>
T pow_mod(T x, T n, T mod)
{
	T res = 1;
	while (n > 0)
	{
		if (n & 1)
			res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}

int main()
{
	cin.tie( 0 ); ios::sync_with_stdio( false );
	const ll maxN = 3000;
	vector<ll> fac( maxN, 1 ), inv( maxN, 1 ), facInv( maxN, 1 );
	calcFactional_mod<ll>( maxN, fac, inv, facInv, cMOD);
	auto mod = cMOD;
	auto add = [mod]      ( ll a, ll b ) { return ( a + b ) % mod; };
	auto sub = [mod]      ( ll a, ll b ) { return ( a + mod -b ) % mod; };
	auto mul = [mod]      ( ll a, ll b ) { return a * b % mod; };
	auto div = [&inv, mod]( ll a, ll b ) { return a * inv[b] % mod; };
	auto pow = [mod]      ( ll a, ll b ) { return pow_mod<ll>( a, b, mod ); };
	
	auto combination = [&fac, &inv, &facInv, mod]( ll n, ll k ) -> ll
	{
		if( n < k  || n < 0 || k < 0) return 0;
		return fac[n] * ( facInv[k] * facInv[n - k] % mod ) % mod; // O(1)
	};

	ll n,k; cin >> n>>k;
	REP(i,k+1)if(i!=0)
	{
		ll ans= combination(k-1,k-i);
		ans = mul( ans, combination( n-k+1, n-k-i+1 ) );
		cout << ans<< endl;
	}
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")"; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
    os << "[ "; for(auto v : V) os << v << " "; return os << "]"; }
template<class T> ostream& operator<<(ostream &os, set<T> S){
    os << "{ "; for(auto s:S) os<<s<<" "; return os<<"}"; }
template<class T> ostream& operator<<(ostream &os, multiset<T> S){
    os << "{ "; for(auto s:S) os<<s<<" "; return os<<"}"; }
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
    os << "{ "; for(auto m:M) os<<"("<<m.F<<":"<<m.S<<") "; return os<<"}"; }
    #define db(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " |"; __f(comma + 1, args...); }
#define rng(x) x.begin(), x.end()
#define pb push_back
#define F first
#define S second
#define el '\n'
 
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<bool> vb;
 
/*-----------------------------Code begins----------------------------------*/

void solve(){
    int n, m, c; cin>>n>>m>>c;
    vi cntRow(n), cntCol(m);
    vector <pi> tar(c);
    for (int i = 0; i < c; ++i){
        int x, y; cin>>x>>y;
        x--; y--;
        tar[i] = {x, y};
        cntRow[x]++;
        cntCol[y]++;
    }
    int mxR = *max_element(rng(cntRow));
    int mxC = *max_element(rng(cntCol));
    int mxColCnt = count(rng(cntCol), mxC);

    vi cntMaxRow(n);
    for (pi t : tar){
        if(cntRow[t.F] == mxR and cntCol[t.S] == mxC)
            cntMaxRow[t.F]++;
    }
    for (int i = 0; i < n; ++i){
        if(cntRow[i] == mxR and cntMaxRow[i] < mxColCnt){
            cout<<mxR + mxC<<el;
            return;
        }
    }
    cout<<mxR + mxC - 1<<el;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T=1, tc = 1;
    // cin>>T; 
    while(T--){
        solve();
    }
    return 0; 
}

Measured memory_bytes: 9012
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**7)
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rf = lambda: float(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]
rf_ = lambda: [float(_) for _ in rs().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
PI = math.pi
# endregion
A, B = ri_()
ans = 0
for i in range(A, B + 1):
    if str(i) == str(i)[::-1]:
        ans += 1
print(ans)

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

vector<vector<int>> g;
vector<int> deg, dist;

void dfs(int i) {
	// cout << "[" << i << "]\n";
	for (auto x : g[i]) {
		dist[x] = max(dist[x], dist[i] + 1);
		// cout << "{" << x << " " << dist[x] << "}\n";
		if (--deg[x] == 0) {
			dfs(x);
		}
	}
	// cout << "(" << i << " " << dist[i] << ")\n";
}

void solve() {
	int n, m; cin >> n >> m;
	deg.assign(n + 1, 0);
	dist.assign(n + 1, 0);
	g.assign(n + 1, vector<int>());
	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		g[x].emplace_back(y);
		++deg[y];
	}
	vector<int> sN;
	for (int i = 1; i <= n; ++i) {
		if (!deg[i]) {
			sN.emplace_back(i);
		}
	}
	for (auto s : sN) {
		dfs(s);
	}
	cout << *max_element(dist.begin(), dist.end());
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	// #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	// #endif
	solve();
	return 0;
}


Measured memory_bytes: 9600
N = int(input())
a = list(map(int,input().split()))

set_a = set(a)

import sys

if len(set_a) == 1:
    easy = 0
    print(easy)
    sys.exit()

totals = []

for i in range(min(a),max(a)+1):
    temp = 0
    for j in range(N):
        temp += (a[j]-i)**2
    totals.append(temp)

res = min(totals)
print(res)


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

int main() {
  int n, a, b, c, d;
  cin >>n;
  a = n/1000;
  b = (n % 1000)/100;
  c = (n % 100)/10;
  d = n % 10;
  if ((b==c)&&((a==b)||(c==d))) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n, r; cin >> n >> r;
	cout << (n >= 10 ? r : r + 100 * (10 - n)) << endl;
	
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	a := make([]int, n+1)
	b := make([]int, n)
	for i := 0; i < n+1; i++ {
		a[i] = nextInt()
	}
	for i := 0; i < n; i++ {
		b[i] = nextInt()
	}

	res := 0
	for i := 0; i < n; i++ {
		if a[i] >= b[i] {
			res += b[i]
		} else {
			if b[i] - a[i] > a[i+1] {
				res += a[i] + a[i+1]
				a[i+1] = 0
			} else {
				res += b[i]
				a[i+1] -= b[i] - a[i]
			}
		}
	}

	fmt.Println(res)
}

Measured memory_bytes: 4736
#include <iostream>
#include <cmath>
#include <string.h>
#include <cstdio>
#include <algorithm>
using namespace std;
bool com(char a,char b){
    return a>b;
}
int main(){
    int a,b,c,d,i,n;
    char arr[27];
    scanf("%s",arr);
    b = strlen(arr);
    sort(arr,arr+b,com);
    c = 0;
    for(i = 0;i < b-1;i++){
        if(arr[i]==arr[i+1]){
            cout<<"no";
            c++;
            break;
        }
    }
    if(c==0){
        cout<<"yes";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <cassert>
#include <fstream>

using namespace std;

int main() {
    
    int a, b;
    cin >> a >> b;
    int ret = max(2 * a - 1, 2 * b - 1);
    ret = max(ret, a + b);
    
    cout << ret << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define f first
#define s second
#define MOD 1000000007
#define mkp make_pair
#define M_PI 3.14159265358979323846
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
#define INF 2147483647
typedef long long ll;

#define MAXV 15000
struct edge {int to, cap, cost, rev;};
int V,E,S,T,F;
vector<edge> G[MAXV];
int dist[MAXV], prevv[MAXV], preve[MAXV];

void add_edge(int from, int to, int cap, int cost)
{
    G[from].pb((edge){to, cap, cost, G[to].size()});
    G[to].pb((edge){from, 0, -cost, G[from].size()-1});
}

int min_cost_flow(int S, int T, int F)
{
    int res = 0;
    while(F > 0)
    {
        fill(dist, dist+V, INF);
        dist[S] = 0;
        bool update = true;
        while(update)
        {
            update = false;
            for(int v = 0; v < V; v++)
            {
                if(dist[v] == INF)continue;
                for(int i = 0; i < G[v].size(); i++)
                {
                    edge &e = G[v][i];
                    if(e.cap > 0 && dist[e.to] > dist[v] + e.cost)
                    {
                        dist[e.to] = dist[v]+e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }
        if(dist[T] == INF)return -1;
        int d = F;
        for(int v = T; v != S; v = prevv[v])
        {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        F-=d;
        res+=d*dist[T];
        for(int v = T; v != S; v = prevv[v])
        {
            edge &e = G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}


#define MAXN 10005
int N,M,K;
int w[MAXN],a[MAXN],last[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    
    cin>>M>>N>>K;
        V=K+2;
        FOR(i,0,V-1)G[i].clear();
        S=0;
        T=K+1;
        
        FOR(i,1,N)cin>>w[i];
        int tot=0;
        FOR(i,1,K)
        {
            cin>>a[i];
            if(i==1||a[i]!=a[i-1])tot+=w[a[i]];//changing count
        }
        
        memset(last,-1,sizeof(last));
        FOR(i,1,K)
        {
            int now=a[i];
            if(last[now]!=-1&&last[now]!=i-1)
            {
                add_edge( last[now], i-1, 1, -w[now] );
            }
            last[now]=i;
        }
        FOR(i,0,V-2)add_edge( i, i+1, INF, 0 );
        
        cout<<tot+min_cost_flow(S,T,M-1)<<'\n';


    return 0;
}


Measured memory_bytes: 4580
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

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

class Solve {
public:
	Solve() {};
	~Solve() {};

	void solver() {
		std::vector<int> results;
		while (1) {
			int n;
			std::cin >> n;
			if (!n) break;

			std::vector<std::pair<int, int>> times;
			std::string str;
			rep(i, n) {
				times.push_back(std::make_pair(0, 0));
				std::cin >> str;
				times.back().first = std::stoi(str.substr(6, 2)) + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(0, 2)) * 3600;
				std::cin >> str;
				times.back().second = std::stoi(str.substr(6, 2)) + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(0, 2)) * 3600;
			}
			std::sort(times.begin(), times.end(), std::greater<std::pair<int, int>>());
			//???????????????????????????
			std::vector<int> usingTrain; //int?????°?????????
			int maxTrain = 0;
			while (!times.empty()) {
				int leave = times.back().first;
				int arrive = times.back().second; times.pop_back();
				//??°???????????????????????????
				std::sort(usingTrain.begin(), usingTrain.end(), std::greater<int>());
				//????????°???
				if (!usingTrain.empty()) {
					//????????°?????????????????????????????°???
					if (leave >= usingTrain.back()) {
						usingTrain.pop_back();
					}
				}
				//??????
				usingTrain.push_back(arrive);
				if (maxTrain < usingTrain.size()) maxTrain = usingTrain.size();
			}
			results.push_back(maxTrain);
		}
		for (auto& x : results) {
			std::cout << x << std::endl;
		}
	}
private:
};

int main() {
	Solve solve;
	solve.solver();
	getchar(); getchar();
	return 0;
}

Measured memory_bytes: 3112
N,M,X = map(int,input().split())
A = list(map(int,input().split()))
cost1 = 0
for i in range(X):
  if i in A:
    cost1 += 1
cost2 = 0
for i in range(X+1,N+1):
  if i in A:
    cost2 += 1
print(min(cost1,cost2))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  int a,b;
  cin>>a>>b;
  int c;
  if(b<10) c=10*a+b;
  else if(b==100) c=1000*a+b;
  else c=100*a+b;
  rep(i,350){
    if(i*i == c){cout<<"Yes"<<endl;return 0;}
  }
  cout<<"No"<<endl;

  return 0;
}






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

int a, b, c, d;

int main() {
	cin >> a >> b >> c >> d;
	if (min(abs(a - c), max(abs(a - b), abs(b - c))) <= d) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def Maximum_Sum(a , b , c , k):

    return a + b + c - max(a , b , c) + max(a , b , c) * (2**k)

def main():
    a, b, c = map(int, input().split())
    k = int(input())
    print(Maximum_Sum(a , b , c , k))

if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, x;
string s;
char c;

int main(){
	cin >> n;
	bool f = 1;
	int rank = 0;
	REP(i, n){
		cin >> c >> x;
		if (c == ')')rank -= x;
		else rank += x;
		if (rank < 0)f = 0;
	}
	if (f&&rank == 0)cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

#define ull unsigned long long
#define ll long long
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define PI acos(-1.0)
const int N=2e5 + 5;
const int M=1e5 + 5;


int main()
{
	ios_base::sync_with_stdio(false);
	int i,n;
	ll s[N];
	cin>>n;
	for(i=0;i<n;i++){
		cin>>s[i];
	}
	if(s[0]!=0){
		cout<<-1<<endl;
		return 0;
	}
	for(i=1;i<n;i++){
		if(!(s[i]<=1+s[i-1])){
			cout<<-1<<endl;
			return 0;		
		}
	}
	ll ans=0;
	ll mx=0;
	for(i=1;i<n;i++){
		if(s[i]!=s[i-1]+1){
			ans+=s[i-1];
		}
	}
	ans+=s[n-1];
	cout<<ans<<endl;
		
	
		
	return 0;
}

Measured memory_bytes: 1920
#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>;
#include <algorithm>
template<class T> inline bool chmax(T& a, T b) { if (a<b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a>b) { a = b; return 1; } return 0;}

const ll INF = 1LL <<  60;

ll h[100010];

ll dp[100010];

int main()
{
        int n;
        cin >> n;
        vector<int> a[n];
        rep(i,n) cin >> h[i];
        rep(i,100010) dp[i] = INF;

        dp[0] = 0;

        for (int i = 1; i < n; i++) {
                chmin(dp[i], dp[i-1] + abs(h[i] - h[i -1]));
                if (i > 1)
                        chmin(dp[i], dp[i-2] + abs(h[i] - h[i -2]));
        }

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


Measured memory_bytes: 4096
#include<stdio.h>
 
int main()
{
  int t[4][14];
  int n, i,j,c;
  char m, d;
  for(i=0; i < 4; i++){
    for(j=0; j < 14; j++){
      t[i][j]=0;
    }
  }
 scanf("%d", &c);
  for(i = 0; i < c; i++){
    scanf("%c", &d);
    scanf("%c %d", &m, &n);
    if(m == 'S'){
      t[0][n] = 1;
    }
    else if(m == 'H'){
      t[1][n] = 1;
    }
    else if(m == 'C'){
      t[2][n] = 1;
    }
    else if(m == 'D'){
      t[3][n] = 1;
    }
  }
  for(j=1; j < 14; j++){
    if(t[0][j] != 1){
      printf("S %d\n", j);
    }
  }
 
 for(j=1; j < 14; j++){
    if(t[1][j] != 1){
      printf("H %d\n", j);
    }
  }
 
 for(j=1; j < 14; j++){
    if(t[2][j] != 1){
      printf("C %d\n", j);
    }
  }
 
 for(j=1; j < 14; j++){
    if(t[3][j] != 1){
      printf("D %d\n", j);
    }
  }
 return 0;
}
 



Measured memory_bytes: 2108
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, h, w; cin >> n >> h >> w;
  int ans = 0;
  REP(i, n) {
    int a, b; cin >> a >> b;
    if (h <= a && w <= b) ++ans;
  }
  cout << ans << '\n';
  return 0;
}


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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(int i=x;i<y;i++)
#define frr(i,x,y) for(int i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
VL dx={1,0,-1,0};
VL dy={0,1,0,-1};
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

void solve()
{
    string str;
    cin>>str;
    ll n=SZ(str);
    if(str[n-1]=='s')
        cout<<str<<"es\n";
    else
        cout<<str<<"s\n";
    return;
}
int main()
{
    IOS;
    ll t=1,pp;
    //cin>>t;
    pp=t;
    while(t--)
    {
        //cout<<"Case #"<<pp-t<<": ";
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
/*
recursion - matrix exponential

*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 3660
#include<cstdio>
const int MaxN=3010,MaxQ=3010,mod=1000000007,I2=mod+1>>1;
int N,Q,A[MaxN],X[MaxQ][2],tmp[MaxN],nxt[MaxQ][2],f[MaxQ][MaxQ],g[MaxQ][MaxN];
int main(){
	scanf("%d%d",&N,&Q);
	for(int i=1;i<=N;i++)scanf("%d",A+i),tmp[i]=-1;
	for(int i=0;i<Q;i++)scanf("%d%d",X[i],X[i]+1);
	for(int i=Q;i--;){
		for(int j=2;j--;)nxt[i][j]=tmp[X[i][j]],tmp[X[i][j]]=i;
		for(int j=1;j<=N;j++){
			for(int k=2;k--;)g[i][j]=(g[i][j]+(nxt[i][k]==-1?(X[i][k]<j):g[nxt[i][k]][j]))%mod;
			g[i][j]=1ll*g[i][j]*I2%mod;
		}
	}
	for(int i=Q;i--;)for(int j=Q;j-->i;){
		if(i==j)f[i][j]=I2;
		else{
			for(int k=2;k--;){
				if(nxt[i][k]==-1)f[i][j]=(f[i][j]+(mod+1-g[j][X[i][k]]))%mod;
				else if(nxt[i][k]<=j)f[i][j]=(f[i][j]+f[nxt[i][k]][j])%mod;
				else f[i][j]=(f[i][j]+(mod+1-f[j][nxt[i][k]]))%mod;
//				f[i][j]=(f[i][j]+(nxt[i][k]==-1?g[j][X[i][k]]:f[nxt[i][k]][j]))%mod,printf("i=%d j=%d k=%d nxt=%d %d\n",i,j,k,nxt[i][k],(nxt[i][k]==-1?g[j][X[i][k]]:f[nxt[i][k]][j]));
			}
			f[i][j]=1ll*f[i][j]*I2%mod;
		}
	}
	int ans=0;
	for(int i=1;i<=N;i++)for(int j=i+1;j<=N;j++)if(A[i]!=A[j]){
		int t=0;
		if(tmp[i]==-1){
			if(tmp[j]==-1)t=1;
			else t=(mod+1-g[tmp[j]][i])%mod;
		}
		else if(tmp[j]==-1)t=g[tmp[i]][j]%mod;
		else t=tmp[i]<tmp[j]?f[tmp[i]][tmp[j]]:(mod+1-f[tmp[j]][tmp[i]])%mod;//,printf("f(%d,%d)=%lld\n",tmp[j],tmp[i],f[tmp[j]][tmp[i]]*(1ll<<Q)%mod);
		if(A[i]<A[j])t=(mod+1-t)%mod;
		ans=(ans+t)%mod;
		//printf("i=%d j=%d ans=%lld\n",i,j,t*(1ll<<Q)%mod);
	}
	for(int i=Q;i--;)ans=ans*2%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 70272
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double E = 1e-9;
//int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0 ,1, 1, 1, 0, -1, -1, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
string a, b;
int dp[3010][3010];
int f(int i, int j){
    if(i == sz(a) or j == sz(b))
        return 0;
    int &ans = dp[i][j];
    if(ans == -1){
        ans = 0;
        if(a[i] == b[j])
            ans = f(i + 1, j + 1) + 1;
        else
            ans = max(f(i + 1, j), f(i, j + 1));

    }return ans;
}

void build(int i, int j){
    if(i == sz(a) or j == sz(b))
        return;
    int ans = f(i, j);
    if(a[i] == b[j] && ans == f(i + 1, j + 1) + 1){
        cout << a[i];
        build(i + 1, j + 1);
        return ;
    }
    else{
        if(ans == f(i + 1, j)){
            build(i + 1, j);
            return;
        }else{
            build(i, j + 1);
            return ;
        }
    }
}
int main(){
    //FL;
    FIN;
    cin >> a >> b;
    cls(dp, -1);
    f(0, 0);
    build(0, 0);
    EjecuteTime;
    return 0;
}       

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

int N;
vector<int> V;
int dp[100010];

int main()
{
    scanf("%d",&N);
    int tmp = 1;
    while(tmp <= N)V.push_back(tmp),tmp *= 6;
    tmp = 1;
    while(tmp <= N)V.push_back(tmp),tmp *= 9;

    for(int i = 1; i <= N; i++)dp[i] = 1001001001;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < V.size(); j++)if(i + V[j] <= N)dp[i + V[j]] = min(dp[i + V[j]],dp[i] + 1);
    }
    printf("%d\n",dp[N]);
    return 0;
}


Measured memory_bytes: 640
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	int nums[16384], ans[8192];
	int i, j, n, size, half, p;
	
	while(scanf("%d", &n), n){
		size = 0;
		half = (n-1) / 2;
		for(i=1; i<n; ++i)
			nums[size++] = (i*i) % n;

		sort(nums, nums + size);
		size = unique(nums, nums + size) - nums;

		memset(ans, 0, (half+1)*4);
		for(i=0; i<size; ++i){
			for(j=0; j<i; ++j){
				++ans[(p=abs(nums[i]-nums[j]))>half?n-p:p];
			}
		}
		for(i=1; i<=half; ++i)
			printf("%d\n", ans[i]*2);
	}

	return 0;
}

Measured memory_bytes: 828
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll a[1000005];
long long n,  cnt = 0;

void dfs(int len, int x, ll num)
{
	if(len == 10) return;
	ll tmp;
	for(int i = -1; i <= 1; i++)
	{
		int y = x + i;
		if(0 <= y && y <= 9)
		{
			tmp = 10 * num + y;
			a[++cnt] = tmp;
			dfs(len + 1, y, tmp);
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= 9; i++)
	{
		a[++cnt] = i;
		dfs(1, i, i);
	}
	sort(a + 1, a + cnt + 1);
	cout << a[n] << endl;
	return 0;
}



Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
string cal(string s) {
	int max_v = -1111111;
	rep(i, 1, s.length()) {
		max_v = max(max_v, stoi(s.substr(0, i))*stoi(s.substr(i)));
	}
	return to_string(max_v);
}
signed main() {
	int q; cin >> q;
	rep(i, 0, q) {
		string s;
		cin >> s;
		set<string>taro;
		int cnt = 0;
		if (stoi(s) < 10)goto here;
		while (taro.find(s) == taro.end()) {
			if (stoi(s) < 10)break;
			cnt++;
			taro.insert(s);
			s = cal(s);
			dump(cnt);
			dump(s);

		}
	here:;
		if (taro.find(s) == taro.end())cout << cnt << endl;
		else cout << -1 << endl;

	}
	return 0;
}

Measured memory_bytes: 3264
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    ll s,w;
    cin >> s >> w;
    if (w >= s){cout << "unsafe" << endl;}
    else {cout << "safe" << endl;}
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e3 + 5;

int n,k,a[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	int ans=0;
	for(int i=1;i<=k;i++){
		ans+=a[i];
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 3660
#include <stdio.h>
#include <math.h>
#include <string.h>


int main(){
	int n, i;
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if(a > b){
			int tmp = b;
			b = a;
			a = tmp;
		}
		if(b > c){
			int tmp = c;
			c = b;
			b = tmp;
		}
		if(a*a + b*b == c*c) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mod(ll a,ll b)
{
    return max(a,b)-min(b,a);
}
ll dp[1000000];
ll h[1000000];
ll k;
ll jum(ll n)
{
    if(n==1)return 0;
    if(dp[n]!=1000000000000000)
        return dp[n];
    for(int i=1;i<=k;i++)
    {
        if(i>=n)break;
        if(dp[n-i]==1000000000000000)
        dp[n-i]=jum(n-i);
        dp[n]=min(dp[n],dp[n-i]+mod(h[n],h[n-i]));
    }
    return dp[n];
}
int main() {
    ll n;
    cin>>n>>k;
    for(ll i=0;i<=n;i++)
        dp[i]=1000000000000000;
    for(ll i=1;i<=n;i++)
        cin>>h[i];
    cout<<jum(n)<<endl;
	return 0;
}

Measured memory_bytes: 9856
def submit():
    n = int(input())
    blist = list(map(int, input().split()))

    ans = blist[0] + blist[-1]
    for i in range(0, n - 2):
        ans += min(blist[i], blist[i + 1])

    print(ans)


if __name__ == "__main__":
    submit()


Measured memory_bytes: 2940
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 40;

int n;
char s[N], t[N];
LL ans;
int dp[20][20];

inline int work(int st) {
  char s1[N], s0[N];
  int t1 = 0, t0 = 0;
  for (int i = 0; i < n; i ++) {
    if ((st >> i) & 1) s1[t1 ++] = s[i];
    else s0[t0 ++] = s[i];
  }
  memset(dp, 0, sizeof dp);
  dp[0][0] = 1;
  for (int i = 0; i <= t1; i ++)
    for (int j = 0; j <= t0; j ++) {
      if (t[i + j] == s1[i]) dp[i + 1][j] += dp[i][j];
      if (t[i + j] == s0[j]) dp[i][j + 1] += dp[i][j];
    }
  return dp[t1][t0];
}

int main() {
  scanf("%d", &n);
  scanf("%s", s);
  memcpy(t, s, sizeof t);
  reverse(t, t + n + n);
  for (int i = 0; i < (1 << n); i ++) ans += work(i);
  printf("%lld\n", ans);
  return 0;
}


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

#define pb push_back
#define mp make_pair

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

int main() {
  double a, b;
  cin >> a >> b;

  int c_low = (int)floor(min(a*12.5, b*10.0));
  int c_high = (int)ceil(max(a*12.5, b*10.0));

  int res = -1;
  for (int i = c_low; i <= c_high; ++i) {
    if ((int)floor((double)i*0.08) == a && (int)floor((double)i*0.1) == b) {
      res = i;
      break;
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15); //"for float-base
  // problem"
  int N;
  cin >> N;
  Vl A(N);
  ll total = 0;
  REP(i, N) {
    cin >> A.at(i);
    total ^= A.at(i);
  }

  REP(j, N) {
    int ans = total ^ A.at(j);
    cout << ans << " ";
  }

  cout << "\n";
}

Measured memory_bytes: 4764
MOD = 10 ** 9 + 7
h, w, k = map(int, input().split())
dp = [0] * w
dp[0] = 1

fdp = [[0, 0] for _ in range(w)]
fdp[0][0] = 1
for i in range(w - 1):
    fdp[i+1][0] += fdp[i][0]
    fdp[i+1][1] += fdp[i][0]
    fdp[i+1][0] += fdp[i][1]

def f(i):
    if i < 0:
        return 1
    return fdp[i][0] + fdp[i][1]

for _ in range(h):
    ndp = [0] * w
    for i in range(w):
        ndp[i] = (ndp[i] + dp[i] * f(i - 1) * f(w - i - 2))  % MOD
        if i + 1 < w:
            ndp[i+1] = (ndp[i+1] + dp[i] * f(i - 1) * f(w - i - 3)) % MOD
        if i - 1 >= 0:
            ndp[i-1] = (ndp[i-1] + dp[i] * f(i - 2) * f(w - i - 2)) % MOD
    dp = ndp
print(dp[k-1])


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
S = input()
h = [0]*N
h = 'RGB'*1000

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')
'''
cnt = -1
ans = 0
for i in range(N):
    cnt = int(h[i])
    for j in range(i+1, N):
        num = cnt + int(h[j])
        if num == 3 or num == 9 or num==8:
            for k in range(j+1, N):
                if num + int(h[k]) == 10 and k!=2*j-i:
                    ans += 1
'''

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')

c_r = c_g = c_b = 0
h = ''
for i, a in enumerate(S):
    if a == 'R':
        c_r += 1
        h += '1'
    if a == 'G':
        c_g += 1
        h += '2'
    if a == 'B':
        c_b += 1
        h += '7'

ans = c_r * c_g * c_b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i<N and int(h[i]) + int(h[j]) + int(h[2*j-i]) == 10:
            ans -= 1
print(ans)

Measured memory_bytes: 68488
#include<iostream>

using namespace std;

int main(){
    int m, d;
    int ans = 0;
    cin >> m >> d;

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= d; j++){
            int d_1 = j % 10;
            int d_10 = j / 10;

            if(d_1 >= 2 && d_10 >= 2 && d_1 * d_10 == i){
                ans++;
            }
        }
    }

    cout << ans;
}


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
//    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    const double PI = acos(-1);
    double a, b, x;
    cin >> a >> b >> x;

    double ang = 0;
    if (x > a*a*b*0.5){
        double y = a*a*b - x;
        double c = 2 * y / a / a;
        ang = atan2(a, c) * 180 / PI;
    }
    else {
        double c = 2 * x / a /  b;
        ang = atan2(c, b) * 180 / PI;
    }
    ang = 90 - ang;
    printf("%.15f\n", ang);

    if (argc == 2 && atoi(argv[1]) == 123456789)        cerr << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n, m, c;
    ll ans = 0;

    cin >> n >> m >> c;

    vector<int> b(m);
    int a[30][30];

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

    for (int i = 0; i < n; i++)
    {
        ll point = 0;

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

            point += a[i][j] * b[j];
        }

        point += c;

        if (point > 0)
        {
            ans++;
        }
    }

    cout << ans << endl;
}

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

#ifdef NOKI
#include "debug.h"
#else
#define debug(args...)
#endif

int main(){
    int a, b, c=-1, d=-2, n, p;scanf("%d", &n);
    string s = "No";
    while(n--){
        scanf("%d%d", &a, &b);
        if(a==b && c==d) {p++;debug("here", p);}
        else if(a==b){p=1;debug("now", p);}
        else p = 0;
        c=a, d=b;
        if(p>=3) s = "Yes";
    }
    cout<<s<<endl;

    return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>
int main(){
        int ball[10];
        int N,i,j,a,b;
        scanf("%d",&N);
        for(j=0;j<N;j++){
        for(i=0;i<10;i++){
                scanf("%d", &ball[i]);
        }
        a = ball[0];
        b = 0;
        for(i=1;i<10;i++){
                if(a < ball[i]){
                        a = ball[i];
                }else if (b < ball[i]){
                        b = ball[i];
                }else{
                        printf("NO\n");
                        break;
                }
                if(i == 9){
                        printf("YES\n");
                }
        }
        }
return 0;
}

Measured memory_bytes: 576