akhauriyash/Code-Regression huggingface dataset:
string = input()
acgt = ['A', 'C', 'G', 'T']

max_length_str = ''
tmp_str = ''
for n in string:
  if n in acgt:
    tmp_str += n
  else:
    if len(tmp_str) > len(max_length_str):
      max_length_str = tmp_str
      tmp_str = ''

if len(tmp_str) > len(max_length_str):
  max_length_str = tmp_str
  tmp_str = ''

print(len(max_length_str))


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

using namespace std;

typedef long long ll;

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

	string s;
	cin >> s;

	if(s == "ABC"){
		cout << "ARC" << endl;
	}else{
		cout << "ABC" << endl;
	}

}


Measured memory_bytes: 3652
import java.text.DecimalFormat;
import java.io.*;
import java.util.*;
import java.util.function.BiFunction;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        DecimalFormat df = new DecimalFormat("0.0000000000");
        
        final int N = Integer.parseInt(sc.next());
        int[] x = new int[N];
        int[] y = new int[N];
        int[] p = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = Integer.parseInt(sc.next());
            y[i] = Integer.parseInt(sc.next());
        }
        for (int i = 0; i < N; i++) p[i] = i;
        double len = 0.0;
        double lap = 0.0; 
        BiFunction<Integer, Integer, Double> dist = (i, j) -> {
            double dx = x[i] - x[j];
            double dy = y[i] - y[j];
            return Math.sqrt(dx * dx + dy * dy);
        };
        
        do {
            ++lap;
            for (int i = 0; i < N - 1; i++) {
                len += dist.apply(p[i], p[i+1]);
            }
        } while (nextPermutation(p));
        
        out.println(df.format(len / lap));
        
        out.flush();
    }

    public static boolean nextPermutation(int[] a) {
        for (int i = a.length - 1; 0 < i; i--) {
            if (a[i - 1] < a[i]) {
                int index = find(a[i - 1], a, i, a.length - 1);
                int temp = a[index];
                a[index] = a[i - 1];
                a[i - 1] = temp;
                Arrays.sort(a, i, a.length);
                return true;
            }
        }
        return false;
    }

    // destより大きい要素の中で最小のもののインデックスを二分探索で探す
    private static int find(int dest, int[] a, int s, int e) {
        if (s == e) {
            return s;
        }
        int m = (s + e + 1) / 2;
        return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
    }
}

Measured memory_bytes: 33484
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int num,count;
  count=0;
  cin>>num;
  vector<char> v;
  for(int i=0; i<num;i++){
    char tmp;
    cin>>tmp;
    v.push_back(tmp);
  }
  for(int i=0;i<num;i++){
    if(v[i]!=v[i+1]){
      count++;
    }
  }
  cout<<count<<endl;
}




Measured memory_bytes: 512
N=int(input())
# N=100
n=str(N)
Length=len(n)

l=list(n)

if l[1:]==['9']*(Length-1):
    ans=int(n[0])+9*(Length-1)
else:
    ans=int(n[0])-1+9*(Length-1)

print(ans)

Measured memory_bytes: 9000
n = int(input())
lst = [int(i) for i in input().split()]

stock = 0
money = 1000
for i in range(n):
  if i < n - 1:
    if lst[i] <= lst[i + 1]:
      stock += money // lst[i]
      money = money % lst[i]
    if lst[i] > lst[i + 1]:
      if stock > 0:
        money += stock * lst[i]
        stock = 0
  if i == n - 1:
    if stock > 0:
      money += stock * lst[i]
      stock = 0
  #print(money)
print(money)

Measured memory_bytes: 9172
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
    char input[10000];
    int n,i,len;
    scanf("%d",&n);
    scanf("%s",input);

    len = strlen(input);

    for(i=0;i<len;i++){
        if(input[i] + n > 'Z'){
            input[i] = 'A' + (input[i] + n - 'Z') - 1;
        }else
        {
            input[i] = input[i] + n;
        }
    }
    printf("%s",input);
    

    return 0;
}

Measured memory_bytes: 128
// 入力マクロ
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// from std
pub use std::cmp::{max, min};
pub use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};

