akhauriyash/Code-Regression huggingface dataset:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a, b = S_MAP()
if a != b:
    print("D")
else:
    print("H")


Measured memory_bytes: 5328
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int ans=0;
  ans-=((n+1)*n)/2;
  rep(i,n){
    int num;
    cin>>num;
    ans+=num;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3216
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
//#include <tuple>
//#include <array>
//#include <random>
//#include <windows.h>
//#pragma comment(lib, "winmm.lib")

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main()
{
	LL N;
	cin >> N;
	vector<LL> a(2);
	cin >> a[0] >> a[1];
	REP(i, N - 1) {
		vector<LL> b(2);
		cin >> b[0] >> b[1];
		LL s = 1;
		REP(j, 2) {
			if (a[j] % b[j] == 0) {
				if (a[j] / b[j] > s) { s = a[j] / b[j]; }
			}
			else {
				LL u = ((a[j]+(b[j]-(a[j]%b[j])) )/ b[j]);
				if (u> s) { s = u; }
			}
		}
		a[0] = b[0]*s;
		a[1] = b[1]*s;
			
	}
	cout << a[0] + a[1] << endl;
}

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

using namespace std;

typedef long long ll;

vector<ll> go;
map<ll, ll> ase;

bool check(ll n) {
  if (n < 100) return false;
  string t = to_string(n);
  bool s7 = false, f5 = false, t3 = false;
  for (int i = 0; i < t.size(); i++) {
    if (t[i] == '7') s7 = true;
    if (t[i] == '5') f5 = true;
    if (t[i] == '3') t3 = true;
  }
  return s7 == 1 && f5 == 1 && t3 == 1 ? true : false;
}

void rec(ll n) {
  if (n > 1000000000) return;
  if (check(n)) go.push_back(n);
  rec(n * 10 + 7);
  rec(n * 10 + 5);
  rec(n * 10 + 3);
}

int main() {
  rec(0);
  sort(go.begin(), go.end());
  ll n, ans = 0;
  scanf("%lld", &n);
  for (ll i = 0; i < go.size(); i++) {
    if (go[i] > n) break;
    else ans++;
  }
  printf("%lld\n", ans);
  return 0;
}


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

using namespace std;

int main(){
	int a,b,c;

	cin >> a >> b >> c;

	if(a == b && a != c || a == c && a != b || b == c && b != a){
		cout << "Yes\n";
	}
	else{
		cout << "No\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int n,cnt=0;
    string s;
    cin>>n>>s;
    rep(i,n-2){
        if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C') cnt++;
    }
    cout<<cnt<<endl;
}

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

#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	int n, m; cin >> n >> m;
	int ans(0);
	if (n * 2 < m) {
		ans += n;
		m -= n * 2;
		ans += m / 4;
	}
	else {
		ans += m / 2;
		n = -m / 2;
	}
	cout << ans << endl;
	return 0;
}

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

const int N = 2e5 + 100, inF = N;

int n, DIS[N];
bool mark[N];
struct tree {
	int dex, root, dis[N], par[N];
	vector<int> nei[N];
	tree() {
		fill(par, par + N, -1);
		fill(dis, dis + N, inF);
	}
	void input() {
		for (int i = 0; i < n - 1; i++) {
			int u, v;
			cin >> u >> v;
			nei[--u].push_back(--v);
			nei[v].push_back(u);
		}
	}
	void dfs(int v, bool b = false) {
		dis[root] = 0;
		if (dis[v] >= DIS[v] && b)
			return;
		for (int u: nei[v])
			if (u ^ par[v]) {
				dis[u] = dis[v] + 1;
				par[u] = v;
				dfs(u, b);
			}
	}
	bool far(int u, int v) {
		if (u == v || u == par[v] || v == par[u] || par[u] == par[v])
			return false;
		if (par[u] != -1 && par[par[u]] == v)
			return false;
		if (par[v] != -1 && par[par[v]] == u)
			return false;
		return true;
	}
} R, B;

void INPUT() {
	cin >> n >> R.root >> B.root;
	R.root--;
	B.root--;
	R.input();
	B.input();
	B.dfs(B.root);
	copy(B.dis, B.dis + n, DIS);
	R.dfs(R.root, true);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	INPUT();
	for (int v = 0; v < n; v++)
		for (int u: R.nei[v])
			if (B.far(u, v))
				mark[u] = mark[v] = true;
	for (int v = 0; v < n; v++)
		if (R.dis[v] < B.dis[v] && mark[v]) {
			cout << -1;
			return 0;
		}
	int a = -1, b = inF;
	for (int v = 0; v < n; v++) {
		if (R.dis[v] < B.dis[v])
			a = max(a, B.dis[v]);
		if (R.dis[v] <= B.dis[v])
			b = min(b, B.dis[v]);
	}
	cout << max(a, b) * 2;
}


Measured memory_bytes: 32380
from bisect import bisect
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa))
mid = acc[-1] // 2
i = bisect(acc, mid)
print(min(abs(2 * acc[i] - acc[-1]), abs(2 * acc[i - 1] - acc[-1])))


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素

