akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
#include<fstream>
#include<cstring>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define P pair<int,int>
#define ll __int64
//#define ll long long 
int n,k;
int a[2000],b[2000];
vector<int>v[2000];
int  dp[2001][2001];
vector<int>type;
P t[2000];
bool used[200];
int num;
const int INF=-1;
int main(){
cin>>n>>k;
rep(i,n){
	cin>>a[i]>>b[i];
	used[b[i]]=1;	
	t[i]=mp(b[i],a[i]);
}
sort(t,t+n,greater<P>());
for(int i=0;i<=20;i++)if(used[i])num++;

int cnt=0,now=t[0].first;

type.push_back(now);
rep(i,n){
	if(now!=t[i].first){

		cnt=1;
		now=t[i].first;
		type.push_back(now);
		v[now].push_back(t[i].second);//v[i]=t[i].second;
	}
	else{
		cnt++;
		if(cnt>=2)v[now].push_back(t[i].second+(cnt*(cnt-1))-((cnt-1)*(cnt-2)));//v[i]=t[i].second+cnt*(cnt-1)-((cnt-1)*(cnt-2));
		else v[now].push_back(t[i].second);//v[i]=t[i].second;
		
	}
}



rep(i,n+1)rep(j,n+1)dp[i][j]=INF;
dp[0][0]=0;
for(int i=0;i<num;i++){
	for(int j=0;j<n;j++){

		if(dp[i][j]!=INF){
			int sum=0;
			dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
			for(int k=0;k<v[type[i]].size();k++){
				//if(j+k>n)break;
				sum+=v[type[i]][k];
				dp[i+1][j+k+1]=max(dp[i+1][j+k+1],dp[i][j]+sum);
			}
		}	
	}
}

/*
rep(i,n+1){
	rep(j,n+1)cout<<dp[i][j]<<" ";
	cout<<endl;
}
*/
int ans=0;
rep(i,n+1)ans=max(ans,dp[i][k]);
cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 18868
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


s = input()
t = input()
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
# print(dp[len(s)][len(t)])
ans = []
x = len(s)
y = len(t)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        ans.append(s[x])
print(''.join(ans[::-1]))


Measured memory_bytes: 125528
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: i32 = read().unwrap();
    let mut map: HashMap<(i32, i32), i32> = HashMap::new();

    for k in 1..n + 1 {
        let num_str = k.to_string();
        let i: i32 = num_str[0..1].parse().unwrap();
        let j: i32 = num_str[num_str.len() - 1..].parse().unwrap();
        let count = map.entry((i, j)).or_insert(0);
        *count += 1;
    }

    let mut total = 0;
    for i in 0..10 {
        for j in 0..10 {
            let pro = map.get(&(i, j)).unwrap_or(&0) * map.get(&(j, i)).unwrap_or(&0);
            total += pro;
            // println!("({}, {}) {}", i, j, total);
        }
    }
    println!("{}", total);
}

Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
string str,ans="",ans2="";
map < string,int > tab;
int main(){
  while(cin>>str){
    if(str.size()>ans2.size())ans2=str;
    tab[str]++;
    if(tab[ans]<tab[str])ans=str;
  }
  cout<<ans<<' '<<ans2<<endl;
  return 0;
}


