akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

fn main() {
    let (h, w): (usize, usize) = read();
    let table: Vec<String> = readn(h);
    let table: Vec<Vec<char>> = table.into_iter().map(|a| a.chars().collect()).collect();

    let mut diff: Vec<Vec<bool>> = vec![vec![false; w-1]; h];
    for i in 0..h {
        for j in 0..w-1 {
            diff[i][j] = table[i][j] == table[i][j+1];
        }
    }


    let mut ans = max(w, h);

    let mut height: Vec<usize> = vec![0; w-1];
    for i in 0..h {
        for j in 0..w-1 {
            let f = diff[i][j];
            if height[j] == i {
                while height[j] < h && diff[height[j]][j] == f {
                    height[j] += 1;
                }
            }
        }

        let mut h: Vec<usize> = vec![0; w-1];
        for j in 0..w-1 {
            h[j] = height[j] - i;
        }
        ans = max(ans, doit(h));
    }

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

fn doit(a: Vec<usize>) -> usize {
    let n = a.len();
    let mut right: Vec<usize> = vec![0; n];
    {
        let mut stk: Vec<usize> = vec![];
        for i in (0..n).rev() {
            while stk.len() >= 1 && a[i] <= a[stk[stk.len()-1]] {
                stk.pop();
            }
            right[i] = if stk.len() >= 1 { stk[stk.len()-1] } else { n };
            stk.push(i);
        }
    }

    let mut left: Vec<usize> = vec![0; n];
    {
        let mut stk: Vec<usize> = vec![];
        for i in 0..n {
            while stk.len() >= 1 && a[i] <= a[stk[stk.len()-1]] {
                stk.pop();
            }
            left[i] = if stk.len() >= 1 { stk[stk.len()-1]+1 } else { 0 };
            stk.push(i);
        }
    }

    let mut ans = 0;
    for i in 0..n {
        ans = max(ans, (right[i] - left[i] + 1) * a[i]);
    }
    ans
}

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

int main() {
	int a,b,t;
	cin >> a >> b >> t;
	int co = t/a;
	cout << co*b << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <climits>
#include<map>
#include<cstdio>

#define ll long long
#define MAX 1000000000
#define INF 1000000000

int main() {
        string s1,s2;
        cin>>s1>>s2;
        int i, n, cnt=0;
        n=s1.length();
        for(i=0;i<n;i++){
            if(s1[i]!=s2[i])
                cnt++;
        }
        cout<<cnt<<endl;

}

Measured memory_bytes: 3840
A = int(input())
B = int(input())

if A == 1 and B == 3:
    print(2)
elif A == 1 and B == 2:
    print(3)
elif A == 2 and B == 1:
    print(3)
elif A == 2 and B == 3:
    print(1)
elif A == 3 and B == 1:
    print(2)
elif A == 3 and B == 2:
    print(1)

Measured memory_bytes: 9056
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int T[110];
    rep(i, N) cin >> T[i];
    int M; cin >> M;
    int p[110], x[110];
    rep(i, M) {
        cin >> p[i] >> x[i];
        p[i]--;
    }
    int sum = 0;
    rep(i, N) sum += T[i];
    rep(i, M) {
        cout << sum - T[p[i]] + x[i] << endl;
    }

    return 0;
}


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

int main(){
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    
    int minv = 1e9;
    int ans = -1e9;
    
    for(int i = 1; i < n; i++){
        minv = min(a[i-1],minv);
        ans = max(a[i]-minv,ans);
    }
    cout << ans << endl;
}




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

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5; 
int a[N];

int main()
{
	//freopen("1.in","r",stdin);
	int n;cin>>n;
	rep(i,1,n)scanf("%d",a+i);
	s64 ans=0;
	rep(i,1,n)
	{
		ans+=a[i]/2;
		a[i]%=2;
		if(a[i]&&a[i+1])
		{
			++ans;
			--a[i+1];
		}
	}
	cout<<ans;
}

Measured memory_bytes: 640
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int main(){
    long long n;
    cin>>n;
    vector<long long> hoge(n);
    map<long long,long long> num;
    
    for(long long i=0;i<n;i++){
        cin>>hoge.at(i);
        
        if(num.count(hoge.at(i))){
            num.at(hoge.at(i))++;
        }else{
            num[hoge.at(i)]=1;
        }
    }
    
    map<long long,long long> plus;
    map<long long,long long> minus;
    long long sum=0;
    
    for(auto a:hoge){
        if(num.at(a)!=-1){
            long long cnt=num.at(a);
            
            plus[a]=(cnt*(cnt-1))/2;
            sum+=plus.at(a);
            minus[a]=((cnt-1)*(cnt-2))/2;
            
            num.at(a)=-1;
        }
    }
    
    for(auto a:hoge){
        cout<<sum-plus.at(a)+minus.at(a)<<endl;
    }
    
    return 0;
}

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

using namespace std;
#define ll long long


int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int q;
    cin >> q;
    int b, e, t;
    while(q--) {
        cin >> b >> e >> t;
        swap_ranges(a + b, a + e, a + t);
    }

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];

    return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int main(){
  string s,t;
  cin >> s >> t;
  int x=int(s.size());
  int y=int(t.size());
  if(x<y)
    s="UNRESTORABLE";
  else{
    for(int i=x-y;i>=0;i--){
      bool c=0;
      for(int k=i;k<i+y;k++){
        if(s.at(k)!='?'&&s.at(k)!=t.at(k-i))
          c=1;
      }
      if(!c){
        rep(j,y)
          s.at(i+j)=t.at(j);
        break;
      }
      if(i==0)
        s="UNRESTORABLE";
    }
  }
  rep(i,int(s.size()))
    if(s.at(i)=='?')s.at(i)='a';
  cout << s << endl;
}
  

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

