akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

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

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

  int sum = 0;
  FOR(i,1,K+1){
    FOR(j,1,K+1){
      FOR(k,1,K+1){
        sum += gcd(i,gcd(j,k));
      }
    }
  }

  cout << sum << endl;
}

Measured memory_bytes: 3564
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define ll long long

int main(void){
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i = 0;i < n;i++)
		cin >> v[i];
	// dp[i][j] - max value can get from array [i, j]
	vector<vector<ll> > dp(n, vector<ll>(n));
	for(int i = 0;i < n;i++){
		dp[i][i] = v[i];
	}
	for(int i = 1;i < n;i++){
		for(int j = i, k = 0;j < n;j++, k++){
			dp[k][j] = max(v[k]-dp[k+1][j], v[j]-dp[k][j-1]);
		}
	}
	cout << dp[0][n-1] << endl;
}

Measured memory_bytes: 70656
import java.math.BigDecimal;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double A = sc.nextDouble();
        double B = sc.nextDouble();
        sc.close();

        BigDecimal res = BigDecimal.valueOf(A).multiply(BigDecimal.valueOf(B));
        String val = res.toPlainString();
        int index = val.indexOf(".");
        if (index >= 0) {
            val = val.substring(0, index);
        }

        System.out.println(val);

    }
}

Measured memory_bytes: 37496
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int MaxN = 1e5;
const int Inf = 1 << 30;

int a[MaxN + 5];

int main()
{
	int n,p;
	while(~scanf("%d",&n)){
		for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
		sort(a + 1,a + 1 + n);p = 0;
		for(int i = 2;i <= n;i++) if(a[i] == a[i - 1]) p++;
		p = p + (p % 2 == 0 ? 0 : 1);
		printf("%d\n",n - p);
	}
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  int x[n];
  int a = 0;
  int b = 999999999;
  for(int i=0; i<n; i++){
    cin >> x[i];
  }
  for(int i=0; i<100; i++){
    for(int j=0; j<n; j++){
      a = a + (x[j]-i)*(x[j]-i);
    }
    if(a<b){b=a;}
    a = 0;
  }
  cout << b << endl;
}

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

const long long MOD = 1000000007;

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

    vector<int> b(n + 1, true);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        b[a] = false;
    }

    vector<long long> dp(n + 1);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= min(n, i + 2); j++) {
            if (b[j]) {
                dp[j] += dp[i];
                dp[j] %= MOD;
            }
        }
    }

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

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

typedef struct {
	char *s;
	int i;
}pair;

int compare_string(const void *a, const void *b){
	return strcmp(*(char **)b, *(char **)a);
}

int compair(const void *a, const void *b){
	pair pa = *(pair *)a, pb = *(pair *)b;
	int res = strcmp(pb.s, pa.s);
	if(res == 0){
		return pa.i - pb.i;
	}
	else{
		return res;
	}
}

int max(int a, int b){
	return a >= b ? a : b;
}