fn main() {
    input! {
        n: usize,
        happiness: [[usize; 3]; n]
    }

    let mut dp = vec![vec![0; 3]; n+1];

    for i in 1..n+1 {
        for j in 0..3 {
            for k in 0..3 {
                if j == k { continue; }
                dp[i][k] = max(dp[i][k], dp[i-1][j] + happiness[i-1][k]);
            }
        }
    }

    let ans = dp[n].iter().max().unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 18684
import math
X = int(input())
if X ==2:
    print(2)
    exit()
elif X%2 == 0:
    X += 1
X -= 2
while True:
    X +=2
    for i in range(2,math.ceil(X**0.5)):
        if X%i ==0:
            break
    else:
        print(X)
        exit()

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

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}


int main() {
int n;cin>>n;
int p[n],q[n];rep(i,n)cin>>p[i];
rep(i,n)cin >>q[i];
int w[n];rep(i,n)w[i]=i+1;
int ans = 0,count =1,count1=0;
    do{
        if(equal(w, w+n, p))ans=count;
        if(equal(w, w+n, q))count1=count;
        count++;
    }while(next_permutation(w,w+n));
    cout << abs(ans-count1) << endl;
    
return 0;

}


Measured memory_bytes: 256
using System;
class Program{
	static void Main(){
		long n=long.Parse(Console.ReadLine());
		long s=long.Parse(Console.ReadLine());
		long ans=n-s+1;
		if(n==s){ans=n+1;}
		else if(s>n/2+(n%2)){ans=-1;}
		else{
			int r=(int)Math.Sqrt(n);
			for(int i=2;i<=r;i++){
				if(fu(i,n)==s){ans=i;break;}
				else if((n-s)%i==0&&fu((n-s)/i+1,n)==s){ans=(n-s)/i+1;}
			}
		}
		Console.WriteLine("{0}",ans);
	}
	static long fu(long b,long n){return n<b?n:fu(b,n/b)+n%b;}
}

Measured memory_bytes: 13140
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int dh[8] = { 0,1,1,1,0,-1,-1,-1 };
int dw[8] = { 1,1,0,-1,-1,-1,0,1 };
vector<string> vs;
map<string, ll> mp;
void solve() {
	int H, W; cin >> H >> W; if (H == 0 and W == 0) exit(0);
	vs.resize(H); for (int i = 0; i < H; i++) cin >> vs[i];
	mp.clear();
	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			for (int i = 0; i < 8; i++) {
				int nh = h;
				int nw = w;
				string s;
				s += vs[nh][nw];
				while (1) {
					nh += dh[i];
					nw += dw[i];
					if (nh >= H) nh = 0;
					if (nw >= W) nw = 0;
					if (nh < 0) nh = H - 1;
					if (nw < 0) nw = W - 1;
					if (nh == h and nw == w) break;
					s += vs[nh][nw];
					mp[s]++;
				}
			}
		}
	}
	string res;
	for (auto& p : mp) {
		if (p.second >= 2) {
			if (res.size() < p.first.size()) res = p.first;
			else if (res.size() == p.first.size() and res > p.first) res = p.first;
		}
	}
	if (res == "") cout << "0" << "\n";
	else cout << res << "\n";
}

