akhauriyash/Code-Regression huggingface dataset:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

# import numpy as np


## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

# import bisect

class BIT:

	def __init__(self,size):
		self.N = size
		self.bit = [0] * (self.N+1)

	def getSum(self,i):
		s = 0
		while 0 < i:
			s += self.bit[i]
			i -= i & -i

		return s

	def getMax(self,i):
		s = 0
		while 0 < i:
			s = max(s, self.bit[i])
			i -= i & -i

		return s

	def add(self,i,val):
		while i <= self.N:
			# for range summary query
			# self.bit[i] += val
			# for range maximum query
			self.bit[i] = max( self.bit[i], val )
			i += i & -i

def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = BIT(N)
	for n in range(N):
		tree.add( H[n], tree.getMax(H[n]) + A[n] )

	lis = tree.getMax(N)

	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()


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

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

    int n, a[100000], b[100000], c[100000], dp[100000][3];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
    }
    cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
    return 0;
}


Measured memory_bytes: 5916
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
 
int main(){
  	int a;
  	string s,ans;
  	cin >> s;
  	a = s.size();
  	for (int i = 0; i < a; i++) {
		ans += "x";
	}   
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)

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

    int n;
    cin >> n;
    int r[n];
    REP(i, n) cin >> r[i];

    int maxProfits = -2e9, tempMin = r[0];
    FOR(i, 1, n) {
        maxProfits = max(maxProfits, r[i] - tempMin);
        tempMin = min(tempMin, r[i]);
    }
    cout << maxProfits << endl;
    return 0;
}

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


#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;
typedef double ld;

ll mod = 1e9 + 7ll;
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 (b<a) { a=b; return 1; } return 0; }
const ll inf = 1ll << 60;

int main(){
    vector<int> t;
    int last = 139;
    int lastidx = -1;
    rp(i, 0, 5){
        int a;
        cin >> a;
        t.emplace_back(a);
        if(a%10 != 0 and a%10 <= last%10){
            last = a;
            lastidx = i;
        }
    }
    int ans = 0;
    rp(i, 0, 5){
        if(i != lastidx){
            if(t.at(i)%10 == 0) ans += t.at(i);
            else ans += (t.at(i)/10 + 1) * 10;
        }
    }
    if(lastidx!=-1) ans += t.at(lastidx);
    cout << ans;
    return 0;

    
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5+5;
int n, k, p;
char s[N];
bool bit[N];
int main()
{
    scanf("%d%d%s", &n, &k, s+1), s[n+1] = 'B';
    // for(p = n-1; p >= 1&&s[p+1]== 'A'&&s[p] == 'B'; p -= 2); p += 2;
    // for( ; k&&p > 2; --k)
    // {
    //     if(s[1] == 'A') s[1] = 'B';
    //     else
    //     {
    //         for(int i = 1; i < p; ++i)
    //         {
    //             if(s[i] == 'B'&&s[i+1] != 'A') s[i] = 'A';
    //             else for( ; s[i+1] == 'A'; ++i) s[i] = 'B';
    //         }
    //         for(p -= 2; p >= 1&&s[p+1]== 'A'&&s[p] == 'B'; p -= 2); p += 2;
    //     }
    //     printf("%s\n", s+1);
    // }
    for(int i = 1; i <= n; ++i) bit[i] = s[i] != s[i+1];
    for(p = 1; p <= n&&k; --k)    
        if(s[1] == 'A') s[1] = 'B', bit[p] ^= 1;
        else if(bit[p] == 0) s[1] = 'A', ++p;
        else ++p;
    if(p <= n)
    {
        for(int i = p+1; i <= n+1; ++i) s[i-p+1] = ((s[i-p]-'A')^bit[i-1])+'A';
        for(int i = n-p+3; i <= n; ++i) s[i] = ((s[i-1]-'A')^1)+'A';
    }
    else for(int i = 1; i <= n; ++i) s[i+(n&1)] = 'A'+(i&1);
    if(k&&(n&1)) s[1] = ((s[1]-'A')^(k&1))+'A'; s[n+1] = 0;
    printf("%s\n", s+1);
    return 0;
}
/*
11 22
ABBBABABABA

ABBBABABAB
1001111110
BBBBABABAB
0001111110
AAABABABAA
0011111101
BAABABABAA
1011111101
BBABABABBA
0111111011
ABABABAABA
1111110111
BBABABAABA
0111110111
ABABABBABA
1111101111
BBABABBABA
0111101111
ABABAABABA
1111011111
BBABAABABA
0111011111
*/

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

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	int L, R;
	int nijigen[501][501] = {};
	repeat(i, M) {
		cin >> L >> R;
		nijigen[L][R] += 1;
	}
	int p[100000], q[100000];
	repeat(i, Q) {
		cin >> p[i] >> q[i];
	}
	int ruikei[502][502] = {};
	repeat(i, N) {
		repeat(ii, N) {
			ruikei[i + 1][ii + 1] = ruikei[i + 1][ii] + nijigen[i + 1][ii + 1];
		}
	}
	repeat(ii, N) {
		repeat(i, N) {
			ruikei[N - i][ii + 1] = ruikei[N - i + 1][ii + 1] + ruikei[N - i][ii + 1];
		}
	}
	repeat(i, Q) {
		cout << ruikei[p[i]][q[i]] << "\n";
	}
	Would you return 0;
}

