akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+7;
multiset <int> ms;
int a[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        auto it=ms.lower_bound(a[i]);
        if(it!=ms.begin()){
            it--;
            ms.erase(it);
        }
        ms.insert(a[i]);
    }
    cout<<ms.size()<<endl;
    return 0;
}


Measured memory_bytes: 5376
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <algorithm>
#include <cassert>
#define pb(x) push_back(x)
using namespace std;
inline int rd(int f = 1, int x = 0, char ch = ' ')
{
	while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
	while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
	return f*x;	
}
const int N = 2e4+5, L = 16;
int n, st[L][N], l2[N], ans, t, ti, top, s[N*L], dfn[N*L], low[N*L], ins[N*L], scc[N*L], cnt; vector<int> e[N*L]; 
struct V { int x, v; } a[N]; bool operator < (V a, V b) { return a.v < b.v; }
int opp(int x) { return x <= n?x+n:x-n; }
void add(int x, int l, int r) { if(l > r) return; int k = l2[r-l+1]; e[x].pb(st[k][l]), e[x].pb(st[k][r-(1<<k)+1]); }
void tarjan(int x)
{
	dfn[x] = low[x] = ++ti, ins[x] = 1, s[++top] = x;
	for(int y:e[x]) if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]); else if(ins[y]) low[x] = min(low[x], dfn[y]);
	if(low[x] == dfn[x]) 
	{
		int z; ++cnt;
		do z = s[top--], ins[z] = 0, scc[z] = cnt; while(z != x);
	}
}
bool chk(int d)
{
	memset(dfn+1, 0, sizeof(int)*t), ti = cnt = 0;
	for(int i = 1; i <= n<<1; ++i) e[i].clear();
	for(int i = 1, j = i; i <= n<<1; ++i)
	{
		while(j < i&&a[i].v-d >= a[j].v) ++j;
		add(a[i].x, j, i-1);
	}
	for(int i = n<<1, j = i; i; --i)
	{
		while(j > i&&a[j].v >= a[i].v+d) --j;
		add(a[i].x, i+1, j);	
	}
	for(int i = 1; i <= t; ++i) if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; ++i) if(scc[i] == scc[i+n]) return false; return true;
}
int main()
{
	n = rd(), t = n<<1; for(int i = 1; i <= n; ++i) a[i].v = rd(), a[i].x = i, a[i+n].v = rd(), a[i+n].x = i+n;
	sort(a+1, a+n*2+1), l2[0] = -1; for(int i = 1; i <= n<<1; ++i) st[0][i] = opp(a[i].x), l2[i] = l2[i>>1]+1; 
	for(int i = 1, k = l2[n<<1]; i <= k; ++i) for(int j = 1; j+(1<<i)-1 <= n<<1; ++j)
		st[i][j] = ++t, e[t].pb(st[i-1][j]), e[t].pb(st[i-1][j+(1<<(i-1))]);
	for(int l = 0, r = a[n<<1].v-a[1].v, x; l <= r; ) x = (l+r)>>1, chk(x)?(l = x+1, ans = x):(r = x-1);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 40732
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
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; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll N;
    cin >> N;
    ll ct = 0;
    rep1(i, N){
        ll a;
        cin >> a;
        if(a != i) ++ct;
    }

    if(ct <= 2) print("YES");
    else print("NO");

    return 0;
}

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

int main() {
  string s;
  cin >> s;
  int sum = 700;
  if (s[0] == 'o')
    sum += 100;
  if (s[1] == 'o')
    sum += 100;
  if (s[2] == 'o')
    sum += 100;
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int k, x;
	cin >> k >> x;
	for (int i = x - k + 1; i < x + k; i++)cout << i<<" ";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int i, n,pa=0,pb=0;
	char a[100], b[100];

	scanf("%d", &n);

	scanf("%s %s", a, b);

	if (strcmp(a, b) > 0)
		pa += 3;
	else if (strcmp(a, b) == 0)
	{
		pa += 1;
		pb += 1;
	}
	else
		pb += 3;

	for (i = 1; i < n; i++)
	{
		scanf("%s %s", a, b);

		if (strcmp(a, b) > 0)
			pa += 3;
		else if (strcmp(a, b) == 0)
		{
			pa += 1;
			pb += 1;
		}
		else
			pb += 3;
	}

	printf("%d %d\n",pa,pb);

}


Measured memory_bytes: 2108
import scala.io.Source
import scala.collection.mutable.{ Set => MSet }

object Main {
  def main(args: Array[String]) = {
    val lines = Source.stdin.getLines.toStream
    loop(lines)
  }

