akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main() {
	int sum_day = 0;

	for (int i = 1; i <= 999; i++) {
		for (int j = 1; j <= 10; j++) {
			for (int k = 1; k <= 19; k++) {
				sum_day++;
				if ((j % 2 != 0 || i % 3 == 0) && k == 19) sum_day++;
			}
		}
	}
	sum_day++;

	int n;
	cin >> n;
	int bir_day[100] = { 0 };
	for (int h = 0; h < n; h++) {
		int y, m, d;
		int flag = 0;
		cin >> y >> m >> d;
		for (int i = 1; i <= 999; i++) {
			for (int j = 1; j <= 10; j++) {
				for (int k = 1; k <= 19; k++) {
					bir_day[h]++;
					if ((i >= y) && (j >= m) && (k >= d)) {
						flag = 1;
						break;
					}
					if ((j % 2 != 0 || i % 3 == 0) && k == 19) bir_day[h]++, k++;
					if ((i >= y) && (j >= m) && (k >= d)) {
						flag = 1;
						break;
					}
				}
				if (flag == 1)break;
			}
			if (flag == 1)break;
		}
		cout << sum_day - bir_day[h] << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
N = int(input())
s = [0 for _ in range(N)]
words = []
for i in range(N):
    s[i] = input()
    if s[i] not in words:
        words.append(s[i])

M = int(input())
t = [0 for _ in range(M)]
for i in range(M):
    t[i] = input()

ans = 0
for i in range(len(words)):
    x = s.count(words[i])
    y = t.count(words[i])
    result = x - y
    if result > ans:
        ans = result
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <iomanip>
#include <string>
#include <sstream>
#include  <list>
//#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
/*
int cmp(shi a,shi b)
{
    return a.x<b.x;
}
long long cmd(long long a, long long  b)
{
    return a > b;
}*/

int cmd(int a, int b)
{
    return abs(a)<abs(b);
}
int main()
{
    int a ,b;
    while(cin >>a >>b){
        if(a+b>=10)
            cout<<"error"<<endl;
        else
            cout<<a+b<<endl;
    }
    return 0;

}


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

using i64 = long long int;

vector<i64> divisor(i64 n) {
    vector<i64> res;
    for (i64 i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(n / i);
        }
    }
    return res;
}

i64 func(i64 b, i64 n){
    return (n < b ? n : (func(b, n/b) + n%b));
}

int main(){
    i64 n, s;
    cin >> n >> s;

    if(s > n)cout << -1 << endl;
    else if(s == n)cout << n + 1 << endl;
    else{
        i64 ans = -1;
        for(i64 b=2;b*b<=n;++b){
            i64 res = func(b, n);
            if(res == s){
                ans = b;
                break;
            }
        }
        if(ans == -1){
            vector<i64> divisors = divisor(n-s);
            sort(divisors.begin(), divisors.end());
            for(auto d : divisors){
                i64 y = (n - s) / d, x = n % (d+1);
                if(x + y*(d+1) == n && x + y == s){
                    ans = d + 1;
                    break;
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}
/*
x + by = n
x + y = s
x = s - y

s - y + by = n
(b - 1)y = n - s
y = (n - s) / (b - 1)
*/


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from string import ascii_lowercase
from collections import Counter
def inpl(): return map(int, input().split())

N = int(input())
S = input()

ans = 0

for i in range(N):
    tmp = 0
    A = Counter(S[:i])
    B = Counter(S[i:])
    for a in ascii_lowercase:
        tmp += (A[a] > 0)&(B[a] > 0)
    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 3828
from functools import lru_cache
import math

def main():
    n=int(input())
    a=list(map(int,input().split()))
    x=set()
    y=a[0]
    pair=True
    for i in a:
        if pair:
            p=set(prime_factorize(i))
            if len(x&p)>0:
                pair=False
            x|=p
        y=math.gcd(y, i)
    if pair:
        print("pairwise coprime")
    elif y==1:
        print("setwise coprime")
    else:
        print("not coprime")

# 素数リスト（エラトステネスの篩）
@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

# 素数判定（単純な素数判定なら十分早い。大量にやる場合はX in primesがよさそう）
@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

# 素因数分解
def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

if __name__ == "__main__":
    main()

Measured memory_bytes: 128008
#include <climits>
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	int q;
	scanf("%d", &q);

	char* s = new char[n];
	scanf("%s", s);

	uint16_t*  c = new uint16_t[n];
	c[0] = 0;
	for (int i = 0; i < n-1; i++)
	{	
		c[i + 1] = c[i];
		if (s[i] == 'A' && s[i+1] == 'C')
			c[i + 1]++;
	}

	for (int i = 0; i < q; i++)
	{
		int a;
		scanf("%d", &a);
		int b;
		scanf("%d", &b);
		a--; b--;
		printf("%d\n", c[b] - c[a]);
	}
	delete c, s;
	return 0;
}

Measured memory_bytes: 1152
#include <cstdio>
#include <algorithm>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 100;
const int W_MAX = N_MAX * 4;
const int W_I_MAX = 1000000000;
const int V_I_MAX = 10000000;

int N, W;
int w[N_MAX];
int v[N_MAX];

int X;
int w0;
int dp[N_MAX + 1][W_MAX + 1];

void solve() {
  w0 = w[0] - 1;
  REP(i, N) w[i] -= w0;
  X = N * 4;
  REP(i, N) {
    // printf("w[i]: %d, v[i]: %d\n", w[i], v[i]);
    for (int j = i; j >= 0; j--) FOR(k, 0, X) {
      if (k >= w[i]) {
        dp[j + 1][k] = max(dp[j + 1][k], dp[j][k- w[i]] + v[i]);
      }
    }
    // DUMP2D(dp, N + 1, X + 1);
  }
  int ans = 0;
  FOR(i, 1, N) {
    if (w0 * i > W) break;
    ans = max(ans, dp[i][min(W - w0 * i, X)]);
  }
  printf("%d\n", ans);
}

void input() {
  scanf("%d%d", &N, &W);
  REP(i, N) scanf("%d%d", w + i, v + i);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


s = input()
t = input()


# str * str -> int
def solve(s, t):
    dp = makelist(len(s)+1, len(t)+1) # 何文字目かで index (offset=1)
    
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    res = ""
    x, y = len(t), len(s)

    while dp[y][x] > 0:
        now = dp[y][x]
        u, lu, l = dp[y-1][x], dp[y-1][x-1], dp[y][x-1]
        if lu == now:
            x, y = x-1, y-1
        else: # lu = now - 1
            if u == lu and l == lu:
                res += s[y-1]
                x, y = x-1, y-1
            else:
                if u >= l:
                    y -= 1
                else:
                    x -= 1
                    
    return res[::-1]


print(solve(s, t))


Measured memory_bytes: 120028
import java.util.Scanner;
public class Main{
	
	public void solve(){
		Scanner sc = new Scanner(System.in);
		int S;
		S = sc.nextInt();
		
		System.out.println(((S-S%3600)/3600)+":"+((S-(S-S%3600)-(S%60))/60)+":"+(S%60));
	}
	public static void main(String[] args){
		Main obj = new Main();
		obj.solve();
	}
}

Measured memory_bytes: 17232
#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      mut hs: [usize;n],
    }

    hs[0] -= 1;
    let mut ok = false;
    for i in 1..n {
        let prev = hs[i-1];
        if prev < hs[i] {
            hs[i] -= 1;
        }
        if prev > hs[i] {
            return puts!("{}\n", "No");
        }
    }
    puts!("{}\n", "Yes");
}


Measured memory_bytes: 4352
#include <cmath>
#include <iostream>
#define f first
#define s second
using namespace std;
typedef long long LL;
const int MAXN = 1e6+66;
int main()
{
    LL n,a,b;
    cin>>n;
    int vis = n;
    LL ans = 0;
    LL bb = 1e9+99;
    while(n--)
    {
        cin>>a>>b;
        ans += a;
        if(a == b) vis--;
        if(a > b) bb = min(bb,b);
    }
    if(vis) cout<<(ans-bb);
    else cout<<0;
    return 0;
}

Measured memory_bytes: 256
s = list(input())
l = len(s)
x = 0
y = 0
ans = 0

for i in range(l):
    if i % 2 == 0:
        if s[i] == '1':
            x += 1
    if i % 2 == 1:
        if s[i] == '0':
            x += 1

for i in range(l):
    if i % 2 == 0:
        if s[i] == '0':
            y += 1
    if i % 2 == 1:
        if s[i] == '1':
            y += 1

ans = min(x, y)
print(ans)

Measured memory_bytes: 49392
#!/usr/bin/env python3

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    l = []
    r = []
    for _ in range(m):
        a, b = list(map(int, input().split()))
        l.append(a)
        r.append(b)

    ans = min(r) - max(l) + 1
    if ans < 0:
        print(0)
    else:
        print(ans)

Measured memory_bytes: 11012
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i=0; i<int(n); i++)
#define RNG(i, f, t) for(int i=int(f); i<=int(t); i++)
bool RELAXED = false;
template<int,typename T> struct MINMAX{ T val; MINMAX(T val) : val(val) {} };
template<typename T> MINMAX<1,T> MAX(T val) { return MINMAX<1,T>(val); };
template<typename T> MINMAX<2,T> MIN(T val) { return MINMAX<2,T>(val); };
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<1,U> rhs) { return lhs = (rhs.val > lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<2,U> rhs) { return lhs = (rhs.val < lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T> inline vector<T> readVector(int n) { vector<T> vec(n); FOR(i,n) cin>>vec[i]; return vec; }
template<typename T> void EXIT(T answer) { cout<<answer<<endl; exit(0); }
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef signed long long int ll;

bool palin(string s) {
    cerr<<s<<endl;
    FOR(i,s.length()) {
        if(s[i]!=s[s.length()-i-1]) return false;
    }
    return true;
}

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

    string s;
    cin>>s;
    bool ans = palin(s) && palin(s.substr(0, (s.length()-1)/2)) && palin(s.substr((s.length()+1)/2));
    cout<<(ans?"Yes":"No")<<endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    int a,b;
    cin >> a >> b;
    if ( a > 9 || a < 1 || b > 9 || b < 1 ) {
        cout << -1 << endl;
        return 0;
    }
    cout << a*b << endl;
    return 0;
}


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

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

  int cnt = 0;
  for (int i = 0; i < n; ++i)
  {
    ll t;
    cin >> t;
    while (t % 2 == 0)
    {
      t /= 2;
      cnt++;
    }
  }
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	String S = sc.next();
	char[] c = S.toCharArray();
	int[] score = new int[N];

	for(int i = 1; i<S.length(); i++) {
	    if(c[i] == 'E') {
		score[0]++;
	    }
	}

	int current = 1;
	int pre = 0;
	while(current < N) {
	    score[current] = score[pre];
	    if(c[current] == 'E') {
		score[current]--;
	    }
	    if(c[pre] == 'W') {
		score[current]++;
	    }
	    current++;
	    pre++;
	}

	int min = Integer.MAX_VALUE;
	for(int s : score) {
	    min = Math.min(s,min);
	}
	System.out.println(min);
    }
}

Measured memory_bytes: 30752
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <string> s(n),s2(n);
    vector <int> p(n);
    for(int i = 0; i < n; i++){
        cin >> s[i] >> p[i];
        s2[i] = s[i];
    }
    sort(s2.begin(),s2.end());
    s2.erase(unique(s2.begin(),s2.end()),s2.end());
    vector <vector<int>> p2(s2.size(),vector<int>());
    vector <int> ans;
    for(int i = 0; i < s2.size(); i++){
        //cout << s2[i] << endl;
        for(int j = 0; j < n; j++){
            if(s2[i].compare(s[j])==0){
                p2[i].push_back(p[j]);
                //cout << p[j] << " ";
            }
            //cout << endl;
        }
        sort(p2[i].begin(),p2[i].end(),greater<int>());
    }
    for(int i = 0; i < p2.size(); i++){
        for(int j = 0; j < p2[i].size(); j++){
            for(int k = 0; k < n; k++){
                if(p2[i][j]==p[k]){
                    ans.push_back(k);
                }
            }
        }
    }
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i]+1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3588
/*
Author : N_o_o_B
Created : April 22 2020 21:30:55 
*/
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;

    string s;
    cin >> s;
    vector<bool> seen(26);
    bool ok =1;
    for(char c:s){
        if(seen[c-'a']) ok = 0;
        seen[c-'a']=1;
    }
    cout << (ok ? "yes":"no") << endl;


    time_taken();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  string s;cin>>s;
  int a[n+1];
  int g=0,h;
  vector<int>b={1,1,2,2};
  vector<int>c={1,2,1,2};
  for(int j=0;j<4;j++){
    a[0]=b.at(j);a[1]=c.at(j);
    if(a[0]==1){
        if(a[1]==1){
          if(s[0]=='o'){
            h=1;
          }
          else{
            h=2;
          }
        }
        else{
          if(s[0]=='o'){
            h=2;
          }
          else{
            h=1;
          }
        }
      }
      else{
        if(a[1]==1){
          if(s[0]=='o'){
            h=2;
          }
          else{
            h=1;
          }
        }
        else{
          if(s[0]=='o'){
            h=1;
          }
          else{
            h=2;
          }
        }
      }
    
    for(int i=1;i<n;i++){
      if(a[i]==1){
        if(a[i-1]==1){
          if(s[i]=='o'){
            a[i+1]=1;
          }
          else{
            a[i+1]=2;
          }
        }
        else{
          if(s[i]=='o'){
            a[i+1]=2;
          }
          else{
            a[i+1]=1;
          }
        }
      }
      else{
        if(a[i-1]==1){
          if(s[i]=='o'){
            a[i+1]=2;
          }
          else{
            a[i+1]=1;
          }
        }
        else{
          if(s[i]=='o'){
            a[i+1]=1;
          }
          else{
            a[i+1]=2;
          }
        }
      }
    }
    if(a[n]==a[0]&&h==a[n-1]){
      g=1;
      break;
    }
  }
  if(g==1){
    for(int i=0;i<n;i++){
      if(a[i]==1) cout<<"S";
      else cout<<"W";
    }
  }
  else if(g==0)
    cout<<-1<<endl;
}
    


