akhauriyash/Code-Regression huggingface dataset:
n = int(input())

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

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

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

    return arr

ele = factorization(n)
cnt = 0
for i in range(len(ele)):
    for j in range(1, ele[i][1]+1):
        if j*(j+1)/2 <= ele[i][1]:
            cnt += 1
        else:
            break
            
if n == 1:
    cnt = 0

print(cnt)

Measured memory_bytes: 9500
import java.util.Scanner;


public class Main{
    public static Scanner scan  = new Scanner(System.in);
    public static void main(String[]args){
        int k = nextInt();
        String s = next();
        if(s.length()<=k){
            print(s);
        }
        else{
            for(int i=0;i<k;i++){
                System.out.printf("%c",s.charAt(i));
            }
            print("...");
        }
    }

    public static int nextInt(){
        return Integer.parseInt(scan.next());
    }
    public static long nextLong(){
        return Long.parseLong(scan.next());
    }
    public static String next(){
        return scan.next();
    }
    public static double nextDouble(){
        return Double.parseDouble(scan.next());
    }
    public static float nextFloat(){
        return Float.parseFloat(scan.next());
    }

    //Yes or No
    public static void yesNo(boolean flag){
        if(flag) System.out.println("Yes");
        else System.out.println("No");
    }
    public static void print(Object a){
        System.out.println(a);
    }
}

Measured memory_bytes: 35812
N = gets.to_i

values = []
3.upto(9) do |digit|
  0.upto(3**digit-1) do |pattern|
    v = 0
    digit.times do
      m = pattern % 3
      if m == 0
        v = 10*v + 3
      elsif m == 1
        v = 10*v + 5
      elsif m == 2
        v = 10*v + 7
      end
      pattern /= 3
    end

    if v <= N && v.to_s.include?('3') && v.to_s.include?('5') && v.to_s.include?('7')
      values << v
    end
  end
end

p values.size


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

int main()
{
    int a, b, c;
    long long k;
    cin >> a >> b >> c >> k;
    if (k % 2 == 0)
    {
        cout << a - b << endl;
    }
    else
    {
        cout << b - a << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        int max = 0;
        int min = 1000;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            if (max < a) {
                max = a;
            }
            if (a < min) {
                min = a;
            }
        }
        System.out.println(max - min);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


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

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

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int x, y , z; cin >> x >> y >> z;

   int ans = 0;
   x = x - 2*z;
   while(x >= y)
   {
      ans++;
      x -= y;
      x-=z;
   }
   cout << ans << nl;


}


Measured memory_bytes: 3644
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>
#include <cassert>

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

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

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    int N, K; cin>>N>>K;
    vector<int>h(N), dp(N+10, (int)1e9);
    for(int i=0;i<N;i++)cin>>h[i];

    dp[0]=0;

    for (int i = 0; i < N; i++) {
        for (int j = i+1; j <= i+K; j++) {
            if(j>=N)continue;
            dp[j]=min(dp[j], dp[i]+abs(h[i]-h[j]));
        }
    }

    cout<<dp[N-1]<<endl;


    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));

            return;
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var M = cin.ReadInt;

            int[] city = new int[N];

            var a = 0;
            var b = 0;

            for (int i = 0; i < M; i++)
            {
                a = cin.ReadInt;
                b = cin.ReadInt;
                city[a - 1] += 1;
                city[b - 1] += 1;

            }

            for (int i = 0; i < N; i++)
            {
                WriteLine(city[i]);
            }

        }
    }

    public static class Extensions
    {
        public static string Reverse(this string sourse)
        {
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

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

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N + 1, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    vector<vector<int>> dist(N + 1, vector<int>(3, inf));
    int S, T;
    cin >> S >> T;
    dist[S][0] = 0;
    queue<pair<int, int>> q;
    q.push({S, 0});
    while (!q.empty()) {
        auto &from = q.front();
        q.pop();

        for (auto &to : G[from.first]) {
            if (dist[to][(from.second + 1) % 3] != inf)
                continue;

            dist[to][(from.second + 1) % 3] = dist[from.first][from.second] + 1;
            q.push({to, (from.second + 1) % 3});
        }
    }

    if (dist[T][0] == inf) {
        cout << -1 << endl;
    } else {
        cout << dist[T][0] / 3 << endl;
    }
    return 0;
}

Measured memory_bytes: 11768
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int INF = 1e9;
#define MAX 105
int t[MAX];
vector<pair<int, int> > p;
int main(void) {
	int n, m,a,b;
	string s;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> t[i];
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a >>b;
		p.push_back(make_pair(a, b));
	}
	for (int i = 0; i < p.size(); ++i) {
		int sum = 0;
		for (int j = 1; j <= n; ++j) {
			if (p[i].first == j) {
				sum += p[i].second;
			}
			else {
				sum += t[j];
			}
		}
		cout << sum << endl;
	}
	return 0;
}

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

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> s(M);
	vector<char> c(M);

	for(int i = 0; i < M; i++)
		cin >> s.at(i) >> c.at(i);

	for(int i = 0; i < M; i++) {
		for(int j = i + 1; j < M; j++) {
			if(s.at(i) == s.at(j)) {
				if(c.at(i) != c.at(j)) {
					cout << -1 << endl;
					return 0;
				}
			}
		}
		if(s.at(i) == 1 && c.at(i) == '0') {
			if(N == 1) {
				cout << 0 << endl;
				return 0;
			}
			cout << -1 << endl;
			return 0;
		}
	}

	string str(N, '0');
	str.at(0) = '1';

	if(M == 0) {
		if(N == 1) {
			str.at(0) = '0';
			cout << str << endl;
			return 0;
		}
		str.at(0) = '1';
		cout << str << endl;
		return 0;
	}

	for(int i = 0; i < M; i++) {
		str.at(s.at(i) - 1) = c.at(i);
	}
	cout << str << endl;
}