  def loop(lines: Stream[String]): Unit = {
    val Array(numWidth, numHeight) = lines.head.split(" ").map(_.toInt)
    if (numWidth == 0) return

    val elems = lines.drop(1).take(numHeight).map(_.split(" ").map(_.toInt))
    val map = (for {
      (_elem, y) <- elems.zipWithIndex
      (elem, x) <- _elem.zipWithIndex
    } yield (x -> y) -> elem).toMap

    check(numWidth, numHeight, map)
    loop(lines.drop(numHeight + 1))
  }

  def check(numWidth: Int, numHeight: Int, map: Map[(Int, Int), Int]): Unit = {
    var cnt = 0
    val isArrived = MSet[(Int, Int)]()
    for {
      x <- 0 to (numWidth-1)
      y <- 0 to (numHeight-1)
    } {
      if (map(x -> y) == 1 && !isArrived.contains(x -> y)) {
        cnt = cnt + 1
        dfs(x -> y, map, isArrived)
      }
    }
    println(cnt)
  }

  def dfs(xy: (Int, Int), map: Map[(Int, Int), Int], isArrived: MSet[(Int, Int)]): Unit = {
    if (isArrived(xy)) return

    isArrived += xy
    val (x, y) = xy
    for {
      i <- -1 to 1
      j <- -1 to 1
    } {
      val xi = x + i
      val yj = y + j
      map.get(xi -> yj).foreach { n =>
        if (n == 1) {
          dfs(xi -> yj, map, isArrived)
        }
      }
    }
  }
}



Measured memory_bytes: 77188
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
int n,  a[5005];

int par[5005],ran[5005];
void init(){ for(int i=0;i<5005;i++) par[i] = i; }
int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
void unite(int x,int y){
	x = find(x); y = find(y); if(x==y) return;
	if(ran[x] < ran[y]) par[x] = y;
	else{
		par[y] = x;
		if(ran[x] == ran[y]) ran[x]++;
	}
}
ll dp[5005];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[5005],R[5005];
void make(){
	F[0] = 1;
	for(int i=1;i<5005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<5005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}


int cntv[5005], cnte[5005];
ll n1[5005];
int main(){
	cin >> n;
	n1[0] = 1;
	for(int i=1;i<5005;i++) n1[i] = n1[i-1] * (n-1)% mod;
	init();
	repn(i, n){
		cin >> a[i];
		if(a[i] != -1) unite(i, a[i]);
	}
	repn(i, n){
		cntv[find(i)] ++;
		if(a[i] != -1) cnte[find(i)] ++;
	}
	vector<int>val;
	int cir = 0;
	repn(i, n){
		if(find(i) != i) continue;
		if(cntv[i] == cnte[i]){
			cir ++ ;
			continue;
		}
		assert(cntv[i]-1 == cnte[i]);
		val.pb(cntv[i]);
	}
	dp[0]= 1;
	make();
	int cnt = 0;
	ll ans = 0;
	int sz = val.size();
	for(auto v:val){
		if(v >= 2){
			ans += n1[sz-1] * (v-1) % mod;
		}
		for(int i=cnt;i>=0;i--){
			if(i){
				ans += n1[sz-i-1] * dp[i] % mod * F[i] % mod * v % mod;
			}
			dp[i+1] += dp[i] * v % mod;
			if(dp[i+1] >= mod) dp[i+1] -= mod;
		}
		cnt++;
	}
	ll ret = n1[sz] * (n-cir) % mod;
	ret -= ans;
	cout << (ret%mod+mod)%mod << endl;
}


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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

signed main(){
    int N, Q;
    cin>>N>>Q;

    vec_int a(N-1), b(N-1);
    rep(i,N-1)cin>>a.at(i)>>b.at(i);
    vec_int p(Q), x(Q);
    rep(i,Q)cin>>p.at(i)>>x.at(i);

    vec_int scores(N+1,0);
    rep(i,Q){
        scores.at(p.at(i)) += x.at(i);
    }

    vector<vector<int>> tree_str(N+1);
    for(int i=0;i<N-1;i++){
        tree_str.at(a.at(i)).push_back(b.at(i));
        tree_str.at(b.at(i)).push_back(a.at(i));
    }


    //深さ優先探索をする 幅優先探索でもOK
    // stackを使おう
    stack<P> next_nodes;
    vec_int visited(N+1,0);
    for(auto pos: tree_str.at(1)){
        next_nodes.push(make_pair(pos, scores.at(1)));
    }
    visited.at(1) = 1;

    while(next_nodes.size()>0){
        int pos, score; tie(pos,score) = next_nodes.top(); next_nodes.pop();
        visited.at(pos) = 1;
        scores.at(pos) = scores.at(pos) + score;

        for(auto next_pos: tree_str.at(pos)){
            if(visited.at(next_pos)==1)continue;
            next_nodes.push(make_pair(next_pos, scores.at(pos)));
        }
    }
    for(int i=1;i<N;i++){
        cout<<scores.at(i)<<" ";
    }
        cout<<scores.at(N)<<endl;

















    return 0;
}

Measured memory_bytes: 28236
#include <iostream>
#include <utility>
#include <vector>
#include <string>

using namespace std;

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

  vector<bool> S;
  S.reserve(s.length());
  for (auto c : s) {
    S.push_back(c=='1');
  }

  int costA=0, costB=0;

  for (int ii=0; ii<S.size(); ++ii) {
    if (S[ii]==ii%2)
      costA++;
    else
      costB++;
  }
  
  cout << min(costA,costB) << endl;
  
  return 0;
}

