akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define FAST  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int 
#define ar array
#define pb push_back
#define fi(a,b) for(ll i=a;i<(b);i++)
#define fj(a,b) for(ll j=a;j<(b);j++)
#define fk(a,b) for(ll k=a;k<(b);k++)

const int mod=998244353;
const int mxn=2e5+2;
int n,k;
vector<int> dp(mxn);
struct node
{
	ll s,m,lz;
} st[1<<19];


void update(int index,int val,int l2=0,int r2=n-1,int ci=0)
{
	if(l2==r2)
	{
		//st[ci].m=val;
		st[ci].s=val;
		return ;
	}
	int mid=(l2+r2)/2;
	if(index<=mid)
		update(index,val,l2,mid,2*ci+1);
	else
	{
		update(index,val,mid+1,r2,2*ci+2);
	}
	st[ci].s=(st[2*ci+1].s+st[2*ci+2].s)%mod;
	st[ci].m=min(st[2*ci+1].m,st[2*ci+2].m);
}
	
int query(int l1,int r1,int l2=0,int r2=n-1,int ci=0)
{
	if(l1<=l2&&r1>=r2)
	{
		return st[ci].s;
	}
	if(l2>r1||r2<l1)
	{
		return 0;
	}
	int mid=(l2+r2)/2;
	
	//return min(query(l1,r1,l2,mid,2*ci+1),query(l1,r1,mid+1,r2,2*ci+2));
	return (query(l1,r1,l2,mid,2*ci+1)+query(l1,r1,mid+1,r2,2*ci+2))%mod;
}

int main()
{
	FAST;
	//#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	//#endif
	//int tt;
	//cin>>tt;
	//while(tt--)
	{
		cin>>n>>k;
		dp=vector<int> (n+1);
		dp[0]=1;
		fi(0,n+1)
		{
			update(i,dp[i]);
		}
		vector<pair<int,int>> pairs;
		vector<int> a(n);
		fi(0,k)
		{
			int l,r;
			cin>>l>>r;
			pairs.pb({l,r});
			fj(l,r+1)
			{
				a.pb(j);
			}
		}
		sort(pairs.begin(),pairs.end());
		// number of ways to get sum n-1
		//sort(a.begin(),a.end());
		fi(1 ,n)
		{
			fj(0,k)
			{
				if(i<pairs[j].first) break;
				int left=max(0LL,(i-pairs[j].second));
				int right=(i-pairs[j].first);
				dp[i]=(dp[i]+query(left,right))%mod;
				update(i,dp[i]);
			}
		}
		cout<<dp[n-1];
		
	}		
}


Measured memory_bytes: 18552
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

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

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;

template<class T> bool ckmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template <class X, class Y>
std::ostream & operator << (std::ostream & os, std::pair <X, Y> const& p) {
    return os << p.first << " " << p.second;
}

template <class Ch, class Tr, class Container>
std::basic_ostream <Ch, Tr> & operator << (std::basic_ostream <Ch, Tr>& os, Container const& x) {
    bool first = true;
    for(auto& y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}

using namespace std;

class AAirportBus {
public:
	void solve(std::istream& in, std::ostream& out) {
        int n, c, k;
        in >> n >> c >> k;
        vi T(n);
        in >> T;
        sort(all(T));
        int res = 0, last = 0, now = 0;
        trav(t, T) {
            if (t > last or now == c) {
                res++;
                last = t + k;
                now = 0;
            }
            now++;
        }
        out << res << '\n';
	}

	void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
	AAirportBus solver;
    solver.setup();
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3772
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    UnionFind(int n) : parent(n, -1) { }
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x != y) {
            if (parent[y] < parent[x]) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
        }
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return parent[x] < 0 ? x : parent[x] = root(parent[x]);
    }
};