Measured memory_bytes: 3712
# _*_ coding:utf-8 _*_
#  Atcoder_Grand_Contest031-A
#  TODO https://atcoder.jp/contests/agc031/tasks/agc031_a
from collections import Counter

def solveProblem(S):
	# Sはサンプル3の[abcab]を取って説明
	SSorted = sorted(S)
	# SSorted = aabbc
	stringCounterBox = Counter(SSorted)
	# [(a,2),(b,2),(c,1)]
	maxStrLength = len(stringCounterBox)
	# 文字そのものを並べる文字列長さは 1から3まで
	# print("maxStringLength:{}".format(maxStrLength))
	countList = list(stringCounterBox.values())
	# [2,2,1] と 各文字数だけ取り出した配列になった
	# print("countList:{}".format(countList))
	'''
	戦略
	1個の時→1個の配列を取り出した物を足す→2 + 2 + 1 = 5
	2個の時→取り出す文字は文字毎に数字だけパターンが替わる→ 2*2 + 2*1 + 2* 1 = 8
	3個の時 同上→ 2*2*1 = 4
	これ以上の取り出しはもう出来ない:同じ文字が出てくるため
	5 + 8 + 4 = 17 と答えと一致した
	TODO 取り出す配列番号を調べる方法が不明
	この場合なら2個の時0番目と1番目,0番目と2番目,1番目と2番目を洗い出すのはどうするのか？
	偉い人の回答待ち
	'''
	counter = 1
	for i in range(0,len(countList),+1):

		# counter = (counter * (countList[i]+1)) % (10^9+7)
		counter = (counter*(countList[i]+1)) % (pow(10,9)+7)

	answer = counter-1
	return answer


if __name__ == '__main__':
	_ = int(input().strip())
	S = str(input().strip())
	solution = solveProblem(S)
	print("{}".format(solution))


Measured memory_bytes: 4660
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	UNDEFINED,
	USED,
	EITHER,
};

#define SIZE 300005

int N,R;
int table[SIZE],num[SIZE];
int dp[SIZE];
map<int,bool> MAP;
Type type[SIZE];


int main(){

	scanf("%d %d",&N,&R);

	int num_either;

	for(int i = 1; i <= N; i++){

		scanf("%d",&table[i]);
		if(i == table[i]){

			type[i] = EITHER; //どちらのグループでも良い
			num_either++;
		}else{

			type[i] = UNDEFINED;
		}
	}

	int sum = 0;

	for(int i = 0; i < SIZE; i++){

		num[i] = 0;
	}

	vector<int> V;

	//場所 != 数字となっている数字の、本来の位置を指したループを作る(グループ1)
	for(int i = 1; i <= N; i++){

		if(type[i] == UNDEFINED){

			int count = 0;

			type[i] = USED;
			count++;

			int loc = i;

			while(type[table[loc]] == UNDEFINED){

				type[table[loc]] = USED;
				count++;
				loc = table[loc];
			}

			sum += count;
			num[count] += 1;

			auto at = MAP.find(count); //初登場の数字
			if(at == MAP.end()){

				MAP[count] = true;
				V.push_back(count);
			}
		}
	}

	dp[0] = 0;
	for(int i = 1; i <= N; i++){

		dp[i] = -1;
	}
	for(int i = 0; i < V.size(); i++){ //数の種類のループ
		for(int k = 0; k <= N; k++){ //作りたい数のループ

			if(dp[k] >= 0){

				dp[k] = num[V[i]]; //V[i]の個数

			}else if(k < V[i] || dp[k-V[i]] <= 0){

				dp[k] = -1;

			}else{

				dp[k] = dp[k-V[i]]-1; //V[i]を1つ使用
			}
		}
	}

	for(int i = 0; i <= max(R,N-R); i++){
		if(dp[i] < 0)continue; //数字iを作れないならSKIP

		if(min(i,sum-i) <= min(R,N-R) && max(i,sum-i) <= max(R,N-R)){
			//差分は、eitherを適当に割り振って調整
			printf("Yes\n");
			return 0;
		}
	}

	printf("No\n");

	return 0;
}



Measured memory_bytes: 7908
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int N,A,B;
	cin>>N>>A>>B;
	
	if((B-A)%2==0) cout<<"Alice";
	else cout<<"Borys";
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)


int main(){
    ll N,sum=0;
    cin>>N;
    REP(i,1,N+1){
        if(i%3==0||i%5==0)continue;
        sum+=i;
    }
    cout<<sum<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 3632
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    cout << (n % 2 == 0 ? n / 2 - 1 : n / 2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
//#define mp make_pair
#define pb push_back
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 1000000007
#define F first
#define S second
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
bool isPowerOfTwo(int n)
{
   if(n==0)
   return false;

   return (ceil(log2(n)) == floor(log2(n)));
}
int power(int x, unsigned int y)
{
    int res = 1;

    x = x;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x);

        y = y>>1;
        x = (x*x);
    }
    return res;
}
bool isprime(int x)
{
      if(x<2)
        return false;
    for(int i=2;i*i<=x;i++)
     {
        if (x%i==0)
            return false;
    }
    return true;
}
vector<int>primeFactors(int n)
{
    vector<int>v;
    while (n % 2 == 0)
    {
        v.pb(2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            v.pb(i);
            n = n/i;
        }
    }
    if (n > 2)
        v.pb(n);
    return v;
}