int main() {
	int n, m, a, b = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a;
		b = b + a;
	}
	if (n < b) {
		cout << "-1\n";
	}
	else {
		cout << n - b << "\n";
	}
	return 0;
}

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

typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 1e9;

int main() {
  int n, k;
  cin >> n >> k;
  int mx = (n-1)*(n-2)/2;
  if (mx < k) {
    puts("-1");
    return 0;
  }
  vector<pair<int, int> > ans;
  for(int i = 0; i < n-1; i++) {
    ans.push_back({i+1,n});
  }
  int add = mx-k;
  vector<pair<int, int> > edge;
  for(int i = 0; i < n-1; i++) {
    for(int j = 0; j < i; j++) {
      edge.push_back({i+1,j+1});
    }
  }
  for(int i = 0; i < add; i++) {
    ans.push_back(edge[i]);
  }
  cout << ans.size() << endl;
  for(int i = 0; i < ans.size(); i++) {
    cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}

Measured memory_bytes: 384
a = gets.chomp.to_i
b = gets.chomp.to_i
c = gets.chomp.to_i
total = gets.chomp.to_i

count = 0

(0..a).each do |i|
    if 500 * i <= total
      (0..b).each do |j|
        if 500 * i + 100 * j <= total
          (0..c).each do |k|
            if 500 * i + 100 * j + 50 * k == total
             count += 1
            end
          end
        end
      end
    end
  end

  puts count

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

int main() {
    int N;
    string res = "No";
    int c = 25;
    int d = 15;

    cin >> N;
    for (int i=0; i<=c; ++i) {
      for (int j=0; j<=d; ++j) {
        if (N == (4*i + 7*j)) res = "Yes";
      }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

    int n,k;
    cin >> n >> k;

    vector<int> h(n);
    rep(i,n) cin >> h[i];

    int ans=0;

    rep(i,n){
        if(h[i] >= k) ans++;
    }
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
  int r,d,x,ans;
  cin>>r>>d>>x;
  for(int i=0;i<10;i++)
  {
   ans=r*x-d;
  	x=ans;
  	cout<<ans<<"\n";
  	ans=0;
  }

}

Measured memory_bytes: 256
#include<stdio.h>
int c[100000];
int main()
{
    int n,i,j,k,l,t;
    scanf("%d",&n);
    i=n%10;
    n/=10;
    j=n%10;
    n/=10;
    k=n%10;
    n/=10;
    t=n%10;
    if((i==j && j==k )||(t==k && k==j))printf("Yes\n");
    else
        printf("No\n");
        return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << n/3 <<endl;

    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

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

typedef long long int64;

class DHandstand2 {
 public:

  void solveOne(std::istream &in, std::ostream &out) {
    int n;
    in >> n;

    int dp[10][10] = {};

    for (int k = 1; k <= n; ++k) {
      int last = k % 10;
      int tmp = k;
      while (tmp >= 10)tmp /= 10;
      int first = tmp;
      dp[first][last]++;
    }

    int64 ans = 0;

    for (int i = 0; i < 10; ++i)
      for (int j = 0; j < 10; ++j) {
        ans += dp[i][j] * dp[j][i];
      }
    out << ans << endl;

  }
  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int i = 0; i < nt; ++i)
      solveOne(in, out);
  }
};

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

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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    
    int ans = 1e9;
    for (int i = -100; i <= 100; ++i) {
        int res = 0;
        rep(j, N) res += (a[j] - i) * (a[j] - i);
        ans = min(ans, res);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	if(a==b && b==c){
		cout<<1;
	}else if(a!=b && b!=c&& c!=a){
		cout<<3;
	}else{
		cout<<2;
	}
}

Measured memory_bytes: 256
program prob4
    implicit none
    integer(8) :: n
    character(10), allocatable :: a(:)
    character(10) :: s(10)
    integer(8) :: i, j
    integer(8) :: ans
    integer(8) :: cnt
    character(10) :: tmp

    read(*,*) n
    allocate(a(n))
    do i = 1, n
        read(*,*) tmp
        do j = 1, 10
            s(j) = tmp(j:j)
        end do
        call msort(s)
        a(i) = ''
        do j = 1, 10
            a(i) = trim(adjustl(a(i))) // trim(adjustl(s(j)))
        end do
    end do

    call msort(a)

    cnt = 1
    tmp = a(1)
    ans = 0
    do i = 2, n
        if(a(i) == tmp)then
            cnt = cnt + 1
        else
            ans = ans + cnt * (cnt - 1) / 2
            tmp = a(i)
            cnt = 1
        end if
    end do
    ans = ans + cnt * (cnt - 1) / 2

    write(*,*) ans



    deallocate(a)

    stop
contains


  !
  ! swap two arguments
  !
subroutine swap(a, b)
    implicit none
    character(10), intent(inout) :: a, b

    character(10) :: c

    c = a
    a = b
    b = c

  end subroutine swap

  !
  ! merge sort
  !
  recursive subroutine msort(x)
    implicit none
    character(10), intent(inout) :: x(:)

    integer(8) :: n, mid, i, j, k
    character(10), allocatable :: tmp(:)
    
    n = size(x)
    
    if(n == 1) then
      return
    end if

    !
    ! 前半と後半に分けてソート
    ! 1~midとmid+1~nをそれぞれソート済みにする
    !
    mid = n / 2
    call msort(x(:mid))
    call msort(x(mid+1:))

    !
    ! tmpという配列にxを一時的に保管
    ! マージソートは外部ソート
    !
    allocate(tmp(n))
    tmp = x

    ! tmpの後半部分を左右反転
    do k = n, mid+1, -1
      tmp(k) = x(mid + n - k + 1)
    end do

    ! iは前半のリストのうちまだ見ていないものの最小値
    ! jは後半のリストのうちまだ見ていないものの最小値
    ! kは見た回数の合計
    i = 1
    j = n

    do k = 1, n
      !
      ! 一番左と一番右のうち小さい方をxに入れていく
      ! ここが等号つき不等号なので、安定ソートとなる
      !
      if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
      else
        x(k) = tmp(j)
        j = j - 1
      end if
    end do
    
    deallocate(tmp)
    return
  end subroutine msort
end program prob4

Measured memory_bytes: 4896
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long a,b,sum,sai=0,i;
  cin>>a>>b;
  sum=a*b;
  sai=min(a,b);
  i=sai;
  while(sai<sum){
    if(!(sai%a)&&!(sai%b)){
      cout<<sai<<"\n";
      return 0;
    }
    sai+=i;
  }
  cout<<sai<<"\n";
  return 0;
}
    


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

