akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;
int main(){
	int zero;
	while(1){
		int card,cut;
		
		cin >> card >> cut;
		if(card == 0 && cut == 0){
			return 0;
		}
		
		int topcard = card;
		
		int *c = new int[cut];
		int *p = new int[cut];

		for(int i=0; i<cut; ++i){
			cin >> p[i] >> c[i];
		}

		for(int i=cut-1; i>=0; --i){
			if(topcard > card-c[i]){
				topcard -= (p[i]-1);
			}
			else if( topcard > card-c[i]-(p[i]-1) ){
				topcard += c[i];
			}
		}
		cout << topcard << endl;
		
		delete[] c;
		delete[] p;
		
	}


}

Measured memory_bytes: 1196
#include <iostream>
#include <vector>
#include <string>
int max (int x,int y){
    if (x>y) {
        return x;
    }
    else
        return y;
}
int min (int s,int t){
    if (s<t) {
        return s;
    }
    else
        return t;
}
using namespace std;
int main(){
    int a;
    cin >> a;
    long long num,sum,b,c;
    b= -1000000;
    c=1000000;
    sum = 0;
    for (int i=0; i<a; i++) {
       cin >> num;
        sum += num;
        b = max(b,num);
        c = min(c,num);
    }
    cout << c << " " << b << " " << sum <<endl;
}


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

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;


deque<int> dq[300];

const int maxn = 2e5+1;
char s[maxn];
int n;
inline void no()
{
  puts("-1");
  exit(0);
}
int bit[maxn];
inline void add(int x, int y)
{
  while (x <= n)
    {
      bit[x] += y;
      x += x&-x;
    }
}
inline int sum(int x)
{
  int ret = 0;
  while (x)
    {
      ret += bit[x];
      x -= x&-x;
    }
  return ret;
}



int main()
{
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < n; ++i)
    dq[s[i]].push_back(i+1);
  char center;
  if (n%2==0)
    {
      for (char c = 'a'; c <= 'z'; ++c)
	if (((int)dq[c].size())%2)
	  no();
    }
  else
    {
      int cnt = 0;
      for (char c = 'a'; c <= 'z'; ++c)
	if (((int)dq[c].size())%2)
	  ++cnt, center = c;
      if (cnt != 1)
	no();
    }
  for (int i = 1; i <= n; ++i)
    add(i, 1);
  ll ans = 0;
  int tot = n;
  for (int l = 1, r = n; l < r; ++l, --r, tot-=2)
    {
      char pick = 0;
      int dif = 1e9;
      for (char c = 'a'; c <= 'z'; ++c)
	if (dq[c].size() > 1)
	  {
	    int lcnt = sum(dq[c].front());
	    int rcnt = sum(dq[c].back());
	    int tmp = lcnt-1+tot-rcnt;
	    if (tmp < dif)
	      dif = tmp, pick = c;
	  }
      ans += dif;
      char c = pick;
      add(dq[c].front(), -1);
      add(dq[c].back(), -1);
      dq[c].pop_front();
      dq[c].pop_back();
    }
  printf("%lld\n", ans);
  
}



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

#define pb push_back
#define ll long long
#define maxn 100005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int n,t;
    cin >> n >> t;
    int dp[6005] = {};
    vector<pair<int,int> >v;
    f(n){
        int add1, add2;
        cin >> add1 >> add2;
        v.pb({add1,add2});
    }
    sort(v.begin(),v.end());
    for(auto i:v){
        int add1=i.F, add2=i.S;
        for(int j = t + add1 - 1 ; j >= add1; j--){
            dp[j] = max(dp[j],dp[j-add1] + add2);
        }
    }
    int mx = 0;
    f(6001){
        mx = max(mx,dp[i]);
    }
    cout << mx << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const long long MAX = 1000000;
const long long MOD = 1000000007;