Measured memory_bytes: 888
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>
#include <locale>
#include <omp.h>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;
typedef pair<long long int, pll> lpll;

const long long int mod = 998244353;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 
//const long long int pl=1000000;

long long int N,M,s[200200],c[200200],res=0;
pll p[200200];
int main(){
    cout << fixed << setprecision(18);
    cin>>N;
    for(long long int i = 0; i < N; i++){
        cin>>s[i];
        res=gcd(res,s[i]);
    }
    cout<<res<<endl;
        
}



Measured memory_bytes: 4380
#include <stdio.h>

int main()
{
    int table[100+1][100+1];
    int r, c;
    int sum;
    int i, j;
    scanf("%d %d", &r, &c);
    for(i = 0; i < r; i++) {
        sum = 0;
        for(j = 0; j < c; j++) {
            scanf("%d", &table[i][j]);
            sum += table[i][j];
        }
        table[i][j] = sum;
    }
    for(j = 0; j < c+1; j++) {
        table[r][j] = 0;
        for(i = 0; i < r; i++) {
            table[r][j] += table[i][j];
        }
    }
    for(i = 0; i < r+1; i++) {
        for(j = 0; j < c; j++) {
            printf("%d ", table[i][j]);
        }
        printf("%d\n", table[i][j]);
    }
    return 0;
}