Measured memory_bytes: 3128
'use strict';
function Main(input) {
    input = input.split("\n");
    let tmp = input[0].split(" ");
    const H = parseInt(tmp[0]);
    const W = parseInt(tmp[1]);
    tmp = input[1].split(" ");
    const h = parseInt(tmp[0]);
    const w = parseInt(tmp[1]);

    console.log((H - h) * (W - w));

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef priority_queue<double, vector<double>, less<double> > QUE_double;
typedef priority_queue<int, vector<int>, less<int> > QUE_int;//lessは大きい順にならべるよ
const int MAX = pow(10, 5)+1;//+1しないとREになる(out of rangeになるんかな?? )

ll gcd(ll a, ll b){//greatest common divider 最大公約数を求める
  if(b==0) return a;
  return gcd(b, a%b);
}

int main(){
  ll N;
  cin >> N;
  vector<int> a(N);
  bool is_one = false;//aの中に1がない場合をfalse
  for(int i=0; i<N; i++){
    cin >> a.at(i);
    if(a.at(i) == 1) is_one = true;
  }
  
  int ans = -1;
  if(is_one == false){
    cout << ans << endl;
    return 0;
  }
  
  
  int forcus_num = 1;
  for(int i=0; i<N; i++){
    if(a.at(i) == forcus_num) forcus_num++;
  }
  
  ans = N-forcus_num + 1;
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <atcoder/lazysegtree>
#include <iostream>
#include <vector>
using ll = long long;
#define rep(i, j, n) for (int i = j; i < (n); ++i)
using namespace std;

constexpr ll mod = 998244353;

// a <- a * b + c
// a1' + a2' <- (a1 + a2) * b + c + c
// 要素は左の値、右の値の和とcを足す数、つまり要素数を持てばよい
struct X {
  ll sum;
  ll size;
};
struct M {
  ll b, c;
};

X op(X left, X right) {
  return X{(left.sum + right.sum) % mod, (left.size + right.size) % mod};
}
X e() { return X{0, 0}; }

// 要素への作用: 和にbをかけて要素数にcをかける
X mapping(M right, X left) {
  return X{(right.b * left.sum + right.c * left.size) % mod, left.size};
}
// 作用かけたものに作用かけると
// (a * b1 + c1) * b2 + c2
// a * b1 * b2 + c1 * b2 + c2
M composition(M right, M left) {
  return M{right.b * left.b % mod, (left.c * right.b + right.c) % mod};
}
M id() { return M{1, 0}; }

int main() {
  int n, q, t, l, r, b, c;
  cin >> n >> q;
  vector<X> a(n);
  rep(i, 0, n) {
    cin >> t;
    a[i] = X{t, 1};
  }
  atcoder::lazy_segtree<X, op, e, M, mapping, composition, id> st(a);
  rep(i, 0, q) {
    cin >> t >> l >> r;
    if (t)
      cout << st.prod(l, r).sum << '\n';
    else {
      cin >> b >> c;
      st.apply(l, r, M{b, c});
    }
  }
  return 0;
}

Measured memory_bytes: 35384
function main(arg) {
	arg = arg.trim().split(/\n/);
  	var a = parseInt(arg[0].split(' ')[0]), b = parseInt(arg[0].split(' ')[1]),
        aa = '', bb = '', out;
  	for (var i = 0; i < b; i++) {
    	aa += a;
    }
  	for (var i = 0; i < a; i++) {
    	bb += b;
    }
	out = [aa, bb].sort();
  	console.log(out[0]);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(i) begin(i), end(i)

const int INF = 0x3fffffff;
const ll MINF = 0x7fffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const int MOD = 1000000007;
const int MODD = 998244353;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932;

template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }

ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll pow_mod(ll n,ll k,ll m){ll r = 1;for(; k > 0;k >>= 1) {if (k & 1) r = (r * n) % m; n = (n * n) % m;}return r;}

//ここから。
int main(){
    int n,x,t;
    cin >> n >> x >> t;
    int ans = n / x * t;
    if(n % x != 0) ans += t;
    cout << ans << endl;
}

Measured memory_bytes: 3596
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))


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

using namespace std;
const long long INF = 1e18L + 5;

void rec(vector<long long> &dp, vector<int>& not_taken, int idx, int mask, int group, const long long &score_so_far, const vector<long long> &score_group)
{
	if (idx == not_taken.size())
	{
		dp[mask] = max(dp[mask], score_so_far + score_group[group]);
		return;
	}
	rec(dp, not_taken, idx + 1, mask, group, score_so_far, score_group);
	rec(dp, not_taken, idx + 1, mask ^ (1 << not_taken[idx]), group ^ (1 << not_taken[idx]), score_so_far, score_group);
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;

	vector<vector<int>> compatibility(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> compatibility[i][j];
		}
	}

	vector<long long> score_group(1 << n);
	for (int mask = 0; mask < (1 << n); mask++)
	{
		long long score = 0;
		for (int i = 0; i < n; i++)
		{
			if ((1 << i) & mask)
			{
				for (int j = i + 1; j < n; j++)
				{
					if ((1 << j) & mask)
					{
						score += compatibility[i][j];
					}
				}
			}
		}
		score_group[mask] = score;
	}

	vector<long long> dp(1 << n, -INF);
	dp[0] = 0;
	for (int mask = 0; mask < (1 << n); mask++)
	{
		vector<int> not_taken;
		for (int i = 0; i < n; i++)
		{
			if (!((1 << i) & mask))
				not_taken.push_back(i);
		}
		rec(dp, not_taken, 0, mask, 0, dp[mask], score_group);
	}
	cout << dp[(1 << n) - 1] << "\n";
}



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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;

int main() {
  int r;
  cin >> r;
  cout << 3*r*r;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  ll n, ans = 0, r = 0, w = 0, red = -1;
  cin >> n;
  vector<char> c(n);
  deque<ll> dq;
  rep(i, n) {
    cin >> c[i];
    if (c[i] == 'R') dq.push_back(i);
  }

  rep(i, n) {
    if (dq.size() == 0) break;
    red = dq.back();
    if (c[i] == 'W')
      swap(c[i], c[red]), ans++, dq.pop_back();
    else
      dq.pop_front();
  }

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


Measured memory_bytes: 5036
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<int,P> PP;

vector<PP> v;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main()
{
	int n;
	double ans = 0;
	cin >> n;
	rep(i,n){
		double a;
		cin >> a;
		ans += 1 / a;
	}
	printf("%.10lf\n",1 / ans);
	
	return 0;
}


Measured memory_bytes: 256
import java.math.*;
import java.text.*;
import java.lang.*;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
//		in.useDelimiter("//n");
		while(in.hasNext()){
			String line = in.nextLine();
			System.out.println(line.toUpperCase());
		}
	}

}