void solve()
{
int n;
cin>>n;
map<string,int>m;
for(int i=0;i<n;i++)
{
    string c;
    cin>>c;
    m[c]++;
}
cout<<m.size()<<endl;
}

signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
//cin>>t;
t=1;
while(t--)
{
  solve();
}
}


Measured memory_bytes: 19152
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>

#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

using namespace std;

int main(){

  string s,p;
  int hoji;

  cin >>s >>p;

  s+=s;
  hoji=s.find(p);

  if(hoji==string::npos) cout <<"No" <<endl;
  else{ cout <<"Yes" <<endl;}

  return 0;
}

Measured memory_bytes: 1192
#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;

int main(){
	int n;

	while (cin >> n){

		double ans = 1;

		while (n){
			ans *= n;
			n--;
		}

		printf("%.0f\n", ans);
	}

	return 0;
}

Measured memory_bytes: 1192
#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

int main(){
  int r,c,k;
  cin >> r >> c >> k;
  vector<vector<vector<ll>>> dp(r+1,vector<vector<ll>>(c+1,vector<ll>(5)));
  vector<vector<ll>> m(r+1,vector<ll> (c+1));
  rep(i,r+1){
    rep(j,c+1){
      rep(p,5){
        dp.at(i).at(j).at(p)=0;
        m.at(i).at(j)=0;
      }
    }
  }
  rep(i,k){
    int a,b;
    ll x;
    cin >>a>>b>>x;
    m.at(a).at(b)=x;
  }
  rep(i,r){
    rep(j,c){
      dp.at(i+1).at(j+1).at(0)=max(dp.at(i).at(j+1).at(4),dp.at(i+1).at(j).at(0));
      for(int p=1;p<4;p++){
        dp.at(i+1).at(j+1).at(p+1)=max(dp.at(i).at(j+1).at(4)+m.at(i+1).at(j+1),max(dp.at(i+1).at(j).at(p)+m.at(i+1).at(j+1),dp.at(i+1).at(j).at(p+1)));
        }
    }
  }
  cout << dp.at(r).at(c).at(4) << endl;
}


Measured memory_bytes: 706932
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if true
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

ss = inputs[0][0]

# body
if $debugFlag
  p ss
end

acnt = 0
bcnt = 0
ss.length.times do |i|
  if i % 2 == 0
    if ss[i..i] == "0"
      acnt += 1 
    else
      bcnt += 1
    end
  else
    if ss[i..i] == "0"
      bcnt += 1 
    else
      acnt += 1
    end
  end
end

puts [acnt, bcnt].min