int isPrime(int x)
{
	int i;
	if(x<2)return 0;
	else if(x==2)return 1;
	if(x%2==0)return 0;
	for(int i=3;i*i<=x;i+=2)
	{
		if(x%i==0)return 0;
	}
	return 1;
}

int main()
{
	int n,a,b,p[100005]={};
	for(int i=1;i<=100000;i+=2)
	{
		if(isPrime(i)&&isPrime((i+1)/2))p[i]++;
	}
	for(int i=1;i<=100000;i++)
	{
		p[i]+=p[i-1];
	}
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a>>b;
		cout<<p[b]-p[a-1]<<endl;
	}
	return 0;
}
	

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const int INF = 0x3f3f3f3f;
using namespace std;

int n, arr[100001][3];
ll dp[100001][3];

ll solve(int i = 0, int lst = 0) {
    if (i==n) {
        return 0;
    }
    if (i==0) {
        return max(arr[i][0] + solve(i+1, 0), max(arr[i][1] + solve(i+1, 1), arr[i][2] + solve(i+1, 2)));
    }
    ll& ret = dp[i][lst];
    if (~ret) {
        return ret;
    }
    if (lst == 0) {
        return ret = max(arr[i][1] + solve(i+1, 1), arr[i][2] + solve(i+1, 2));
    }
    if (lst == 1) {
        return ret = max(arr[i][0] + solve(i+1, 0), arr[i][2] + solve(i+1, 2));
    }
    return ret = max(arr[i][0] + solve(i+1, 0), arr[i][1] + solve(i+1, 1));
}
int main()
{
    IOS
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j != k) {
                    dp[i][k] = max(dp[i][k], dp[i-1][j]+arr[i-1][k]);
                }
            }
        }
    }
    cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;



    return 0;
}