Measured memory_bytes: 2096
#include<stdio.h>
int main()
{
	char a[1000],b[1000],c[1000];
	scanf("%s %s %s",a,b,c);
	printf("%c",a[0]-32);
	printf("%c",b[0]-32);
	printf("%c",c[0]-32);
	printf("\n");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

ll d;
ll cost[3];
map<ll, ll> mp;
vl v = {2, 3, 5};

ll f(ll n) {
  if(n < 0) return 1e18;
  if(mp.count(n)) return mp[n];
  ll res = 1e18;
  if(n <= 1e18 / d) res = n * d;
  rep(i, 3) {
    ll k = v[i];
    ll p = n / k;
    ll e = n % k ? 2 : 1;
    rep(j, e) res = min(res, f(p + j) + cost[i] + abs(n - (p + j) * k) * d);
  }
  mp[n] = res;
  return res;
}

int main() {
  ll t;
  cin >> t;
  rep(_, t) {
    mp.clear();
    ll n;
    cin >> n;
    rep(i, 3) cin >> cost[i];
    cin >> d;
    mp[0] = 0;
    mp[1] = d;
    cout << f(n) << endl;
  }
}

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

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

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    char c;
    cin >> c;
    cout << (char)(c+1) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <queue>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define sqr(x) (x)*(x)
typedef long long ll;

bool check(string s) {
    int size = s.size();
    bool flag = true;
    for(int i = 0; i < size/2; i++) {
        if(s.substr(i, 1) != s.substr(size-i-1, 1)) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int count = (n-1)/2;
    if(check(s) && check(s.substr(0, count)) && check(s.substr((n+3/2)-1, count))) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 760
#include<bits/stdc++.h>
namespace ZDY{
    #pragma GCC optimize(3)
    #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
    #pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
    #define il __inline__ __attribute__ ((always_inline))
    #define rg register
    #define ll long long
    #define db double
    #define sht short
    #define MB template <class T>
    #define Fur(i,x,y) for(rg int i=x;i<=y;i++)
    #define Fdr(i,x,y) for(rg int i=x;i>=y;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdout)
    #define l2(n) (int(log2(n)))
    #define inf 2000000000
    #define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define fcin ios::sync_with_stdio(false)
    MB T ABS(T x){return x>0?x:-x;}
    MB T MAX(T x,T y){return x>=y?x:y;}
    MB T MIN(T x,T y){return x<=y?x:y;}
    MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
    void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
}using namespace ZDY;using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 1001
int main(){
    int n,m,a,b;in>>n>>m>>a>>b;
    out<<n*m-a*m-b*n+a*b<<ln;
}

Measured memory_bytes: 256
// abc049_b
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(int argc, char *argv[])
{
  int h,w;
  cin>>h>>w;
  string s;
  rep(i, h) {
    cin >> s;
    cout << s << endl;
    cout << s << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>

using namespace std;

int n, x;
map<int, int> map_a;

int main()
{
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> x;
		map_a[x]++;
	}

	cout << map_a.size() << endl;

	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn calc(k: i64, index: usize, seq: &Vec<i64>) -> bool {
    let n = seq.len();
    let mut dp = vec![false; k as usize];
    dp[0] = true;
    for i in 0..n {
        if i == index {
            continue;
        }
        for j in (0..k - seq[i]).rev() {
            let v = seq[i] + j;
            dp[v as usize] |= dp[j as usize];
        }
    }
    // println!("{} {:?}", index, dp);
    for i in 0..k {
        if i + seq[index] >= k && dp[i as usize] {
            return true;
        }
    }
    return false;
}

fn main() {
    let n = read::<usize>();
    let k = read::<i64>();
    let mut seq = vec![0; n];
    for i in 0..n {
        seq[i] = read::<i64>();
    }
    let ans = solve(n, k, &seq);
    println!("{}", ans);
}
fn solve(n: usize, k: i64, seq: &Vec<i64>) -> usize {
    let mut sum = 0;
    for i in 0..n {
        sum += seq[i];
    }
    if sum < k {
        return n;
    }

    let mut seq = seq.clone();
    seq.sort();
    let mut l = -1;
    let mut r = n as i64 - 1;
    while r - l > 1 {
        let mid = (l + r) / 2;
        if calc(k, mid as usize, &seq) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r as usize;
}

Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;




int main(void) {

    int n,r;
    cin>>n>>r;
    if(n>=10)fin(r);
    else fin(r+100*(10-n));
}

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

# input = stdin.readline



def main():
  N = int(input())
  p = list(map(int,input().split()))
  def solve(n,p):
    assert n >= 2
    target = sum(0 if p[i]==i+1 else 1 for i in range(n)) 
    return target == 0 or target == 2
  print("YES" if solve(N,p) else "NO")
  return

if __name__ == '__main__':
  main()


Measured memory_bytes: 9016
#include <stdio.h>
#include <string.h>
int main() {
	char A[11], B[11], C[11];
	scanf("%s %s %s", A, B, C);
	int lastA = strlen(A) - 1, lastB = strlen(B) - 1;
	if (A[lastA] == B[0] && B[lastB] == C[0]) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 1624
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;

int dis[1010], wea[1010],dp[2][1010];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> dis[i];
	}
	for (int i = 1; i <= M; i++) {
		cin >> wea[i];
	}
	int in = 0, ou = 1;
	fill(dp[in], dp[in] + N + 1, INF);
	dp[in][0] = 0;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			dp[ou][j] = min(dp[in][j], dp[in][j - 1] + dis[j] * wea[i]);
		}
		swap(in, ou);
	}
	cout << dp[in][N] << endl;
	return 0;
}

Measured memory_bytes: 3084
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
	int res = 0;
	char c;
	bool flag = false;
	c = getchar();
	while(!isdigit(c))
	{
		flag = (c == '-');
		c = getchar();
	}
	while(isdigit(c))
	{
		res = res * 10 + (c ^ 48);
		c = getchar();
	}
	return !flag ? res : -res;
}
const int Max_n = 2e3 + 5;
struct node{
	int nex , to;
	node(int a , int b)
	{
		nex = a , to = b;
	}
	node(){}
}edge[Max_n << 2];
const int MOD = 924844033;
int head[Max_n * 2] , tot , n , k , siz[Max_n * 2];
ll jc[Max_n ] , g[Max_n] , f[Max_n * 2][Max_n][2];
vector<int> fin;
bool vis[Max_n * 2];
inline void add_edge(int x , int y)
{
	edge[ ++ tot] = node(head[x] , y) , head[x] = tot;
	edge[ ++ tot] = node(head[y] , x) , head[y] = tot;
}
void dp(int now , int from)
{
	vis[now] = true;
	siz[now] = siz[from] + 1;
	bool flag = true;
	for(int i = head[now] ; i ; i = edge[i].nex)
	{
		int nex = edge[i].to;
		if(nex == from)	continue;
		f[nex][0][0] = f[now][0][0] + f[now][0][1] , f[nex][0][0] %= MOD;
		for(int j = 1 ; j <= n ; ++ j)
		{
			f[nex][j][0] = f[now][j][0] + f[now][j][1] , f[nex][j][0] %= MOD;
			f[nex][j][1] = f[now][j - 1][0];
		}
		flag = false;
		dp(nex , now);
	}
	if(flag)	fin.push_back(now);
}
int main()
{
	n = read() , k = read();
	for(int i = 1 ; i <= n ; ++ i)
	{
		if(i - k > 0)	
			add_edge(i , i - k + n);
		if(i + k <= n)	
			add_edge(i , i + k + n);
	}
	for(int i = 1 ; i <= n ; ++ i)
	{
		if(!vis[i])	f[i][0][0] = 1 , dp(i , 0);
		if(!vis[i + n])	f[i + n][0][0] = 1 , dp(i + n , 0);
	}
	g[0] = 1;
	int sz = fin.size();
	for(int i = 0 ; i < sz ; ++ i)
	{
		int now = fin[i];
		for(int j = n ; j >= 1 ; -- j)
			for(int h = j - 1 ; h >= max(0 , j - (siz[now] / 2 + 1)) ; -- h)
					g[j] += g[h] * ((f[now][j - h][0] + f[now][j - h][1]) % MOD) , g[j] %= MOD;
			
	}
	jc[0] = 1;
	for(int i = 1 ; i <= n ; ++ i)
		jc[i] = jc[i - 1] * i % MOD;
	ll ans = jc[n];
	for(int i = 1 ; i <= n ; ++ i)
		if(i % 2)	ans -= g[i] * jc[n - i] , ans %= MOD;
		else ans += g[i] * jc[n - i] , ans %= MOD;
	ans = (ans + MOD) % MOD;
	printf("%lld\n" , ans);
	return 0;
}

Measured memory_bytes: 128612
package main

import "fmt"

func main() {
	var n, ans, cnt int
	fmt.Scan(&n)
	h := make([]int, n)
	for i := range h {
		fmt.Scan(&h[i])
	}
	var on bool
	for {
		cnt = 0
		on = false
		for i := 0; i < n; i++ {
			if h[i] > 0 {
				h[i]--
				if !on {
					cnt++
					on = true
				}
			} else {
				on = false
			}
		}
		if cnt == 0 {
			break
		} else {
			ans += cnt
		}
	}
	fmt.Println(ans)

}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<vector>
#include<stdio.h>
#define nl "\n"
using namespace std;
#define f(i, a, b) for(ll i = a; i<b;i++)
#define ll long long
int main()
{
    ll cost = 1e10;
    ll n, m, x;
    cin>>n>>m>>x;
    vector< vector<ll> > books(n, vector<ll> (m+1));
    f(i, 0, n)
    f(j, 0, m+1)
    {
        cin>>books[i][j];
    }

    f(i, 1, (1<<n))
    {
         ll total = 0;
         vector <ll> v(m);
         ll t= 0;
         f(j, 0, n)
         {
             if(i&(1<<j))                           //if that bit is on then fetch its price
             {
                 total+=books[j][0];
                 f(k, 0, m)                         //we will add up the skills
                 v[k]+=books[j][k+1];

             }


         }
           bool f = 1;
         f(j, 0, m)
         if(v[j]<x)
         {
             f = 0;
             break;
         }

         if(f)
         cost = min(cost, total);




    }
if(cost==1e10)
            cout<<-1<<nl;
         else
            cout<<cost;


/*
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

*/

    //cin>>a>>b>>c>>k;

   // cout<<sum<<nl;


    return 0;
}
/*
 if(k-a>=0)
    {
        sum+=a;
        k -= a;
    }
    else{
        printf("%lld\n", sum);
//        cout<<k+sum<<nl;
        return 0;
    }
    if(k-b>=0)
    {
        k-=b;
    }
    else
    {
        cout<<sum<<nl;
        return 0;
    }
    if(k-c>=0)
    {
        sum -= c;
        k-=c;
    }
    else{
        cout<<sum-k<<nl;
    }

    */


Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int a,b;
	cin >> a >>b;
	if ((a *b) %2==0) cout << "Even" << endl;
	else cout << "Odd" << endl;
	return 0;
}


Measured memory_bytes: 256
/*3
2 5 //b
a b c
2>=max(a,b)
5>=max(b,c)

2
3//b
a b
3>=max(a,b)
6
0,153,10,10,23
a,b,c,d,e,f
0>=max(a,b)
153>=max(b,c)
10>=max(c,d)
10>=max(d,e)
23>=max(e,f)
a=0,
b=0,
c=10,
d=10
e=10
f=23*/

#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
int main(){
  int n;cin >> n;
  vector<int> b(n-1);
  int ans = 0;
  for(auto &i:b) cin >> i;
  ans+=b[0]+b[n-2];
  rep(i,n-2){
    ans+=min(b[i],b[i+1]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
int dp[n];
memset(dp,-1,sizeof(dp));
dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=min(i+k,n-1);j++){
            if(dp[j]==-1) dp[j]=dp[i]+abs(arr[i]-arr[j]);
           else dp[j]=min(dp[j],dp[i]+abs(arr[i]-arr[j]));
        }
    }
cout<<dp[n-1]<<endl;
return 0;
}

Measured memory_bytes: 1024
M=10**9+7;n=int(input());s=input();d=[1]*n
for k in range(n-1,0,-1):
 N=[0]*n
 for i in range(k+1):
  if'<'<s[n-1-k]:N[0]+=d[i];N[i]-=d[i]
  else:N[i]+=d[i];N[k]-=d[i]
 for i in range(k):N[i+1]=(N[i+1]+N[i])%M
 d=N
print(d[0]%M)

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

int main() 
{
     int n ; 
     cin >> n ;
     ll x , ans = 0 ;
     for ( int i = 0 ; i < n ; i++ )
     {
         cin >> x ;
         int cnt = 0 ;
         while ( x  && (x %2 == 0 ) )
         {
             cnt++ ;
             x = x / 2 ;
         }
         ans += cnt ;
     }

  cout << ans << endl ;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}




map<ll,ll> D;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N ; cin >> N ;
  rep(i,N){
    ll inp; cin >> inp;
    D[inp] ++;
  }
  ll M ; cin >> M ;
  vector<ll> T;
  rep(i,M){
    ll inp; cin >> inp;
    T.pb(inp);
  }
  
  rep(i,M){
    D[T[i]]--;
    if(D[T[i]] < 0) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  
  //cout << fixed << setprecision(16) << ans << endl;
  
  return 0;
}


Measured memory_bytes: 14964
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    set<int> s;
    rep(i,n){
        int x;
        cin >> x;
        s.insert(x);
    }
    if(s.size()==n){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 9600
#include<iostream>
using namespace std;
int a[1000000];
int sum[1000000];
int n;
int main(){
 for (int i=2;i<1000000;i++){
  if (!a[i])
   for (int j=i*2;j<1000000;j+=i)
    a[j]=1;
 }
 for (int i=2;i<1000000;i++) sum[i]=sum[i-1]+(a[i]==0?1:0);
 while (cin>>n)
  cout<<sum[n]<<endl;
 return 0;
}

Measured memory_bytes: 10908
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        
        int tmp;
        tmp = x2 - x1;
        while (tmp-- > 0) {
            System.out.print("R");
        }
        
        tmp = y2 - y1;
        while (tmp-- > 0) {
            System.out.print("U");
        }
        
        tmp = x2 - x1;
        while (tmp-- > 0) {
            System.out.print("L");
        }
        
        tmp = y2 - y1;
        while (tmp-- > 0) {
            System.out.print("D");
        }
        
        System.out.print("D");
        
        tmp = x2 - x1;
        while (tmp-- > 0) {
            System.out.print("R");
        }
        
        System.out.print("RU");
        
        tmp = y2 - y1;
        while (tmp-- > 0) {
            System.out.print("U");
        }
        
        System.out.print("LU");
        
        tmp = x2 - x1;
        while (tmp-- > 0) {
            System.out.print("L");
        }
        
        System.out.print("LD");
        
        tmp = y2 - y1;
        while (tmp-- > 0) {
            System.out.print("D");
        }
        
        System.out.println("R");
    }
}