Measured memory_bytes: 11000
#include<iostream>
#include<vector>
int N;
std::vector<int> res,six,ans;
int main(){
    std::cin>>N;
    if(N==3){
        std::cout<<"2 3 25"<<std::endl;
        return 0;
    }
    res.push_back(3);
    res.push_back(9);
    for(int i=2;i+2<=30000;i+=6){
        res.push_back(i);
        res.push_back(i+2);
    }
    for(int i=15;i+6<=30000;i+=12){
        res.push_back(i);
        res.push_back(i+6);
    }
    for(int i=6;i<=30000;i+=6){
        six.push_back(i);
    }
    int count=0;
    while(count+2<=N&&count+2<=15000){
        ans.push_back(res[count]);
        ans.push_back(res[count+1]);
        count+=2;
    }
    for(int i=0;i+count+1<=N;i++){
        ans.push_back(six[i]);
    }
    for(int i=0;i<N;i++){
        std::cout<<ans[i];
        if(i!=N-1)std::cout<<" ";
        else std::cout<<std::endl;
    }
    return 0;
}


Measured memory_bytes: 640
//筛法也快不到哪里去啊
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
bool prime(int cur)
{
    if(cur==1||cur==0)return false;
    for(int i=2;i<=sqrt(cur);i++)
    {
        if(cur%i==0)
        {
            return false;
        }
    }
    return true;
}
int cnt[1000005];
int main()
{
    for(int i=1;i<=1000005;i++)
    {
        if(prime(i))cnt[i]=cnt[i-1]+1;
        else cnt[i]=cnt[i-1];
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        cout<<cnt[n]<<endl;
    }
    return 0;
}


Measured memory_bytes: 7032
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>
#include <functional>
#include <cmath>
#include <set>
#include <map>


//マクロ
/*動かない・・・
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _roverload3(_1,_2,_3,name,...) name
#define _rrep(i,n) repi(i,0,n)
#define rrepi(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(...) _roverload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
//*/
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
//*/
#define All(a) (a).begin(),(a).end()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define INFL 1e18
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
//*/
using namespace std;
using Graph = vector<vector<int>>;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数
double l, l1,l2,l3;

//使用する関数
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 (a > b) { a = b; return 1; }
	return 0;
}



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

	cin >> l;
	l1 = l / 3;
	l2 = l / 3;
	l3 = l - l1 -l2;

	printf("%.10lf\n", l1 * l2 * l3);
}

Measured memory_bytes: 256
unittest
{
	assert( [ "3", "1 10 100" ].parse.expand.solve == "Yes" );
	assert( [ "4", "1 2 3 4" ].parse.expand.solve == "No" );
	assert( [ "3", "1 4 1" ].parse.expand.solve == "Yes" );
	assert( [ "2", "1 1" ].parse.expand.solve == "No" );
	assert( [ "6", "2 7 1 8 2 8" ].parse.expand.solve == "Yes" );
	
	assert( [ "6", "2 2 7 8 1 8 1" ].parse.expand.solve == "No" );		// 追加ケース
	assert( [ "6", "2 2" ].parse.expand.solve == "Yes" );		// 追加ケース
	assert( [ "6", "2 2 2" ].parse.expand.solve == "Yes" );		// 追加ケース
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.strip.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( as );
}

auto solve( long[] as )
{
	// 4の倍数があれば、4の倍数を4の倍数以外で挟めば条件を満たせる
	auto q = as.count!( ( a ) => a % 4 == 0 );
	auto qq = ( ( 0 < q ) ? 1 : 0 ) + q * 2;		// 4の倍数を使って条件を満たせる要素数
	if( as.length <= qq ) return "Yes";
	
	// 2の倍数があれば、2の倍数同士を並べれば条件を満たせる（ただし4の倍数の隣に置く必要がある）
	auto d = as.count!( ( a ) => ( a % 4 != 0 ) && ( a % 2 == 0 ) );
	auto dd = q * 2 + d;		// 4の倍数と2の倍数を使って条件を満たせる要素数
	if( as.length <= dd ) return "Yes";
	
	return "No";
}


Measured memory_bytes: 7092
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
       
        if( a.equals( "ABC" ) ){
            System.out.println("ARC");
        }else{
            System.out.println("ABC");
            }
    }
}


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

using namespace std;

#define int long long
#define double long double 
const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;


typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef unordered_map<int,int> mii;
typedef unordered_map<char,int> mci;
typedef unordered_map<string,int> msi;

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