Measured memory_bytes: 3840
#include <iostream>

using namespace std;

int main(){
    int N, m, maxm, h, preh, c, maxc;
    c = -1;
    m = maxm = h = preh = maxc = 0;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> h;
        if(h <= preh){
            c++;
            if(c > maxc){
                maxm = m;
                maxc = c;
            }
        }
        else{
            m = i;
            c = 0;
        }
        preh = h;
    }
    cout << maxc << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            s = s.Replace("eraser", "");
            s = s.Replace("erase", "");
            s = s.Replace("dreamer", "");
            s = s.Replace("dream", "");

            Console.WriteLine(s.Length == 0 ? "YES" : "NO");
        }
    }
}


Measured memory_bytes: 13140
#include  <bits/stdc++.h>
using namespace std;
static int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
int main(){
  long long int n,k;
  cin>>n>>k;
  while(n%k<n){
    n=n%k;
  }
  while(abs(n-k)<n){
    n=abs(n-k);
  }
  cout<<n<<"\n";  
  return 0;
}

Measured memory_bytes: 256
# your code goes here
N = int(input())

direction = input()

ruiseki_W = [0]
ruiseki_E = [0]
num_W = 0
num_E = 0
ans = 1145141919
for i in range(N):
	if direction[i] == 'W':
		num_W += 1
	else:
		num_E += 1
	ruiseki_W.append(num_W)
	ruiseki_E.append(num_E)
	
for i in range(N):
	ans = min(ans,ruiseki_W[i]+(ruiseki_E[N] - ruiseki_E[i+1]))
	# print(ruiseki_W[i]+(ruiseki_E[N] - ruiseki_E[i+1]))
# print(ruiseki_W,ruiseki_E)
print(ans)

Measured memory_bytes: 17732
//Name: Where's Your Robot?
//Level: 1
//Category: シミュレーション,練習問題
//Note:

/**
 * 問題文の通りにシミュレーションする。
 */
#include <iostream>
#include <string>

using namespace std;

const int DR[] = {1, 0, -1, 0};
const int DC[] = {0, -1, 0, 1};

bool solve() {
    int W, H;
    if(!(cin >> W >> H)) return false;
    if(!W && !H) return false;

    int r = 1, c = 1, dir = 0;
    while(true) {
        string cmd;
        cin >> cmd;
        if(cmd == "FORWARD") {
            int d;
            cin >> d;
            r = max(1, min(H, r + DR[dir] * d));
            c = max(1, min(W, c + DC[dir] * d));
        } else if(cmd == "BACKWARD") {
            int d;
            cin >> d;
            r = max(1, min(H, r - DR[dir] * d));
            c = max(1, min(W, c - DC[dir] * d));
        } else if(cmd == "RIGHT") {
            dir = (dir + 3) % 4;
        } else if(cmd == "LEFT") {
            dir = (dir + 1) % 4;
        } else if(cmd == "STOP") {
            break;
        }
    }
    cout << c << ' ' << r << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1216
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: Chars,
    }

    for i in 0..n.len() {
        if n[i]=='9' {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


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

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

vector<pair<ll, int>> factorize(ll n) {
  vector<pair<ll, int>> res;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i) continue;
    res.emplace_back(i, 0);
    while (n % i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n, 1);
  return res;
}

int main() {
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a, b);
  auto f = factorize(g);
  int ans = f.size() + 1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define repn(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) for(int i = 0; i < (a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

int dp[100005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n, k;
	cin >> n >> k;
	int a[n + 1];
	repn(i, 1, n + 1){
		cin >> a[i];
	}
	repn(i, 1, k + 1){
		repn(j, 1, n + 1){
			if(i >= a[j] && !dp[i - a[j]]){
				dp[i] = 1;
			}
		}
	}
	cout << (dp[k] ? "First" : "Second") << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 768
#include <iostream>
using namespace std;
int eval(int *l, char *c, int n, int i){
  switch (c[i]) {
    case '+':
    {
      int sum = 0;
      for(int k = i+1 ; l[i+1] <= l[k] && i < n ; k++){
        if(l[i+1] == l[k]){
          sum += eval(l,c,n,k);
        }
      }
      return sum;
    }
    case '*':
    {
      int prod = 1;
      for(int k = i+1 ; l[i+1] <= l[k] && i < n ; k++){
        if(l[i+1] == l[k]){
          prod *= eval(l,c,n,k);
        }
      }
      return prod;
    }
    default:
      return c[i] - '0';
  }
}
int main(void){
  for(;;){
    int n;
    cin >> n;
    if(n == 0){ return 0; }
    int  l[n];
    char c[n];
    for(int i = 0 ; i < n ; i++){
      string s;
      cin >> s;
      l[i] = s.length();
      c[i] = s[l[i]-1];
    }
    cout << eval(l,c,n,0) << endl;
  }
}



Measured memory_bytes: 3164
import java.util.*;
import java.util.stream.*;
import java.io.*;
class Main {
  public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.lines()
      .skip(1)
      // .parallel()
      .map(line -> Stream.of(line.split(" "))
                    .mapToInt(Integer::parseInt)
                    .map(n -> n * n)
                    .sorted()
                    .toArray())
      .map(ar -> (ar[0] + ar[1] == ar[2]) ? "YES" : "NO")
      // .sequential()
      .forEach(System.out::println);
  }
}

Measured memory_bytes: 32532
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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 TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

S = input()

if S[-1] == "s":
	print(S+"es")
else:
	print(S+"s")

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

const long long MOD = 1e9 + 7;

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL

int n, k;
vector<int>v;
int memo[101010];

bool solve(int pos){
	
	if(memo[pos] != -1) return memo[pos] ? false : true;
	
	bool outcome = false;
	
	for(int i = 0 ; i < n ; i ++){
		if(pos - v[i] >= 0) outcome |= solve(pos - v[i]);
		if(outcome) break;
	}
	
	memo[pos] = outcome;
	
	return outcome ? false : true;
}

int main(){
	
	ios::sync_with_stdio(false); cin.tie(0);
	
	memset(memo, -1, sizeof memo);
	
	cin>>n>>k;
	
	v.resize(n);
	
	for(int i = 0 ; i < n ; i ++)
		cin>>v[i];
	
	memo[0] = 0;
	
	solve(k);
	
	if(memo[k]) cout<<"First\n";
	else cout<<"Second\n";
	
	return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	ll ans = 0;
	ll sum = 0;
	map <int, int> MA;
	MA[0]++;
	REP(i, N) {
		int in;
		cin >> in;
		sum += in;
		int val = sum % M;
		ans += MA[val];
		MA[val]++;
	}
	cout << ans << endl;
	PAU;
	return 0;
}




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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
  int n;cin >> n;
  int  a[2 * 100000 + 1];
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] -= i;
  }

  sort(a + 1, a + n + 1);
  int b1 = a[n / 2 + 1];
  int b2 = a[n / 2];
  ll ans1 = 0;
  ll ans2 = 0;
  for(int i = 1; i <= n; i++) {
    ans1 += abs(a[i] - b1);
    ans2 += abs(a[i] - b2);
  }

  cout << min(ans1, ans2) << endl;

}