Measured memory_bytes: 2044
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if (a <= 0 && b >= 0) {
        cout << "Zero" << endl;
    } else if (a > 0) {
        cout << "Positive" << endl;
    } else {
        if ((b-a)%2) {
            cout << "Positive" << endl;
        } else {
            cout << "Negative" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
typedef long long ll;
const int inf = 100100100;

int main(){
  ll n,c,k;
  cin >> n >> c >> k;
  vector<int> t(n);
  rep(i,n) cin >> t[i];
  sort(t.begin(),t.end());
  
  ll ans = 0;
  ll cnt = 0;
  ll init;
  rep(i,n){
    if(cnt == 0 || cnt == c) {
      init = t[i]+k;
      cnt=1;
      ans++;
    }
    else if(t[i]<=init) cnt++;
    else {
      cnt = 1;
      ans++;
      init = t[i]+k;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3724
Q=int(input())
LR=[]
for i in range(Q):
    LR.append(list(map(int,input().split())))
L=[]
R=[]
for i in range(Q):
    L.append(LR[i][0])
    R.append(LR[i][1])

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

PL=primes(10**5)
LN=[]
for i in PL:
    if (i+1)//2 in PL:
        LN.append(i)

A=[0]*10**5
for i in LN:
    A[i]+=1

for i in range(1,10**5):
    A[i]+=A[i-1]
    
for i in range(Q):
    print(A[R[i]]-A[L[i]-1])

Measured memory_bytes: 73944
#include <iostream>
#include <vector>
using namespace std;
#define MOD 998244353
#define MAX 200000

long long fac[MAX];		// n!
long long finv[MAX];	// 1/(n!)
long long inv[MAX];		// 1/n
string to_binString(unsigned int val)
{
	if (!val)
		return string("0");
	string str;
	while (val != 0) {
		if ((val & 1) == 0)  // val は偶数か？
			str.insert(str.begin(), '0');  //  偶数の場合
		else
			str.insert(str.begin(), '1');  //  奇数の場合
		val >>= 1;
	}
	return str;
}
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;
	}
	return;
}

long long COM(int n, int k) {
	if (n < k) {
		return 0;
	}
	if (n < 0 || k < 0) {
		return 0;
	}
	long long res = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
	if (res < 0) {
		cout << endl;;
	}
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

}


long long  calc_amari(long long  x) {
	if (x >= MOD) {
		return x % MOD;
	}
	return x;
}

long long  pow(long long  x, long long  n) {
	long long  ans = 1;
	for (int i = 0; i < n; i++) {
		ans *= x;
	}
	return ans;
}

long long  pow_amari(long long  x, long long  n) {
	long long  res = 1;
	long long xk = x;
	while (n > 0) {
		string temp = to_binString(n);
		if ((n & 1) == 1) {
			res = res * xk % MOD;
		}
		xk = xk * xk % MOD;
		n = (n >> 1);
	}
	if (res < 0) {
		return 0;
	}
	return res;
}


long long  kaijo(long long n) {
	long long  ans = 1;
	for (int i = 1; i <= n; i++) {
		ans = ans * i % MOD;
	}
	return ans;
}
long long div(long long a) {
	return pow_amari(a, MOD - 2);
}


long long  calc_C(long long N, long long K) {
	long long  ans = 1;
	ans = kaijo(N);
	ans *= div(kaijo(N - K));
	ans	*= div(kaijo(K));
	ans = calc_amari(ans);
	return ans;
}


int main() {
	long long N, M, K;
	cin >> N >> M >> K;
	long long  ans = 0;
	COMinit();
	for (int k = 0; k <= K; k++) {
		int temp = M * COM(N-1, k) % MOD * pow_amari(M - 1, N - 1 - k) % MOD;

		ans = (ans + temp) % MOD;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 8292
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin>>N;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin>>A.at(i);
  }
  sort(A.begin(),A.end());
  int K=A.at(N/2-1);
  int L=0;
  for(int i=0; i<A.at(N-1)+1; i++){
    K++;
    if(K<=A.at(N/2))
      L++;
    else break;
  }
  cout<<L<<endl;
}


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

#define int long long

signed main() {
	int N, A, B, C, D;
	cin >> N >> A >> B >> C >> D;
	int k = abs(B - A);
	N--;
	int mn = N*C - k;
	int mx = N*D - k;
	for(int i=0;i<=N;i++){
		if (mn <= i*(C + D) && i*(C + D) <= mx) {
			cout << "YES" << endl;
			return 0;
		}
	}
	
		cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,m,a[10][10],x,t;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> m;
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            cin >> a[i][j];
        }
    }
    for(int k=0;k<=9;k++){
        for(int i=0;i<=9;i++){
            for(int j=0;j<=9;j++){
                if(i==j || i==k || j==k) continue;
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> x;
            if(x!=-1) t+=a[x][1];
        }
    }
    cout << t;
}



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

int main()
{
    int w, h, n; cin>>w>>h>>n;
    int xmin = 0, xmax = w, ymin = 0, ymax = h;
    vector<int> x(n), y(n), a(n);
    for(int i = 0; i < n; i++){
        cin>>x[i]>>y[i]>>a[i];
        if(a[i] == 1) xmin = max(xmin, x[i]);
        else if(a[i] == 2) xmax = min(xmax, x[i]);
        else if(a[i] == 3) ymin = max(ymin, y[i]);
        else if(a[i] == 4) ymax = min(ymax, y[i]);
    }
    
    
    cout << ((xmax - xmin <= 0 || ymax - ymin <= 0)? 0 : (xmax - xmin)*(ymax - ymin) )<< endl;
}

Measured memory_bytes: 256
// Let's bring the sky down :)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5;
const int M = 1e9 + 7;
int dp[N][N];
int main()
{
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    dp[1][0] = 1;
    char ch;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> ch;
            if(ch == '#') continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            if(dp[i][j] >= M) dp[i][j] -= M;
        }
    }
    cout << dp[n][m];
return 0;
}


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

int main()
{

        long long n,m,a,b,c,d,e,f,g,h,p,q,r,fr,sc,tr,sz,tz,i,j,k,mx=LLONG_MIN,mn=LLONG_MAX;
        long long x=0,y=0,cnt=0,res=0,ttl=0,ans=0,sum=0; long long flg=0,flag=1,na=0,as=1;
        vector<long long>u,v,w; vector< pair<long long,long long> >vct; vector<string>vst;
        set<long long>st,nt,tt; map<long long,long long>mp,nq,qr; string str,ttr,ntr;

        scanf("%lld",&n);

        for(i=0;i<n;i++)
        {
            scanf("%lld",&a);  v.push_back(a);

        }

        sort(v.begin(),v.end());

        for(i=n-1;i>=0;i--)
        {

            if(i==n-1){   ans=ans+v[i];  cnt++; if(cnt==n-1)break;   }
            else
            {
                ans=ans+v[i];  cnt++; if(cnt==n-1)break;
                ans=ans+v[i];  cnt++; if(cnt==n-1)break;
            }

        }


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



    return 0;
}





Measured memory_bytes: 5384
N, K = map(int, input().split())
height_list = list()
for i in range(N):
    height_list.append(int(input()))
height_list.sort(reverse=True)
diff_min = 0
for i in range(N-K+1):
    h_max = height_list[i]
    h_min = height_list[i+K-1]
    if i == 0 or h_max-h_min <= diff_min:
        diff_min = h_max - h_min