int main(){
    set<int> s;
    int n;
    cin>>n;
    rep(i,n){
       int a;
       cin>>a;
       s.insert(a);
    }
    if(n==s.size()) cout<<"YES";
    else cout<<"NO";
    cout<<endl;
    return 0;
}

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

using namespace std;

#define ll long long
#define ini(arr, val) memset(arr, (val), sizeof(arr))
#define loop(i,n)  for(ll i=0; i<n; i++)
#define loop1(i,n)  for(ll i=1; i<=n; i++)

#define all(a)      (a).begin(),(a).end()
#define dupli(a)     unique(all(a)),(a).end()
#define exist(s,e)  (s.find(e)!=s.end())
#define dbg(x)  cout << #x << " is " << x << endl;
#define pt(x) cout<<x<<"\n"
#define pts(x) cout<<x<<" "

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


#define inf (int)1e9
#define eps 1e-9
#define PI 3.1415926535897932384626433832795
#define mod 1000000007


#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test   int t; cin>>t; while(t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef set<int> si;

typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pll> vpll;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
typedef set<ll> sl;


//////////////////////////////////////////////////////////////////////////////////////////
//                      main starts
//////////////////////////////////////////////////////////////////////////////////////////
int const lmt=1e5+5;



int main(){

 //    #ifndef ONLINE_JUDGE
 //    freopen("../input.txt", "r", stdin);
 //    freopen("../output.txt", "w", stdout);
	// #endif
 //    fast
    
    ll k;
    cin>>k;
    string s;
    cin>>s;
    ll n=s.size();
    if(n<=k){ pt(s); return 0;}
    loop(i,k){
    	cout<<s[i];
    }
    pts("...");
    pt("");

    

}


/*

// 

*/

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N;
vector<ll> edges[202020];
vector<ll> colors(202020, -1);
queue<ll> mod[3];
vector<ll> vertices[2];
vector<ll> ans(202020,0);

void dfs(ll i, ll col) {
  if (colors[i] != -1)
    return;
  colors[i] = col;
  vertices[col].push_back(i);
  for (auto c : edges[i]) {
    dfs(c, 1-col);
  }
}