Measured memory_bytes: 1024
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <tuple>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
#define MAX_N 100000
#define MAX_M 200000
using namespace std;

class edge{
  public:
    int u, v, c;
    edge(int u, int v, int c): u(u), v(v), c(c){}
    edge(){}
};

vector< edge > graph[MAX_N];

void dfs(int v, int x[], bool visited[]){
  visited[v] = true;
  for(edge e: graph[v]){
    int w = e.v;
    if(!visited[w]){
      x[w] = x[v] + e.c;
      dfs(w, x, visited);
    }
  }
}

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

  int n, m;
  cin >> n >> m;
  int l[MAX_M], r[MAX_M], d[MAX_M];
  for(int i = 0; i < m; i++){
    cin >> l[i] >> r[i] >> d[i];
    --l[i]; --r[i];
  }

  if(m == 0){
    cout << "Yes" << endl;
    return 0;
  }

  for(int i = 0; i < m; i++){
    graph[l[i]].push_back(edge(l[i], r[i], d[i]));
    graph[r[i]].push_back(edge(r[i], l[i], -d[i]));
  }

  int x[n];
  fill(x, x + n, -1);
  bool visited[n];
  fill(visited, visited + n, false);
  for(int s = 0; s < n; s++){
    if(!visited[s]){
      x[s] = 0;
      dfs(s, x, visited);
    }
  }

  bool exist = true;
  for(int i = 0; i < m; i++){
    if(x[r[i]] - x[l[i]] != d[i]){
      exist = false; break;
    }
  }

  if(exist) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int,int>> p(n);
  for (auto&pa : p) {
    int x, l;
    cin >> x >> l;
    pa = make_pair(x+l, x-l);
  }
  sort(p.begin(), p.end());

  int ans = 0, cur = -2e9;
  for (auto&pa : p) {
    int s = pa.second, e = pa.first;
    if (s >= cur) {
      ans++;
      cur = e;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

class Graph {
	int n;
	vector<vector<int>> node;
	vector<int> res, d;

public:
	Graph(int N) : n(N), node(N), res(N), d(N, INT_MAX) {}
	void add(int a, int b) {
		node[a].emplace_back(b);
		node[b].emplace_back(a);
	}
	void bfs() {
		d[0] = 0;
		queue<int> qu;
		qu.emplace(0);
		while (!qu.empty()) {
			int i = qu.front();
			qu.pop();
			for (auto &j : node[i]) {
				if (d[j] > d[i] + 1) {
					d[j] = d[i] + 1;
					res[j] = i + 1;
					qu.emplace(j);
				}
			}
		}
	}
	void solve() {
		bfs();
		cout << "Yes\n";
		FOR(i, 1, n) {
			cout << res[i] << endl;
		}
	}
};

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

	int N, M;
	cin >> N >> M;
	Graph graph(N);
	REP(i, M) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		graph.add(a, b);
	}
	graph.solve();

	return 0;
}


