akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace ABC169D
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = long.Parse(Console.ReadLine());

            var fact = Prime.PrimeFactors(N).ToArray();

            Dictionary<long, int> count = new Dictionary<long, int>();
            for (int i = 0; i < fact.Count(); i++)
            {
                if (count.ContainsKey(fact[i])) count[fact[i]]++;
                else count.Add(fact[i], 1);
            }

            long ans = 0;
            foreach (var c in count)
            {
                int a = 2;
                int val = c.Value;
                while (val > 0)
                {
                    ans++;
                    val -= a;
                    a++;
                }
            }

            if (N == 1) ans = 0;
            if (fact.Length == 1) ans = 1;

            Console.WriteLine(ans);
        }

        /// <summary>
        /// 自然数n以下の素数prime列挙 (NloglogN)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int[] PrimeNumbers(int n)
        {
            int max = n;
            var searchList = Enumerable.Range(2, max).ToList();

            var pList = new List<int>();
            while (searchList.Count > 0)
            {
                int cand = searchList.First();

                pList.Add(cand);

                searchList.RemoveAll(x => x % cand == 0);
            }

            return pList.ToArray();
        }

        /// <summary>
        /// 自然数nの素因数分解 
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static long[] PrimeFactorization(long n, List<int> pList)
        {
            long N = n;
            //var pList = PrimeNumbers((int)Math.Sqrt(n)).ToList();

            var ansList = new List<long>();
            for (int i = 0; i < pList.Count;)
            {
                if (N % pList[i] == 0)
                {
                    ansList.Add(pList[i]);
                    N /= pList[i];
                }
                else i++;
            }
            if (ansList.Count == 0 || N != 1) ansList.Add(N);

            return ansList.ToArray();
        }

    }
    public class Prime
    {
        public static IEnumerable<long> PrimeFactors(long n)
        {
            long i = 2;
            long tmp = n;

            while (i * i <= n) //※1
            {
                if (tmp % i == 0)
                {
                    tmp /= i;
                    yield return i;
                }
                else
                {
                    i++;
                }
            }
            if (tmp != 1) yield return tmp;//最後の素数も返す
        }
    }

}


Measured memory_bytes: 28252
// Original macro is in https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = || -> 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)*}
    };
    
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $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, [$t:tt]) => {
        {
            let len = read_value!($next, usize);
            (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")
    };
}

// for adhoc read (ex. https://atcoder.jp/contests/abc112/tasks/abc112_a)
#[allow(dead_code)]
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: i64, b: i64) -> i64 {
    a*b / gcd(a, b)
}

fn main() {
    input!{ mut a: i64, b: i64, c: i64, d: i64 }
    a -= 1;
    let l = lcm(c,d);
    let p = b - b/c - b/d + b/l;
    let q = a - a/c - a/d + a/l;

    println!("{}", p-q);
}

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

const int dx[] = {0, 0, 0, 0, 0, 0, -3, -2, -1, 1, 2, 3};
const int dy[] = {-3, -2, -1, 1, 2, 3, 0, 0, 0, 0, 0, 0};
string mapInfo[8];

void solve(int x, int y)
{
	mapInfo[x][y] = '0';
	for(int i = 0; i < 12; i++)
	{
		const int X = x + dx[i];
		const int Y = y + dy[i];
		
		if(0 <= X && X < 8 && 0 <= Y && Y < 8 && mapInfo[X][Y] == '1') solve(X, Y);
	}
}

int main()
{
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j < 8; j++)
		{
			cin >> mapInfo[j];
		}
		int x, y;
		cin >> x >> y;
		
		
		solve(y - 1, x - 1);
		
		cout << "Data " << i << ":" << endl;
		for(int j = 0; j < 8; j++)
		{
			cout << mapInfo[j] << endl;
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 3160
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();         
        int b = 0;
		int c = 0;
        int d;
		int [] in = new int [9];
        for(int i=0;i<a;i++){d = sc.nextInt()/400;
                             if(d<8){if(in[d]==0){in[d]=1;}}else{in[8]++;}
                            }
        for(int i=0;i<8;i++){b+=in[i];
                            }
        c = b+in[8];
        b = Math.max(b,1);
		System.out.println(b + " " + c);
	}
}