void p() {
  for (ll i=1; i<=N; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

signed main() {
  cin >> N;
  for (ll i=1; i<=N; i++) {
    mod[i%3].push(i);
  }
  rep(i, N-1) {
    ll x,y;
    cin>>x>>y;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  dfs(1, 0);

  if (vertices[0].size() <= mod[0].size()) {
    // 1側を 1,2 で埋める
    // 残りを0にする
    for (auto i : vertices[1]) if (!ans[i] && !mod[1].empty()){ ans[i] = mod[1].front(); mod[1].pop(); }
    for (auto i : vertices[1]) if (!ans[i] && !mod[2].empty()){ ans[i] = mod[2].front(); mod[2].pop(); }
    for (ll i=1; i<=N; i++)    if (!ans[i] && !mod[0].empty()){ ans[i] = mod[0].front(); mod[0].pop(); }
    p();
    return 0;
  }

  if (vertices[1].size() <= mod[0].size()) {
    // 0側を 1,2 で埋める
    // 残りを0にする
    for (auto i : vertices[0]) if (!ans[i] && !mod[1].empty()){ ans[i] = mod[1].front(); mod[1].pop(); }
    for (auto i : vertices[0]) if (!ans[i] && !mod[2].empty()){ ans[i] = mod[2].front(); mod[2].pop(); }
    for (ll i=1; i<=N; i++)    if (!ans[i] && !mod[0].empty()){ ans[i] = mod[0].front(); mod[0].pop(); }
    p();
    return 0;
  }

  if (vertices[0].size() >= mod[1].size() && vertices[1].size() >= mod[2].size()){
    // 0側を1で埋める、1側を2で埋める
    // 残りを0にする
    for (auto i : vertices[0]) if (!ans[i] && !mod[1].empty()){ ans[i] = mod[1].front(); mod[1].pop(); }
    for (auto i : vertices[1]) if (!ans[i] && !mod[2].empty()){ ans[i] = mod[2].front(); mod[2].pop(); }
    for (ll i=1; i<=N; i++)    if (!ans[i] && !mod[0].empty()){ ans[i] = mod[0].front(); mod[0].pop(); }
    p();
    return 0;
  }

  if (vertices[0].size() >= mod[2].size() && vertices[1].size() >= mod[1].size()){
    // 0側を2で埋める、1側を1で埋める
    // 残りを0にする
    for (auto i : vertices[0]) if (!ans[i] && !mod[2].empty()){ ans[i] = mod[2].front(); mod[2].pop(); }
    for (auto i : vertices[1]) if (!ans[i] && !mod[1].empty()){ ans[i] = mod[1].front(); mod[1].pop(); }
    for (ll i=1; i<=N; i++)    if (!ans[i] && !mod[0].empty()){ ans[i] = mod[0].front(); mod[0].pop(); }
    p();
    return 0;
  }

  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 26012
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define n_l '\n'

#ifndef ONLINE_JUDGE
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#endif

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef double db;
typedef vector<vi> vvi;
const ll mod=1000000007;
const ll N=200005; //check this
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powb(ll a,ll b) {ll res=1;a ; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

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

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n,k;cin>>n>>k;
    vi a(n);
    forn(i,n)cin>>a[i];
    ll ans=0;
    sort(all(a));
    forn(i,k)ans+=a[i];
    cout<<ans;
}


Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  ll n, k;
  double ans = 0;
  cin >> n >> k;
  vector<double> x(n, 0);
  for (ll i = 1; k > i && i <= n; i++) {
    x[i - 1] = ceil((logl(k) - logl(i)) / logl(2)-0.00000001);
  }
  REP(i, n) {
    if (x[i] == 0) {
      ans += n - i;
      break;
    }
    ans += 1.0 / (pow(2, x[i]));
  }
  ans /= n;
  cout << fixed << setprecision(15) << ans << "\n";

  return 0;
}


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

int main()
{
    int map[50] = {};
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        map[a-1] += 1;
        map[b-1] += 1;
    }
    for(int i = 0; i < n; ++i)
    {
        cout << map[i] << endl;
    }
}

Measured memory_bytes: 256
from collections import deque

N, M = map(int,input().split())
edges = [[int(e)-1 for e in input().split()] for _ in range(M)]
ad = [[] for _ in range(N)]
num = [0] * N
for x, y in edges:
    ad[x].append(y)
    num[y] += 1

S = deque()
L = []
dp = [-1] * N

for v in range(N):
    if num[v] == 0:
        S.append(v)
        dp[v] = 0

while S:
    v = S.popleft()
    L.append(v)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        dp[nv] = max(dp[nv], dp[v] + 1)

ans = max(dp)
print(ans)

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

bool fin(bool ok){
    cout << (ok ? "Yes" : "No") << endl;
    exit(0);
}

int main(){
    int N;
    cin >> N;
    vector<pair<int, int>> A(N), B(N);
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        A[i] = {a, i};
    }
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        B[i] = {a, i};
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(int i=0; i<N; i++) if(A[i].first > B[i].first) fin(false);
    for(int i=0; i<N-1; i++) if(A[i+1].first <= B[i].first) fin(true);

    vector<int> A2B(N);
    for(int i=0; i<N; i++) A2B[A[i].second] = B[i].second;
    int pt = 0, num = 0;
    while(true){
        pt = A2B[pt];
        num++;
        if(pt == 0) break;
    }
    fin(num < N);
    return 0;
}


Measured memory_bytes: 2176
#include<iostream>
#include<tuple>
#include<vector>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

template<typename T>
std::vector<std::vector<T>> mk2d(size_t s1, size_t s2, T const& val) {
  std::vector<T> tmp(s2, val);
  return std::vector<std::vector<T>>(s1, tmp);
}

int const MAXL = 1e5;

int msb_(int x) { return 31 - __builtin_clz(x); }

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<int> V(N), W(N);
  for(int i = 0; i < N; ++i) std::cin >> V[i] >> W[i];
  int pN = std::min(N+1, 1024);
  int maxL = 0;
  std::vector<std::vector<std::tuple<int,int,int>>> Qu(pN);
  int Q; std::cin >> Q;
  for(int q = 0; q < Q; ++q) {
    int u, L; std::cin >> u >> L;
    std::vector<int> nodes;
    int pu = u;
    while(pu >= pN) pu /= 2;
    Qu[pu].emplace_back(q, u, L);
    maxL = std::max(maxL, L);
  }
  auto dp = mk2d(19, maxL+1, (int)0);
  int sumv[256], sumw[256];
  sumv[0] = sumw[0] = 0;
  std::vector<int> ans(Q);
  auto calc = [&](auto&& f, int u, int d)->void {
    if(u >= pN) return;
    int wm = std::min(maxL+1, W[u-1]);
    std::copy_n(dp[d].begin(), wm, dp[d+1].begin());
    for(int w = W[u-1]; w <= maxL; ++w) {
      dp[d+1][w] = std::max(dp[d][w], dp[d][w-W[u-1]] + V[u-1]);
    }
    f(f, u*2,   d+1);
    f(f, u*2+1, d+1);
    
    for(auto [i, xu, L]: Qu[u]) {
      std::vector<int> nodes;
      while(xu >= pN) {
        nodes.push_back(xu);
        xu /= 2;
      }
      int S = (1<<nodes.size());
      int cur = dp[d+1][L];
      for(int s = 1; s < S; ++s) {
        int m = msb_(s);
        sumv[s] = sumv[s^(1<<m)] + V[nodes[m]-1];
        sumw[s] = sumw[s^(1<<m)] + W[nodes[m]-1];
        if(sumw[s] > L) continue;
        cur = std::max(cur, sumv[s] + dp[d+1][L - sumw[s]]);
      }
      ans[i] = cur;
    }
  };
  calc(calc, 1, 0);
  for(auto a: ans) std::cout << a << "\n";
  return 0;
}



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

