akhauriyash/Code-Regression huggingface dataset:
#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>

using namespace std;

long long result, N,T,a,b,c;
string S;


typedef pair<long long, long long> pl;
vector<pl> re;
vector<pl> bl;
pl buf;

long long Answer[200] = {};


int main() {
	result = 0;
	cin >> S;
	a = 0;
	b = 0;
	c = 0;
	/*for (int i = 0; i < T; i++) {
		if (Answer[i] == -1) {
			cout << "Case #" << i + 1 << ": OK" << endl;
		}
		else {
			cout << "Case #" << i + 1 << ": " << Answer[i] << endl;
		}

	}*/
	for (int i = 0; i < 3; i++) {
		if (S[i] == 'a') {
			a++;
		}
		if (S[i] == 'b') {
			b++;
		}
		if (S[i] == 'c') {
			c++;
		}
	}

	if (a == 1 && b == 1 && c == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	//cout << result << endl;

return 0;
}

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

using namespace std;

const int MAXN=2e5+10;
const int INF=1e9+10;
int N;
int A[MAXN];
int ans[MAXN];
int dp[MAXN];
vector<int> graph[MAXN];

void DFS(int cur,int parent,int max_len){
    int *pos=lower_bound(dp+1,dp+1+max_len,A[cur]);
    auto temp=*pos;
    *pos=A[cur];
    auto len=pos-dp;
    // printf("len=%d\n",len);
    auto new_max=max(max_len,(int)len);
    ans[cur]=new_max;
    for(auto adj:graph[cur]){
        if (adj==parent) continue;
        DFS(adj,cur,new_max);
    }

    *pos=temp;
}

int main(){
    scanf("%d",&N);
    fill(dp+1,dp+3+N,INF);
    for(int i=1;i<=N;i++) scanf("%d",A+i);
    for(int i=0;i<N-1;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        graph[s].push_back(e);
        graph[e].push_back(s);
    }

    DFS(1,1,0);
    for(int i=1;i<=N;i++) printf("%d\n",ans[i]);

    return 0;
}

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

int main()

{
    unsigned long long int n=100;
    unsigned long long int check;
    cin>>check;
    //int ans;

    for(int i=1;i<i+2;i++)
    {
        unsigned long long  temp=(n/100);
        n=n+temp;
        if(n>=check)
        {
            //ans=i;
            cout<<i<<endl;
            return 0;
            //cout<<"there are sum of the first
        }

    }



}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int N; cin >> N;
    vector<pair<string, int>> v(N);
    map<pair<string, int>, int> mp;

    for(int i=0; i<N; i++) { cin >> v[i].first >> v[i].second; v[i].second *= -1; }
    for(int i=0; i<N; i++) mp[v[i]] = i+1;
    sort(v.begin(), v.end());

    for(auto u:v) cout << mp[u] << endl;
}

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

using namespace std;

const int N = 200 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n;
long long a[N], b[N];

bool read() {
    if (!(cin >> n))
        return false;

    for (int i = 0; i < n; ++i)
        cin >> a[i] >> b[i];

    return true;
}