Measured memory_bytes: 21204
#include <iostream>
using namespace std;
const int Size = 105;
int Arr[Size];
int main()
{
    int N, c = 0; cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> Arr[i];
        if (i%2 == 1 && Arr[i] % 2 == 1) c++;
    }
    cout << c << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n, 0);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  for(int i = n - 1; i >= 0; i--) {
    int cnt = 0;
    for(int j = i + 1; j <= n; j += (i + 1)) {
      if(b[j - 1] == 1){
        cnt++;
      }
    }
    if(cnt % 2 != a[i]){
      b[i] = 1;
    }
  }
  int ans = 0;
  for(int i = 0; i < n; i++) {
    if(b[i] == 1){
      ans++;
    }
  }
  cout << ans << '\n';
  for(int i = 0; i < n; i++){
    if(b[i] == 1){
      cout << i + 1 << " ";
    }
  }
  if(ans > 0){
    cout << '\n';
  }
  return 0;
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
ll powmod(ll x,ll n){
    if(n == 0)return 1;
    ll ans = powmod(x*x%MOD,n/2);
    if(n % 2)ans = ans * x % MOD;
    return ans;
}
ll divmod(ll a,ll b){
    return ((a%MOD) * (powmod(b,MOD-2)%MOD)) % MOD;
}
ll combi(ll n,ll r){
    ll num = 1;
    for(ll i = 1;i <= r;i++){
        num = divmod((n-i+1)*num,i);
    }
    return num;
}
ll mul(ll i){
    return (i * (i+1) / 2) % MOD;
}
main(){
    ll N,M,K;
    cin >> N >> M >> K;
    ll table[N][M] = {};
    ll tb1[N] = {}, tb2[M] = {};
    rep(i,0,N){
        tb1[i] = mul(i) + mul(N-i-1);
        //cout << tb1[i] << " \n"[i==N-1];
    }
    rep(i,0,M){
        tb2[i] = mul(i) + mul(M-i-1);
        //cout << tb2[i] << " \n"[i==M-1];
    }

    rep(i,0,N)rep(j,0,M){
        table[i][j] = (tb1[i] * M) % MOD + (tb2[j] * N) % MOD;
        //cout << table[i][j] << " \n"[j==M-1];
    }
    ll sum = 0, r = combi(N * M - 2, K - 2);
    //cout << r << endl;
    rep(i,0,N)rep(j,0,M){
        sum += (table[i][j] * r) % MOD;
        sum %= MOD;
    }
    sum = divmod(sum, 2);
    cout << sum << endl;
}

Measured memory_bytes: 3328
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
        int N, ans = 0;
        cin >> N;
        vector<int> A(N + 1);
        rep(i, N) cin >> A[i];

        bool up = false;
        bool down = false;

        rep(i, N - 1)
        {
                if (up)
                {
                }

                if (A[i] < A[i + 1])
                {
                        up = true;
                }
                else if (A[i] > A[i + 1])
                {
                        down = true;
                }
                else
                {
                        continue;
                }

                if (up && down)
                {
                        ans += 1;
                        up = false;
                        down = false;
                }
        }
        cout << ans + 1 << endl;

        return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
int N;
ll A[10005];
unordered_map <ll, ll> factors;
unordered_map <ll, ll> newfactors;
ll mod = 1000000007;
ll lcm = 1;

ll power(ll b, ll e){
    ll res = 1;
    while (e > 0){
        if (e & 1) res = res * b % mod;
        e /= 2;
        b = b * b % mod;
    }
    return res;
}

ll inverse(ll num){
    return power(num, mod-2);
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++){
        scanf("%lld", &A[i]);
    }
    for (int i=0; i<N; i++){
        int p = sqrt(A[i])+1;
        int copy = A[i];
        for (int j=2; j<=p; j++){
            while (copy%j == 0) {
                newfactors[j]++;
                copy/=j;
            }
        }
        if (copy != 1) newfactors[copy]++;
        for (auto it: newfactors){
            factors[it.first] = max(factors[it.first], it.second);
        }
        newfactors.clear();
    }
    for (auto it: factors){
        lcm *= power(it.first, it.second);
        lcm %= mod;
    }
    ll sum = 0;
    for (int i=0; i<N; i++){
        sum += (lcm * inverse(A[i])) % mod;
        sum %= mod;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 768
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as B
import Data.List
import qualified Data.Map as M
import Control.Monad
import Data.Tuple
import Data.Ord

make :: M.Map B.ByteString Int -> B.ByteString -> M.Map B.ByteString Int
make m bs =
    case M.lookup bs m of
        Just i -> M.adjust (+1) bs m
        Nothing -> M.insert bs 1 m

solve :: [(Int, B.ByteString)] -> (Int, B.ByteString) -> [B.ByteString]
solve [] _ = []
solve ((a,b):xs) (a', b')
    | a == a' = [b] ++ solve xs (a, b)
    | otherwise = []

main = do
    n <- readLn :: IO Int
    strs <- V.replicateM n B.getLine
    let m = V.foldl' (\m s -> make m s) M.empty strs
    let ms = sortBy (comparing Down) $ map swap $ M.toList m
    let res = solve ms (head ms)
    forM_ (sort res) $ \r -> putStrLn $ B.unpack r

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

using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;

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

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ s >> p.first >> p.second; return s;}

int main()
{
    int N, M; ll K; cin >> N >> M >> K;
    vector<ll> A(N); cin >> A;
    vector<ll> B(M); cin >> B;
    vector<ll> pa(N+1);
    partial_sum(A.begin(), A.end(), pa.begin()+1);
    vector<ll> pb(M+1);  
    partial_sum(B.begin(), B.end(), pb.begin()+1);

    int ans = 0;
    int l = 0, r = N + M + 1;
    while (r - l > 1) {
        int c = (l + r) / 2;

        bool ok = false;
        for (int a = 0; a <= min(N, c); a++) {
            int b = c - a;
            if (b > M) continue;
            if (pa[a] + pb[b] <= K) {
                ok = true;
                break;
            }
        }
        if (ok) {
            l = c;
        } else {
            r = c;
        }
    }

    cout << l << endl;
}


