akhauriyash/Code-Regression huggingface dataset:
import java.util.*

fun main(args: Array<String>){
    var S: String = readLine()!!
    var T: String = readLine()!!
    var found = false
    var count = 0

    for(i in (S.length -T.length) downTo 0){
        var OK = true
        for(j in 0 until T.length){
            if(S[i+j] != '?' && (T[j] != S[i+j])){
                OK = false
            }
        }

        if(OK){
            count = i
            found = true
            break
        }
    }

    if(found){
        for(i in 0 until S.length){
            if(i >= count && i < count+T.length){
                print(T[i-count])
            } else if(S[i] == '?'){
                print('a')
            } else {
                print(S[i])
            }
        }

    } else {
        System.out.println("UNRESTORABLE")
    }


}

Measured memory_bytes: 34352
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

vector<ll>pa(51, 0), ba(51, 0);

ll func(ll n, ll x) {

	if (n == 0) {
		return 1;
	}
	else if (x == 1) {
		return 0;
	}
	else if (x > 1 && x <= ba[n-1]+1) {
		return func(n - 1, x - 1);
	}
	else if (x == ba[n - 1] + 2) {
		return pa[n-1]+1;
	}
	else if (x > ba[n - 1] + 2 && x < ba[n]) {
		return pa[n - 1] + 1 + func(n - 1, x - ba[n - 1] - 2);
	}
	else if (x == ba[n]) {
		return pa[n];
	}


	return 0;
}


