akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a,b;
    int count=0;
    cin>>a>>b;
    if(b==1)
        count=0;
    else if(a>=b)
        count=1;
    else
    {
        b-=a;
        count++;
        while(b>0)
        {
            b-=a-1;
            count++;
        }
    }
    cout<<count<<endl;

    return 0;
}

Measured memory_bytes: 256
#if 0



#endif // 0

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = (int) 35;
const int INF = (int) 0x3f3f3f3f;
typedef long long LL;
int H,W,S;
int f[MAXN][MAXN][MAXN][MAXN];
int g[MAXN][MAXN][MAXN][MAXN];
int a[MAXN][MAXN];
int TOTAL;
int MI;

int get_sum(int i,int j,int k,int t){
    return a[k][t]-a[k][j-1]-a[i-1][t]+a[i-1][j-1];
}

void DFS(int I,int J,int K,int T){
    f[I][J][K][T]=1;
    g[I][J][K][T]=get_sum(I,J,K,T);
    if(I==K&&J==T) return;
    if(g[I][J][K][T]<MI) return;
    for(int i=I;i<K;i++){
        if(f[I][J][i][T]==-1) DFS(I,J,i,T);
        if(f[i+1][J][K][T]==-1) DFS(i+1,J,K,T);
        if(g[I][J][i][T]>=MI&&g[i+1][J][K][T]>=MI){
            if(f[I][J][i][T]+f[i+1][J][K][T]>f[I][J][K][T]){
                f[I][J][K][T]=f[I][J][i][T]+f[i+1][J][K][T];
                g[I][J][K][T]=min(g[I][J][i][T],g[i+1][J][K][T]);
            }
            else if(f[I][J][i][T]+f[i+1][J][K][T]==f[I][J][K][T]){
                int cur_mi=min(g[I][J][i][T],g[i+1][J][K][T]);
                g[I][J][K][T]=max(g[I][J][K][T],cur_mi);
            }
        }
    }
    for(int j=J;j<T;j++){
        if(f[I][J][K][j]==-1) DFS(I,J,K,j);
        if(f[I][j+1][K][T]==-1) DFS(I,j+1,K,T);
        if(g[I][J][K][j]>=MI&&g[I][j+1][K][T]>=MI){
            if(f[I][J][K][j]+f[I][j+1][K][T]>f[I][J][K][T]){
                f[I][J][K][T]=f[I][J][K][j]+f[I][j+1][K][T];
                g[I][J][K][T]=min(g[I][J][K][j],g[I][j+1][K][T]);
            }
            else if(f[I][J][K][j]+f[I][j+1][K][T]==f[I][J][K][T]){
                int cur_mi=min(g[I][J][K][j],g[I][j+1][K][T]);
                g[I][J][K][T]=max(g[I][J][K][T],cur_mi);
            }
        }
    }
}

void work(){
    while(~scanf("%d%d%d",&H,&W,&S)){
        if(H==0&&W==0&&S==0) break;
        TOTAL=0;
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++){
                scanf("%d",&a[i][j]);
                TOTAL+=a[i][j];
                a[i][j]+=a[i][j-1];
            }
        }
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++){
                a[i][j]+=a[i-1][j];
            }
        }
//        for(int i=1;i<=H;i++){
//            for(int j=1;j<=W;j++){
//                printf("%d ",a[i][j]);
//            }
//            printf("\n");
//        }
        MI=TOTAL-S;
        memset(f,-1,sizeof(f));
        memset(g,-1,sizeof(g));
        DFS(1,1,H,W);
        printf("%d %d\n",f[1][1][H][W],g[1][1][H][W]-MI);
    }
}

int main(){
    work();
    return 0;
}



Measured memory_bytes: 14872
import math
dataset=[]
while True:
	num=int(input())
	if num==0:
		break
		
	scores=[int(x) for x in input().split(' ')]
	dataset.append([num,scores])


for d in dataset:
	num=d[0]
	scores=d[1]
	fsum=sum(scores)
	average=fsum/num

	sts=[i-average for i in scores]
	bunsan=sum([i**2 for i in sts])/num
	sd=math.sqrt(bunsan)
	print("{:.4f}".format(sd))




Measured memory_bytes: 5720
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main() {
  int h,w;
  cin >> h>>w;
  
  vector<string> p(h);
  rep(i,h){
  cin>>p[i];
  cout << p[i] << endl;
  cout << p[i] << endl;  
  }
    
    
}

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

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

    vector<int> v(n);
    rep(i, n){
        cin >> v[i];
    }

    sort(all(v));
    vector<int> sa(n);
    rep(i, n-1){
        sa[i] = v[i+1] - v[i];
    }
    sa[n-1] = k + v[0] - v[n-1];

    cout << k - *max_element(all(sa));

}

Measured memory_bytes: 1792
from math import cos, sqrt
pi = 3.141592653589793238
a, b, H, M = map(int, input().split())
h, m = (2*pi*(H+M/60))/12, (2*pi*M)/60
if h-m < pi:
	x = h-m
else:
	x = 2*pi - h+m
print(sqrt(a*a + b*b - 2*a*b*cos(x)))

Measured memory_bytes: 62584
import sys
import math
import itertools as it
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

def f(a,b):
    if a == b:
        return True
    return False