int main(void) {
	int N, M;
	cin >> N >> M;
	if (N==1 && M==1) {
		cout << 1 << endl;
		return 0;
	}

	if (N==1 || M==1) {
		cout << std::max(N, M)-2 << endl;
		return 0;
	}
	// 2x2以上
	cout << (long long)(N-2)*(M-2) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

void BubbleSort(string* array, int N) {
    for(int i = 0; i < N; i++) {
        for(int j = N-1; j > i; j--) if (array[j][1] < array[j-1][1]) swap(array[j], array[j-1]);
    }
}
void SelectionSort(string* array, int N) {
    for(int i = 0; i < N; i++) {
        int minj = i;
        for(int j = i; j < N; j++) if(array[j][1] < array[minj][1]) minj = j;
        swap(array[i], array[minj]);
    }
}
int main() {
    int n;
    cin >> n;
    string A[n];
    for(int i = 0; i < n; i++) cin >> A[i];
    string B[n];
    memcpy(B, A, sizeof(A));
    BubbleSort(A, n);
    SelectionSort(B, n);
    for(int i = 0; i < n; i++) i != n-1 ? cout << A[i] << ' ' : cout << A[i] << endl;
    cout << "Stable" << endl;
    for(int i = 0; i < n; i++) i != n-1 ? cout << B[i] << ' ' : cout << B[i] << endl;
    bool flag = false;
    for(int i = 0; i < n; i++) if(A[i] != B[i]) flag = true;
    flag ? cout << "Not stable" << endl : cout << "Stable" << endl;
    
    return 0;
}


Measured memory_bytes: 3148
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;cin>>s;
  ll k;cin>>k;
  ll n = s.size();
  set<string>se;
  for(int i=0;i<n;i++){
    string ss = "";
    for(int j=i;j<n;j++){
      ss.pb(s[j]);
      se.insert(ss);
      //  cout<<ss<<endl;
      //cout<<se.size()<<endl;
      auto po = se.end();
      --po;
      if(se.size() > k)se.erase(po);
    }
    //   se.insert(ss);
  }
  ll cnt = 0;
  auto po = se.end();
  --po;
  // cout<<se.size()<<endl;
  cout<<*(po)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

#define SET_MAX 1024

/* ????????????????????£?¨? */
void matrix_cal(double array[2][3]);

/* main??¢??° */
int main(void){
	double a, b, c, d, e, f;
	double array[SET_MAX][2][3];
	int set_cnt, i;

	for(set_cnt = 0;set_cnt < SET_MAX;set_cnt++){
		if(scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) == EOF)break;
		array[set_cnt][0][0] = a;
		array[set_cnt][0][1] = b;
		array[set_cnt][0][2] = c;
		array[set_cnt][1][0] = d;
		array[set_cnt][1][1] = e;
		array[set_cnt][1][2] = f;
	}

	for(i = 0;i < set_cnt;i++){
		matrix_cal(array[i]);
		printf("%.3f %.3f\n", array[i][0][2], array[i][1][2]);
	}

	return 0;
}

/* ??????????????£?????£???????¨????????§£????±?????????¢??° */
void matrix_cal(double array[2][3]){
	/* array[0][0]???1????????? */
	array[0][1] /= array[0][0];
	array[0][2] /= array[0][0];
	array[0][0] = 1.0;

	/* array[1][0]???0????????? */
	array[1][1] -= array[1][0] * array[0][1];
	array[1][2] -= array[1][0] * array[0][2];
	array[1][0] = 0.0;

	/* array[1][1]???1????????? */
	array[1][2] /= array[1][1];
	array[1][1] = 1.0;

	/* array[0][1]???0????????? */
	array[0][2] -= array[0][1] * array[1][2];
	array[0][1] = 0.0;
}