print(diff_min)

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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    // random_device rnd;
    // mt19937 mt(rnd());
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A (N);
    for(int i = 0;i < N;i++){
        cin >> A[i];
    }

    int a = 0;
    for(int i = 1;i < N;i++){
        a = A[i]-a;
    }
    a = (A[0]-a)/2;
    vector<int> ans (N);
    ans[0] = a;
    for(int i = 1;i < N;i++){
        a = A[i]-a;
        ans[i] = a;
    }

    cout << ans[N-1]*2 << endl;
    for(int i = 0;i < N-1;i++){
        cout << ans[i]*2 << endl;
    }
}


Measured memory_bytes: 2176
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) {
        int[] H;
        int[] W;
        H = new int[100000];
        W = new int[100000];
        int i, j, k, l;
        int count = 0;
    Scanner sc = new Scanner(System.in);
        for(i=1;i<100000;i++){
        int h = sc.nextInt();
        int w = sc.nextInt();
        H[i] = h;
        W[i] = w;
        if (H[i]==0 && W[i]==0) break;
        count++;
        }

        for (j=1;j<=count;j++){
            for (k=1;k<=H[j];k++){
                for (l=1;l<=W[j];l++){
                    System.out.print("#");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 37700
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int BASE = 1 << 20;
int N;
ll tree[2 * BASE + 9];
ll h[200009], a[200009], dp[200009];
ll ans;

void set_max(int l, int r, ll val)
{
    int v = l + BASE - 1;
    int w = r + BASE - 1;

    tree[v] = max(val, tree[v]);
    tree[w] = max(val, tree[w]);
    while (v / 2 != w / 2)
    {
        if (v % 2 == 0) tree[v + 1] = max(tree[v + 1], val);
        if (w % 2 == 1) tree[w - 1] = max(tree[w - 1], val);

        v /= 2;
        w /= 2;
    }
}

ll query(int v)
{
    v += BASE - 1;

    ll ret = 0;
    while (v != 0)
    {
        ret = max(ret, tree[v]);
        v /= 2;
    }

    return ret;
}

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

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> h[i];
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= N; i++)
    {
        dp[i] = query(h[i]) + a[i];

        set_max(h[i] + 1, N + 1, dp[i]);
        ans = max(ans, dp[i]);
    }

    cout << ans << "\n";
}

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

/* -------------------------------- Template -------------------------------- */

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

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

int main() {
  int W, H, p;
  cin >> W >> H;
  vector<pair<ll,int>> vec;
  REP(i,W) {
    cin >> p;
    vec.emplace_back(p, 0);
  }
  REP(i,H) {
    cin >> p;
    vec.emplace_back(p, 1);
  }
  sort(ALL(vec));
  ++W; ++H;
  ll res = 0;
  for (auto p: vec) {
    if (p.second == 0) {
      res += H * p.first;
      --W;
    }
    else {
      res += W * p.first;
      --H;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4464
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << endl; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "abc163_a.cpp"

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

  double r;
  cin >> r;
  coutd(10) << 2 * r * M_PI << endl;
  return 0;
}


Measured memory_bytes: 3804
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int ans = solve();
		System.out.println(ans);
	}

	public static int solve() {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();
		if (a == b) return c;
		if (a == c) return b;
		if (b == c) return a;
		return a;
	}
}

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

using namespace std;

int n, a[210000];
set <pair<int, int> > Set;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		Set.insert(make_pair(a[i], i));
	}
	int ans = 0;
	for (int i = n; i; i--) {
		if (Set.count(make_pair(a[i], i))) {
			Set.erase(make_pair(a[i], i));
			for (int j = 30; j >= 0; j--)
				if ((1 << j) > a[i]) {
					int c = (1 << j) - a[i];
					auto it = Set.lower_bound(make_pair(c, 0));
					if (it != Set.end() && it -> first == c) {
						Set.erase(it);
						ans++;
						break;
					}
				}
		}
	}
	printf("%d\n", ans);
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
struct Edge{
  int to, cost;

  Edge(int t, int c = 0): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

};
using Graph =  vector< vector<Edge> >;

void add_edge(Graph& graph, int u, int v, int cost = 0){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}

void lowlink(int u, int p, int& num, const Graph& G, VI& ord, VI& low,
			 VI& art, vector<pair<int,int>>& brd){
  ord[u] = low[u] = num++;
  int chd_num = 0, chd_low_mx = -1;

  for(unsigned int i=0;i<G[u].size();++i){
	auto& e =  G[u][i];
	int to = e.to;
	if(to == p) continue;
	if(ord[to] < 0){
	  lowlink(to, u, num, G, ord, low, art, brd);
	  low[u] = min(low[u], low[to]);
	  if(ord[u] < low[to]){
		brd.push_back(MP(u, i));
	  }
	  ++chd_num;
	  chd_low_mx = max(chd_low_mx, low[to]);
	}
	else{
	  low[u] = min(low[u], ord[to]);
	}
  }

  if(p == -1){
	if(chd_num > 1)
	  art.push_back(u);
  }
  else{
	if(ord[u] <= chd_low_mx)
	  art.push_back(u);
  }
}

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

  int V, E;
  cin >> V >> E;
  Graph G(V);
  REP(i,E){
	int u, v;
	cin >> u >> v;
	add_edge(G, u, v);
  }

  int num = 0;
  VI ord(V, -1);
  VI low(V, -1);
  vector<PII> brd;
  VI art;
  lowlink(0, -1, num, G, ord, low, art, brd);
  SORT(art);
  for(int v: art) cout << v << endl;

  return 0;
}