signed main() {
	int i, j;
	ll n, x;
	

	cin >> n >> x;

	pa[0] = 1;
	ba[0] = 1;


	for (i = 1; i <= n; i++) {
		pa[i] = pa[i - 1] * 2 + 1;
	}

	for (i = 1; i <= n; i++) {
		ba[i] = ba[i - 1] * 2 + 3;
	}

	cout << func(n, x) << endl;











	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
/*
 * @Author: Kaizyn
 * @Date: 2020-08-29 21:37:37
 * @LastEditTime: 2020-08-29 21:38:59
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const double eps = 1e-7;
const double PI = acos(-1);
typedef pair<int, int> pii;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int N = 2e5+7;

int n;
int a[N];

inline void solve() {
  cin >> n;
  long long sum = 0, res = 0;
  for (int i=  1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  for (int i = 1; i <= n; ++i) {
    sum -= a[i];
    res += sum%MOD*a[i]%MOD;
  }
  cout << res%MOD << endl;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 4364
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=1e5+5;
int a[N],b[N];
ll s[N];
ll sum;
int n;

int main()
{
	scanf("%d",&n);
	FOR(i,0,n-1)scanf("%d",&b[i]),b[i]*=2;
	FOR(i,0,n-1)sum+=b[i];
	s[0]=b[0],s[1]=b[1];
	FOR(i,2,n-1)s[i]=s[i-2]+b[i];
	sum/=2;
	FOR(i,0,n-1)
	{
		ll tmp=sum;
		if(i&1)
		{
			if(i>2)tmp-=s[i-2];
			if(i<n-3)tmp-=s[n-3]-s[i-1];
			tmp-=b[n-1];
		}
		else
		{
			if(i>1)tmp-=s[i-2];
			if(i<n-2)tmp-=s[n-2]-s[i-1];
		}
		printf("%lld%c",tmp,(i==n-1?'\n':' '));

	}
	return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
#define Pll pair<ll,ll>

template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const int INF =2e+9;
const ll INFL =9e+18;
const long MOD =1e+9+7;
#define PI 3.14159265258979

int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};
int fn(int a,int b){
	if(a<b) return fn(b,a);
	
	if(a%b!=0) return fn(b,a%b);
	else return b;
}
int main(void){
	ll Q,H,S,D,N,tem=INF;
	cin>>Q>>H>>S>>D>>N;

	chmin(tem,4*Q);
	chmin(tem,2*H);
	chmin(tem,S);

	print(min(N*tem,(N/2)*D+(N%2)*tem));
	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
int main(void){
	int N, M;
  	std::cin >> N >> M;
  
	if(M == 1 || N >= M){
    	std::cout << 0;
      	return 0;
    }
  
  	std::vector<int> zahyou;
  	zahyou.resize(M);
  	
  	for(int i = 0; i < M; i++){
    	std::cin >> zahyou[i];
    }
  
  	std::sort(zahyou.begin(), zahyou.end());
  	std::vector<int> distance;
  	distance.resize(M-1);
  	
  	for(int i = 0; i < M-1; i++){
    	distance[i] = std::abs(zahyou[i]-zahyou[i+1]);
    }
  	
  	std::sort(distance.begin(), distance.end());
  
  	int count = 0;
  	for(int i = 0; i < distance.size()-N+1; i++){
    	count += distance[i];
    }
  
  	std::cout << count;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>

using namespace std;

long long dp[100][101][301];
long long w[100];
long long v[100];
long long adjusted_w[100];
int main(){
    int N;
    long long W;
    cin >> N >> W;
    for(int i = 0; i < N; i++){
        cin >> w[i] >> v[i];
    }

    for(int i = 0; i < N; i++){
        adjusted_w[i] = w[i] - w[0];
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= 3 * N; k++){
                dp[i][j][k] = -1;
            }
        }
    }
    dp[0][0][0] = 0;
    dp[0][1][0] = v[0];
    for(int i = 1; i < N; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= 3 * N; k++){
                dp[i][j][k] = dp[i - 1][j][k];
                if(j > 0 && k - adjusted_w[i] >= 0 && dp[i - 1][j - 1][k - adjusted_w[i]] >= 0){
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - adjusted_w[i]] + v[i]);
                }
            }
        }
    }
    /*
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= N; j++){
            cout << j << ": ";
            for(int k = 0; k <= 3 * N; k++){
                cout << dp[i][j][k] << " ";
            }
        }
        cout << endl;
    }
    */
    long long ans = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= W - (w[0] * i); j++){
            if(j  <= 3 * N){
                ans = max(ans, dp[N - 1][i][j]);
                //cout << i << ", " << j << ": " << dp[N - 1][i][j] << endl;
            } else {
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 24444
import sys
input = lambda : sys.stdin.readline().rstrip()

import collections
s = [int(c) for c in input()]
tmp = 1
mod = 0
count = collections.defaultdict(int)
for i,num in enumerate(s[::-1]):
    mod = (tmp * num + mod) % 2019
    count[mod] += 1
    tmp *= 10
    tmp %= 2019
count[0] += 1
print(sum((item*(item-1)//2 for item in count.values())))

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

const ll INF = ll(1e18)+1;
//10^{18}+1を表す

int main() {
    int n; ll k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    ll l = -INF, r = INF; //lはx未満となる数字の大丈夫な範囲，rはダメな範囲
    //二分探索開始
    while(l+1 < r){ //lとrが隣り合ったら終了
        ll x = (l+r)/2; //中央値を設定
        bool ok = [&]{ //ラムダ式の関数
            ll total = 0; //x以下となる組み合わせの個数
            rep(i, n){ //配列の値を全て確認
                if(a[i] > 0){ //正か負かで処理が異なる
                    int l = -1, r = n; //lは大丈夫なインデックス，rはダメなインデックス
                    while(l+1 < r){ //二分探索
                        int c = (l+r)/2;
                        if(a[c]*a[i] < x) l = c; else r = c;
                    }
                    total += r; //本当はl+1
                }
                else{
                    int l = -1, r = n; //lはダメなインデックス，rは大丈夫
                    while(l+1 < r){
                        int c = (l+r)/2;
                        if(a[c]*a[i] < x) r = c; else l = c;
                    }
                    total += n - r;
                }
                if(a[i]*a[i] < x) total --; //自分自身は組み合わせに入らないので引いておく
            }
            total /= 2;
            return total < k;//xとなる組み合わせがk未満かどうか返す
        }();//関数呼び出し
        if(ok) l = x; else r = x;
    }

    cout << l << endl;

    return 0;
}

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

int main(){
	string a,b;
  	cin>>a>>b;
  	for(int i=0;i<b.size();++i)cout<<a[i]<<b[i];
  	if(b.size()<a.size())cout<<a[a.size()-1];
  	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int inv[2011];
char str[30][128];
int mod=2011;
int a;
int b;
int find(int top,int bottom,int left){
	for(int i=top;i<=bottom;i++)if(str[i][left]!='.')return i;
}
int find2(int top,int bottom,int left){
	for(int i=left;i<b;i++){
		for(int j=top;j<=bottom;j++){
			if(str[j][i]!='.')return i;
		}
	}
}
pair<int,int>expr(int top,int bottom,int left);
pair<int,int> fraction(int top,int bottom,int left){
	int base=find(top,bottom,left);
	pair<int,int>bunshi=expr(top,base-1,find2(top,base-1,left));
	pair<int,int>bunbo=expr(base+1,bottom,find2(base+1,bottom,left));
	return make_pair(bunshi.first*inv[bunbo.first]%mod,max(bunshi.second,bunbo.second)+1);
}
pair<int,int> primary(int top,int bottom,int left){
	int base=find(top,bottom,left);
	int at=left;
	if(str[base][at]>='0'&&str[base][at]<='9'){
		return make_pair(str[base][at]-'0',at);
	}else{
		pair<int,int>res=expr(top,bottom,left+2);
		res.second+=2;
		return res;
	}
}
pair<int,int> powexpr(int top,int bottom,int left){
	int base=find(top,bottom,left);
	int at=left;
	pair<int,int> val=primary(top,bottom,left);
	if(val.second<b-1&&base&&'0'<=str[base-1][val.second+1]&&str[base-1][val.second+1]<='9'){
		int res=1;
		for(int i=0;i<str[base-1][val.second+1]-'0';i++){
			res=res*val.first%mod;
		}
		return make_pair(res,val.second+1);
	}else{
		return val;
	}
}
pair<int,int> factor(int top,int bottom,int left){
	int base=find(top,bottom,left);
	int at=left;
	if(at<b-1&&str[base][at]=='-'&&str[base][at+1]=='-'){
		return fraction(top,bottom,at);
	}else if(str[base][at]=='-'){
		pair<int,int> val=factor(top,bottom,at+2);
		val.first=2011-val.first;
		return val;
	}else{
		return powexpr(top,bottom,at);
	}
}
pair<int,int> term(int top,int bottom,int left){
	int base=find(top,bottom,left);
	int val=1;
	int at=left;
	while(1){
		pair<int,int> res=factor(top,bottom,at);
		at=res.second+2;
		val=val*res.first%mod;
		if(at>=b||str[base][at]!='*'){
			if(at>=b)return make_pair(val,at);
			else return make_pair(val,at-2);
			break;
		}
		at+=2;
	}
}
pair<int,int> expr(int top,int bottom,int left){
	int base=find(top,bottom,left);
	int val=0;
	int at=left;
	int P=1;
	while(1){
		pair<int,int> res=term(top,bottom,at);
		at=res.second+2;
		val=(val+P*res.first+mod)%mod;
		if(at>=b||(str[base][at]!='+'&&str[base][at]!='-')){
			if(at>=b)return make_pair(val,at);
			else return make_pair(val,at-2);
		}
		if(str[base][at]=='+')P=1;
		else P=-1;
		at+=2;
	}
}
int main(){
	inv[1]=1;
	for(int i=2;i<2011;i++){
		inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
	}
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++)scanf("%s",str[i]);
	//	printf("%s\n",str[0]);
		b=strlen(str[0]);
		int B=0;
		for(int i=0;i<a;i++)if(str[i][0]!='.')B=i;
		printf("%d\n",expr(0,a-1,0).first);
	}
}

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

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

    long long n {};
    cin >> n;

    string ans {};
    while (n) {
        --n;
        ans += 'a' + (n%26);
        n /= 26;
    };

    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
using namespace std;
int a,b;
int main(){
	cin >> a >> b;
	if(a <= b){
		for(int i = 1; i <= b; i++)
			cout << a ;
	}
	else {
		for(int i = 1; i <= a; i++)
			cout << b;
	}
	cout << endl;
}

Measured memory_bytes: 256
#16D8101014F 久留米 竜之介 Utyan0604 python3
def insertionsort(n,A):
	for i in range(n):
		t=A[i]
		j=i-1
		while j>=0 and A[j] > t:
			A[j+1]=A[j]
			j-=1
			A[j+1]=t
			
			
	
		for k in range(n):
			if k<n-1:
				print(A[k],end=" ")
			else:
				print(A[k])
			
n=int(input())
A=list(map(int, input().split()))

insertionsort(n,A)




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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> v(n+1, vector<int>(3));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> v[i][j];
    vector<vector<int>> dp(n+1, vector<int>(3));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            int val = 0;
            for (int k = 0; k < 3; k++) {
                if (k == j)
                    continue;
                val = max(val, dp[i-1][k] + v[i][j]);
            }
            dp[i][j] = val;
        }
    }
    int ans = 0;
    for (int i = 0; i < 3; i++)
        ans = max(ans, dp[n][i]);
    cout << ans;
    return 0;
}

Measured memory_bytes: 14080
#include <stdio.h>

typedef struct Node{
    struct Node* parent;
    struct Node* next;
    struct Node* son;
    unsigned int id;
}Node;

int get_depth(Node* node){
    if(node->parent==NULL)
        return 0;
    else
        return get_depth(node->parent)+1;
}

int main(){
    int Node_num;
    scanf("%d", &Node_num);
    Node node[Node_num];
    Node *nodes[Node_num];
    for(int i=0;i<Node_num;i++){
        nodes[i] = &node[i];
        nodes[i]->next = NULL;
        nodes[i]->parent = NULL;
        nodes[i]->son = NULL;
    }
    for(int i=0;i<Node_num;i++){
        int id;
        int sons;
        scanf("%d %d", &id, &sons);
        nodes[id]->id = id;
        int first_son,next_son;
        if(sons--!=0){
            scanf("%d", &first_son);
            nodes[id]->son = nodes[first_son];
            nodes[first_son]->parent = nodes[id];
            next_son = first_son;
        }
        while(sons-->0){
            int next_son_id;
            scanf("%d", &next_son_id);
            nodes[next_son]->next = nodes[next_son_id];
            nodes[next_son_id]->parent = nodes[id];
            next_son = next_son_id;
        }
    }
    for(int i=0;i<Node_num;i++){
        printf("node %d: parent = ", i);
        if(nodes[i]->parent!=NULL){
            printf("%d,", nodes[i]->parent-nodes[0]);
        }
        else
            printf("-1,");
        printf(" depth = %d, ", get_depth(nodes[i]));
        if(nodes[i]->parent==NULL)
            printf("root,");
        else if(nodes[i]->son==NULL)
            printf("leaf,");
        else
            printf("internal node,");
        printf(" [");
        if(nodes[i]->son!=NULL){
            Node * first_son = nodes[i]->son;
            printf("%d", first_son-nodes[0]);
            while(first_son->next!=NULL){
                printf(", %d", first_son->next-nodes[0]);
                first_son = first_son->next;
            }
        }
        printf("]\n");
    }
}



Measured memory_bytes: 5624
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    int pt = 0, px = 0, py = 0;
    for (int i = 0; i < N; i++) {
        int t, x, y;
        cin >> t >> x >> y;
        int dt = abs(t - pt);
        int dx = abs(x - px);
        int dy = abs(y - py);
        if (dt % 2 != (dx + dy) % 2
                || dt < dx + dy) {
            cout << "No" << endl;
            return 0;
        }
        t = pt, x = px, y = py;
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
n = int(input())
li = [0] * 100003
ans = 0

for i in range(n):
    a,b = map(int,input().split())
    li[a] += 1
    li[b + 1] -= 1

for i in range(1,len(li)):
    li[i] += li[i-1]
    if i -1 <= li[i]:
        ans = i-1
print(ans)


Measured memory_bytes: 9464
#include<bits/stdc++.h>
#include<deque>
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
char s[maxn];
deque<int> q;
deque<int>::iterator it;
int main(void)
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	int m; scanf("%d",&m);
	for(int i=1;i<=n;i++) q.push_back(s[i]-'a');
	int f=1;
	while(m--)
	{
		int opt,pos; char c;
		scanf("%d",&opt);
		if(opt==1)
		{
			f=f^1;
		}
		else
		{
			scanf("%d %c",&pos,&c);
			if(f==1)
			{
				if(pos==1) q.push_front(c-'a');
				else q.push_back(c-'a');
			}
			else
			{
				if(pos==1) q.push_back(c-'a');
				else q.push_front(c-'a');
			}
		}
	}
	if(f==1)
	{
		while(!q.empty()) 
		{
			printf("%c",q.front()+'a');
			q.pop_front();
		}
		printf("\n");
	}
	else
	{
		while(!q.empty())
		{
			printf("%c",q.back()+'a');
			q.pop_back();
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define rep for(int i = 0;i<n;i++)
 
int main(void){
  int n;cin >> n;
  int ng = 0;int m = 1e9;long long sum = 0;
  rep{
    int ai;
    cin >> ai;
    if(ai < 0)ng++;
    sum += abs(ai);
    m = min(m,abs(ai));
  }
  if(ng % 2 == 1){
    sum -= 2*m;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp64 {
    class Program {
        static void Main(string[] args) {
            var st = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int A = st[0];
            int B = st[1];
            int K = st[2];

            List<int> ans = new List<int>();

            for (int i = 0; i < K; i++) {

                if (A + i <= B) {
                    ans.Add(A + i);
                }
                if (B - i >= A) {
                    ans.Add(B - i);
                }
            }

            var ans_new = ans.Distinct().OrderBy(x => x);

            foreach(var element in ans_new) {
                Console.WriteLine(element);
            }
        }
    }
}


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


// int minimumCost(int index, int arr[], int size, vector<int>&memo ){
//     if(index == size){
//         return 0;
//     }
//     if(memo[index] != -1)
//         return memo[index];
//     int left = abs(arr[index] - arr[index+1]) + minimumCost(index + 1, arr, size,memo);
//     int right = INT_MAX;
//     if(index + 2 <= size)
//         right = abs(arr[index] - arr[index+2]) + minimumCost(index + 2, arr, size,memo);
//     return memo[index] = min(left, right);
// }

int main(){
    int N;
    cin>>N;
    int arr[N];
    vector<int> dp(N, INT_MAX);
    for(int i = 0; i < N; ++i){
        cin>>arr[i];
    }
    dp[0] = 0;
    // for (int i = 0; i < N; ++i)
        // int val = minimumCost(0, arr, N-1,memo);
    // cout << val << endl;

    for (int i = 0; i < N; ++i){
        for (int j = 1; j <= 2; ++j){
            if(i+j <= N)
                dp[i + j] = min(dp[i + j], dp[i] + abs(arr[i + j] - arr[i]));
        }
    }
    cout << dp[N - 1];
}

Measured memory_bytes: 3984
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <cmath>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)


int main(){

    int n;
    scanf("%d",&n);
    int now_x = 0,  now_y = 0,pr_t=0,t,des_x,des_y;
    while(n--){
        scanf("%d %d %d\n", &t, &des_x, &des_y);
        if(abs(des_x-now_x)+abs(des_y-now_y)>(t-pr_t)||(abs(des_x-now_x)+abs(des_y-now_y))%2!=(t-pr_t)%2){
            printf("No\n");
            return 0;
        }else{
            now_x = des_x;
            now_y = des_y;
            pr_t = t;
        }

    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
    #define int ll
    #define M 1000000007
    #define hell 998244353
    #define big 1e18
    #define pb push_back
    #define pi 3.1415926536
    #define mp make_pair
    #define ub upper_bound
    #define lb lower_bound
    #define mem0(a) memset(a,0,sizeof(a))
    #define memf(a) memset(a,false,sizeof(a))
    #define mem1(a) memset(a,1,sizeof(a))
    #define all(a) a.begin(),a.end()
    #define ll long long
    #define vec vector <int>
    #define pii pair<int,int>
    #define endl "\n"
    #define gcd __gcd
    using namespace std;
    int power(int x, unsigned int y, unsigned int m) 
	{ 
    	if (y == 0) 
        	return 1; 
    	int p = power(x, y/2, m) % m; 
    	p = (p * p) % m; 
  
 	   return (y%2 == 0)? p : (x * p) % m; 
	} 
	int modInverse(int a, int m) 
	{   
    	return power(a, m-2, m);
	}
    signed main()
    {
    	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	ll t=1;
    	// cin >> t;
    	/*SAARE INPUTS LENA*/
    	/*VARIABLES KI RANGE DEKHLENA*/
    	while(t-->0)
    	{
    		ll n=0;
    		cin>>n;
    		int r=n%10;
    		if(r==2 || r==4 || r==5 || r==7 || r==9)
    			cout<<"hon";
    		else if(r==0 || r==1 || r==6 || r==8)
    			cout<<"pon";
    		else
    			cout<<"bon";
    	}
    	return 0;
    }

Measured memory_bytes: 3620
#include<stdio.h>
#include<string.h>
int main(){
	char a[105];
	int n,m=0;
	scanf("%s",a);
	n=strlen(a);
	for(int i=0;i<n/2;i++)
	{
		if(a[i]!=a[n-i-1])
		m++;
	}
	printf("%d\n",m);
}

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

using namespace std;

#define ll       long long

#define  sci(x)   scanf("%d", &x)
#define  scl(x)   scanf("%lld", &x)
#define  scd(x)   scanf("%lf", &x)

#define  pfi(x)   printf("%d", x)
#define  pfl(x)   printf("%lld", x)
#define  pfd(x)   printf("%lf", x)
#define  pfc(x)   printf("Case %d: ", x++)
#define  ps       printf(" ")
#define  pn       printf("\n")

#define  pb       push_back
#define  ppb      pop_back
#define  pf       push_front
#define  ppf      pop_front
#define  In       insert
#define  All(a)   a.begin(), a.end()

ll dp[100][100005];
int w[100], v[100], n;

ll solve(int pos, int rem)
{
	if(pos >= n)
		return 0;

	ll ret = dp[pos][rem];
	if(ret != -1)
		return ret;

	ret = solve(pos + 1, rem);
	if(rem >= w[pos])
		ret = max(ret, v[pos] + solve(pos + 1, rem - w[pos]));

	return dp[pos][rem] = ret;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    memset(dp, -1, sizeof dp);
    int ww;
    sci(n), sci(ww);

    for(int i = 0; i < n; i++)
    	sci(w[i]), sci(v[i]);

    cout << solve(0, ww);
    return 0;
}

Measured memory_bytes: 78336
using System;
using System.Linq;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var HList = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            var output = 0;
            var max = 0;
            foreach (var H in HList)
            {
                if (H >= max) output++;
                max = Math.Max(max, H);
            }

            Console.Write(output);
        }
    }
}


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

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

    int x, y, z = -1;
    for(x = 0; x <= n; x++){
        for(y = 0; x+y <= n; y++){
            if(x*10000+y*5000+(n-x-y)*1000 == y0){
                z = n-x-y;
                break;
            }
        }
        if(z != -1) break;
    }

    if(z == -1){
        x = -1;
        y = -1;
    }

    cout << x << " " << y << " " << z << endl;
    return 0;
}

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

int M[52][52];

void fill(int y, int x){
	M[y][x] = 0;
	if(M[y-1][x]) fill(y-1,x);
	if(M[y+1][x]) fill(y+1,x);
	if(M[y][x-1]) fill(y,x-1);
	if(M[y][x+1]) fill(y,x+1);
	if(M[y-1][x-1]) fill(y-1,x-1);
	if(M[y+1][x-1]) fill(y+1,x-1);
	if(M[y-1][x+1]) fill(y-1,x+1);
	if(M[y+1][x+1]) fill(y+1,x+1);
}

main(){
	int w,h,c,i,j;
	while(cin>>w>>h,w){
		memset(M, 0, sizeof(M));
		c=0;
		for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			cin >> M[i][j];
		}
		}
		for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			if(!M[i][j]) continue;
			fill(i, j);
			c ++;
		}
		}
		
		cout << c << endl;
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<string>
#include<cmath>
typedef long long int ll;
#define VI vector<int>

#define rep(i,a) for(int i=0;i<(a);i++)
#define all(i) i.begin(),i.end()
#define INF 1000000000


using namespace std;


/**/
VI y;
pair<int,int> x[31];


int main(){
	while(1){
		int n;
		int a,b;
		int suma=0,sumb=0;
		cin>>n;
		if(n==0)break;
		rep(i,n){
			cin>>a>>b;
			if(a>b){
				suma+=a+b;
			}else if(a<b){
				sumb+=a+b;
			}else if(a==b){
				suma+=a;
				sumb+=b;
			}
		}
		cout<<suma<<" "<<sumb<<endl;
	}

	return 0;
}

Measured memory_bytes: 1160
using System.Linq;
using static System.Console;

class B
{
	static void Main()
	{
		var M = 1000000007;
		var h = ReadLine().Split().Select(int.Parse).ToArray();
		var a = ReadLine().Split().Select(int.Parse).ToArray();
		long k = h[1];

		int x1 = 0, x2 = 0;
		for (var i = 0; i < h[0]; i++)
			for (var j = i + 1; j < h[0]; j++)
			{
				if (a[i] < a[j]) x1++;
				if (a[i] > a[j]) x2++;
			}
		WriteLine((k * (k - 1) / 2 % M * x1 + k * (k + 1) / 2 % M * x2) % M);
	}
}


Measured memory_bytes: 13396
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, M;

int main() {
  INCANT;
  cin >> N >> M;
  int sm=0;
  int a;
  rep(i, M) {
    cin >> a;
    sm+=a;
  }
  if (sm>N) {
    cout << -1 << "\n";
  } else {
    cout << N-sm << "\n";
  }
  return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <cmath>
#include <string>
#include <stack>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long llong;

int main() {
	int a, b, k;
	int ad[110], bd[110];
	int count_ad = 0, count_bd = 0;
	cin >> a >> b >> k;

	int i = 1;
	while(a >= i){
		if(a%i == 0){
			ad[count_ad++] = i;
		}
		i++;
	}
	i = 1;
	while(b >= i){
		if(b%i == 0){
			bd[count_bd++] = i;
		}
		i++;
	}

	/*
	for (int m = 0; m < count_ad; ++m) {
		cout << ad[m] << endl;
	}*/

	int c = 0;

	for (int j = count_ad-1; j >= 0; --j) {
		for (int l = count_bd-1; l >= 0; --l) {
			if(ad[j] == bd[l]){
				c++;
				if(c == k) {
					cout << ad[j] << endl;
					return 0;
				}else{
					break;
				}
			}
		}
	}
	
	return 0;
}

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

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, l;
	cin >> n >> l;
	vi v(n);
	REP(i, n)cin >> v[i];
	int p=-1;
	REP(i, n - 1) {
		if (v[i] + v[i + 1] >= l) {
			p = i;
			break;
		}
	}
	if(p==-1) cout << "Impossible" << endl;
	else {

		cout << "Possible" << endl;
		REP(i, p)cout << i + 1 << endl;
		RFOR(i, p, n-1) {
			cout <<i+1 << endl;
		}
	}
	return 0;
}


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

int iabs(int &a){
    if(a>=0)return a;
    else return -a;
}

int main(void){
    int n,l;
    cin>>n>>l;
    int min=100000;
    int sum=0;
    for(int i=0;i<n;i++){
        int a=l+i;
        if(iabs(min)>iabs(a))min=a;
        sum+=a;
    }
    sum-=min;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

const int inf = ( 1 << 28);

int dp[20001][256];
int solve(int n,int m,int *cbook,int *in){
  rep(i,n+1)rep(j,256)dp[i][j]=inf;
  dp[0][128]=0;

  rep(i,n){
    rep(j,256){
      if (dp[i][j] == inf)continue;
      rep(k,m){
	int next=j+cbook[k];
	if (next<0)next=0;
	else if (next>255)next=255;
	dp[i+1][next]=min(dp[i+1][next],dp[i][j]+(next-in[i])*(next-in[i]));
      }
    }
  }
  
  int ans = inf;
  rep(i,256)ans=min(ans,dp[n][i]);
  return ans;
}


main(){
  int n,m;
  int in[20000],cbook[200];
  while(cin>>n>>m && n){
    rep(i,m)cin>>cbook[i];
    rep(i,n)cin>>in[i];
    cout << solve(n,m,cbook,in) << endl;
  }
}

Measured memory_bytes: 20000
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
  		Scanner $ = new Scanner(System.in);
        int N = $.nextInt();
    	int id =1;
    	List<Town> ts = new ArrayList<>();
    	while(N-- != 0){
         	Town t = new Town();
           	t.id = id;
            id++;
            t.town = $.next();
          	t.ten = $.nextInt();
          	ts.add(t);
        }  
    
		Comparator<Town> com = (t1, t2) -> t1.town.compareTo(t2.town);
    	Comparator<Town> comX = (t1,t2) -> t2.ten - t1.ten;
    	ts.sort(com.thenComparing(comX));
    	ts.forEach(tX-> System.out.println(tX.id));
  }

	static class Town {
		String town;
		int ten;
		int id;
	}
}