void solve() {
    int n,k,ans; cin>>n>>k;
    vi A(n),pre(k+1);
    for(int i=0;i<n;i++) cin>>A[i];
   
    vvi dp(n+1,vi(k+1));
    for(int i=0;i<=n;i++) {
        dp[i][0] = 1;
    }
    for(int i=1;i<=k;i++) {
        dp[0][i] = 0;
    }
    for(int i=1;i<=n;i++) {
        pre[0] = dp[i-1][0];
        for(int j=1;j<=k;j++) {
            pre[j] = (pre[j-1] + dp[i-1][j])%MOD; 
        }
        for(int j=1;j<=k;j++) {
            dp[i][j] = pre[j];
            if(A[i-1]<j) {
                dp[i][j] = (dp[i][j] - pre[j-A[i-1]-1] + MOD)%MOD;
            }
            dp[i][j] %= MOD;
        }
    }
    cout<<dp[n][k]<<endl;
}

int32_t main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);
    //#ifdef LOCAL
       // freopen("input.txt", "r", stdin);
       // freopen("output.txt", "w", stdout);
    //#endif

    int tc; tc=1;
    for (int t = 1; t <= tc; t++) {
        //cout << "Case #" << t  << ": ";
        solve();
    }
}

Measured memory_bytes: 83904
// inputに入力データ全体が入る
function Main(input) {
	ans = [];
	for(var i=0;i<input.length;i++){
		if(input[i] == 'B') ans.pop();
		else ans.push(input[i]);
	}
	console.log(ans.join(''));
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N = 1e6 + 5;
typedef long long ll;
using namespace std; 

int n, m, d[N], p[N], f[N], Q; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

ll mabs(ll x) { return x < 0 ? -x : x; }

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	n = read <int> (), m = read <int> ();
	for(int i = 1; i <= n; i++) d[i] = read <int> ();
	p[0] = m;
	for(int i = 1; i <= n; i++)
	{
		if(d[i] < 2 * p[i - 1]) p[i] = mabs(p[i - 1] - d[i]);
		else p[i] = p[i - 1]; 
	}
	f[n + 1] = 1;
	for(int i = n; i >= 1; i--)
		f[i] = (d[i] < 2 * f[i + 1] ? (f[i + 1] + d[i]) : f[i + 1]);
	Q = read <int> ();
	for(int x, i = 1; i <= Q; i++)
	{
		x = read <int> ();
		if(f[x + 1] > p[x - 1]) puts("NO");
		else puts("YES"); 
	}
	return 0; 
}


Measured memory_bytes: 8864
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, a[N], b[N], cnt[N], par[N], ans, sz[N];
vi num, G[N], GG[N];
bool mark[N];

int getpar(int v){
	return (par[v] == v?v:par[v] = getpar(par[v]));
}