Measured memory_bytes: 5660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout << fixed
#define endl '\n'

const int INF = 1e9;
const int MOD = 998244353;
const ll LINF = 1e18;

struct mint {
  ll x;
  mint() : x(0) {
  }
  mint(ll x) : x((x % MOD + MOD) % MOD) {
  }
  mint& operator+=(const mint& r) {
    if ((x += r.x) >= MOD) {
      x -= MOD;
    }
    return *this;
  }
  mint& operator-=(const mint& r) {
    if ((x -= r.x) < 0) {
      x += MOD;
    }
    return *this;
  }
  mint& operator*=(const mint& r) {
    if ((x *= r.x) > MOD) {
      x %= MOD;
    }
    return *this;
  }
  mint& operator++() {
    if ((++x) >= MOD) {
      x -= MOD;
    }
    return *this;
  }
  mint operator++(int) {
    mint ret = x;
    if ((++x) >= MOD) {
      x -= MOD;
    }
    return ret;
  }
  mint& operator--() {
    if ((--x) < 0) {
      x += MOD;
    }
    return *this;
  }
  mint operator--(int) {
    mint ret = x;
    if ((--x) < 0) {
      x += MOD;
    }
    return ret;
  }
  mint operator+(const mint& r) {
    mint ret;
    return ret = x + r.x;
  }
  mint operator-(const mint& r) {
    mint ret;
    return ret = x - r.x;
  }
  mint operator*(const mint& r) {
    mint ret;
    return ret = x * r.x;
  }
  mint operator-() {
    return mint() - *this;
  }
  mint pow(ll t) {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  bool operator<(const mint& a) {
    return x < a.x;
  }
  bool operator>(const mint& a) {
    return x > a.x;
  }
  bool operator<=(const mint& a) {
    return x <= a.x;
  }
  bool operator>=(const mint& a) {
    return x >= a.x;
  }
  bool operator==(const mint& a) {
    return x == a.x;
  }
  bool operator!=(const mint& a) {
    return x != a.x;
  }
};
ostream& operator<<(ostream& os, const mint& r) {
  os << r.x;
  return os;
}
ostream& operator>>(ostream& os, const mint& r) {
  os >> r.x;
  return os;
}

mint dp[3002][3002];

void solve(istream& cin, ostream& cout) {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  dp[a][b] = 1;
  FOR(i, a, c + 1) {
    FOR(j, b, d + 1) {
      if (i > a) dp[i][j] += dp[i - 1][j] * j;
      if (j > b) dp[i][j] += dp[i][j - 1] * i;
      if (i > a && j > b) dp[i][j] -= dp[i - 1][j - 1] * (i - 1) * (j - 1);
    }
  }
  cout << dp[c][d] << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
  return 0;
}
#endif


Measured memory_bytes: 74036
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	unsigned int q; cin >> q;
	for (int i = 0; i < q; i++){
		unsigned int c, a, n; 
		cin >> c >> a >> n;
		if (c == 0)cout << 0 << endl;
		else if (c == 1){
			if (a == 0 || n == 0)cout << 0 << endl;
			else cout << 1 << endl;
		}
		else if (c == 2) {
			if (a == 0)	cout << 0 << endl;
			else if (n <= 1 || a == 1)cout << 1 << endl;
			else cout << 2 << endl;
		}
		else{
			int sum = 0;
			for (int i = 0;; i++){
				if (!c || !a || !n){
					if (!c)goto End;
					else if (c == 1) {
						if (a == 0 || n == 0)goto End;
						else {
							sum++;
							goto End;
						}
					}
					else if (c == 2) {
						if (a == 0)	goto End;
						else if (n <= 1 || a == 1) {
							sum++;
							goto End;
						}
						else {
							sum += 2;
							goto End;
						}
					}
					else if (!a){
						sum += (c - (c % 3)) / 3;
						goto End;
					}
					else{
						c -= 2;
						a--;
						sum++;
					}
				}
				else{
					c--;
					a--;
					n--;
					sum++;
				}
			}
		End: cout << sum << endl;
		}
	}
}

Measured memory_bytes: 3072
import sys
import numpy as np

N, M = list(map(int, sys.stdin.readline().strip().split(" ")))
A = list(map(int, sys.stdin.readline().strip().split(" ")))
B = []
C = []

for _ in range(M):
    b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    B.append(b)
    C.append(c)

A = sorted(A)
arg_list = list(reversed(np.argsort(C)))
B = np.array(B)[arg_list]
C = np.array(C)[arg_list]

index = 0
count = 0
flag = False
for b, c in zip(B, C):
    for _ in range(b):
        if index == N:
            flag = True
            break
        if A[index] >= c:
            flag = True
            break
        A[index] = c
        index += 1
    if flag:
        break