Measured memory_bytes: 256
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,k = map(int, input().split())
    s,p,r=map(int, input().split())
    t=list(input())
    points=0
    for i in range(0,k):
        if t[i]=="r":
            points+=r
        elif t[i]=="s":
            points+=s
        else:
            points+=p
    for i in range(k,n):
        if t[i-k]==t[i]:
            t[i]="x"
        else:
            if t[i] == "r":
                points += r
            elif t[i] == "s":
                points += s
            else:
                points += p
    print(points)


if __name__ == "__main__":
    main()

Measured memory_bytes: 4212
from itertools import groupby
import copy

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2


N=int(input())
A=list(map(int,input().split()))

B=copy.copy(A)
s=equalfind(B)
data=groupby(B)
ans=[0 for i in range(0,N+1)]
for key,group in data:
    g=len(list(group))
    ans[key]=g

for i in range(0,N):
    minus=ans[A[i]]-1
    print(s-minus)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define repp(i, n) rep(i, n)
#define reppp(i, n) repp(i, n)
#define rrepp(i, n) rrep(i, n)
#define repss(i, n) reps(i, n)
#define repcc(i, n) repc(i, n)
#define repii(i, a, b) repi(i, a, b)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

void solve() {
  int a, b, s;
  while (cin >> a >> b >> s) {
    a %= b;
    int ans = 0;
    rep(i, s) {
      a *= 10;
      ans += a / b;
      a = a - a / b * b;
    }
    cout << ans << '\n';
  }
}



Measured memory_bytes: 3144
#include<bits/stdc++.h>
#define int long long int  //comment for large arrays
#define pll pair<int,int>
#define dbl long double
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define eps 0.00000001
#define INF 10000000000000001
#define all(x) (x).begin(),(x).end()
#define LB(v,x) (lower_bound(all(v),x) - v.begin()) 
#define UB(v,x) (upper_bound(all(v),x) - v.begin())
#define size(x) (int)(x).size()
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define popb() pop_back()
#define popf() pop_front()
#define mp(x,y) make_pair((x),(y))
#define vec(dt) vector<dt>
#define vv(dt) vector<vector<dt>>
#define fastio(x) ios_base::sync_with_stdio(x); cin.tie(NULL)
#define init(v,s) memset(v,s,sizeof(v)) 
#define bug(x) cerr<<"LINE: "<<__LINE__<<" || click to see test details "<<#x<<" = "<<x<<endl
#define loop(i,s,n) for(int i=s;i<n;i++)
#define bugprint(v) for(auto it:v) cout<<it<<" "; cout<<endl 
using namespace std;


signed main()
{
	fastio(0);
	int n,w;
	cin>>n>>w;
	int value[n+1],weight[n+1];
	loop(i,1,n+1) cin>>weight[i]>>value[i];
	int dp[w+1];
	init(dp,0);
	loop(i,1,n+1)
		for(int j=w;j>0;j--)
			if(j - weight[i]>=0) 
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	cout<<dp[w]<<endl;
	return 0;		
}

Measured memory_bytes: 1152
n,y=map(int,input().split())
flg=0
for i in range(n+1):
    for j in range(n-i+1):
        if (i*10000+j*5000+(n-i-j)*1000==y):
            flg=1
            print(i,j,n-i-j)
            exit()

print("-1 -1 -1")


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath> 
#include <queue>
#include <functional>

using namespace std;
//typedef long long ll;
//typedef pair<int, int> P;
//static const int dx[4] = {1, -1, 0, 0};
//static const int dy[4] = {0, 0, 1, -1};