int main() {
    int n;
    cin >> n;
    UnionFind uf(n);
    vector<pair<int,pair<int,int> > > E;
    int cost;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            cin >> cost;
            if (0 <= cost) {
                E.push_back(make_pair(cost, make_pair(i, j)));
            }
        }
    }
    sort(E.begin(), E.end());
    int res = 0;
    for (int i=0; i<(int)E.size(); ++i) {
        if ( ! uf.find(E[i].second.first, E[i].second.second)) {
            uf.unite(E[i].second.first, E[i].second.second);
            res += E[i].first;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1324
#include<iostream>
#include<cstdio>
using namespace std;
struct data{
	long long s,la,sz,p;
}t[1000001];
long long n,m,x,y,d,f[200001],mod=998244353ll;
void up(long long a){
	t[a].s=(t[a*2ll].s*f[t[a*2ll+1ll].sz]+t[a*2ll+1ll].s)%mod;
}
void down(long long a,long long c){
	t[a].s=(t[a].p*c)%mod;
	t[a].la=c;
}
void downtag(long long a){
	if(t[a].la){
		down(a*2ll,t[a].la);
		down(a*2ll+1ll,t[a].la);
		t[a].la=0ll;
	}
}
void build(long long a,long long l,long long r){
	t[a].sz=r-l+1ll;
	if(l==r){
		t[a].s=1ll;
		t[a].la=0ll;
		t[a].p=1ll;
		return;
	}
	long long mid=(l+r)/2ll;
	build(a*2ll,l,mid);
	build(a*2ll+1ll,mid+1ll,r);
	up(a);
	t[a].p=t[a].s;
}
void turn(long long a,long long l,long long r,long long ql,long long qr,long long c){
	if(l>qr||r<ql)return;
	if(ql<=l&&r<=qr){
		down(a,c);
		return;
	}
	downtag(a);
	long long mid=(l+r)/2ll;
	turn(a*2ll,l,mid,ql,qr,c);
	turn(a*2ll+1ll,mid+1ll,r,ql,qr,c);
	up(a);
}
int main(){
	scanf("%lld%d",&n,&m);
	f[0ll]=1ll;
	for(long long i=1ll;i<=n;i++)f[i]=(f[i-1ll]*10ll)%mod;
	build(1ll,1ll,n);
	for(long long i=1ll;i<=m;i++){
		scanf("%lld%d%d",&x,&y,&d);
		turn(1ll,1ll,n,x,y,d);
		printf("%lld\n",t[1ll].s);
	}
}

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

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

  
  
  for (int i = 0; i < S.size(); i++){ 
   if(isupper(S.at(i) + N)){
    T.at(i) = S.at(i) + N;
   }
    else {
      T.at(i) = S.at(i) + N - 26;
  }
  }
 
    cout << T <<endl;

}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

using namespace std;
using ll = unsigned long long;
using pii = pair<int, int>;

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7,maxn = 100000000;
const double PI = acos(-1);


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    cout << (n == m? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;

typedef long long ll;

ll gcd(ll x, ll y) {
  while (y != 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}

int main(){
   int N;
   cin >> N;
   vector<long long> tokei(N);
   for(int i = 0;i<N;i++){
      cin >> tokei.at(i);
   }
  	long long ans = tokei.at(0);

   for(int j = 0;j<N-1;j++){
   	ans = lcm(ans,tokei.at(j+1));
    tokei.at(j+1) = ans;
   }

   cout << tokei.back() << endl;


}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    long long int flag,a1,b1,t,k,a,b;
    while(cin>>a>>b){
		if(a==b){
			cout<<'1'<<" "<<a<<endl;
			continue;
		}
    	a1=a,b1=b;
		if(a<b)
			t=a,a=b,b=t;
		k=a%b;
		while(k){
			a=b;
			b=k;
			k=a%b;
		}
		cout<<b<<" "<<(a1/b)*b1<<endl;
    }
}

Measured memory_bytes: 1160
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;
//#define int long long
#define m_p make_pair
#define mod 1000000007
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>vec[i];
using namespace std;

int jousu(int, int);
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int kurai(int x00, int y00) {
	int z00 = (x00 % jousu(10, y00)) / jousu(10, y00 - 1);
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}



int main() {
	int a=0,b,d;
	string s;
	char c='R';
	vector<int>vec;
	cin >> s;
	vector<int>vec2;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != c) {
			vec.push_back(a);
			a = 0;
			c == 'R' ? c = 'L' : c = 'R';
		}
		a++;
	}
	vec.push_back(a);
	for (int i = 0; i < vec.size(); i+=2) {
		b = vec[i];
		d = vec[i + 1];
		for (int i = 0; i < b - 1; i++) {
			vec2.push_back(0);
		}
		vec2.push_back((b + 1) / 2 + d / 2);
		vec2.push_back(b / 2 + (d + 1) / 2);
		for (int i = 0; i < d - 1; i++) {
			vec2.push_back(0);
		}
	}
	cout << vec2[0];
	for (int i = 1; i < vec2.size(); i++) {
		cout << " " << vec2[i];
	}
	cout << endl;
}



Measured memory_bytes: 1592
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
string s;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	reverse(s.begin(),s.end());
	int sz = (int)s.size();
	int ans = 0 , fix = 0;
	for(int i=0;i<sz;i++) {
		int val = s[i] - '0' + fix;
		int need = val % 10;
		fix = val / 10;
		if(need > 5 || (need == 5 && i < sz-1 && s[i+1] >= '5'))
			ans += (10 - need) , fix = 1;
		else
			ans += need;
	}
	ans += fix;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1948
X, K, D = map(int, input().split())

X = abs(X)

if X == 0:
  if K % 2 == 0:
    print(0)
  else:
    print(D)

elif X - K*D >= 0:
  print(X - K*D)
    
elif X - K*D < 0:
  a = X // D
  b = a + 1
  if (K - a) % 2 == 0:
    print(X % D)
  else:
    print(D - X % D)

Measured memory_bytes: 9180
import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for _ in range(M):
    pop = heapq.heappop(A)
    if pop % 2 == 0:
        num = pop//2
    else:
        num = (pop+1)//2
    heapq.heappush(A, num)

print(-sum(A))


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