if __name__ == "__main__":
    s = L()
    for i in range(1,len(s)-1):
        a = s[:len(s)-i]
        n = len(a)
        #print(a[:n//2],a[n//2:])
        if (f(a[:n//2],a[n//2:])):
            print(n)
            break

Measured memory_bytes: 9020
let () = Scanf.scanf "%d %d\n" @@ fun n t ->
    Array.init n (fun _ -> Scanf.scanf " %d" (fun t -> t))
    |> Array.fold_left (fun (t1, sum) t2 -> (t2, sum+min (t2-t1) t)) (0, t)
    |> function (_, sum) -> sum
    |> Printf.printf "%d"


Measured memory_bytes: 6016
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

/**
 * The Code A Doctor Loved
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		final String[] c1 = new String[128];
		c1[' '] = "101";
		c1['\''] = "000000";
		c1[','] = "000011";
		c1['-'] = "10010001";
		c1['.'] = "010001";
		c1['?'] = "000001";
		c1['A'] = "100101";
		c1['B'] = "10011010";
		c1['C'] = "0101";
		c1['D'] = "0001";
		c1['E'] = "110";
		c1['F'] = "01001";
		c1['G'] = "10011011";
		c1['H'] = "010000";
		c1['I'] = "0111";
		c1['J'] = "10011000";
		c1['K'] = "0110";
		c1['L'] = "00100";
		c1['M'] = "10011001";
		c1['N'] = "10011110";
		c1['O'] = "00101";
		c1['P'] = "111";
		c1['Q'] = "10011111";
		c1['R'] = "1000";
		c1['S'] = "00110";
		c1['T'] = "00111";
		c1['U'] = "10011100";
		c1['V'] = "10011101";
		c1['W'] = "000010";
		c1['X'] = "10010010";
		c1['Y'] = "10010011";
		c1['Z'] = "10010000";

		final HashMap<String, Character> c2 = new HashMap<String, Character>() {
			{
				put("00000", 'A');
				put("00001", 'B');
				put("00010", 'C');
				put("00011", 'D');
				put("00100", 'E');
				put("00101", 'F');
				put("00110", 'G');
				put("00111", 'H');
				put("01000", 'I');
				put("01001", 'J');
				put("01010", 'K');
				put("01011", 'L');
				put("01100", 'M');
				put("01101", 'N');
				put("01110", 'O');
				put("01111", 'P');
				put("10000", 'Q');
				put("10001", 'R');
				put("10010", 'S');
				put("10011", 'T');
				put("10100", 'U');
				put("10101", 'V');
				put("10110", 'W');
				put("10111", 'X');
				put("11000", 'Y');
				put("11001", 'Z');
				put("11010", ' ');
				put("11011", '.');
				put("11100", ',');
				put("11101", '-');
				put("11110", '\'');
				put("11111", '?');
			}
		};

		while ((line = br.readLine()) != null) {
			//
			if (line.isEmpty()) {
				System.out.println("");
				continue;
			}
			StringBuilder sb1, sb2;
			sb1 = new StringBuilder();
			sb2 = new StringBuilder();
			for (char c : line.toCharArray()) {
				sb1.append(c1[c]);
			}
			//
			sb1.append("00000");
			//
			String line2 = sb1.toString();
			for (int i = 0; i < line2.length() - 5; i += 5) {
				sb2.append(c2.get(line2.substring(i, i + 5)));
			}
			System.out.println(sb2.toString());
		}
	}
}

Measured memory_bytes: 24036
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using namespace std;

typedef pair<int, int> point;
#define X first
#define Y second

inline point operator+(const point &a, const point &b) {
	return point(a.X + b.X, a.Y + b.Y);
}

enum { N, E, S, W, D };
const point dv[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

char convert[128];

constexpr int MAX_D = 10;
constexpr int MAX_T = 100;
constexpr int MAX_C = 50;

bool can_move[MAX_C + 1][MAX_C + 1][D];
set<point> dp[MAX_D * MAX_T + 1][D];

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

	convert['N'] = N;
	convert['E'] = E;
	convert['S'] = S;
	convert['W'] = W;

	int n, sx, sy, t;
	cin >> n >> sx >> sy >> t;

	for(int i = 0; i < n; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		if(x1 == x2) {
			if(y1 > y2) swap(y1, y2);

			for(int y = y1; y <= y2; ++y) {
				if(y > y1) can_move[y][x1][S] = true;
				if(y < y2) can_move[y][x1][N] = true;
			}
		}
		else {
			if(x1 > x2) swap(x1, x2);

			for(int x = x1; x <= x2; ++x) {
				if(x > x1) can_move[y1][x][W] = true;
				if(x < x2) can_move[y1][x][E] = true;
			}
		}
	}

	vector<int> dist(t);
	vector<int> direction(t);

	for(int i = 0; i < t; ++i) {
		char c;
		cin >> dist[i] >> c;
		direction[i] = convert[c];
	}

	partial_sum(begin(dist), end(dist), begin(dist));

	for(int dir = 0; dir < D; ++dir) {
		dp[0][dir].insert(point(sx, sy));
	}

	int check_index = 0;
	for(int d = 0; d < dist.back(); ++d) {
		const bool is_check_time = (d == dist[check_index]);

		for(int dir = 0; dir < D; ++dir) {
			for(int next_dir = 0; next_dir < D; ++next_dir) {
				if((dir ^ next_dir) == 2) continue;
				if(is_check_time && (dir != direction[check_index] && next_dir != direction[check_index])) continue;

				for(const auto &p : dp[d][dir]) {
					if(!can_move[p.Y][p.X][next_dir]) continue;
					dp[d + 1][next_dir].insert(p + dv[next_dir]);
				}
			}
			dp[d][dir].clear();
		}

		if(is_check_time) ++check_index;
	}

	set<point> ans;
	for(int dir = 0; dir < D; ++dir) {
		if((dir ^ direction.back()) == 2) continue;

		for(const auto &p : dp[dist.back()][dir]) {
			if(dir == direction.back() || can_move[p.Y][p.X][direction.back()]) {
				ans.insert(p);
			}
		}
	}

	for(const auto &p : ans) {
		cout << p.X << " " << p.Y << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1492
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll q;
  cin >> q;
  vl a(q),b(q);
  rep(i,q){
    cin >> a[i] >> b[i];
  }
  rep(i,q){
    if(a[i]==b[i]){
      cout << 2*a[i]-2 << endl;
    }
    else{
    ll k=sqrt(a[i]*b[i]);
    if(k*k==a[i]*b[i]){
      k--;
    }
    ll l=k;
    if(k*(l+1)<a[i]*b[i]){
      l++;
    }
    cout << k+l-2 << endl;
    }
  }
}

Measured memory_bytes: 256
n,k=map(int,(input().split()))
a=[]
for i in range(n):
    a.append(int(input()))

a.sort()
min_high=1000000000000

for i in range(n-k+1):
    high=-a[i]+a[i+k-1]
#    print(high,a[i],i)
    if high<min_high:
        min_high=high

print(min_high)

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

using namespace std;

typedef long long ll;

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

    bool ans=true;
    for (int i=0;i<s.size();i+=2) {
        if ((i+1)%2==1 && (s[i]=='R' || s[i]=='U' || s[i]=='D')) {
        } else {
            cout << "No" << endl;
            return 0;
        }
    }
    
    for (int i=1;i<s.size();i+=2) {
        if ((i+1)%2==0 && (s[i]=='L' || s[i]=='U' || s[i]=='D')) {
        } else {
            cout << "No" << endl;
            return 0;
        } 
    }

    cout << "Yes" << endl;
    
    return 0;
}

Measured memory_bytes: 256
str = gets.split
N,L = str[0].to_i, str[1].to_i
min = L.abs
a = L
sum = 0
for x in 0...N do
    sum += L + x
    if min > (L+x).abs
        a = (L+x)
        min = a.abs
    end
end
puts sum - a

Measured memory_bytes: 1788
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top,S[1000];

void push(int x);
int pop();

int main(){
  int a,b;
  top=0;
  char s[100];

  while(scanf("%s",s)!=EOF){
    if(s[0]=='+'){
      a=pop();
      b=pop();
      push(a+b);
    }
    else if(s[0]=='-'){
      a=pop();
      b=pop();
      push(b-a);
    }
    else if(s[0]=='*'){
      a=pop();
      b=pop();
      push(a*b);
    }
    else
      push(atoi(s));
  }

printf("%d\n",pop());

return 0;
}

void push(x){
  S[++top]=x;
}

int pop(){

  top--;

  return S[top+1];
}

Measured memory_bytes: 548
//
// Created on 2020/09/23.
//


#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
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; }
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;

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

int main() {
    int n;
    cin>>n;
    int x;
    cin>>x;
    ll t;
    cin>>t;
    t = abs(t-x);
    ll ans = t;
    for (int i = 1; i < n; ++i) {
        ll t;
        cin>>t;
        t = abs(t-x);
        ans = gcd(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3572
let ans s =
  let n = String.length s in
  let rec f i c ret =
    if i = n then ret
    else if s.[i] = c then f (i+1) c ret
    else f (i+1) s.[i] (ret+1)
  in f 1 s.[0] 0;;

Scanf.scanf "%s" (fun s -> print_int (ans s))


Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
#include <sstream>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

 
int main() {
    ll ans = 0;
    ll n;

    cin >> n;

    vector<ll> h;

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        h.push_back (temp);
    }

    ll max = 0;
    for (int i = 0; i < n; i++) {
        if (h[i] > max) max = h[i];
        if (max > h[i] + 1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

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

const long long mod = 1e9 + 7;
vector <vector <long long>> c;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	c.resize(n + 1);
	for (int i = 0; i <= n; i++){
		c[i].resize(n + 1);
	}
	c[0][0] = 1;
	for (int i = 1; i <= n; i++){
		c[i][0] = 1;
		for (int j = 1; j <= i; j++){
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
			c[i][j] %= mod;
		}
	}
	for (int i = 0; i < k; i++){
		if (i + 1 > n - k + 1){
			cout << "0\n";
		}
		else
			cout << (long long)(c[n - k + 1][i + 1] * c[k - 1][i]) % mod << '\n';
	}
}

Measured memory_bytes: 31616
keys = {
    '1': '.,!? ',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

def solve_testcase():
    s = input().split('0')
    res = ''
    for s0 in s:
        if not s0: continue
        c = s0[0]
        v = keys[c]
        res += v[(len(s0)-1) % len(v)]

    print(res)

def main():
    n = int(input())
    for _ in range(n): solve_testcase()

main()



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

long long Gcd(long long c, long long d){
    long long gcd = c%d;
    while(gcd > 0){
        c = d;
        d = gcd;
        gcd = c%d;
    }
    return d;
}

int main(){
    long long a, b, c, d, lcm, ans;
    cin >> a >> b >> c >> d;

    lcm = c*d/Gcd(c,d);
    ans = b/c - (a-1)/c + b/d - (a-1)/d - b/lcm + (a-1)/lcm;
    ans = b - a + 1 - ans;
    cout << ans << endl;

    return 0;
}


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

int main(){
	int N; string S; cin>>N>>S;
	map<char,int> c;
	rep(i, N) c[S[i]]++;
	long long ans = (long long)c['R'] * c['G'] * c['B'];
	rep(i, N-2)
		for(int j=i+1,k=i+2; k<N; k+=2,j++)
			if((S[i]^S[j]^S[k]) == ('R'^'G'^'B')) ans--;
	cout<< ans <<endl;
}

Measured memory_bytes: 3596
text = input()
lines = text.split("\n")

lines = list(map(lambda x: x.split(" "), lines))
n_and_m = lines[0]
n = n_and_m[0]
m = n_and_m[1]
a_and_b = []
for i in range(int(n)):
    a_and_b.append(input().split(" "))


tmp = []

a_and_b = sorted(a_and_b, key=lambda x:int(x[0]))


remain = int(m)

price = 0
for i in range(len(a_and_b)):
    for j in range(int(a_and_b[i][1])):
        remain = remain - 1
        price = price + int(a_and_b[i][0])
        if (remain == 0):
            break
    else:
        continue
    break
print(price)


Measured memory_bytes: 38564
/*
█████████───███─────────███───███─────────████████████───███████████████───████████████───████████████───█████████───────
█████████───███─────────███───███─────────████████████───███████████████───████████████───████████████───█████████───────
█████████───███─────────███───███─────────████████████───███████████████───████████████───████████████───█████████───────
███─────────███─────────███───███─────────███──────███───███───███───███───███──────███───███──────███───███─────────────
███─────────███─────────███───███─────────███──────███───███───███───███───███──────███───███──────███───███─────────────
███─────────███─────────███───███─────────███──────███───███───███───███───███──────███───███──────███───███─────────────
█████████──────███───███──────███─────────████████████───███───███───███───████████████───███──────███───█████████───────
█████████──────███───███──────███─────────████████████───███───███───███───████████████───███──────███───█████████───────
█████████──────███───███──────███─────────████████████───███───███───███───████████████───███──────███───█████████───────
███────────────███───███──────███─────────███──────███───███───███───███───███────────────███──────███─────────███───────
███────────────███───███──────███─────────███──────███───███───███───███───███────────────███──────███─────────███───────
███────────────███───███──────███─────────███──────███───███───███───███───███────────────███──────███─────────███───────
█████████─────────███─────────█████████───███──────███───███───███───███───███────────────████████████───█████████───────
█████████─────────███─────────█████████───███──────███───███───███───███───███────────────████████████───█████████───────
█████████─────────███─────────█████████───███──────███───███───███───███───███────────────████████████───█████████───────
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fori(n) for ( int i = 0; i < (n);i++)
#define forj(n) for ( int j = 0; j < (n);j++)
#define fork(n) for ( int k = 0; k < (n);k++)
#define forghj(n) for ( int ghj = 0; ghj < (n);ghj++)
#define fori1(n) for ( int i = (n)-1; i >= 0;i--)
#define all(vector) (vector).begin(),(vector).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define INF 1e9+7
#define EPS 1e-6
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma GCC optimize "-O3"

int main() {
    srand(time(NULL));
    int n;
    cin >> n;
    vector < int > a;
    a.resize(n + 1);
    vector < int > b;
    b.resize(n);
    fori(a.size()) cin >> a[i];
    fori(b.size()) cin >> b[i];
    ll ans = 0;
    ll del;
    fori(b.size()) {
        del = min(a[i], b[i]);
        ans += del;
        a[i] -= del;
        b[i] -= del;
        del = min(a[i + 1], b[i]);
        ans += del;
        a[i + 1] -= del;
        b[i] -= del;
    }
    cout << ans;
}






Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a,b,c,k;cin>>a>>b>>c>>k;
  ll num=0;
  while(a>=b) {b*=2;num++;}
  while(b>=c) {c*=2;num++;}
  print((num<=k)?"Yes":"No");
  return 0;
}

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

int main(){
   int A, B, C, D;
   cin >> A >> B >> C >> D;
    if((A+B)>(C+D)){
        cout << "Left" << endl;
    }
    if((A+B)==(C+D)){
        cout << "Balanced" << endl;
    }
    if((A+B)<(C+D)){
        cout << "Right" << endl;
    }
}

Measured memory_bytes: 3632
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int M,N,A[200010];
bool check(int md){
	for(int i=M;i>=1;i--){
		int ls=N+1-i,rs=N+2-i;
		if((A[i]>md ^ A[i-1]<=md) && A[i-1]!=0)	return A[i]>md;
		if((A[rs]>md ^ A[ls]<=md) && A[ls]!=0)	return A[rs]>md;
	}
	return A[1]>md;
}
int main(){
	scanf("%d",&M);N=2*M-1;
	for(int i=1;i<=N;i++)	scanf("%d",&A[i]);
	int L=1,R=1000010,m=0;
	while(L+1<R){
		m=(L+R)>>1;
		if(check(m))	L=m;
		else	R=m;
	}
	printf("%d\n",R);
	return 0;
}

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

using namespace std;
typedef long long ll;

class TaskC {
public:
	void solve(std::istream& in, std::ostream& out) {
        int n;
        in >> n;
        if (n < 4) {
            out << 0;
            return;
        }
        ll a[n];
        for (int i = 0; i < n; ++i) {
            in >> a[i];
        }
        sort(a, a+n);
        int b; int c;
        ll side[2] = {0, 0};
        int nside = 0;
        int k = n -1;
        while(k > 0) {
            if (nside == 2)
                break;
            if (a[k-1] == a[k]) {
                side[nside] = a[k];
                nside++;
                k -= 2;
            }
            else
                k--;
        }
        if (nside == 2) {
            out << side[0]*side[1];
        }
        else
            out << 0;


	}
};


int main() {
       ios_base::sync_with_stdio(0); cin.tie(false); cout.tie(false);
	TaskC solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >>n;
    long long a[n],ans=0;
    for(int i=0;i<n;i++)cin >>a[i];
    for(int i=0;i<n-1;i++){
        int sa = a[i+1]-a[i];
        if(sa<0){
            ans-=sa;
            a[i+1]-=sa;
        }
    }
    cout <<ans<<endl;
    return 0;
}

Measured memory_bytes: 5176
N, M = map(int, input().split())
lst_X = sorted(list(map(int, input().split())))

if N>=M:
    print(0)
else:
    lst_diff = sorted([lst_X[i+1]-lst_X[i] for i in range(M-1)])[:M-N]
    print(sum(lst_diff))



Measured memory_bytes: 13968
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;
using namespace std;
int main(){
    int n;
    
    while(true){
        cin>>n;
        if(n==0)break;
        string s;
        int ans=0;
        bool l=true,r=true;
        bool t=false;
        
        rep(i,n){
            cin>>s;
            if(s[0]=='l'){
                if(s[1]=='u'){
                    l=false;
                }else{
                    l=true;
                }
            }else if(s[0]=='r'){
                if(s[1]=='u'){
                    r=false;
                }else{
                    r=true;
                }
            }
            //cout<<l<<r<<endl;
            if(l==t&&r==t){
                t=!t;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    
    
return 0;
}



Measured memory_bytes: 3168
import sys
input = sys.stdin.readline

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n, m = map(int, input().split())

    print(combinations_count(n+m, 2) - n * m)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
c = [[int(x) for x in input().split()] for _ in range(3)]
s = True
for i in range(2):
    for j in range(i+1, 3):
        if c[0][j] - c[0][i] == c[1][j] - c[1][i] == c[2][j] - c[2][i]:
            continue
        else:
            s = False
            break
for i in range(2):
    for j in range(i+1, 3):
        if c[j][0] - c[i][0] == c[j][1] - c[i][1] == c[j][2] - c[i][2]:
            continue
        else:
            s = False
            break
print("Yes") if s else print("No")

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

using namespace std;

#define REP(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << "\t"; } cout << "\n";

template <typename T>
using V = vector<T>;

typedef long double ld;


int N, M;
vector<vector<pair<int, int>>> conds;

const int64_t MOD = 1e9+7;

V<V<V<int>>> DP(305, V<V<int>>(305, V<int>(305, -1)));

int ways(int r, int b, int g) {
	if (DP[r][b][g] != -1)
		return DP[r][b][g];
	int i = max(r, g);
	i = max(i, b);
	++i;
	bool ok = 1;
	for (auto& cond : conds[i-1]) {
		int l, c;
		tie(l, c) = cond;
		int cc = 0;
		if (r >= l)
			++cc;
		if (b >= l)
			++cc;
		if (g >= l)
			++cc;
		if (c != cc) {
			ok = 0;
			break;
		}
	}
	if (!ok)
		return DP[r][b][g] = 0;
	if (i == N+1)
		return DP[r][b][g] = 1;
	int64_t ans = ways(i, b, g);
	ans %= MOD;
	ans += ways(r, i, g);
	ans %= MOD;
	ans += ways(r, b, i);
	ans %= MOD;
	return DP[r][b][g] = ans;

}


int main() {
	cin >> N >> M;
	conds.resize(N+1);
	REP(i, M) {
		int l, r, x;
		cin >> l >> r >> x;
		conds[r].emplace_back(l, x);
	}

	cout << ways(0, 0, 0) << endl;
}

Measured memory_bytes: 114816
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    const MAX: usize = 100001;

    let mut is_prime = [true;MAX];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..MAX {
        if !is_prime[i] { continue; }
        let mut m = 2;
        while i * m < MAX {
            is_prime[i * m] = false;
            m += 1;
        }
    }

    let mut is_likenum = [false;MAX];
    for i in 0..MAX {
        if i % 2 == 1 && is_prime[i] && is_prime[(i+1)/2] {
            is_likenum[i] = true;
        }
    }

    let mut csum = [0;MAX + 1];
    for i in 0..MAX {
        csum[i+1] = csum[i] + (if is_likenum[i] { 1 } else { 0 })
    }

    let q: u32 = read();
    let lr: Vec<(usize, usize)> = (0..q).map(|_| (read(), read())).collect();

    for (l, r) in lr {
        println!("{}", csum[r+1] - csum[l]);
    }
}


Measured memory_bytes: 7292
n=int(input())
c=1
t=[0]*(n+1)
x=[0]*(n+1)
y=[0]*(n+1)
while c<n+1:
    a,b,d=(int(x) for x in input().split())
    t[c]=a
    x[c]=b
    y[c]=d
    c=c+1
c=1
kotae=0
while c<n+1:
    time=t[c]-t[c-1]
    kyori=x[c]-x[c-1]+y[c]-y[c-1]
    if time>=kyori:
        if time%2==kyori%2:
            kotae=1
        else:
            kotae=2
            break
    else:
        kotae=2
        break
    c=c+1
if kotae==1:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 11636
import math
n = int(input())

def first_last(n):return n//(10**int(math.log10(n))), n%10
data = []
for i in range(9):data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])

for i in range(1, n+1):
    first, last = first_last(i)
    if(first!=0 and last!=0):data[first-1][last-1] += 1

ans = 0
for i in range(9):
    for j in range(9):
        ans += data[i][j] * data[j][i]
print(ans)

Measured memory_bytes: 41196
#include<stdio.h>

int mini(int a,int b){
  if(a>b) return b;
  return a;
}

int max(int a,int b){
  if(a>b) return a;
  return b;
}

int main(void){
  int a,b,c,d,start,end;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  start=max(a,c);
  end=mini(b,d);
  printf("%d\n",max(end-start,0));
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N], b[N];
vector<int> g[N]; 
int tot = -1, dfn[N], fa[N], dep[N], sz[N], son[N], top[N];
void pre(int u) {
  sz[u] = 1;
  for (auto v : g[u]) {
    if (v ^ fa[u]) {
      dep[v] = dep[u] + 1;
      fa[v] = u;
      pre(v);
      sz[u] += sz[v];
      if (sz[son[u]] < sz[v]) {
        son[u] = v;
      }
    }
  }
}
void dfs(int u) {
  dfn[u] = ++tot;
  if (son[u]) {
    top[son[u]] = top[u];
    dfs(son[u]);
  }
  for (auto v : g[u]) {
    if ((v ^ fa[u]) && (v ^ son[u])) {
      top[v] = v;
      dfs(v);
    }
  }
}
struct Data {
  int val, cnt, pos;
  inline void operator += (const Data &rhs) {
    val ^= rhs.val;
    cnt += rhs.cnt;
  }
  inline Data operator + (const Data &rhs) {
    if (cnt < rhs.cnt) {
      return *this;
    } else {
      return rhs;
    }
  }
}; 
struct node {
  Data info, tag;
} t[N << 2];
void build(int p, int l, int r) {
  t[p].info.pos = l;
  if (l ^ r) {
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
  }
}
inline void pushup(int p) {
  t[p].info = t[p << 1].info + t[p << 1 | 1].info;
}
inline void tag(int p, Data add) {
  t[p].info += add;
  t[p].tag += add;
}
inline void pushdown(int p) {
  if (t[p].tag.cnt || t[p].tag.val) {
    tag(p << 1, t[p].tag);
    tag(p << 1 | 1, t[p].tag);
    t[p].tag = (Data) {0, 0};
  }
}
void modify(int p, int l, int r, int L, int R, Data add) {
  if (l >= L && r <= R) {
    tag(p, add);
    return;
  }
  pushdown(p);
  int mid = l + r >> 1;
  if (mid >= L) {
    modify(p << 1, l, mid, L, R, add);
  } 
  if (mid < R) {
    modify(p << 1 | 1, mid + 1, r, L, R, add);
  }
  pushup(p);
}
inline void modify(int u, int v, Data add) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) {
      swap(u, v);
    }
    modify(1, 1, tot, dfn[top[u]], dfn[u], add);
    u = fa[top[u]];
  }
  if (u ^ v) {
    if (dep[u] > dep[v]) {
      swap(u, v);
    }
    modify(1, 1, tot, dfn[u] + 1, dfn[v], add);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  pre(1);
  top[1] = 1;
  dfs(1);
  build(1, 1, tot);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &a[i], &b[i]);
    modify(a[i], b[i], (Data) {i, 1});
  }
  for (int i = 1; i < n; ++i) {
    int cnt = t[1].info.cnt;
    int idx = t[1].info.val;
    int pos = t[1].info.pos;
    if (cnt ^ 1) {
      puts("NO");
      return 0;
    }
    modify(1, 1, tot, pos, pos, (Data) {0, 0x3f3f3f3f});
    modify(a[idx], b[idx], (Data) {idx, -1});
  }
  puts("YES");
  return 0;
}

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

int const N=21+5, M=(1<<21)+5, OO = 0x3f3f3f3f, MOD=1e9+7;

int n;
bool grid[N][N];

long long mem[N][M];
long long solve(int i, int mask)
{
    if(mask == (1<<n)-1)
        return 1;
    if(mem[i][mask]!=-1)
        return mem[i][mask];
    long long ret=0;
    for(int j=0; j<n; j++)
        if(grid[i][j] && !((mask>>j)&1))
            ret=(ret+solve(i+1,mask|(1<<j)))%MOD;
    return mem[i][mask]=ret;
}



int main()
{
//    freopen("input.txt","rt",stdin);
//    freopen("output.txt","wt",stdout);
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d",grid[i]+j);
    memset(mem, -1, sizeof mem);
    printf("%lld\n",solve(0,0));




}


Measured memory_bytes: 426368
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	map<int,int>m;
	m[a]++;
	m[b]++;
	m[c]++;
	if(m[5]==2 && m[7]==1)
	cout<<"YES";
	else
	cout<<"NO";
	return 0;
}


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

using namespace std;

typedef int INT;
#define int long long

int a[100000];
INT main(){
    int n;
    while(scanf("%lld",&n) , n){
        for(int i=0;i<n;i++)scanf("%lld",a+i);
        sort(a,a+n);
        int ans=0;
        for(int i=0;i<n;i++){
            ans += a[i]*(n-i-1);
            //printf("%d ",ans);
        }
        printf("%lld\n",ans);
    }
}

Measured memory_bytes: 1260
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
#define vecmin(A) *min_element(A.begin(),A.end())
#define vecmax(A) *max_element(A.begin(),A.end())
typedef long long ll;

int main(){
  int a,b,h;
  cin >> a >> b >>h;
  cout << (a+b)*h/2 << endl;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)

function main()
	n,k = map(parseInt, split(readline()))
	h = Array{Int}(n)
	for i in 1:n
		h[i] = parseInt(readline())
	end
	h = sort(h)
	dif = 1000000000
	for i in k:n
		dif = min(h[i]-h[i-k+1], dif)
	end
	print(dif)
end

main()

Measured memory_bytes: 147204
const processData = (lines) => {
    let acc = 0
    const n = +lines[acc]
    const map = {
        'AC': 0,
        'WA': 0,
        'TLE': 0,
        'RE': 0
    }
    const iter = ['AC', 'WA', 'TLE', 'RE']
    acc++
    for (let i=0; i<n; i++) {
        const t = lines[acc]
        map[t]++
        acc++
    }

    for (const c of iter) {
        console.log(`${c} x ${map[c]}`)
    }
}

let i = ''
process.stdin.on('data', c => i += c)
process.stdin.on('end', () => {
    const {EOL} = require('os')
    const lines = i.split(EOL) /*your input text, split by lines*/
    processData(lines)
})


Measured memory_bytes: 39080
#include<bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define nl cout<<"\n"
#define endl '\n'
#define pb push_back
#define se second
#define fi first
#define int long long 
#define pi pair<int,int>
#define vpi vector<pi>
#define vvpi vector<vpi>
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define For(i,n) for(int i=0;i<n;i++)
#define Forn(i,a,n) for(int i=a;i<n;i++)
#define pie =3.14159265358979323846264338327950;
const int mod= 1e9+7;


void solve(){
	fio;
	int n;
	cin>>n;
	int ar[n];
	For(i,n) cin>>ar[i];
	int suf[n];
	suf[n-1]=ar[n-1];
	for(int i=n-2;i>=0;i--){
		suf[i]= suf[i+1]+ar[i];
		suf[i]%=mod;
	}
	int ans=0;
	for(int i=0;i<n-1;i++){
		ans+= ar[i]*suf[i+1];
		ans%=mod;
	}
	cout<<ans<<endl;
}

int32_t main(){
	fio;
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int t=1;
	//cin>>t;
	for(int i=1;i<=t;i++){ 
		//cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}


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

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vb vector<bool>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vs vector<string>
#define pull pair<ull, ull>
#define m_p make_pair
#define debug(x) cout << #x << " " << x << endl
#define printArr(a, start, end)for(int i=start ; i<end ; ++i)cout << a[i] << " ";
#define readArr(a, start, end)for(int i=start ; i<end ; ++i)cin >> a[i];
#define read2D(mat, n, m)for(int i=0 ; i<n ; ++i)for(int j=0 ; j<m ; ++j)cin >> mat[i][j];

const long double PI = 3.141592653589793238462643383279502884197169399;

// Find Set LSB = (x&(-x)), isPowerOfTwo = (x & (x-1))

void solve(){
	int n;
	cin >> n;
	
	vi a(n);
	int X=0;
	for(int& x : a){
		cin >> x;
		X ^= x;
	}
	
	for(int& x : a)cout << (X^x) << " ";
}

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


Measured memory_bytes: 3988
#include<queue>
#include<string>
#include<utility>
#include<iostream>
using namespace std;

int main() {
  queue< pair<string,int> > Q;
  pair<string,int> temp;
  int n, qtm, i, time=0;
  cin >> n >> qtm;
  for(; n > 0; n--) {
    cin >> temp.first >> temp.second;
    Q.push(temp);
  }
  while(! Q.empty()) {
    i = Q.front().second - qtm;
    if (i <= 0) {
      time += qtm + i;
      cout << Q.front().first << " " << time << endl;
      Q.pop();
    } else {
      time += qtm;
      temp.first = Q.front().first;
      temp.second = i;
      Q.pop();
      Q.push(temp);
    }
  }
  return 0;
}

Measured memory_bytes: 4404
n = gets.to_i
a = gets.split.map(&:to_i)

st = Array.new(n).map{Array.new(2)}
for i in 0..(n-1)
  st[i][0] = a[i]
  st[i][1] = i+1
end

st.sort!{|a,b| a[0] <=> b[0]}

for i in 0..(n-1)
  print "#{st[i][1]} "
end
puts ""

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

int main(){
    int n,k;cin>>n>>k;
    vector<int> a(n);
    vector<bool> dp(k+1);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int stones=1;stones<=k;stones++){
        for(int j=0;j<n;j++){
            if(stones-a[j]>=0 && dp[stones-a[j]]==false){
                dp[stones]=true;
                break;
            }
        }
    }
    if(dp[k]){
        cout<<"First";
    }
    else{
        cout<<"Second";
    }
}

Measured memory_bytes: 256
from collections import defaultdict

memo = dict()

n,m = list(map(int, input().split()))

for i in range(m):
    p, s = input().split()
    if p not in memo:
        memo[p] = [0, False]

    if memo[p][1]:
        continue

    v = memo[p]
    if s == 'AC':
        memo[p] = [v[0], True]
    else:
        memo[p] = [v[0]+1, False]        

ac, wa = 0, 0
for _,v in memo.items():
    w, a = v
    if a:
        ac += 1
        wa += w

print(ac, wa)

Measured memory_bytes: 25664
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int s;
    cin >> s;
    
    set<int> st;
    int cnt = 1;
    while(1)
    {
        if (st.find(s) != st.end()) break;
        st.insert(s);
        if (s%2==0) s /= 2;
        else s = 3*s + 1;
        ++cnt;
    }
    
    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
h = [int(i) for i in input().split()]

ans = 0

if h.count(0) == 0:
  ans += min(h)
  h = list(map(lambda x:x-min(h) ,h))

while h.count(0) != len(h):

  pos = 0
  for i in range(len(h)):
    if h[i] != 0:
      pos = i
      break

  pos2 = len(h)
  for j in range(pos, len(h)):
    if h[j] == 0:
      pos2 = j
      break

  ans += min(h[pos:pos2])
  h[pos: pos2] = list(map(lambda x: x - min(h[pos:pos2]), h[pos:pos2]))
  
print(ans)
  


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

const int MAXN = 200010;

vector<int> vec1[MAXN], vec2[MAXN];
int f[MAXN], vis[MAXN], cnt[MAXN];
int ans[MAXN], Stack[MAXN], tp;

bool cmp (int a, int b) {
    return f[a] < f[b];
}

void dfs (int id, int fa, int x) {
    f[id] = x;
    vis[id] = 1;
    for (int i = 0; i < vec1[id].size(); i++) {
        if (vis[vec1[id][i]])   continue;
        dfs (vec1[id][i], id, x);
    }
}

void ds (int id, int fa) {
    Stack[++tp] = id;
    vis[id] = 1;
    for (int i = 0; i < vec2[id].size(); i++) {
        if (vis[vec2[id][i]])   continue;
        ds (vec2[id][i], id);
    }
}


int main () {
    int n, K, L;
    scanf ("%d%d%d", &n, &K, &L);
    for (int i = 1; i <= K; i++) {
        int x, y;
        scanf ("%d%d", &x, &y);
        vec1[x].push_back (y);
        vec1[y].push_back (x);
    }
    for (int i = 1; i <= L; i++) {
        int x, y;
        scanf ("%d%d", &x, &y);
        vec2[x].push_back (y);
        vec2[y].push_back (x);
    }
    for (int i = 1; i <= n; i++)    f[i] = i;
    memset (vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++) {
        if (f[i] == i) {
            dfs (i, -1, i);
        }
    }
    memset (vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            tp = 0;
            ds (i, -1);
            sort (Stack + 1, Stack + tp + 1, cmp);
            int pre = 1;
            for (int j = 2; j <= tp; j++) {
                if (f[Stack[pre]] != f[Stack[j]]) {
                    int now = j - pre;
                    for ( ; pre < j; pre++) {
                        ans[Stack[pre]] = now;
                    }
                }
            }
            int now = tp - pre + 1;
            for ( ; pre <= tp; pre++) {
                ans[Stack[pre]] = now;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i < n)  printf ("%d ", ans[i]);
        else    printf ("%d\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 19584
import java.util.Scanner;

 class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int k = input.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i=0;i<n;++i){
            arr[i]=input.nextInt();
        }
        if(n==0 || n==1)
            System.out.println("0");
        else {
            dp[1]=Math.abs(arr[1]-arr[0]);
            for (int i = 2; i < n; ++i) {
                int ans = Integer.MAX_VALUE;
                int j = i-k;
                if(j<0)j=0;
                for(int l=j;l<i;++l){
                    int val = dp[l]+Math.abs(arr[i]-arr[l]);
                    ans = Math.min(ans,val);
                }
                dp[i]=ans;
            }
        }
        System.out.println(dp[n-1]);

    }
}


Measured memory_bytes: 50160
#include <cstdio>
#include <vector>
#include <algorithm>

typedef struct{
    long long int price;
    long long int number;
}shop;

bool operator<(const shop& left, const shop& right){
    return left.price < right.price;
}

int main(){
    int i,n,m;
    std::vector<shop> data;
    shop a;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%lld %lld",&(a.price),&(a.number));
        data.push_back(a);
    }
    std::sort(data.begin(),data.end());
    long long int ret=0;
    for(i=0;i<n;i++){
        a = data[i];
        if(a.number>=m){
            ret += a.price * m;
            break;
        }else{
            ret += a.price * a.number;
            m -= a.number;
        }
    }
    printf("%lld\n",ret);
    return 0;
}


Measured memory_bytes: 2420
#include <stdio.h>
int main(void){
    int a,b,i;
    char op;
    
    for(i=1;i>0;i++){
        scanf("%d %c %d",&a,&op,&b);
        if(op=='+'){
            printf("%d\n",a+b);
        }        
        else if(op=='-'){
            printf("%d\n",a-b);
        }        
        else if(op=='*'){
            printf("%d\n",a*b);
        }        
        else if(op=='/'){
            printf("%d\n",a/b);
        }
        else if(op=='?'){
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 2100
#include <iostream>
#include <algorithm>
#include <string>
typedef long long ll;
using namespace std;





int main(){
    int r,d,x;
    cin >> r >> d >>x;
    int ans = r*x-d;
    cout << ans << endl;
    for(int i=0;i<9;i++){
        ans = r*ans-d;
        cout << ans << endl;
    }
}


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

void fnInput(vector<string>& rvsStr)
{
  int nStrSiz;
  cin >> nStrSiz;
  rvsStr.resize(nStrSiz);

  for (string& rsStr : rvsStr)
    cin >> rsStr;
}
  
llong fnAnagramCnt(const vector<string>& cnrvsStr)
{
  vector<string> vsSortStr(cnrvsStr);

  for (string& rsSortStr : vsSortStr)
    sort(begin(rsSortStr), end(rsSortStr));

  llong nAnagramCnt = 0;
  map<string, int> mpSortStr;

  for (string sSortStr : vsSortStr)
  {
    nAnagramCnt += mpSortStr[ sSortStr ];
    mpSortStr[ sSortStr ]++;
  }
  return nAnagramCnt;
}
  
int main()
{
  vector<string> vsStr;

  fnInput(vsStr);
  cout << fnAnagramCnt(vsStr) << endl;

  return 0;
}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;
ull max(ull a, ull b) 
{
	return (a>b)?a:b;
}
ull knapsack(ull n,ull W,ull weight[], ull value[])
{
	ull arr[n+1][W+1];
	for(ull i = 0; i <= n; ++i)
	{
		for(ull w = 0; w <= W; ++w)
		{
			if(i==0 || w==0) arr[i][w]=0;
			else if(weight[i-1]>w) arr[i][w] = arr[i-1][w];
			else	arr[i][w]=max(value[i-1]+arr[i-1][w-weight[i-1]],arr[i-1][w]);
		}
	}
	return arr[n][W];
}
int main(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);cin.tie(0);
	ull n,w;
	cin>>n>>w;
	ull weight[n], value[n];
	for (ull i = 0; i < n; ++i)
		cin>>weight[i]>>value[i];
	cout<<knapsack(n,w,weight,value);
	return 0;
}

Measured memory_bytes: 79232
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

int main(){
    ll N; cin >> N;
    cout << (N-1)*N/2;
}

Measured memory_bytes: 256
using System;

class AOJ
{

    public static void Main()
    {
        string[] s = Console.ReadLine().Split(' ');
        int [] a = new int[5];

        for (int i = 0; i < 5; i++)
        {
            a[i] = int.Parse(s[i]);
        }

        Array.Sort(a);
        Array.Reverse(a);

        for (int i = 0; i < 5; i++)
        {
            Console.Write("{0}",a[i]);
            if (i != 4)
                Console.Write(" ");
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 5792
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int n,x,m,i,t=1000,res;
  cin >> n >> x;
  res=n;
  for(i=0;i<n;i++){
    cin >> m;
    x-=m;
    t=min(t,m);
  }
  res+=x/t;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define rep(i,l,r)  for(int i=l;i<=r;i++)
#define pre(i,r,l)  for(int i=r;i>=l;i--)
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int maxn = 500005;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

int w[maxn];
int main() {
   int n = read(), k = read();
   while(k--) {
    int t = read();
    rep(i, 1, t) {
       int a = read();
       w[a] = 1;
    }
   }
   int sum  = 0;
   rep(i, 1, n) {
      if(!w[i]) sum++;
   }
   cout << sum << endl;
}


Measured memory_bytes: 3612