void solve() {
    auto sum = accumulate(a, a + n, 0ll);
    auto mn = sum;

    for (auto i = 0; i < n; ++i)
        if (a[i] > b[i])
            mn = min(mn, b[i]);

    cout << sum - mn << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 640
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define INF 1e+9


int main() {
	int n, k;
	cin >> n >> k;
	if (n % 2 == 1) n++;
	n = n / 2;
	if (n >= k)cout << "YES" << endl;
	else cout << "NO" << endl;


	return 0;
}

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

int main(){
  ll n,k,r,s,p;
  string t;
  cin>>n>>k>>r>>s>>p>>t;
  ll point=0;
  vector<ll>v1(t.size());
  
  for(ll i=0;i<t.size();i++){
    if(t[i]=='r'){
      point+=p;
    }
    else if(t[i]=='s'){
      point+=r;
    }
    else{
      point+=s;
    }
  }
  
  
  for(ll i=t.size()-1;i>=k;i--){
    if(t.at(i)==t.at(i-k)){
      if(v1.at(i)%2==0){
      v1.at(i-k)+=v1.at(i)+1; 
        if(t[i]=='r'){
      point-=p;
    }
        else if(t[i]=='s'){
      point-=r;
    }
        
        else{
      point-=s;
        }
        
      }
      
      else{
        v1.at(i-k)+=v1.at(i)+1;
      }
    }
       
  }
       cout<<point<<endl;
       
     
       
}
       
        
      
  
    

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

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    rep(i,H){
        cin >> a[i];
    }
    vector<bool> row(H, false);
    vector<bool> cul(W, false);
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            if(a[i][j]=='#'){
                row[i] = true;
                cul[j] = true;
            }
        }
    }
    for (int  i = 0; i < H; i++)
    {
        if(row[i]){
            for (int  j = 0; j < W; j++)
            {
                if(cul[j]){
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  cin >> c;
  if(c == 'a'||c == 'i'||c == 'u'||c == 'e'||c == 'o'){
    cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
import scala.io.StdIn.readInt
import scala.annotation.tailrec

object Main {
  @tailrec def fib(a:Int, b:Int, c:Int, n:Int):Int = {
    n match {
      case 0 => a
      case n => fib(a+b, a, b, n-1)
    }
  }

  def main(args: Array[String]) = {
    val n = readInt()
    println(fib(1, 0, 0, n))
  }
}

Measured memory_bytes: 43620
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
#define INF 0x3f3f3f3f
int n,m,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=10;j<=m;j++)
			if(j%10>=2&&j/10>=2&&(j%10)*(j/10)==i)
				ans++;
	printf("%d",ans);
}

Measured memory_bytes: 128
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>
#include <random>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

random_device seed_gen;
mt19937 engine(seed_gen());
// 0, 1, 2 のどれかが得られる一様分布
// uniform_int_distribution<> dist(0, 2);
// cout << dist(engine) << endl;
// みたいに、先に確率分布を宣言して、そこにengineを与えて使う。

// =========ここまでテンプレ============

int main()
{
    ll n;
    cin >> n;
    vector<char> c(n);
    rep(i, n) cin >> c[i];
    ll count = 0;
    ll l = 0;
    ll r = n - 1;
    while (l < r)
    {
        if (c[l] == 'W' && c[r] == 'R')
        {
            ++count;
            ++l;
            --r;
        }
        else if (c[l] == 'W' && c[r] != 'R')
        {
            --r;
        }
        else if (c[l] != 'W' && c[r] == 'R')
        {
            ++l;
        }
        else
        {
            ++l;
            --r;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3196
from collections import deque

def print_postorder(A, B, n):
    C = []
    def reconstruction(l, r):
        if l >= r:
            return
        c = A.popleft()
        m = B.index(c)
        reconstruction(l, m)
        reconstruction(m + 1, r)
        C.append(c)

    reconstruction(0, n)
    print(*C, sep=" ")

n = int(input())
A = deque([int(i) for i in input().split()])
B = [int(i) for i in input().split()]
print_postorder(A, B, n)


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

int main()
{
  int N, M;
  cin >> N >> M;
  long mod = pow(10, 9) + 7;
  long ans = 0;
  if (abs(N - M) < 2)
  {
    int in_min = min(N, M);
    int in_max = max(N, M);
    ans = in_min;
    rep(i, in_min - 1)
    {
      ans *= (i + 1);
      ans %= mod;
    }
    ans *= ans;
    ans %= mod;
    if (in_min == in_max)
    {
      ans *= 2;
      ans %= mod;
    }
    else
    {
      ans *= in_max;
      ans %= mod;
    }
  }

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

Measured memory_bytes: 256
import sys,math
import numpy as np
input = sys.stdin.readline

b_max=0
a_max=0
a = []
b = []
N,H = list(map(int,input().split()))
for i in range(N):
    an,bn = list(map(int,input().split()))
    a.append(an)
    b.append(bn)
    a_max = max(a_max,an)
    b_max = max(b_max,bn)
a = np.array(a)
b = np.array(b)
b = sorted(list(b[b>=a_max]))

cnt = 0
for i in range(len(b)):
    H -= b.pop()
    cnt += 1
    if H <=0:
        print(cnt)
        exit()

cnt += math.ceil(H/a_max)
print(cnt)


Measured memory_bytes: 35136
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int 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 (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int 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 int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	int dp[120] = {};
	long long int a74 = 0;
	long long int a24 = 0;
	long long int a14 = 0;
	long long int a4 = 0;
	long long int a2 = 0;
	for (int i = 1; i <= n; i++) {
		int a = i;
		for (int j = 2; j <= 100; j++) {
			while (a % j == 0) {
				dp[j]++;
				a = a / j;
			}
		}
	}
	int two = 0;
	int other = 0;
	for (int i = 2; i <= 100; i++) {
		if (dp[i] >= 74) {
			a74++;
		}
		if (dp[i] >= 24) {
			a24++;
		}
		if (dp[i] >= 14) {
			a14++;
		}
		if (dp[i] >= 4) {
			a4++;
		}
		if (dp[i] >= 2) {
			a2++;
		}
	}
	long long int ans = 0;
	ans = ans + a74;
	ans = ans + a24 * (a2 - 1);
	ans = ans + a14 * (a4 - 1);
	ans = ans + (a2 - 2) * a4 * (a4 - 1) / 2;
	cout << ans;
}


Measured memory_bytes: 256
N, M = map(float, input().split())

xList = [int(i) for i in input().split()]
xList.sort()

distanse_list = []
if N > M:
    N = M

if N == M:
    print("0")
else:
    for i in range(len(xList)-1):
        distanse = xList[i+1] - xList[i]
        distanse_list.append(distanse)

    distanse_list.sort()
    print(sum(distanse_list[0:int(M - N)]))


Measured memory_bytes: 13840
N = int(input())
L = [int(input()) for _ in range(5)]
minL = 10**16
minIndex = -1
for i in range(5):
  if L[i] < minL:
    minIndex = i
    minL = L[i]
ans = 4 + N//minL
if N%minL != 0: ans += 1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;



#define INF 2000000000
#define MAX_V 10



bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

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

ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}
const ll MAX = 5100000;
const ll MOD = 1000000007;
 
ll fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using graph = vector<vector<ll>>;
pair<pair<ll,ll>,ll> p[100010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll a,b,c;
    cin>>a>>b>>c;
    
    if(a%2==0 || b%2==0 || c%2==0){
        cout<<0<<endl;
        return 0;
    }
    ll split=a/2;
    ll mini=abs(b*c*split-b*c*(a-split));
    split=b/2;
    mini=min(mini,abs(a*c*split-a*c*(b-split)));
    split=c/2;
    mini=min(mini,abs(b*a*split-b*a*(c-split)));
    cout<<mini<<endl;
    return 0;
}

Measured memory_bytes: 256
inputStr = input()
char_list = list(inputStr)

N = len(char_list)

cnt1 = (N - 1)/2
cnt1 = int(cnt1)
cnt2 = (N + 3)/2
cnt2 = int(cnt2)

str1 = []
str2 = []

i = 0
while i < cnt1:
    str1.append(char_list[i])
    i += 1

i = cnt2 -1
while i < N:
    str2.append(char_list[i])
    i += 1

if str1 == str2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
n,k,x,y = IR(4)
print(min(k,n)*x+max(n-k,0)*y)
#B

#C
"""
n,a = LI()
x = LI()
s = sum(x)
dp = [[[0 for i in range(s+1)] for j in range(n+1)] for k in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = 1
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(s+1):
            if k >= x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
            else:
                dp[i][j][k] = dp[i-1][j][k]
ans = 0
for i in range(1,n+1):
    if a*i <= s:
        ans += dp[n][i][a*i]
print(ans)
"""

#D
"""
def f(b,n):
    m = n
    res = 0
    while m > 0:
        res += m%b
        m //= b
    return res
n,s = IR(2)
if n == s:
    print(n+1)
    quit()
if n == 1:
    print(-1)
    quit()
k = int(n**0.5)
for b in range(2,k+1):
    if f(b,n) == s:
        print(b)
        quit()
for p in range(1,k+1)[::-1]:
    if (n-s)%p == 0:
        b = (n-s)//p+1
        if b != 0:
            if f(b,n) == s:
                print(b)
                quit()
print(-1)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 38512
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int N = readInt(reader);

            System.out.println(N * N * N);
        }
    }

    public static int readInt(BufferedReader reader) throws Exception {
        return Integer.parseInt(reader.readLine());
    }

}


Measured memory_bytes: 22992
n = int(input())
x = list(map(int, input()))

dp = [0] * n

for i in range(n):
    num = i
    while num:
        num2 = num
        cnt = 0
        while num2:
            if num2 & 1:
                cnt += 1
            num2 >>= 1

        num %= cnt
        dp[i] += 1

one_cnt = x.count(1)
mod1 = one_cnt - 1
mod2 = one_cnt + 1

sm1 = 0
sm2 = 0
for i, e in enumerate(x):
    if e == 0:
        continue

    if mod1 != 0:
        sm1 += pow(2, n - i - 1, mod1)
        sm1 %= mod1

    sm2 += pow(2, n - i - 1, mod2)
    sm2 %= mod2

for i, e in enumerate(x):
    if mod1 == 0 and e:
        print(0)
        continue

    if e:
        val = sm1 - pow(2, n - i - 1, mod1)
        val %= mod1

    else:
        val = sm2 + pow(2, n - i - 1, mod2)
        val %= mod2

    ans = dp[val] + 1
    print(ans)


Measured memory_bytes: 12768
#include<bits/stdc++.h>
#define ll long long int
#define db long double
#define ull unsigned long long int
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
#define Nmax 1000005
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
 
using namespace std;

ll dp[200005];
ll seg[800005];

void update(ll node,ll tl,ll tr,ll pos,ll val)
{
	if(pos>tr || pos<tl) return ;
	if(pos==tl && pos==tr)
	{
		seg[node]=val;
		return ;
	}
	ll tm=(tl+tr)/2;
	if(pos<=tm) update(2*node,tl,tm,pos,val);
	else update(2*node+1,tm+1,tr,pos,val);
	seg[node]=max(seg[2*node],seg[2*node+1]);
}

ll query(ll node,ll tl,ll tr,ll l,ll r)
{
	if(l>tr || tl>r) return 0;
	if(l<=tl && r>=tr)
	{
		return seg[node];
	}
	ll tm=(tl+tr)/2;
	ll left=query(2*node,tl,tm,l,r);
	ll right=query(2*node+1,tm+1,tr,l,r);
	return max(left,right);
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    int tests=1;
    // compute();
    // cin>>tests;
    while(tests--)
    {
    	ll i,j,k,n;
    	cin>>n;
    	vector<ll>h(n+1),a(n+1),ind(n+1,0);
    	rep(i,1,n) cin>>h[i];
    	rep(i,1,n) cin>>a[i];

    	dp[1]=a[1];
    	update(1,1,n,h[1],a[1]);
    	rep(i,2,n)
    	{
    		ll val=query(1,1,n,1,h[i]);
    		dp[i]=val+a[i];
    		update(1,1,n,h[i],dp[i]);
    	}
    	ll ans=0;
    	rep(i,1,n) ans=max(ans,dp[i]);
    	cout<<ans;

    }
    	return 0;
    
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define int ll
//const ll mod = 1000000007;

int n;
int b[100010], a[100010];

signed main() {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (b[i] >= (a[i] + a[i + 1])) {
            ans += a[i] + a[i + 1];
            a[i] = 0;
            a[i + 1] = 0;
        } else if (b[i] >= a[i]) {
            ans += b[i];
            a[i + 1] -= (b[i] - a[i]);
            a[i] = 0;
        } else {
            ans += b[i];
            a[i] -= b[i];
        }

    }

    cout << ans << endl;
}

// 貪欲法

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

int main() {
    ll l, k;
    cin >> l >> k;

    ll dp[2][105] = {0};
    // tebann, takasa,
    dp[0][1] = 1;
    dp[0][k] = 1;

    rep(j, l) rep(i, 2) {
        // cout << i << " " << j << endl;
        if (dp[i][j] == 0) continue; // noseru
        dp[i ^ 1][j + 1] += dp[i][j];
        if (i == 1) dp[i ^ 1][j + k] += dp[i][j];

        // cout << i << " " << j << endl;
        // rep(_, 2) { rep(__, l + 1) cout << dp[_][__] << " "; cout << endl; }
    }

    ll ans = 0;
    rep(i, l + 1) ans += dp[0][i];
    cout << ans << endl;

    // rep(i, 2) { rep(j, l + 1) cout << dp[i][j] << " "; cout << endl; }

}



Measured memory_bytes: 3084
n=int(input())
cnt=[[0]*10 for i in range(10)]
for i in range(1,n+1):
  s=str(i)
  cnt[int(s[0])][int(s[-1])]+=1
ans=0
for i in range(10):
  for j in range(10):
    ans+=cnt[i][j]*cnt[j][i]
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int N=2010,M=200020,mod=1e9+7;
ll n,m,T,k,cnt,x,y,z,a[M],b[M],f[N][N],g[N][N];
string s;
int main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++)
	{
		cin>>s;
		ll x=0;
		m=s.size();
		int flag=0;
		for (int i=0;i<m;i++)
		{
			if (s[i]>='0'&&s[i]<='9') x=x*10+s[i]-'0';
			if (s[i]=='.') y=i+1,flag=1;
		}
		if (!flag) y=m;
		while (x%2==0) x/=2,a[i]++;
		while (x%5==0) x/=5,b[i]++;
		a[i]-=m-y; b[i]-=m-y;
		f[1000-a[i]][1000-b[i]]++;
		g[1000+a[i]][1000+b[i]]++;
		//a[i]+=1000; b[i]+=1000;
	}
	//for (int i=1;i<=n;i++) printf("%lld %lld\n",a[i]-1000,b[i]-1000);
	ll ans=0;
	for (int i=0;i<=2000;i++)
		for (int j=0;j<=2000;j++)
		{
			if (i>1&&j>1) f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
			else if (i>1) f[i][j]=f[i-1][j]+f[i][j];
			else if (j>1) f[i][j]=f[i][j-1]+f[i][j];
			ans+=g[i][j]*f[i][j];
		}
	/*
	for (int i=990;i<=1010;i++)
	{
		for (int j=990;j<=1010;j++) printf("%lld ",f[i][j]);puts("");
	}
	for (int i=990;i<=1010;i++)
	{
		for (int j=990;j<=1010;j++) printf("%lld ",g[i][j]);puts("");
	}
	*/
	for (int i=1;i<=n;i++) if (a[i]>=0&&b[i]>=0) ans--;
	ans/=2;
	printf("%lld\n",ans);
}

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

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
char capitalize(char c) { return static_cast<char>(std::toupper(static_cast<unsigned char>(c))); }
// template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
// template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

// #define int long long
#define YES "YES"
#define NO  "NO"

using namespace std;

signed main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int num = 0;
  // num = numeric_limits<int>::max();
  // num = numeric_limits<int>::min();
  bool flag = false;
  // flag = true;

  int n; cin >> n;

  num = 800 * n - 200 * (n / 15);
  
  cout << num << endl;
  // cout << (flag ? "H" : "D") << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int64_t MOD=1000000007;
const long long INF = 1LL<<60;

int main() {
  int64_t N,K,ans=-1*INF; cin>>N>>K;
  vector<int64_t> P(N);
  rep(i,N) cin>>P.at(i);
  rep(i,N) P.at(i)--;
  vector<int64_t> C(N);
  rep(i,N) cin>>C.at(i);

  rep(i,N){
    vector<bool> seen(N,true);
    vector<int64_t> S,T;
    int64_t k=i,sum=0;
    while(seen.at(k)){
      seen.at(k)=false;
      S.push_back(C.at(k));
      sum+=C.at(k);
      k=P.at(k);
    }
    int64_t t=S.size(),r=K/t,q=K%t,MAX=-1*INF,NMAX,MAX2=-1*INF;
    rep(i,t){
      T.push_back(S.at(i));
      if(i>0) T.at(i)+=T.at(i-1);
      if(T.at(i)>MAX){
        MAX=T.at(i);
        NMAX=i+1;
      }
    }
    if(q==0) ans=max(ans,MAX+sum*(r-1));
    else{
      if(q<NMAX){
        rep(i,q) MAX2=max(MAX2,T.at(i));
        if(sum<0) ans=max(ans,MAX);
        else{
          auto temp=max(MAX+sum*(r-1),MAX2+sum*r);
          ans=max(ans,temp);
        }
      }
      else{
        if(sum<0) ans=max(ans,MAX);
        else ans=max(ans,MAX+sum*r);
      }
    }
  }
  cout<<ans;
}

Measured memory_bytes: 3736
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 100002;
int dp[N];
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt",  "r", stdin);
    //freopen("output.txt", "w", stdout);
    int q, h, s, d, n;
    cin >> q >> h >> s >> d;
    cin >> n;
    n *= 4;
    dp[0] = 0;
    for (int i = 1; i <= min((int)100000, n); i++){
        dp[i] = 1e18;
        if (i >= 1) dp[i] = min(dp[i], dp[i - 1] + q);
        if (i >= 2) dp[i] = min(dp[i], dp[i - 2] + h);
        if (i >= 4) dp[i] = min(dp[i], dp[i - 4] + s);
        if (i >= 8) dp[i] = min(dp[i], dp[i - 8] + d);
    }
    if (n < 100000){
        cout << dp[n];
        return 0;
    }
    int k1 = 8 * q;
    int k2 = 4 * h;
    int k3 = 2 * s;
    int k4 = d;
    int t = min({k1, k2, k3, k4});
    int ans = 0;
    if (t == k1){
        int x = n / 1;
        n -= x * 1;
        ans += x * q;
        ans -= 10000 * q;
        n += 10000;
        ans += dp[n];
        cout << ans;
        return 0;
    }
    if (t == k2){
        int x = n / 2;
        n -= x * 2;
        ans += x * h;
        ans -= 10000 * h;
        n += 20000;
        ans += dp[n];
        cout << ans;
        return 0;
    }
    if (t == k3){
        int x = n / 4;
        n -= x * 4;
        ans += x * s;
        ans -= 10000 * s;
        n += 40000;
        ans += dp[n];
        cout << ans;
        return 0;
    }
    if (t == k4){
        int x = n / 8;
        n -= x * 8;
        ans += x * d;
        ans -= 10000 * d;
        n += 80000;
        ans += dp[n];
        cout << ans;
        return 0;
    }
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n;
	string s;
	cin>>n>>s;
	int a[301010]={};
	FOR(i,0,n){
		if(s[i]=='E')a[i]=1;
		//cout<<a[i]<<" ";
	}
	//cout<<a[0]<<" ";
	FOR(i,1,n){
		a[i]+=a[i-1];
		//cout<<a[i]<<" ";

	}
	//cout<<endl;
	int mn=a[n-1]-a[0];
	FOR(i,1,n){
		mn=min(mn,i-a[i-1]+a[n-1]-a[i]);
		//cout<<i-a[i-1]+a[n-1]-a[i]<<" ";

	}
	cout<<mn<<endl;

    return 0;
}


Measured memory_bytes: 1796
#include <iostream>
#include <vector>
#include <array>
#include <cmath>
 
using namespace std;
#define ll long long
 
int main()
{
	// Value
	ll N;
	string s,t;
	ll result;
 
	// Input
	cin >>N;
	cin >>s;
	cin >>t;
 
	// Cal
	ll startpos = 0;
	if(s.size() < t.size()){
		startpos = 0;
	}else{
		startpos = s.size() - t.size();
	}
	for(int i=startpos;i<s.size()+1;++i){
		bool is_matching = true;
		for(int j=0;j<(s.size()-i);++j){
			if(s[i+j] != t[j]){
				is_matching = false;
				break;
			}
		}
		if(is_matching){
			if(s.size() < t.size()){
				result = t.size() + i;
			}else{
				result = startpos + t.size() + i;
			}
			
			break;
		}
	}
 
	// Output
	cout <<result<< endl;
 
	// Fin
	return 0;
}

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

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1000000007;

int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);
  int h,w;
  cin>>h>>w;
  string s[h];
  for(int i=0; i<h; i++){
    cin>>s[i];
  }

  int dp[h+1][w+1];
  for(int i=0; i<=h; i++){
    for(int j=0; j<=w; j++){
        dp[i][j]=0;
    }
  }
  dp[1][1]=1;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
        if(i!=1||j!=1){
            if(s[i-1][j-1]!='#'){dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;}
        }
    }
  }

  cout<<(dp[h][w]+mod)%mod;

  return 0;
}

Measured memory_bytes: 8516
#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 FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll a, b, c, d;
  cin >> a >> b >> c >> d;

  ll ans = -INF;
  if (a <= 0 && b >= 0) chmax(ans, 0LL);
  if (c <= 0 && d >= 0) chmax(ans, 0LL);
  chmax(ans, a * c);
  chmax(ans, a * d);
  chmax(ans, b * c);
  chmax(ans, b * d);
  cout << ans << '\n';

  

  

  
  return 0;
}

Measured memory_bytes: 3660
import std.functional,
       std.algorithm,
       std.container,
       std.typetuple,
       std.typecons,
       std.bigint,
       std.string,
       std.traits,
       std.array,
       std.range,
       std.stdio,
       std.conv;

void main() {
  int[] NK = readln.chomp.split.to!(int[]);
  int N = NK[0],
      K = NK[1];
  int[] A = readln.chomp.split.to!(int[]);
  int ans = 1;
  int cnt = K;

  ans += (N - K) / (K - 1);
  if ((N - K) % (K - 1) != 0) {
    ans++;
  }

  writeln(ans);
}


Measured memory_bytes: 3772
#include<stdio.h>
int main(void)
{
		int a,b,c,d,e,f,x;
		scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
		x=a*1+b*5+c*10+d*50+e*100+f*500;
		if(x>=1000) printf("1\n");
		else printf("0\n");
		return 0;
}	

Measured memory_bytes: 2688
/*
 * cpp_filepath
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


void solve() {
  string S[] = {"Left", "Balanced", "Right"};
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  a += b; c += d;
  if (a == c) cout << S[1] << endl;
  else if (a > c) cout << S[0] << endl;
  else cout << S[2] << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  unordered_map<int,int> mp;
  for(int i = 0; i < N; i++){
    mp[A[i]] = i + 1;
  }
  
  for(int i = 1; i < N + 1; i++){
    cout << mp[i] << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 5284
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n,a,b,c,d; cin >>n>>a>>b>>c>>d;
    a--;
    b--;
    c--;
    d--;
    string s; cin >> s;

    if (c < d) {
        
        for (int i = b+1; i < d; i++) {
            char c = s[i];
            if (s[i+1] == '#' && c == '#') {
                cout << "No" << endl;
                return 0;
            } 
        }
        for (int i = a+1; i < c; i++) {
            char c = s[i];
            if (s[i+1] == '#' && c == '#') {
                cout << "No" << endl;
                return 0;
            } 
        }
        cout << "Yes" << endl;
        return 0;

    } else {

        //bがdまでいけない
        for (int i = b+1; i < d; i++) {
            char c = s[i];
            if (s[i+1] == '#' && c == '#') {
                cout << "No" << endl;
                return 0;
            } 
        }

        //bを先に動かすとき
        bool flag1 = false;
        for (int i = b; i <= d; i++) {
            if (s[i-1] == '.' && s[i] == '.' && s[i+1] == '.') {
                flag1 = true;
            } 
        }
        //aがcまでいけない
        for (int i = a+1; i < c; i++) {
            char c = s[i];
            if (s[i+1] == '#' && c == '#') {
                flag1 = false;
            }
        }

        //aを先に動かすとき
        bool flag2 = true;
        //aがcまでいけない
        s[b] = '#';
        for (int i = a+1; i < c; i++) {
            char c = s[i];
            if (s[i+1] == '#' && c == '#') {
                flag2 = false;
            }
        }

        if (flag2 || flag1) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }

        return 0;
    }
}




Measured memory_bytes: 640
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W, A, B = getNM()

"""
0, ?の場合は対応可能

0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 1 1

対応出来ないケース無さそう？
1, 2の場合は？

これは1, 2
1 1 1 1 0
1 1 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
"""

res = [[''] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if (i < B) ^ (j < A):
            res[i][j] = str(0)
        else:
            res[i][j] = str(1)
res = [''.join(i) for i in res]
for i in res:
    print(i)

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

const int SPQR = 20005;

vector<int> a, b, p;

int main(void) {
    int n;

    cin >> n;
    a.resize(n);
    b.resize(n);
    p.resize(n);

    for(auto &i: p) {
        cin >> i; --i; }

    for(int i = 0; i < n; ++i) {
        a[p[i]]+= i;
        a[i]+= (n + 1) * (i + 1);
        b[i]+= (n + 1) * (n - i); }

    for(auto i: a) cout << i << ' ';
    cout << '\n';
    for(auto i: b) cout << i << ' ';

    return 0; }


Measured memory_bytes: 896
#include <stdio.h>
int N=100;

int main(){
  int M[N][N];
  int n,u,k,v,i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++) M[i][j]=0;
  }
  
  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      M[u][v]=1;
    }
  }
  
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){      
      printf("%d",M[i][j]);
      if(j<n-1) printf(" ");
    }
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 2052
mod = 1000000007

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

dp = [[0] * (m+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]) % mod
        if s[i-1] == t[j-1]: 
            dp[i][j] = (dp[i][j] + dp[i-1][j-1] + 1) % mod
print((dp[n][m]+1) % mod)

Measured memory_bytes: 98676
n = int(input())
p = list(map(int, input().split()))

count = 0

for i in range(1, n-1):
    n3 = [
            p[i-1],
            p[i],
            p[i+1]
        ]
    n3.sort()
   
    if n3[1] == p[i]:
        count += 1
print(count)

Measured memory_bytes: 3060
/*****************************************************
 *     created by: nayakashutosh9
 * "Winners Never Quit and Quitters Never Win".
*****************************************************/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace __gnu_pbds;
using namespace std;
#define int long long int
#define endl '\n'
#define mod 1000000007
#define inf 1e18
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 300005;
/**********************************************************************************************/


void solve() {
	int n, k; cin >> n >> k;
	vector<int> a(n, 0);
	for (int i = 0; i < k; i++) {
		int d; cin >> d;
		for (int j = 0; j < d; j++) {
			int x; cin >> x;
			a[x - 1]++;
		}
	}
	int ans = count(a.begin(), a.end(), 0);
	cout << ans << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1, z = 1;
	// cin >> t; cin.ignore();
	while (t--) {
		// cout << "Case #" << (z++) << ": ";
		// clock_t start = clock();
		solve();
		// clock_t end = clock();
		// cout << (end-start) << endl;
		//print execution time in ms
	}

	return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <stdlib.h> 
typedef struct{
    int k,l,r;
}Node;
void insert(int, int);
void inParse(int);
void preParse(int);
Node T[500001];
int main(void)
{
    char s[8];
    int m;
    int num,count=0;
    int i;
   
    scanf("%d", &m);  
    for(i=0; i<m; i++){
        scanf("%s", &s);
        if(s[0]=='i'){ 
          scanf("%d", &num); 
          insert(count, num); 
          count++; 
        }
        if(s[0]=='p'){
          if(count>0) inParse(0);
            printf("\n");
            if(count>0) preParse(0);
            printf("\n");
        }
    }  
    return 0;  
}
   
void inParse(int p){
    if(T[p].l>=0) inParse( T[p].l);
    printf(" %d", T[p].k);
    if(T[p].r>=0) inParse( T[p].r);
}
   
void preParse(int p){
    printf(" %d", T[p].k);
    if(T[p].l>=0) preParse(T[p].l);
    if(T[p].r>=0) preParse(T[p].r);
}
   
void insert(int count, int z){
    int x=0, y;
    if(count<1) x=-1;
   
    T[count].k = z;
    T[count].l = -1;
    T[count].r = -1;
   
    while(x>=0){
        y = x; 
        if(z < T[x].k)x = T[x].l; 
        else x = T[x].r; 
    }
    if(count<1){}
    else if(z < T[y].k)T[y].l = count; 
    else T[y].r = count; 
}


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

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FI first
#define SE second
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;

const double EPS = 1e-9;
const double PI = acos(-1);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

ll addMod(ll a, ll b){
	return (a+b) % MOD;
}

ll mulMod(ll a, ll b){
	return (a*b) % MOD;
}

/////////////////////////////////////////////////////////

typedef long double ld;
const int N = 1000;

struct point{
	ld x,y;
}p[N + 5], st, en;

ld square(ld a){
	return a*a;
}

ld getDist(point a, point b){
	return (ld)sqrt(square(a.x - b.x) + square(a.y - b.y));
}

vector < pair < int , double > > G[N + 5];
bool vis[N + 5];
ld r[N + 5];
int n;
ld solve(){
	priority_queue < pair < ld, int > > pq;
	while(!pq.empty()) pq.pop();
	pq.push(MP(0, 0));
	while(!pq.empty()){
		ld dist = -pq.top().FI;
		int now = pq.top().SE;
		pq.pop();
		if(vis[now]) continue;
		if(now == n+1) return dist;
		vis[now] = true;
		FOR(i,G[now].size()){
			int nxt = G[now][i].FI;
			ld dt = G[now][i].SE;
			if(!vis[nxt]){
				pq.push(MP(-(dist + dt), nxt));
			}
		}
	}
	return 0;
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> st.x >> st.y >> en.x >> en.y;
	cin >> n;
	REP(i,1,n) cin >> p[i].x >> p[i].y >> r[i];
	p[0] = st;
	p[n+1] = en;
	REP(i,0,n){
		REP(j,i+1,n+1){
			ld dist = getDist(p[i], p[j]) - r[i] - r[j];
			dist = max((ld)0, dist);
			G[i].PB(MP(j,dist));
			G[j].PB(MP(i,dist));
		}
	}
	cout << fixed << setprecision(10) << solve() << endl;
	return 0;
}

Measured memory_bytes: 34920
s = input()
fir = int(s[:2])
sec = int(s[2:])
# print(fir, sec)
if fir == 0:
    if sec == 0:
        print('NA')
    elif 0 < sec <= 12:
        print('YYMM')
    else:
        print('NA')
elif 0 < fir <= 12:
    if sec == 0:
        print('MMYY')
    elif 0 < sec <= 12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if sec == 0:
        print('NA')
    elif 0 < sec <= 12:
        print('YYMM')
    else:
        print('NA')


Measured memory_bytes: 3060
import sys
def input(): return sys.stdin.readline().strip()


def prod_max(a, d, b, e, n):
    """
    初項a、公差dの等差数列および初項b、公差eの等差数列を各項ごとに
    掛け合わせた時の第0項から第n項までの最大値を返す。
    a>0, d>0, b>0, e<0を仮定する。
    """
    if n < 0: return 0
    idx = round((-(b / e) - (a / d)) / 2)
    if idx < 0: return a * b
    if idx <= n: return (a + idx * d) * (b + idx * e)
    return (a + n * d) * (b + n * e)

def main():
    """
    解説放送にしたがって決め打ち二分探索による実装。
    まずa<=bを仮定しても良い。a*bよりも小さい積がX個作れるかを考える。
    これは1, 2, ..., a-1, a+1, ...からX個、1, 2, ..., b-1, b+1, ...からX個選んで
    小さいものと大きいもののペアで積を取ったものが全てa*b未満であることをいえば良い。

    積を実際に全て計算していては間に合わないが、実質これは等差数列の積なので
    これらの積のうち最大値はO(1)で計算可能。
    """
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        if a > b: a, b = b, a

        # 決め打ち二分探索
        left = a - 1
        right = 10 ** 10
        while right - left > 1:
            mid = (left + right) // 2
            if mid < b:
                """
                この時ペアリングは
                1*mid, 2*(mid-1), ..., (a-1)*(mid-a+1), (a+1)*(mid-a), ..., (mid+1)*1
                前半後半でそれぞれ最大値を取得する。
                """
                cand1 = prod_max(1, 1, mid, -1, a-2)
                cand2 = prod_max(a+1, 1, mid-a+1, -1, mid-a)
                if cand1 < a * b and cand2 < a * b: left = mid
                else: right = mid
                #print("case1 left={}, right={}".format(left, right))
            elif mid < a + b - 1:
                """
                この時ペアリングは
                1*(mid+1), 2*mid, ..., (mid-b+1)*(b+1),
                (mid-b+2)*(b-1), ..., (a-1)*(mid-a+2),
                (a+1)*(mid-a+1), ..., (mid+1)*1
                より3つに分けて最大値を求める。
                """
                cand1 = prod_max(1, 1, mid+1, -1, mid-b)
                cand2 = prod_max(mid-b+2, 1, b-1, -1, a+b-mid-3)
                cand3 = prod_max(a+1, 1, mid-a+1, -1, mid-a)
                if cand1 < a * b and cand2 < a * b and cand3 < a * b: left = mid
                else: right = mid
                #print("case2 left={}, right={}".format(left, right))
            else:
                """
                この時ペアリングは
                1*(mid+1), 2*mid, ..., (mid-a+3)*(a-1),
                (a+1)*(mid-a+2), ..., (mid-b+2)*(b+1),
                (mid-b+3)*(b-1), ..., (mid+1)*1
                より3つに分けて最大値を求める。
                """
                cand1 = prod_max(1, 1, mid+1, -1, a-2)
                cand2 = prod_max(a+1, 1, mid-a+2, -1, mid-a-b+1)
                cand3 = prod_max(mid-b+3, 1, b-1, -1, b-2)
                if cand1 < a * b and cand2 < a * b and cand3 < a * b: left = mid
                else: right = mid
                #print("case3 left={}, right={}".format(left, right))
        print(left)


if __name__ == "__main__":
    main()


Measured memory_bytes: 69060
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 1e2+7 , INF = 0x3f3f3f3f , mz = 1e9+7;
const double PI = acos(0.0) * 2;
template<typename T1>
T1 gcd(T1 a , T1 b){ return b ? gcd(b,a%b) : a;}

int h,w,n;
int p[N*N] , c[N][N];

int main(){
#ifdef LOCAL
    freopen("F:\\c++\\in.txt", "r", stdin);
//  freopen("F:\\c++\\out.txt","w",stdout);
#endif
    scanf("%d%d%d",&h,&w,&n);
    for(int i = 1 ; i <= n ; i++){
        scanf("%d",p+i);
    }
    int top = 1;
    for(int i = 1 ; i <= h ; i++){
        if( i&1 ){
            for(int j = 1 ; j <= w ; j++){
                while( !p[top] && top <= n )    top++;
                p[top]--;
                c[i][j] = top;
            }
        }else{
            for(int j = w ; j > 0 ; j--){
                while( !p[top] && top <= n )    top++;
                p[top]--;
                c[i][j] = top;
            }
        }
    }
    for(int i = 1 ; i <= h ; i++){
        printf("%d",c[i][1]);
        for(int j = 2 ; j <= w ; j++){
            printf(" %d",c[i][j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 384