long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (long long i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        //そのまま計算すると負の値になるのでMODを足す
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
/*
long long COM(long long n, long long k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
*/

long long COM2(long long n, long long k) {
    long long t1 = 1;
    long long t2 = 1;
    for(long long i=n;i>=n-k+1;i--) {
        t1 = (t1 * i) % MOD;
    }
    return (t1 * finv[k]) % MOD;
}

long long fast_pow(long long n, long long k) {
    if(k==0) return 1;
    if(k%2 == 0) {
        return fast_pow(n*n % MOD, k/2);
    } else {
        return (fast_pow(n, k-1) * n) % MOD;
    }
}

int main() {
    COMinit();
    long long int n, a, b;
    cin >> n >> a >> b;

    long long ans = (fast_pow(2, n) - COM2(n, a)+MOD) % MOD;
    ans = (ans - COM2(n, b) + MOD) % MOD;
    ans = (ans - 1 + MOD) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 23808
#include<stdio.h>
const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,
                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};
int main(void)
{
  int i,x;
  long long a=0,N;
  x=scanf("%lld",&N);
  for(i=2;i<=1e6;i++)
  {
    for(x=0;N%i==0;x++)N/=i;
    a+=e[x];
  }
  if(N>1)a++;
  return printf("%lld\n",a),0;
}

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

int main() {

  int N,K;
  string str;
  
  cin >> N >> K >> str;

  for(int i = 0; i<N; i++){
    if(i != K-1)
      cout<< str.at(i);
      else if(str.at(i)=='A')
      cout<<"a";
      else if(str.at(i)=='B')
      cout<<"b";
      else
      cout<<"c";
      
      
      
      }
      
}

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

using namespace std;

typedef long long ll;

const int N = 2010;
const int MOD = 1e9 + 7;

ll sum, comb[N][N];

int main() {
  for (int i = 0; i < N; ++i) comb[i][0] = 1;
  for (int i = 1; i < N; ++i) for (int j = 1; j <= i; ++j) {
    comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    if (comb[i][j] >= MOD) comb[i][j] -= MOD;
  }
  cin >> sum;
  ll ans = 0;
  for (ll k = 1; 3 * k <= sum; ++k) {
    ans += comb[sum - 2 * k - 1][k - 1];
  }
  ans %= MOD;
  cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 26404
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=200000+10;
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int n,a,ans;

int main()
{
    #ifdef __LOCAL__
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    cin>>n;
    int last=0;
    _rep(i,1,n) 
    {
        cin>>a;
        if(a==last+1)
            last=a;
        else
            ans++;
    }
    if(last)
        cout<<ans<<endl;    
    else
        cout<<-1<<endl;
    return 0;
}

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

const int N = (int) 2e5 + 5;

int n; 
char s[N];
int blk[N], wht[N];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	cin >> s + 1;
	for (int i = 1; i <= n; i++) blk[i] = blk[i - 1] + (s[i] == '#');
	for (int i = n; i >= 1; i--) wht[i] = wht[i + 1] + (s[i] == '.');
	int ans = n + 1;
	for (int i = 0; i <= n; i++) ans = min(ans, blk[i] + wht[i + 1]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define ld          long double
#define endl        "\n"

//const int mod = 998244353;

int mod;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

int modpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b % 2) res = mul(res, a);
        b /= 2;
        a = mul(a, a);
    }
    return res;
}

void solve() {
    int n, p; cin >> n >> p;
    string s; cin >> s;
    if(p==2 or p==5) {
        int ans=0;
        for(int i=0; i<n; i++) 
            if((s[i]-'0') % p == 0)
                ans += (i+1);
        cout << ans << endl;
        return;
    } 
    int cnt[p]; memset(cnt, 0, sizeof cnt);
    cnt[0] = 1;
    int cur = 0;
    mod = p;
    for(int i=0; i<n; i++) {
        cur = mul(cur, 10); cur = add(cur, s[i] - '0'); 
        int val = mul(cur, modpow(10, n-i-1));
        cnt[val]++;
    }
    int ans=0;
    for(int i=0; i<p; i++) ans += (cnt[i] * (cnt[i] - 1)) / 2;
    cout << ans << endl;
}


signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;
}

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

#define abs(a) (((a) < 0) ? (-(a)) : (a))
int main(void) {
    int64_t N;
    int64_t pint;
    int64_t qint;
    int64_t cnt = 0;
    cin >> N;

    char buf[N+1] = {0};
    string P,Q;
    string check;  
    
    for(int i=0;i<N;i++) {
        cin >> buf[i];
        check += ((i +1) + '0');
    }
    P = buf;
    for(int i=0;i<N;i++) {
        cin >> buf[i];
    }
    Q = buf;
   
//    cout << P << " " << Q << " " << check << "\n";
    do{
        if(P == check) pint = cnt;
        if(Q == check) qint = cnt;
        cnt++;
    }while(next_permutation(check.begin(), check.end()));

    cout << abs(qint - pint) << "\n";

    return 0;
}


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

using namespace std;

int main(){
	int h,w;
	cin >> h >> w;
	unordered_map<int,bool> row,col;
	vector<string> v;
	for(int i=0;i<h;i++) {
		string s;
		cin >> s;
		for(int j=0;j<(int)s.size();j++) {
			if(s[j]=='#') {
				col[j]=1;
				row[i]=1;
			}
		}
		v.push_back(s);
	}
	for(int i=0;i<h;i++) {
		if(row[i]) {
			for(int j=0;j<w;j++) {
				if(col[j]) {
					cout << v[i][j];
				}
			}
			cout << "\n";
		}
	}
	return 0;
}




Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a; }

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

    ll ans = 0;
    rep(i, n) rep(j, n) rep(k, n) {
        ll tmp = gcd(i+1, j+1);
        ans += gcd(tmp, k+1);
    }

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