int main(){
	int N, i, j, k, l;
	scanf("%d", &N);
	char *S = (char *)malloc(sizeof(char) * (2 * N + 1));
	scanf("%s", S);
	int *T = (int *)malloc(sizeof(int) * (2 * N + 1));
	int *a = (int *)malloc(sizeof(int) * (N + 1));
	int *b = (int *)malloc(sizeof(int) * (N + 1));
	for(i = 0, j = 0, k = 0; i < 2 * N; i++){
		if(S[i] == 'a'){
			T[i] = j;
			a[j] = i;
			j++;
		}
		else{
			T[i] = k;
			b[k] = i;
			k++;
		}
	}
	a[N] = 2 * N;
	b[N] = 2 * N;
	int *left = (int *)malloc(sizeof(int) * N);
	int *right = (int *)malloc(sizeof(int) * N);
	left[0] = 0;
	for(i = 1, j = 1; i < N; i++){
		if(a[i] > b[i - 1] && b[i] > a[i - 1]){
			left[j] = i;
			right[j - 1] = i;
			j++;
		}
	}
	right[j - 1] = N;
	int K = j, prevj;
//	printf("K = %d\n", K);
	pair *p = (pair *)malloc(sizeof(pair) * K);
	for(i = 0; i < K; i++){
		l = max(a[right[i] - 1] - b[left[i]], b[right[i] - 1] - a[left[i]]) + 1;
		p[i].s = (char *)malloc(sizeof(char) * (l + 1));
		p[i].i = i;
		if(a[left[i]] < b[left[i]]){
			for(j = left[i], k = 0; j < right[i]; ){
				p[i].s[k] = 'a';
				p[i].s[k + 1] = 'b';
				k += 2;
				prevj = j;
				while(a[j] < b[prevj] && j < right[i]){
					j++;
				}
			}
			p[i].s[k] = '\0';
		}
		else{
			int d = right[i] - left[i];
			char **sub = (char **)malloc(sizeof(char *) * d);
			for(j = left[i]; j < right[i]; j++){
				sub[j - left[i]] = (char *)malloc(sizeof(char) * (2 * (right[i] - j) + 1));
				for(k = b[left[i]], l = 0; k <= a[right[i] - 1]; k++){
					if(T[k] >= j){
						sub[j - left[i]][l] = S[k];
						l++;
					}
				}
				sub[j - left[i]][l] = '\0';
//				printf("sub[%d] = %s\n", j - left[i], sub[j - left[i]]);
			}
//			printf("qsort!\n");
			qsort(sub, d, sizeof(char *), compare_string);
/*			for(j = 0; j < d; j++){
				printf("sub[%d] = %s\n", j, sub[j]);
			}
*/			for(j = 0; sub[0][j] != '\0'; j++){
				p[i].s[j] = sub[0][j];
			}
			p[i].s[j] = '\0';
		}
	}
	int ab = 0;
	for(i = K - 1; i >= 0; i--){
		if(p[i].s[0] == 'a'){
			for(j = 0; p[i].s[j] != '\0'; j++){}
			ab += j / 2;
		}
		else{
			break;
		}
	}
	qsort(p, K, sizeof(pair), compair);
/*	for(i = 0; i < K; i++){
		printf("i = %d\n", i);
		printf("(i, s) = (%d, %s))\n", p[i].i, p[i].s);
	}
*/	for(i = 0, j = -1; i < K; i++){
//		printf("\n(i, j) = (%d, %d)\n", i, j);
		if(p[i].i > j && p[i].s[0] == 'b'){
			for(k = 0; p[i].s[k] != '\0'; k++){
				printf("%c", p[i].s[k]);
			}
			j = p[i].i;
		}
	}
	for(i = 0; i < ab; i++){
		printf("ab");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 8956
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(1)
    exit()

XY.sort(key=lambda x: x[0])

PQ = {}

for i in range(N):
    x0, y0 = XY[i]
    for j in range(N):
        if i == j:
            continue
        x1, y1 = XY[j]
        p, q = x0 - x1, y0 - y1
        key = str(p) + ',' + str(q)
        if key in PQ:
            PQ[key] += 1
        else:
            PQ[key] = 1
ansL = PQ.values()
print(N - max(list(ansL)))


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


vector<vector<int> > V;

ll ami[102][9];
static const ll mod = 1000000007;

int main() {

    int H, W, K;
    cin >> H >> W >> K;

    vector<int> init;
    init.push_back(1);
    V.push_back(init);

    int cnt = 1;

    // 縦線W本のあみだくじの１列を全通り作るよ
    // ex) W = 3
    // 1 2 3
    // 1 3 2
    // 2 1 3
    while (cnt < W) {

        vector<vector<int> > temp;

        for (int i = 0; i < V.size(); i++) {
            vector<int> v = V[i];
            v.push_back(cnt+1);
            
            temp.push_back(v);
            if (v[cnt-1] != cnt) {
                continue;
            }
            else {
                swap(v[cnt], v[cnt-1]);
                temp.push_back(v);
            }
        }
        cnt++;
        V = temp;
    }
    // あみだ確認
    /*
    for (int i = 0; i < V.size(); i++) {
        for (int j = 0; j < V[i].size(); j++) {
            cout << V[i][j] << ' ';
        }
        cout << '\n';
    }
    */

    // dpで個数求めるよ
    ami[0][1] = 1;
    for (int h = 0; h < H; h++) {

        for (int w = 1; w <= W; w++) {
            if (ami[h][w] == 0)
                continue;
            for (int i = 0; i < V.size(); i++) {
                ami[h+1][V[i][w-1]] += ami[h][w];
                ami[h+1][V[i][w-1]] %= mod;
            }
        }
    }

    cout << ami[H][K] << '\n';

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  string s, t = "AKIHABARA";
  cin >> s;
  if (s.size() > 9) {
    NO();
    return 0;
  }
  ll j = 0;
  ll m;
  for (ll i = 0; i < s.size() && j < 9; i++) {
    if (s[i] == t[j]) {
      j++;
      m = i;
    }
    else if (t[j] == 'A') {
      i--;
      j++;
      m = i - 1;
    }
    else {
      NO();
      return 0;
    }
  }
  if (j <= 7) NO();
  else {
    for (ll i = m + 1; i < s.size(); i++) {
      if (s[i] != 'A') {
        NO();
        return 0;
      }
    }
    YES();
  }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> a = new ArrayList<>();
        long aTotal = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextInt();
            a.add(x);
            aTotal += x;
        }
        List<Long> b = new ArrayList<>();
        long bTotal = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextInt();
            b.add(x);
            bTotal += x;
        }

        if (aTotal < bTotal) {
            System.out.println(-1);
            return;
        }
        List<Long> sub = new ArrayList<>();
        long cnt = 0;
        long minusTotal = 0;
        for (int i = 0; i < n; i++) {
            long s = a.get(i) - b.get(i);
            if (s < 0) {
                cnt++;
                minusTotal += s;
            }
            sub.add(s);
        }
        if (cnt == 0) {
            System.out.println(0);
            return;
        }
        Collections.sort(sub,Comparator.reverseOrder());

        boolean ok = false;
        for (long i : sub) {
            if (i < 0) {
                continue;
            }
            minusTotal += i;
            cnt++;
            if (minusTotal >= 0) {
                ok = true;
                break;
            }
        }
        if (!ok) {
            System.out.println(-1);
            return;
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 96532
#include <bits/stdc++.h>
#include <queue>
#include <math.h>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const ll INF = 1010101010;
int dp[101010];

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  rep(i,n) dp[i] = INF;
  dp[0] = 0;
  //rep(i,n) cout << h[i] << endl;
  rep(i,n){
    if(i==0) continue;
    for(int j=1;j<=k;j++){
      if(i-j>=0) dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
    }
  }
  //rep(i,n-1) cout << dp[i] << endl;
  cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long

using namespace std;
const int N=3e5+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int n,a[N],bt[N],b[N],c1[N],c2[N];
void add(int x,int y){while(x<=n) bt[x]+=y,x+=x&(-x);}
int gsm(int x){int an=0;while(x) an+=bt[x],x-=x&(-x);return an;}
void wa(){puts("No");exit(0);}
void ac(){puts("Yes");}

int main()
{
////
    n=rd();
    for(int i=1;i<=n;++i) a[i]=rd();
    for(int i=1;i<=n;++i)
	if((a[i]^i)&1) wa();
    for(int o=0;o<=1;++o)
    {
	memset(bt,0,sizeof(bt));
	for(int i=1+((o^1)&1);i<=n;i+=2)
	{
	    b[i]+=(bool)(gsm(n)-gsm(a[i]));
	    add(a[i],1);
	}
	memset(bt,0,sizeof(bt));
	for(int i=n-((o^n)&1);i>=1;i-=2)
	{
	    b[i]+=(bool)gsm(a[i]);
	    add(a[i],1);
	    if(b[i]==2) wa();
	}
    }
    for(int i=1;i<=n;i+=2)
	if(i<a[i]) ++c1[i],--c1[a[i]+1];
    for(int i=2;i<=n;i+=2)
	if(i<a[i]) ++c2[i],--c2[a[i]+1];
    for(int i=1;i<=n;++i)
    {
	c1[i]+=c1[i-1],c2[i]+=c2[i-1];
	if(c1[i]&&c2[i]) wa();
    }
    ac();
    return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
ll MOD=1000000007;
int main() {
    ll n,m;
  cin>>n>>m;
  vector<ll> broken(n+1);
  rep(i,m){
    ll a;
     cin>>a;
    broken[a]++;
 }
  vector<ll> dp(n+1);
    dp[1]=1; dp[2]=2;
if(broken[1]!=0){
  dp[1]=0;
  dp[2]=1;
}
if(broken[2]!=0) dp[2]=0;
  rep2(i,3,n+1){
   if(broken[i]==0) dp[i]=dp[i-1]%MOD+dp[i-2]%MOD;
else dp[i]=0;
    }
    cout<<dp[n]%MOD<<endl;
  return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mymalloc(p,n) {p = malloc((n)*sizeof(*p));if ((p)==NULL) {printf("not enough memory?\n"); exit(1);};}
#define INT_MAX 50000

void swap(int *i,int *j){
	int tmp;
	tmp=*i;
	*i=*j;
	*j=tmp;
}

int partition(int *A,int p,int r){
	int i,j,x;
	x=A[r];
	i=p;
	for(j=p;j<r;j++){
		if(A[j]<=x){
			swap(&A[i],&A[j]);
			i++;
		}
	}
	swap(&A[i],&A[r]);
	return i;
}

void quickSort(int *A, int p, int r){
	int q;
	if(p<r){
		q=partition(A,p,r);
		quickSort(A,p,q-1);
		quickSort(A,q+1,r);
	}
}


int min(int a, int b){
	if(a<b){
		return a;
	}else{
		return b;
	}
}

int fchange(int n,int m,int *A,int *change,int *memo){
	int i,j,num;
	num=INT_MAX;
	if(n==0){
		return 0;
	}
	i=0;
	while(A[i]<=n && i<m){
		j=A[i];
		if(memo[n-j]==0){
			change[n-j]=fchange(n-j,m,A,change,memo);
			memo[n-j]=1;
		}
		if(change[n-j]!=-1){
			num=min(num,1+change[n-j]);
		}
		i++;
	}
	if(i==0){
		return -1;
	}
	return num;
}

main(){
	int i,k,n,m;
	int *A,*C,*M;
	scanf("%d %d",&n,&m);
	mymalloc(C,n);
	mymalloc(M,n);
	mymalloc(A,m);
	for(i=0;i<n;i++){
		M[i]=0;
	}
	for(i=0;i<m;i++){
		scanf(" %d",&k);
		A[i]=k;
	}
	quickSort(A,0,m-1);
	printf("%d\n",fchange(n,m,A,C,M));
	return 0;
}

Measured memory_bytes: 5676
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;

/*
*/

ll n,m,k[11],s[11][11],p[11],ans=0;

void init(){
	cin>>n>>m;
	rep(i,m){
		cin>>k[i];
		rep(j,k[i]){
			cin>>s[i][j];
			s[i][j]--;
		}
	}
	rep(i,m)cin>>p[i];
}

int main(void){
	init();
	rep(st,1<<n){
		bool ok=true;
		rep(i,m){
			ll cnt=0;
			rep(j,k[i]){
				if(1 & st>>s[i][j])cnt++;
			};
			if(p[i]%2 != cnt%2)ok=false;
		}
		if(ok)ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def is_m(a):
    if 1 <= a <= 12:
        return 1
    return 0


def main():
    S = input()

    A = int(S[:2])
    B = int(S[2:])

    a = is_m(A)
    b = is_m(B)

    if a and b:
        print("AMBIGUOUS")
    elif not a and not b:
        print("NA")
    elif a:
        print("MMYY")
    else:
        print("YYMM")


if __name__ == '__main__':
    main()


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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For (i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, auto init = 0) {
    return std::accumulate(all(vec), T(init));
}
// -------------------------------------------------------------------

using E = pair<int, int>;
constexpr int modmod = 998244353;

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;

    int kueruc = min(A + B, C);
    if (C > A + B) kueruc++;
    print(kueruc + B);

    return 0;
}


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

int n, mx;
string s;
map<string, int> mp;
int main() {
	cin >> n;
	while(n--) {
		cin >> s;
		mp[s]++;
		mx = max(mx, mp[s]);
	}
	for(auto x:mp) {
		if(x.second==mx) printf("%s\n", x.first.c_str());
	}
	return 0;
}

Measured memory_bytes: 25216
#include "bits/stdc++.h"

//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

#define int long long
#define ll long long

ll INF = (1LL << 60);
int mod = 998244353;
using P = pair<int, int>;

signed main() {
	int n, x, m; cin >> n >> x >> m;
	vector<int>a(m);
	for (int i = 0; i < m; i++) {
		a[i] = (i*i) % m;
	}
	vector<vector<int>>next(45, vector<int>(m)), sum(45, vector<int>(m));
	for (int i = 0; i < m; i++) {
		next[0][i] = a[i];
	}
	for (int i = 1; i < 45; i++) {
		for (int j = 0; j < m; j++) {
			next[i][j] = next[i - 1][next[i - 1][j]];
		}
	}
	for (int i = 0; i < m; i++) {
		sum[0][i] = i;
	}
	for (int i = 1; i < 45; i++) {
		for (int j = 0; j < m; j++) {
			sum[i][j] = sum[i - 1][next[i - 1][j]] + sum[i - 1][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < 45; i++) {
		if (n >> i & 1) {
			ans += sum[i][x];
			x = next[i][x];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 75368
#include <bits/stdc++.h>
#define rt "\n"
#define sp " "
#define test(n) cout << "test" << n << endl;
#define fixsp(n) fixed << setprecision(n)
#define defsp(n) defaultfloat << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define iikae auto&
#define vector3D(K, N, M, DP) vector<vector<vector<ll>>> DP(K, vector<vector<ll>>(N, vector<ll>(M)));
#define vector4D(K, N, M, O, DP) vector<vector<vector<vector<ll>>>> DP(K, vector<vector<vector<ll>>>(N, vector<vector<ll>>(M, vector<ll>(O))));
#define zenbu(a) a.begin(), a.end()
#define rzenbu(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;/* 最大公約数 */template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}/* UnionFind */template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};/* コンビネーション */template<typename T> ll combpm(T N_, T C_) {const int NUM_=400001;static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];if (fact[0]==0) {inv[1]=fact[0]=factr[0]=1;for (int i=2;i<=NUM_;++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%MOD, factr[i]=factr[i-1]*inv[i]%MOD;}if(C_<0 || C_>N_) return 0;return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;}
/* ここからコード開始 */

int main(){
  kyopro;
  ll tate, yoko, kaisuu;
  cin >> tate >> yoko >> kaisuu;
  ll initx, inity;
  cin >> inity >> initx;
  string takahashi, aoki;
  cin >> takahashi >> aoki;
  ll l{1}, r{yoko}, u{1}, d{tate};
  ll lm{1}, rm{yoko}, um{1}, dm{tate};
  rem(i, kaisuu-1, -1){
    if(takahashi[i] == 'L') l++;
    else if(takahashi[i] == 'R') r--;
    else if(takahashi[i] == 'U') u++;
    else if(takahashi[i] == 'D') d--;
    // cout << l << r << u << d << rt;
    if(i == 0) break;
    if(aoki[i-1] == 'R' && l > 1 && l <= r) l--;
    else if(aoki[i-1] == 'L' && r < yoko && l <= r) r++;
    else if(aoki[i-1] == 'D' && u > 1 && u <= d) u--;
    else if(aoki[i-1] == 'U' && d < tate && u <= d) d++;
  }
  if(l <= initx && initx <= r && u <= inity && inity <= d) cout << "YES" << rt;
  else cout << "NO" << rt;
}

Measured memory_bytes: 920
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define int long long
using P = pair<int,int>;

signed main(){
  string s;
  cin >> s;
  bool a = false;
  bool b = false;
  bool c = false;
  rep(i,3){
    if(s[i] == 'a') a = true;
    if(s[i] == 'b') b = true;
    if(s[i] == 'c') c = true;
  }
  if(a && b && c) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a%2==0&&b%2==0||a%2==1&&b%2==1)
	{
		if(a>b)
		swap(a,b);
		int k=a;
		k+=(b-a)/2;
		printf("%d",k);
	}
	else
	{
		printf("IMPOSSIBLE");
	}
	
}

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

#define FOR(i,k,n)  for(int i=(k);i<(int)(n);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(x)  begin(x),end(x)

using namespace std;

int64_t f2(int64_t x) {
  if ((x % 2) == 1) return 1;
  return 2 * f2(x / 2);
}

int64_t grundy(vector<string> &v, int64_t depth, int i = 0) {
  if (v.empty()) {
    return f2(depth - i + 1);
  } else if (v.size() == 1 && i >= v.front().size()) {
    return 0;
  }
  vector<string> zero, one;
  for (const auto &s : v) {
    if (s[i] == '0') zero.push_back(s);
    else one.push_back(s);
  }
  return grundy(zero, depth, i+1) ^ grundy(one, depth, i+1);
}

int main() {
  int n;
  int64_t l;
  cin>>n>>l;
  vector<string> t(n);
  REP(i,n) cin>>t[i];
  sort(ALL(t));
  if (grundy(t, l) == 0) {
    cout << "Bob" << endl;
  } else {
    cout << "Alice" << endl;
  }
  return 0;
}


Measured memory_bytes: 16000
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

template<typename T>
struct Coordinate_Compression_2D {
  int N;
  vector<T> x,y;
  vector<T> x1,x2,y1,y2;

  Coordinate_Compression_2D() = delete;
  Coordinate_Compression_2D(T *x1_,T *x2_,T *y1_,T *y2_,int N_) {
    init(x1_,x2_,y1_,y2_,N_);
  }
  Coordinate_Compression_2D(const vector<T> &x1_,const vector<T> &x2_,const vector<T> y1_,const vector<T> y2_) {
    if (x1_.size() != x2_.size() || x2_.size() != y1_.size() || y1_.size() != y2_.size()) {
      std::cerr << "warning" << std::endl;
      return;
    }
    init(x1_.data(),x2_.data(),y1_.data(),y2_.data(),x1_.size());
  }

  void init (const T *x1_,const T *x2_,const T *y1_,const T *y2_,const int N_) {//[x1,x2) [y1,y2)
    x.clear();y.clear();
    x1.clear(),x2.clear(),y1.clear(),y2.clear();

    N = N_;

    rep(i,N) {
      x1.push_back(x1_[i]);
      x2.push_back(x2_[i]);
      y1.push_back(y1_[i]);
      y2.push_back(y2_[i]);
    }

    rep (i,N) {
      x.push_back(x1[i]);x.push_back(x2[i]);
      y.push_back(y1[i]);y.push_back(y2[i]);
    }

    sort(x.begin(),x.end());
    sort(y.begin(),y.end());

    x.erase(unique(x.begin(),x.end()),x.end());
    y.erase(unique(y.begin(),y.end()),y.end());

  }

  T imos_area () {

    vector<vector<T>> c(y.size(),vector<T>(x.size(),(T)0));

    rep (i,N) {
      T ix1 = lower_bound(x.begin(),x.end(),x1[i]) - x.begin();
      T ix2 = lower_bound(x.begin(),x.end(),x2[i]) - x.begin();
      T iy1 = lower_bound(y.begin(),y.end(),y1[i]) - y.begin();
      T iy2 = lower_bound(y.begin(),y.end(),y2[i]) - y.begin();

      c[iy1][ix1]++;
      c[iy1][ix2]--;
      c[iy2][ix1]--;
      c[iy2][ix2]++;
    }

    rep (i,y.size()) {
      rep (j,(int)x.size() - 1) {
        c[i][j + 1] += c[i][j];
      }
    }

    rep (i,(int)y.size() - 1) {
      rep (j,x.size()) {
        c[i + 1][j] += c[i][j];
      }
    }

    T ret = 0;

    rep (i,(int)y.size() - 1) {
      rep (j,(int)x.size() - 1) {
        if (c[i][j] > 0)
          ret += (x[j + 1] - x[j]) * (y[i + 1] - y[i]);
      }
    }

    return ret;
  }
};

typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<ll> x1(n),x2(n),y1(n),y2(n);

  rep (i,n) {
    cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
  }

  Coordinate_Compression_2D<ll> cc2(x1,x2,y1,y2);

  cout << cc2.imos_area() << endl;
  return 0;
}





Measured memory_bytes: 128216
# ABC094C - Many Medians (ARC095C)
def main():
    N, *X = map(int, open(0).read().split())
    l, h = sorted(X)[N // 2 - 1 : N // 2 + 1]
    ans = [h if i <= l else l for i in X]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 28764
#include<cstdio>
int main(){
	int h1,m1,h2,m2,k;
	scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
	printf("%d\n",h2*60+m2-h1*60-m1-k);
	return 0;
}

Measured memory_bytes: 1736
s = list(input())
k = int(input())

substring = []
for i in range(len(s)):
    for j in range(i,min(len(s),i+k)):
        if not("".join(s[i:j+1]) in substring):
            substring.append("".join(s[i:j+1]))

substring.sort()
print(substring[k-1])

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

using namespace std;

int main(){

	int n,ans=0;
	cin>>n;
	vector<int>a(n-1),b(n),c(n);
	for(int i=0;i<n-1;++i){
		cin>>a[i];
		b[i+1]=a[i];
		c[i]=a[i];
	}
	b[0]=a[0];
	c[n-1]=a[n-2];
	//for(int i=0;i<n;++i) cout<<b[i]<<" "<<c[i]<<endl;
	for(int i=0;i<n;++i) ans+=min(c[i],b[i]);	
	cout<<ans<<endl;
	return 0;
}	



Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

class P{
public:
	int x,y,cost,bit;

	P(int _x,int _y,int _cost,int _bit){
		x = _x;
		y = _y;
		cost = _cost;
		bit = _bit;
	}

	bool operator<(const P &p)const{
		return cost > p.cost;
	}
};

int w,h;
int s[32][32];
char t[32][32];

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

int solve(int sx,int sy){
	priority_queue<P> open;
	map< int, map<int, map<int, bool> > > closed;

	open.push(P(sx,sy,0,0));

	while(!open.empty()){
		P p = open.top(); open.pop();

		if(closed[p.x][p.y][p.bit]) continue;
		closed[p.x][p.y][p.bit] = true;

		//cout<<t[p.y][p.x]<<" : "<<"("<<p.x<<","<<p.y<<","<<p.cost<<")"<<endl;

		if(t[p.y][p.x] == '<'){
			return p.cost;
		}

		for(int i=0;i<4;i++){
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];

			if(t[ny][nx]=='#') continue;

			//¬¶ ... âÌbit½]
			if(s[ny][nx] < 0){
				open.push(P(nx,ny,p.cost+1,(p.bit ^ (1<<(-s[ny][nx])))));
			}
			//å¶
			else if(s[ny][nx] > 0){
				if( (p.bit & (1<<s[ny][nx])) != 0 ){
					open.push(P(nx,ny,p.cost+1,p.bit));
				}
			}
			else{
				open.push(P(nx,ny,p.cost+1,p.bit));
			}
		}
	}

	return -1;
}

int main(void){
	while(cin>>w>>h && (w||h)){
		int sx,sy;
		int alpha[26],size=1;
		memset(alpha,-1,sizeof(alpha));
		memset(s,0,sizeof(s));

		for(int i=0;i<h;i++){
			cin>>t[i];
			for(int j=0;j<w;j++){
				if('A' <= t[i][j] && t[i][j] <= 'Z'){
					int idx = t[i][j] - 'A';
					if(alpha[idx] == -1){
						alpha[idx] = size++;
					}
					t[i][j] = '.';
					s[i][j] = alpha[idx];
				}
				else if('a' <= t[i][j] && t[i][j] <= 'z'){
					int idx = t[i][j] - 'a';
					if(alpha[idx] == -1){
						alpha[idx] = size++;
					}
					t[i][j] = '.';
					s[i][j] = -alpha[idx];
				}
				else if(t[i][j] == '@'){
					sx = j;
					sy = i;
				}
			}
		}

		cout<<solve(sx,sy)<<endl;
	}

	return 0;
}

Measured memory_bytes: 7724
# C - Remainder Minimization 2019



def remind2019(L, R):
    # 0 2019の倍数がある
    if (R-L)> 2019:
        return 0

    if (R%2019 == 0) or (L%2019==0):
        return 0
    else:
        qL, mL = divmod(L,2019)
        qR, mR = divmod(R, 2019)

        if mR <= mL: #１周している
            return 0
        else:
            min_m = 2017*2018
            for i in range(mL, mR):
                for j in range(i+1, mR+1):
                    m = (i*j)%2019

                    if m < min_m:
                        min_m = m 
            return min_m



L,R = map(int, input().split())
print(remind2019(L,R))


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

int main(){
	int n;
	int a;
	vector<int> l;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a;
		if(l.empty()) l.push_back(a);
		else{
			if(l.back() < a) l.push_back(a);
			else{
				l[lower_bound(l.begin(),l.end(),a) - l.begin()] = a;
			}
		}
	}
	cout << l.size() << endl;
	return 0;
}

Measured memory_bytes: 3508
#include <iostream>
#include <string>
using namespace std;
int main(){
	int n,m,j=0;
	cin>>n;
	string u[n],t;
	for(int i=0;i<n;i++){
		cin>>u[i];
	}
	cin>>m;
	for(int i=0;i<m;i++){
		int a=0;
		cin>>t;
		for(int k=0;k<n;k++){
			if(u[k]==t){
				if(j==0){
					cout<<"Opened by "<<t<<endl;
					j=1;
				}
				else if(j==1){
					cout<<"Closed by "<<t<<endl;
					j=0;
				}
				a=1;
			}
		}
		if(a==0){
			cout<<"Unknown "<<t<<endl;
		}
	}
    return 0;
}

Measured memory_bytes: 1216
package main

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

type MyScanner struct {
	sc *bufio.Scanner
}

type MyWriter struct {
	stdout io.Writer
}

type MyPut interface{}

func getScanner(fp io.Reader) *bufio.Scanner {
	sc := bufio.NewScanner(fp)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 500001), 500000)
	return sc
}

func getHugeScanner(fp io.Reader, size int) *bufio.Scanner {
	sc := bufio.NewScanner(fp)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, size), size)
	return sc
}

func (mysc *MyScanner)String() string {
	mysc.sc.Scan()
	return mysc.sc.Text()
}

func (mysc *MyScanner)Int() int {
	i, _ := strconv.Atoi(mysc.String())
	return i
}

func (mysc *MyScanner)Int64() int64 {
	i, _ := strconv.ParseInt(mysc.String(), 10, 64)
	return i
}

func (mysc *MyScanner)Float64() float64 {
	i, _ := strconv.ParseFloat(mysc.String(), 64)
	return i
}

func (mw MyWriter)Puts(v MyPut) {
	_, _ = fmt.Fprintf(mw.stdout, "%v\n", v)
}

var e [][]int
var done []bool

func DFS(i int) {
	if done[i] {
		return
	}
	done[i] = true
	for _, v := range e[i] {
		DFS(v)
	}
	return
}

func Solve(stdin io.Reader, stdout io.Writer) {
	sc := MyScanner{getScanner(stdin)}
	mw := MyWriter{stdout}

	n := sc.Int()
	m := sc.Int()

	e = make([][]int, n)
	done = make([]bool, n)

	for i := 0; i < m; i++ {
		x := sc.Int()
		y := sc.Int()
		_ = sc.Int()
		x--
		y--
		e[x] = append(e[x], y)
		e[y] = append(e[y], x)
	}

	ans := 0

	for i := 0; i < n; i++ {
		if !done[i] {
			DFS(i)
			ans++
		}
	}

	mw.Puts(ans)
}

func main() {
	Solve(os.Stdin, os.Stdout)
	return
}

Measured memory_bytes: 22400
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define double long double
using namespace std;
const int N = 301;
const int INF = 1e9;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
typedef tuple<int,int,int> T;
int n;
int m;
vector<T> A;

bool check(int r,int g,int b){
  static bool mem[N][N][N];
  static bool used[N][N][N]={};
  if(used[r][g][b]) return mem[r][g][b];
  used[r][g][b] = 1;
  int i = lower_bound(A.begin(),A.end(),T(b,-1,-1)) - A.begin();

  bool res = 1;
  for(;i < m && res;i++){
    int R,L,x; tie(R,L,x) = A[i];
    if(R > b) break;
    if(x == 1) res &= r < L && g < L;
    else if(x == 2) res &= r < L && g >= L;
    else if(x == 3) res &= r >= L && g >= L;
  }
  return mem[r][g][b] = res;
}

int mem[N][N][N];
bool used[N][N][N];
int dfs(int r,int g,int b){
  vector<int> Idx({r,g,b});
  sort(Idx.begin(),Idx.end());
  r = Idx[0], g = Idx[1], b = Idx[2];
  
  int idx = max({r,g,b});
  if(!check(r,g,b)) return mem[r][g][b] = 0;
  if(idx == n) return 1;
  if(used[r][g][b]) return mem[r][g][b];
  used[r][g][b] = 1;
  
  ll res = 0;
  res = (res + dfs(idx+1,g,b));
  res = (res + dfs(r,idx+1,b));
  res = (res + dfs(r,g,idx+1));
  return mem[r][g][b] = res % mod;
}

signed main(){
  cin>>n>>m;

  A.resize(m);
  for(int i=0;i<m;i++){
    int l,r,x;
    cin>>l>>r>>x;
    A[i] = T(r,l,x);
  }
  sort(A.begin(),A.end());

  int ans = dfs(0,0,0);
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 186624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
string s,t;
int ans=1000;
signed main(){
	cin>>s>>t;
	int ss=s.size(),st=t.size();
	for(int i=0;i<=ss-st;i++){
		int cnt=0;
		for(int j=i;j<i+st;j++){
			if(t[j-i]!=s[j])cnt++;
		}
		ans=min(ans,cnt);
	}
	ans=min(ans,st);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3640
fun main(args: Array<String>) {
    val sc = java.util.Scanner(System.`in`)
    var h = sc.nextLong()

    var r = 0L
    var p = 1L
    while (true) {
        if (h > 1) {
            r += p
            p *= 2
            h /= 2
        } else {
            r += p
            break
        }
    }
    print(r)
}


Measured memory_bytes: 31392
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, a[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	multiset<int>st;
	for (int i = n - 1; i >= 0; i--) {
		if (st.upper_bound(a[i]) == st.end())st.insert(a[i]);
		else {
			st.erase(st.upper_bound(a[i]));
			st.insert(a[i]);
		}
	}
	cout << st.size() << endl;
}

Measured memory_bytes: 5760
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(ALL(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x : a){
        cin >> x;
    }
    int ans = 0;
    while(1){
        for(int i = 0; i < n;){
            int l = i;
            int mn = 102;
            while(l < n && a[l] > 0){
                mn = min(mn, a[l]);
                l++;
            }
            if(l > i){
                for(int j = i; j < l; j++){
                    a[j] -= mn;
                }
                ans += mn;
                i = l;
            }else i++;
        }
        int sum = accumulate(ALL(a), 0);
        if(sum == 0){
            break;
        }
    }
    cout << ans;
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}

static void ABC138E();

#if 1
int main()
{
	ABC138E();
	fflush(stdout);
	return 0;
}
#endif

static void ABC138E()
{
	std::string si, ti;

	std::cin >> si;
	std::cin >> ti;

	std::vector<int> sParts('z' - 'a' + 1, 0), tParts('z' - 'a' + 1, 0);

	int slen = si.size();
	for (int i = 0; i < slen; i++) {
		sParts[si[i] - 'a']++;
	}

	int tlen = ti.size();
	for (int i = 0; i < tlen; i++) {
		tParts[ti[i] - 'a']++;
	}
	//	t の構成要素を全部持っているかチェック
	for (int i = 0; i < ('z' - 'a' + 1); i++) {
		if (tParts[i] && !sParts[i]) {
			printf("-1\n");
			return;
		}
	}

	//	次のアルファベットは何文字目に出現するか
	std::vector<std::vector<int>> next(slen, std::vector<int>('z' - 'a' + 1, -1));
	next[slen - 1][si[slen - 1] - 'a'] = slen - 1;
	for (int i = slen - 2; i >= 0; i--) {
		next[i] = next[i + 1];
		next[i][si[i] - 'a'] = i;
	}

	LLONG ans = 0;
	int tPos = 0;
	int nowPos = 0;
	while (tPos < tlen) {
		int nextPos = next[nowPos][ti[tPos] - 'a'];
		if (nextPos == -1) {
			ans += (LLONG)(slen - nowPos);
			nowPos = 0;
		}
		else {
			tPos++;
			nextPos++;
			if (nextPos > (slen - 1)) {
				ans += slen - nowPos;
				nextPos = 0;
			}
			else {
				ans += nextPos - nowPos;
			}
			nowPos = nextPos;
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 13696
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 1000000000
#define eps 1e-7
#define mod 1000000007
#define int ll
using namespace std;

signed main(void) {
    int K, A, B;
    cin >> K >> A >> B;
    int D = B-A;
    if (K==1) { //ビスケット叩く一択
        cout << 2 << endl;
        return 0;
    }
    if (D <= 2) { //換金がアドじゃない
        cout << K+1 <<endl;
        return 0;
    } else { //換金がアド
        int nec = A-1; //換金できるまでに叩く回数
        int rem = K - nec; //残された操作回数
        if (rem <= 1) { //換金しても虚無
            cout << A+1 << endl;
            return 0;
        } else if (rem % 2 == 0) { //偶数→交互に換金
            cout << A + (rem / 2) * D << endl;
            return 0;
        } else { //奇数→最後は叩く
            cout << A + (rem / 2) * D + 1 << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

typedef pair<bool, char> lit;

lit literal(string str){
  if(str.size() == 2) return lit(false, str[1]);
  return lit(true, str[0]);
}

bool clause(string str){
  lit data[3];
  int p = 0;
  int pre = 0;
  for(int i=0;i<str.size();i++){
    if(str[i] == '&'){
      data[p++] = literal(str.substr(pre, i-pre));
      pre = i+1;
    }
  }
  data[p++] = literal(str.substr(pre, (int)str.size()-pre));
  for(int i=0;i<3;i++){
    for(int j=i+1;j<3;j++){
      if(data[i].first != data[j].first && data[i].second == data[j].second) return false;
    }
  }
  return true;
}

bool expression(string str){
  int l;
  for(int i=0;i<str.size();i++){
    if(str[i] == '(') l = i+1;
    if(str[i] == ')' && clause(str.substr(l, i-l))) return true;
  }
  return false;
}

main(){
  string str;
  while(cin >> str){
    if(str == "#") break;
    cout << (expression(str) ? "yes" : "no") << endl;
  }
}

Measured memory_bytes: 900
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repr(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
  int n;
  cin >> n;
  v a(n, 0);
  rep(i, n - 1)
  {
    int temp;
    cin >> temp;
    a[temp - 1]++;
  }
  rep(i, n)
  {
    cout << a[i] << endl;
  }
}


Measured memory_bytes: 4000
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

class BIT{
    private:
    vector<ll> _bit;
    int _n;
    public:
    BIT(int n) : _n(n), _bit(vector<ll>(n+1, 0)) {}
    ll sum(int i){
        ll s = 0;
        while(i > 0){
            s += _bit[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, ll x){
        while(i <= _n){
            _bit[i] += x;
            i += i & -i;
        }
    }
    ll get_value(int i){
        return _bit[i];
    }
};

int main(void)
{
    int n;
    cin >> n;
    BIT bit(n);
    vector<int> a(n), b(n);
    REP(i, n){
        cin >> a[i];
    }
    b = a;
    SORT(b);
    map<int, int> m;
    REP(i, n){
        m[b[i]] = i+1;
    }
    ll ans = 0;
    REP(i,n){
        ans += i - bit.sum(m[a[i]]);
        bit.add(m[a[i]], 1);
    }
    pr(ans);
}


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

typedef pair<int,int>P;
typedef pair<int,P>PP;

int main(){
	int n,m;
	while(cin>>n>>m,n){
		vector<PP>V;
		int t,s,d;
		for(int i=0;i<m;i++){
			cin>>t>>s>>d;
			V.push_back(PP(t,P(s,d)));
		}
		sort(V.begin(),V.end());
		
		int flag[20001]={0};
		flag[1]=1;
		int cnt=1;
		for(int i=0;i<m;i++){
			if(flag[V[i].second.first]==1&&flag[V[i].second.second]==0){
				flag[V[i].second.second]=1;
				cnt++;
			}
		}
		
		cout<<cnt<<endl;
		
	}
	
	return 0;
}


Measured memory_bytes: 1764