int solution_sort(vector<pair<int,int>>& dish, int T)
{
    int N = dish.size();
    sort(dish.begin(), dish.end());
    
    int ans = 0;
    vector<int> dp(T, 0);
    for(int i = 0; i < N; ++i){
        int A = dish[i].first;
        int B = dish[i].second;
        ans = max(ans, dp[T-1]+B);
        for(int j = T-1; j >= A; --j) dp[j] = max(dp[j], dp[j-A]+B);
    }
    return ans;
}

int main()
{
    int N, T;
    cin >> N >> T;
    vector<pair<int,int>> dish(N);
    REP(i, N) cin >> dish[i].first >> dish[i].second;

    cout << solution_sort(dish, T) << endl;

    return 0;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 10;
const int MAX_M = 10;
const int MAX_Q = 50;

int N, M, Q;
int A[MAX_Q], B[MAX_Q], C[MAX_Q], D[MAX_Q];

int E[MAX_N];
int solve(int pos = 0, int preE = 1) {
  if (pos == N) {
    int ret = 0;
    REP(q,Q) {
      if (E[B[q]] - E[A[q]] == C[q]) {
        ret += D[q];
      }
    }
    return ret;
  } else {
    int ans = 0;
    FOR(e,preE,M+1) {
      E[pos] = e;
      ans = max(ans, solve(pos+1, e));
    }
    return ans;
  }
}

signed main()
{
  cin >> N >> M >> Q;
  REP(q,Q) {
    cin >> A[q] >> B[q] >> C[q] >> D[q];
    A[q]--; B[q]--;
  }

  cout << solve() << endl;

  return 0;
}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main(){
    int H, W, i, j;
    cin >> H >> W;
    
    while(H != 0 && W != 0){
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
        cin >> H >> W;
    }
    return 0;
}


Measured memory_bytes: 3084
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  auto ai = readln.split.to!(int[]);

  auto c = 0L;
  mergeSort(ai, 0, n, c);

  writeln(c);
}

void merge(ref int[] ai, size_t l, size_t m, size_t r, ref long c)
{
  auto li = ai[l..m].dup;
  auto ri = ai[m..r].dup;

  li ~= int.max;
  ri ~= int.max;

  auto i = 0, j = 0, t = 0L;
  foreach (k; l..r) {
    if (li[i] <= ri[j]) {
      ai[k] = li[i];
      ++i;
      c += t;
    } else {
      ai[k] = ri[j];
      ++j;
      ++t;
    }
  }
}

void mergeSort(ref int[] ai, size_t l, size_t r, ref long c)
{
  if (l + 1 < r) {
    auto m = (l + r) / 2;
    mergeSort(ai, l, m, c);
    mergeSort(ai, m, r, c);
    merge(ai, l, m, r, c);
  }
}

Measured memory_bytes: 11732
n = int(input())
S = [input() for _ in range(n)]
m = int(input())
T = [input() for _ in range(m)]

# print(n,m)
# print(S)
# print(T)

s = {}
for x in S:
    if x in s:
        s[x] += 1
    else:
        s[x] = 1

t = {}
for x in T:
    if x in t:
        t[x] += 1
    else:
        t[x] = 1

# print(s,t)
ans = 0
for k,v in s.items():
    # print(k,v)
    c = v
    if k in t:
        c -= t[k]
    ans = max([ans,c])
print(ans)



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

#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long ll;

char s[100005];

int main() {
	int n;

	scanf("%d %s", &n, s);

	for(int i = 0; s[i]; i++) {
		int c = s[i]-'A' + n;
		s[i] = c%26 + 'A';
	}
	printf("%s\n", s);

    return 0;
}

Measured memory_bytes: 256
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def get_cost(min_v,max_v):
	if max_v<0:
		return abs(min_v)
	elif min_v >=0:
		return max_v
	else:
		ret = min(max_v+abs(min_v)*2, abs(min_v)+ max_v*2)
		return ret

def main():
	n, k = IN()
	al=list(IN())
	ret=min([get_cost(a,b) for a,b in zip(al,al[k-1:])])
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 62576
#include <bits/stdc++.h>
using namespace std;
 
#define    int                      long long int
#define    ld                       long double
#define    f(i,j,n)                 for(int i = j; i <= n; i++)
#define    r(i,n,j)                 for(int i = n; i >= j; i--)
#define    mod                      1000000007
#define    speed                    ios_base::sync_with_stdio(false);
#define    upp                      cin.tie(NULL);
#define    pb                       push_back
#define    mp                       make_pair
#define    T                        int ttt; cin >> ttt; while(ttt--)
#define    ff                       first
#define    ss                       second
#define    all(container)            container.begin() , container.end()
#define    sz(container)             (int)container.size()
#define    pii                      pair <int , int>
#define    sp(x)                    setprecision(x)

int power(int x, int y, int p)  
{  
    int res = 1;     
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)  
    {  
        
        if (y & 1)  
            res = (res*x) % p;  
  
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
}  
  