Measured memory_bytes: 27220
from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

hp = []
for x, h in xh:
    heappush(hp, [x, REAL, h])

bomb_acm = 0
ans = 0
while hp:
    x, r, h = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, UNREAL, hp_dis])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

print(ans)


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

int main()
{char c;
    cin >> c;
    int code = int(c);
    
    
    if (code == int('a')||code==int('e')||code==int('i')||code==int('o')||code==int('u'))
        cout <<"vowel";
    else
        cout <<"consonant";
        
}

Measured memory_bytes: 256
//#pragma GCC optimize("-O3")
/*
				C++
				encoding: UTF-8
				Last Modified: 12/Apr/20 05:41:19 PM
*/

#include <bits/stdc++.h>
#ifdef H4wk3ye
#	include <prettypr.hpp>
#endif

using namespace std;

// clang-format off

#define		int                    long long
#define		ve                     vector
#define		pb                     push_back
#define		endl                   "\n"
#define		ff                     first
#define		ss                     second
#define		pii                    pair<int, int>
#define		len(v)                 (int)v.size()
#define		all(v)                 v.begin(), v.end()
#define		reset(a, b)            memset(a, b, sizeof(a));
#define		fr(i, s, n)            for (int i = s ; i < n ; ++i)
#define		dfr(i, s, n)           for (int i = s ; i > n ; --i)