Measured memory_bytes: 10692
#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;

const int Nmax = 2e5 + 5;

int n, L[Nmax], R[Nmax], Lmax;
vector<int> ord;
int lmax[Nmax], rmin[Nmax];


bool cmp(int x, int y)
{
    return R[x] < R[y];
}

int main()
{
    //freopen("inputB", "r", stdin);
    // freopen("output", "w", stdout);
    cin.sync_with_stdio(false); cin.tie(0);
    
    cin >> n;
    int i;
    for(i=1; i<=n; ++i)
        cin >> L[i] >> R[i];

    int longest = 0;

    for(i=1; i<=n; ++i)
    {
        longest = max(longest, R[i] - L[i] + 1);
        Lmax = max(Lmax, L[i]);
        ord.push_back(i);
    }

    sort(ord.begin(), ord.end(), cmp);
    
    for(i=0; i<n; ++i)
        lmax[i] = max( (i ? lmax[i-1] : 0), L[ord[i]]),
        rmin[i] = min( (i ? rmin[i-1] : INT_MAX), R[ord[i]]);
   
    int ans = 0;

    for(i=0; i<n-1; ++i)
    {
        int curr = 0;

        curr += max(0, rmin[i] - lmax[i] + 1);
        curr += max(0, R[ord[i+1]] - Lmax + 1);
        
        ans = max(ans, curr);
    }

    int curr;
    curr = max(0, R[ord[0]] - Lmax + 1);
    curr += longest;

    ans = max(ans, curr);
    cout << ans << '\n';

    return 0;
}



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

int main() {
    ll N, C, K; cin >> N >> C >> K;

    vector<ll> T(N+1, -1);
    vector<ll> T_angry(N+1, -1);
    for(ll i=1; i<N+1; i++){
        cin >> T.at(i);
    }
    sort(T.begin(), T.end());
    for(int i=1; i<N+1; i++){
        T_angry.at(i) = T.at(i) + K;
    }

    ll cnt = 1;
    ll people = 1;
    ll tmp_b = T_angry.at(1);
    for(ll i=2; i<N+1; i++){
        people++;

        if(people == C+1){
            tmp_b = T_angry.at(i);
            cnt++;
            people = 1;
            continue;
        }

        if(T.at(i) > tmp_b){
            tmp_b = T_angry.at(i);
            cnt++;
            people = 1;
            continue;
        }
    }

    cout << cnt << endl;

}

Measured memory_bytes: 1792
n,a,b=map(int,input().split())
ac=0
bc=0
for i in input():
  if i=='a':
    if ac+bc<a+b:
      print('Yes')
      ac+=1
      continue
  elif i=='b':
    if ac+bc<a+b and bc<b:
      print('Yes')
      bc+=1
      continue
  print('No')

Measured memory_bytes: 53080
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
const int INF = 1e9;
const ll MOD = 1000000007;
const ll LINF = 1e18;
using namespace std;



int main() {
    ll a, b, n,x, ans;
    
    cin>>a>>b>>n;
    
    x = b-1;
    if(x>n) x = n;
    
    ans = ((a*x)/b) - a * (x/b);
    
    cout<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  int n,k;
  cin >> n >> k;
  
  vector<int> a(n,0);
  REP(i,n){
    cin >> a[i];
  }
  
  sort(a.begin(), a.end());
  
  int ans = 0;
  
  REP(i,k){
    ans += a[i];
  }
  
  cout << ans << endl;
    
  

}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in insert
#define mp make_pair
#define F first
#define pb push_back
#define pf push_front
#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test ll t; cin>>t; while(t--)
ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}
ll exp(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x); x=(x*x); y/=2; } return res;}

