akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define TEMP_T template<typename T>
TEMP_T void sort(T& v){ sort(v.begin(), v.end()); }
TEMP_T void revs(T& v){ reverse(v.begin(), v.end()); }
TEMP_T void uniq(T& v){ sort(v); v.erase(unique(v.begin(), v.end())); }
TEMP_T T    cums(T& v){ T r(v.size()); partial_sum(v.begin(), v.end(), r); return r; }
TEMP_T void show(T& v, char delim=' ', char end='\n'){ for(int i=0; i<v.size()-1; i++) cout << v[i] << delim; cout << v[v.size()-1] << end; }
TEMP_T T    acum(vector<T>& v, T b=0){ return accumulate(v.begin(), v.end(), b); }
TEMP_T vector<T> inpt(int n){ vector<T> v(n); for (int i=0; i<n; i++) cin >> v[i]; return v; }

static inline int in(){ int x; scanf("%d", &x); return x; }

struct Solver {
  Solver(){}
  int solve(){
  }
};

int main()
{
  int n;
  while (n = in()){
    vector<pair<int, int> > vs;
    for (int i = 0; i < n; i++){
      int cost, lim;
      cost = in();
      lim = in();
      vs.push_back(make_pair(lim, cost));
    }
    sort(vs);
    int tc = 0;
    bool ok = true;
    for (int i = 0; i < n; i++){
      if (vs[i].first < tc){
        ok = false;
        break;
      }
      tc += vs[i].second;
      if (vs[i].first < tc){
        ok = false;
        break;
      }
    }
    if (ok) puts("Yes");
    else puts("No");
  }
  return (0);
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rev(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rev2(i, s, n) for (int i = (int)(n) - 1; i >= (int)(s); i--)
#define bitrep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define all(v) v.begin(), v.end()
#define println(x) cout << x << endl
#define fi first
#define se second
#define Yes println("Yes")
#define No println("No")
#define YES println("YES")
#define NO println("NO")
using pii = pair<int, int>;

int main()
{
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    rep(i, 10)
    rep(j, 10)
    rep(k, 10)
    {
        vector<char> vc(3);
        vc[0] = '0' + i;
        vc[1] = '0' + j;
        vc[2] = '0' + k;
        int idx = 0;
        rep(l, s.size())
        {
            if (s[l] == vc[idx])
            {
                idx++;
                if (idx == 3)
                {
                    cnt++;
                    break;
                }
            }
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3708
#include <stdio.h>
long long lucas(int n){ //リュカ数列 int型だとoverflowするのでdouble型
    int i;
    long long a=2,b=1,c;
    for(i=1;i<n;i++){
        c=a+b;
        a=b;
        b=c;
    }
    return b;
}
int main(void){
    int n;
    scanf("%d",&n);
    printf("%ld\n",lucas(n));
    return 0;
}


Measured memory_bytes: 128
//JOI2010-2011本選問４歩くサンタクロース(Walking Santa)
#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
int main(){

	long long sum = 0LL, osum = 0LL;
	long long f1, f2, f3, w, h, L, HL, temp, oxy[2][2], *LXY[2], ox, oy, max = 0;
	deque<long long> XY[2];
	scanf("%lld %lld",&w, &h);
	scanf("%lld",&L);
	for(f1 = 0; f1 < 2; f1++)
		LXY[f1] = new long long [L];
	//100k
	for(f1 = 0; f1 < L; f1++){
		scanf("%lld %lld",&LXY[0][f1], &LXY[1][f1]);
		XY[0].push_back(LXY[0][f1]);
		XY[1].push_back(LXY[1][f1]);
	}
	//1m
	stable_sort( XY[0].begin(), XY[0].end() );
	stable_sort( XY[1].begin(), XY[1].end() );
	HL = (L + 1) / 2;
	//x軸での最小値の点、y軸での最小値の点を探す
	//200k
	if(L == 1){
		printf("0\n");
		printf("%lld %lld\n",LXY[0][0],LXY[1][0]);
	}
	else{
		for(f1 = 0; f1 < 2; f1++){
			oxy[0][f1] = XY[f1][HL-1];
			oxy[1][f1] = XY[f1][HL];
		}
		//400k
		for(f2 = 0; f2 < 2; f2++){
			for(f3 = 0; f3 < 2; f3++){
				sum = 0LL;
				max = 0LL;
				for(f1 = 0; f1 < L; f1++){
					temp = (long long)abs(LXY[0][f1] - oxy[f2][0]) + abs(LXY[1][f1] - oxy[f3][1]);
					sum += temp * 2;
					if(max < temp)
						max = temp;
				}
				sum -= max;
				if(osum == 0 || osum > sum){
					osum = sum;
					ox = oxy[f2][0];
					oy = oxy[f3][1];
				}
			}
		}
		printf("%lld\n", osum);
		printf("%lld %lld\n", ox, oy);
	}
	return 0;
}

Measured memory_bytes: 4708
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define int long long

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

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n, m;
int l[100100], r[100100], c[100100];
int dist[100100];
vector<pii> edge[100100];

signed main() {

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        edge[i+1].bash({i, 0});
    }
    
    for(int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> c[i];
        edge[l[i]].bash({r[i], c[i]});
        edge[r[i]].bash({l[i], c[i]});
    }

    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push({0, 1});
    
    while(!que.empty()) {
        int c = que.top().first;
        int u = que.top().second;
        que.pop();
        if(dist[u] != c) continue;
        for(auto&&i:edge[u]) {
            int v = i.first;
            int pc = i.second;
            if(dist[v] > c + pc) {
                dist[v] = c + pc;
                que.push({dist[v], v});
            }
        }
    }
    if(dist[n] == LINF) dist[n] = -1;
    
    cout << dist[n] << endl;
  
    return 0;
}



Measured memory_bytes: 15732
//package beginner176;

import java.util.Scanner;

public class Main {


    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int max = 0;

        long result = 0;
        for(int i = 0; i < N; i++){
            int x = in.nextInt();
            if(x < max){
                result += max - x;
            }
            max = Math.max(max, x);
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 59960
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    auto n = lread();
    auto a = aryread();
    auto ans = new long[](2 * (10 ^^ 5) + 10);
    foreach (i; 0 .. n - 1)
    {
        ans[a[i]] += 1;
    }
    foreach (i; 1 .. n + 1)
    {
        writeln(ans[i]);

    }

}
//https://rclone.org/

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


Measured memory_bytes: 12608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

char another(char c){
    if(c == 'S') return 'W';
    else return 'S';

}

int main(){
    int n;
    string s;
    cin >> n >> s;
    string S[4] = {"SS", "SW", "WS", "WW"};
    for(int j = 0; j < 4; j++){
        bool flag = true;
        for(int i = 1; i < n-1; i++){
            if((S[j][i] == 'S' && s[i] == 'o') || (S[j][i] == 'W' & s[i] == 'x')){
                S[j] += S[j][i-1];
            }
            else{
                S[j] += another(S[j][i-1]);
            }
        }
        if((S[j][n-1] == 'S' && s[n-1] == 'o') || (S[j][n-1] == 'W' & s[n-1] == 'x')){
            if(S[j][0] != S[j][n-2]) flag = false;
        }
        else{
            if(S[j][0] == S[j][n-2]) flag = false;
        }
        if(!flag) continue;
        
        if((S[j][0] == 'S' && s[0] == 'o') || (S[j][0] == 'W' & s[0] == 'x')){
            if(S[j][1] != S[j][n-1]) flag = false;
        }
        else{
            if(S[j][1] == S[j][n-1]) flag = false;
        }
        if(flag){
            cout << S[j] << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  int ans = 0;
  rep(i,4) if(s[i]=='+') ++ans; else --ans;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define Max 1000000

void printA(int A[Max], int N) {
	int i;

	for (i = 0; i < N - 1; i++)
		printf("%d ", A[i]);
	printf("%d\n", A[i]);
}

int insertionSort(int A[Max], int N, int g) {
	int i, j, v;
	int cnt = 0;

	for (i = g; i < N; i++) {
		v = A[i];
		j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = v;
	}

	return cnt;
}

void shellSort(int A[Max], int N) {
	int i = 0;
	int cnt = 0;
	int m = 0;
	int box[20];
	int G[Max];


	box[0] = 1;
	for (i = 1; i < 20; i++) box[i] = 3 * box[i - 1] + 1;

	for (i = 20 - 1; i >= 0; i--) {
		if (box[i] <= N) G[m++] = box[i];
	}

	printf("%d\n", m);

	printA(G, m);

	for (i = 0; i < m; i++) cnt += insertionSort(A, N, G[i]);

	printf("%d\n", cnt);

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

int main( ) {
	int N, i, j;
	int A[Max];

	scanf("%d", &N);

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

	shellSort(A, N);

	return 0;
}

Measured memory_bytes: 4512
#include <iostream>

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int n = 0;
  for (int i = a; i <= b; ++i) {
    if (c % i == 0)
      ++n;
  }
  cout << n << endl;
  return 0;
}

Measured memory_bytes: 3080
#include<stdio.h>
int main(void){
	int t[3][3][3], i, j, k;
	for (i = 0; i < 3; i++){
		for (j = 0; j < 2; j++){
			for (k = 0; k < 3; k++){
				scanf("%d", &t[i][j][k]);
			}
		}
	}
	for (i = 0; i < 3; i++){
		for (j = 0; j < 2; j++){
			t[i][j][2] += t[i][j][1] * 60 + t[i][j][0] * 3600;
		}
		t[i][0][2] = t[i][1][2] - t[i][0][2];
		t[i][2][0] = t[i][0][2] / 3600;
		t[i][0][2] %= 3600;
		t[i][2][1] = t[i][0][2] / 60;
		t[i][2][2] = t[i][0][2] % 60;
	}
	for (i = 0; i < 3; i++){
		for (j = 0; j < 2; j++){
			printf("%d ", t[i][2][j]);
		}
		printf("%d\n",t[i][2][2]);
	}
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<long long int> L(N);
    int i, j, k;
    int ans = 0;
    

    
    for(i=0;i<N;i++){
        cin >> L.at(i);
    }

    if(N < 3){
        cout << 0 << endl;
        return 0;
    }

    

    for(i=0;i<(N-2);i++){
        for(j=i+1;j<(N-1);j++){
            for(k=j+1;k<N;k++){
                if((L.at(i) == L.at(j)) || (L.at(k) == L.at(j)) || (L.at(i) == L.at(k))){
                    continue;
                }
                if(((L.at(i)+L.at(j))>L.at(k)) && ((L.at(j)+L.at(k))>L.at(i)) && ((L.at(k)+L.at(i))>L.at(j))){
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;


}

Measured memory_bytes: 3608
#include<stdio.h>
 
#define MAX 45
 
int fibonacci(int);
int F[MAX];
 
int main(){
 
  int n;
 
  scanf("%d",&n);
 
  printf("%d\n",fibonacci(n));
 
  return 0;
}
 
int fibonacci(int n){
 
  if(n == 0 || n == 1) return F[n] = 1;
  else if(F[n] > 0) return F[n];
  else return F[n] = fibonacci(n-2) + fibonacci(n-1);
}
    

Measured memory_bytes: 596
// #include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define trace(x) cerr << #x << ": " << x << " " << endl;
 
typedef int64_t ll;
 
#define endl '\n'
#define int ll
ll mod=1e9+7;
ll mod1=1e9+5;
ll power(ll a,ll b)
{
    if(b==0) return 1;
    else if(b%2==0)
        return power(((((a)%mod)*((a)%mod))%mod),b/2)%mod;
    else return (((a)%mod)*(power(((((a)%mod)*((a)%mod))%mod),b/2)%mod))%mod;
}
inline ll inverse(ll a) {
  a %= mod;
  if (a < 0) a += mod;
  ll b = mod, u = 0, v = 1;
  while (a) {
    ll t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += mod;
  return u;
}
  
  
 //using namespace __gnu_pbds;
 //#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
//find_by_order(k)  returns iterator to kth element starting from 0;
//order_of_key(k) returns count of elements strictly smaller than k;
//erase,insert same as normal set
// mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count()); for randomized solution
ll fastmod(ll x)
{
    return x<mod?x:x%mod;
}
int32_t main()
{
    IOS

    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.length();i++)
    {
        map<char,int> m;
        for(int j=i;j<s.length();j++)
        {
            if(j-i+1<=2)
            {
                m[s[j]]++;
                continue;
            }
            else
            {
                m[s[j]]++;
                char ch='R'+'G'+'B'-s[i]-s[j];
                if((j+i)%2)
                {
                    ans+=m[ch];
                }
                else
                {
                    int k=(j+i)/2;
                    ans+=m[ch];
                    if(s[k]==ch)
                        ans--;
                }
            }
        }
    }
    cout<<ans<<endl;
}       

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

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

	string ans = "None";
	for( char a = 'a'; a <= 'z'; a++ ) {
		if( S.find( a ) == string::npos ) {
			ans = string( 1, a );
			break;
		}
	}

	cout << ans << endl;
}


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

const int N = 111;
const int fac7 = 5040;

int d[N], a[N];
int dp[N][fac7];

int ptoi(int *p) {
	int r = 0, t = 1;
	for(int i = 0; i < 7; i ++) {
		int c = 0;
		for(int j = 0; j < i; j ++)
			if(p[j] < p[i]) c ++;
		r += c * t;
		t *= i + 1;
	}
	return r;
}

int main() {
	ios :: sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i <= n; i ++) cin >> d[i];
	for(int i = 1; i <= n; i ++) cin >> a[i];

	int ans = 0;
	int m = min(n, 7);
	int p[8]; iota(p, p + m, 0);
	do {
		int tmp = 0;
		for(int i = 1; i <= m; i ++)
			for(int j = 1; j <= m; j ++)
				if(p[i - 1] < p[j - 1] && abs(i - j) <= d[i]) tmp += a[i];
		ans = max(ans, tmp);
		if(m == 7) dp[7][ptoi(p)] = tmp;
	} while(next_permutation(p, p + m));
	if(n > 7) {
		for(int i = 8; i <= n; i ++) {
			iota(p, p + 8, 0);
			do {
				int tmp = 0, s = ptoi(p), t = ptoi(p + 1);
				for(int j = 0; j < 7; j ++) {
					if(7 - j <= d[i] && p[7] < p[j]) tmp += a[i];
					if(7 - j <= d[i - 7 + j] && p[j] < p[7]) tmp += a[i - 7 + j];
				}
				dp[i][t] = max(dp[i][t], dp[i - 1][s] + tmp);
			} while(next_permutation(p, p + 8));
		}
		ans = *max_element(dp[n], dp[n] + fac7);
	}
	cout << ans << '\n';
}

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

using namespace std;

priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q[265000];
set <pair<int,int>> Se[265000];

int main()
{
    int n, l, a, Si, b, S, I, Ma=0;
    cin >> n;
    Si = (1 << n);
    for (int i = 0; i < Si; i++)
    {
        cin >> a;
        Q[i].push({a,i});
        Se[i].insert({a,i});
        while (Q[i].size() > 2)
        {
            Se[i].erase(Se[i].find({Q[i].top().first, Q[i].top().second}));
            Q[i].pop();
        }
        S = 0;
        while (Q[i].size() > 0)
        {
            S += Q[i].top().first;
            I = Q[i].top().second;
            for (int u = 0; u < n; u++)
            {
                if (((1 << u) & i) == 0)
                {
                    b = i | (1 << u);
                    if (Se[b].find({Q[i].top().first,I}) == Se[b].end())
                    {
                        Q[b].push({Q[i].top().first, I});
                        Se[b].insert({Q[i].top().first, I});
                        while (Q[b].size() > 2)
                        {
                            Se[b].erase(Se[b].find({Q[b].top().first,Q[b].top().second}));
                            Q[b].pop();
                        }
                    }
                }
            }
            Se[i].erase(Se[i].find({Q[i].top().first,I}));
            Q[i].pop();
        }
        if (i != 0)
        {
            Ma = max(Ma, S);
            cout << Ma << "\n";
        }
    }
    return 0;
}


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

constexpr int MaxN = 100000;
constexpr int MaxM = 100000;

int main()
{
	int N, M;
	vector<pair<int, int>> vec;

	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		vec.push_back(pair<int, int>(a, b));
	}

	sort(vec.begin(), vec.end(), [](pair<int, int> s, pair<int, int> t) { return s.second < t.second; });

	int count = 0;
	vector<int> filters;
	for (auto v : vec)
	{
		bool test = true;
		for (auto f : filters)
		{
			if (v.first < f)
			{
				test = false;
			}
		}

		if (test || filters.size() == 0)
		{
			filters.push_back(v.second);
			++count;
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 1528
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    int n,i,l,j;
    char s[105][105],aux[105];
    cin >> n>>l;
    for (i=1;i<=n;++i)
        cin>>s[i];
        
    for (i=1;i<n;++i)
        for (j=i+1;j<=n;++j)
            if (strcmp(s[i],s[j])>0) {
                strcpy(aux,s[i]);
                strcpy(s[i],s[j]);
                strcpy(s[j],aux);
            }

    for (i=1;i<=n;++i)
        cout<<s[i];
        
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[3];

int main() {
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if (a[0] == 5 && a[1] == 5 && a[2] == 7) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll dpL[200000][2];
ll dpR[200000][2];
ll sumL[200000];
ll sumR[200000];
ll A[200000];
int main() {
	int N;
	cin >> N;
	if (N == 1) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sumL[0] = A[0];
	for (int i = 1; i < N; i++) sumL[i] = A[i] + sumL[i - 1];
	sumR[N - 1] = A[N - 1];
	for (int i = N - 2; i >= 0; i--) sumR[i] = A[i] + sumR[i + 1];
	fill((ll*)dpL, (ll*)(dpL + N), 1LL << 60);
	fill((ll*)dpR, (ll*)(dpR + N), 1LL << 60);
	dpL[0][0] = (A[0] % 2 == 0);
	dpL[0][1] = A[0] % 2;
	dpR[N - 1][0] = (A[N - 1] % 2 == 0);
	dpR[N - 1][1] = A[N - 1] % 2;
	for (int i = 1; i < N; i++) {
		if (A[i] == 0) {
			dpL[i][0] = min(dpL[i - 1][0], dpL[i - 1][1]) + 1;
			dpL[i][1] = min(sumL[i], dpL[i - 1][1] + 2);
		}
		else {
			dpL[i][0] = min(dpL[i - 1][0], dpL[i - 1][1]) + (A[i] % 2 == 0);
			dpL[i][1] = min(sumL[i], dpL[i - 1][1] + (A[i] % 2));
		}
	}
	for (int i = N - 2; i >= 0; i--) {
		if (A[i] == 0) {
			dpR[i][0] = min(dpR[i + 1][0], dpR[i + 1][1]) + 1;
			dpR[i][1] = min(sumR[i], dpR[i + 1][1] + 2);
		}
		else {
			dpR[i][0] = min(dpR[i + 1][0], dpR[i + 1][1]) + (A[i] % 2 == 0);
			dpR[i][1] = min(sumR[i], dpR[i + 1][1] + (A[i] % 2));
		}
	}
	ll ans = 1LL << 60;
	ans = min(ans, dpL[N - 1][0]);
	ans = min(ans, dpL[N - 1][1]);
	ans = min(ans, dpR[0][0]);
	ans = min(ans, dpR[0][1]);
	for (int i = 0; i + 1 < N; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				if (j == 0 && k == 0) continue;
				ans = min(ans, dpL[i][j] + dpR[i + 1][k]);
			}
		}
	}
	cout << ans << endl;
}

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

vector<int>v,dp;

void solve(){
	int n,k;cin>>n>>k;
	dp.resize(n,-1);
	v.resize(n);

	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	dp[0]=0;
	for(int i=1;i<n;i++){
        int mn=INT_MAX;
        for(int j=1;j<=k;j++){
            if(i-j>=0){
                mn = min(mn,dp[i-j]+abs(v[i]-v[i-j]));
            }
        }
		dp[i]=mn;
	}
	cout<<dp[n-1]<<"\n";

}
int main(){
	int t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 1024
import java.util.*;

class Main {
    Scanner sc = new Scanner(System.in);

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

    private void run() {
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] a = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            a[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            int s = sc.nextInt();
            int c = sc.nextInt();
            if (a[s] != -1 && a[s] != c || s == 1 && c == 0 && n > 1) {
                System.out.println(-1);
                return;
            }
            a[s] = c;
        }

        StringBuilder sb = new StringBuilder();

        if (n > 1) {
            sb.append(a[1] == -1 ? 1 : a[1]);
        } else {
            sb.append(a[1] == -1 ? 0 : a[1]);
        }
        for (int i = 2; i < n+1; i++) {
            sb.append(a[i] == -1 ? 0 : a[i]);
        }
        System.out.println(sb.toString());
    }
}


Measured memory_bytes: 23124
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

s= input()
s = list(s)
for i in range(len(s)):
    if s[i] =='?':
        s[i] = 'D'
print(''.join(s))

Measured memory_bytes: 76680
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
	int n, i, j, min;
	long long abs_t;
	scanf("%d",&n);
	int a[n];
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	abs_t = 0;
	int count = 0;
	min = abs(a[0]);
	for(i=0;i<n;i++){
		abs_t += abs(a[i]);
		if(a[i]<0){
			count++;
		}
		if(min>abs(a[i]))min=abs(a[i]);
	}
	
	if(count%2==1){
		printf("%lld",abs_t-min*2);
	}else{
		printf("%lld",abs_t);
	}
	
	
	return 0;
}

Measured memory_bytes: 512
<?php
define('MOD', 10 ** 9 + 7);
list($n) = ints();
for ($i = 0; $i < $n; ++$i) list($c[]) = ints();
$dp[0] = 1;
for ($i = 1; $i <= $n; ++$i) {
    $a = $c[$i - 1];
    $dp[$i] = $dp[$i - 1];
    if ((isset($last[$a])) && $last[$a] !== $i - 1)
        $dp[$i] += $dp[$last[$a]];
    $dp[$i] %= MOD;
    $last[$a] = $i;
}
echo $dp[$n];
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 39732
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
	public static void Main()
	{
		var n = int.Parse(ReadLine());
		int i = 1;
		for(; i + i <= n; i <<= 1);
		WriteLine(i);
	}
}


Measured memory_bytes: 17604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
const long long MOD = 998244353;

template<class T>
T mod_pow(T x, T n, const T mod) {
    T res = 1;
    while(n > 0) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n = n >> 1;
    }
    return res;
}

void solve() {
    int N; cin >> N;
    vector<int> D(N);
    rep(i, N) cin >> D[i];
    if(D[0] != 0) {
        cout << 0 << '\n';
        return;
    }
    sort(D.begin(), D.end());
    vector<long long> cnt(N);
    rep(i, N) cnt[D[i]]++;
    if(cnt[0] != 1) {
        cout << 0 << '\n';
        return;
    }
    long long ans = 1;
    rep(i, N - 1) {
        ans *= mod_pow(cnt[i], cnt[i + 1], MOD);
        ans %= MOD;
    }
    cout << ans << '\n';
}

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


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, c;
  cin >> n >> c;
  int d[c + 1][c + 1], g[n][n];
  for(int i = 1; i < c + 1; i++){
    for(int j = 1; j < c + 1; j++){
      cin >> d[i][j];
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cin >> g[i][j];
    }
  }
  int line[3][31] = {0};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int lnum = (i + j) % 3;
      for(int k = 1; k < c + 1; k++){
        if(g[i][j] != k){
          line[lnum][k] += d[g[i][j]][k];
        }
      }
    }
  }
  int ans = 250000001;
  for(int i = 1; i < c + 1; i++){
    for(int j = 1; j < c + 1; j++){
      if(i == j)continue;
      for(int k = 1; k < c + 1; k++){
        if(i == k || j == k)continue;
        int cost = line[0][i] + line[1][j] + line[2][k];
        ans = min(ans, cost);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
 

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	int AC = 0, WA = 0, TLE = 0, RE = 0;
	string s;
	for (int i = 0; i < n; ++i)
	{
		/* code */
		cin >> s;
		if (s == "AC"){
			AC++;
		} else if (s == "WA"){
			WA++;
		} else if (s == "TLE"){
			TLE++; 
		} else if (s == "RE"){
			RE++;
		}
	}
	cout << "AC x " << AC << "\n";
	cout << "WA x " << WA << "\n";
	cout << "TLE x " << TLE << "\n";
	cout << "RE x " << RE << "\n";


	return 0;
}



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

int main () {
  string s, ans = "Yes";
  cin >> s;
  
  sort(s.begin(), s.end());
  
  int a = 0, b = s.size();
  for (int i = 0; i < b; i++) {
    a++;
    if (i+1 == b) {
      if (a%2 == 1) {
        ans = "No";
        break;
      }
    }
    else if (s[i] != s[i+1]) {
      if (a%2 == 1) {
        ans = "No";
        break;
      }
      a = 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int a[n];
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
    }
 int c[n];
  c[0]=0;
  for(int i=1;i<n;i++)
    c[i]=INT_MAX;
  
  for(int i=1;i<n;i++)
  {
     int j=i;
    for(int j=i-1;j>=i-k;j--)
    {
      if(j<0)
      {
        break;
      }
      else
      {
        c[i]=min(c[i],c[j]+abs(a[i]-a[j]));
      }
    }
  }
                 cout<<c[n-1];
}

Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define pb push_back
#define f first
#define s second
#define double long double
const int MAX=2e5+5;
const int MAX2=2e5+4;
const int MAAX=1e10;
const int MOD=1e9+7;

int x,y,a,b,c;
int r[MAX],g[MAX],nc[MAX];
in main()
{
  cin>>x>>y>>a>>b>>c;
  for(int i=0;i<a;i++)
  {
      scanf("%lld",&r[i]);
      r[i]*=-1;
  }
  for(int i=0;i<b;i++)
  {
     scanf("%lld",&g[i]);
     g[i]*=-1;
  }
  for(int i=0;i<c;i++)
  {
      scanf("%lld",&nc[i]);
      nc[i]*=-1;
  }
  sort(r,r+a);
  sort(g,g+b);
  sort(nc,nc+c);
  vector<int>ans;
  for(int i=0;i<x;i++)
  {
      ans.pb(-r[i]);
  }
  for(int i=0;i<y;i++)
  {
      ans.pb(-g[i]);
  }
  sort(ans.begin(),ans.end());
  int idx=0;
  for(int i=0;i<c;i++)
  {
      if(idx<ans.size()&&ans[idx]<-nc[i])
      {
          ans[idx++]=-nc[i];
      }
  }
  int anss=0;
  for(int i=0;i<ans.size();i++)
    anss+=ans[i];
  cout<<anss<<endl;
 return 0;
}


Measured memory_bytes: 5748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


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

    if(abs(n-k)%2==0){
        cout << (abs(n-k)/2)+min(n,k) << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;

}


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

int main() {
  int n;
  cin >> n;
  
  cout << n << ":";
  while (n > 1) {
    // 約数を探す
    const double sqrtn = sqrt(n);
    for (int i=2; i<=sqrtn; i++) {
      if (n % i == 0) {
	// iが約数
	cout << " " << i;
	n /= i;
	goto LAST;
      }
    }
    // nは素数なので終了
    cout << " " << n << endl;
    break;
    
    LAST: 0;
  }
  
  return 0;
}


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

using namespace std;
using ll = long long;

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    int A, B, C;
    cin>>A>>B>>C;
    if((A==B && B==C)&&(A%2==0)){
        cout<<-1<<endl;
        return 0;
    }
    
    int cnt=0;
    while(!(A%2||B%2||C%2)){
        int nA=B/2+C/2, nB=A/2+C/2, nC=A/2+B/2;
        ++cnt;
        A=nA, B=nB, C=nC;
    }
    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);
    vector<ll> a(n),b(n);
    int i;
    for(i=0; i<n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a.begin(), a.end());
    ll mid=(n%2? a[n/2]*2: a[n/2-1]+a[n/2]);

    for(i=0; i<n; i++) {
        b[i]=abs(2*a[i]-mid);
    }
    sort(b.begin(),b.end());

    ll sum=0;
    for(i=0; i<n; i++) {
        if(i<2) sum+=b[i];
        else  sum+=b[i]*2;
    }
    printf("%lld\n", sum/2);


    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T; scanf("%d", &T);
    while(T--) {
        solve();
    }
#endif
    return 0;
}


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

vector<char> s;
int n;

int count(int N, int A) {
  int c = 0;
  for(int i = N; i < n; i++) { // NをN-1にする？
    if(s.at(i) == 'R') break;
    c++;
    if(c >= A) {
      c = -1;
      break;
    }
  }
  return c;
}

int main() {
  cin >> n;
  int w = 0, r = 0;
  s = vector<char>(n);
  for(int i = 0; i < n; i++) {
    cin >> s.at(i);
    if(s.at(i) == 'W') w++;
    else r++;
  }
  int anser = 0;
  int p = 0;
  if(w != 0 && r != 0) {
    while(r > 0) {
      int x = count(p, r);
      if(x == -1) {
        anser += r;
        break;
      }
      else {
        anser += x;
        r -= (x + 1);
      }
      p += (x + 1);
    }
  }
  cout << anser << endl;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

#define ri(b,c) for(ll i=(b);i<(c);++i)
#define rj(b,c) for(ll j=(b);j<(c);++j)
#define rk(b,c) for(ll k=(b);k<(c);++k)
#define rl(b,c) for(ll l=(b);l<(c);++l)
#define rr(b,c) for(ll r=(b);r>(c);--r)
#define fcout cout<<fixed<<setprecision(10)
#define a_m a,b,c,d,e,f,g,h,i,j,k,l,m
#define n_z n,o,p,q,r,s,t,u,v,w,x,y,z
#define p50 614889782588491410
#define isprime(a) gcd(p50,a)==1

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

	ll a_m,n_z;
	cin>>n>>m>>d;
    p=d?2*(n-d):n;

    fcout<<double(m-1)*p/(n*n)<<"\n";
}


Measured memory_bytes: 256
class Dice

    attr_accessor :dice_pos_1,:dice_pos_2,:dice_pos_3,:dice_pos_4,:dice_pos_5,:dice_pos_6
    def initialize(dice_num:[])
        @dice_pos_1 = dice_num[0]
        @dice_pos_2 = dice_num[1]
        @dice_pos_3 = dice_num[2]
        @dice_pos_4 = dice_num[3]
        @dice_pos_5 = dice_num[4]
        @dice_pos_6 = dice_num[5]
    end
    def parse_spin(spin_directions:[])
        spin_directions.each do |spin|
            if spin == "N"
                turn_north()
            elsif spin == "S"
                turn_south()
            elsif spin == "W"
                turn_west()
            elsif spin == "E"
                turn_east()
            end
        end
        return self
    end
    def turn_north
        @dice_pos_1,@dice_pos_2,@dice_pos_5,@dice_pos_6 = @dice_pos_2,@dice_pos_6,@dice_pos_1,@dice_pos_5
    end
    def turn_south
        @dice_pos_1,@dice_pos_2,@dice_pos_5,@dice_pos_6 = @dice_pos_5,@dice_pos_1,@dice_pos_6,@dice_pos_2
    end
    def turn_west
        @dice_pos_1,@dice_pos_3,@dice_pos_4,@dice_pos_6 = @dice_pos_3,@dice_pos_6,@dice_pos_1,@dice_pos_4
    end
    def turn_east
        @dice_pos_1,@dice_pos_3,@dice_pos_4,@dice_pos_6 = @dice_pos_4,@dice_pos_1,@dice_pos_6,@dice_pos_3
    end
end

dice = Dice.new(dice_num:gets.split.map(&:to_i))
puts dice.parse_spin(spin_directions: gets.chomp.split("")).dice_pos_1


Measured memory_bytes: 6864
#define NDEBUG
NDEBUG


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>


using namespace std;

template<class T>
using vec = std::vector<T>;

template<class T>
using vec2d = std::vector<std::vector<T>>;


template<class T>
vec2d<T> makeVec2d(const int n1) {
  return vec2d<T>(n1);
}


template<class T>
vec2d<T> makeVec2d(const int n1, const int n2, const T initValue) {
  return vec2d<T>(n1, vec<T>(n2, initValue));
}


#define FOR(i, n) for (int i = 0; i < (n); ++i)
#define FORA(i, a, n) for (int i = (a); i < (n); ++i)


// TC_REMOVE_BEGIN
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
// TC_REMOVE_END


template<class T>
inline T mx(T arg) {
    return arg;
}

template<class T, class... Ts>
inline typename common_type<T, Ts...>::type mx(T arg, Ts... args) {
    auto arg1 = mx(args...);
    return arg > arg1 ? arg : arg1;
}


// Section with adoption of array and vector algorithms.


//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//
//template <class T> using StdTree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    template<int N>
    struct bytetype {
        
    };

    
    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vec(istream& in, size_t n) {
  vector<T> ret(n);
  for (size_t i = 0; i < n; ++i) {
    ret[i] = next<T>(in);
  }
  return ret;
}


void solve(istream& in, ostream& out) {
  auto n = next<int>(in);
  vec2d<int> a = makeVec2d<int>(n);
  FOR(i, n) {
    a[i] = next_vec<int>(in, 3);
  }
  auto f = makeVec2d<int>(n, 3, numeric_limits<int>::min() / 2);
  FOR(i, 3) {
    f[0][i] = a[0][i];
  }
  FORA(i, 1, n) {
    FOR(j, 3) {
      FOR(k, 3) {
        if (j != k) {
          f[i][k] = max(f[i][k], f[i-1][j] + a[i][k]);
        }
      }
    }
  }
  out << mx(f[n-1][0], f[n-1][1], f[n-1][2]) << "\n";
}

//#include <fstream>


int main() {
//  ifstream fin("bridges.in");
//  ofstream fout("bridges.out");
    solve(cin, cout);
//  solve(fin, fout);
    return 0;
}



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

char s[100];
int main() {
	int n; scanf("%d", &n);
	list<int>ls;
	rep(i, n) {
		scanf("%s", s);
		if (!strcmp(s, "insert")) {
			int x; scanf("%d", &x);
			ls.push_front(x);
		}
		else if (!strcmp(s, "delete")) {
			int x; scanf("%d", &x);
			auto it = find(ls.begin(), ls.end(), x);
			if (it != ls.end())ls.erase(it);
		}
		else if (!strcmp(s, "deleteFirst"))ls.pop_front();
		else ls.pop_back();
	}
	for (auto it = ls.begin(); it != ls.end(); it++) {
		printf("%d", *it);
		if (it != --ls.end())printf(" ");
	}
	printf("\n");
}

Measured memory_bytes: 34432
#include <bits/stdc++.h>
using namespace std;
int a[100005];
struct nu
{
    int num,ti;
}b[100005];
int main()
{
    int n,i,j,k,kk,ans;ans=k=kk=0;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
   // b[1].num=a[1];
    //b[1].ti=1;
    for(i=1;i<=n;i++)
    {
        if(a[i]==b[k].num)
            b[k].ti+=1;
        else
            {b[++k].num=a[i];
            b[k].ti+=1;}
    }
    for(i=1;i<=k;i++)
    {
        if(b[i].num>b[i].ti)
            ans+=b[i].ti;
        else if(b[i].num<b[i].ti)
            ans=ans+b[i].ti-b[i].num;

    }
    printf("%d",ans);
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)

int main(){
    bool C[52][52] = {};
    int H,W;
    int R=0;
    int B=0;
    cin >> H >> W;
    rep(i,H){
        string s;
        cin >> s;
        rep(j,W){
            if(s[j]=='.'){
                C[i+1][j+1] = true;
            }else{
                C[i+1][j+1] = false;
                B++;
            }
        }
    }
    queue<tuple<int,int,int>> que;//n,h,w
    que.push(make_tuple(1,1,1));
    C[1][1] = 0;
    while(!que.empty()){
        auto q = que.front();
        que.pop();
        int n = get<0>(q);
        int h = get<1>(q);
        int w = get<2>(q);
        if(h == H && w == W){ R = n; break; }
        if(C[h][w+1])que.push(make_tuple(n+1,h,w+1));
        if(C[h][w-1])que.push(make_tuple(n+1,h,w-1));
        if(C[h+1][w])que.push(make_tuple(n+1,h+1,w));
        if(C[h-1][w])que.push(make_tuple(n+1,h-1,w));
        C[h][w+1] = 0;
        C[h][w-1] = 0;
        C[h+1][w] = 0;
        C[h-1][w] = 0;
    }
    if(R){
        cout << H*W - R - B << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}

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

long n,w,w1,a,b,ans=0;
vector<vector<long>> p(4,vector<long>(0));

void saiki(long ii,long aaa,long bbb) {
  if(ii==4) {
    ans=max(ans,aaa);
    return;
  }
  saiki(ii+1,aaa,bbb);
  for(long i=0;i<p[ii].size();i++) {
    if((w1+ii)*(i+1)+bbb>w) break;
    saiki(ii+1,aaa+p[ii][i],bbb+(w1+ii)*(i+1));
  }
  return;
}

int main() {
  cin >> n >> w;
  cin >> w1 >> b;
  p[0].push_back(b);
  for(long i=1;i<n;i++) {
    cin >> a >> b;
    p[a-w1].push_back(b);
  }
  for(long i=0;i<4;i++){
    sort(p[i].begin(),p[i].end());
    reverse(p[i].begin(),p[i].end());
    for(long j=1;j<p[i].size();j++) {
      p[i][j]=p[i][j-1]+p[i][j];
    }
  }
  saiki(0,0,0);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*
直径がもともとK以下なら0でよくて、Kより大きいならちょうどKにしたいはず
根付き木で考えた場合、全部深さがK/2以下くらいならよさそう？
でも実際は、一つの葉の深さだけ大きくて残りの葉の深さを減らすだったり、そもそも根自体を使わない選択肢もある
出来上がるのも木で、距離がKになる葉の組みが存在する
それらを結んで、そこからのそれはそいつらを越さないようにするので一意に決まる
つまり？距離がKの2点を選ぶのが2e6通り
そこから進んでいくのが2e3通り？
距離がKの点はKが2だったりするとうにで沢山
距離がKの点でも一回見たやつはなくすとかで案外？
やってみよう！
*/
int d[2005];
struct e{int a,b,d;};
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}

signed main(){
  int n,k;cin>>n>>k;
  vector<int> edge[n];
  for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;a--;b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  int ans=0;
  if(k&1){
    queue<e> que;
    for(int a=0;a<n;a++){
      for(int b:edge[a]){
        que.push({a,b,0});
        que.push({b,a,0});
        int res=0;
        while(que.size()){
          e p=que.front();que.pop();
          int u=p.a,pre=p.b,d=p.d;
          res++;if(d==k/2)continue;
          for(int q:edge[u]){
            if(q==pre)continue;
            que.push({q,u,d+1});
          }
        }
        chmax(ans,res);
      }
    }
    cout<<n-ans<<endl;
  }
  else{
    queue<e> que;
    for(int a=0;a<n;a++){
      que.push({a,-1,0});
      int res=0;
      while(que.size()){
        e p=que.front();que.pop();
        int u=p.a,pre=p.b,d=p.d;
        res++;if(d==k/2)continue;
        for(int q:edge[u]){
          if(q==pre)continue;
          que.push({q,u,d+1});
        }
      }
      chmax(ans,res);
    }
    cout<<n-ans<<endl;
  }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

signed main() {
	int n, k;
	cin >> n >> k;
	int ans = 0;
	REP(i, n) {
		int h;
		cin >> h;
		if (h >= k) {
			ans++;
		}
	}
	col(ans);
	return 0;
}

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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 <= i; i--)
#define FOR(i, from, to) for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to) for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;
constexpr ll ll_max = numeric_limits<ll>::max();

int main()
{
  ll N, A, B;
  cin >> N >> A >> B;
  if (B < A)
  {
    cout << 0 << endl;
    return 0;
  }

  if (N == 1 && A != B)
  {
    cout << 0 << endl;
    return 0;
  }

  ll l = A * (N - 1) + B;
  ll r = A + B * (N - 1);

  cout << r-l+1 << endl;

  return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int d, g;
  cin >> d >> g;
  
  vector<int> p(d), c(d);
  for(int i = 0; i < d; i++) cin >> p.at(i) >> c.at(i);
  
  int ans = 99999;
  // 全て解く問題を2進数で管理
  for(int i = 0; i < (1 << d); i++){
    int count = 0, point = 0;
    
    for(int j = 0; j < d; j++){
      if(i & (int) pow(2, j)){
        count += p.at(j);
        point += (j + 1) * 100 * p.at(j) + c.at(j);
      }
    }
    
    for(int j = d - 1; j >= 0; j--){
      if((i & (int) pow(2, j)) == 0 && point < g){
        count += min(p.at(j) - 1, ((g - point) + (j + 1) * 100 - 1) / ((j + 1) * 100));
        point += min(p.at(j) - 1, ((g - point) + (j + 1) * 100 - 1) / ((j + 1) * 100)) * (j + 1) * 100;
        break;
      }
    }
    
    if(point >= g) ans = min(ans, count);
  }
  
  cout << ans << "\n";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;
using static System.Array;

class MainClass : Scanner
{
    static void Main()
    {
        string S = RString();
        var dic = new Dictionary<char, int>();
        for (int i = 0; i < 4; i++)
        {
            if (!dic.ContainsKey(S[i]))
            {
                dic[S[i]] = 1;
            }
            else
            {
                dic[S[i]]++;
            }
        }
        bool frag = true;
        if (dic.Count != 2) frag = false;
        else
        {
            foreach (var item in dic.Values)
            {
                if (item != 2) frag = false;
            }
        }
        WriteLine(frag?"Yes":"No");
    }
}

class Scanner
{
    public static int RInt() => int.Parse(Console.ReadLine());
    public static long RLong() => long.Parse(Console.ReadLine());
    public static string RString() => Console.ReadLine();
    public static double RDouble() => double.Parse(Console.ReadLine());

    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static string[] RStrings() => Console.ReadLine().Split();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static T1 ReadStream<T1>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadStream<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadStream<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadStream<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[3], typeof(T4));
        return (r1, r2, r3, r4);
    }
}

Measured memory_bytes: 26192