void merge(int v, int u){
	v = getpar(v), u = getpar(u);
	if (v == u) return;
	if (sz[v] < sz[u]) swap(v, u);
	ans --;
	par[u] = v;
	sz[v] += sz[u];
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int X = 0;
	cin >> n;
	for (int i = 1; i < N; i++) par[i] = i, sz[i] = 1;
	for (int i = 1; i <= n; i++){
		cin >>a[i];
		X ^= a[i];
		num.pb(a[i]);
	}
	a[n + 1] = X;
	num.pb(X);
	for (int i = 1; i <= n; i++){
		cin >> b[i];
		num.pb(b[i]);
	}
	sort(all(num));
	num.resize(unique(all(num)) - num.begin());
	for (int i = 1; i <= n + 1; i++){
		a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
		cnt[a[i]]++;
	}
	for (int i = 1; i <= n; i++){
		b[i] = lower_bound(all(num), b[i]) - num.begin() + 1;
		if (cnt[b[i]] == 0) return cout << -1, 0;
		cnt[b[i]]--;
	}	
	for (int i = 0; i <N; i++){
		if (cnt[i] == 1){
			X = i;
			break;
		}
	}
//	cout << X << '\n';
	memset(cnt, 0, sizeof cnt);
	for (int i = 1; i <= n; i++){
		if (a[i] == b[i]) continue;
		ans ++;
		cnt[a[i]]++;
		G[b[i]].pb(i);
	}
	G[b[n + 1]].pb(n + 1);
	if (ans == 0) return cout << 0, 0;
	ans ++;
	ans *= 2;
	ans -= 2;
//	cout << ans << '\n';
	for (int i = 1; i <= n; i++){
		if (a[i] == b[i]) continue;
		GG[a[i]].pb(i);
	}
	GG[a[n + 1]].pb(n + 1);
	for (int i = 1; i <= n; i++){
		if (a[i] == b[i]) continue;
		if (!mark[a[i]]){
			mark[a[i]] = 1;
			for (auto u:G[a[i]]){
				merge(i, u);
			}
			for (auto u:GG[a[i]]) merge(i, u);
		}
	}
	if (!mark[a[n + 1]]){
		for (auto u:G[a[n + 1]]){
			merge(n + 1, u);
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 22872
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		Array.Sort(A);
		Array.Reverse(A);
		
		int l = 0, r = N;
		if(!isEssential(0)){
			Console.WriteLine(N);
			return;
		}
		
		while(r - l > 1){
			int c = (l + r) / 2;
			if(isEssential(c)){
				l = c;
			} else {
				r = c;
			}
		}
		
		Console.WriteLine(N - (l + 1));
	}
	
	bool isEssential(int t){
		
		bool[] reach = new bool[K];
		reach[0] = true;
		for(int i=0;i<N;i++){
			if(i == t) continue;
			for(int j=K-1;j>=0;j--){
				if(!reach[j]) continue;
				if(j + A[i] < K) reach[j + A[i]] = true;
			}
		}
		
		bool chk = false;
		for(int i=K-1;i>= Math.Max(0, K - A[t]);i--) chk |= reach[i];
		
		return chk;
		
	}
	
	int N;
	int K;
	long[] A;
	public Sol(){
		var d = ria();
		N = d[0]; K = d[1];
		A = rla();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 13408
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector<ll>
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define pii pair<ll,ll>
#define vii vector<pii>
#define MOD 1000000007LL
#define calc_fact(n) tgamma(n+1)

ll exEuclid(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1;y=0;
        return a;
    }
    ll x1,y1,g;
    g=exEuclid(b,a%b,x1,y1);
    
    x=y1;
    y=x1 - y1*(a/b);
    return g;
}

ll value(ll hor,ll vert,vi& fact)
{
    ll x,y,g,denm,num,inv;
    denm=(fact[hor]*fact[vert])%MOD;
    num=fact[hor+vert];
    g=exEuclid(denm,MOD,x,y);
    inv=(x%MOD+MOD)%MOD;
    
    return (inv*num)%MOD;
}

signed main()
{
    FIO;
    ll n,m,a,b;
    cin>>n>>m>>a>>b;
    vi fact(n+m+1,1);
    for(ll i=1;i<=n+m;i++)
    fact[i]=(i*fact[i-1])%MOD;
    
    ll ans=0;
    
    for(ll i=1;i<=n-a;i++)
    {
        ans=(ans+(value(b-1,i-1,fact)*value(m-b-1,n-i,fact))%MOD)%MOD;
    }
    cout<<ans;
}

Measured memory_bytes: 4744
<?php

$n = trim(fgets(STDIN));
$v = explode(' ', trim(fgets(STDIN)));
sort($v);

for($i=0; $i<$n-1; $i++){  
  if ($i==0) {
    $a = ($v[$i]+$v[$i+1])/2;
  } else {
    $a = ($a+$v[$i+1])/2;
  }  
}
echo $a;
  
?>

Measured memory_bytes: 4604
//int a = stoi(c); 文字列をintへ
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
//チェックリストはマップを使う
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//またはかかつか
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//数が大きい時のせぐふぉはコードテストで試してみる
//スペルミスに注意
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

//円周率
const double PI = 3.14159265358979323846;
//割るやつ
const ll M = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}


//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1)) % M;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

int main() {
	ll N, K; cin >> N >> K;
	vector<ll> H(N); rep(i, N)cin >> H[i];

	sort(ALL(H));

	ll ans;
	if (N <= K) {
		cout << 0 << endl;
		return 0;
	}
	else {
		ans = 0;
		for (int i = 0; i <= N - K - 1; i++) {
			ans += H[i];
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 9600
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)

	S, T := getString(), getString()
	ms := make(map[byte]byte)
	mt := make(map[byte]byte)

	ans := "Yes"
	for i := 0; i < len(S); i++ {
		s := S[i]
		t := T[i]
		v, ok := ms[s]
		if ok == false {
			ms[s] = t
		} else if v != t {
			ans = "No"
			break
		}
		v, ok = mt[t]
		if ok == false {
			mt[t] = s
		} else if v != s {
			ans = "No"
			break
		}
	}
	out(ans)
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,d,i;

int main(){
	cin>>n;
	string s;
	
	for(i=1;i<=n;i++){
		cin>>s;
		
		if(s=="AC") a++;
		if(s=="WA") b++;
		if(s=="TLE") c++;
		if(s=="RE") d++;
	}
	
	cout<<"AC x "<<a<<endl;
	cout<<"WA x "<<b<<endl;
	cout<<"TLE x "<<c<<endl;
	cout<<"RE x "<<d;
	
	return 0;
}

Measured memory_bytes: 3628
#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;
	set<int> mochi;
	rep(i, n){
		int d;
		cin >> d;
		mochi.insert(d);
	}
	cout << mochi.size() << endl;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
A = input().split()
A = [int(x)-1 for x in A]

if K >= 2*N:
    point = 0
    L = [0 for _ in range(N)]
    loop = []
    for i in range(N+1):
        L[point] +=1
        T = 1
        if L[point] == 2:
            loop.append(point)
            p = point
            for j in range(N+1):
                point = A[point]
                if point != p:
                    loop.append(point)
                else:
                    T = 0
                    break
        if T == 1:
            point = A[point]
        else:
            break
    c = 0
    p = 0
    for i in range(N):
        if p != loop[0]:
            c+=1
            p = A[p]
        else:
            break
    J = K-c
    n = len(loop)
    k = J%n
    print(loop[k]+1)
else:
    point = 0
    for i in range(K):
        point = A[point]
    print(point+1)

Measured memory_bytes: 32116
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define f first
#define s second

using namespace std;
typedef long long ll;

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

	string s;
	cin >> s;
	if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R'){
		cout << "3\n";
	}else if((s[0] == 'R' || s[2] == 'R') && s[1] == 'R'){
		cout << "2\n";
	}else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R'){
		cout << "1\n";
	}else{
		cout << "0\n";
	}
	
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 1e5+17;
LL a[MAXN];
int main(int argc ,char const *argv[])
{
    #ifdef noob
    freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
    	cin>>a[i];
    }
    sort(a, a+n);
    LL nc=1,ng=a[0];
    for (int i = 1; i < n; ++i)
    {
    	if(ng*2>=a[i])
    		nc++;
    	else
    		nc=1;
    	ng+=a[i];
    	// debug(nc);
    }
    cout<<nc<<endl;
    return 0;        
}