int32_t main()
{
    speed upp
        int x,y,z;
    cin>>x>>y>>z;
    cout<<z<<" "<<x<<" "<<y;     
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <fstream>
#include <cstring>

using namespace std;
typedef long long LL;

#define MAXN 100010
int n, m, k;
int a[MAXN];
LL dp[2][MAXN];
deque<pair<LL, int> > q;

int main() {
	//freopen("struck_out.in", "r", stdin);
	cin>>n>>m>>k;
	for (int i=0;i<n;i++) scanf("%d", &a[i]);
	memset(dp, 0, sizeof(dp));
	for (int i=0;i<n;i++) {
		dp[(k-1)&1][i] = 1LL*k*a[i];
		//cout<<k-1<<" "<<i<<" = "<<dp[k-1][i]<<endl;
	}
	for (int i=k-2;i>=0;i--) {
		q.clear();
		for (int j=n-2;j>=0;j--) {
			LL val=dp[(i+1)&1][j+1];
			while (q.size()>0 && q.front().first<=val) q.pop_front();
			q.push_front(make_pair(val, j+1));
			while (q.size()>0 && q.back().second-j-1>=m) q.pop_back();
			dp[i&1][j]=q.back().first+1LL*(i+1)*a[j];
			//cout<<i<<" "<<j<<" = "<<dp[i][j]<<endl;
		}
	}
	LL ret=0;
	for (int i=0;i<n;i++) ret=max(ret, dp[0][i]);
	cout<<ret<<endl;
}


Measured memory_bytes: 2304
#include	<bits/stdc++.h>
using	namespace	std;
main(){
int N;
string S;
cin>>N>>S;
int U=0;
for (int i=2;i<N;i++) {
	int T=0;
	for (int j=0;i+j<N;j++)
		if (S[j]==S[j+i]) U=max(U,min(i, ++T));
		else T=0;
}
cout<<U;
}



Measured memory_bytes: 256
n = int(input())
a = input()
b = input()
c = input()

count = 0

for i in range(n):
  if a[i] == b[i]:
    if a[i] != c[i]:
      count += 1
  elif a[i] == c[i]:
    count += 1
  elif b[i] == c[i]:
    count += 1
  else:
    count += 2
    
print(count)

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

int main(){

  int A, B, num=0;
  cin >> A >> B;
  bool kai;

  for(int i=A; i<=B; i++){

    kai = true;
    if(i%10 != (i/10000)%10) kai = false;
    if((i/10)%10 != (i/1000)%10) kai = false;
    num += kai ? 1 : 0 ;
    
  }

  cout << num << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define inf 1000000000
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define yoi cout<<"yo"<<endl;
#define debug(x) cerr << #x << " is " << x << endl;
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int main(){
IOS;
string s;
cin>>s;
int i;
int n=s.length();
int left[n],right[n];
for(i=n-1;i>=0;i--){
    if(s[i]=='L')
        right[i]=i;
    else right[i]=right[i+1];
}
for(i=0;i<n;i++){
    if(s[i]=='R')
        left[i]=i;
    else left[i]=left[i-1];
}
int a[n];
memset(a,0,sizeof(a));
for(i=0;i<n;i++){
    if(s[i]=='R'){
        if((right[i]-i)%2)
            a[right[i]-1]++;
        else a[right[i]]++;
    }
    else{
        if((i-left[i])%2)
            a[left[i]+1]++;
        else a[left[i]]++;
    }
}
for(i=0;i<n;i++){
    cout<<a[i]<<" ";
}
cout<<endl;
}


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

int main()
{
	int n,T;
  	cin>>n>>T;
  	int x,y;
  	int min_cost=INT_MAX;
  	for(int i=0 ; i<n ; ++i)
    {
      	cin>>x>>y;
		if(y<=T)
        {
        	min_cost=min(min_cost,x);
        }
    }
  	if(min_cost!=INT_MAX)
  	cout<<min_cost<<endl;
  	else
    cout<<"TLE"<<endl;
	return 0;
}

Measured memory_bytes: 256
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A)

x = A[0]
L = []
c = 1
for i in range(len(A) - 1):
	if x == A[i + 1]:
		c += 1
	else:
		L.append(c)
		c = 1
	x = A[i + 1]

L.append(c)

L = sorted(L)

n = len(L)

ans = 0

if n <= K:
	print(0)
else:
	for i in range(n - K):
		ans += L[i]
	print(ans)

Measured memory_bytes: 25716
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

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

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

    static void solve(Scanner scanner) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        int d = scanner.nextInt();
        System.out.println((a - c) * (b - d));
    }
}

Measured memory_bytes: 23636
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix


def solv(A, B):
    for price in range(B*10, B*10+10):
        if (price * 8) // 100 == A:
            return price
    return -1


if __name__ == "__main__":

    A, B = map(int, input().split())
    ans = solv(A, B)

    print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<stdio.h>
using namespace std;
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<((abs(c-a)<=d||(abs(c-b)<=d&&abs(b-a)<=d))?"Yes":"No")<<endl;;