Measured memory_bytes: 1700
#include <iostream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;
#define For(i, a, b) for(long long i = (a); i < (b); ++i)
#define rep(i, n) for(long long i = 0; i < (n); ++i)


int main()
{
	long long N;

	cin >> N;

	long long minAns = N;

	long long sq = sqrtl(N);

	long long ans;

	For(i, 1, (sq + 1)) {
		if ((N % i) == 0) {
			ans = (i - 1) + ((N / i) - 1);
			minAns = min(ans, minAns);
		}
	}

	cout << minAns << endl;

	return 0;
}

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


int main(){	
	long long W;
	long long s_r;
	long long s_c;
	long long H;
	string T;
	string S;
	long long N;
	scanf("%lld",&H);
	scanf("%lld",&W);
	scanf("%lld",&N);
	scanf("%lld",&s_r);
	scanf("%lld",&s_c);
	cin >> S;
	cin >> T;
	
	ll l=0, r=W, u=0, d=H;
	for (int i = N-1; i >= 0; i--) {
		if (T[i] == 'R' && l != 0) l--;
		if (T[i] == 'L' && r != W) r++;
		if (T[i] == 'D' && u != 0) u--;
		if (T[i] == 'U' && d != H) d++;
		if (S[i] == 'L' ) l++;
		if (S[i] == 'R' ) r--;
		if (S[i] == 'U' ) u++;
		if (S[i] == 'D' ) d--;
		if (l == W || r == 0 || u == H || d == 0) {
			cout << "NO" << endl;
			return 0;
		}
	}

	if (u < s_r && s_r <= d && l < s_c && s_c <= r) cout << "YES" << endl; else cout << "NO" << endl;

	return 0;
}