int main() {

    int k, t; cin >> k >> t;
    vector<int> a(101);
    for (int i = 0; i < t; i++) cin >> a[i];

    vector<int> cake(10001);

    int before_ind = -1;
    int cur_ind = -1;
    int max_value = 0;
    int ans = 0;
    for (int i = 0; i < k; i++) {

        max_value = 0;
        cur_ind = -1;

        for (int ind = 0; ind < t; ind++) {

            if (a[ind] > max_value and ind != before_ind) {
                max_value = a[ind];
                cur_ind = ind;

            }
        }

        if (cur_ind == -1) {
            cur_ind = before_ind;
            ans++;
        }
        a[cur_ind]--;
        cake[i] = cur_ind;
        before_ind = cur_ind;

    }

    /*
    for (int i = 0; i < k; i++) {
        cout << cake[i] << ' ' ;
    } cout << '\n';
    */
    cout << ans << '\n';

}


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

const double rate = 380000.0;

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

  double sum_jpy = 0;
  double sum_btc = 0;
  rep(i, N) {
    double x;
    string u;
    cin >> x >> u;

    if (u == "JPY")
      sum_jpy += x;
    else
      sum_btc += x;
  }

  printf("%.9f\n", sum_jpy + rate * sum_btc);
}

Measured memory_bytes: 256
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
int main()
{
  int N,M,A,B,count,H[100001]={0},peak[100001]={0};
  count=scanf("%d %d",&N,&M);
  rep(i,N)count=scanf("%d",&H[i]);
  rep(i,M){count=scanf("%d %d",&A,&B);A--,B--;peak[A]=(peak[A]>H[B])?peak[A]:H[B];peak[B]=(H[A]>peak[B])?H[A]:peak[B];}
  count=0;
  rep(i,N)count+=H[i]>peak[i];
  return printf("%d\n",count),0;
}

Measured memory_bytes: 2452
#include <stdio.h>

typedef struct {
  char mark;
  int number;
}card;

void BubbleSort(card C[], int N);
void SelectionSort(card C[], int N);

int main(){
  int N,i;
  card C[36];
  card D[36];

  scanf("%d",&N);

  for(i=0;i<N;i++){
    scanf(" %c",&C[i].mark);
    scanf("%d",&C[i].number);
    D[i] = C[i];
  }

  BubbleSort(C,N);
  SelectionSort(D,N);

    for(i=0;i<N-1;i++){
      printf("%c%d ",C[i].mark,C[i].number);
    }
    printf("%c%d\n",C[N-1].mark,C[N-1].number);
    printf("Stable\n");

    for(i=0;i<N-1;i++){
      printf("%c%d ",D[i].mark,D[i].number);
    }
    printf("%c%d\n",D[N-1].mark,D[N-1].number);

    for(i=0;i<N;i++){
      if(i == N-1){
        printf("Stable\n");
      }
      if((C[i].number != D[i].number) || (C[i].mark != D[i].mark)){
          printf("Not stable\n");
          break;
        }
    }
    return 0;
}


void BubbleSort(card C[], int N){
  int i,j;
  card tmp;

  for(i=0;i<N-1;i++){
    for(j=N-1;j>i;j--){
      if(C[j].number < C[j-1].number){
        tmp = C[j];
        C[j] = C[j-1];
        C[j-1] = tmp;
      }
    }
  }
}

void SelectionSort(card C[],int N){
  card tmp;
  int minj,i,j;

  for(i=0;i<N;i++){
    minj = i;
    for(j=i;j<N;j++){
      if(C[j].number < C[minj].number){
        minj = j;
      }
    }
    tmp = C[i];
    C[i] = C[minj];
    C[minj] = tmp; 
      
  }

  return;
}