return 0;
}


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(){
    int a, b; cin >> a >> b;
    cout << max({a+b, a-b, a*b}) << endl;
}

Measured memory_bytes: 3548
import scala.io.StdIn.readLine

object Main {
  def main(args:Array[String]):Unit = {
    val N:Int = readLine().toInt
    val data = readLine().split(" ").map(_.toInt)
    var total:Long = 0
    for (i <- 0 until N) {
      total += data(i)
    }
    println("%d %d %d".format(data.min, data.max, total))
  }
}

Measured memory_bytes: 48840
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef long double ld;
typedef unsigned long long ull;
#define X first
#define Y second
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class X> using indexed_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int M = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int modpow(int n, int k, int MOD);

/**************** code starts here ****************/

void poppingfever() {
	int n, a, b; cin >> n >> a >> b;
	cout << min(a, b) << ' ' << max(0LL, (a+b) - n);
} 

/**************************************************/

signed main() {
	#ifdef fastfurioustransform
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0); cin.tie(0);
	//cout << fixed << setprecision(12);

	int t = 1;
	while(t--) {
		poppingfever();
	}

	return 0;
}

int modpow(int n, int k, int MOD) {
	int ans = 1; n %= MOD;
	while (k > 0) {
		if (k & 1) ans = (ans*n) % MOD;
		k >>= 1; n = (n*n) % MOD;
	}
	return ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i=l,i##end=r;i<=i##end;++i)
#define per(i,r,l) for (int i=r,i##end=l;i>=i##end;--i)
#define sit set<int>::iterator
#define ll long long
using namespace std;
const int N=1e6+6;
int tag[N];
int main(){
    int n,k; cin>>n>>k;
    rep(i,1,k){ int x; cin>>x; tag[x]=true; }
    for (int i=n;;++i){
        int x=i; bool f=false;
        while (x){
            if (tag[x%10]){ f=true; break; }
            x/=10;
        }
        if (!f){ cout<<i<<endl; return 0; }
    }
    return 0;
}


Measured memory_bytes: 256
#ABC108 B
x1,y1,x2,y2 = map(int,input().split(' '))

#ベクトル(x,y)を反時計周りに90度回転したベクトルは(-y,x)
vec12 = [x2-x1,y2-y1]
vec23 = [-vec12[1], vec12[0]]
vec34 = [-vec23[1], vec23[0]]
x3 = x2 + vec23[0]
y3 = y2 + vec23[1]
x4 = x3 + vec34[0]
y4 = y3 + vec34[1]
print(x3,y3,x4,y4)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<cassert>
using namespace std;
int inf = 1000000000;

int main(void) {
  int dx[4] = {0, 0, 1, -1};
  int dy[4] = {1, -1, 0, 0};
  int w, h;
  while( cin >> w >> h ){
    if( w == 0 && h == 0 ) break;
    vector<string> s(2*h-1);
    cin.ignore();
    for(int i=0; i<s.size(); i++) getline(cin, s[i]);

    // for(int i=0; i<s.size(); i++) cerr << s[i] << endl;

    queue< pair<int, int> > q;
    q.push( make_pair(0, 0) );
    vector< vector<int> > cost(2*h-1, vector<int> (2*w-1, inf));
    cost[0][0] = 1;

    while( !q.empty() ){
      pair<int, int> p = q.front();
      q.pop();

      for(int dir=0; dir<4; dir++){
        int nx = p.second + dx[dir];
        int ny = p.first + dy[dir];

        if( nx < 0 || ny < 0 || nx >= 2*w-1 || ny >= 2*h-1 ) continue;
        if( s[ ny ][ nx ] == '1' ) continue;
        s[ny][nx] = '1';
        nx += dx[dir];
        ny += dy[dir];
        if( nx < 0 || ny < 0 || nx >= 2*w-1 || ny >= 2*h-1 ) continue;
        cost[ny][nx] = cost[p.first][p.second]+1;
        q.push( make_pair(ny, nx) );

      }
    }

    // for(int i=0; i<2*h-1; i++){
    //   for(int j=0; j<2*w-1; j++){
    //     cerr << cost[i][j] << " ";
    //   }
    //   cerr << endl;
    // }
    if( cost[2*h-2][2*w-2] == inf ) cout << 0 << endl;
    else cout << cost[2*h-2][2*w-2] << endl;

  }


  return 0;
}


// EOF

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

int main() {
  int N;
  cin >> N;
  vector<int>H(N);
  for (int i=0; i < N; i++) {
   cin >> H.at(i);//i番目の山の高さ
  }
  int f =1;//眺められる数（最西端は確定だから初期値は１
  int c =H.at(0);//最初は最西端が高さmax
  for(int i=1;i<N;i++){
    if(c<=H.at(i)){//i番目の山がmaxより高い場合
      f++;//眺＋１
      c = H.at(i);//max更新
    }
  }
    cout<< f << endl;
}
 

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

int main() {
    while (true) {
        double n;
        cin >> n;
        if (n < 0) {
            break;
        }
        double d_integer, decimal;
        decimal = modf(n, &d_integer);
        string ans = ".";
        bool canTranslate = true;
        int integer = (int) d_integer;
        for (int i = 0; i < 8; i++) {
            if (integer % 2 == 0) {
                ans.insert(0, 1, '0');
            } else {
                ans.insert(0, 1, '1');
            }
            integer /= 2;
        }
        if (integer > 0) {
            canTranslate = false;
        }
        for (int i = 0; i < 4; i++) {
            decimal *= 2;
            if (decimal >= 1) {
                ans += '1';
            } else {
                ans += '0';
            }
            decimal -= (int) decimal;
        }
        if (decimal > 0.0000001) {
            canTranslate = false;
        }
        if (canTranslate) {
            cout << ans << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

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

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

    if (n >= 30)
    {

        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

#define MAX_N 802

vector<int> G[MAX_N];
queue<int> que;

ll dp[301][301][301]={};
int n,m;
int main() {
	cin>>n>>m;
	memset(dp,-1,sizeof(dp));
	dp[1][0][0]=1;
	rep(i,n){
		rep(j,i+1) dp[i+1][j+1][j+1]=0;
	}
	rep(i,m){
		int l1,r1,x1;
		cin>>l1>>r1>>x1;
		rep(a1,r1){
			rep(a2,a1+1){
				if(x1==1){
					if(a1>=l1||a2>=l1)dp[r1][a1][a2]=0;
				}
				if(x1==2){
					if((a1>=l1&&a2>=l1)||(a1<l1&&a2<l1))dp[r1][a1][a2]=0;
				}
				if(x1==3){
					if(a2<l1||a1<l1)dp[r1][a1][a2]=0;
				}
			}
		}
	}

	REP(i,2,n+1){
		rep(j,i){
			rep(k,j+1){
				if(dp[i][j][k]==0)continue;
				dp[i][j][k]=0;
				if(j==i-1){
					rep(i2,j){
						if(i2<k)dp[i][j][k]+=dp[j][k][i2];
						if(i2>=k)dp[i][j][k]+=dp[j][i2][k];
						dp[i][j][k]%=i197;
					}
				}else{
					dp[i][j][k]=dp[i-1][j][k];
				}
			}
		}
	}

	ll t=dp[n][0][0]*3;
	rep(j,n){
		rep(k,j){
			t+=dp[n][j][k]*6;
			t%=i197;
		}
	}
	cout<<t<<endl;
	return 0;
}


Measured memory_bytes: 213376
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  if(a <= 8 && b <= 8){
    cout << "Yay!\n";
    return 0;
  }
  cout << ":(\n";
}
  
  
  

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

typedef struct _APPLE {
    int appetite;
    int type;
} APPLE;
typedef unsigned long long _ULL;

const int MAXN = 3e5+8;
APPLE nums[MAXN];

bool mycmp(const APPLE &x, const APPLE &y) {
    return x.appetite>y.appetite;
}

int main() {
    int x,y,a,b,c;
    scanf("%d%d%d%d%d", &x, &y, &a, &b, &c);

    for (int i=0; i<a; i++) {
        scanf("%d", &nums[i].appetite);
        nums[i].type = 0;//红苹果
    }
    for (int i=a; i<a+b; i++) {
        scanf("%d", &nums[i].appetite);
        nums[i].type = 1;//绿苹果
    }
    for (int i=a+b; i<a+b+c; i++) {
        scanf("%d", &nums[i].appetite);
        nums[i].type = 2;//无色苹果
    }

    std::sort(nums, nums+a+b+c, mycmp);

    _ULL ans = 0;
    _ULL cnt = 0;
    for (int i=0; i<a+b+c; i++) {
        if (0==nums[i].type) {
            if (x>0) {
                x--;
                ans += nums[i].appetite;
            }
        } else if (1==nums[i].type) {
            if (y>0) {
                y--;
                ans += nums[i].appetite;
            }
        } else if (2==nums[i].type) {
            cnt++;
            ans += nums[i].appetite;
        }
        if (x+y==cnt) {
            break;
        }
    }

    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 2560
N = int(input())
A = [i for i in input()]
B = [i for i in input()]
C = [i for i in input()]

countA = 0
countB = 0
countC = 0
countALL = 0

for i in range(N):
    if A[i] == B[i] and A[i] == C[i]:
        continue
    elif A[i] == B[i]:
        countC += 1
    elif B[i] == C[i]:
        countA += 1
    elif A[i] == C[i]:
        countB += 1
    else:
        countALL += 1


result = countA + countB + countC + int(countALL * 2)

print(result)


Measured memory_bytes: 3064
#include<stdio.h>
#define MAX 100005
#define NIL -1
 
typedef struct{
  int parent, left, right;
}Node;
 
Node Tree[MAX];
int Depth[MAX];
int degree[MAX];
int h;
 
void preOrder(int);
void inOrder(int);
void postOrder(int);
 
int main(void){
  int i, n, root;
  int vertex;
  int child[2];
 
 
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ) {
    Tree[i].parent = NIL;
    Tree[i].left = NIL;
    Tree[i].right = NIL;
  }
 
  for ( i = 0; i < n; i++ ){
    scanf("%d %d %d", &vertex, &child[0], &child[1]);
 
   
    if(child[0] == NIL && child[1] == NIL)
      degree[vertex] = 0;
 
    
    else if(child[0] == NIL && child[1] != NIL){
      degree[vertex] = 1;
      Tree[child[1]].parent = vertex;
      Tree[vertex].right = child[1];
    }
     
    else if(child[0] != NIL && child[1] == NIL){
      degree[vertex] = 1;
      Tree[child[0]].parent = vertex;
      Tree[vertex].left = child[0];
    }
 
 
   
    else{
      degree[vertex] = 2;
      Tree[child[0]].parent = vertex;
      Tree[child[1]].parent = vertex;
       
      Tree[vertex].left = child[0];
      Tree[vertex].right = child[1];
    }
  }

  for (i = 0; i < n; i++)
  {
    if (Tree[i].parent == NIL){
      root = i;
    }
  }

  printf("Preorder\n");
  preOrder(root);
  printf("\n");
 
  printf("Inorder\n");
  inOrder(root);
  printf("\n");
 
  printf("Postorder\n");
  postOrder(root);
  printf("\n");
 
  return 0;
}
 
void preOrder(int n) {
  if(n == NIL)return;
  printf(" %d", n);
  preOrder(Tree[n].left);
  preOrder(Tree[n].right);
}
 
void inOrder(int n) {
  if(n == NIL)return;
  inOrder(Tree[n].left);
  printf(" %d", n);
  inOrder(Tree[n].right);
}
 
void postOrder(int n) {
  if(n == NIL)return;
  postOrder(Tree[n].left);
  postOrder(Tree[n].right);
  printf(" %d", n);
}
 




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

// Function to return LCM of two numbers 
long long int findLCM(long long int a,long long int b) 
{ 
	long long int lar = max(a, b); 
	long long int small = min(a, b); 
	for (long long int i = lar; ; i += lar) { 
		if (i % small == 0) 
			return i; 
	} 
} 

// Driver program to test above function 
int main() 
{ 
	long long int a, b; 
  cin>>a>>b;
	cout <<findLCM(a,b); 
	return 0; 
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountll
#define m_p make_pair
#define infi 1e18+1
#define eps 0.000000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>//usage rand<long long>()
T rand() {
    return uniform_int_distribution<T>()(rng);
}
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
//////////////
auto clk=clock();
#define all(x) x.begin(),x.end()
#define S second
#define F first
#define sz(x) ((long long)x.size())
#define int long long  
#define f80 __float128
#define pii pair<int,int>
/////////////

signed main()
{
	fastio;
	#ifdef ANIKET_GOYAL
		freopen("inputf.in","r",stdin);
		freopen("outputf.in","w",stdout);
	#endif
	int n;
	cin>>n;
	int x=n;
	set<int> s;
	for(int i=2;i*i<=n;++i)
	{
		if(n%i==0)
		{
			int x=n;
			while(x>=i&&x%i==0)
				x=x/i;
			if(x%i==1)
				s.insert(i);
		}
	}
	if(n!=1)
	s.insert(n);
	n=x-1;
	for(int i=2;i*i<=n;++i)
	{
		if(n%i==0)
		{
			s.insert(i);
			s.insert(n/i);
		}
	}
	if(n!=1)
		s.insert(n);
	// for(auto r:s)
	// 	cout<<r<<"\n";
	cout<<s.size();
	#ifdef ANIKET_GOYAL
		cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
	#endif
}

Measured memory_bytes: 256
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
#include <list>
//AtCoderC++.cpp

using namespace std;


inline int ceileing(int a, int b) {
	return a % b == 0 ? a / b : a / b + 1;
}
int count_digit(int n) {
	auto count = 0;
	while (n > 0) {
		++count;
		n /= 10;
	}
	return count;
}

int main() {
	int A, B, C; cin >> A >> B >> C;
	if (A >= B + C) {
		cout << 0 << endl;
	} else {
		cout << C - (A - B) << endl;
	}
}


Measured memory_bytes: 256
<?php


$input = explode(" ", trim(fgets(STDIN)));

$N = $input[0];
$A = $input[1];
$B = $input[2];

$k = 0;

for ($i = 1; $i <= $N; ++$i) {
    $a = 0;
    if ($i >= 10) {
        $c = str_split($i);

        for ($x = 0; $x < count($c); ++$x) {
            $a += $c[$x];
        }
    } else {
        $a += $i;
    }

    if ($a >= $A && $a <= $B) {
        $k += $i;
    }
}

echo $k;

Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;


const LLI inf = 1LL << 50;

LLI dp[400][400];

int main(){
  int N,K;
  while(cin >> N >> K){
    vector<int> H(N); cin >> H;

    fill_array(dp, inf);

    dp[0][0] = 0;
    dp[0][1] = H[0];

    REP(i,N) dp[i][0] = 0;

    FOR(i,1,N){
      dp[i][1] = H[i];
      
      FORE(j,2,N){
        REP(l,i){
          chmin(dp[i][j], dp[l][j-1] + max(0, H[i]-H[l]));
        }
      }
    }
    /*
    REP(i,N){
      REPE(j,N){
        cerr << dp[i][j] << " ";
      }
      cerr << endl;
      }*/

    

    LLI ans = inf;

    REP(i,N){
      chmin(ans, dp[i][N-K]);
    }

    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X, Y, Z;
  cin >> X >> Y >> Z;
  cout << (X-Z) / (Y+Z) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();

char lose_sel(char sel)
{
    switch(sel){
        case 'r':
            return 's';
        case 's':
            return 'p';
        case 'p':
            return 'r';
        default:
            return '*';
    }
}
char win_sel(char sel)
{
    switch(sel){
        case 'r':
            return 'p';
        case 's':
            return 'r';
        case 'p':
            return 's';
        default:
            return '*';
    }
}
int main()
{
    int n, k ,r, s, p;
    string t;
    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> t;

    map<char, int> score_mp = {{'r', r}, {'p', p}, {'s', s}};
    int ans = 0;
    /* K個のグループに分割して計算 */
    for (int group_no = 0; group_no < k; group_no++){
        vector<char> g_str;
        for (int i = 0; i <= n / k; i++){
            if (t.length() <= (i * k) + group_no) break;
            g_str.push_back(t[(i*k) + group_no]);
        }
        char pre_sel = '*';
        for (int j = 0; j < g_str.size(); j++){
            /* g_str 勝手を返す関数 */
            char win_sel_can = win_sel(g_str[j]);
            if ( win_sel_can != pre_sel){
                pre_sel = win_sel_can;
                ans += score_mp[win_sel_can];
            }
            else
            {
                if ( j != g_str.size() - 1){
                    if ( win_sel(g_str[j + 1]) == g_str[j]){
                        pre_sel = lose_sel(g_str[j]);
                    }
                    else{
                        pre_sel = g_str[j];
                    }

                }
                else
                {
                    pre_sel = g_str[j];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>


using namespace std;

int main()
{


	int n, k, q;
	vector<int> a;

	cin >> n >> k >> q;


	int wk;
	for (int i = 0; i < q; i++) {
		cin >> wk;
		a.push_back(wk);
	}

	vector<int> anscount(n);
	for (int i = 0; i < anscount.size(); i++) {
		anscount[i] = 0;
	}

	int goalline = q - k + 1;

	for (int i = 0; i < a.size(); i++) {
		anscount[a[i] - 1]++;
	}


	string result;
	for (int i = 0; i < anscount.size(); i++) {
		if (anscount[i] >= goalline) {
			result = "Yes";
		}
		else {
			result = "No";
		}

		cout << result << endl;
	}
	





	return 0;
}



Measured memory_bytes: 1528
n = int(input())
w1 = input()
w2 = input()

def joint(x,y):
    tmp = n
    tmp_x = x
    tmp_y = y
    while tmp_x != tmp_y:
        tmp_x = tmp_x[1:]
        tmp_y =  tmp_y[0:-1]
        tmp -= 1
    joi_x = x[0:n-tmp]
    return(joi_x+y)

print(len(joint(w1,w2)))

Measured memory_bytes: 3064
#include <stdio.h>
#define MAX 500000

int H,X[MAX];

void MHeap(int i){
    int l,r,lrge,temp;
    
    l=2*i;
    r=2*i+1;
    
    if(l <= H && X[l] > X[i])
        lrge=l;
        
    else
        lrge=i;
        
    if(r <= H && X[r] > X[lrge])
        lrge=r;

    if(lrge != i){
        temp=X[i];
        X[i]=X[lrge];
        X[lrge]=temp;
        MHeap(lrge);
    }
}

int main(void){
    int i;
    
    
    scanf("%d",&H);
    
    for(i=1;i<=H;i++)
        scanf("%d",&X[i]);
        
    for(i=H/2;i>=1;i--)
        MHeap(i);
        
    for(i=1;i<=H;i++)
        printf(" %d",X[i]);
        
    puts("");
    return 0;
}



Measured memory_bytes: 3652
#include<iostream>
using namespace std;
int main() {
	while(1) {
		int a, c; char b;
		cin>>a>>b>>c;

		if(b=='?') break;
		
		if(b=='+') cout<<a+c<<endl;
		if(b=='-') cout<<a-c<<endl;
		if(b=='*') cout<<a*c<<endl;
		if(b=='/') cout<<a/c<<endl;

	}
	return 0;
}


Measured memory_bytes: 3100
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
bool f(LL a)
{
    int s=0;
    while(a)
    {
        s++;
        a=a/10;
    }
    if(s%2) return true;
    else return false;
}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    while(cin>>n)
    {
        c=0;
        Rep(i,n)
        {
            if(f(i)) c++;
        }
        cout<<c<<en;
    }
}



Measured memory_bytes: 256