Measured memory_bytes: 9580
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define eb emplace_back
using namespace std;
const int MAX_N=2e3+10;
const int mod=1e9+7;
ll a[MAX_N],ans[MAX_N],res=0,n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<i;j++){
            if(a[j]>a[i]){
                ans[i]++;
            }
        }
    }
    for(int i=0;i<n;i++){
        ll cnt=0;
        for(int j=0;j<n;j++){
            if(a[j]>a[i]){
                cnt++;
            }
        }
        (ans[i]*=k)%=mod;
        (ans[i]+=k*(k-1)/2%mod*cnt%mod)%=mod;
    }
    for(int i=0;i<n;i++){
        (res+=ans[i])%=mod;
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  int X;
  cin >> X;
  for(int i = 1; i <= X / 100; i++){
    if(X - 100 * i >= 0 && X - 100 * i <= 5 * i){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
  return 0;
}


Measured memory_bytes: 256
#24 C - Not so Diverse AC
import collections 
N,K = map(int,input().split())
A = list(map(int,input().split()))

cnt = collections.Counter(A)

diff = len(cnt.keys()) - K
# 個数が少ないボールを diff 種類書き換える
values = sorted(list(cnt.values()),reverse = False)
ans = values[:diff]
print(sum(ans))

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

using namespace std;
const int N = 1e5 + 3;
int c[N];
int main() {
//	freopen("input.in", "r", stdin);
	int n, m, cnt = 0, sum = 0;
	scanf("%d %d", &n, &m);
	while (m--) {
		int p;
		char a, b;
		scanf("%d %c%c", &p, &a, &b);
		if (a == 'A') {
			if (c[p] == -1)
				continue;
			++cnt;
			sum += c[p];
			c[p] = -1;
		} else if (c[p] != -1){
			++c[p];
		}
	}
	printf("%d %d\n", cnt, sum);
	return 0;
}




Measured memory_bytes: 640
#include<cmath>
#include<bits/stdc++.h>
#define MAX(a,b) (a>b? a:b)
#define MIN(a,b) (a>b? b:a)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repr(i,n) for(lint i=(lint)(n);i>0;--i)
#define reps(i,a,b) for(lint i=a;i<=(lint)(b);i++)
typedef long long lint;
typedef long double ld;
using namespace std;
const ld PI = acos(-1.0);

int main(){
    string s; cin >> s;
    rep(i,s.size()) if(s[i]==',') s[i]=' ';
    cout << s << endl; 
	return 0;
}

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

#define fio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define tc(t) int t; cin >> t; while (t--)
#define for0(i, n)  for(int i = 0; i < n; i++)
#define pb push_back
#define ll long long 

vector<vector<int>> vis, dist;
vector<vector<char>> g;
int n, m, k, x11, y11, x22, y22;
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, 1, -1};

void bfs() {
  queue<pair<int, int>>q;
  q.push({x11, y11});
  vis[x11][y11] = 1;
  dist[x11][y11] = 0;
  
  int nx, ny;
  while(!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    
    for0(i, 4) {
      for(int len = 1; len <= k; len++) {
        nx = x + dirx[i]*len;
        ny = y + diry[i]*len;
        
        if(nx<1 || ny<1 || nx>n || ny>m)  break;
        if(vis[nx][ny] && dist[x][y] +1 > dist[nx][ny]) break;
        if(g[nx][ny] == '@')  break;
        if(vis[nx][ny]) continue;
        
        vis[nx][ny] = 1;
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
      }
    }
  }
}

void solve()
{
  
  cin>>n>>m>>k;
  cin>>x11>>y11>>x22>>y22;
  vis = dist = vector<vector<int>>(n+1, vector<int>(m+1, 0));
  g = vector<vector<char>>(n+1, vector<char>(m+1));
  for0(i, n)  for0(j, m)  cin>>g[i+1][j+1];
  bfs();
  if(!vis[x22][y22])
    cout<<"-1";
  else
    cout<<dist[x22][y22];
}

signed main() {

  fio;
  //tc(tt) {
    solve();
    cout<<"\n";
  //}
  
  return 0;
}


Measured memory_bytes: 22736
#include<iostream>                                              
#include<string>                                                
#include<algorithm>                                             
                                                                
using namespace std;                                            
                                                                
int main(void) {                                                
  string str;                                                   
  cin >> str;                                                   
  int N;                                                        
  cin >> N;                                                     
  for (int i=0; i<N; i++) {                                     
    string m;                                                   
    cin >> m;                                                   
    if (m=="print") {                                           
      int a, b;                                                 
      cin >> a >> b;                                            
      cout << str.substr(a,b-a+1) << endl;                      
    }                                                           
    else if (m=="reverse") {                                    
      int a,b;                                                  
      cin >> a >> b;                                            
      string::iterator it;                                      
      it=str.begin();                                           
      std::reverse(it+a,it+b+1);                                
    }                                                           
    else if (m=="replace") {                                    
      int a,b;                                                  
      string p;                                                 
      cin >> a >> b >> p;                                       
      for (int i=0; a<=b; i++) {                                
        str[a]=p[i];                                            
        a++;                                                    
      }                                                         
    }                                                           
  }                                                             
}                      

Measured memory_bytes: 3192
N = int(input())
H = [int(i) for i in input().split()]
c = 0
ans = 0
for i in range(N-1):
    if H[i] < H[i+1]:
        ans = max(ans, c)
        c = 0
    else:
        c += 1
ans = max(ans, c)
print(ans)


Measured memory_bytes: 14252
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,a,b=n1()

c=n//(a+b)
d=n%(a+b)
print(c*a+min(a,d))

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int64 comb(int n,int k){
  int64 res=1;
  int i;
  for(i=1;i<=k;i++) res=res*(n+1-i)/i;
  return res;
}

void run(void){
  int n,p;
  scanf("%d%d",&n,&p);
  int cnt[2]={0,0};
  int i;
  for(i=0;i<n;i++){
    int a;
    scanf("%d",&a);
    cnt[a%2]++;
  }
  int64 way=0;
  for(i=p;i<=cnt[1];i+=2){
    way+=comb(cnt[1],i)*(1LL<<cnt[0]);
  }
  printf("%lld\n",way);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
/*#include <ctime>
#include <list>
#include <numeric>
#include <bitset>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <utility>
#include <fstream>
#include <sstream>
#include <cmath>
#include <stack>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <iomanip>
#include <limits>*/

using namespace std;


/// Bismilahir Rahmanir Rahim


typedef unsigned int ui;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef short int si;
typedef unsigned short int usi;
typedef pair <int, int> pii;


#define CASE false
#define TEST false
#define BUFFER true
#define TIME false
#define DEBUG true
#define SET_GEN false
#define File false
#define _ << " " <<
#define __ << "\n"
#define ff first
#define ss second
#define EMPTY_VAL -1
#define RANGE(a, b) (rand() % (b-a+1) + a)


const double pi = acos(-1.);
const double eps = 1e-8;
const int inf = 2147483647;
const int _inf = -2147483648;
const lli INF = 1e18;
const int mod = 1e9+7;
const int maxn = 201;

void delay(int sec); // DEBUG


void solution(void)
{
    int i = 1;
    while (true) {
        int num;
        cin >> num;
        if (num == 0) {
            cout << i __;
            break;
        }
        i++;
    }



    return ;
}

int main(int argc, char *arv[])
{
    #if File
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    #if BUFFER
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #endif

    #if SET_GEN
    srand((unsigned int) time(0));
    #endif

    int t = 1;

    #if CASE
    int cnt = 1;
    #endif

    #if TEST
    cin >> t;
    #endif

    #if TIME
    clock_t start_time, end_time;
    double time_elapsed;
    #endif


    while(t--) {

        #if TIME
        start_time = clock();
        #endif

        #if CASE
        cout << "Case #" << cnt++ << ": ";
        #endif

        solution();

        #if TIME
        end_time = clock();

        time_elapsed = (double) (end_time - start_time) / CLOCKS_PER_SEC;

        cout << "\nRuntime: " << fixed << setprecision(7) << time_elapsed << "\n";
        #endif
    }


    return 0;
}

void delay(int sec)
{
    int mili_sec = 1000 * sec;

    clock_t start_time = clock();

    while (clock() < start_time + mili_sec);

    return ;
}
/*
1
6 5
1 2 3
1 5 2
5 4 1
2 3 4
3 6 5
5
6 5
*/


Measured memory_bytes: 3644
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		String s = sc.next();
	    char[] S = s.toCharArray();
		int[][] q = new int[Q][2];
		for(int i=0; i<Q; i++) {
			q[i][0] = sc.nextInt();
			q[i][1] = sc.nextInt();
		}
		
		//文字列Sのn番目の文字がAで、その次の文字がCなら１、そうでなければ０を格納
		int[] isAcList = new int[S.length];
		for(int i=0; i<S.length - 1; i++) {
			if( S[i] == 'A' && S[i+1] == 'C') isAcList[i] = 1;
			else isAcList[i] = 0;
		}
		isAcList[S.length - 1] = 0;
		//累積和
		int[] sum = new int[S.length + 1];
		for(int i=0; i<S.length; i++) {
			sum[i + 1] = sum[i] + isAcList[i];
		} 
		
		for(int i = 0; i<Q; i++) {
			int left = q[i][0] - 1;
			int right = q[i][1];
			int ans = sum[right] - sum[left];
			if (isAcList[right - 1] == 1) ans--;
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 101580
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm> // sort

#define REP(i, n) for (int i = 0; i < (n); i++) 
#define ll long long

using namespace std;

int gcd(int a, int b)
{
    if(a < b){
        return gcd(b,a);
    }

    int r = a % b;
    if(r != 0)
    {
        a = b;
        b = r;
        gcd(a,b);
    }
    else
    {
        return b;
    }
}
//A[0]とA[1]の最大公約数(r1)を求める.r1とA[2]の最大公約数r2を求める.rNを出力

int main(){
    int N,res;

    vector<int> A;

    cin >> N;

    A.resize(N);

    REP(i,N)
    {
        cin >> A[i];
    }

    //N == 2の場合
    if(N == 2)
    {
        if(A[0] > A[1])res = A[0];
        else res = A[1];
        cout << res << endl;

        return 0;
    }

    //0～Nまでそれぞれを使わなかった場合を考える

    vector<int> l(N);
    vector<int> r(N);

    //各範囲のgcdを保存する
    //L[0]→ 0
    //L[1]→ 0～1までのgcd
    //R[(N-1) - 1]→ N~N-1までのgcd
    //R[0]→ N~0までのgcd

    // 3番目をしない場合のgcdは、
    //gcd(L[2],R[4])とする

    l[0] = A[0];
    for(int i = 1; i < N; i++)
    {
        l[i] = gcd(A[i], l[i-1]);
    }

    r[N-1] = A[N-1];
    for(int i = N-2; i >= 0; i--)
    {
        r[i] = gcd(A[i],r[i+1]);
    }

    //i=0をしない場合を初期値に設定
    res = r[1];

    int tmp;

    for(int i = 1; i <= N-2; i++)
    {
        res = max(res, gcd(l[i-1],r[i+1]));
    }
    //N-1を使用しないパターン
    
    res = max(res, l[N-2]);

    //0とN+1に、0を指定すれば、gcdだけでよい?


    cout << res << endl;
}


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

int main(void){
  int n,max = 0,maxcount = 0;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++){
    cin >> h[i];
    if(max <= h[i]){
      max = h[i];
      maxcount++;
    }
  }
  cout << maxcount << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 101
#define F 0
#define T 1

int s[MAX], top = 0;

int isEmpty(void) {
  if(top == 0) return F;
  else return T;
}

int isFull(void) {
  if(top >= MAX -1) return F;
  else return T;
}

void push(int n){
  if(isFull() == F) {
    fprintf(stderr, "OverFlow");
    exit(1);
  }
  top++;
  s[top] = n;
}

int pop(void) {
  if (isEmpty() == F) {
    fprintf(stderr, "UnderFlow");
    exit(1);
  }
  top--;
  return s[top+1];
}

int main () {
  int x, y, i;
  char c[MAX];

  while(scanf("%s", c) != EOF) {
    if(c[0] == '+') {
      x = pop();
      y = pop();
      push(x + y);
    }
    else if(c[0] == '-') {
      x = pop();
      y = pop();
      push(y - x);
    }
    else if(c[0] == '*') {
      x = pop();
      y = pop();
      push(x * y);
    }  
    else {
      x = atoi(c);
      push(x);
    }
  }

  printf("%d\n", s[1]);
  return 0;
}

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

using namespace std;

int N, Q;
string str;
vector<char> t, d;

int is_down(int k) {
	int pos = k;
	for (int i = 0; i < Q; i++) {
		if (pos == -1 || pos == N) return pos;
		if (str[pos] == t[i]) {
			if (d[i] == 'L') pos--;
			else pos++;
		}
	}
	return pos;
}


int main() {

	cin >> N >> Q;
	cin >> str;
	
	for (int i = 0; i < Q; i++)
	{
		char tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		t.push_back(tmp1);
		d.push_back(tmp2);
	}

	//左に落ちないゴーレムのうち、最も左端のものを二分探索
	int left= -1, right = N;
	while (left +1 < right) {
		int mid = (left + right) / 2;
		if (is_down(mid) == -1) left = mid;
		else right = mid;
	}
	int remainL = right;

	//右に落ちないゴーレムのうち、最も右端のものを二分探索
	left = -1, right = N;
	while (left + 1 < right) {
		int mid = (left + right) / 2;
		if (is_down(mid) == N) right = mid;
		else left = mid;
	}
	int remainR = left;
	int ans = remainR - remainL + 1;

	cout << ans << endl;

	return 0;
}

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

#define MAX 8
char table[MAX][MAX];

void rotate_90()
{
	char tmp[MAX][MAX];
	for ( int i = 0 ; i < MAX ; i++ ) {
		for ( int j = 0 ; j < MAX ; j++ ) {
			tmp[j][(MAX-1)-i] = table[i][j];	
		}
	}

	memcpy( table, tmp, sizeof( table ) );
}

void print_table() 
{
	for ( int i = 0 ; i < MAX ; i++ ) {
		for ( int j = 0 ; j < MAX ; j++ ) {
			printf( "%c", table[i][j] );
		}
		printf( "\n" );
	}
}

int main()
{
	int i = 0;

	for ( i = 0 ; i < MAX ; i++ ) {
		scanf( "%s", table[i] );
	}

	for ( i = 1 ; i < 4 ; i++ ) {
		rotate_90();
		printf( "%d\n", 90 * i );
		print_table();
	}

	return 0;
}



Measured memory_bytes: 2752
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
int n,m,a[55],b[55],c[55],d[55],q;
int calc(vector<int> &v){
    int ret = 0;
    rep(i,q){
        if(v[b[i]]-v[a[i]] == c[i])ret += d[i];

    }
    return ret;
}
int dfs(int d,vector<int> &v){
    if(d == n){
        //for(auto p:v)trace(p);
        //trace(calc(v));
        return calc(v);
    }
    int ret = 0;
    
    for(int i = 1;i <= m;i++){
        if(v.size()&&v.back() > i)continue;
        v.push_back(i);
        ret = max(ret,dfs(d+1,v));
        v.pop_back();
    }
    //trace(ret);
    return ret;

}
using P = pair<int,int>;
signed main(){
    cin >> n >> m >> q;
    
    rep(i,q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;b[i]--;

    }
    vector<int> v;
    int ans = dfs(0,v);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

int main() {
  int ab, bc, ca; cin >> ab >> bc >> ca;
  int a = ab * bc, b = bc * ca, c = ca * ab;
  int vmin = min(min(a, b),  c);
  cout << vmin / 2  << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>
using namespace std;
int main(){
    int N,Q,l,r;
    string S;
    cin >> N >> Q >> S;
    int number[N];
    int count = 0;
    number[0] = 0;
    for(int j = 1;j<N;j++){
            if(S[j-1]=='A' && S[j]=='C'){ 
            count++;
            }
            number[j] = count;
    }
    for(int i = 0;i<Q;i++){
        scanf("%d",&l);
        scanf("%d",&r);
        cout << number[r-1] - number[l-1]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1408
import random
D=int(input())                                          #コンテの日数
c=list(map(int,input().split()))                        #26タイプ(AAC~AZC)のコンテストの満足度低下度
s=[list(map(int,input().split())) for _ in range(D)]    #s[d][i]...d(1<=d<=D)日目にi(1<=i<=26)番目のコンテストを行った時の満足度上昇
#types=[int(input()) for _ in range(D)]                  #コンテタイプ(1~26)
#満足度低下はΣ(1<=i<=26)ci*(d-last(d,i))                  #なおlast(d,i)=d日目以前に最後にタイプiのコンテストをやった日にち(ない場合0)
#よって満足度はs[d][i]-Σ(1<=i<=26)ci*(d-last(d,i))
#i日目のスコアはmax(10^6+s[d][i]-Σ(1<=i<=26)ci*(d-last(d,i)),0)
#last=[0]*26                                             #typeごとに、最後に使われた日にちを記録するよ
typ=0
ans=0
l=[i for i in range(1,27)]
for i in range(D):
    if i%26==0:
        random.shuffle(l)
    print(l[i%26])


Measured memory_bytes: 77884
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int H, W;
char C[300][300];
long long  memo1[310][310];
bool used1[310][310];
int num[310][310];
long long solve1(int a, int b, int r){
  if( a == -1 || b == -1 ) return 0;
  if( used1[a][b] )
    return memo1[a][b];
  long long ans = 1e8;
  ans = min(ans, solve1( a-1, b, r ) + num[a][b] );
  ans = min(ans, solve1( a, b-1, r ) + num[a][b] );
  used1[a][b] = true;
  return memo1[a][b] = ans;
}

int main(){
  char c;
  scanf("%d %d", &H, &W);
  REP(i,H){
    scanf("%c", &c);
    REP(j,W){
      scanf("%c", &C[i][j]);
    }
  }
  long long ans = 0;
  REP(i,W-1){
    REP(l,H+1) REP(m,H+1){
      used1[l][m] = false;
    }
    REP(h,H){
      num[h][0] = (C[h][i] == C[0][i+1]) ? 1 : 0;
      num[0][h] = (C[0][i] == C[h][i+1]) ? 1 : 0;
    }
    REP(s,H){
      REP(t,H){
	if( s > 0 && t > 0 ){
	  num[s][t] = num[s-1][t-1] + ((C[s][i] == C[t][i+1]) ? 1 : 0);
	}
      }
    }
    ans += solve1( H-1, H-1, i );
  }
  cout << ans << endl;
}


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

ll solve(vector<ll> &A, vector<ll> &X) {
    ll res = -1;
    for(int i=1; i<=N; ++i) {
        ll tmp;
        if((i + N) % 2) {
            int m = (i + N + 1) / 2;
            tmp = 2LL * (A[m - 1] - A[i - 1]) + X[m - 1] - 2LL * (A[N] - A[m - 1]);
        } else {
            int m = (i + N) / 2;
            tmp = 2LL * (A[m] - A[i - 1]) - X[m - 1] - 2LL * (A[N] - A[m]);
        }
        tmp += (N - i) * L;
        res = max(res, tmp);
    }
    return res;
}

int main() {
    cin >> L >> N;
    vector<ll> X(N);
    vector<ll> Y(N);
    for(int i=0; i<N; ++i) {
        cin >> X[i];
    }
    for(int i=0; i<N; ++i) Y[i] = L - X[N - i - 1];

    vector<ll> A(N+1, 0);
    vector<ll> B(N+1, 0);
    for(int i=0; i<N; ++i) {
        A[i+1] = A[i] + X[i];
        B[i+1] = B[i] + Y[i];
    }

    ll res = max(solve(A, X), solve(B, Y));
    cout << res << endl;
}

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

int main(){
#ifdef _DEBUG
	freopen("in" , "r", stdin );
	freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	string s; char c;
	while(cin >> c){
		if(c == 'B' && s.size()) s.erase(prev(s.end()));
		if(c != 'B') s += c;
	}
	cout << s << '\n';
}


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

int main(){
    int N;
    string S,T;
    cin >> N;
    cin >> S >> T;

    string ans;
    for(int i=0; i<2*N; i++){
        if(i%2==0){
            string tmp(1,S[i/2]);
            ans=ans+tmp;
        }else{
            string tmp(1,T[(int)i/2]);
            ans=ans+tmp;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.TreeMap;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.next());
        int K = Integer.parseInt(scanner.next());
        int Q = Integer.parseInt(scanner.next());
        int[] score = new int[N];
        for (int i = 0; i < Q; i++) {
            int n = Integer.parseInt(scanner.next()) - 1;
            score[n]++;
        }

        for (int i = 0; i < N; i++) {
            if (K - Q + score[i] > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}



Measured memory_bytes: 49264
N = int(input())
d = list(sorted([int(i) for i in input().split()]))
l = len(d) // 2
boundary = d[l - 1]
next_d = boundary
boundary_cnt = 0
for i in d[l:]:
    if i == boundary:
        boundary_cnt += 1
        if boundary > 2:
            next_d = boundary
            break
    elif i > boundary:
        next_d = i
        break
print(next_d - boundary)


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

/*                          
---------------------------------------------------------------
Aditya Kumar mishra
---------------------------------------------------------------
*/

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define len(s) s.length()
#define forp(i, a, b) for (int i = a; i <= b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define ren(i, n) for (int i = n - 1; i >= 0; i--)
#define forn(i, a, b) for (int i = a; i >= b; i--)
#define on cout << endl
#define o2(a, b) cout << a << " " << b
#define os cout << " "
#define all(v) v.begin(), v.end()
#define mem(n, m) memset(n, m, sizeof(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define sii set<int>
#define us unordered_set<int>
#define um unordered_map<int, int>
#define sll set<long long>
#define vii vector<int>
#define vll vector<long long>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ret return 0
#define present(s, x) (s.find(x) != s.end())
#define cpresent(s, x) (find(all(s), x) != s.end())
#define ford(container, it) for (__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define fors(container, it, a, b) for (__typeof(container.begin()) it = a; it != b; it++)

#define boost ios_base::sync_with_stdio(0)
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100001
#define SIZ 1000001
#define SIZE 200001

typedef long long ll;
typedef long double ldo;
typedef double db;
using namespace std;
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)

void c_p_c()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int main()
{
   // c_p_c();
    string s;
    cin >> s;
    ll sum = 0;
    for (int i = 0; i < (int)len(s); i++)
    {
        sum += s[i] - '0';
    }
    if (sum % 9 == 0 || sum==0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3720
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

int f_dir[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}}; //↑→↓←
int e_dir[2][8] = {{-1, -1, -1, 0, 0, 1, 1, 1}, {-1, 0, 1, -1, 1, -1, 0, 1}};
bool is_in_field(int y, int x, int h, int w){
  return (y >= 0 && y < h && x >= 0 && x < w);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n, m, x;
  cin >> n >> m >> x;
  vi costs(n);
  vvi a(n, vi(m));
  for(int i = 0; i < n; i++){
    cin >> costs[i];
    for(int j = 0; j < m; j++){
      cin >> a[i][j];
    }
  }
  int ans = 1000000000;
  for(int i = 0; i < (1<<n); i++){
    int tmp = 0;
    vi acc(m, 0);
    for(int j = 0; j < n; j++){
      if(i & (1<<j)){
        tmp += costs[j];
        for(int k = 0; k < m; k++){
          acc[k] += a[j][k];
        }
      }
    }
    int f = 1;
    for(int j = 0; j < m; j++){
      if(acc[j] < x) f = 0;
    }
    if(f) ans = min(ans, tmp);
  }
  if(ans == 1000000000)cout << -1 << endl;
  else cout << ans << endl;

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
string a,b;
int d[3009][3009],x,c[3009][3009];
int dp(int i,int j){
    if(i==a.size()||j==b.size()) return 0;
    if(d[i][j]!=-1) return d[i][j];
    if(a[i]==b[j]) {c[i][j]=0; return d[i][j]=1+dp(i+1,j+1);}
    if(dp(i+1,j)>dp(i,j+1)) {c[i][j]=1; return d[i][j]=dp(i+1,j);}
    c[i][j]=2;
    return d[i][j]=dp(i,j+1);
}
string dp2(int i,int j){
    if(i==a.size()||j==b.size()) return "";
    if(c[i][j]==0) return a[i]+dp2(i+1,j+1);
    if(c[i][j]==1) return dp2(i+1,j);
    return dp2(i,j+1);
}
int main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    memset(d,-1,sizeof d);
    cin>>a>>b;
    x=dp(0,0);
    cout<<dp2(0,0);
    return 0;
}


Measured memory_bytes: 71424
// Charan Sriramula

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;

const ll lg=14;
const ll N=2e5+5;
const ll INF=1e9;
const ll mod=1e9+7;
const double PI = 3.14159265358979323846;

#define ints(n) scanf("%d",&n)
#define intp(n) printf("%d\n",n)
#define longs(n) scanf("%lld",&n)
#define longp(n) printf("%lld\n",n)

#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define ms(dp,val) memset(dp,val,sizeof(dp))
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

ll n,h[N],b[N],seg[4*N];

void update(ll low,ll high,ll qpos,ll pos,ll val)
{
  if(low==high)
  {
    seg[pos]=val;
    return;
  }
  else
  {
    ll mid=(low+high)/2;
    if(low<=qpos&&qpos<=mid) update(low,mid,qpos,2*pos,val);
    else update(mid+1,high,qpos,2*pos+1,val);
    seg[pos]=max(seg[2*pos],seg[2*pos+1]);
  }
}

ll query(ll low,ll high,ll qlow,ll qhigh,ll pos)
{
  if(qlow>high||qhigh<low) return 0;
  if(qlow<=low&&qhigh>=high) return seg[pos];
  ll mid=(low+high)/2;
  return max(query(low,mid,qlow,qhigh,2*pos),query(mid+1,high,qlow,qhigh,2*pos+1));
}

int main()
{
  cin>>n;
  ll maxi=0;
  for(ll i=1;i<=n;i++){cin>>h[i];}
  for(ll i=1;i<=n;i++){cin>>b[i];}
  for(ll i=1;i<=n;i++)
  {
    ll val=b[i]+query(1,n,1,h[i],1);
    maxi=max(maxi,val);
    update(1,n,h[i],1,val);
  }
  cout<<maxi<<endl;
}


Measured memory_bytes: 9600
#include "bits/stdc++.h"
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
 
void _main() {
  int A, B, C;
  cin >> A >> B >> C;
 
  if (A==B && B==C) {
    cout << "0" << "\n";
    return;
  }
 
  int ans = 0;
  if (A%2==B%2 && A%2!=C%2) {
    A++, B++, ans++;
  } else if (A%2==C%2 && A%2!=B%2) {
    A++, C++, ans++;
  } else if (B%2==C%2 && B%2!=A%2) {
    B++, C++, ans++;
  }
 
  int MAX = max({A, B, C});
  ans += (MAX-A) / 2;
  ans += (MAX-B) / 2;
  ans += (MAX-C) / 2;
 
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100000
#define M 2000000000

typedef struct Card{
  char m;
  int n;
} Card;

void merge(Card *,int ,int ,int ,int);
void merges(Card *,int ,int ,int);
int part(Card *,int ,int ,int);
void quicks(Card *,int ,int ,int);

Card L[N/2+2] ,R[N/2+2];

int main() {
  int n ,i ,v ,m=1;
  Card a[N] ,b[N];
  char s[10];

  scanf("%d" ,&n);

  for(i=0;i<n;i++){
    scanf("%s %d" ,s ,&v);
    a[i].m=b[i].m=s[0];
    a[i].n=b[i].n=v;
  }
  merges(a ,n ,0 ,n);
  quicks(b ,n ,0 ,n-1);

  for(i=0;i<n;i++){
    if(a[i].m!=b[i].m) m=0;
  }

  if(m==1)printf("Stable\n");
  else printf("Not stable\n");

  for(i=0;i<n;i++){
    printf("%c %d\n" ,b[i].m ,b[i].n);
  }

  return 0;
}

void merge(Card a[],int n,int l,int m,int r){
  int i ,j ,k ,n1=m-l ,n2=r-m;
  for(i=0;i<n1;i++){
    L[i]=a[l+i];
  }
  for(i=0;i<n2;i++){
    R[i]=a[m+i];
  }

  L[n1].n=R[n2].n=M;
  i=j=0;
  for(k=l;k<r;k++){
    if(L[i].n<=R[j].n) a[k]=L[i++];
    else a[k]=R[j++];
  }
}

void merges(Card a[] ,int n ,int l ,int r){
  int m;
  if(l+1<r){
    m=(l+r)/2;
    merges(a ,n ,l ,m);
    merges(a ,n ,m ,r);
    merge(a ,n ,l ,m ,r);
  }
}

int part(Card a[] ,int n ,int p ,int r){
  int i ,j;
  Card t ,x;
  x=a[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(a[j].n<=x.n){
      i++;
      t=a[i];
      a[i]=a[j];
      a[j]=t;
    }
  }
  t=a[i+1];
  a[i+1]=a[r];
  a[r]=t;

  return i+1;
}

void quicks(Card a[],int n ,int p ,int r){
  int q;
  if(p<r){
    q=part(a ,n ,p ,r);
    quicks(a ,n ,p ,q-1);
    quicks(a ,n ,q+1 ,r);
  }
}


Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define bit(k) (1LL<<(k))
#define SUM(v) accumulate(all(v), 0LL)

typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
struct fast_ios{ fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; }fast_ios_;

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

#define TOSTRING(x) string(#x)
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &x : vec) is >> x; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { os  << "["; for(auto _: v) os << _ << ", "; os << "]"; return os; };
template <typename T> ostream &operator<<(ostream &os, set<T> &st) { os << "("; for(auto _: st) { os << _ << ", "; } os << ")";return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair< T, U >& p){os << "{" <<p.first << ", " << p.second << "}";return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &mp){ os << "["; for(auto _: mp){ os << _ << ", "; } os << "]" << endl; return os; }

#define DUMPOUT cerr
void dump_func(){ DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

#ifdef DEBUG
#define dbg(...) dump_func(__VA_ARGS__)
#define dump(...) DUMPOUT << string(#__VA_ARGS__) << ": "; dump_func(__VA_ARGS__)
#else
#define dbg(...)
#define dump(...)
#endif

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const long double PI = acos(-1.0);

/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

const int MAXT = 3002;
int main() {
    ll N, T;
    cin >> N >> T;
    vector<l_l> AB;
    rep(i,N){
        ll a, b;
        cin >> a >> b;
        AB.emplace_back(a, b);
    }
    sort(all(AB));
    vector<ll> dp(T+1, -1);
    dp[0] = 0;
    rep(i,N){
        auto [a, b] = AB[i];
        vector<ll> dp2(T+1, -1);
        rep(j,T+1)chmax(dp2[j], dp[j]);
        rep(j,T){
            if(dp[j] >= 0)chmax(dp2[min(T,j+a)], dp[j]+b);
        }
        swap(dp, dp2);
    }
    cout << *max_element(all(dp)) << endl;
}


Measured memory_bytes: 3696