Measured memory_bytes: 1024
A=int(input())
B=int(input())
C=int(input())
X=int(input())
counti = 0

for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if 500*a + 100*b + 50*c == X:
        counti += 1

print(counti)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>

#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}

template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    string s;
    cin >> s;
    sort(s.begin(), s.end());

    if(s[0] == s[1] && s[2] == s[3] && s[1] != s[2]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
} /*atcoder*/



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

#define int long long

set<int>a;
int n, x;
string resp;

int32_t main()
{
	cin >> n;

	for(int i=0; i<n; i++)
	{
		cin >> x;
		a.insert(x); 
	}

	//cout << a.size() << '\n';
	if(a.size()==n)
		cout << "YES\n";
	else
		cout << "NO\n";
}

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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)

int main()
{
  ll k;
  string s;
  cin >> s >> k;
  forll(i, 0, min((ll)s.size(), k)){
	if (s[i] != '1'){
	  cout << s[i] << endl;
	  return 0;
	}
  }
  cout << 1 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000

int A[MAX],n;

int partition(int p, int r){
  int x,i,j,t;
  x = A[r];
  i = p - 1;
  for(j = p; j < r; j++){
    if(A[j] <= x){
      i++;
      t = A[i]; A[i]=A[j]; A[j] = t;
    }
  }
  t = A[i + 1]; A[i + 1] = A[r]; A[r] = t;
  return i + 1;
}

int main(){
  int i,q;

  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d",&A[i]);

  q = partition(0,n-1);

  for(i = 0; i < n; i++){
    if(i) printf(" ");
    if(i == q) printf("[");
    printf("%d",A[i]);
    if(i == q) printf("]");
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 2132
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];

  sort(a.begin(),a.end());
  
  vector<Int> sum(n+1,0);
  for(Int i=0;i<n;i++) sum[i+1]=sum[i]+a[i];

  vector<Int> dp(n);
  for(Int i=n-1;i>=0;i--){
    dp[i]=i;
    Int k=--upper_bound(a.begin(),a.end(),sum[i+1]*2)-a.begin();
    //cout<<i<<" "<<sum[i+1]<<" "<<a[k]<<endl;
    assert(i<=k);
    dp[i]=dp[k];
  }

  Int ans=0;
  for(Int i=0;i<n;i++)
    if(dp[i]==n-1) ans++;

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


Measured memory_bytes: 2684
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
	int N, K, Q;
	cin >> N >> K >> Q;
	int a[2002], sa[2002];
	for(int i = 0; i < N; i++){
		cin >> a[i];
		sa[i] = a[i];
	}
	sort(sa, sa + N);
	int ans = INF;
	for(int l = 0; l < N - Q + 1; l++){
		int r = Q + l;
		int safelen = 0, ct = 0, canremovect = 0;
		for(int i = 0; i < N; i++){
			if(a[i] < sa[l]){
        if(safelen >= K) ct += min(safelen - K + 1, canremovect);
        canremovect = 0;
        safelen = 0;
      }
      else if(a[i] > sa[r-1]) safelen++;
			else{
				safelen++;
        canremovect++;
			}
		}
    if(safelen >= K) ct += min(safelen - K + 1, canremovect);
		if(ct >= Q) ans = min(ans, sa[r - 1] - sa[l]);
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5;
int s[N];

int main()
{
	//freopen("1.in","r",stdin);
	int n;cin>>n;
	rep(i,1,n)s[i]=s[i/10]+i%10;
	int ans=s[1]+s[n-1];
	rep(i,1,n-1)ans=min(ans,s[i]+s[n-i]);
	cout<<ans;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int r,c,n,m,fl,st[N],tp;
struct node{int p,id;bool friend operator <(node a,node b){return a.p<b.p;}}a[N];
bool chk(int x,int y){return !x||x==r||!y||y==c;}
int id(int x,int y){
    int z=0;
    if(!x)z=y;
    else if(y==c)z=x+c;
    else if(x==r)z=r+2*c-y;
    else z=2*c+2*r-x;
    return z;
}
int main(){
    scanf("%d%d%d",&r,&c,&n);
    for(int i=1,x1,y1,x2,y2,k=0;i<=n;i++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(chk(x1,y1)&&chk(x2,y2)){
            int l=id(x1,y1),r=id(x2,y2);
            if(l>r)swap(l,r);
            a[++m]=node{l,++k};
            a[++m]=node{r,-k};
        }
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)
        if(a[i].id>0)st[++tp]=a[i].id;
        else fl|=st[tp]!=-a[i].id,tp--;
    puts(fl?"NO":"YES");
    return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <climits>
#define INF INT_MAX>>1 
#define W_MAX 35
#define H_MAX 65

using namespace std;

typedef long long ll;

int w, h;
char cliff[H_MAX][W_MAX];
int dp[H_MAX][W_MAX][2];
int dx[9] = {1, 1, 1, 1, 1, 2, 2, 2, 3};
int dy[9] = {2, 1, 0,-1,-2, 1, 0,-1, 0};

bool check(int i, int j){
	if(i<0 || h<=i || j<0 || w<=j) return false;
	if(cliff[i][j] == 'X')return false;
	return true;
}

int main(){
	while(1){
		cin >> w >> h;
		if(!w && !h)break;
		queue<tuple<int, int, int, int> > que;
		fill(dp[0][0], dp[H_MAX][0], INF);
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				cin >> cliff[i][j];
				if(cliff[i][j] == 'S'){
					dp[i][j][0] = dp[i][j][1] = 0;
					que.push(make_tuple(i, j, 0, 0));
					que.push(make_tuple(i, j, 1, 0));
					cliff[i][j] = '0';
				}
			}
		}

		while(!que.empty()){
			tuple<int, int, int, int> t = que.front(); que.pop();
			int y = get<0>(t);
			int x = get<1>(t);
			int lr = get<2>(t);
			int m = get<3>(t);
			//if(dp[y][x][lr] != m)continue;
			for(int k=0; k<9; k++){
				int i, j;
				if(lr == 0){
					i = y + dy[k];
					j = x + dx[k];
				} else{
					i = y - dy[k];
					j = x - dx[k];
				}
				if(check(i, j) == false)continue;
				if(dp[i][j][(lr+1)%2] > m + (cliff[y][x] - '0')){
					dp[i][j][(lr+1)%2] = m + (cliff[y][x] - '0');
					if(cliff[i][j] != 'T'){
						que.push(make_tuple(i, j, (lr+1)%2, dp[i][j][(lr+1)%2]));
					}
				}
			}
		}

		int ans = INF;
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				for(int k=0; k<2; k++){
					if(cliff[i][j] == 'T') ans = min(ans, dp[i][j][k]);
				}
			}
		}

		if(ans == INF) cout << "-1" << endl;
		else cout << ans << endl;
	}
	return 0;
}


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

void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	unsyncIO();
	if(s.size()){
		setIn(s + ".in");
		setOut(s + ".out");
	}
}