Measured memory_bytes: 896
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

pub fn readnr<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let _: usize = read();
    let a: Vec<i32> = readnc();
    let mut map: HashMap<i32, usize> = HashMap::new();

    let mut ans = 0;
    for i in a {
        for ii in i-1..i+2 {
            let tv = map.get(&ii).unwrap_or(&0) + 1;
            map.insert(ii, tv);
            ans = max(ans, tv);
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 12540
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	int A,B,C,K;cin>>A>>B>>C>>K;
	while(K--){
		if(A>=B){B*=2;}
		else if(B>=C){C*=2;}
	}
	cout<<((A<B&&B<C)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 3632
# https://beta.atcoder.jp/contests/arc098/tasks/arc098_a

# N 人が与えられる
# N 人はそれぞれ、 E か W を向いている
# リーダーを一人決める
# 一番向きなしが少ない人をリーダーにしたい
# 向く回数が一番少ないやつをリーダーにした場合、最低何回向き直しが必要になるか出力する

n = gets.to_i
s = gets.to_s
ans = Array.new(n, 0)

east_count =  s[1..n-1].count('E')
west_count = 0

min = 0 + east_count

1.upto(n-1) do |i|
  west_count += 1 if s[i-1] == 'W'
  east_count -= 1 if s[i] == 'E'
  change_count = west_count + east_count
  if change_count < min
    min = change_count
  end
end

puts min

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

int main(){
    int n; cin>>n;
    string s;
    long a[5]={};
    for(int i=0;i<n;i++){
        cin>>s;
        if(s[0]=='M') a[0]++;
        if(s[0]=='A') a[1]++;
        if(s[0]=='R') a[2]++;
        if(s[0]=='C') a[3]++;
        if(s[0]=='H') a[4]++;
    }

    long sum=0;
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<5;k++){
                sum+=a[i]*a[j]*a[k];
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio> 
using namespace std;
string s,t;
int main()
{
	cin>>s>>t;
	sort(s.begin(),s.end());
	sort(t.rbegin(),t.rend());
	printf(s<t?"Yes\n":"No\n");
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        long R = 0;
        long G = 0;
        long B = 0;
        char[] let = s.toCharArray();
        for (int i = 0; i < n; i++) {
            switch (let[i]) {
                case 'R':
                    R++;
                    break;
                case 'G':
                    G++;
                    break;
                case 'B':
                    B++;
                    break;
            }
        }
        long ans = R * G * B;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if ((a != b && (a + b) % 2 == 0) && (b - a >= 0)) {
                    if (let[a] == let[b] || let[a] == let[(a + b) / 2] || let[b] == let[(a + b) / 2]) {

                    } else {
                        ans--;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 36224
#include<cstdio>
using namespace std;
int main()
{
	int n,a[100],i,cnt,mx;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	mx=0;
	cnt=0;
	for(i=0;i<n;i++){
		if(a[i]==1){
			cnt++;
			if(mx<cnt){
				mx=cnt;
			}
		}
		if(a[i]==0){
			cnt=0;
		}
	}
	printf("%d\n",mx+1);
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

vector<bool> used(200010,false);
vector<int> edges[200010];
int x,y,e;

void dfs(int i,int p = -1) {
    used[i] = true;
    if (i > 100000) y++;
    else x++;
    e += edges[i].size();
    for (int& j : edges[i]) if (j != p && !used[j]) {
        dfs(j,i);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0;i < n;++i) {
        int u,v;
        cin >> u >> v;
        edges[u].push_back(v+100000);
        edges[v+100000].push_back(u);
    }
    ll ans = 0;
    for (int i = 0;i < 200010;++i) if (!used[i]) {
        x = y = e = 0;
        dfs(i);
        e /= 2;
        if (e) ans += (ll)x*y-e;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11008
#include <cstdio>
#include <iostream>
#include <utility>
using namespace std;

int main(){
	int n;
	int a[100];
	int count=0;
	
	scanf(" %d", &n);
	for(int i=0; i<n; ++i) scanf(" %d", &a[i]);
	
	//bubble sort	
	bool flag=true;
	while(flag){
		flag=false;
		for(int i=n-1; i>0; --i){
			if(a[i]<a[i-1]){
				swap(a[i], a[i-1]);
				flag=true;
				count++;
			}	
		}
	}
	
	for(int i=0; i<n; ++i){
		if(i>0) printf(" ");
		printf("%d", a[i]);
	}
	printf("\n%d\n", count);
	
}

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

int main(){
    int n,m;
    cin >> n >> m;
    int total=0;
    vector<int> a(m);
    for(int i=0;i<m;i++){
        cin >> a[i];
        total+=a[i];
        //cout << "done/i:" << i << endl; 
    }
    //cout << "total:" << total << endl;
    if(n>=total) cout << n-total << endl;
    else cout << "-1" << endl;
}


Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int main(){
  int n, k, r, s, p;
  char input[101000] = {0}, copy[101000] = {0};
  cin >> n >> k >> r >> s >> p;
  cin >> input;
  for(int i = 0; i < n; i++){
    if(i < k){
      copy[i] = 1;
    }else{
      if(input[i] != input[i - k]){
        copy[i] = 1;
      }else{
        if(copy[i - k] == 0){
          copy[i] = 1;
        }
      }
    }
  }
  int c = 0;
  for(int i = 0; i < n; i++){
    if(copy[i] == 1){
      if(input[i] == 'r'){
        c += p;
      }else if(input[i] == 's'){
        c += r;
      }else{
        c += s;
      }
    }
  }
  cout << c;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#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 srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005
#define MOD 1000000007;

/*
    Ball and Boxes 8
*/

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

    int ans;

    if(n <= k){
        ans = 1;
    }else{
        ans = 0;
    }

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



Measured memory_bytes: 3124
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int N;
	int h[110];
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> h[i];
	}
	int l,k;
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		while (h[i] > 0) {
			int j;
			for (j = i + 1; j < N; ++j) {
				if (h[j] == 0) {
					break;
				}
			}
			for (int k = i; k < j; ++k) {
				h[k]--;
			}
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
use std::io::*;
const MOD: usize = 1_000_000_007;

fn main() {
    let mut s: String = String::new();
    stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..m)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut no = vec![false; n + 5];
    for &u in a.iter() {
        no[u] = true;
    }

    let mut dp = vec![0; n + 5];
    dp[0] = 1;
    for i in 0..n {
        if !no[i + 1] {
            dp[i + 1] += dp[i];
            dp[i + 1] %= MOD;
        }
        if !no[i + 2] {
            dp[i + 2] += dp[i];
            dp[i + 2] %= MOD;
        }
    }
    println!("{}", dp[n]);
}


Measured memory_bytes: 6396
import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
for i in range(n):
    A[i] *= -1
heapq.heapify(A)
for i in range(m):
    a = heapq.heappop(A)
    if a%2 == 0:
        a = a//2
    else:
        a = a//2+1
    heapq.heappush(A,a)
print(sum(A)*(-1))

Measured memory_bytes: 73496
a,b,x = map(int,input().split())

q_b = b//x
q_a = a//x
r_a = a%x
if x==1:
    print(b-a+1)
else:
    if r_a == 0:
        print(q_b-q_a + 1 )
    else:
        print(q_b-q_a)

Measured memory_bytes: 3060
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math


# In[10]:


a,b,x = map(int, input().split())


# In[13]:


theta = 0
if x >= a**2*b/2:
    tan = (2*(a*a*b-x))/(a**3)
    ans = math.degrees(math.atan(tan))
else:
    tan = (a*b*b)/(2*x)
    ans = math.degrees(math.atan(tan))
print(ans)


# In[ ]:






Measured memory_bytes: 62452
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

a = list(map(int, input().split()))

a = sorted(a)

print((a[0] * a[1]) // 2)



Measured memory_bytes: 7752
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
#define N 100001
vector<int> G[N],rG[N],g;
bool u[N];
int n,cmp[N],c[N];
  
void add_edge(int x,int y){G[x].push_back(y);rG[y].push_back(x);}
void dfs(int x){u[x]=1;rep(i,G[x].size())if(!u[G[x][i]])dfs(G[x][i]);g.push_back(x);} 
void rdfs(int x,int k){u[x]=1;cmp[x]=k;rep(i,rG[x].size())if(!u[rG[x][i]])rdfs(rG[x][i],k);}
int scc() {
  mem(u);g.clear();rep(i,n)if(!u[i])dfs(i);mem(u);
  int k=0;rrep(i,g.size())if(!u[g[i]])rdfs(g[i],k++);return k;
}

void Main() {
  R n;
  int a[n];
  rep(i,n) R a[i];
  rep(i,n) {
    if(a[i]) add_edge(i,i+a[i]);
  }
  scc();
  rep(i,n) c[cmp[i]]++;
  mem(u);
  rep(i,n) {
    if(c[cmp[i]]<=1||!a[i]) continue;
    u[i]=1;
    queue<int> que;
    que.push(i);
    while(!que.empty()) {
      int x=que.front();que.pop();
      rep(j,rG[x].size()) {
        int y=rG[x][j];
        if(u[y]||!a[y]) continue;
        u[y]=1;
        cmp[y]=cmp[x];
        que.push(y);
      }
    }
  }
  mem(c);
  rep(i,n) c[cmp[i]]++;
  queue<int> que;
  que.push(0);
  int d[n];
  fill(d,d+n,MAX);
  d[0]=0;
  while(!que.empty()) {
    int x=que.front();que.pop();
    REP(i,1,7) {
      int y=x+i;
      if(y>=n||c[cmp[y]]>1) continue;
      while(a[y]) {
        if(d[y]<=d[x]+1) goto next;
        d[y]=d[x]+1;
        y+=a[y];
      }
      if(d[y]<=d[x]+1) continue;
      d[y]=d[x]+1;
      que.push(y);
    next:;
    }
  }
  pr(d[n-1]);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 18320
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {

			int n = Integer.parseInt(br.readLine());

			if (n == 0)
				break;

			int key[] = new int[n];

			String str[] = br.readLine().split(" ");
			for (int i = 0; i < n; i++) {
				key[i] = Integer.parseInt(str[i]);
			}

			char c[] = br.readLine().toCharArray();
			int keyCount = 0;
			for (int i = 0; i < c.length; i++) {
				for (int j = 0; j < key[keyCount]; j++) {
					if (c[i] == 97)
						c[i] = 90;
					else if (c[i] == 65)
						c[i] = 122;
					else
						c[i] -= 1;
				}
				if (keyCount == key.length - 1) {
					keyCount = 0;
				} else {
					keyCount++;
				}
			}
			for (int i = 0; i < c.length; i++)
				System.out.print(c[i]);
			System.out.print("\n");
		}
	}
}


Measured memory_bytes: 25884
def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def r_sort(a) a.sort{|a,b|b<=>a} end

a,b = inp
p r_up(b-1,a-1)

Measured memory_bytes: 1788
N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

max1 = max(A)
if A.count(max1) >= 2:
    max2 = max1
else:
    max2 = 0
    for num in A:
        if max2 < num and max1 > num:
            max2 = num

for num in A:
    if num == max1:
        print(max2)
    else:
        print(max1)


Measured memory_bytes: 12608
while True:
    n, x = map(int,input().split())
    if n == x == 0:
        break
    cnt = 0
    for i in range(1,n+1,1):
        for j in range(i+1,n+1,1):
            for k in range(j+1,n+1,1):
                if i+j+k == x:
                    cnt+=1
    print(cnt)



Measured memory_bytes: 5596
#include <stdio.h>
#define N 10000
#define NOT_FOUND -1
int n,q;
int linearSearch(int[],int);

int main(){
    int i,cnt=0,S[N],T[N];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&S[i]);
    }
      scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&T[i]);
    }

    for(i=0;i<q;i++){
		if(linearSearch(S,T[i])!=NOT_FOUND){
			cnt++;
		}
	}
    
	printf("%d\n",cnt);


    return 0;
}

int linearSearch(int A[N],int x){
         int i = 0;
		 A[n]  = x;
		 while(A[i]!=x){
			 i++;
		 }
		   if(i == n){
				  return NOT_FOUND;
		 	}
	return i;
		
}


Measured memory_bytes: 2064
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n;
    cin >> n;
    vvl a(n, vl(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    vl cost(1 << n, 0);
    vl dp(1 << n, 0);
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (i & (1 << j) && i & (1 << k)) {
                    cost[i] += a[j][k];
                }
            }
        }
    }
    for (int mask = 0; mask < 1 << n; ++mask) {
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            ll n = dp[mask - submask] + cost[submask];
            chmax(dp[mask], n);
        }
    }
    cout << dp[(1 << n) - 1] << "\n";

    return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

long long gcd(long long m, long long n) {
  return n == 0 ? m : gcd(n, m % n);
}

int main() {
  long long n, x;
  vector<int> a;
  cin >> n >> x;
  REP(i, n) {
    long long ax;
    cin >> ax;
    a.push_back(abs(x - ax));
  }
  // if (n == 1) {
  //   cout << x + a[0] - 1 << endl;
  //   return 0;
  // }
  long long ans = gcd(a[0], a[1]);
  for (long long i = 2; i < n; i++) {
    ans = gcd(ans, a[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 892
fun main(args:Array<String>) {
    val n = readLine()!!.toInt()
    val numList = (1..n).map { readLine()!!.split(" ").map { it.toLong() }.toMutableList() }.reversed()
    var ans = 0L
    for(num in numList) {
        val md = (num[0]+ans) % num[1]
        if(md == 0L) {
            continue
        }
        ans += num[1] - md
    }
    println(ans)
}


Measured memory_bytes: 66468
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define INF 1000000000

using namespace std;

int main(void) {
  int n,k;
  cin >> n >> k;

  vector<int> h(n);
  vector<long> dp(n,INF);

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

  dp[0] = 0;
  dp[1] = abs(h[1] - h[0]);
  for(int i = 2;i < n;i++){
    for(int j = 1;j <= k;j++){
      if(i - j >= 0){
        dp[i] = min(
                    dp[i],
                    dp[i - j] + abs(h[i] - h[i - j])
                    );
      }
    }
  }
  
  cout << dp[n -1] << endl;
  return 0;
}


Measured memory_bytes: 1408
B=[0]*2**19;
n,*a=`dd`.split.map &:to_i;
a.pop(n).zip(a){|a,h|r=0;i=h;(r=[r,B[i]].max;i-=i&-i)while i>0;a+=r;(B[h]=[B[h],a].max;h+=h&-h)while h<2**19}
p B[2**18]

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

int main(){
  map<char, char> m[2];
  m[0]['A'] = 'X';
  m[1]['A'] = 'Y';
  m[1]['X'] = 'Z';
  m[0]['Y'] = 'X';
  m[0]['Z'] = 'W';
  m[1]['Z'] = 'B';
  m[0]['W'] = 'B';
  m[1]['W'] = 'Y';
  m[0]['B'] = 'Y';
  m[1]['B'] = 'X';

  while(1){
    string s;
    cin >> s;
    char now = 'A';
    if(s[0] == '#') break;
    int i;
    for(i = 0;i < s.size();i++){
      if(m[s[i]-'0'][now] == 0){
        break;
      }
      now = m[s[i]-'0'][now];
    }
    if(i == s.size() && now == 'B'){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 3240
#include<stdio.h>
int main()
{
    long long int a,b,r,d,v,u,l,c=0,t,k,n,i,j;
    scanf("%lld%lld%lld",&a,&b,&c);
    if(a-b>c){r=0;}
    else{r=c-(a-b);}
    printf("%lld\n",r);
return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <string> 
using namespace std;
using int64 = long long;
typedef long long ll;
int main()
{

  string T;
  cin>>T;
  for(int i=T.size()-1;i>=0;i--){
    if(T[i]=='?'){
      
        T[i]='D';
    }
  }
  cout<<T;

  
  return 0;
}


Measured memory_bytes: 3756
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int m = sc.nextInt();
			if(m==0) break;
			
			double sum1 = 0;
			int sumd = 0;
			int v;
			for(int i=0;i<m-1;i++){
				v = sc.nextInt();
				sum1 += Math.sin(v*Math.PI/180);
				sumd += v;
			}
			sum1 += Math.sin((360-sumd)*Math.PI/180);
			sum1 = (double)((int)(sum1*1000000))/1000000;
			
			int n = sc.nextInt();
			sumd = 0;
			double sum2 = 0;
			for(int i=0;i<n-1;i++){
				v = sc.nextInt();
				sum2 += Math.sin(v*Math.PI/180);
				sumd += v;
			}
			sum2 += Math.sin((360-sumd)*Math.PI/180);
			sum2 = (double)((int)(sum2*1000000))/1000000;
			
			if(sum1==sum2) System.out.println(0);
			else if(sum1>sum2) System.out.println(1);
			else System.out.println(2);
		}	
	}	
}

Measured memory_bytes: 20960
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String line = sc.nextLine();
      String[] linesp = line.split(" ");
      int n = Integer.parseInt(linesp[0]);
      int m = Integer.parseInt(linesp[1]);
      int[][] mat = new int[n][m];
      for(int i = 0; i < n; i++) {
        String line1 = sc.nextLine();
        String[] line1sp = line1.split(" ");
        for(int j = 0; j < m; j++) {
            mat[i][j] = Integer.parseInt(line1sp[j]);
        }
      }
      int[] b = new int[m];
      for(int i = 0; i < m; i++) {
          String line2 = sc.nextLine();
          b[i] = Integer.parseInt(line2);
      }
      
      for(int i = 0; i < n; i++) {
          int ans = 0;
          for(int j = 0; j < m; j++) {
              ans += b[j] * mat[i][j];
          }
          System.out.println(ans);
      }
  }
}


Measured memory_bytes: 30296
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue 优先队列
#include <map>
#include <set> //multiset  set<int>::reverse_iterator rit; for(rit=s.rbegin();rit!=s.rend();rit++)
#include <vector>
#include <stack>
#include <cmath>
#include <utility>
#include <sstream>
#include <string>
#define mod 1000000007
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const db eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
using namespace std;

int t,n,m,x,y,z,flag=0;
int a[N]={0},vis[N]={0};

int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&x,&y);
		if(vis[x]==0){
			a[x]=y;
			vis[x]=1;
		}else if(vis[x]==1&&y!=a[x]){
			flag=1;
		}
	}
	if(a[1]==0&&n!=1&&vis[1]==1) flag=1;
	if(flag) printf("-1\n");
	else{
		if(vis[1]==0&&n!=1) printf("1");
		else if(vis[1]==0&&n==1) printf("0");
		else printf("%d",a[1]);
		for(int i=2;i<=n;i++){
			printf("%d",a[i]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 760
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
const int M = 100005;

bool comp(const pii &a,const pii &b){
	return (a.S - a.F) < (b.S - b.F);	
}

int t[M];

int query(int x){
	int res = 0;
	for(;x;x&=x-1){
		res += t[x];	
	}
	return res;
}

void update(int x,int val){
	for(;x < M;x+=(x&-x)){
		t[x]+=val;
	}
}


int main(){
	fast_io();
	int n,m;
	cin >> n >> m;
	vector<pii> v(n);
	cu(i,0,n){
		cin >> v[i].F >> v[i].S;
	}
	int ind = 0;
	sort(all(v), comp);
	fu(i,1,m){
		while(ind < v.size() && v[ind].S - v[ind].F + 1 < i){
			update(v[ind].F, 1);
			update(v[ind].S + 1, -1);
			++ind;
		}
		int ans = v.size() - ind;
		for(int j = i;j <= m;j+=i){
			ans += query(j);
		}
		cout << ans << '\n';
	}
}



Measured memory_bytes: 3712
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

class BinSearchTree1 {

	Node root;

	public void run() {

		root = null;

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

			int m = Integer.parseInt(br.readLine());
			for (int i = 0; i < m; i++) {

				String line = br.readLine();

				if(line.charAt(0) == 'i') {
					int val = Integer.parseInt(line.substring(7));
					insert(val);
				} else if (line.charAt(0) == 'f') {
					int val = Integer.parseInt(line.substring(5));
					find(val);
				} else {
					print();
				}

			}

		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private void find(int tgt) {

		Node now = root;

		while ( now != null ) {
			if (now.key == tgt) {

				System.out.println("yes");
				return;

			} else {
				if (tgt < now.key) {
					now = now.left;
				} else {
					now = now.right;
				}
			}
		}

		System.out.println("no");

	}

	private void insert(int val) {

		Node y = null;
		Node x = root;

		Node z = new Node();
		z.key = val;
		z.left = null;
		z.right = null;

		while (x != null) {
			y = x;
			if (val < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.parent = y;

		if (y == null) {
			root = z;
		} else {
			if (val < y.key) {
				y.left = z;
			} else {
				y.right = z;
			}
		}
	}

	private void print() {

		pByInOrder(root);
		System.out.println();
		pByPreOrder(root);
		System.out.println();

	}

	private void pByInOrder(Node node) {

		if(node == null) return;

		pByInOrder(node.left);
		System.out.print(" " + node.key);
		pByInOrder(node.right);

	}

	private void pByPreOrder(Node node) {

		if(node == null) return;

		System.out.print(" " + node.key);
		pByPreOrder(node.left);
		pByPreOrder(node.right);

	}

}

class Node {

	int key;
	Node left, right, parent;

}

Measured memory_bytes: 125408