int main()
{
	
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/

	int kkt = 89;
	while (kkt) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 37816
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
#define nin(n) int n; cin >> n;
#define kin(k) int k; cin >> k;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
int main() {
  int n,m; cin >> n >> m;
  vector<int> p(n);
  for(int i=0;i<n;i++){
    cin >> p[i];
  }
  UnionFind tree(n);
  for(int i=0;i<m;i++){
    int x,y;
    cin >> x >> y;
    tree.unite(x-1,y-1);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(tree.same(i,p[i]-1)){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int maxn = 1e6+10;

bool ex[maxn];
int main(){
    int x,n,p;
    cin>>x>>n;
    fo(i,1,n){
        cin>>p;ex[p]=1;
    }
    int ans=0,mi=1000;
    fo(i,0,101){
        if(ex[i]) continue;
        if(abs(i-x)<mi){
            mi=abs(i-x);ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    unsigned long long int n,m;
    cin>>n>>m;
    vector<pair<unsigned long long int,unsigned long long int>>vp;
    for(unsigned long long int i=0;i<n;i++)
    {
        unsigned long long int f,s;
        cin>>f>>s;
        vp.push_back({f,s});
    }
    sort(vp.begin(),vp.end());
    unsigned long long int result=0;
    unsigned long long int index=0;
    while(m){
        if(m>vp[index].second){
            m-=vp[index].second;
            result+=vp[index].first*vp[index].second;
        }
        else{
            result+=vp[index].first*m;
            m=0;
        }
        index++;
    }
    cout<<result;
}

Measured memory_bytes: 5352
#include<bits/stdc++.h>
using namespace std;
main(){
  int c[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>c[i][j];
    }
  }
  int a1=0,a2,a3,b1=c[0][0],b2=c[0][1],b3=c[0][2];
  a2=c[1][0]-b1;
  a3=c[2][0]-b1;
  int ju=1;
    for(int i=0;i<=c[0][0];i++){
      b1=c[0][0]-a1;
      b2=c[0][1]-a1;
      b3=c[0][2]-a1;
      a2=c[1][0]-b1;
      a3=c[2][0]-b1;
      if(b1+a2==c[1][0] && b1+a3==c[2][0] && b2+a2==c[1][1] && b2+a3==c[2][1]\
   && b3+a2==c[1][2] && b3+a3==c[2][2]) ju=0;
    }
    if(ju) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAXN	205
#define P	998244353
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
struct point {int x, y; };
point operator + (point a, point b) {return (point) {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) {return (point) {a.x - b.x, a.y - b.y}; }
int operator * (point a, point b) {return a.x * b.y - a.y * b.x; }
point a[MAXN];
long long fac[MAXN], inv[MAXN];
long long power(long long x, long long y) {
	if (y == 0) return 1;
	long long tmp = power(x, y / 2);
	if (y % 2 == 0) return tmp * tmp % P;
	else return tmp * tmp % P * x % P;
}
long long getc(int x, int y) {
	if (x < y) return 0;
	else return fac[x] * inv[y] % P * inv[x - y] % P;
}
bool online(point a, point b, point c) {
	return (c - a) * (b - a) == 0;
}
void update(long long &a, long long b) {
	a = (a - b + P) % P;
}
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(a[i].x), read(a[i].y);
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % P;
	inv[n] = power(fac[n], P - 2);
	for (int i = n - 1; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % P;
	long long ans = 1;
	for (int i = 1; i <= n; i++)
		ans = ans * 2 % P;
	update(ans, n + 1); update(ans, getc(n, 2));
	for (int i = 1; i <= n; i++)
	for (int j = i + 1; j <= n; j++) {
		bool halted = false;
		for (int k = 1; k < j; k++)
			if (k != i && online(a[i], a[j], a[k])) {
				halted = true;
				break;
			}
		if (halted) continue;
		int cnt = 2;
		for (int k = j + 1; k <= n; k++)
			if (online(a[i], a[j], a[k])) cnt++;
		for (int k = 3; k <= cnt; k++)
			update(ans, getc(cnt, k));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a;
    map<int,int> cnt;
    cin >> n;
    rep(i,n){
        cin >> a;
        cnt[a]++;
    }
    int ans = 0;
    for (auto i = cnt.begin();i != cnt.end();i++){
        if ((*i).second%2) ans++;
    }
    PRINT(ans);
}

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

const int N = 1e5 + 5;

int32_t main()
{
	IOS;
	int a, b;
	cin >> a >> b;
	cout << a * b;
	return 0;
}

Measured memory_bytes: 3652
using System;
using System.Collections.Generic;

namespace AtCoder
{
    internal static class Program
    {
        private static void Main()
        {
            int S = int.Parse(Console.ReadLine());
            List<int> fn = new List<int>();
            int res = -1;
            fn.Add(S);

            for(int i = 0; i < 1000000; i++)
            {
                if (S % 2 == 0)
                {
                    S /= 2;
                }
                else
                {
                    S = S * 3 + 1;
                }

                fn.Add(S);

                for(int y = 0; y < fn.Count; y++)
                {
                    for (int x = 0; x < fn.Count && x != y; x++)
                    {
                        if(fn[y] == fn[x])
                        {
                            res = y + 1;
                            break;
                        }
                    }
                }

                if (res != -1)
                    break;
            }

            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 13140
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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

void trace(int A[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

using ll = long long;
using P = pair<int, int>;

const unsigned long long INF = 1LL << 60;

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

int main() {
    int K, N;
    int A[200010];
    cin >> K >> N;
    rep(i, N) cin >> A[i];

    // 各点の距離の中で最大のものを求める
    int max_l = 0;
    for (int i = 0; i < N; ++i) {
        if (i + 1 == N) {
            max_l = max(max_l, A[0] + K - A[i]);
        } else {
            max_l = max(max_l, A[i + 1] - A[i]);
        }
    }
    // 円周から最も長い部分を引いた残りが最短移動距離
    cout << K - max_l << endl;
}


Measured memory_bytes: 1024
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse! {it, n:usize};
    let mut ret = 0;
    for i in 1..=n {
        if i % 5 != 0 && i % 3 != 0 {
            ret += i;
        }
    }
    println!("{}", ret);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 2120
#include<stdio.h>
#include<string.h>

int main()
{
    int n, x, t, a = 0;

    scanf("%d %d %d", &n, &x, &t);

    a = (n/x)*t;

    if ((n%x) != 0)
    {
        a += t;
    }

    printf("%d", a);

    return 0;
}

Measured memory_bytes: 1728
class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def size
    @data.size
  end

  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx] > @data[target_idx])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    # child がある場合
    while (has_child?(target_idx))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      # 右側の child が無い場合
      if @data[b].nil?
        if @data[target_idx] > @data[a]
          swap(target_idx, a)
        end
        return
      end

      c = @data[a] < @data[b] ? a : b

      if @data[target_idx] > @data[c]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < (@data.size - 1)
  end
end


N, M = gets.chomp.split(' ').map(&:to_i)

AB = []
N.times do |i|
  AB[i] = gets.chomp.split(' ').map(&:to_i)
end

group_by_day = Hash[AB.group_by{|v|v[0]}.sort]

day_fee = Array.new(M){[]}
group_by_day.each do |k,v|
  day_fee[k-1] = v.map{|j| j[1]}
end

# require 'pry'
# binding.pry

ans = 0
pq = PriorityQueue.new
day_fee.each_with_index do |fees, idx|
  break if idx > M - 1
  fees.each do |fee|
    pq.push(fee*(-1))
  end
  ans += pq.pop.to_i
  # p pq
  # p pq.pop*(-1)
end

puts ans*(-1)


Measured memory_bytes: 38284
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main
{
	public static void main(String[] args) throws Exception
	{
		invoke(System.in);
	}

	public static void	invoke(InputStream is) throws IOException
	{
		try (Scanner in = new Scanner(is))
		{
			int	n = in.nextInt();
			int	h = in.nextInt();

			SW[]	sw = new SW[n];
			int	maxA = 0;
			for (int i = 0; i < n; ++i)
			{
				sw[i] = new SW();
				sw[i].a = in.nextInt();
				sw[i].b = in.nextInt();

				if (sw[i].a > maxA)
				{
					maxA = sw[i].a;
				}
			}

			Arrays.sort(sw, new Comparator<SW>(){
				@Override
				public int compare(SW s0, SW s1)
				{
					return s1.b - s0.b;
				}});

			int	attackB = 0;
			int	useB;
			for (useB = 0; useB < n; ++useB)
			{
				if (sw[useB].b < maxA)
				{
					break;
				}
				h -= sw[useB].b;
				++attackB;
				if (h <= 0)
				{
					System.out.println(attackB);
					return;
				}
			}

			int	aAttack = (h + maxA - 1) / maxA;

			System.out.println(attackB + aAttack);
		}
	}


	public static class	SW
	{
		public int a;
		public int b;
	}
}

Measured memory_bytes: 83664
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) {
	  FastReader sc = new FastReader();
	  int a = sc.nextInt();
	  int b = sc.nextInt();
	  	  
	  if ((a*b) % 2 == 0) {
		  System.out.println("No");
		  System.exit(0);
	  }
	  
	  System.out.println("Yes");
	  System.exit(0);
  }
  
  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: 21076
import sys
#大きすぎるとダメ
h,w=map(int,input().split())
sys.setrecursionlimit(h*w+10)
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




Measured memory_bytes: 67548
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll inf = 1e10;
ll w[105], v[105];
ll dp[300005] = {};
ll t[200005];
ll b[200005];
int main() {
	ll n,T;
	cin >> n >> T;
	
	for (int i = 0; i < n; i++) {
		cin >> t[i];
	}
	ll sum = 0;
	for (int i = 0; i < n - 1; i++) {
		if (t[i + 1] - t[i] <T) {
			sum += t[i + 1] - t[i];
		}
		else {
			sum += T;
		}
	}
	cout << sum+T << endl;
	return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

// int main() {
//     ll A[6];
//     rep(i,2){
//         cin >> A[i];
//     }
//     //sort(A,A+3);
//     cout << (A[0]+A[1]) %24 << endl;
// }

int main(){
    char X[108],Y[108],Z[108];cin >> X >> Y;

    cout <<(X[0]==Y[0] ? "H" : "D")<<endl;;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001

int main(void) {
	string s,t; cin >> s >> t;
	int a,b; cin >> a >> b;
	string u; cin >> u;
	if(s==u) a--;
	else b--;
	cout << a << " " << b << endl;
}




Measured memory_bytes: 256
fun main(args:Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val num = mutableListOf<Int?>()
    num.addAll((1..n).map { null })
    val query = (1..m).map { readLine()!!.split(" ").map { it.toInt() }.let { listOf(it[0]-1,it[1]) } }
    for(tmp in query) {
        val idx = tmp[0]
        if(num[idx] == null) {
            num[idx] = tmp[1]
        } else {
            if(num[idx]!! != tmp[1]) {
                println(-1)
                return
            }
        }
    }
    for(i in num.indices) {
        if(num[i] == null) {
            if(num.size > 1 && i == 0) {
                num[i] = 1
            } else {
                num[i] = 0
            }
        }
    }
    if(num.size > 1 && num[0] == 0) {
        println(-1)
        return
    }
    println(num.joinToString(""))

}


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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;
using vvs = vector<vs>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, (int)v.size()) {
        if (i)
            os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
    for (auto val : array)
        std::cout << val << ", ";
    std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::setprecision(10);

    string s, t; std::cin >> s >> t;
    vvi idx(27);
    int slen = s.size(), tlen = t.size();
    rep(i, slen) {
        idx[s[i]-'a'].pb(i);
    }
    ll cur = -1, ans = 0;
    rep(i, tlen) {
        if (idx[t[i]-'a'].size() == 0) {
            ans = -1;
            break;
        }
        auto it = upper_bound(rng(idx[t[i]-'a']), cur);
        if (it == idx[t[i]-'a'].end()) {
            ans += slen-(cur+1);
            ans += idx[t[i]-'a'][0]+1;
            cur = idx[t[i]-'a'][0];
        } else {
            ans += *it-cur;
            cur = *it;
        }
    }
    std::cout << ans << "\n";
}


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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define In(vec) rep(i, n) cin>>vec[i];
#define ANS(s) cout << s << endl
#define inc(a, b) cin >> a >> b;

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
using vii = vector<pair<int, int>>;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
int round_int(int a, int b) { return (a + (b - 1)) / b; }


// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

// ────────────────────────────────────────────────────

int main() {
	int m, d;
	cin >> m >> d;
	int cnt = 0;
	for (int i = 1; i <= d; ++i) {
		if (i % 10 >= 2 && i / 10 >= 2) {
			for (int j = 1; j <= m; ++j) {
				if (j == (i / 10) * (i % 10)) cnt++;
			}
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
     
#define pll pair <long long,long long>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define vll vector <ll>
#define NFS ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define M 1000000007   
using namespace std;

void solve()
{
	ll a,b,c;
	cin>>a>>b>>c;
	cout<<c<<" "<<a<<" "<<b;
}
 
int main()
{
    NFS
 	int t=1;
 	//cin>>t;
 	while(t--)
 	{
 		solve();
 	}
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    if(a==b && b==c) {
        if(a%2 == 0) cout << -1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    int count = 0;
    while(a%2==0 && b%2==0 && c%2==0) {
        int na = (b+c)/2;
        int nb = (a+c)/2;
        int nc = (a+b)/2;
        a = na, b = nb, c = nc;
        count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#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 srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 200005;

ll dp[MAX_N][3], a[MAX_N];

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    rep(i,n){
        cin >> a[i];
        rep(j,3){
            if(j == 1){
                cmx(dp[i+1][j], dp[i][j]+((a[i]==0)?(-1):((a[i]-1)/2*2+1)));
            }else{
                cmx(dp[i+1][j], dp[i][j]+((a[i]==0)?(-2):(a[i]/2*2)));
            }
        }
        rep(j,2){
            cmx(dp[i+1][j+1], dp[i+1][j]);
        }
        cmx(ans, dp[i+1][2]);
    }
    cout << accumulate(a, a+n, 0LL) - ans << "\n";
    return 0;
}

Measured memory_bytes: 6528
//
// Created by Takaaki Hirano on 2018/09/05.
//
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

int abc[3], X, Y;

void solve() {
    int A = abc[0], B = abc[1], C = abc[2];
    int normal = A * X + B * Y;
    if (X > Y) {
        cout << min(X * 2 * C, min(Y * 2 * C + max(X - Y, 0) * A, normal)) << endl;
    } else {
        cout << min(Y * 2 * C, min(X * 2 * C + max(Y - X, 0) * B, normal)) << endl;
    }
}

int main() {
    REP(i, 3)cin >> abc[i];
    cin >> X >> Y;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h> 
#define MAX 10000
int D[50][50];
int max(int max1,int max2)
{
	if(max1>max2)
	return max1;
	else
	return max2;
}
int min(int min1,int min2)
{
	if(min1<min2)
	return min1;
	else
	return min2;
}
int main(){
    int i,j,k,n,ma,ga,ok,gg,ab,sum;

   
     while(scanf("%d",&ga),ga!=0)
     {
	 
    memset(D,0x3f,sizeof(D));
    
    n=-1;
   for(i=0;i<ga;i++)
   {
   	scanf("%d%d%d",&ma,&j,&ab);
   	if(D[ma][j] > ab)
   	D[ma][j] = D[j][ma]=ab;
   	n=max(n,ma);
   	n=max(n,j);
   }
   for(i=0;i<n+1;i++)
   {
   	D[i][i]=0;
   }
     for(k=0;k<n+1;k++){
        for(i=0;i<n+1;i++){
            for(j=0;j<n+1;j++){
                if(D[i][j]>D[i][k]+D[k][j]){
                    D[i][j]=D[i][k]+D[k][j];
                   
                }
            }
        }
    }
  ok=99999999;
    for(i=0;i<n+1;i++)
	{
		sum=0;
        for(j=0;j<n+1;j++){
           
           sum=sum+D[i][j];
          
            }
           if(ok > sum)
           ok = sum, gg = i;
        }
        printf("%d %d\n",gg,ok);
		}
        return 0;
    }


   

Measured memory_bytes: 616
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
const ll MOD = 1e9 + 7;

// Binary Indexed Tree （indexは1始まり）
// T は +-*/ と 0 を持つ
template<class T> class BIT {
private:
	int N; // 要素数
	vector<T> nodes;

public:
	BIT(int N) {
		this->N = N;
		nodes.assign(N+1, 0);
	}

	// index k の値にxを加える
	void add(int k, T x) {
		for (int i=k; i<=N; i += (i & -i)) {
			nodes[i] += x;
		}
	}

	// 半開区間 [0, k) の合計を返す
	T sum(int k) {
		T result = 0;
		for (int i=k-1; i>0; i -= (i & -i)) {
			result += nodes[i];
		}

		return result;
	}

	// 半開区間 [s, t) の合計を返す
	T sum(int s, int t) {
		return sum(t) - sum(s);
	}
};

// 数列Xの転倒数を求める
ll count_inversions(vector<ll>& X) {
	int N = X.size();
	BIT<ll> bit(N+1); // ひとつ余分に確保
	unordered_map<ll, int> X_to_sorted_idx;

	vector<ll> X_sorted = X;
	sort(X_sorted.begin(), X_sorted.end());

	for (int i=0; i<N; i++) {
		if (! X_to_sorted_idx[X_sorted[i]]) X_to_sorted_idx[X_sorted[i]] = i + 1; // 1-idx
	}

	ll result = 0;

	for (int i=0; i<N; i++) {
		result += bit.sum(X_to_sorted_idx[X[i]] + 1, N+2);
		bit.add(X_to_sorted_idx[X[i]], 1);

	}

	return result;
}

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

	vector<ll> A(N);
	vector<ll> B(N*2);

	for (int i=0; i<N; i++) {
		cin >> A[i];
		B[i] = A[i];
		B[i+N] = A[i];
	}

	ll A_inv = count_inversions(A);
	ll B_inv = count_inversions(B);

	ll ans = ((A_inv * K) % MOD + ((B_inv - A_inv * 2) * (K * (K-1) / 2 % MOD)) % MOD) % MOD;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3740
#include <iostream>
#include <vector>

using namespace std;

int main(){
	vector<int> cards;
	vector<int> ::iterator cardsIterator;
	vector<int> ::iterator shuffuleIterator;
	int n,r,p,c;

	while(cin >> n >> r, n && r){
		cards.clear(); //初期化
		// カードの山生成
		for (int i = 0; i < n; ++i){
			cards.push_back(i+1);
		}
		// シャッフル
		while(cin >> p >> c, r--){
			cardsIterator = cards.end();
			cardsIterator -= p + (c - 1);
			while(c--){
				cards.push_back(*cardsIterator);
				cards.erase(cardsIterator);
			}
			if (r == 0){
				break;
			}
		}
		// 一番上のカード表示
		cout << cards.back() << endl;
	}
}

Measured memory_bytes: 1220
#include<iostream>
using namespace std;
typedef long long LL;

const LL mod=1e9+7;
const int N=1e5+10;

LL n;
int a[N];
LL f[N];
void init()
{
    f[0]=1;
    for(LL i=1;i<=100000;i++)
        f[i]=f[i-1]*i%mod;
}
 
int main()
{
    init();
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    LL ans=1;
    LL b=1;
    LL num=0;
    for(LL i=2;i<=n;i++)
    {
        if(b+2<=a[i])
            b=b+2;
        else
        {
            ans=ans*(i-num)%mod;
            num++;
        }
    }
    ans=ans*f[n-num]%mod;
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 1408
/*_BELIEVE_*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int          long long int
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     __gcd((a),(b))
#define     lcm(a,b)     ((a)*(b))/gcd((a),(b))
#define     pb           push_back
#define     ins          insert
#define     F            first
#define     S            second

const int inf=1e18,M=1e9+7;

void solve()
{
 int n,a,b;
 cin>>n>>a>>b;
 cout<<min(n*a,b);
}

int32_t main()
{
 fast();

 int t=1;
 //cin>>t;
 while(t--)
 {
  solve();
 }

 return 0;
}



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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int D;
ll ans = 0;

ll rev(ll x) {
    string s = to_string(x);
    reverse(all(s));
    return stoll(s);
}

void solve(int dig) {
    vl tmp;
    ll ret = 0;
    for (int i = 0; i < dig-1-i; ++i) {
        ll z = (ll)pow(10,dig-1-i)-(ll)pow(10,i);
        z /= 9;
        tmp.pb(z);
    }
    map<ll,int> dif, DIF; dif[D] = 1;
    
    bool beg = 1;
    for (auto a: tmp) {
        while (a % 10 == 0) a /= 10;
        
        swap(dif,DIF); dif.clear();
        for (auto b: DIF) {
            F0R(i,10) {
                if (i == 0 && beg) continue;
                F0R(j,10) {
                    ll ne = b.f-(j-i)*a;
                    if (ne % 10 == 0) dif[ne/10] += b.s;
                }
            }
        }
        
        beg = 0;
    }
    ret = dif[0];
    if (dig % 2 == 1) ret *= 10;
    ans += ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> D;
    if (D % 9 != 0) {
        cout << 0;
        exit(0);
    }
    D /= 9;
    FOR(i,2,19) solve(i);
    cout << ans;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <stack>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;

int main()
{
    int n, s, t;
    while(cin >> n){
        s = 0;
        for (int i = 0; i < n/4; i++){
            cin >> t;
            s += t;
        }
      if (n != 0)
        cout << s << endl;
    
    }
    return 0;
}


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

int main()
{

  int n, d;
  cin >> n >> d;
  int ans = 0;
  int x = 0;
  while (x < n){
    x = x + d * 2 + 1;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3596
import java.util.Scanner;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int A = sc.nextInt();
   int B = sc.nextInt();
   int w = A+B;
   int s = A-B;
   int seki = A*B;
   
   int M1 = Math.max(w,s);
   int M = Math.max(M1,seki);

   System.out.println(M);
 }
}

Measured memory_bytes: 21588
n = int(input())
s = list(input())
i = 0
Answer = "No"
if n%2 == 0:
  while i < n/2 :
    if s[i] == s[int((n/2))+i]:
      Answer = "Yes"
      i += 1
    else:
      Answer = "No"
      break
print(Answer)

Measured memory_bytes: 3060
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0

for i in range(n-1):
    ans += a[i]//2
    if a[i]%2 == 1 and a[i+1] > 0:
        a[i+1]-=1
        ans += 1

ans += a[n-1]//2
print(ans)


Measured memory_bytes: 7072