print(sum(A))
        



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

using namespace std;
typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    int ans = 0;
    int now_num = 1;
    for(int i = 0; i < n; i++){
        if(A[i] == now_num){
            now_num++;
        }else{
            ans++;
        }
    }
    if(now_num > 1){
        cout << ans << endl;
    }else{
        cout << "-1" << endl;
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int a, b;
	scanf("%d%d",&a,&b);
    if(a>0)puts("Positive");               
    else if(b>=0)puts("Zero");             
    else if((a&1)^(b&1))puts("Positive");  
    else puts("Negative");
	return 0;
}

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

def eratosthenes(num):
	out = []
	d = math.floor(num**(1/2))
	is_prime = [True] * (d+1)
	is_prime[0] = False
	is_prime[1] = True

	for i in range(2,d+1):
		if is_prime[i]:
			out.append(i)
			for j in range(2*i, d+1, i):
				is_prime[j] = False

	return out

tmp = n
primes = eratosthenes(10**9)
ans = []
for p in primes:
	while True:
		div, mod = divmod(tmp, p)
		if mod == 0:
			ans.append(p)
			tmp = div
		else:
			break

if len(ans) == 0:
	print('{}: {}'.format(n,n))
else:
	print('{}: {}'.format(n, ' '.join(list(map(str, ans)))))


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

int main()
{
    string s;
    cin >> s;
    int a, b, c, d;
    a = b = c = d = 0;
    for (int i = 0; i < s.size(); i++) {
        a += (s[i] == 'S');
        b += (s[i] == 'N');
        c += (s[i] == 'W');
        d += (s[i] == 'E');
    }
    if ((!!a) ^ (!!b)) puts("No");
    else if ((!!c) ^ (!!d)) puts("No");
    else puts("Yes");
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	list := make([]int, n)
	for i := 0; i < n; i++ {
		list[i] = nextInt()
		if list[i]%2 == 0 {
			if list[i]%3 == 0 || list[i]%5 == 0 {

			} else {
				fmt.Println("DENIED")
				return
			}
		}
	}
	fmt.Println("APPROVED")
	return
}

// ---- readfunc
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
long long i,j,n,m,c;
bool r;
int main(){
  for(cin>>n>>m,i=max(m,n);;i+=max(m,n)){
    if(i%n==0&&i%m==0)return cout<<i,0;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    long A, B;
    cin >> A; cin >> B;
    if (A % 2 == B % 2) {
        cout << (long)(A + B) / 2 << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}



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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

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

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

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

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n; ll k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }
    vi b(n, -1), c;
    int v = 0;
    while(b[v] == -1) {
        c.pb(v);
        b[v] = sz(c) - 1;
        v = a[v];
    }
    int roop = sz(c) - b[v], start = b[v];
    if (k >= start) {
        k -= start;
        k %= roop;
        k += start;
    }
    cout << c[k]+1 << endl;
    return 0;
}


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