Measured memory_bytes: 27204
N, A, B = map(int, input().split())
ans = 0
for i in range(1, N+1):
  j = list(str(i))
  n = len(j)
  a = 0
  for l in range(n):
    a += int(j[l])
  if a >= A and a <= B:
    ans += i
print(ans)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int N;
  cin >> N;
  string s;
  cin >> s;
  int count=0;
  if(N%2==1)cout<<"No"<<endl;
  else{
	for(int i=0;i<N/2;i++){
     if(s.at(i)== s.at(N/2+i) )count++; 
    }
    if(count==N/2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
   

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long _MOD = 1000000007;
const long long MOD = 998244353;

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

	ll n, k;
	cin >> n >> k;

	ll ans = 1;
	llREP(i, 1, (n + 2) - k) {
		ans += (n*(n + 1)) / 2 - ((n - i)*(n - i + 1)) / 2 - ((i - 1)*i) / 2 + 1;

		ans %= _MOD;
	}

	cout << ans << "\n";

	return 0;
}
 

Measured memory_bytes: 3656
#include "iostream"
#include "vector"
#include "array"
#include "string"
#include "algorithm"

using namespace std;
#define rep(p,q) for(int i = p;i < q;i++)

//ICPC Score Totalizer Software
int main(void) {
	int num = 0;
	while (cin >> num && num != 0) {
		vector<int> v = vector<int>();
		int point = 0;
		rep(0, num) {
			cin >> point;
			v.push_back(point);
		}
		sort(v.begin(), v.end());
		int sum = 0;
		rep(1, num - 1) {
			sum += v[i];
		}
		cout << sum / (num - 2) << endl;
	}
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
//<(") 
#define ll long long  
using namespace std;
 
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
 
const ll mod = 1e9 + 7;
const ll siz = 3e2 + 10;
const ll base = 32;
const ll MAXX = 1e18;

ll n, k;
vector<ll> hold;
vector<ll> nxt;
ll change[siz];

ll res[siz][siz][siz];

void compress() {
	sort(nxt.begin(), nxt.end());
	ll l = unique(nxt.begin(), nxt.end()) - nxt.begin();
	nxt.resize(l);
	for (ll i = 0; i <= n; i++) {
		ll val = lower_bound(nxt.begin(), nxt.end(), hold[i]) - nxt.begin() + 1;
		change[val] = hold[i];
		hold[i] = val;
	}
}

ll dp(ll last, ll cur, ll rem) {
	if (cur > n) {
		return 0;
	}
	ll &ans = res[last][cur][rem];
	if (ans != -1) {
		return ans;
	}
	ans = dp(cur, cur + 1, rem) + max(0LL, hold[cur] - hold[last]);
	if (rem > 0) {
		ans = min(ans, dp(last, cur + 1, rem - 1));
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("INP.txt", "r", stdin);
	//freopen("OUT.txt", "w", stdout);
	cin >> n >> k;
	hold.resize(n + 1);
	hold[0] = 0;
	nxt.push_back(0);
	memset(res, -1, sizeof(res));
	for (ll i = 1; i <= n; i++) {
		cin >> hold[i];
		nxt.push_back(hold[i]);
	}
	cout << dp(0, 1, k) << '\n';
	return 0;
}  	 	   		  		 		 	  			  		

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

const ll MOD = 1000000007;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> S(N), T(M);
  for (int i = 0; i < N; i++) cin >> S[i];
  for (int i = 0; i < M; i++) cin >> T[i];

  vector<vector<ll>> dp(N, vector<ll>(M)), sum(N, vector<ll>(M));
  dp[0][0] = sum[0][0] = (S[0] == T[0]);
  for (int i = 1; i < N; i++) {
    dp[i][0] = (S[i] == T[0]);
    sum[i][0] = sum[i - 1][0] + dp[i][0];
  }
  for (int j = 1; j < M; j++) {
    dp[0][j] = (S[0] == T[j]);
    sum[0][j] = sum[0][j - 1] + dp[0][j];
  }
  for (int i = 1; i < N; i++) {
    for (int j = 1; j < M; j++) {
      dp[i][j] = S[i] == T[j] ? sum[i - 1][j - 1] + 1 : 0;
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + dp[i][j];
      sum[i][j] = (sum[i][j] + MOD) % MOD;
    }
  }
  cout << (sum[N - 1][M - 1] + 1) % MOD << endl;
}

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

//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3", "Ofast", "unroll-loops", "fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


#define int long long
#define endl '\n'

using namespace std;


char need(char a, char b){
    if (a == 'R' && b == 'G' || a == 'G' && b == 'R'){
        return 'B';
    }
    if (a == 'R' && b == 'B' || a == 'B' && b == 'R'){
        return 'G';
    }
    if (a == 'B' && b == 'G' || a == 'G' && b == 'B'){
        return 'R';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int i, j, n;
    cin >> n >> s;
    map < char, int > m;
    m['R'] = 0;
    m['G'] = 1;
    m['B'] = 2;
    vector < vector < int > > a(n, vector < int > (3));
    a[n - 1][m[s[n - 1]]] = 1;
    for (i = n - 2; i > -1; i--){
        a[i][0] = a[i + 1][0];
        a[i][1] = a[i + 1][1];
        a[i][2] = a[i + 1][2];
        a[i][m[s[i]]]++;
    }
    int ans = 0;
    for (i = 0; i < n; i++){
        for (j = i + 1; j < n; j++){
            if (s[i] == s[j] || j + 1 == n){
                continue;
            }
            char x = need(s[i], s[j]);
            ans += a[j + 1][m[x]];
            if (j + (j - i) < n && s[j + (j - i)] == x){
                ans--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3808
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;

int h, w;
int n[30] = { 0 };

int main() {
	cin >> h >> w;
	char c;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> c;
			n[c - 'a']++;
		}
	}
	if (h % 2 == 1 && w % 2 == 1) {
		bool flag = true;
		bool flag_ = true;
		for (int i = 0; i <= 'z' - 'a'; i++) {
			if (n[i] % 2 != 0) {
				if (flag) {
					n[i]--;
					flag = false;
				}
				else {
					cout << "No" << endl;
					flag_ = false;
					break;
				}
			}
		}
		if (flag_) {
			int count = 0;
			for (int i = 0; i <= 'z' - 'a'; i++) {
				if (n[i] % 4 == 2) count++;
			}
			if (count <= (h + w) / 2 - 1) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	else if (h % 2 == 1 || w % 2 == 1) {
		bool flag = true;
		for (int i = 0; i <= 'z' - 'a'; i++) {
			if (n[i] % 2 == 1) flag = false;
		}
		if (!flag) cout << "No" << endl;
		else {
			int count = 0;
			for (int i = 0; i <= 'z' - 'a'; i++) {
				if (n[i] % 4 == 2) count++;
			}
			if (h % 2 == 1 && count <= w / 2) cout << "Yes" << endl;
			else if (w % 2 == 1 && count <= h / 2) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	else {
		bool flag = true;
		for (int i = 0; i <= 'z' - 'a'; i++) {
			if (n[i] % 4 != 0) flag = false;
		}
		if (flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0; 
} 

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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
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);
}

int ans = 0;
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main()
{
  int a, b;
cin>> a >> b;
if(a>b) pr(a-1);
else pr(a);
  return 0;
}


Measured memory_bytes: 3600
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;

map<int, int> mp;

int
main(void){  
  ios_base::sync_with_stdio(false);

  int a, b, c, d;
  cin >> a >> b >> c >> d;

  mp[a]++;
  mp[b]++;
  mp[c]++;
  mp[d]++;
  
  if(mp[1] == 1 && mp[9] == 1 && mp[7] == 1 && mp[4] == 1) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 256
z=0
h={}
n=gets.to_i
n.times do
    a, b=gets.split.map(&:to_i)
    if a==0 and b==0
        z+=1
    else
        h[ab=b==0 ? (10**20).to_r : Rational(a, b)]||=0
        h[ab]+=1
    end
end

MOD=10**9+7
res=1
h.each do |k, v|
    x=k.zero? ? (10**20).to_r : -1/k
    x=0.to_r if k==(10**20).to_r

    w=h[x]||0
    res*=2.pow(v, MOD)+2.pow(w, MOD)-1
    res%=MOD

    h[k]=0
    h[x]&&=0
end
puts (res+z+MOD-1)%MOD


Measured memory_bytes: 34068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N;
    cin >> N;
    ll tmp;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        if(tmp % 2 == 1){
            printf("first\n");
            return 0;
        }
    }
    printf("second\n");

}


Measured memory_bytes: 3564
N, A, B = map(int, input().split(" "))
X = list(map(int, input().split(" ")))

diff_X = [i-j for i,j in zip(X[1:], X[:-1])]

res = 0
for i in range(len(diff_X)):
    if A*diff_X[i] < B:
        res += A*diff_X[i]
    else:
        res += B

print(res)

Measured memory_bytes: 14252
#1行目の文字列
s = str(input())
#2行目の文字列
t = str(input())
#文字列の各文字が一致しているか確認
count = 0
#入力文字列の文字数だけループ
for i in range(len(s)):
    #文字列が一致していれカウンターに1プラス
    if s[i] == t[i]:
        count += 1
print(count)


Measured memory_bytes: 38384
import numpy as np
import sys
N,M,X = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
temp = []
ans1 = 0
ans2 = 0
for i in range(N+1):
    if (i == 0) or (i==N):
        temp.append(0)
    elif i in A:
        temp.append(1)
    # elif (i == 0) or (i==N):
    #     temp.append(0)
    else:
        temp.append(0)
for i in range(X,N+1):
    ans1 += temp[i]

for i in range(X):
    ans2 += temp[i]

print(min(ans1,ans2))

Measured memory_bytes: 12748