Measured memory_bytes: 3640
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush

def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, N3 = N * 2, N * 3
    E = [[] for _ in range(N3)]
    ref = lambda v : v if v < 3 * N else v - N2

    # build range-edge graph
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    def add_range_edge(l0, r0, l1, r1, w):
        E.append([])
        v = len(E) - 1
        _add_range_edge(l0 + N, r0 + N, v, w, to = True)
        _add_range_edge(l1 + N, r1 + N, v, 0, to = False)

    def _add_range_edge(l, r, v, w, to):
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((v, w)) if to else E[v].append((l, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((v, w)) if to else E[v].append((r, w))
            l >>= 1
            r >>= 1

    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        add_range_edge(u, v, u, v, w)

    # Dijkstra (start : N, terminal : N + n - 1)
    dist = [INF] * (N3 + m)
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Measured memory_bytes: 261920
package main

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

func main() {
	N, R := ReadInt(), ReadInt()
	if N > 10 {
		fmt.Println(R)
		return
	}
	fmt.Println(R + 100*(10-N))
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1840
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = [input() for _ in range(H)]

for x in C:
	print(x)
	print(x)

Measured memory_bytes: 14492
#include <iostream>
using namespace std;
const int nmax=8;
bool graph[nmax][nmax];

int dfs(int v,int N, bool visited[nmax]) {
    
    bool all_visited=true;

    for (int i=0; i<N; ++i) {
        if (visited[i]==false) 
            all_visited=false;
    }

    if (all_visited){
        return 1;
    }

    int ret=0;

    for (int i=0; i<N; ++i) {
        if (graph[v][i]==false) continue;
        if (visited[i]) continue;

        visited[i]=true;
        ret+=dfs(i,N,visited);
        visited[i]=false;
    }

    return ret;
}

int main() {
    int N, M;
    
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a-1][b-1] = graph[b-1][a-1] = true;
    }

    bool visited[nmax];
    for (int i=0; i<N; ++i) {
        visited[i] = false;
    }

    visited[0] =true;
    cout << dfs(0, N, visited) << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = 0
tmp = 1000000000000
for i in range(N):
  ans += b[a[i]-1]
  if tmp - a[i] == -1:
    ans += c[a[i-1]-1]
  tmp = a[i]

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int n;
  cin >> n;
  vl a(n);
  rep(i,n) cin >> a.at(i);
  long ans = 0;
  rep(i,n-1){
    long d = a.at(i) - a.at(i+1);
    if(d > 0){
      ans += d;
      a.at(i+1) += d;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 4788
import sys, math
from collections import defaultdict, deque
from copy import deepcopy
import itertools
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
S = input()
q = deque([])
q_new = deque([])
d = defaultdict(list)
for i in range(10):
    for j in range(10):
        for k in range(10):
            d[i].append([k, j, i])

ans = 0
for x in S:
    x = int(x)
    q = deepcopy(d[x])
    d[x] = []
    for key in q:
        l = len(key)
        if l == 3:
            d[key[1]].append(key[:2])
        elif l == 2:
            d[key[0]].append(key[:1])
        elif l == 1:
            ans += 1

print(ans)

Measured memory_bytes: 49756
#include<bits/stdc++.h>
using namespace std;
int main(){
    int k;
    char s[105];
    cin>>k;cin>>s;
    if(strlen(s)<=k) cout<<s;
    else {
        for(int i=0;i<k;i++)
            cout<<s[i];
        cout<<"...";
    }
    return 0;
}

Measured memory_bytes: 3604
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val _ = readLine
    val Array(tAve0, tTarget) = readLine.split(" ").map(_.toInt)
    val cand = readLine.split(" ").map(_.toInt)
    import scala.math.abs
    val tDiffWIdx = cand.map(x => abs((tAve0 * 1000) - (x * 6) - (tTarget * 1000))).zipWithIndex.sortBy(_._1)

    val ans = tDiffWIdx.head._2
    println(ans + 1)
  }
}


Measured memory_bytes: 25400
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int H, W, A, B;
    cin >> H >> W >> A >> B;
    REP(i, H) {
        string s = "";
        if (i < B) {
            REP(j, A) s += '0';
            REP(j, W-A) s += '1';
        } else {
            REP(j, A) s += '1';
            REP(j, W-A) s += '0';
        }
        cout << s << '\n';
    }
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll N,M,K;
ll T;
ll fast,slow,mid;
 
vector<ll> t;
typedef pair<ll,ll> P;
 
priority_queue< P > Q;

ll search(ll x,ll v){
  if(x>T)return 0;
  return (T-x)/v+1;
}

void solve(){
  ll ans=0;
  vector<ll> v;
  if( (N-1)*fast <= T )ans++;
  
  for(int i=0;i+1<(int)t.size();i++){
    ll left=t[i];
    ll right=t[i+1];
    ll lx=(left-1)*fast;
    ll Fi=search(lx,slow);
    ans+=min(left+Fi,right)-left;
    //cout<<left<<' '<<left+Fi<<endl;
    
    for(int j=0;j<K-M;j++){
      ll Se=search(lx+Fi*mid,slow);
      ll first=left+Fi;
      ll second=left+Fi+Se;
      first=min(first,right);
      second=min(second,right);
      v.push_back(max(0LL,second-first));
      Fi+=Se;
    }
  }
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  for(int i=0;i<K-M;i++){
    ans+=v[i];
  }
  cout<<ans-1<<endl;
}
 
int main(){
  cin>>N>>M>>K;
  cin>>slow>>fast>>mid;
  cin>>T;
  t.resize(M);
  for(int i=0;i<M;i++)cin>>t[i];
  solve();
  return 0;
}

Measured memory_bytes: 19280
N,M=[int(x) for x in input().split()]
INF=1000000000000000
adj=[[INF for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
	adj[i][i]=0
	
A=[]
B=[]
C=[]
ans=M

for i in range(M):
	a,b,c=[int(x) for x in input().split()]
	adj[a][b]=min(adj[a][b],c)
	adj[b][a]=min(adj[b][a],c)
	A.append(a)
	B.append(b)
	C.append(c)

for k in range(1,N+1):
		for i in range(1,N+1):
			for j in range(1,N+1):
				adj[i][j]=min(adj[i][k]+adj[k][j],adj[i][j])


for i in range(M):
	temp=1
	for j in range(1,N+1):
		if adj[j][A[i]]+C[i]==adj[j][B[i]]:
			temp=0
	if temp==0:
		ans-=1
print(ans)
		






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

struct mp{
	int to,dis;
	mp(int x,int y):to(x),dis(y){}
};

void trip(int nw,int f,int64_t dist,vector<vector<mp>>&v,vector<int64_t>&d){
	d.at(nw)=dist;
	for(auto&i:v.at(nw)){
		if(i.to!=f)trip(i.to,nw,dist+i.dis,v,d);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<vector<mp>>v(n+1);
	for(int i=1;i<n;++i){
		int a,b,c; cin>>a>>b>>c;
		mp x(a,c),y(b,c);
		v.at(a).emplace_back(y);
		v.at(b).emplace_back(x);
	}
	int q,k; cin>>q>>k;
	vector<int64_t>d(n+1);
	trip(k,-1,0,v,d);
	for(int i=0;i<q;++i){
		int x,y; cin>>x>>y;
		cout<<d.at(x)+d.at(y)<<"\n"s;
	}
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
typedef long long ll;
vector<string>v;
map<string, int>mp;
int main(){
	int n;
	cin >> n;
	int mx = 0;
	for (int i = 1; i <= n; i++){
		string s;
		cin >> s;
		mp[s]++;
		mx = max(mx, mp[s]);
	}
	for (auto it : mp){
		if (it.second == mx){
			cout << it.first << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int N, T;
  cin >> N >> T;

  vector<int> t(N);
  REP(i, N) cin >> t[i];

  int ans = T;
  REP(i, N-1){
    ans += min(T, t[i+1]-t[i]);
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 1792
a = input()
b = input()
c = input()
Sa,Sb,Sc = [],[],[]
for x in a:
    Sa.append(x)
for x in b:
    Sb.append(x)
for x in c:
    Sc.append(x)

x = Sa.pop(0)
while True:
    
    if x == "a":
        if Sa == []:
            print("A")
            break
        else:
            x = Sa.pop(0)
    elif x == "b":
        if Sb == []:
            print("B")
            break
        else:
            x = Sb.pop(0)
    else :
        if Sc == []:
            print("C")
            break
        else:
            x = Sc.pop(0)


Measured memory_bytes: 3064
#include <vector>
#include <cstdint>
#include <functional>

using namespace std; //ごめんなさい

template<typename T=int_fast64_t>
struct segT{
  vector<T>node;
  using func=function<T(T,T)>;
  func f;
  T e;
  int sz;
  segT(int n){
    f=[](T a,T b){return a+b;};
    e=0;
    sz=1;while(sz<n)sz*=2;
    node.resize(2*sz-1,e);
  }
  segT(int n,T e,func f):e(e),f(f){
    sz=1;while(sz<n)sz*=2;
    node.resize(2*sz-1,e);
  }
  void add(int x,T val){
    x+=sz-1;
    node[x]=f(node[x],val);
    while(x>0){
      x=(x-1)/2;
      node[x]=f(node[2*x+1],node[2*x+2]);
    }
  }
  void update(int x,T val){
    x+=sz-1;
    node[x]=val;
    while(x>0){
      x=(x-1)/2;
      node[x]=f(node[2*x+1],node[2*x+2]);
    }
  }
  T sum(int a,int b,int l=0,int r=-1,int k=0){
    if(r==-1)r=sz;
    if(a<=l&&r<=b)return node[k];
    if(b<=l||r<=a)return e;
    T lval=sum(a,b,l,(l+r)/2,2*k+1);
    T rval=sum(a,b,(l+r)/2,r,2*k+2);
    return f(lval,rval);
  }
};

#include <bits/stdc++.h>

int main(){
  int n,q;
  cin>>n>>q;
  segT<int>s(n,INT_MAX,[](int a,int b){return min(a,b);});
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==0)s.update(x,y);
    if(c==1)cout<<s.sum(x,y+1)<<endl;
  }
}



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

int main(){
	int h;
	int a;
	cin >> h >> a;

	if(h%a == 0)
		cout << h/a << endl;
	else
		cout << (h/a)+1 << endl;
	
}

Measured memory_bytes: 256
N = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

F = factorization(N)
import math
f = []
if F[0][0] != 1:
  for i in range(len(F)):
    f.append(int((math.sqrt(8*F[i][1]+1) - 1)/2))

print(sum(f))

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

int  main()
{
	int a,b;
	cin >> a >> b;
	if (a < 10 && b < 10) cout << a*b << endl;
	else cout << -1;
	return (0);
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int N,i;
    scanf("%d",&N);
    i=N%10;
    if(i==3)
    {
        printf("bon\n");
    }
    else if(i==0||i==1||i==6||i==8)
    {
        printf("pon\n");
    }
    else
        printf("hon\n");
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	char c;
	cin>> c;

	if('A'<=c && c<='Z'){
		//大文字
		//cout<< "large" <<endl;

		//大文字を小文字に
		cout<< 'A' <<endl;
	}
	if('a'<=c && c<='z'){
		//小文字
		//cout<< "small" <<endl;

		//小文字を大文字に
		cout<< 'a' <<endl;
	}
 
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <map>
#include <string>
int main()
{
	std::string S;
	std::cin >> S;
	if (S == "ABC") {
		std::cout << "ARC" << std::endl;
	}
	else {
		std::cout << "ABC" << std::endl;
	}
	return 0;
}

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

int main() {
  int N,A=0;
  cin >> N;
  vector<int>vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
   sort(vec.begin(), vec.end()); 
   reverse(vec.begin(), vec.end());
  for(int i=0; i<N; i++){
    if(i%2 == 0){
      A += vec.at(i);
    }
    else{
      A -= vec.at(i);
    }
  }
  cout << A << endl;
}


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

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

	for(int n; cin >> n, n;) {
		vector<int> schedule(n, 0);
		for(int i = 0; i < n; ++i) {
			int m;
			cin >> m;
			for(int j = 0; j < m; ++j) {
				int day;
				cin >> day;
				schedule[i] |= (1 << day);
			}
		}

		vector<long long> map(n);
		for(int i = 0; i < n; ++i)
			map[i] = (1ll << i);

		for(int day = 1; day <= 30; ++day) {
			for(int i = 0; i < n; ++i)
				if(schedule[i] & (1 << day))
					for(int j = i + 1; j < n; ++j)
						if(schedule[j] & (1 << day))
							map[i] = map[j] = (map[i] | map[j]);

			if(find(map.begin(), map.end(), (1ll << n) - 1) != map.end()) {
				cout << day << endl;
				goto success;
			}
		}

		cout << -1 << endl;
	success:;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1204
let () =
  let rec loop () = 
    let h, w = Scanf.scanf "%d %d\n" (fun h w -> h, w) in
    if h = 0 && w = 0 then ()
    else
      (for _ = 1 to h do
        print_endline (String.make w '#');
      done;
      print_endline "";
      loop ())
  in loop ()

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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <math.h>

#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;

constexpr long long int ma = 1000000000000000000LL;

int main() {

    long long int n;
    cin >> n;

    mp::cpp_int ans = 1;
    for ( long long int i = 0; i < n; i++ ) {
        long long int in;
        cin >> in;
        ans *= in;
        if ( ans > ma ) ans = ma + 1;
    }
    if ( ans > ma ) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;

}


Measured memory_bytes: 3680
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
const ll mod=1e9 + 7;
ll power(ll a,ll n)
{
        ll ans=1;
        a=a%mod;
        while(n>0)
        {
                if(n%2==1)
                {
                        ans=(ans*a)%mod;
                }
                n=n/2;
                a=(a*a)%mod;
        }
        return ans;
}

int main()
{
    ll n,l;
    cin>>n>>l;
     ll  sum=0;
    for(int i=1;i<=n;i++)
    {
       sum=sum+(l+i-1);
    }
    ll diff=INT_MAX;
    ll x;
    for(int i=1;i<=n;i++)
    {
      ll z=(l+i-1);
      if(abs(sum-(sum-z))< diff)
      {
          diff=abs(sum-(sum-z));
          x=z;
      }
    }
    cout<<sum-x;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iomanip>


#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;


// <<fixed<<setprecision(6)<<


int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}


int digsum(int n) {
  int res = 0;
  while(n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}


int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}


int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}


int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}


int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}


int main(){
  string s;
  cin>>s;
  if(s=="ABC"){
    cout<<"ARC";
  }
  else{
    cout<<"ABC";
  }
}

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

import sys
patc = [0,1,2,3]
patg = [0,1,7,8]
pata = [0,1,8,9]
pate = [0,1,9,10]
patd = [0,7,8,15]
patf = [0,8,9,17]
patb = [0,8,16,24]
pats = [patc,patg,pata,pate,patd,patf,patb]
pats.sort(key = lambda x:x[-1])
patsname = ["C","G","A","E","D","F","B"]

def iscomp(data,pat):
  if sum([ 1 for s in pat if data[s] == 1]) == len(pat):
    return True
  else:
    return False

def whichpat(data):
  for i in xrange(len(pats)):
    if iscomp(data,pats[i]):
      return i

d = []
b = []
i = 0
for s in sys.stdin:
  if i != -1:
    d.append( [ 1 if e == "1" else 0 for e in  map(str,s)[:-1]])
  i += 1
  if i == 8:
    b.append( [ c for e in d for c in e] )
    d = []
    i = -1
for c in b:
  print patsname[whichpat(c[c.index(1):])]

Measured memory_bytes: 4312
a=input()
n=len(a)

for i in range(2**n):
  res=int(a[0])
  ans=[a[0]]
  for j in range(1,n):
    if i&(1<<j):
      ans.append('+')
      ans.append(a[j])
      res+=int(a[j])
    else:
      ans.append('-')
      ans.append(a[j])
      res-=int(a[j])
  if res==7:
    print(*ans,'=7',sep='')
    exit()

Measured memory_bytes: 9108
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            var a = IO.GetInt();
            var s = IO.GetString();
            var ans = a < 3200 ? "red" : s;

            Console.WriteLine(ans);
        }
    }


    static class IO
    {
        static public string GetString() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public List<string> GetStringList() { return Console.ReadLine().Split(' ').ToList(); }
        static public List<int> GetIntList() { return Console.ReadLine().Split(' ').Select(int.Parse).ToList(); }
        static public List<long> GetLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteStrings<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
    }
}

Measured memory_bytes: 11092
pub fn get_str() -> String {
    use std::io;
    let mut input = String::new();
    io::stdin().read_line(&mut input);
    input.as_str().trim().to_string()
}
fn split_by_space(ss:&str) -> Vec<&str> {
    ss.split_whitespace().collect()
}
fn str_to_int(ss:&str) -> i64 {
    ss.parse().unwrap()
}
pub fn get_ints() -> Vec<i64> {
    split_by_space(&get_str()).iter().map(|s:&&str| str_to_int(s)).collect()
}


fn group_id(i :i64) -> i32 {
    match i {
        1 | 3 | 5 | 7 | 8 | 10 | 12 => 1,
        4 | 6 | 9 | 11 => 2,
        2 => 3,
        _ => panic!("ERROR")
    }
}

fn main() {
    let (x, y) = { let v = get_ints(); (v[0], v[1]) };
    if group_id(x) == group_id(y) {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 X, Y;
	map<int64, int64> mp;
	mp[1] = 300000;
	mp[2] = 200000;
	mp[3] = 100000;
	cin >> X >> Y;
	cout << mp[X] + mp[Y] + (X+Y == 2 ? 400000 : 0) << endl;
}


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

int main(){
  
  int n,m;
  int data[20000];

  while(1){
    int max=0;
    cin>>n>>m;
    if(n==0 && m==0) break;
    for(int i=0;i<n+m;i++)
      cin>>data[i];

    sort(data,data+n+m);
    max=data[0];
    for(int i=1;i<n+m;i++){
      if(data[i]-data[i-1]>max)
	max=data[i]-data[i-1];
    }
    cout<<max<<endl;
  }
  return 0;
}

Measured memory_bytes: 1252
#include <iostream>

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
using namespace std;

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

    int a[n];
    rep(i, n)
    {
        cin >> a[i];
    }

    int min = 1000000, count = 0;

    rep(i, n)
    {
        while (a[i] % 2 == 0)
        {
            a[i] /= 2;
            count++;
        }

        if (min > count)
            min = count;

        count = 0;
    }

    cout << min << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
#define _GLIBCXX_DEBUG
using namespace std;
int64_t M = 1000000007;
int main(){
  int64_t n;
  cin >> n;
  vector<int64_t> t(n),a(n);
  rep(i,n){
    cin >> t[i];
  }
  rep(i,n){
    cin >> a[i];
  }
  vector<int64_t> th(n),ah(n);
  vector<bool> tdecided(n),adecided(n);
  rep(i,n){
    if(i == 0){
      th[i] = t[0];
      tdecided[0] = true;
    }else{
      th[i] = t[i];
      if(t[i-1] != t[i]){
        tdecided[i] = true;
      }
    }
  }
  invrep(i,n){
    if(i == n-1){
      ah[n-1] = a[n-1];
      adecided[n-1] = true;
    }else{
      ah[i] = a[i];
      if(a[i+1] !=a[i]){
        adecided[i] = true;
      }
    }
  }
  /*rep(i,n){
    cout << adecided[i] << tdecided[i] << endl;
  }*/
  bool failed = false;
  vector<int64_t> resh(n);
  vector<bool> decided(n);
  
  rep(i,n){
    if(tdecided[i] && adecided[i]){
      if(th[i] == ah[i]){
        resh[i] = th[i];
        decided[i] = true;
      }else{
        failed = true;
        break;
      }
    }else if(tdecided[i]){
      if(th[i] <= ah[i]){
        resh[i] = th[i];
        decided[i] = true;
      }else{
        failed = true;
        break;
      }
    }else if(adecided[i]){
      if(ah[i] <= th[i]){
        resh[i] = ah[i];
        decided[i] = true;
      }else{
        failed = true;
        break;
      }
    }else{
      resh[i] = min(th[i],ah[i]);
      decided[i] = false;
    }
  }
  /*rep(i,n){
    cout << decided[i] << " ";
  }
  cout << endl;
  rep(i,n){
    cout << resh[i] << " ";
  }*/
  if(failed){
    cout << 0 << endl;
  }else{
    int64_t res = 1;
    rep(i,n){
      if(!decided[i]){
        res = (res * resh[i])%M;
      }
    }
    cout << res << endl;
  }
        
      
  

      
  
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[100007],b[100007];
int main()
{
	int ans=0;
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<n;i++) if (a[i]>a[i+1]) b[i]=1; else if (a[i]<a[i+1]) b[i]=-1;
	int now=1;
	while (now<n)
	{
		int check=0;
		while (now<n&&b[now]*check>=0)
		{
			if (b[now]!=0) check=b[now];
			++now;
//cout << now << endl;
		}
		++ans;
		++now;
//cout << now << endl;
	}
	if (now==n) ++ans;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>

void process() {
	int64_t H {};
	std::cin >> H;

	int64_t cnt {};
	for(int i = 0; i <= static_cast<int>(log2(H)); ++i)
		cnt += static_cast<uint64_t>(std::pow(2, i));

	std::cout << cnt << std::endl;
}

int main() {
	process();
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
   public static void main(String args[]){
      //declaration and initialization
      Scanner sc = new Scanner(System.in);
      String input[];
      
      //variables for each problem
      String answer;
      int a;
      int b;
      int c;
      int temp;
      
      //reading the intput
      input = sc.nextLine().split(" ",0);
      
      //assginment
      a = Integer.parseInt(input[0]);
      b = Integer.parseInt(input[1]);
      c = Integer.parseInt(input[2]);
      
      //evaluation
      //bubble sort
      if(a > b){
         temp = a;
         a = b;
         b = temp;
      }
      
      if(b > c){
         temp = b;
         b = c;
         c = temp;
      }
      
      if(a > b){
         temp = a;
         a = b;
         b = temp;
      }
            
     //output
     System.out.println(a + " " + b + " " + c);
      
      
      
   }//main
      
}//class

Measured memory_bytes: 26048
n = int(input())
p_list = [int(x) for x in input().split()]
cnt = 0
for i in range(n-2):
    cnt += ((p_list[i] < p_list[i+1] < p_list[i+2]) or (p_list[i] > p_list[i+1] > p_list[i+2]))
print(cnt)


Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int A, B, X; std::cin >> A >> B >> X;
  if ( X >= A && A+B >= X ) std::cout << "YES" << std::endl;
  else std::cout << "NO" << std::endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(input().split())
B = A[:]

for i in range(N):
    for j in range(N-1, i, -1):
        if A[j][1] < A[j-1][1]:
            A[j], A[j-1] = A[j-1], A[j]

print(*A, sep=' ')
print('Stable')

for i in range(N):
    minj = i
    for j in range(i, N):
        if B[j][1] < B[minj][1]:
            minj = j
    B[i], B[minj] = B[minj], B[i]

print(*B, sep=' ')
if A == B:
    print('Stable')
else:
    print('Not stable')


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

pair<ll,ll> printDivisors(ll n,pair<ll,ll> res)
{
    // Note that this loop runs till square root
    for (ll i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i)
                {
                    if(res.first+res.second>i+i)
                    {res.first=i;res.second=i;}
                }

            else // Otherwise print both
                {
                   if(res.first+res.second>i+n/i)
                    {res.first=i;res.second=n/i;}

                }
        }
    }
return res;
}


int main()
{
    ll n;
     cin>>n;
     pair<ll,ll> p;
     p.first=1e14;p.second=1e14;
     p=printDivisors( n,p);
    cout<<p.first+p.second-2;
    return 0;
}


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

#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
#define down(i, x, y) for (int i = (x), _ = (y); i >= _; --i)
#define x first
#define y second

using namespace std;
typedef long long LL;

template<typename T> inline void upmax(T & x, T y) { x < y ? x = y : 0; }
template<typename T> inline void upmin(T & x, T y) { x > y ? x = y : 0; }

template<typename T>
inline void read(T & x)
{
	char c;
	while ((c = getchar()) < '0' || c > '9');
	for (x = c - '0'; (c = getchar()) >= '0' && c <= '9'; x = x * 10 + c - '0');
}

const int mo = 1e9 + 7;
const int N = 9e5 + 10;

int pow_2[N], pow_3[N];
int fac[N], inv[N];
int X, Y, Z, n;

inline int qpow(int x, int n)
{
	int ans = 1;
	while (n)
	{
		if (n & 1)
			ans = (LL) ans * x % mo;
		x = (LL) x * x % mo;
		n >>= 1;
	}
	return ans;
}

inline int C(int n, int m)
{
	if (n < m)
		return 0;
	return (LL) fac[n] * inv[m] % mo * inv[n - m] % mo;
}

inline void upd(int & x, int y)
{
	(x += y) >= mo ? x -= mo : 0;
}

int main()
{
#ifdef LX_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	read(X);
	read(Y);
	read(Z);

	n = X + Y + Z;

	fac[0] = 1;
	rep (i, 1, n)
		fac[i] = (LL) fac[i - 1] * i % mo;
	inv[n] = qpow(fac[n], mo - 2);
	down (i, n, 1)
		inv[i - 1] = (LL) inv[i] * i % mo;

	pow_2[0] = 1;
	rep (i, 1, n)
		(pow_2[i] = pow_2[i - 1] << 1) >= mo ? pow_2[i] -= mo : 0;

	pow_3[0] = 1;
	rep (i, 1, n)
		pow_3[i] = (LL) pow_3[i - 1] * 3 % mo;

	int ans = 0;
	int f = 1, g = 1;

	for (int i = X, c = 0; i <= n; ++i, ++c)
	{
		LL t = (LL) f + g + mo - pow_2[c];
		upd(ans, t * C(i - 1, X - 1) % mo * pow_3[n - i] % mo);
		f = ((LL) f * 2 + mo - C(c, Y)) % mo;
		g = ((LL) g * 2 + mo - C(c, Z)) % mo;
	}

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

	return 0;
}


Measured memory_bytes: 14336
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  while(N != 0){
    vector<int> A(N);
    rep(i,N){
      cin >> A[i];
    }
    sort(A.begin(),A.end());
    int sum = 0;
    for(int i=1; i<N-1; i++){
      sum += A[i];
    }
    cout << sum/(N-2) << endl;
    cin >> N;
  }
  return 0;
}


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

vector<int> adj[100005];
#define ll long long 
ll val[100005]; 
ll n,m; 
ll ans=0; 

ll mi=1000000000000; 
int in; 
bool visited[100005]; 
ll dfs(int u,int p){
		visited[u]=1; 
		if(mi>val[u]){
				mi=val[u]; 
				in=u; 
		}
		for(int i=0;i<adj[u].size();i++){
				int v=adj[u][i]; 
				if(p==v) { continue; }
				else {
						dfs(v,u); 
				}
		}
}

		
int main(){
		cin>>n>>m; 
		for(int i=0;i<n;i++) { cin>>val[i]; }
		for(int i=0;i<m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); }
		if(n==m+1) { cout<<0; return 0; }
		else if (n<2*(n-1-m)) { cout<<"Impossible"; return 0;  }
		set<int> bl; 
		int comp=0; 
		for(int i=0;i<n;i++) { 
				if(!visited[i]) {
						comp++; 
						mi=100000000000000; 
						dfs(i,-1); 
						ans+=mi; 
						bl.insert(in); 
				}
		}
		priority_queue<ll,vector<ll> , greater<ll> > q; 
		for(int i=0;i<n;i++){
				if(bl.find(i)==bl.end()){
						q.push(val[i]); 
				}
		}
		int req=2*(n-1-m)-comp; 
		while(req--){ ans+=q.top(); q.pop(); }
		cout<<ans; 
}




Measured memory_bytes: 8568
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <set>
#include <string>
using namespace std;

int main(){
    int a,b; cin >> a >> b;
    if ( a > 8 || b > 8) cout << ":("<< endl;
    else cout << "Yay!" << endl;
}

Measured memory_bytes: 256