int main(){
    string s; cin>>s;
    if(s[2]== s[3] && s[4]==s[5])
        cout<<"Yes";
    else cout<<"No";
    
    
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

using ll = long long;
using namespace std;

ll M = 1000000007;



int main()
{
  int h,n;
  cin>>h>>n;
  int sum=0;
  rep(i,n){
      int t;
      cin>>t;
      sum+=t;
  }
  if(sum>=h){
      cout<<"Yes"<<endl;
  }else{
      cout<<"No"<<endl;
  }
}

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

using namespace std;
 
int main(){

    int n;
    cin >> n;

    vector<int> v;
    vector<int> m;

    int count = 1;


    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
        if(i == 0){
            m.push_back(tmp);
        }else{
            if(tmp >= m[i - 1]){
                count++;
                m.push_back(tmp);
            }else{
                m.push_back(m[i - 1]);
            }
        }
    }

    cout << count << endl;



    return 0;
}

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

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

/* define const */
const long long INF = (1LL << 60);
/* end defineing */

int main()
{
    bool f = false;
    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;

    if (a + k < e)
        f = true;

    if (f)
        cout << ":(" << endl;
    else
        cout << "Yay!" << endl;
}


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

int main() {
  long long N,D;
  cin >> N >> D;
  vector<long long> X(N),Y(N);
  for (int i=0;i<N;i++) {
    cin >> X.at(i) >> Y.at(i);
  }
  int c=0;
  for (int i=0;i<N;i++) {
    if ((X.at(i)*X.at(i)+Y.at(i)*Y.at(i))<=D*D) {
      c++;
    }
  }
  cout << c << endl;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    string s;
    cin >> s;
    int n = s.size();
    bool a[26];
    rep(i, 26) a[i] = false;

    rep(i, n) {
        a[s[i] - 'a'] = true;
    }

    rep(i, 26) {
        if(!a[i]) {
            cout << (char)(i + 'a') << endl;
            return 0;
        }
    }

    cout << "None" << endl;

    return 0;
}

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

void fast() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
}

const int N = 200005;

const int inf = 2e9;

int dp[3][N];
int a[3][N];

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

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

   dp[0][0] = a[0][0];
   dp[1][0] = a[1][0];
   dp[2][0] = a[2][0];


   for(int i = 1; i < n; i++) {
      for(int j = 0; j < 3; j++) {
         for(int k = 0; k < 3; k++) {
            if(j == k) continue;
            dp[j][i] = max(dp[j][i], dp[k][i - 1] + a[j][i]);
         }
      }
   }

   cout << max({dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]}) << endl;

   return 0;
}


Measured memory_bytes: 3712
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		for (int i = 1; i <= b; i++) {
			if (a * i % b == c) {
				System.out.println("YES");
				return;
			}
		}
		System.out.println("NO");
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <unordered_map>
#include <algorithm>

#define ll long long

using namespace std;
int x, k, q, t, a, low, up, add, delta, now, ans, r[100007];
bool flag;