Measured memory_bytes: 776
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	int X, Y;
	cin >> X >> Y;
	int x = 0;
	int y=0;
	if (X == 1 || X == 3 || X == 5 || X == 7 || X == 8 || X == 10 || X == 12) {
		x += 1;
	}
	if (X == 4 || X == 6 || X == 9 || X == 11) {
		x += 2;
	}
	if (X == 2) {
		x += 3;
	}

	if (Y == 1 || Y == 3 || Y == 5 || Y == 7 || Y == 8 || Y == 10 || Y == 12) {
		y += 1;
	}
	if (Y == 4 || Y == 6 || Y == 9 || Y == 11) {
		y += 2;
	}
	if (Y == 2) {
		y += 3;
	}
	if (x == y) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define BITF(n, i) (((n) >> i) & 1)
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= x; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define REPZ(i, x) for (int i = 0; i <= x; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
using namespace std;
#define DUMPOUT cerr
// vector
template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec) is >> x;
  return is;
}
// pair
template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
// vector
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "{";
  REP(i, (int)vec.size())
  os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", ");
  os << "}";
  return os;
}
// map
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) {
  os << "{";
  FORA(itr, map_var) {
    os << *itr;
    itr++;
    if (itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
// set
template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) {
  os << "{";
  FORA(itr, set_var) {
    os << *itr;
    itr++;
    if (itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {
  DUMPOUT << head;
  if (sizeof...(Tail) > 0) DUMPOUT << ", ";
  dump_func(std::move(tail)...);
}
#ifdef DEBUG_
#define DEB
#define DUMP(...)                                                             \
  DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                             \
          << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
          << "    ",                                                          \
      dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define DUMP(...)
#endif

#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
#define pint pair<int, int>
#define ld long double
using namespace std;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> using vec = std::vector<T>;
template <class T> void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int A, B;
  cin >> A >> B;
  print(max(0ll, A - 2 * B));
}

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

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

    set<string> se;
    int len = s.size();
    for (int i = 1; i <= min(5, len); i++) {
        for (int j = 0; j < len - i + 1; j++) {
            string t = s.substr(j, i);
            se.insert(t);
        }
    }

    int cnt = 0;
    for (auto x : se) {
        if (++cnt == k) return cout << x << endl, 0;
    }

    return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<map>
#include<algorithm>
#include <iomanip>
#include <cmath>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>

#define INF 1050000000
#define MOD 1000000007

using namespace std;


int main() {
	int n; cin >> n;
	int a[n + 1];
	for (int i = 1; i < n + 1; i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 1; i < n + 1; i++) {
		if (i == a[a[i]]) { ans++; }
	}

	cout << ans / 2 << endl;

}

Measured memory_bytes: 640
n, m, x, y = map(int, input().split(" "))
xs = list(map(int, input().split(" ")))
ys = list(map(int, input().split(" ")))
xs.append(x)
ys.append(y)
xs.sort()
ys.sort()
if xs[-1] >= ys[0]:
    print("War")
else:
    print("No War")


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }

template<typename T>
T gcd(T u, T v) {
	if (u == 0)return v;
	if (v == 0)return u;
	T r;
	while (v) {
		r = u % v;
		u = v;
		v = r;
	}
	return u;
}

template<typename T>
T up(const T& l, const T& r) {//SegmentTreeのupdate関数
	T res = gcd(l,r);
	return res;
}

template<typename T>
class SegmentTree {
public:
	vector<T> seg;
	int sz = 1;
	T unit;
	//T (*up)(const T& l,const T& r);
	SegmentTree(int n, T unit = 0) {
		this->unit = unit;
		//int sz = 1;
		while (sz < n) sz <<= 1;
		seg.resize(sz * 2, unit);
		//up = &up1;
	}
	void set(const int& k, const T& x) {//左からk番目の葉にxを代入する
		seg[sz - 1 + k] = x;
	}
	T get(const int& k) {//左からk番目の葉を得る
		return seg[sz - 1 + k];
	}
	void update(int k, const T& v) {//k番目の値をvに変更
		k += sz - 1;
		seg[k] = v;
		while (k > 0) {
			k = (k - 1) / 2;
			seg[k] = up(seg[2 * k + 1], seg[2 * k + 2]);
		}
	}
	T query(int a, int b, int k, int l, int r) {//[a,b)のupの合成を求める(a,b,0,0,sz)のように使う
		if (r <= a || b <= l) {
			return unit;
		}
		if (a <= l && r <= b) {
			return seg[k];
		}
		else {
			T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return up(vl, vr);
		}
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	Rep(i, n) {
		cin >> a[i];
	}
	
	SegmentTree<int> st(n, 0);
	int res = 0;
	Rep(i, n) {
		st.update(i, a[i]);
	}
	int sz = st.sz;
	Rep(i, n) {
		int temp = up(st.query(0, i, 0, 0, sz),st.query(i+1,n,0,0,sz));
		chmax(res, temp);
	}
	put(res);
	return 0;
}



Measured memory_bytes: 1664
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node{int left, parent, right;};
Node node[MAX];
int depth[MAX], height[MAX], n, root;

void setDepth(int n, int d){
  depth[n] = d;
  if(node[n].left != NIL) setDepth(node[n].left, d + 1);
  if(node[n].right != NIL) setDepth(node[n].right, d + 1);
}

int setHeight(int n){
  int lh = 0, rh = 0;
  if(node[n].left != NIL) lh = setHeight(node[n].left) + 1;
  if(node[n].right != NIL) rh = setHeight(node[n].right) + 1;
  return height[n] = max(lh, rh);
}

int getSibling(int n){
  int p = node[n].parent;
  if(p == NIL) return NIL;
  else if(node[p].left != n) return node[p].left;
  else return node[p].right;
}

int getDegree(int n){
  return (node[n].left != NIL) + (node[n].right != NIL);
}

void printNodeInf(int n){
  cout << "node " << n << ": ";
  cout << "parent = " << node[n].parent << ", ";
  cout << "sibling = " << getSibling(n) << ", ";
  cout << "degree = " << getDegree(n) << ", ";
  cout << "depth = " << depth[n] << ", ";
  cout << "height = " << height[n] << ", ";
  if(n == root) cout << "root" << endl;
  else if(node[n].left == NIL && node[n].right == NIL) cout << "leaf" << endl;
  else cout << "internal node" << endl;
}

int main(void){
  cin >> n;

  for(int i = 0; i < n; i++) node[i].parent = node[i].left = node[i].right = NIL;

  for(int i = 0; i < n; i++){
    int id, l, r;
    cin >> id >> l >> r;
    node[id].left = l;
    node[id].right = r;
    if(l != NIL) node[l].parent = id;
    if(r != NIL) node[r].parent = id;
  }

  for(int i = 0; i < n; i++) if(node[i].parent == NIL) root = i;

  setDepth(root, 0);
  setHeight(root);

  for(int i = 0; i < n; i++) printNodeInf(i);
  return 0;
}

Measured memory_bytes: 1172
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

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

int N, M, a[112345], fib[112345];

int main() {

	scanf("%d%d", &N, &M);
	a[0] = -1;
	rep(i, M) scanf("%d", &a[i + 1]);

	rep(i, M - 1) {
		if (a[i] + 1 == a[i + 1]) {
			printf("0\n");
			return 0;
		}
	}

	fib[0] = 1;
	fib[1] = 1;
	rep(i, N + 123) {
		fib[i + 2] = (fib[i] + fib[i + 1]) % 1000000007;
	}

	ll ans = 1;


	rep(i, M) {
		ans *= fib[a[i + 1] - a[i] - 2];
		ans %= 1000000007;
	}
	ans *= fib[N + 1 - a[M] - 2];
	ans %= 1000000007;


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

	return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<30;
const ll LINF = 1LL<<58;
const ll mod = 1000000007;

int main(){
    int n;
    cin >> n;
    double ans = 0;
    rep(i,n){
        double a;
        cin >> a;
        ans += 1/a;
    }
    cout << fixed << setprecision(10) << 1/ans << endl;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
MOD = 10**9 + 7

ans = 1
l = 0
r = 0
for i in range(0,n-k+1):  
  l += i
  r += n-i
  ans = (ans + r - l + 1)% MOD    
  
print(ans)  

Measured memory_bytes: 9184
#ifdef __GNUC__
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <atcoder/math>

using namespace std;
using namespace atcoder;

typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> II;
typedef pair<LL, II> III;
typedef priority_queue<III, vector<III>, greater<>> Queue;
static const LL INF = 1LL << 60;

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

#if 0
	auto possible = [&](LL t) {

		return false;
	};
	LL left = 1, right = 1000000000;
	while (right - left > 1) {
		LL mid = (left + right) / 2;
		if (possible(mid)) {
			left = mid;
		} else {
			right = mid;
		}
	}
#endif

void solve(long long T, std::vector<long long> &N, std::vector<long long> &M, std::vector<long long> &A, std::vector<long long> &B) {
	for (LL i = 0; i < T; ++i) {
		LL ans = floor_sum(N[i], M[i], A[i], B[i]);
		cout << ans << endl;
	}
}

int main() {
    long long T;
	std::cin >> T;
	std::vector<long long> N(T);
	std::vector<long long> M(T);
	std::vector<long long> A(T);
	std::vector<long long> B(T);
	for (int i = 0; i < T; i++) {
		std::cin >> N[i]; // N[i]--;
		std::cin >> M[i]; // M[i]--;
		std::cin >> A[i]; // A[i]--;
		std::cin >> B[i]; // B[i]--;
	}
	solve(T, N, M, A, B);
	return 0;
}


Measured memory_bytes: 5288
//I had a dream :)
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 90005;
int x[maxn], y[maxn];
vi buck[maxn];
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int n, m, d; cin >> n >> m >> d;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= m; j++)
        {
            int k; cin >> k;
            x[k] = i; y[k] = j;
        }
    }
    for(int i = 1; i<= d; i++)
    {
        buck[i].pb(0); //dumm;y
        for(int j = i+d; j<= n*m; j+=d)
        {
            buck[i].pb(buck[i].back()+abs(x[j]-x[j-d])+abs(y[j]-y[j-d]));
        }
    }
    int q; cin >> q;
    while(q--)
    {
        int L, R;
        cin >> L >> R;
        int id = L%d;
        if(id == 0)
        {
            int a = L/d, b = R/d;
            a--; b--;
            cout << buck[d][b] - buck[d][a] << endl;
        }
        else
        {
            int a = (L-id)/d, b = (R-id)/d;
            cout << buck[id][b]-buck[id][a] << endl;
        }
    }
}


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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(ll n,m,d;cin>>n>>m>>d&&n|m|d;){
		double x=0;
		if(d==0)
			x=n;
		else if(2*d<n)
			x=2*d+2*(n-2*d);
		else if(d<n)
			x=n-(2*d-n);
		printf("%.9f\n",x/(n*n)*(m-1));
	}
}


Measured memory_bytes: 256
import itertools
import math

n = int(input())
l = []
x = []
y = []
for i in range(n):
    l.append(i+1)
    tmp_x, tmp_y = map(int, input().split())
    x.append(tmp_x)
    y.append(tmp_y)

permutation = list(itertools.permutations(l, n))

ans = 0
for per in itertools.permutations(l, n):
    for i in range(0, n-1):
        suffix = per[i]
        ans += math.sqrt((x[per[i]-1] - x[per[i+1]-1])**2 + (y[per[i]-1] - y[per[i+1]-1])**2)

print(ans / len(permutation))


Measured memory_bytes: 7972
#include <bits/stdc++.h>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

unordered_map<int, int> mp;
vector<int> sticks;
int n,extra,m,firstMatch,firstCnt;
string d[10001];
string maxS="";

string maxStr(string a,string b){
    if(a[0]=='-')return b;
    if(b[0]=='-')return a;
    if(a.size()==b.size())return max(a,b);
    return a.size()>b.size()?a:b;
}

string dp(int extra) {
    if(extra==0) return "";
    if(d[extra]!="")return d[extra];
    string res="-";
    for(int i=0;i<m;i++){
        if(mp[sticks[i]]<=extra){
            string t=dp(extra-mp[sticks[i]])+to_string(sticks[i]);
            res=maxStr(res,t);
        }
    }
    d[extra]=res;
    return res;
}
int main() {
    mp[1]=2;mp[2]=5;mp[3]=5;
    mp[4]=4;mp[5]=5;mp[6]=6;
    mp[7]=3;mp[8]=7;mp[9]=6;
    int i, t;
    cin>>n>>m;

    int first = 999;
    for(i=0;i<m;i++){
        cin >> t;
        sticks.push_back(t);
    }
    cout<<dp(n);
    // cout<<;
    return 0;
}

Measured memory_bytes: 30592
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <tuple>
#include <functional>
#include <map>
#include <unordered_map>
#include <queue>
#include <tuple>

using namespace std;

#define endl '\n'

using ull = unsigned long int;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  const int precision = 13;
  cout.precision(precision);
  cout.setf(ios_base::fixed);

  string s, t; cin >> s >> t;
  vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
  vector<vector<int>> op(s.size() + 1, vector<int>(t.size() + 1, -1));

  for (int i = 1; i <= s.size(); ++i) {
    for (int j = 1; j <= t.size(); ++j) {
      if (s[i-1] == t[j-1]) {
        op[i][j] = 0;
        dp[i][j] = dp[i-1][j-1] + 1;
      } else if (dp[i-1][j] > dp[i][j-1]) {
        op[i][j] = 1;
        dp[i][j] = dp[i-1][j];
      } else {
        op[i][j] = 2;
        dp[i][j] = dp[i][j-1];
      }
    }
  }

  string ans;
  int x = s.size();
  int y = t.size();
  while (x != 0 and y != 0) {
    if (op[x][y] == 0) {
      ans.push_back(s[x-1]);
      --x; --y;
    } else if (op[x][y] == 1) {
      --x;
    } else {
      --y;
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 70912
#include <iostream>
#include <string>

using namespace std;

int main(void) {
    string S;
    cin >> S;
    if(S[2] == S[3] && S[4] == S[5]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int main() {
    long long n, k, ans, ans1, ans2;
    cin >> n >> k;
    if (n < k) {
        if (n < (double)(k / 2)) {
            ans = n;
        }
        else ans = k - n;
    }
    else {
        ans1 = n % k;
        ans2 = (ans1 - k) * -1;
        ans = min(ans1, ans2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import           Control.Monad (replicateM)
import           Data.List     (foldl')

main :: IO ()
main = do
  s <- getLine
  q <- readLn
  qs <- replicateM q getQuery
  putStrLn $ solve s qs

data Query = Reverse | Add Bool Char

getQuery :: IO Query
getQuery = do
  (t:xs) <- words <$> getLine
  if t == "1"
    then return Reverse
    else let [f, c] = xs in return $ Add (f == "1") (head c)

solve :: String -> [Query] -> String
solve s qs = toList $ foldr g (fromList s) (reverse qs)
  where g Reverse xs   = rev xs
        g (Add f c) xs = add c f xs

data DoubleList a = DoubleList ![a] ![a] Bool
  deriving Show

fromList :: [a] -> DoubleList a
fromList xs = DoubleList xs [] True

toList :: DoubleList a -> [a]
toList (DoubleList xs ys True)  = xs ++ reverse ys
toList (DoubleList xs ys False) = ys ++ reverse xs

rev :: DoubleList a -> DoubleList a
rev (DoubleList xs ys f) = DoubleList xs ys $ not f

add :: a -> Bool -> DoubleList a -> DoubleList a
add x True (DoubleList xs ys True)   = DoubleList (x:xs) ys True
add x True (DoubleList xs ys False)  = DoubleList xs (x:ys) False
add x False (DoubleList xs ys True)  = DoubleList xs (x:ys) True
add x False (DoubleList xs ys False) = DoubleList (x:xs) ys False


Measured memory_bytes: 175868
#include<cstdio>
using namespace std;
int main()
{
	int n,a,flg[31],i;
	for(i=1;i<=30;i++)	flg[i]=0;
	for(i=0;i<28;i++){
		scanf("%d",&a);
		flg[a]=1;
	}
	for(i=1;i<=30;i++){
		if(flg[i]!=1){
			printf("%d\n",i);
		}
	}
	return 0;
}


Measured memory_bytes: 2612
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int r;
  cin >> r;
  if(r<1200){
    cout << "ABC" << endl;
  }else if(r<2800){
    cout << "ARC" << endl;
  }else{
    cout << "AGC" << endl;
  }
}


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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

vector<long long> arr;

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;

    for(int i = 0; i < n; ++i){
        long long j;
        cin >> j;
        arr.push_back(j);
    }

    sort(arr.begin(), arr.end());

    long long sz = arr[0];
    long long minimum = 0;

    for(int i = 1; i < n; ++i){
        if(arr[i] - sz > sz){
            minimum = i;
        }
        sz += arr[i];
    }

    cout << n - minimum;

    return 0;
}


Measured memory_bytes: 1400