#define ll long long
const ll mod = 1e9 + 7;
const int MX = 5005;

int main(){
	setIO();
	int n;
	cin >> n;
	vector<ll> v(n), suff(n + 1, 0ll);
	for(int i =0 ; i < n; i ++) cin >> v[i];
	for(int i = n- 1; i >= 0; i --)
		suff[i] = (suff[i + 1] + v[i]) % mod;

	ll ans = 0ll;
	for(int i = 0; i < n; i ++)
		ans = (ans + (suff[i + 1] * 1ll * v[i] ) % mod) % mod;
	cout << ans << endl;
}

Measured memory_bytes: 6348
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
u = [0]*4
for i in range(n):
    s = input()
    if s == "AC":
        u[0] += 1
    if s == "WA":
        u[1] += 1
    if s == "TLE":
        u[2] += 1
    if s == "RE":
        u[3] += 1
print("AC", "x", u[0])
print("WA", "x", u[1])
print("TLE", "x", u[2])
print("RE", "x", u[3])






Measured memory_bytes: 9216
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
  int n;
  cin >> n;
  int a[n];
  REP(i, n) cin >> a[i];
  int l[n + 2], r[n + 2];
  l[0] = 0;
  r[n] = 0;
  REP(i, n) l[i + 1] = gcd(l[i], a[i]);
  RREP(i, n + 1) r[i - 1] = gcd(r[i], a[i - 1]);
  int ans = 0;
  REP(i, n) { ans = max(ans, gcd(l[i], r[i + 1])); }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include<iostream>

using namespace std;