int cal(int tt, int lower = 0, int upper = x) {
    if (tt < lower) return lower;
    if (tt > upper) return upper;
    return tt;
}

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

    cin >> x >> k;
    for (int i = 1; i <= k; i++) cin >> r[i];
    cin >> q;

    low = x, now = 1;
    while (q--) {
        cin >> t >> a;
        while (t >= r[now] && now <= k) {
            delta = (flag ? 1 : -1) * (r[now] - r[now - 1]), add += delta;
            up = cal(delta + up), low = cal(delta + low);
            flag = !flag, now++;
        }
        ans = cal((flag ? 1 : -1) * (t - r[now - 1]) + cal(a + add, up, low));
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n;
    cin >> n;
    int a[1000001];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 1;
    int first = 1;
    for(int i = 3; i <= n; i++){
        if((a[first] < a[i - 1]) && (a[i - 1] > a[i])){
            ans++;
            first = i;
            i++;
            continue;
        }
        if((a[first] > a[i - 1]) && (a[i - 1] < a[i])){
            ans++;
            first = i;
            i++;
        }
    }
    cout << ans << endl;
        return 0;
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
#define pb push_back
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define F first
#define S second
const int NUM = 2e5 + 5;

signed main(){
    int t = 1; //cin >> t;
    while(t--){
        string s; cin >> s;
        if(s[s.size()-1] == 's')
        {
            cout << s << "es";
        }
        else cout << s << "s";
    }    
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
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;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ll n;
vector<ll> num; // num[0] +(-) num[1] +(-) ... +(-) num[n-2] = num[n-1]
ll dp[101][21];

void input()
{
    cin >> n;
    num.resize(n);
    for (ll i = 0; i < n; i++)
        cin >> num[i];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    memset(dp,0,sizeof(dp));
    dp[0][num[0]] = 1;
    for (ll i = 0; i < n - 1; i++)
    {
        for (ll _sum = 0; _sum <= 20; _sum++)
        {
            if (_sum - num[i+1] >= 0 && _sum - num[i+1] <= 20)
            {
                dp[i + 1][_sum] += dp[i][_sum - num[i+1]];
            }
            if (_sum + num[i+1] <= 20 && _sum + num[i+1] >= 0)
            {
                dp[i + 1][_sum] += dp[i][_sum + num[i+1]];
            }
        }
    }
    cout << dp[n-2][num[n-1]] << endl;
    return 0;
}



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

int gcd(long long  x, long long  y) {
    long long  tmp;
    while ((fmod(x, y)) != 0) {
        tmp = y;
        y = fmod(x, y);
        x = tmp;
    }
    return y;
}

int main() {
    long long  a,b;
    cin >> a >> b;
    long long  lcd = (a * b) / gcd(max(a, b), min(a, b));
    cout << lcd << endl;
    return 0;
}

Measured memory_bytes: 256
#!/mnt/c/Users/moiki/bash/env/bin/python
Q = int(input())
qs = [ tuple(map(int, input().split())) for _ in range(Q)]
for i in range(Q):
    # A,B = map(int, input().split())
    A,B = qs[i]
    A,B = min(A,B), max(A,B)
    if A == B:
        C = A
        print(2*(C-1))
    elif B == A+1:
        C = A
        print(C-1 + C-1)

    else:
        C = int( (A*B)**(1/2))
        if C**2 == A*B:
            C=C-1

        if C*(C+1) >= A*B:
            print(2*C-2)
        else:
            print(2*C-1)



        continue
        C = A
        n = B - C
        ans = C-1
        # print("NONE")

        MIN = 1
        MAX = B-1 +1 # CANNOT BE
        middle = (MIN+MAX)//2

        # i = (MIN+MAX)//2
        i = middle
        # while (A*B)//(i+1) >= A+1 and not ((A*B//i != (A*B)//(i+1))and(A*B//(i+1) != A*B//(i+2))): # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :

        # while (A*B)//(i+1) >= A+1 and MAX - MIN > 1: # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :
        while MAX - MIN > 1: # (A*B)//i != (A*B)//(i+1) and (A*B)//(i+1) >= A+1 :
            if (A*B-1) // i != (A*B-1)//(i+1) and (A*B-1)//i >= A+1:
                MIN = middle
                i = middle = (MIN+MAX)//2
            else:
                MAX = middle
                i = middle = (MIN+MAX)//2
                

        print("min: {}, max: {}".format(MIN, MAX))
        print(ans + i)
            

        # s = set()
        # for i in range(1,1+C+n):
        #     if (A*B//i) in s:
        #         break
        #     else:
        #         s.add(A*B//i)
        # ans += i
        # print(ans)





Measured memory_bytes: 38384
#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 ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int N;
  cin >> N;

  if (N < 105) {
    cout << 0;
  } else if (N == 105) {
    cout << 1;
  } else {
    int cnt = 0;
    for (int i = 107; i <= N; i += 2) {
      int divi = 0;
      FOR(l, 1, i+1) {
        if (i % l == 0) divi++;
      }
      if (divi == 8) {
        cnt++;
      }
    }
    cout << cnt + 1;
  }
}

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

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

	if(b<=a) {
		cout << "delicious" << endl;
	} else {
		if(b<=a+x) {
			cout << "safe" << endl;
		} else {
			cout << "dangerous" << endl;
		}
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// #define debug(a) cout << "["; rep(i,a.size()) cout << a[i] << ", "; cout<<"]"<< endl;

const ll mod = 1000000007;

int main() {
    ll x, k, d; cin >> x >> k >> d;
    ll mostCloseX = x % d;
    ll needMove = abs(x % d - x) / d;
    if(needMove >= k) {
        if(x < 0){
            cout << abs(x + d * k) << endl;
        } else {
            cout << abs(x - d * k) << endl;
        }
        return 0;
    }
    ll leftMove = k - needMove;
    if(leftMove % 2 == 0){
        cout << abs(mostCloseX) << endl;
    } else {
        cout << min(abs(mostCloseX + d), abs(mostCloseX - d)) << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
MOD = 10**9 + 7
H, W, K = map(int, input().split())
table = [[0, 0, 0] for i in range(9)]

for i in range(2**(W-1)):
    n = [i & 2**j for j in range(8)]
    for i in range(7):
        if n[i] and n[i+1]:#真横にかかるとき
            break
    else:
        i = 0
        while i < W:
            if not n[i]:
                table[i+1][1] += 1
                i += 1
            else:
                table[i+1][2] += 1
                table[i+2][0] += 1
                i += 2
dp = [[0 for i in range(W+2)] for j in range(H+1)]
dp[0][1] = 1

for i in range(1, H+1):
    for j in range(1, W+1):
        a = dp[i-1][j-1] * table[j][0]
        b = dp[i-1][j] * table[j][1]
        c = dp[i-1][j+1] * table[j][2]
        dp[i][j] = (a+b+c) % MOD
print(dp[H][K])

Measured memory_bytes: 3064