template < typename T > void pr (const T& t) {
    cout << t << "\n";
}

template < typename T, typename U, typename... ARGS >
void pr (const T& t, const U& u, const ARGS&... args) {
    cout << t << " ";
    pr (u, args...);
}

// clang-format on


signed main () {
	ios_base::sync_with_stdio (false), cin.tie (nullptr);
	int k;
	cin >> k;
	int ans = 0;
	fr (i, 1, k + 1) {
		fr (j, 1, k + 1) {
			fr (l, 1, k + 1) {
				ans += __gcd (i, __gcd (j, l));
			}
		}
	}
	pr (ans);
	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i = 0; i < (n); ++i )
#define rep_rev(n,i) for(ll i = n; i >= 0; --i )
using namespace std;
const long long INF = 1LL << 60;
 //setを使う練習問題
int N;
set<int> st;

 int main(){
   cin >> N;
   rep(i,N){
     int tmp;
     cin >> tmp;
     st.insert(tmp);
   }
   cout << st.size() << endl;
   return 0;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a[101];int n,i;
int main(){
    scanf("%d%*d",&n);
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++)
        cout<<a[i];
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<iostream>
using namespace std;
long long f[50];
int main()
{
    int n;  f[0]=2;
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)  f[i]=f[i-1]*2+2;
	cout<<f[n];
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = sc.nextInt();
        int total = 1;
        for(int i = 0; i < n - 1; i++){
            int tmp = sc.nextInt();
            if(max <= tmp){
                max = tmp;
                total++;
            }
        }
        System.out.println(total);
        
    }
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int a = s[0] - '0',b = s[1] - '0',c = s[2] - '0',d = s[3] - '0';
    int x[8] = {a+b+c+d,a+b+c-d,a+b-c+d,a-b+c+d,a+b-c-d,a-b+c-d,a-b-c+d,a-b-c-d};
    for(int i = 0;i < 8;i++)
    {
        if(x[i] == 7)
        {
            switch(i)
            {
                case 0: cout << a << "+" << b << "+" << c << "+" << d << "=7"; return 0;
                case 1: cout << a << "+" << b << "+" << c << "-" << d << "=7"; return 0;
                case 2: cout << a << "+" << b << "-" << c << "+" << d << "=7"; return 0;
                case 3: cout << a << "-" << b << "+" << c << "+" << d << "=7"; return 0;
                case 4: cout << a << "+" << b << "-" << c << "-" << d << "=7"; return 0;
                case 5: cout << a << "-" << b << "+" << c << "-" << d << "=7"; return 0;
                case 6: cout << a << "-" << b << "-" << c << "+" << d << "=7"; return 0;
                case 7: cout << a << "-" << b << "-" << c << "-" << d << "=7"; return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}
 
int main() {
  ll max = 200000;
  ll n,k;
  cin >> n >> k;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

  vector<ll> v(max + 1, 0);
  
  for(ll i=0; i<n; i++) {
    ll a;
    cin >> a;
    v.at(a) = v.at(a) + 1;
  }
  
  ll c = max;
  
  while(c > 0) {
    if(v.at(c) != 0) {
      pq.push(make_pair(v.at(c), c));
    }
    c--;
  }
  
  ll t = 0;
  while(pq.size() > k) {
    pair<ll, ll> top = pq.top(); 
    t = t + top.first;
    pq.pop();
  }
  cout << t;

}

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
int P[200011];
VI G[200011];
VI R[200011];

bool use[200011];
int par[200011];

int A[200011], C[200011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", P+i), P[i]--;
    REP (i, N) {
	G[P[i]].push_back(i);
    }

    int s = 0;
    REP (i, N) s = P[s];
    VI cycle;
    while (!use[s]) {
	use[s] = true;
	cycle.push_back(s);
	s = P[s];
    }

    memset(C, -1, sizeof C);
    VI ord;
    EACH (e, cycle) {
	ord.clear();
	ord.push_back(*e);
	par[*e] = *e;
	for (int i=0; i<(int)ord.size(); i++) {
	    int v = ord[i];
	    EACH (f, G[v]) if (!use[*f] && *f != par[v]) {
		par[*f] = v;
		ord.push_back(*f);
	    }
	}

	for (int i=ord.size(); i--;) {
	    int v = ord[i];
	    EACH (f, G[v]) if (!use[*f] && *f != par[v]) {
		C[A[*f]] = v;
	    }

	    REP (j, N+1) if (C[j] != v) {
		A[v] = j;
		break;
	    }
	}
    }
    REP (add, 2) {
	int prv = A[cycle.back()] + add;
	REP (i, cycle.size()) {
	    int v = cycle[i];
	    if (A[v] == prv) {
		prv = A[v] + 1;
	    } else {
		prv = A[v];
	    }
	}
	if (prv == A[cycle.back()] + add) {
	    puts("POSSIBLE");
	    return;
	}
    }
    puts("IMPOSSIBLE");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 18932
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100000,100
#a=[i for i in range(100000)]

kl=[i for i in range(1,k+1)]

dp=[float("inf")]*(n)
dp[0]=0
for i in range(1,n):
  dp[i] = min(dp[j] + abs(a[i] - a[j]) for j in range(max(0, i - k), i))

print(dp[n-1])


Measured memory_bytes: 20576
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
using ll = long long;
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
int main() {
	ll n, k;
	cin >> n >> k;
	ll a[n], f[n];
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> f[i];
	sort(a, a + n);
	sort(f, f + n, greater<ll>());
	ll l = -1, r = 1e18 + 1;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		ll p = 0;
		rep(i, n) p += max(0LL, a[i] - m / f[i]);
		if (p > k)
			l = m;
		else
			r = m;
	}
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    //ios::sync_with_stdio(0); cin.tie(0);
    ll a, b;
    int c, d;
    scanf("%lld %d.%d", &a, &c, &d);
    b = c*100 + d;
    ll ans = b*a/100;
    printf("%lld\n", ans);
}


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

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

int main() {
  ll n, X;
  cin >> n >> X;
  vector<ll> x(n);
  rep(i, n) cin >> x[i];
  sort(x.begin(), x.end());
  if (n == 1) {
    cout << abs(X - x[0]) << endl;
    return 0;
  }
  ll ans = abs(x[0] - x[1]), ans2=0;
  rep(i, n - 3) ans = gcd(ans, abs(x[i + 1] - x[i + 2]));
  rep(i, n) ans2 = max(ans2, gcd(ans, X - x[i]));
  cout << ans2 << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1e+9 + 7;
// constexpr int mod = 998244353;

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

    int n;
    cin >> n;
    vector<ll> a(n);
    ll XorSum = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        XorSum ^= a[i];
    }
    ll ans = XorSum;
    XorSum = ~XorSum;
    for(int i = 0; i < n; ++i)  a[i] &= XorSum;
    int Rank = 0;
    vector<int> digitpop(n);
    for(int d = 60; d >= 0; --d){
        bool update = false;
        for(int i = Rank; i < n; ++i){
            if((a[i] >> d) & 1){
                if(i != Rank)   swap(a[i], a[Rank]);
                update = true;
                break;
            }
        }
        digitpop[Rank] = d;
        if(update){
            for(int i = 0; i < n; ++i){
                if(i == Rank)   continue;
                if((a[i] >> d) & 1) a[i] ^= a[Rank];
            }
            ++Rank;
        }
    }

    ll MoveUpSum = 0;
    for(int d = 60; d >= 0; --d){
        ll next = MoveUpSum | (1ll << d);
        ll foo = next;
        for(int i = 0; i < Rank; ++i){
            if((foo >> digitpop[i]) & 1)    foo ^= a[i];
        }
        if((foo & next) == 0)   MoveUpSum = next;
    }
    // for(int i = 0; i < n; ++i)  cerr << bitset<60>(a[i]) << "\n";
    // cerr << bitset<60>(MoveUpSum) << "\n";
    ans += MoveUpSum * 2;
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e9;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<vector<ll>> dp(62,vector<ll>(3,0));
    dp[61][0] = 1;
    for (ll i = 60;i >= 0;i--){
        if (n&(1ll<<i)){
            dp[i][0] = dp[i+1][0];
            dp[i][1] = (dp[i+1][1]+dp[i+1][0])%MOD;
            dp[i][2] = (3*dp[i+1][2]+2*dp[i+1][1])%MOD;
        }
        else{
            dp[i][0] = (dp[i+1][0]+dp[i+1][1])%MOD;
            dp[i][1] = dp[i+1][1];
            dp[i][2] = (3*dp[i+1][2]+dp[i+1][1])%MOD;
        }
    }
    PRINT((dp[0][0]+dp[0][1]+dp[0][2])%MOD);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int x, k, d;
    cin >> x >> k >> d;
    if(x >= 0)
    {
        int rem = x/d;
        if(rem >= k)
            cout << (x - k*d);
        else
        {
            x = x - rem*d;
            k = k - rem;
            if(k%2 == 1)
            {
                // if(abs(x-d) < x)
                //     cout << abs(x-d);
                // else
                //     cout << x;
                cout << abs(x-d);
            }
            else
                cout << x;
        }
    }
    else
    {
        int rem = (-x)/d;
        if(rem >= k)
            cout << abs(x + k*d);
        else
        {
            x = x + rem*d;
            k = k - rem;
            if(k%2 == 1)
            {
                // if(abs(x+d) < abs(x))
                //     cout << abs(x+d);
                // else
                //     cout << abs(x);
                cout << abs(x+d);
            }
            else
                cout << abs(x);
        }
    }

}

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, R: int, S: int, P: int, T: str):
    ret = 0
    a = []
    for i, c in enumerate(T):
        if c == 'r' and not (i >= K and a[i - K] == c):
            ret += P
            a.append('r')
        elif c == 's' and not (i >= K and a[i - K] == c):
            ret += R
            a.append('s')
        elif c == 'p' and not (i >= K and a[i - K] == c):
            ret += S
            a.append('p')
        else:
            a.append('g')
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    T = next(tokens)  # type: str
    solve(N, K, R, S, P, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4212
if __file__.startswith('/tmp/'):
	import sys; sys.stdin = open('input.txt')

n, k = map(int, raw_input().split())
d = ''.join(raw_input().split())

l = len(str(n)) + 1

m = n
while True:
	s = str(m)
	ok = True
	for c in s:
		if c in d:
			ok = False
			break
	if ok:
		print s
		break
	m += 1


Measured memory_bytes: 2824