int main() {
	
	int bT, aT, hC, iC, E;
	int sum = 0;
	
	while( cin >> bT >> aT >> hC >> iC >> E ) {
		
	int sum = 0;
	if( bT < 0){
		
	sum += (-bT * hC);
	sum += iC;
	bT = 0;
}
	if( bT >= 0){
		
	sum += ( aT - bT ) * E;
}
	cout << sum << "\n";
}
	return 0;
}


Measured memory_bytes: 3032
import Control.Applicative
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

readi b | Just (n, _) <- B.readInt b = n

f xs = (head xs, length xs)

g _  [] = True
g [] _  = False
g ((da, db):ds) ((ta, tb):ts)
    | da < ta   = g ds ((ta, tb):ts)
    | da > ta   = False
    | db >= tb  = g ds ts
    | otherwise = False

main = do
    n <- readLn :: IO Int
    ds <- fmap f . group . sort . fmap readi . B.words <$> B.getLine
    m <- readLn :: IO Int
    ts <- fmap f . group . sort . fmap readi . B.words <$> B.getLine
    if g ds ts
        then putStrLn "YES"
        else putStrLn "NO"

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





int main() {
  int x,a,b;
  cin>>x>>a>>b;
  if (b-a<=0){
    cout<<"delicious"<<endl;
  }
  else if (0<b-a and b-a<=x){
    cout<<"safe"<<endl;
  }
  else {
    cout<<"dangerous"<<endl;
  }
  
  
    
  
  
}













Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
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; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n;
    cin >> n;
    string s="No";
    FOR(i,1,10){
        FOR(j,1,10){
            if(i*j==n)s="Yes";
        }
    }
    cout << s;

    return 0;
}

Measured memory_bytes: 3580
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
        int room[4][3][10];
        for(int i=0;i<4;i++){
                for(int j=0;j<3;j++){
                        for(int k=0;k<10;k++){
                                room[i][j][k]=0;
                        }
                }
        }
        int n;
        scanf("%d",&n);
        for(int i;i<n;i++){
                int b,f,r,v;
                scanf("%d %d %d %d",&b,&f,&r,&v);
                room[b-1][f-1][r-1]+=v;
        }
        for(int i=0;i<4;i++){
                for(int j=0;j<3;j++){
                        for(int k=0;k<10;k++){
                                if(k<9){
                                        printf(" %d",room[i][j][k]);
                                }else{
                                        printf(" %d\n",room[i][j][k]);
                                }
                        }
                        if(j==2 && i!=3){
                                printf("####################\n");
                        }
                }
        }
        return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main() {

	ll n,m;cin>>n>>m;
	vector<pair<ll,ll>> vc;
	ll a,b;
	ll d[m+1],f[m+1];
	map<ll,ll> mp;
	for(int i=1;i<=m;i++){
	cin>>d[i]>>f[i]	;
	vc.push_back({d[i],f[i]});}
	
	sort(vc.begin(),vc.end());
	int count=1;
	mp[vc[0].second]+=count;
	
	for(int i=1;i<vc.size();i++)
	{
		if(vc[i].first==vc[i-1].first){
		count++;
		mp[vc[i].second]+=count;}
		else{
		count=1;
		mp[vc[i].second]+=count;}
	}
	
	for(int i=1;i<=m;i++)
	{
		string res=to_string(d[i]);
		ll zero=6-res.length();
		for(int j=0;j<zero;j++)
		cout<<"0";
		cout<<res;
		
	res=to_string(mp[f[i]]);
     zero=6-res.length();
		for(int j=0;j<zero;j++)
		cout<<"0";
		cout<<res;
		
		cout<<"\n";
	}
	
	
}
	
	
	

Measured memory_bytes: 10864
//Be Name Khoda
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma optimize O3
using namespace __gnu_pbds;
using namespace std;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long int LL;
typedef LL ll;
typedef long double ld;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;
 
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for (int i=a;i<b;i++)
#define Ford(i,a,b) for (int i=a;i>=b;i--)
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define ER(a) cout << #a << ' ' << a << endl
#define LB(a,n,x) (lower_bound(a,(a)+(n),x)-(a))
#define RET(x) { cout << x; exit(0); } 
#define RETD(x) { cout << fixed << setprecision(15) << x; exit(0); }
const ll M=2e5+5,LG=32,SM=600+5,inf=1e18+5;
ll mod=1e9+7;

ll n;
vll g[M];
ll a[M];

ll dfs(ll x,ll p)
{
    for (ll y:g[x])
    {
        if (y==p) continue;
        if (!dfs(y,x) && a[y]<a[x])
            return 1;
    }
    return 0;
}

int main()
{
	ios::sync_with_stdio(0);
    cin >> n;
    For(i,0,n) cin >> a[i];
    For(i,1,n)
    {
        ll u,v;
        cin >> u >> v;
        u--;v--;
        g[u].PB(v);g[v].PB(u);
    }
    For(i,0,n)
    {
        if (dfs(i,i))
            cout << i+1 << ' ';
    }
} 

Measured memory_bytes: 5248