Measured memory_bytes: 2048
def main():
    n = int(input())
    s = input().rstrip()
    t = input().rstrip()
    ans = 2*n
    for i in range(n):
        f = True
        for j in range(n-i):
            if s[i+j] != t[j]:
                f = False
                break
        if f:
            ans = i + n
            break
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
ll inf = 1e18;
int main() {
    int n;
    cin >> n;
    long long sum = 1;
    bool f = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 0) {
            f = 0;
        }
    }
    if (!f) {
        cout << 0 << endl;
    } else {
        for (int i = 0; i < n; i++) {
            ll gd = (inf + sum - 1) / sum;
            if (a[i] > gd) {
                cout << -1 << endl;
                return 0;
            }
            sum *= a[i];
            if (sum > inf) {
                cout << -1 << endl;
                return 0;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 4372
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=998244353;

#define MAX_N 20020
ll inv[MAX_N+10],fac[MAX_N+10],ifac[MAX_N+10];

void setComb(){
  inv[0]=1;inv[1]=1;fac[1]=1;ifac[1]=1;fac[0]=1;ifac[0]=1;
  for(int i=2;i<MAX_N;i++){
    inv[i]=(-MOD/i)*inv[MOD%i]%MOD;
    fac[i]=fac[i-1]*i%MOD;
    ifac[i]=ifac[i-1]*inv[i]%MOD;

    inv[i]=(inv[i]+MOD)%MOD;
    fac[i]=(fac[i]+MOD)%MOD;
    ifac[i]=(ifac[i]+MOD)%MOD;
  }
  return;
}

ll comb(ll n,ll k){
  if(n<k||n<0||k<0) return 0;
  else return ((fac[n]*ifac[k]%MOD*ifac[n-k]%MOD+MOD)%MOD);
}

ll hcomb(ll n,ll r){
  if(n==0&&r==0) return 1;
  else if(n<0||r<0) return 0;
  else return comb(n+r-1,r-1);
}

ll N,S;

void mul(ll &a,ll b){
    a%=MOD;
    b%=MOD;
    a=a*b%MOD;
}

void add(ll &a,ll b){
    a=(a+b)%MOD;
}

ll mod_pow(ll x,ll n){
    x%=MOD;
    ll res=1;
    while(n>0){
        if(n&1) mul(res,x);
        mul(x,x);
        n/=2;
    }
    return res;
}

ll ber[2020];

void init_ber(int n){
    ber[0]=1;
    for(int i=1;i<=n;i++){
        ll res=0;
        for(int k=0;k<i;k++){
            ll c=comb(i+1,k);
            mul(c,ber[k]);
            add(res,c);
        }
        mul(res,inv[i+1]);
        res=MOD-res;
        add(res,MOD);
        ber[i]=res;
    }
}

ll faul(ll n,ll k){
    ll res=0;
    n++;
    for(int j=0;j<=k;j++){
        ll c=comb(k+1,j);
        mul(c,ber[j]);
        ll p=mod_pow(n,k+1-j);
        mul(c,p);
        add(res,c);
    }
    mul(res,inv[k+1]);
    return res;
}

int main(){
  cin>>N;
  cin>>S;

  setComb();
  init_ber(1010);


  ll ans=inv[2];
  mul(ans,S);
  mul(ans,S+1);
  mul(ans,mod_pow(S+1,N-2));

  if(S%2){
      ll a=faul(S/2,N-1);
      ll b=faul(S,N-1);
      ll c=mod_pow(2ll,N);
      mul(a,c);
      add(ans,b-a+MOD);
  }else{
      ll a=faul(S/2,N-1);
      ll b=faul(S,N-1);
      ll c=mod_pow(2ll,N);
      mul(a,c);
      add(ans,a-b+MOD);
  }

  add(ans,MOD);
  cout<<ans<<endl;


  return 0;
}



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

int main()
{
    int n;
    cin>>n;
    int arr[n+5],frr[n+5];
    for(int i=0;i<n;i++)cin>>arr[i]>>frr[i];
    bool tr=false;
    for(int i=1;i<n-1;i++)
    {
        if(arr[i]==frr[i]&&arr[i-1]==frr[i-1]&&arr[i+1]==frr[i+1])tr=true;
    }
    if(tr)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iomanip>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
#define pii pair<int,int>

#define MAXM 1000001
#define MAXSQM 1003
int diff[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int map[MAXSQM][MAXSQM] = {};
bool furui[MAXM] = {};
pii dpmap[MAXSQM][2] = {};

void init_map(int m){
    fill_n(*map,MAXSQM*MAXSQM,0);
    fill_n(*dpmap,MAXSQM*2,pii(-1,-1));
    int idx=MAXSQM/2,idy=MAXSQM/2;
    int dir=0;
    int c=1;
    for(int i=1;c<=m;i++){
        for(int j=0;j<i&&c<=m;j++){
            map[idx][idy]=c++;
            idx+=diff[dir][0];
            idy+=diff[dir][1];
        }
        dir=(dir+1)%4;
        for(int j=0;j<i&&c<=m;j++){
            map[idx][idy]=c++;
            idx+=diff[dir][0];
            idy+=diff[dir][1];
        }
        dir=(dir+1)%4;
    }
}

pii dp(int n){
    int nx,ny;
    for(nx=0;nx<MAXSQM;nx++){
        for(ny=0;ny<MAXSQM;ny++){
            if(n==map[nx][ny]) break;
        }
        if(n==map[nx][ny]) break;
    }

    pii ans=pii(0,0);

    if(!furui[map[nx][ny]]){
        dpmap[nx][ny%2]=pii(1,map[nx][ny]);
        ans=dpmap[nx][ny%2];
    }
    else
    {
        dpmap[nx][ny%2]=pii(0,0);
    }

    for(int j=ny;j>=1;j--){
        for(int i=0;i<MAXSQM;i++){
            if(map[i][j]==0 || dpmap[i][j%2].first==-1) continue;
            for(int k=-1;k<=1;k++){
                if(map[i+k][j-1]==0) continue;
                if(!furui[map[i+k][j-1]]){
                    dpmap[i+k][(j-1)%2]=max(pii(dpmap[i][j%2].first+1,map[i+k][j-1]), dpmap[i+k][(j-1)%2]);
                }
                else
                {
                    dpmap[i+k][(j-1)%2]=max(dpmap[i][j%2], dpmap[i+k][(j-1)%2]);
                }
                ans=max(ans,dpmap[i+k][(j-1)%2]);
            }
        }
    }
    return ans;
}

int main(){
    while(1){
        int m,n;
        cin>>m>>n;
        if(m==0) break;

        furui[0]=furui[1]=true;
        for(int i=2;i<MAXSQM;i++){
            for(int j=2;i*j<MAXM;j++){
                if(!furui[i]){
                    furui[i*j]=true;
                }
            }
        }
        init_map(m);
        pii p=dp(n);

        /*int b=MAXSQM/2,a=MAXSQM/2;
        for(int i=a-5;i<a+5;i++){
            for(int j=b-5;j<b+5;j++){
                cout<<std::setw(4)<<map[j][i];
            }
            cout<<endl;
        }
        for(int i=a-5;i<a+5;i++){
            for(int j=b-5;j<b+5;j++){
                cout<<setw(4)<<dpmap[j][i].first;
            }
            cout<<endl;
        }*/
        cout<<p.first<<" "<<p.second<<endl;
    }
    return 0;
}

Measured memory_bytes: 6080
#include <iostream>
using namespace std;
int n,i,ans,a;
int main() {
	
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin >>a;
		if(i%2!=0&&a%2!=0)
		ans++;
	}
	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 3552
a = int(input())
b = int(input())
c = int(input())
d = int(input())
count = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k == d:
        count += 1
print(count)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define int long long
#define all(c) (c).begin(), (c).end()
#define cpresent(c,x) ((c).find(x) != (c).end()) // present in container?
#define vpresent(c,x) (find(all(c),x) != (c).end()) // present in vector?
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
using namespace std;

int n;

bool isprime(int n){
    if(n == 1)
        return false;
    for(int i = 2; i*i <= n; ++i){
        if(n%i == 0)
            return false;
    }
    return true;
}

int cnt(vector<int>& fac, int n){
    int ret = 0;
    for(int i = 0 ; i < fac.size(); ++i){
        int temp = fac[i];
        int ans = 0;
        while(n%temp == 0){
            n /= temp;
            ans++;
        }
        // cout << "a " << ans << endl;
        ans = (sqrt(1 + 8*ans) - 1)/2;
        // cout << "a1 " << ans << endl;
        ret += ans;
    }
    return ret;
}

void solve(){   
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return;
    }
    vector<int> fac;
    for(int i = 1; i*i <= n; ++i){
        if(n%i == 0){
            if(i*i == n){
                if(isprime(i))
                    fac.emplace_back(i);
            }else{
                if(isprime(i))
                    fac.emplace_back(i);
                if(isprime(n/i))
                    fac.emplace_back(n/i);
            }
        }
    }
    // cout << "v\n";
    // for(int i = 0; i < fac.size(); ++i)
    //     cout << fac[i] << " ";
    // cout << endl;
    cout << cnt(fac, n) << endl;
}
signed main(){
	fastio;
	// int t; cin >> t;
	// while(t--)
		solve();
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    int p[N];
    for(int i = 0; i < N; ++i){
        cin >> p[i];
    }
    vector<int> vec(N);
    vector<int> abs(N);
    vec.assign(&p[0], &p[N]);
    abs = vec;
    sort(abs.begin(), abs.end());
    int count = 0;
    int num[100] = {};
    for(int i = 0; i < vec.size(); ++i){
        if(p[i] != abs.at(i)){
            num[count] = i;
            ++count;
        }
        if(count > 2) break;
    }
    bool final_judge = true;
    if(count == 0){
        cout << "YES" << endl;
    }else if(count == 2){
        swap(vec.at(num[0]), vec.at(num[1]));
        for(int i = 0; i < vec.size(); ++i){
            if(abs.at(i) != vec.at(i)){
                final_judge = false;
            }
        }
        if(final_judge == true){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }else{
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int diff[100001];
int main(){
    int a, b;
    cin>>a>>b;
    int x, y;
    for (int i=0; i<b; i++){
        cin>>x>>y;
        diff[x]++;
        diff[y+1]--;
    }
    int ans=0, tar=0;
    for (int i=1; i<=a; i++){
        tar+=diff[i];
        if (tar==b) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

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

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

int main() {
	std::string s; cin >> s;

	for(int i = 0; i < s.size(); i++) {
		if(i % 2) {
			if(s[i] == 'L' or s[i] == 'U' or s[i] == 'D') continue;
			printf("No\n");
			return 0;			
		} else {
			if(s[i] == 'R' or s[i] == 'U' or s[i] == 'D') continue;
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

#整数の入力
#a = int(input())
#b = int(input())
#スペース区切りの整数の入力
#a, b, c = map(int, input().split())
#文字列の入力
s1 = input()
s2 = input()

if s1[0] == s2[2] and s1[1] == s2[1] and s1[2] == s2[0]:
    ans = "YES"
else :
    ans = "NO"

#出力
print(ans)

Measured memory_bytes: 3060
from collections import defaultdict
import bisect

alphabet="abcdefghijklmnopqrstuvwxyz"

bS = int(input())
S= input()
nQ = int(input())

S = [i for i in S]

query = []
for i in range(nQ):
  query.append(input().split())

locs =defaultdict(list)

for i,char in enumerate(S):
    locs[char].append(i)
    
def countChars(iter,ss,ee):
  nChar = 0
  for i in alphabet:
    if len(locs[i]) == 0:
      pass
    else:
      sptr = bisect.bisect_right(locs[i],ss)
      eptr = bisect.bisect_left(locs[i],ee)
      if sptr == eptr:
        if sptr < 1 or sptr > len(locs[i]):
          continue
        else:
          if locs[i][sptr-1] == ss:
            nChar+=1
      else:
        nChar += 1
  return nChar
    
  
res = []
for iter,iQ in enumerate(query):
  if int(iQ[0]) == 2:
    res.append(str( countChars(iter,int(iQ[1])-1,int(iQ[2])) ))
  if int(iQ[0]) == 1:
    location = int(iQ[1])-1
    curChar  = S[location]
    if curChar != iQ[2]:
      locs[curChar].remove(location) #remove from old
      bisect.insort(locs[iQ[2]],location)
      S[location] = iQ[2]
      
print(" ".join(res))

  

Measured memory_bytes: 98532
import collections

N = int(input())
c = collections.Counter(input() for _ in range(N))

c = sorted(c.items(), key=lambda x: x[1], reverse=True)

a = []
for i in c:
    if c[0][1] != i[1]: break
    a.append(i)

a = sorted(a)
for i in a:
    print(i[0])
    

Measured memory_bytes: 43484
import collections


def calc(A, K):
    dist = {}
    tmp = collections.Counter(A)
    type_ = len(tmp)

    if type_ <= K:
        return 0

    for a, count in tmp.items():
        if count not in dist.keys():
            dist[count] = [a]
        else:
            dist[count].append(a)

    rewrite = 0
    i = 0
    for c in sorted(dist.keys()):
        for _ in dist[c]:
            i += 1
            rewrite += c
            if i == type_ - K:
                return rewrite


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = calc(A, K)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 32556
#include<stdio.h>
#define INF 100000
#define MAX 101
#define NIL -6
#define WHITE 0
#define GRAY 1
#define BLACK 2

int G[MAX][MAX];
int n;

void prim(){
  int i,j;
  int d[MAX];
  int pi[MAX];
  int color[MAX];
  int min,u,v,sum=0;

  for(i=0;i<n;i++){
    d[i] = INF;
    pi[i] = NIL;
    color[i] = WHITE;
  }

  d[0] = 0;

  while(1){
    min = INF;
    u = NIL;
    for(i=0;i<n;i++){
      if(color[i] != BLACK && d[i] < min){
        min = d[i];
        u = i;
      }
    }
    if(u == NIL){
      break;
    }
    color[u] = BLACK;
    for(v=0;v<n;v++){
      if(color[v] != BLACK && G[u][v] != INF){
        if(d[v] > G[u][v]){
          d[v] = G[u][v];
          pi[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
  for(i=0;i<n;i++){
    if(pi[i] != NIL)sum += G[i][pi[i]];
  }
  printf("%d\n",sum);
}

int main(){
  int e;
  int i,j;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    if(i<n)break;
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      if(e == -1){
        G[i][j] = INF;
      }else{
        G[i][j] = e;
      }
    }
  }

  prim();
  return 0;
}



Measured memory_bytes: 2108
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N=2010;
const ll mod=1e9+7;
ll f[N];
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int s;
        cin>>s;
        f[0]=1;
        for(int i=3;i<=s;i++)
            for(int j=3;j<=i;j++)
                f[i]=(f[i]+f[i-j])%mod;
    
        cout<<f[s]<<'\n';
    }
    return 0;
}


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

int main(){
	int A,B;

	cin >> A >> B;

	int plug = 1;
	int cnt = 0;
	while(true){
		if( plug >= B )break;
		plug += (A - 1);
		cnt++;
	}
	
	cout << cnt << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<utility>
#include<algorithm>
#define MP make_pair
using namespace std;
typedef pair<int, int> P;

const int MAX_LEN = 3003;
pair<int, P> dp[MAX_LEN][MAX_LEN];
bool s_is_used[MAX_LEN], t_is_used[MAX_LEN];

int main() {
    string s, t;
    cin >> s >> t;
    for (int i = 0; i <= s.length(); i++) {
        dp[i][0] = MP(0, MP(-1, -1));
    }
    for (int i = 0; i <= t.length(); i++) {
        dp[0][i] = MP(0, MP(-1, -1));
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= t.length(); j++) {
            if (dp[i - 1][j].first > dp[i][j - 1].first) dp[i][j] = MP(dp[i - 1][j].first, MP(i - 1, j));
            else dp[i][j] = MP(dp[i][j - 1].first, MP(i, j - 1));
            if (s[i - 1] == t[j - 1] && dp[i][j].first < dp[i - 1][j - 1].first + 1) {
                dp[i][j] = MP(dp[i - 1][j - 1].first + 1, MP(i - 1, j - 1));
            }
        }
    }
    int s_len = s.length() - 1, t_len = t.length() - 1;
    string ans = "";
    while (s_len >= 0 && t_len >= 0 && ans.length() < dp[s.length()][t.length()].first) {
        if (s[s_len] == t[t_len] && !s_is_used[s_len] && !t_is_used[t_len]) {
            ans.push_back(s[s_len]);
            s_is_used[s_len] = t_is_used[t_len] = true;
        }
        P prev_state = dp[s_len + 1][t_len + 1].second;
        s_len = prev_state.first - 1;
        t_len = prev_state.second - 1;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 105856
/*
─────────────────────
───────────████████──
──────────███▄███████
──────────███████████
──────────███████████
──────────██████─────
──────────█████████──
█───────███████──────
██────████████████───
███──██████████──█───
███████████████──────
███████████████──────
─█████████████───────
──███████████────────
────████████─────────
─────███──██─────────
─────██────█─────────
─────█─────█─────────
─────██────██────────
─────────────────────
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define int long long
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; fori (i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; fori (i, 1, n) {fori (j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) fori (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) fori (i, 1, n) {fori (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(s) (int)(s.size())
#define pb push_back
#define fi first
#define se second
#define rz resize
#define fori(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define sort1(v) sort(v.begin(), v.end()) 
#define endl '\n'
 
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair <int, int>> vpi;
typedef vector < vector <int> > vvi;
 
const int INF = 4e18;
const int mod = 1e9+7; 
     
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    //start from here

    read(x);

    cout << (x/500)*1000 + ((x%500)/5)*5;

    return 0;
}


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

using namespace std;
int w,h,n,ans;
int main(){
	cin >> w >> h >> n;
	int ex,ey,x,y;
	cin >> ex >> ey;
	for(int i = 2;i <= n;i++){
		cin >> x >> y;
		int a=abs(x-ex),b=abs(y-ey);
		ans += a + b;
		if(x < ex && y < ey)ans-=min(a,b);
		if(x > ex && y > ey)ans-=min(a,b);
		ex=x,ey=y;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1160
#include<stdio.h>
int main(void){
  double n;
  while(scanf("%lf",&n)!=EOF){
    if(n<=48.00)printf("light fly");
    else if(48.00<n&&n<=51.00)printf("fly");
    else if(51.00<n&&n<=54.00)printf("bantam");
    else if(54.00<n&&n<=57.00)printf("feather");
    else if(57.00<n&&n<=60.00)printf("light");
    else if(60.00<n&&n<=64.00)printf("light welter");
    else if(64.00<n&&n<=69.00)printf("welter");
    else if(69.00<n&&n<=75.00)printf("light middle");
    else if(75.00<n&&n<=81.00)printf("middle");
    else if(81.00<n&&n<=91.00)printf("light heavy");
    else printf("heavy");
    printf("\n");
  }
  return 0;
}

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

int main (){
    while(1){
        int mH,mW;
        cin>>mH>>mW;
        if((mH==0)&&(mW==0))break;
        for(int i=0;i<mH;i++){
            for(int j=0;j<mW;j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3104
import * as fs from "fs";

const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
//const n = +input[0];
//const a = [];
//for(let i=0;i<n;i++){
//	a.push(input[i+1].split(" ").map((x:string):number=>+x));
//}

//const [n, m] = input[0].split(" ").map((x: string): number => +x);
//const a = input[1].split(" ").map((x: string): number => +x);

function compareFunc(a, b){
    return a-b;
}

const n: number = +input[0];
const d: number[] = input[1].split(' ').map((x: string): number => +x);

let ans: number = 0;

for(let i = 0; i < n; i++){
    for(let j = i+1; j < n; j++){
        ans += d[i] * d[j];
    }
}
console.log(ans);

Measured memory_bytes: 7500
// B - Minor Change
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s, t; cin>>s>>t;
	int n = s.size();
	int ans = 0;
	for(int i=0; i<n; ++i) if(s[i] != t[i]) ans++;
	cout<< ans <<endl;
}


Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 60;

int N;
int a[Nmax];

int main() {
	cin >> N;
	int buf = 0, memo = 0;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		if (abs(buf) <= abs(a[i])) {
			memo = i;
			buf = a[i];
		}
	}

	if (buf == 0) {
		cout << 0 << endl;
		return 0;
	}

	cout << 2 * N - 1 << endl;
	for (int i = 1; i <= N; i++) {
		cout << memo << " " << i << endl;
	}
	if (buf > 0) {
		for (int i = 1; i <= N - 1; i++) {
			cout << i << " " << i + 1 << endl;
		}
	}
	else {
		for (int i = N; i >= 2; i--) {
			cout << i << " " << i - 1 << endl;
		}
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
#define P pair<int,int>
typedef long long ll;
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> a;
    rep(i,n){
        int num; cin >> num;
            if(a.empty()){
                a.push_back(num);
                continue;
            }
            if(num<=a[a.size()-1]){
                a.push_back(num);
                continue;
            }
            int l=0; int r=a.size()-1;
            while(r!=l){
                int next=(r+l)/2;
                if(a[next]<num) r=next;
                else l=next+1;
            }
            a[r]=num;
    }

    cout << a.size() << endl;
return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 5;
int N, H, Ans;
struct Katana {
	int A, B, Id;
}Set[MAXN];
bool Flag = false;
inline bool cmpByA(const Katana &A, const Katana &B)
{
	return A.A == B.A ? A.B > B.B : A.A > B.A;
}
inline bool cmpByB(const Katana &A, const Katana &B)
{
	return A.B > B.B;
}
inline void Throw(int valueReduced)
{
	if(H > valueReduced) H -= valueReduced, ++Ans;
	else {
		cout << Ans + 1 << endl;
	    Flag = true;
	}
}
inline void Wield(int wieldValue)
{
	if(H > 0){
		Ans += H / wieldValue;
		if((H % wieldValue))++Ans;
	}
	cout << Ans << endl;
}
int main()
{
	scanf("%d%d", &N, &H);
	for(int I = 1; I <= N; ++I)
		scanf("%d%d", &Set[I].A, &Set[I].B), Set[I].Id = I;
	sort(Set + 1, Set + N + 1, cmpByA);
	int maxA = Set[1].A, maxBInMaxA = Set[1].B, maxAId = Set[1].Id;
	sort(Set + 1, Set + N + 1, cmpByB);
	for(int I = 1; I <= N; ++I)
		if(Set[I].B > maxA){
			Throw(Set[I].B);
			if(Flag)return 0;
		}else break;
	Wield(maxA);
	return 0;
}


Measured memory_bytes: 1408
var main = (lines) => {
	var N = Number(lines[0])
    var As = lines[1].split(" ").map(Number)
    const isOdd = Boolean(As.filter(x=>x<0).length % 2)
    let minNum = Infinity
    let result = As.reduce((acc,x)=>{
      const absx = Math.abs(x) 
      if (absx < minNum) minNum = absx 
      return acc + absx
    }, 0)
  	if(isOdd) result -= minNum * 2
  console.log(result)
}

main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));

Measured memory_bytes: 29672
#include <stdio.h>

int main(void)
{
	int n,x,i;
	x=0;
	scanf("%d",&n);
	
	for(i=n;i>0;i--)
	{	
		x=x+i;
	}
	printf("%d\n",x);
	
	return 0;
	
}

Measured memory_bytes: 128
n,m,r=map(int,input().split());
a=n+r-n*m-1;b=r-n*m;
s=1;
if a<b or a<0 or b<0:s=0;
else:
    if b>a-b:b=a-b;
    for i in range(b):s=s*(a-i)//(i+1);
print(s)


Measured memory_bytes: 5596
#include <stdio.h>
#include <string.h>
#define lop(i, n) for(i=0; i<n; i++)

int main()
{
	int a, b;
	
	scanf("%d %d", &a, &b);
	
	printf("%d", (a>9 || b>9)?(-1):(a*b));
	
return 0;
}

Measured memory_bytes: 128
from math import gcd
K = int(input())
ans = 0
for i in range(1,K + 1):
    for j in range(1,K + 1):
        if gcd(i,j) == 1: ans += K
        else:
            for k in range(1,K + 1):
                ans += gcd(gcd(i,j),k)
print(ans)


Measured memory_bytes: 68180
#include <bits/stdc++.h>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
typedef long long ll;
 
ll k; 
 
ll func(ll n,ll cur){
	ll ret=n-n/k-1;
	return ret-cur;
}
 
using namespace std;
int main(void){
	int n;
	cin >> n >> k;
	ll cur=0;
	for(int i = 0; i < n-1; i++) {
		ll l=0LL,r=1e18;
		while(r-l>1){
			ll m=(l+r)/2;
			ll ret=func(m,cur);
			if(ret>0||(ret==0&&m%k==0))
				r=m;
			else
			l=m;					
		}
		cur=l;
	}
	cout << cur << endl;
    return 0;
}

Measured memory_bytes: 3096
#include "bits/stdc++.h"
using namespace std;
int INF = numeric_limits<int>::max() / 2;
using ll = long long;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
    }
    cout << 1 + (n-2)/(k-1) << endl;
    return 0;
}

Measured memory_bytes: 256