akhauriyash/Code-Regression huggingface dataset:
#include <numeric>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <string>
#include <bitset>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <set>
#include <algorithm>
#include <tuple>
#include <sstream>

using namespace std;

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; for (auto& e : a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; for (auto& e : a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; for (auto& r : a) { for (auto& e : r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; for (auto& e : a) { cerr << e.field << " ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

#define forn(a, e) for (int a = 0; a < (int)(e); a++)
#define forr(a, s, e) for (int a = s; a < (int)(e); a++)

using i64 = long long;

template<typename T>
using Pair = array<T, 2>;

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

    i64 n;
    while (cin >> n) {
        int k;
        cin >> k;
        string s;
        cin >> s;

        auto it = unique(s.begin(), s.end());
        s.erase(it, s.end());
        logs(s);
        int c = s.size();
        int ans = min(n - 1, n - c + k * 2);
        cout << ans << endl;
    }
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define rFORq(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
int main(){
    int D;
    SCD(D);

    if (D==25) printf("Christmas");
    else if (D==24) printf("Christmas Eve");
    else if (D==23) printf("Christmas Eve Eve");
    else printf("Christmas Eve Eve Eve");
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	private static final int BIG_NUM  = 2000000000;

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int H,W;

		String work[] = new String[2];

		while(true){

			try {
				work = br.readLine().split("[\\s]+");
				if(work[0].equals("0") && work[1].equals("0"))break;

				H = Integer.parseInt(work[0]);
				W = Integer.parseInt(work[1]);

				for(int row = 0; row < H; row++){
					for(int col = 0; col < W; col++){
						System.out.printf("#");
					}
					System.out.printf("\n");
				}

				System.out.printf("\n");

			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}





Measured memory_bytes: 57840
#include "bits/stdc++.h"
using namespace std;
struct bus {
	int from;
	int to;
	int depart;
	int arrive;
};
bool operator<(const bus&l, const bus&r) {
	return l.depart < r.depart;
}
struct edge {
	int from;
	int to;
	int cost;
};
struct aa {
	int now;
	int time;
};
class Compare {
public:
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};	//aa?????????????????¶


int N, M, S, G;

int  dfs(const int start,const int goal, const vector<vector<edge>>&edges,vector<int>&memo,const vector<int>&node_id) {
	int ans = 1e7;
	priority_queue<aa,vector<aa>,Compare>que;
	que.push(aa{ start,0 });
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		for (auto e : edges[atop.now]) {
			if (e.to==goal) {
				return atop.time;
			}
			if (memo[e.to] > atop.time + e.cost) {
				memo[e.to] = atop.time + e.cost;
				que.push(aa{ e.to,atop.time+e.cost });
			}
		}
	}
	return -1;
	
}
int main() {cin >> N >> M >> S >> G;
	S--; G--;
	vector<vector<bus>>buss(N);
	for (int i = 0; i < M; ++i) {
		int u, v, t, c; cin >> u >> v >> t >>c;
		buss[u-1].push_back(bus{ u - 1,v - 1,t,t+c });
	}
	for (int i = 0; i < N; ++i) {
		sort(buss[i].begin(), buss[i].end());
	}
	
	const int start = 0;
	vector<int>node_id(N);
	int num = 1;
	for (int i = 0; i < N; ++i) {
		node_id[i] = num;
		num += buss[i].size();
	}
	const int goal = num;
	vector<vector<edge>>edges(num+1);
	vector<int>memo(num, 1e8);
	edges[start].push_back(edge{ start,node_id[S],buss[S][0].depart });
	

	for (int from_stop = 0; from_stop < N; ++from_stop) {
		for (int i = 0; i < buss[from_stop].size(); ++i) {
			bus b(buss[from_stop][i]);
			const int from_id = node_id[from_stop] +i;

			if (i != buss[from_stop].size() - 1) {
				edges[from_id].push_back(edge{ from_id,from_id + 1,buss[from_stop][i + 1].depart - buss[from_stop][i].depart });
			}

			auto it = lower_bound(buss[b.to].begin(), buss[b.to].end(), bus{ -1,-1,b.arrive,-1 });
			if (b.to == G) {
				edges[from_id].push_back(edge{ from_id,goal,0 });
			}
			else {
				if (it != buss[b.to].end()) {
					const int to_id = node_id[b.to] + (it - buss[b.to].begin());
					const int acost = it->depart-b.arrive;
					edges[from_id].push_back(edge{ from_id, to_id, acost });
				}
			}
			
		}
	}
	int ans=dfs(0,goal, edges, memo,node_id);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 21468
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n,m;
    cin >> n >> m;
    VI a(m),b(m),mask(m);
    //VVI c(m);
    int in;
    REP(i,0,m) {
        cin >> a[i] >> b[i];
        REP(j,0,b[i]) {
            cin >> in;
            mask[i] |= (1 << (in-1));
        }
    }
    VVI dp(m+1,VI(1<<n,1'000'000'000));

    REP(i,0,m) {
        dp[i+1][mask[i]] = min(dp[i+1][mask[i]], a[i]);
        //dump(dp[i+1][mask[i]]);
        REP(j,0,1<<n) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            dp[i+1][j|(mask[i])] = min({dp[i+1][j|(mask[i])], dp[i][j|(mask[i])], dp[i][j] + a[i]});
        }
    }
    if (dp[m][(1<<n)-1] == 1000000000) {
        dp[m][(1<<n)-1] = -1;
    }
    cout << dp[m][(1<<n)-1] << endl;
    /*
    REP(i,0,m+1) {
        REP(j,0,1<<n) {
            cout << dp[i][j] << " ";
        }
        cout << endl;

    }
    */
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 16384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; i++)
#define RFOR(i, a, n) for (ll i = (ll)n - 1; i >= (ll)a; i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define bra(first, second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 1001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template <typename T>
void remove(std::vector<T> &vector, unsigned int index)
{
   vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

ll A[200010];

int main(){
   ll N,ans = 0,M = 0;
   cin >> N;
   rep(i,N){
      cin >> A[i];
      if(M > A[i]){
         ans += M - A[i];
      }
      M = max(M,A[i]);
   }
   cout << ans << endl;
}

Measured memory_bytes: 5188
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vvi G(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int ans = 0;
    function<int(int, int)> dfs = [&](int i, int j) {
        int res = 0, rres = -1;
        for(int ne:G[i]) {
            if(ne == j) continue;
            int x = dfs(ne, i);
            if(x > res) {
                rres = res;
                res = x; 
            } else if(x > rres) {
                rres = x;
            }
        }
        chmax(ans, res+rres+1);
        return res+1;
    };
    dfs(0, -1);

    cout << (ans%3 == 2?"Second":"First") << endl;
}

Measured memory_bytes: 32008
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main(){
  int N;
  cin >> N;
  int M = N;
  int f = 0;
  rep(i, 9){
    f += N % 10;
    N /= 10;
  }
  if(M % f == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
s = input()
a = [chr(i) for i in range(ord('a'), ord('z')+1)]
if len(s)< 26:
    for i in a:
        if sorted(s).count(i)==0:
            break
    print(s+i)
else:
    l = [ord(i) for i in s]
    for i in range(1,len(s)):
        if l[-i]-l[-i-1]>0:
            k = sorted(s[-i:])
            for j in k:
                if ord(j)>ord(s[-i-1]):
                    break
            print(s[:-i-1]+j)
            break
    else:
        print(-1)


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

#define rin(i,a,b) for(int i=(a);i<=(b);++i)
#define irin(i,a,b) for(int i=(a);i>=(b);--i)
#define trav(i,a) for(int i=head[a];i;i=e[i].nxt)
#define Size(a) (int)a.size()
#define pb push_back
#define mkpr std::make_pair
#define fi first
#define se second
#define lowbit(a) ((a)&(-(a)))
typedef long long LL;

using std::cerr;
using std::endl;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=200005;

int n,a,b,c,d;
char s[MAXN];

int main(){
	n=read(),a=read(),b=read(),c=read(),d=read();
	scanf("%s",s+1);
	if(c<d){
		rin(i,b+1,d-1){
			if(s[i-1]=='#'&&s[i]=='#'){
				printf("No\n");
				return 0;
			}
		}
		rin(i,a+1,c-1){
			if(s[i-1]=='#'&&s[i]=='#'){
				printf("No\n");
				return 0;
			}
		}
		printf("Yes\n");
		return 0;
	}
	else{
		bool flag=false;
		rin(i,b,d){
			if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.'){
				flag=true;
				s[i]='#';
			}
		}
		if(!flag){
			printf("No\n");
			return 0;
		}
		rin(i,a+1,c-1){
			if(s[i-1]=='#'&&s[i]=='#'){
				printf("No\n");
				return 0;
			}
		}
		printf("Yes\n");
		return 0;
	}
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

double calc(ll x) {
	ll tmp = x, sum = 0;
	while(x) {
		sum += x % 10;
		x /= 10;
	}
	return 1.0 * tmp / sum;
}

int main()
{
	int k;
	cin>>k;
	ll x = 1, tmp = 0;
	while(k--) {
		double s1, s2;
		while(1) {
			s1 = calc(tmp + x), s2 = calc(tmp + x * 10);
			if(s1 <= s2) break;
			x *= 10;
		}
		tmp += x;
		cout<<tmp<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
ac = 0
wa = 0
arr = []
h = {}
for _ in range(M):
    p, s = input().split()
    arr.append([int(p), s])
    if h.get(int(p)) is None:
        h[int(p)] = [s] 
    else:
        h[int(p)].append(s)
        
        
for k in h.keys():
    if all(x == 'WA' for x in h[k]):
        continue
    for v in h[k]:
        if v == 'AC':
            ac += 1
            break
        else:
            wa += 1

print(ac, wa)

Measured memory_bytes: 40920
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl "\n"

using namespace std;

int main()
{

    ll n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector<int> dp(n);

    dp[0] = 0;
    dp[1] = abs(arr[0] - arr[1]);

    for (int i = 2; i < n; i++)
    {
        int p = abs(arr[i] - arr[i - 1]);
        int q = abs(arr[i] - arr[i - 2]);

        dp[i] = min(dp[i - 2] + q, dp[i - 1] + p);
    }

    cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1024
n, k = map(int, input().split())

nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
for i in range(n):
    c = 0
    for j in range(i + 1, n):
        if nums[i] > nums[j]:
            c += 1
    ans += (c * k) % mod

dp = [0] * n
for i in range(n):
    for j in range(n):
        if nums[i] > nums[j]:
            dp[i] += 1
for i in range(n):
    ans += ((k - 1) * k // 2 * dp[i]) % mod
print(ans % mod)

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

int main(){
    int  N; cin >> N;
    int M, m;
    long long s;
    s = 0;
    M = -1000006;
    m = 1000006;
    for(int i = 0; i < N ;i++){
        int tmp;
        cin >> tmp;
        if(tmp > M) M = tmp;
        if(tmp < m) m = tmp;
        s += tmp;
    }
    cout << m << " " << M << " " << s << endl;
    return 0;
}


Measured memory_bytes: 3084
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	int INF = 1001001001;
	Scanner sc = new Scanner(System.in);
	int n, m, x;
	n = sc.nextInt();
	m = sc.nextInt();
	x = sc.nextInt();
	int a[][] = new int[n][m];
	int c[] = new int[n];
	for (int i = 0; i < n; i++) {
	    c[i] = sc.nextInt();
	    for (int j = 0; j < m; j++) {
		a[i][j] = sc.nextInt();
	    }
	}
	sc.close();
	int ans = INF;
	for (int i = 0; i < (1 << n); i++) {
	    int cost = 0;
	    int[] skill = new int[m];
	    // Arrays.fill(skill, 0);
	    for (int j = 0; j < n; j++) {
		if ((i >> j & 1) == 1) {
		    cost += c[j];
		    for (int k = 0; k < m; k++) {
			skill[k] += a[j][k];
		    }
		}
	    }
	    boolean ok = true;
	    for (int j : skill) {
		if (j < x) {
		    ok = false;
		    break;
		}
	    }
	    if (ok)
		ans = Math.min(ans, cost);
	}
	// System.out.println(A+B+C+K);
	if (ans == INF) {
	    System.out.println(-1);
	} else {
	    System.out.println(ans);
	}
    }
}

Measured memory_bytes: 28308
#include "bits/stdc++.h"
using namespace std;
int M(){
    string s;
    if(!(cin >> s)) return 0;
    string w;
    for(char v : s) if(v != 'x') w.push_back(v);
    string r = w;
    reverse(r.begin(), r.end());
    if(r != w) printf("-1\n");
    else{
        int i = 0, j = s.size() - 1;
        string ans;
        int cnt = 0;
        while(i <= j){
            if(s[i] != s[j]){
                if(s[i] == 'x') ans.push_back('x'), i++, cnt++;
                else if(s[j] == 'x') ans.push_back('x'), j--, cnt++;;
            } else
                ans.push_back(s[i]), i++, j--;
        }
        cout << cnt << endl;
        // if(r.size()&1){
        //     string cp = ans;
        //     cp.pop_back();
        //     reverse(cp.begin(), cp.end());
        //     ans += cp;
        // } else {
        //     string cp = ans;
        //     reverse(cp.begin(), cp.end());
        //     ans += cp;
        // }
        // cout << ans.size() - s.size() << endl;
    }
    return 1;
}
int main(){
    while(M());
    return 0;
}


Measured memory_bytes: 768
import java.io.*;
import java.util.*;

class Main
{
    public static void main(String[] args)
    {
	Scanner sc = new Scanner(System.in);
	
	int a = sc.nextInt();
	int b = sc.nextInt();


if(a==b){
System.out.println("a == b");
}else if(a < b){
System.out.println("a < b");
}else{
System.out.println("a > b");
    }
}
}


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

int main() {
	vector<int>A(3);
	for (int i = 0; i < 3; ++i) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	if ((A[0] + A[1]) == A[2]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

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

using namespace std ; 

const int N = 3e5 + 7 ; 

int n ; 
vector<int> adj[N] ; 
int a[N] ; 
int tree[N * 4 ] ; 
int ans[N] ; 
int cnt ; 
vector<int> treev[N * 4] , mxs[4 * N] ;  


int gnode(int x){
        int ret = 0  ; 
        for(auto u : treev[x]){
                ret = max(ret , u) ; 
        }
        return ret ; 
}

void update(int node , int L , int R , int ix , int val){

        if(L == R){
                if(mxs[node].size() == 0){
                        mxs[node].push_back(0) ;
                }
                if(val > 0){
                        mxs[node].push_back(max(val , mxs[node].back())) ;         
                        treev[node].push_back(val) ;              
                }
                else{
                        treev[node].pop_back() ; 
                        mxs[node].pop_back() ; 
                }
                tree[node] = gnode(node);
                //tree[node] = mxs[node].back() ; 
                return ; 
        }

        int mid = (L + R) >> 1 ; 
        if(ix<=mid){
                update(node*2+1 , L , mid , ix , val) ; 
        }
        else{   
                update(node*2+2 , mid+1 , R , ix , val) ; 
        }
        tree[node] = max(tree[node*2+1] , tree[node*2+2] ) ; 
}

int get(int node , int L , int R , int l , int r){      
        if(l > R || r < L) return 0 ; 
        if(L>= l && R<= r)
                return tree[node] ; 
        int mid = (L+R) >>1 ; 
        int s1 = get(node*2+1 , L , mid , l , r) ; 
        int s2 = get(node*2+2 , mid+1 , R , l , r) ; 
        return max(s1 , s2) ;
}

vector<int> liss = {0} ; 
vector<int> mxl  = {0} ; 

void dfs(int x , int p){

        int mxp = get(0 , 1 , N , 1 , a[x] -1 ) ; 
        liss.push_back({mxp+1}) ; 
        mxl.push_back(max(mxl.back() , liss.back())) ;
        ans[x] = mxl.back() ; 
        update(0 , 1 , N , a[x] , mxp + 1 ) ; 

        for(auto u : adj[x]){
                if(u == p)
                        continue ; 
                dfs(u , x) ;        
        }
        update(0 , 1 , N , a[x] , -1) ; 
        mxl.pop_back() ; 
        liss.pop_back() ;
}


int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ; 
        //freopen("in.in" ,"r" , stdin) ; 

        cin >> n; 
        vector<pair<int , int > > dbl ; 
        for(int i = 1;i <=n;i++){
                int x ; cin >> x ; 
                dbl.push_back({x , i}) ; 
        }
        sort(dbl.begin() , dbl.end()) ; 
        int T = 1 , l = 0  ;
        for(int i = 0 ;i < n;i++){
                T += (dbl[i].first != l) ; 
                a[dbl[i].second] = T ; 
                l = dbl[i].first ; 
        }
        for(int i = 0 ;i < n -1 ;i ++){
                int u , v; 
                cin >> u >> v ; 
                adj[u].push_back(v) ; 
                adj[v].push_back(u) ; 
        }

        dfs(1 , 1) ; 
        for(int i =1 ;i <=n;i++)
                cout<< ans[i] <<"\n" ; 

        return 0; 
}

Measured memory_bytes: 101644
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
 
using namespace std;
 
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
 
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
 
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
 
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
 
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

              

int main(){
  int K;
  cin >> K;
  queue<ll> q;
  
  int cnt = 0;
  int i = 0;
  rep(i,9){
    q.push(i+1);
  }
  while(1){
    ll tmp = q.front();q.pop();i++;
    
    if(i==K){
      cout << tmp << endl;
      break;
    }
    if(tmp%10 == 0){
      q.push(tmp*10 + 0);
      q.push(tmp*10 + 1);
    }
    else if(tmp%10 == 9){
      q.push(tmp*10 + 8);
      q.push(tmp*10 + 9);
    }
    else {
      q.push(tmp*10 + tmp%10 - 1);
      q.push(tmp*10 + tmp%10);
      q.push(tmp*10 + tmp%10 + 1);
    }
  }
  
  return 0;
}
  
  


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

namespace ABC162
{
    class Program
    {
        static void Main(string[] args)
        {
            b();
        }

        public static void b()
        {
            long n = long.Parse(Console.ReadLine());
            long sum = 0;
            for (long i = 1; i < n + 1; i++)
            {
                if (i % 3 != 0 && i % 5 != 0)
                {
                    sum += i;
                }
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 17620
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  bool flip = false;
  if (a < b) {
    swap(a, b);
    flip = true;
  }
  int h = 100, w = 100;
  vector<VI> ans(h, VI(w, 0));
  int hf = w / 2;
  int pos = 0;
  REP(i, 0, h) {
    REP(j, 0, w) {
      ans[i][j] = i >= h / 2 ? 1 : 0;
    }
  }
  //DEBUGP(hf);
  //DEBUGP(dr);
  while (pos < a - 1) {
    ans[h / 2 + 1 + 2 * (pos / hf)][2 * (pos % hf)] = 0;
    pos++;
  }
  pos = 0;
  while (pos < b - 1) {
    ans[2 * (pos / hf)][2 * (pos % hf)] = 1;
    pos++;
  }

  if (flip) {
    REP(i, 0, h) {
      REP(j, 0, w) {
	ans[i][j] = 1 - ans[i][j];
      }
    }
  }

  cout << h << " " << w << endl;
  REP(i, 0, h) {
    REP(j, 0, w) {
      cout << (ans[i][j] ? '#' : '.'); 
    }
    cout << endl;
  }
}


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

using namespace std;

int main(void){
	int n;
	cin >> n;
	vector<int> r(n);

	int buy;
	int profit;
	for (int i = 0; i < n; i++){
		cin >> r[i];
		if (i == 1){
			profit = r[1] - r[0];
		}
		else if (i > 1){
			profit = max(profit, r[i] - buy);
		}
		if (i == 0){
			buy = r[i];
		}
		else if (buy > r[i]){
			buy = r[i];
		}
	}

	cout << profit << endl;
	return 0;
}

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

int main(){

  int b[11] = {63,6,91,79,102,109,125,39,127,111,0};
  int now = 11;
  int k;
  int n;

  while(cin >> n){
    if(n == -1) break;
    
    cin >> k;
    for(int i=6;i>-1;i--) printf("%d", (b[k]>>i)&1);
    now = k;
    cout << endl;
    n--;
    
    while(n--){
      cin >> k;
      int p = (b[now]^b[k]);
      for(int i=6;i>-1;i--) printf("%d", (p>>i)&1);
      printf( "\n" );
      now = k;
    }
  }

}

Measured memory_bytes: 1180
N, K = map(int, input().split())
ans = 0
if K == 0:
    print(N**2)
    exit()
    
for b in range(1, N+1):
    block_K = max(0, b-K)
    #print("b", b, "block_num", (N+1)//b, "block_K", block_K, "remain", (N+1)%b)
    ans += block_K * ((N+1)//b) + max(0, (N+1)%b - K)

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<int>;
using A = array<int, 2>;
using P = pair<int, int>;
constexpr int MOD{1000000000 + 7};
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr array<int, 4> dx{1, 0, -1, 0}, dy{0, 1, 0, -1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
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;
}
constexpr int div_roundup(int a, int b)
{
    return (a + b - 1) / b;
}
// power with modulo
ll powMod(ll b, ll e, const ll m = MOD)
{
    ll r = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
    }
    return r;
}
// factrial with modulo
ll factMod(const ll n, const ll m = MOD)
{
    ll x = 1;
    for (ll i = 1; i <= n; ++i)
        x = (x * i) % m;
    return x;
}
class Combi
{
private:
    const int n_, mod_;
    vector<ll> fac_, finv_;

public:
    Combi(int n = 10000, int mod = MOD);
    ll count(int n, int k);
};
Combi::Combi(int n, int mod) : n_(n), mod_(mod)
{
    fac_.resize(n_);
    finv_.resize(n_);
    vector<ll> inv(n_);

    fac_[0] = fac_[1] = 1;
    finv_[0] = finv_[1] = 1;
    inv[1] = 1;

    for (int i = 2; i < n_; i++)
    {
        fac_[i] = fac_[i - 1] * i % mod_;
        inv[i] = mod_ - inv[mod_ % i] * (mod_ / i) % mod_;
        finv_[i] = finv_[i - 1] * inv[i] % mod_;
    }
}
ll Combi::count(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac_[n] * (finv_[k] * finv_[n - k] % mod_) % mod_;
}

// vector<vector<int>> vec(n_rows, vector<int>(n_cols, value));

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

void solve()
{
    const ll y = 2019;

    ll l, r;
    cin >> l >> r;

    ll ans = 1e18;

    for (ll i = l; i <= min(r, l + y + 100); i++)
        for (ll j = i + 1; j <= min(r, l + y + 100); j++)
        {
            chmin(ans, (i % y * j % y) % y);
            if (ans <= 0)
                break;
        }

    cout << ans << endl;
}

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

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

    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using vin=vector<int>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;

int main() {
  int n;
  cin>>n;
  vin a(n);
  rep(i,n) cin>>a[i];
  ll ans=inf;
  //////
  
  for(int i=-100;i<101;i++){//全探索
    ll cnt=0;
    rep(j,n){
      cnt+=(a[j]-i)*(a[j]-i);
    }
    ans=min(ans,cnt);
  }
  cout<<ans<<endl;
}






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

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

fn main() {
    let n: i16 = read();
    let mut sum = 0.0;
    for _ in 0..n {
        let i: f64 = read();
        sum += 1.0/i;
    }
    println!("{}", 1.0/sum);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 1e9+7;
const int MN = 2e5+10;
int ksm(int a,int x){
 	int ans=1,w=a;
   	while(x){
   		if(x&1)ans=ans*w%Mod;
   		w=w*w%Mod;
   		x>>=1;
   	}
   	return ans;
}
int n,bin[MN],fa[MN],siz[MN],f[MN][3],ans=0,inv2=(Mod+1)/2;
int to[MN<<1],net[MN<<1],h[MN],e=0;
void add(int x,int y){
	to[++e]=y;net[e]=h[x];h[x]=e;
}
void dfs(int x){
 	siz[x]=1;
   	f[x][0]=1;
	for(int i=h[x];i;i=net[i]){
		int y=to[i];
   		if(fa[x]==y)continue;
   		fa[y]=x;
   		dfs(y);
   		siz[x]+=siz[y];
		int P=bin[siz[y]];
		(f[x][2]+=f[x][1]*(1ll-P+Mod)%Mod)%=Mod;
		f[x][1]=(f[x][1]*(P)%Mod+f[x][0]*(1ll-P+Mod)%Mod)%Mod;
		f[x][0]=f[x][0]*(P)%Mod;
	}
	(ans+=1ll*f[x][2]*inv2%Mod)%=Mod;
	if(x!=1)
		(ans+=1ll*f[x][1]*inv2%Mod*(1+Mod-bin[n-siz[x]])%Mod)%=Mod;
	return;
}
signed main(){
  	scanf("%lld",&n);
   	bin[0]=1;
   	for(int i=1;i<=n;++i)bin[i]=bin[i-1]*inv2%Mod;
   	for(int i=1;i<n;++i){
   		int x,y;
   		scanf("%lld%lld",&x,&y);
   		add(x,y);add(y,x);
	}
   	dfs(1);
    printf("%lld\n",ans%Mod);
    return 0;
}

Measured memory_bytes: 24064
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)


using namespace std;
using ll = long long;

int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int s ,w;
    cin >> s >> w;
    if(s<=w)cout << "unsafe" << endl;
    else cout << "safe" << endl;
   
   

    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int a[3];
int main () {
	string s;
	cin >> s;
	for (int i = 0; i < (int)s.size(); ++i)
	{
		if(s[i] == 'a'){
			a[0]++;
		}else if(s[i] == 'b'){
			a[1]++;
		}else{
			a[2]++;
		}
	}
	if(a[0] == 1 && a[1] == 1 && a[2] == 1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	while(1){
		int n,m; cin >> n >> m;
		if(n==0&&m==0)break;
		vector<string> s(n);
		vector<int> a(n);
		ll sum=0;
		for(int i=0;i<n;i++){
			cin >> s[i] >> a[i];
		}
		for(int i=0;i<m;i++){
			string t; cin >> t;
			for(int j=0;j<n;j++){
				bool ok=true;
				for(int k=0;k<8;k++){
					if(s[j][k]!='*'){
						if(s[j][k]!=t[k])ok=false;
					}
				}
				if(ok){
					sum+=a[j];
					break;
				}
			}
		}
		cout << sum << endl;
	}
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
const ll INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    ll a; cin >> a;
    //dp[i][j][s][t]はi番まで見たとき,カッコがj個ひらいているときの最大値
    ll dp[n][3];
    //初期化
    REP(i,n)REP(j,3) dp[i][j] = -INF;
    dp[0][0] = a;
    REP(i, n - 1){
        char c; ll a; cin >> c >> a;
        int z = c == '-';
        //カッコを変化させない場合
        REP(j,3) chmax(dp[i+1][j], dp[i][j] + ( (j % 2) xor z ? -a : a) );

        //カッコを減らす場合
        RREPS(j,2) chmax(dp[i+1][j-1], dp[i][j] + ( (j % 2) xor z ? -a : a) );

        //カッコを増やす場合
        if(z) REP(j,2) chmax(dp[i+1][j+1], dp[i][j] + ( (j % 2) xor z ? -a : a) );
    }
    cout << dp[n-1][0] << '\n';
}

Measured memory_bytes: 5972
import java.util.Scanner;

public class Main {

    public Main() {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        long K = scan.nextLong();

        int[] A = new int[N];
        for (int i=0;i<N;i++){
            A[i] = scan.nextInt()-1;
        }

        boolean[] P = new boolean[N];

        int index = 0;
        int num = 0;
        while(true){
            if(P[A[index]]){
                index = A[index];
                K -= num+1;
                break;
            }
            P[index] = true;

            index = A[index];
            num++;
            if(num == K){
                System.out.println(index+1);
                return;
            }
        }

        int start = index;

        //閉路の長さを求める
        int L = 1;
        while(true){
            if(!P[index]) break;
            L++;
            P[index] = false;
            index = A[index];
        }

        K = K % L;
        index = start;
        for(int i=0;i<K;i++){
            index = A[index];
        }

        System.out.println(index+1);

    }

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


Measured memory_bytes: 60040
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>

typedef std::map< std::string,std::vector<int> > Dic;
int main(){
	std::string input;
	int inum;
	Dic map;
	while( std::cin>>input>>inum )
		map[input].push_back(inum);
	
	for(auto it=map.begin();it!=map.end();++it){
			std::cout<<it->first<<std::endl;
			std::sort(it->second.begin(),it->second.end());
			for(int Page=0; Page!=it->second.size(); ++Page){
				std::cout<<it->second[Page]<<(Page==it->second.size()-1?"\n":" ");
			}
		}
	return 0;
}

Measured memory_bytes: 1240
#![allow(unused_imports, dead_code)]
use std::f64::*;
use std::cmp::*;
use std::collections::*;

macro_rules! dump{
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

const INF: i64 = 0x3f3f3f3f3f3f3f3f;
const MOD: i64 = 1000000007;
const NOTHING: usize = std::usize::MAX;
const DX: [usize; 4] = [1, 0, std::usize::MAX, 0];
const DY: [usize; 4] = [0, 1, 0, std::usize::MAX];

fn main() {
    let n: usize = readln();
    let mut gr: Vec<Vec<usize>> = vec![vec![];n];
    for _ in 0..n - 1 {
        let (a, b): (usize, usize) = readln();
        gr[a - 1].push(b - 1);
        gr[b - 1].push(a - 1);
    }
    let mut q: VecDeque<(usize, usize, usize)> = VecDeque::new();
    let fennec = 0;
    let snuke = n - 1;
    q.push_back((fennec, NOTHING, 0));
    let mut depth = NOTHING;
    let mut parent: Vec<usize> = vec![NOTHING;n];
    while let Some((v, p, d)) = q.pop_front() {
        if v == snuke {
            depth = d;
            break;
        }
        for &u in &gr[v] {
            if u != p {
                q.push_back((u, v, d + 1));
                parent[u] = v;
            }
        }
    }
    let mut d = (depth - 1) / 2;
    let mut r = snuke;
    while d > 0 {
        r = parent[r];
        d -= 1;
    }

    let mut count = 0;
    let mut q: VecDeque<(usize, usize)> = VecDeque::new();
    q.push_back((r, parent[r]));
    while let Some((v, p)) = q.pop_front() {
        for &u in &gr[v] {
            if u != p {
                count += 1;
                q.push_back((u, v));
            }
        }
    }
    if count * 2 < n - 2 {
        println!("Fennec");
    } else {
        println!("Snuke");
    }
}

trait Read {
    fn read(s: &str) -> Self;
}

fn readln<T: Read>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

macro_rules! read_impl{
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl Read for String {
    fn read(s: &str) -> Self {
        s.to_string()
    }
}

impl Read for Vec<char> {
    fn read(s: &str) -> Self {
        s.chars().collect()
    }
}

impl<T: Read> Read for Vec<T> {
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

impl<A: Read, B: Read, C: Read, D: Read> Read for (A, B, C, D) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]), D::read(tokens[3]))
    }
}


Measured memory_bytes: 12540
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

N = int(input())

# 複数個の数値を、intの配列として取得
H = list(map(int, input().split()))

for i in range(1,N-1):
  if H[-i-1]-H[-i]==1:
    H[-i-1] -= 1
  elif H[-i-1]-H[-i]>1:
    print('No')
    exit()
    
print('Yes')

Measured memory_bytes: 14404
import java.util.Scanner;

public class Main{

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

		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[m];
		int[] b = new int[n];
		int[] s = new int[n];

		for(int i = 0; i < m; i++) {
			a[i] = sc.nextInt() - 1;
			//i = [0, m-1]だが、m = [1, m]だから
		}	//まずa[i]を一通り読み込む
		
		for(int i = 0; i < m; i++) {	
			for(int j = 0; j < n; j++) {
				b[j] = sc.nextInt() - 1;
				
				if(b[j] == a[i]) {
					s[j] += 1;
				}
				else {
					s[a[i]] += 1;
				}
			}
		}
		
		for(int j = 0; j < n; j++) {
			System.out.println(s[j]);	
		}
		
		sc.close();
	}

}



Measured memory_bytes: 38988
a, b, c, d = map(int, input().split())
As = [i for i in range(a, (b + 1))]
Bs = [i for i in range(c, (d + 1))]

ans = []
for A in As:
    for B in Bs:
        if A == B:
            ans.append(A)
if ans:
    print(ans[-1] - ans[0])
else:
    print(0)


Measured memory_bytes: 38512
object Main {

  val INF = Long.MaxValue

  case class Edge(u: Int, v: Int, weight: Int)
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val V, E = sc.nextInt()

    val edges = (0 until E).foldLeft(Nil: List[Edge])((lst, _) => {
      val u, v, w = sc.nextInt()
      Edge(u, v, -w) :: lst
    })

    // N頂点,M辺の重み付き有向グラフ
    // このグラフと駒を使用する
    // 最初, 駒を頂点1に置いて, プレイヤーのスコアを0とします
    // プレイヤーは次の条件で駒を繰り返し移動させることができます
    // * 頂点a_iに駒がある時, i番目の辺を利用して, 頂点b_iに移動する
    //   移動後にプレイヤーのスコアがc_i加算される
    // 頂点Nに駒がある時のみ, ゲームを終了できます.
    // なお, 与えられる有向グラフの上で、頂点1から頂点Nに移動できることは保証されています
    // プレイヤーがゲーム終了時のスコアをできるだけ大きくするような行動を取った時
    // ゲーム終了時のスコアは幾つになるでしょうか?

    // なんで, 閉路がある場合には, いくらでも回ればいいので, INFになる
    // なるべくスコアを大きくしたいので, この場合, c' = -c となる新しい重みを
    // 導入すると, u -> vに行くときになるべく大きい値を取るようになる(最短路なので)

    // 始点と終点が決まっているので, 単一始点最短経路問題に帰着する.
    // 負辺があるのでダイクストラは使えない.
    // 普通にO(VE)でもV = 1000, E = 2000 なので間に合う感じ
    bellmanFord(V, edges, 1) match {
      case Some(v) => println(v)
      case _ => println("inf")
    }
  }

  def bellmanFord(V: Int, edges: List[Edge], s: Int): Option[Long] = {
    val dist = Array.fill(V+1)(INF)

    dist(s) = 0L
    for {
      _ <- 0 until V - 1
      edge <- edges
    } relax(edge.u, edge.v, edge.weight)

    def relax(u: Int, v: Int, w: Int): Unit =
      if (dist(u) != INF && dist(v) > dist(u) + w) {
        dist(v) = dist(u) + w
      }

    val result = dist(V)
    val negative = new Array[Boolean](V+1)
    def relax2(u: Int, v: Int, w: Int): Unit =
      if (dist(u) != INF && dist(v) > dist(u) + w) {
        dist(v) = dist(u) + w
        negative(v) = true
      }

    for {
      _ <- 0 until V
      edge <- edges
    } relax2(edge.u, edge.v, edge.weight)

    if (!negative(V)) Some(-result)
    else None
  }

}


Measured memory_bytes: 31580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int BIG = 2e9 + 55;

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

    ll a, b, c, k; cin >> a >> b >> c >> k;
    ll delta = 0;

    if(k % 2){
        delta = -1;
    } else {
        delta = 1;
    }

    ll diff = a * delta - b * delta;

    if(diff > INF){
        cout << "Unfair\n";
        return 0;
    }

    cout << diff << '\n';

    return 0;
}

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

int row(int w);
  
int main() {


  int h, w;

  while(1) {
    cin >> h >> w;
    if((h + w) == 0) break;

    for(int j = 0; j < h; j++) {
      row(w);
    }
    cout << endl;
    
  }
  return 0;  
}      

int row(int w){

  for(int i = 0; i < w; i++) {
    cout << "#";
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const ll LIM = 1000000000000000LL;

int s(ll x){
    int ret = 0;
    while(x){
        ret += x%10;
        x/=10;
    }
    return ret;
}

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

    vector<ll> v;
    rep(i,15){
        string nine(i,'9');
        for(int j=1; j<=999; ++j){
            string t = to_string(j) + nine;
            ll val = stoll(t);
            if(val <= LIM) v.pb(val);
        }
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    sort(all(v), [](const ll &lh, const ll &rh){
        return (lh*s(rh) == rh*s(lh))?lh<rh:lh*s(rh) < rh*s(lh);
    });

    vector<ll> ans;
    ll pre = 0;
    for(ll i:v){
        if(pre<i){
            pre = i;
            ans.pb(i);
        }
    }
    rep(i,k) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void) {
    string s;
    cin >> s;
    if(s.back() == 's') {
        s.push_back('e');
    }
    s.push_back('s');
    cout << s << endl;
    return 0;
}


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


int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	a=max(a,c);
	b=min(b,d);
	
	b=b-a;
	if(b<0) b=0;
	cout << b << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[100010];

int main()
{
    #ifdef waltz
        freopen("input.txt","r",stdin);
    #endif
    int n;scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1]=0;
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        ans+=a[i]/2;a[i]&=1;
        if (a[i]&&a[i+1])
        {
            a[i+1]--;ans++;
        }
    }
    printf("%lld\n",ans);
    
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);

    if ((a + b) % 2 == 0)
    {
        printf("%d\n", (a + b) / 2);
    }
    else
    {
        printf("%d\n", ((a + b) / 2) + 1);
    }
    return 0;
}


Measured memory_bytes: 128
#include <cstdio>

int main () {
    bool output = true;
    int a;
    int i = 1;
    scanf("%d", &a);
    while (output) {
        printf("Case %d: %d\n", i, a);
        i++;
        scanf("%d", &a);
        if (a == 0) output = false;
    }

    return 0;
}

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

int main(){
    int n, k;
    cin >> n >> k;
    int v[n];
    for(int i = 0; i < n ; ++i) cin >> v[i];
    vector<int> dp(n+1, oo);
    dp[0] = 0;
    for(int i = 1; i < n ; ++i){
        for(int x = i-1; x >= 0 && x>=i-k ; x--){
            dp[i] = min(dp[i], dp[x]+abs(v[i]-v[x]));
        }
    }
    printf("%d\n", dp[n-1]);

    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    string a, b, c;
    cin >> a >> b >> c;

    map<char, queue<char > >mp;

    //準備
    for(ll i = 0; i < a.length(); i++){
        mp['a'].push(a[i]);
    }
    for(ll i = 0; i < b.length(); i++){
        mp['b'].push(b[i]);
    }
    for(ll i = 0; i < c.length(); i++){
        mp['c'].push(c[i]);
    }

    //シミュレーション
    char teban = 'a';
    while(!mp[teban].empty()){
        char tmp = mp[teban].front();
        mp[teban].pop();
        teban = tmp;
        
    }

    teban -= 32;
    cout << (char)teban << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll n,k;
	cin >> n >> k;
	string arr;
	cin >> arr;
	ll count = 1;
	vector <ll> record;
	for (int z=1;z<n;z++){
		if (arr[z-1] != arr[z]){
			if (arr[z-1] == '0'){
				record.push_back(-count);
				count = 0;
			}
			else {
				record.push_back(count);
				count = 0;
			}
		}
		count++;
	}
	if (count != 0) {
		if (arr[n-1] == '0') count = -count;
		record.push_back(count);
	}
	ll feet = 0;
	for (int z=0;z<record.size();z++){
		if (record[z] < 0){
			feet++;
		}
	}
	ll answer = 0;
	ll temp = 0;
	ll s = 0;
	ll e = 0;
	for (int z=0;z<record.size();z++){
		if (record[z] > 0){
			answer += record[z];
		}
		else {
			if (temp == k){
				e = z;
				break;
			}
			answer -= record[z];
			temp++;
		}
	}
	temp = answer;
	for (int z=e;z<record.size();z++){
		if (record[z] < 0){
			answer = max(answer,temp);
			temp -= record[z];
			for (;s<record.size();s++){
				if (record[s] > 0){
					temp -= record[s];
				} else {
					temp += record[s];
					s++;
					break;
				}
			}
			answer = max(answer,temp);
		} else {
			temp += record[z];
		}
	}
	if (feet <= k){
		cout << n << endl;
	} else {
		cout << max(answer,temp) << endl;
	}
	cin >> n;
}

Measured memory_bytes: 1528