int main() {
  int d, t, s;
  string ans;

  cin >> d >> t >> s;

  if(t*s>=d) {
    ans = "Yes";
  } else {
    ans = "No";
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>


#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define LOWER(a,x) lower_bound(ALL(a), x) - a.begin() - 1;
#define COUNT(a,x)  upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
#define MCOUNT(a,x,y) upper_bound(ALL(a), y) - lower_bound(ALL(a), x);
#define scan(x) scanf("%lld",&x);
#define inf 5555555555555555555
#define mod 1000000007
#define pi 3.14159265358979323846
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool flag, ok;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111



int main(void) {
  ll t, now = 0, st;
  cin >> n >> t;

  st = 0;
  now = t;
  FOR(i, 0, n) {
	cin >> tmp;
	if (now < tmp) {
	  ans += now - st;
	  st = tmp;
	}
	now = tmp + t;
  }
  ans += now - st;

  cout << ans << endl;

  return 0;
}

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

int main()
{
	int N;
	cin >> N;
	vector<vector<int>> g( N );
	for( int i = 0; i < N - 1; i++ ) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back( b );
		g[b].push_back( a );
	}
	vector<int> c( N );
	for( int i = 0; i < N; i++ ) {
		cin >> c[i];
	}

	sort( c.begin(), c.end(), greater<int>() );
	long long ans = 0;
	vector<int> d( N, -1 );
	queue<int> que;
	que.push( 0 );
	int i = 0;
	d[0] = c[i];
	i++;
	while( !que.empty() ) {
		int j = que.front();
		que.pop();
		for( int e : g[j] ) {
			if( d[e] >= 0 ) continue;
			d[e] = c[i];
			i++;
			que.push( e );
			ans += min( d[j], d[e] );
		}
	}

	cout << ans << endl;
	for( int i = 0; i < N; i++ ) {
		if( i ) cout << " ";
		cout << d[i];
	}
	cout << endl;
}


Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef long int lint;
typedef vector<char> vchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
#define vsort(v) sort((v).begin(), (v).end())
#define vreverse(v) reverse((v).begin(), (v).end())
#define pb(a) push_back(a)
#define INF 1000000007
#define MOD 1e9+7
long long int gcd(int ga,int gb){
  while(gb > 0){
    llint tmp;
    tmp=ga;
    ga=gb;
    gb=tmp%gb;
  }
  return ga;
}
int main(){
  //input
  lint n,i,j;cin>>n;vint a(n);
  for(i=0;i<n;i++){cin>>a[i];}
  vint s;s.pb(0);
  double d=n;double sqq=sqrt(d);int sq=sqq;llint h=0;
  while(h+sq<=n){
    s.pb(h+sq);h+=sq;
  }
  if(n<9){llint gc,mx;mx=0;
  //caricurate
  for(i=0;i<n;i++){
    if(i){gc=a[0];}else{gc=a[1];}
    for(j=0;j<n;j++){
      if(i!=j){gc=gcd(gc,a[j]);}
    }
    if(mx<gc){mx=gc;}
  }
  //output
  cout<<mx<<endl;}
  else{
  s.pb(n);
  vint gc(s.size()-1);
  for(i=0;i<s.size()-1;i++){
    gc[i]=a[s[i]];
    for(j=s[i]+1;j<s[i+1];j++){
    gc[i]=gcd(gc[i],a[j]);
    }
  }
  llint gt,gm;lint y;gm=0;lint u;
  for(i=0;i<s.size()-1;i++){
    for(j=s[i];j<s[i+1];j++){
      if(j!=s[i]){gt=a[j-1];}else{gt=a[j+1];}
    for(y=s[i];y<s[i+1];y++){
      if(y!=j){gt=gcd(gt,a[y]);}
    }
    for(u=0;u<s.size()-1;u++){if(u!=i){gt=gcd(gt,gc[u]);}}
      if(gm<gt){gm=gt;}
    }
  }
  cout<<gm<<endl;}
  
}


Measured memory_bytes: 640
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, t = LI()
A = LI()
min_ret = A[0]
max_diff = 1
for i in range(1, n):
    max_diff = max(max_diff, A[i] - min_ret)
    min_ret = min(min_ret, A[i])



ans = 0
min_ret = A[0]
for j in range(1, n):
    if A[j] - min_ret == max_diff:
        ans += 1
    min_ret = min(min_ret, A[j])


print(ans)




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

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	list<int> l;
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		string s;
		int k;
		cin >> s;
		if(s == "insert"){
			cin >> k;
			l.emplace_front(k);
		}else if(s == "delete"){
			cin >> k;
			auto it = find(l.begin(),l.end(),k);
			if(it == l.end())continue;
			l.erase(it);
		}else if(s == "deleteFirst"){
			l.pop_front();
		}else{
			l.pop_back();
		}
	}

	for(auto it=l.begin();it!=l.end();it++){
		cout << *it;
		if(it != --l.end()){
			 cout << " ";
		}
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 34432
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
	ll s; cin >> s;
	vector<ll> res(2001, 0);
	res[3] = res[4] = res[5] = 1;
	for (ll i = 6; i < 2001; i++) {
		res[i] = res[i-2] + res[i-3] + res[i-4];
		res[i] %= MOD;
	}
	cout << res[s] << '\n';
    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define ls(x) (x)<<1
#define rs(x) (x)<<1|1
#define fu(i,r,t) for(int i=r;i<=t;i++)
#define fd(i,r,t) for(int i=r;i>=t;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl '\n'
#define lcm(a,b) (a*b)/__gcd(a,b)
#define Case(i,ans) cout<<"Case "<<i<<": "<<ans<<endl;
#define cp(i,ans) printf("%.if",ans);
#define cpp(i,ans) cout<<setprecision(i)<<fixed<<ans<<endl;
#define ppb pop_back
#define ppf pop_front
#define pb push_back
#define pf push_front
#define pq priority_queue
#define lowbit(x) (x)&(-x)
#define all(V) V.begin(),V.end()
#define ms multiset
#define mod(x) (x)%mo_num
#define vc vector
#define vct vector<int>
#define fa(i,V) for(auto i:V)
#define out(i) cout<<i<<endl;
#define fi first
#define sc second
#define fun(i) fu(i,1,n)
#define fut(i) fu(i,1,t)
#define fum(i) fu(i,1,m)
//#define P pair<int,int>
using namespace std;
const int INF=1e17+5;
const int maxn=2e5+5;
const int mo_num=1e9+7;
int n,m,a[maxn],b[maxn],ans;
bool cmp(int a,int b)
{
    return a>=b;
}
int weihu1[maxn],weihu2[maxn],last=0,Last=0;
int32_t main()
{
    IOS
    cin>>n;
    weihu1[last]=-1;
    fun(i)
    {
        cin>>a[i];
        //最长不上升子序列
        a[i]<=weihu1[last]?weihu1[++last]=a[i]:weihu1[lower_bound(weihu1,weihu1+last+1,a[i],cmp)-weihu1]=a[i];
        //最长上升子序列
//        a[i]>weihu2[Last]?weihu2[++Last]=a[i]:weihu2[lower_bound(weihu2,weihu2+Last+1,a[i])-weihu2]=a[i];
    }
    out(last+1)
    return 0;
}


Measured memory_bytes: 4992