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

using namespace std;

int main(){
    int h, n, sum = 0;
    cin >> h >> n;
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++){
        cin >> v[i];
        sum += v[i];
    }
    if(sum < h){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 768
from collections import*
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
d=defaultdict(list)
l=[]
for i in range(m):
    p,y=map(int,input().split())
    l.append([p,y])
    d[p].append(y)

for k,v in d.items():
    d[k]=list(enumerate(sorted(v)))
d2=defaultdict(int)
for k,v in d.items():
    for s,t in v:
        d2[(k,t)]=s+1
for i in l:
    print(str(i[0]).zfill(6)+str(d2[tuple(i)]).zfill(6))

Measured memory_bytes: 72128
#include <string>
#include <bits/stdc++.h>
#include <stdio.h>
#include<math.h>
using namespace std;

int main() {
  vector<int> vec(3);
  cin >> vec.at(0) >> vec.at(1) >> vec.at(2);
  sort(vec.begin(), vec.end());
cout << vec.at(0)*vec.at(1)/2 << endl;
}
  


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<utility>
#include<bitset>
#include<complex>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define FOR(i,a,b) for(int i=a; i<b; ++i)
#define MP make_pair
typedef long long LL;
typedef pair<int,int> pii;

const int maxn = 100;
const int Range = maxn * maxn;

int n;
bool vist[Range + 5];

int main() {
	int a;
	vist[0] = 1;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a);
		for(int k = Range; k >= a; --k)
			vist[k] |= vist[k - a];
	}
	int ans = 0;
	for(int i = 1; i <= Range; ++i) {
		if(i % 10 == 0) continue;
		if(vist[i]) ans = i;
	}
	printf("%d\n", ans);
	return 0;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans =0;
	cin >>n;
	vector<ll> a(n);
	rep(i,n) cin >>a[i];
	multiset<int> st;
	rep(i,n) st.insert(a[i]);
	
	while(!st.empty()){
		auto it = st.end(); it--;
		int cr = *it;
		st.erase(it);
		repr(i,32,0){
			ll tg=1LL<<i;
			if(st.count(tg-cr)){
				ans++;
				st.erase(st.find(tg-cr));
				break;
			}
		}
		
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 11136
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<functional>
#include<vector>
#include<queue>
using namespace std;
#define f(i,n) for(int i=0;i<(int)n;i++)
#define MOD 1000000009

int main(void){
	char a[200001];
	char b[200001];
	f(i, 200001){
		a[i] = 0;
		b[i] = 0;
	}
	int n, k;
	int p, q;
	int x, y;
	int z = 0;
	scanf("%d", &n);
	scanf("%s", a);
	scanf("%s", b);
	p = strlen(a);
	q = strlen(b);
	f(i, n){
		x = i % p;
		y = i % q;
		if (a[x] != b[y]){
			if (a[x] > b[y])z = 1;
			break;
		}
	}
	k = n;
	if (z == 0){
		while (z == 0){
			if (k%p == 0){
				z = 2;
				for (int i = 0; i < k / p; i++){
					for (int j = 0; j<p; j++)printf("%c", a[j]);
				}
				for (int i = 0; i < (n - k) / q; i++){
					for (int j = 0; j<q; j++)printf("%c", b[j]);
				}
			}
			k -= q;
		}
	}
	else{
		while (z == 1){
			if (k%q == 0){
				z = 2;
				for (int i = 0; i < k / q; i++){
					for (int j = 0; j<q; j++)printf("%c", b[j]);
				}
				for (int i = 0; i < (n - k) / p; i++){
					for (int j = 0; j<p; j++)printf("%c", a[j]);
				}
			}
			k -= p;
		}
	}

	return 0;
}

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

int main() {
  int H, W, b = 0;
  string a;
  cin >> H >> W;
  for (; b < W + 2; b++) cout << '#';
  for (cout << endl; H; H--) {
    cin >> a;
    cout << '#' << a << '#' << endl;
  }
  for (; b; b--) cout << '#';
}

Measured memory_bytes: 3640
def main():
    N = int(input())
    A = []
    for i in range(N):
        S, P = input().split()
        A.append((S,int(P),i+1))
 
    sort_A = sorted(A, key=lambda x:(x[0], -x[1])) 
    for i in range(N):
        print(sort_A[i][2])
 
main()

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	long long int A, B, K;
	cin >> A >> B >> K;
	if (B - A + 1 >= 2 * K) {
		for (long long int i = 0; i < K; i++) {
			cout << A + i << endl;
		}
		for (long long int i = 0; i < K; i++) {
			cout << B - K + 1 + i << endl;
		}
	}
	else {
		for (long long int i = A; i <= B; i++) {
			cout << i  << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3636
#ITP1_10-C Standard Deviation
while True:
    n= int(input())
    if n==0:
        break
    s = input().split(" ")
    mean = 0.0
    for i in range(n):
        mean += float(s[i])
    mean /= n
    cov = 0.0
    
    for i in range(n):
        cov+=((float(s[i])-mean)**2)/n
    print(cov**0.5)

Measured memory_bytes: 7772
process.stdin.resume();
process.stdin.setEncoding('utf8');
// Here your code !
process.stdin.on( 'data', function(x) {
    calc(x);
});

function calc(x){
    var ary = x.split(" ");
    
    var y = parseInt(ary[0].trim(), 10);
    var z = parseInt(ary[1].trim(), 10);
    var sum1 = y * z;
    var sum2 = (2 * y) + (2 * z);
    
    console.log(sum1 + ' ' + sum2)
}

Measured memory_bytes: 15504
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
	#define SAY(X) cout << (X) << '\n';
#else
	#define DBG(X)
	#define SAY(X)
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for(auto& elem: ret) cin >> elem; return ret; }

int get(int fst, vector<int> seq) {
	int answ = 0;
	int n = len(seq);

	for(int i = 0; i < n; ++i) {
		int must = fst ^ (i & 1);
		answ += (seq[i] != must);
	}

	return (answ & 1 ? INT_INF : answ / 2);
}

void solve() {
	int n = fetch<int>();
	vector<pii> a(n);
	vector<int> seq(n);

	for(int i = 0; i < n; ++i) {
		cin >> a[i].first;
		a[i].second = i & 1;
	}
	
	sort(a.begin(), a.end());

	for(int i = 0; i < n; ++i) {
		seq[i] = a[i].second;
	}

	DBG(seq);
	cout << get(0, seq) << '\n';
}

int main() {
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 1792
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
d = [[10**9 for _ in range(W)] for _ in range(H)]

w_count = -2
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      w_count += 1

que = deque()
que.append([0, 0])
d[0][0] = 0
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == 10**9 and maze[nx][ny] == ".":
      d[nx][ny] = d[p[0]][p[1]] + 1
      que.append([nx, ny])
if d[H-1][W-1] == 10**9:
  print(-1)
else:
  print(w_count - d[H-1][W-1] + 1)

Measured memory_bytes: 3316
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 1000000009;
const ll LINF = 1e18;

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

  ll sum = 0;
  for (int i = 1; i < n; ++i) {
    if (a[i - 1] > a[i]) {
      sum += a[i - 1] - a[i];
      a[i] = a[i - 1];
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 3564
#include<cstdio>
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a+b==c||a+c==b||c+b==a)
	{
printf("Yes\n");
	}
else
{
	printf("No\n");
}
return 0;
}


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

using namespace std;


int main(void){

  int N;
  vector<int> d;

  cin >> N;

  for(int i = 0; i < N;i++){
    int tmp;
    cin >> tmp;
    d.push_back(tmp);
  }

  int sum = 0;
  for(int i = 0;i < N; i++){
    for(int j = i + 1; j < N; j++){
      sum += d.at(i)*d.at(j);
    }
  }

  cout << sum << endl;

  return 0;
}




Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

class union_find {
    private:
        vector<int> par;
        vector<int> ran;
        vector<ll> size;
    public:
        union_find(int n);
        int find(int x);
        void unite(int x, int y);
        bool same(int x, int y);
        ll show_size(int x);
};

union_find::union_find(int n){
    par.resize(n);
    ran.resize(n);
    size.resize(n);
    rep(i,n) par[i] = i;
    rep(i,n) ran[i] = 0;
    rep(i,n) size[i] = 1;
};

int union_find::find(int x) {
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
};

void union_find::unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    ll t = show_size(x)+show_size(y);
    size[x] = size[y] = t;
    if(ran[x] < ran[y]){
        par[x] = y;
        //size[y] += size[x];
    }
    else{
        par[y] = x;
        //size[x] += size[y];
        if(ran[x] == ran[y]) ran[x]++;
    }
};

ll union_find::show_size(int x) {
    if(par[x] == x) return size[x];
    return show_size(par[x] = find(par[x]));
}

bool union_find::same(int x, int y) {
    return (find(x) == find(y));
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    union_find uf(n);
    vector<int> p(n);
    rep(i,n){
        cin >> p[i];
        p[i]--;
    }
    int x, y;
    rep(i,m){
        cin >> x >> y;
        x--; y--;
        uf.unite(x, y);
    }
    int ans = 0;
    rep(i,n){
        if(uf.same(i, p[i])) ans++;
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2176
// LightOj Pass : qavajxyq

#include <bits/stdc++.h>
#define deb(x)     cerr << (#x) << " : " << x << "\n"
#define ll long long int
#define ld long double
using namespace std;
const ll MOD = 1e9 + 7 ;
const ll INF = 1e18;

ll phi, m;
ll powmod(ll a, ll b, ll mod = MOD){
	ll res = 1ll;
	b %= (phi), a %= mod;
	while(b){
		if(b%2 == 1)	res = (res * a) % mod;
		a = (a * a) % mod;
		b /= 2;
	}
	return res;
}

class something {
	public:
	ld func(int dd, int t){
		int m = min(2 * dd, t);

		ld d = dd;
		ld unit = 1.0 / (d * d);
		ld dp[(1 << (m + 1))];
		for(int i = 0; i < (1 << (m + 1)); i++)	dp[i] = 0.0;
		dp[0] = 1.0;
		ld prob[100];
		for(int i = 0; i < 100; i++)	prob[i] = 0.0;

		for(int i = 0; i < dd; i++){
			for(int j = 0; j < dd; j++){
				prob[i + j + 2] += unit;
			}
		}

		ld rej = 0.0;
		int sum = 0, tmp, b;
		bool state;

		ld ans = 0.0;
		for(int mask = 1; mask < (1 << m); mask++){
			rej = 0.0;
			for(int sum = 2; sum <= 12; sum++){
				state = false;
				for(int a = 0; (2*a) < sum; a++){
					b = sum - a;
					if(a == b or b > dd)	continue;
					tmp = (1 << (a-1)) | (1 << (b-1));
					if(a == 0){
						tmp = (1 << (b-1));
					}
					if((mask&tmp) == tmp){
						state = true;
						dp[mask] += (dp[mask^tmp] * prob[sum]);
					}
				}

				if(!state){
					rej += prob[sum];

				}
			}
			cout << mask << " " << dp[mask] << " " << rej << "\n";
			ld tt = 0.0;

			for(ld i = 1.0; i <= 12.0; i++){
				int j = i - 1.0;
				if(mask&(1 << j))	tt += i;
			}

			ans += (dp[mask] * rej * tt);
			deb(rej);
		}

		deb(ans);

		ld tot = t * (t + 1);
		tot /= 2.0;
		return tot - ans;
	}
};

int n;
vector<vector<int>> edges;
int sub[500000];
ll dp[500000], res[500000];

void rec(int u, int par = -1){
	dp[u] = 1ll, sub[u] = 1;
	for(auto v : edges[u]){
		if(v != par){
			rec(v, u);
			sub[u] += sub[u];
			dp[u] = (dp[u] * (1ll + dp[v])) % m;
		}
	}
}

void dfs(int u, ll ans = 0, int par = -1){
	res[u] = ans;
	ll tmp;
	// deb(u), deb(ans);

	ll temp[edges[u].size() + 1];
	int xx = edges[u].size() + 1;
	temp[xx-1] = 1ll;
	for(int i = xx - 2; i >= 0; i--){
		temp[i] = temp[i+1];
		if(edges[u][i] == par)	continue;
		temp[i] = (temp[i] * (dp[edges[u][i]] + 1ll)) % m;
		// deb(temp[i]);
	}
	ll cur = ans + 1ll;
	res[u] = (cur * temp[0]) % m;
	// deb(res[u]);

	int i = 0;
	for(auto v : edges[u]){
		if(v != par){
			tmp = (cur * temp[i + 1]) % m;
			// deb(tmp);
		//	deb(v), deb(powmod((dp[v] + 1ll) % m, phi - 1ll, m));
			dfs(v, tmp, u);
			cur = (cur * (dp[v] + 1ll)) % m;
		}
		i++;
	}
}

int main(){	

 
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	edges.resize(n + 1);
	int u, v;

	for(int i = 0; i < n-1; i++){
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}

	rec(1);

	phi = m;
	ll tmp = m;
	for(ll i = 2; (i * i) <= tmp; i++){
		if(tmp % i == 0){
			while(tmp % i == 0){
				tmp /= i;
			}

			phi /= i;
			phi *= i-1ll;
		}
	}

	if(tmp > 1ll){
		phi /= tmp;
		phi *= tmp - 1ll;
	}

	dfs(1, 0ll);

	for(int i = 1; i <= n; i++)	cout << res[i] << " "; 
}	

Measured memory_bytes: 22656
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>
#include <fstream>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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 COM (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;
}

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

    COMinit();

    ll n;
    cin >> n;
    vector<ll> a(n+1);
    vector<ll> idx(n, -1);
    ll c;
    Rep (i, n+1) {
        cin >> a[i];
        a[i]--;
        if (idx[a[i]] == -1) idx[a[i]] = i;
        else c = i - idx[a[i]];
    }

    // cout << "c=" << c << "\n";

    for (ll k = 1; k <= n+1; k++) {
        cout << (COM(n+1, k) - COM(n-c, k-1) + MOD) % MOD << "\n";
    }
}

Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
	vvi ans(101,vi(101,INF));
	vvi data;
	rep(i,n){
	    int x,y,h;
	    cin>>x>>y>>h;
	    data.push_back(vi{x,y,h});
	}
	sort(all(data),[](vi a,vi b){return a[2]>b[2];});
	for(auto&d:data){
	    rep(cx,101)rep(cy,101){
	        int H=abs(d[0]-cx)+abs(d[1]-cy)+d[2];
	        if(ans[cy][cx]==INF)ans[cy][cx]=H;
	        if(d[2]==0){
	            if(ans[cy][cx]>H)ans[cy][cx]=-1;
	        }else{
    	        if(ans[cy][cx]!=H)ans[cy][cx]=-1;
	        }
	    }
	}
	rep(cx,101)rep(cy,101){
	    if(ans[cy][cx]!=-1){
	        cout<<cx<<" "<<cy<<" "<<ans[cy][cx]<<endl;
	        return 0;
	    }
	}
    cout<<ans[1000000][1]<<endl;
	return 0;
}


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

int main() {
  string s;
  cin >> s;
  map<char, int> mp;
  bool flg = true;
  for(auto x : s) ++mp[x];
  if(mp.size() == 2) {
    for(auto x : mp) {
      if(x.second != 2) flg = false;
    }
    if(flg) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
map<string, int> m;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        m[s]++;
    }
    map<string, int>::iterator it;
    int mmax = 0;
    string s;
    vector<string> v;
    for (it = m.begin(); it != m.end(); it++) {
        if (it->second > mmax) {
            mmax = it->second;
            v.clear();
            v.push_back(it->first);
        } else if (it->second == mmax) {
            v.push_back(it->first);
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << endl;
    }
}

Measured memory_bytes: 26868
import sys

#+++++

def nn(val, count, aal):
	#pa((val,count,aal))
	if aal[val] >= 0:
		return aal[val]
	
	ll=[1]
	i=1
	while 6**i <= val:
		ll.append(6**i)
		i+=1
	
	i=1
	while 9 ** i <= val:
		ll.append(9**i)
		i+=1
	
	ll=ll[::-1]
	min_v = val
	for l in ll:
		temp = nn(val-l, count+1,aal)
		min_v = min(min_v,temp)
	
	aal[val]=min_v+1
	return min_v+1
	
	
		
def main():
	N = int(input())
	al=[-1]*(N+1)
	al[0:6]=[0,1,2,3,4,5]
	#print(al[0:10])
	ans=nn(N,0,al)

	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 46300
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
struct node{
	ll sum;int id;
	bool operator<(const node n)const{
		return sum>n.sum;
	}
}p[maxn];
int n,sz[maxn],fa[maxn];
int to[maxn],nxt[maxn],head[maxn],el;
ll sum[maxn],tot;
inline void add(int u,int v){
	to[++el]=v;nxt[el]=head[u];head[u]=el;
}
void dfs(int u,ll dis){
	tot+=dis;
	for(int i=head[u];i;i=nxt[i]) dfs(to[i],dis+1);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&p[i].sum),p[i].id=i,sz[i]=1;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++) sum[i]=p[i].sum;
	for(int i=1;i<n;i++){
		int f=lower_bound(sum+1,sum+n+1,sum[i]-n+2*sz[i],greater<ll>())-sum;
		if(sum[f]!=sum[i]-n+2*sz[i] || f==i) return puts("-1"),0;
		fa[p[i].id]=p[f].id;sz[f]+=sz[i];add(f,i);
	}
	dfs(n,0);
	if(tot!=sum[n]) return puts("-1"),0;
	for(int i=1;i<=n;i++) if(fa[i]) printf("%d %d\n",i,fa[i]);
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powmod(ll b, ll e){ll r=1;while(e>0){if(e&1)r=(r%MOD)*(b%MOD)%MOD;b=(b%MOD)*(b%MOD)%MOD;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

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; }
template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    };
}fastio;

int main(){

    int n;
    cin >> n;
    ll ans = 0;
    map<string, ll> mp;
    rep(i, n){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        mp[s]++;
    }
    for(auto x : mp){
        ll y = x.second;
        ans += y*(y-1)/2;
    }
    ppp(ans);


    return 0;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  ui N, M; cin >> N >> M;
  multiset<ull> A{};
  for(ui i = 0; i < N; ++i){
    ui a; cin >> a;
    A.emplace(a);
  }
  while (M)
  {
    auto it = A.end();
    --it;
    auto n = *it / 2;
    A.erase(it);
    A.emplace(n);
    --M;
  }

  // vector<ull> A(N);
  // for(auto& a : A) cin >> a;
  // boost::sort(A, std::greater<ull>());

  // for(size_t i = 0; i < N; ++i)
  // {
  //   if(i == N - 1){
  //     if(M){
  //       A[i] = A[i] / (2 << (M - 1));
  //     }
  //   }
  //   else
  //   {
  //     ull tmp{};
  //     auto a = A[i];
  //     while (a >= A[i + 1])
  //     {
  //       ++tmp;
  //       if(tmp < M){
  //         a = A[i] / (2 << (tmp - 1));
  //       }
  //       else
  //       {
  //         break;
  //       }
  //     }
  //     M -= tmp;
  //     A[i] = a;
  //   }
  // }
  auto ans = boost::accumulate(A, (ull)0);
  cout << ans << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 4992
<?php
  list($n, $k) = explode(" ", trim(fgets(STDIN)));

  $v = explode(" ", trim(fgets(STDIN)));

  $max = 0;
  $sum = 0;
  for ($left=0; $left<=$n; $left++) {
    for ($right=0; ($right+$left)<=$n; $right++){
      if($right+$left > $k){
        continue;
      }

      $sum = 0;
      $smh = new SplMinHeap();
      for ($i=0; $i<$left; $i++){
        $sum += $v[$i];
        $smh->insert($v[$i]);
      }
      for ($i=0; $i<$right; $i++){
        $sum += $v[$n-$i-1];
        $smh->insert($v[$n-$i-1]);
      }
        //echo $left." ".$right." ";
      for ($i=0; $i<($k-$right-$left);$i++){
        if($smh->isEmpty()){
          break;
        }
        $a = $smh->extract();
        if($a < 0){
          $sum -= $a;
        }else{
          break;
        }
      }
      //echo $sum.PHP_EOL;
      $max = max($max, $sum);
    }
  }
  echo $max;

Measured memory_bytes: 4728
N = int(input())
S = list(input())
T = list(input())

ans = N + N
for i in range(N):
  w = S + T[-(i+1):]
  if w[:N] == S and w[-N:] == T:
    ans = min(ans,i+N+1)

if S == T:
  ans = N
    
print(ans)
    


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

  int n, a;
  cin >> n;
  multiset<int> q;
  rep(i,n){
    cin >> a;
    auto it = q.upper_bound(a - 1);
    if (it != q.begin())
      q.erase(--it);
    q.insert(a);
  }
  cout << q.size() << '\n';
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        vi v(3);
        rep(i,3)cin>>v[i];
        sort(all(v));
        cout<<v[0]*v[1]/2<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
typedef long long int lli;
using namespace std;

const int MAX_WH=100;
int dx[2][6]={{0,-1,0,1,1,1},{-1,-1,-1,0,1,0}};
int dy[6]={-1,0,1,1,0,-1};
int ans=0;
int a[MAX_WH+2][MAX_WH+2];
int W,H;

void dfs(int x,int y){
	a[y][x]=2;
	for(int i=0; i<6; ++i){
		int nx=x+dx[(y+1)%2][i];
		int ny=y+dy[i];
		if(0<=nx&&nx<=W+1&&0<=ny&&ny<=H+1){
			if(a[ny][nx]==1) ++ans;
			else if(a[ny][nx]==0) dfs(nx,ny);
		}
	}
}

int main(){
	cin >> W >> H;
	for(int i=1; i<=H; ++i){
		for(int j=1; j<=W; ++j){
			cin >> a[i][j];
		}
	}
	dfs(0,0);
	cout << ans << "\n";
	return 0;
}

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

#define MS(ARRAY,VALUE) memset(ARRAY,VALUE,sizeof(ARRAY))
#define Fin freopen("input.txt","r",stdin)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define Fout freopen("output.txt","w",stdout)
#define rep(i,a,b) for(i=a;i<=b;i++)
#define EPS 0.00000001
#define INF INT_MAX
#define PI 2*acos(0.0)
#define P1(XX) cout<<"db1: "<<XX<<endl
#define P2(XX,YY) cout<<"db2: "<<XX<<" "<<YY<<endl
#define P3(XX,YY,ZZ) cout<<"db3: "<<XX<<" "<<YY<<" "<<ZZ<<endl
#define set(XX,POS) XX|=(1<<POS)
#define reset(XX,POS) XX&=(~(1<<POS))
#define check(XX,POS) (bool)(XX&(1<<POS))
#define toggle(XX,POS) (XX^(1<<POS))
#define SORT(v) sort(v.begin(),v.end())
#define REVERSE(V) reverse(v.begin(),v.end())
#define VALID(X,Y,R,C) X>=0 && X<R && Y>=0 && Y<C
#define SIZE(ARRAY) sizeof(ARRAY)/sizeof(ARRAY[0])
#define RT printf("Run Time : %0.3lf seconds\n", clock()/(CLOCKS_PER_SEC*1.0))

#define ll long long
#define MX 100005
#define MOD 1000000007LL
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree< pair<int,int> , null_type, less< pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> odrst;


int main()
{
    //Fin;
    ll n, a, b, m, ans;
    cin>>n>>a>>b;
    if(a>b)swap(a,b);
    m=(b-a);
    if(m%2==1){
        ans=min(b-1, n-a);
        m=(n-a+n-b);
        if(m%2==1)m++;
        ans=min(ans, m/2);


        m=(a+b-2);
        if(m%2==1)m++;
        ans=min(ans, m/2);


    }
    else ans=m/2;
    cout<<ans<<endl;
    return 0;
}



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

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

    int t;
    while(cin >> t && t){

        int n;
        cin >> n;

        int sum = 0;
        for(int i = 0; i < n; ++i){
            int s, f;
            cin >> s >> f;
            sum += f - s;
        }

        if(sum >= t)
            cout << "OK" << endl;
        else
            cout << t - sum << endl;
    }

   return 0;
}

Measured memory_bytes: 1196
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define long long int
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]==s[i+1])
        continue;
        else
        count+=1;
    }
    cout<<count<<endl;
    return 0;


}

Measured memory_bytes: 512
N,W,*A=`dd`.split.map &:to_i
h={0=>0}
N.times{
	a,b,*A=A
	h.to_a.each{|w,v|
		h[w+a]=[h[w+a]||0,v+b].max if w+a<=W
	}
}
p h.values.max

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

#define int long long
#define ld long double

#define pb push_back
#define F first
#define S second
#define I insert
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define debug1(a) cerr<<" "<<#a<<" : "<<a<<"\n"
#define debug2(a,b) cerr<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define debug3(a,b,c) cerr<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define debug4(a,b,c,d) cerr<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"

#define INF (int)10000000000000000
#define PI (double)3.14159265358979
// #define M 421412341324321
#define MOD 998244353


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
 	int x;
 	cin>>x;

 	cout << ((x>=30)?"Yes":"No");
    
    return 0;
}



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

using namespace std;

string x;

int k, ans;

int main() {
    cin >> x;

    k = 0, ans = x.length();
    for (int i = 0; i < x.length(); i++) {
        if (x[i] == 'S') {
            k++;
        }

        if (x[i] == 'T') {
            if (k > 0) {
                k--;

                ans -= 2;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    for(int i = 2; i * i <= n; i++){
        int now = n, sum = 0;
        while(now != 0){
            sum += now % i;
            now /= i;
        }
        if(sum == s){
            cout << i << endl;
            return 0;
        }
    }
    if(n == s){
        cout << n + 1 << endl;
        return 0;
    }
    int ans = INF;
    for(int i = 1; i * i <= n; i++){
        if((n - s) % i != 0) continue;
        int b = (n - s) / i + 1;
        int y = s - i;
        if(!(2 <= b && 0 <= i && i < b && 0 <= y && y < b)) continue;
        chmin(ans, b);
    }
    if(ans != INF) cout << ans << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<string> ves;
typedef vector<vector<int>> ve_vei;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define fs first
#define sc second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
 
int main() {
	//cout.precision(10);
	cin.tie(0);
	ios::sync_with_stdio(false);

    string s; cin >> s;
    vector<bool> check(26);
    rep(i,26) check[i] = false;

    rep(i,s.size()) {
        if(check[s[i] - 'a']) {
            cout << "no" << endl;
            return 0;
        }
        if(!(check[s[i] - 'a'])) check[s[i] - 'a'] = true; 
    }
    cout << "yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    ll x;
    cin >> x;
    ll yokin = 100;
    for (int i=1; true; i++) {
        yokin = (ll)(1.01 * yokin);
        if (yokin >= x) {
            cout << i << '\n';
            return 0;
        }
    }
}

Measured memory_bytes: 3640
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;

int main(void) {

  ll n;
  cin >> n;
  ll a[55], b[55];
  rep(i, n) cin >> a[i];


  sort(a, a + n);
  ll s = 0;
  rep(i, n) {
    b[i] = (a[i] - a[0]) / (n + 1LL);
    s += (a[i] - a[0]) / (n + 1LL);
  }

  rep(i, n) a[i] = a[i] + s - b[i] - n * b[i];
  sort(a, a + n);
  

  ll mi = LLONG_MAX;
  rep(i, n) {
    ll x = max(0LL, a[i] - i);
    mi = min(mi, n - 1 - i + n * x);
  }
  cout << s + mi << endl;
}

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

int h1[31], w1[31], h2[31], w2[31];
long long A, B, C, D;
long long pow3[31];

int calch(int n) {
  if (n == -1) return n;
  if (h1[n] != h2[n]) return -1;
  if (h1[n] != 1) return calch(n - 1);
  bool c = false;
  if (w1[n] != w2[n] && w1[n + 1] == w2[n + 1]) c = true;
  if (abs(B - D) > 2 * pow3[n]) c = true;
  if (c) return n;
  else return calch(n - 1);
}

int calcw(int n) {
  if (n == -1) return n;
  if (w1[n] != w2[n]) return -1;
  if (w1[n] != 1) return calcw(n - 1);
  bool c = false;
  if (h1[n] != h2[n] && h1[n + 1] == h2[n + 1]) c = true;
  if (abs(A - C) > 2 * pow3[n]) c = true;
  if (c)
    return n;
  else
    return calcw(n - 1);
}


int main(){
  pow3[0] = 1; rep(i, 30) pow3[i + 1] = pow3[i] * 3; 
  int Q; cin >> Q;
  rep(q, Q){ 
    cin >> A >> B >> C >> D;
    A--; B--; C--; D--;
    long long H1 = A, W1 = B, H2 = C, W2 = D;
    rep(i, 30) {
      h1[i] = H1 % 3; H1 /= 3;
      w1[i] = W1 % 3; W1 /= 3;
      h2[i] = H2 % 3; H2 /= 3;
      w2[i] = W2 % 3; W2 /= 3;
    }
    long long ans = abs(A - C) + abs(B - D);
    int ch = calch(30), cw = calcw(30);
    int n = max(ch, cw);
    if (n >= 0) {
      long long S, T;
      if(ch > cw) {
        S = A; T = C; 
      } else {
        S = B; T = D;
      }
      S %= pow3[n]; T %= pow3[n];
      long long los = min(min(S, T) + 1, pow3[n] - max(S, T));
      ans += los * 2;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 384
#include<iostream>
#include<functional>
#include<utility>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;
const auto MOD = 1000000007;
const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef vector<int> VI;
typedef vector<long long> VLL;


int n, m;
string s,t;

int main() {
	cin >> n;
	VI a(n),b(n),c(n-1);
	rep(i, n) { cin >> m;a[i] = m - 1; }
	rep(i, n)cin >> b[i];
	rep(i, n-1)cin >> c[i];
	int ans = 0;
	int pre = -2;
	for (int i = 0; i < n; i++)
	{
		ans += b[a[i]];
		if (pre == a[i] - 1)ans += c[a[i]-1];
		pre = a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
x=[int(i) for i in input (). split ()]
g=[0,0]
for i in range(len(x)):
    if x[i]==2:
        g[i]=2
    elif x[i]==4 or x[i]==6 or x[i]==9 or x[i]==11:
        g[i]=1
if g[0]==g[1]:
    print ("Yes")
else:
    print ("No")

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

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

  int x = n;
  int sum = 0;
  while (x > 0) {
    sum += x % 10;
    x /= 10;
  } 

  if (n % sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;     

  return 0;
}


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

int main() {
    int n, count=0;
    int a[100];

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

    cout << count << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x


using namespace std;

const int INF = INT_MAX;
const long long INFL = 1LL<<40;
const double PI = atan(1)*4;
const long long MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

int main() {
    int n,k;cin>>n>>k;
    vector<ll> a(n);cin>>a;
    
    vector<ll> cum(n+1,0);
    cum[0] = max(0LL,a[0]);
    repsg(i,1,n){
        cum[i] =cum[i-1]+max(0LL,a[i]);
    }
    
    vector<ll> cumsigned(n+1,0);
    rep(i,k){
        cumsigned[0]+=a[i];
    }
    repsg(i,1,n-k+1){
        cumsigned[i] = cumsigned[i-1] - a[i-1] + a[i+k-1];
    }
    
    vector<ll> cumabs(n+1,0);
    rep(i,k){
        cumabs[0]+=max(0LL,a[i]);
    }
    
    repsg(i,1,n-k+1){
        cumabs[i] = cumabs[i-1] - max(0LL,a[i-1]) + max(0LL,a[i+k-1]);
    }
    
    ll mx = 0;
    rep(i,n-k+1){
        mx = max(mx,cum[n-1]-cumabs[i]+max(0LL,cumsigned[i]));
    }
    
    cout<<mx<<endl;
    
    
    return 0;
}




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

#define White 0 //未訪問
#define Gray 1 //訪問中、または未訪問へのEdgeがある
#define Black 2 //訪問済み

int n;
int Graph[100][100] = {};

int color[100] = {}, d[100], f[100], tt; 
// d[v] = v 訪問時の時間 f[v] = v の隣接リスト調査後の時間 tt = 時間の記録

int nt[100] = {};


//u に隣接する v を番号順に取得
int next(int u){
  for(int v = nt[u] ; v < n ; v++ ){
    nt[u] = v + 1;
    if(Graph[u][v] != 0) return v;
  }
  return -1;
}

void dfs_visit(int r){
  stack<int> S;
  S.push(r); //スタート地点をスタックに積む

  color[r] = Gray; //スタート地点を訪問済みに

  tt++;
  d[r] = tt; //時間を取得

  while(!S.empty()){
    int u = S.top();  //topの値を入れる
    int v = next(u);
    if(v != -1){
      //末訪問なら訪問中にし時間を取得、次の頂点をスタックに積む
      //どちらでもなければ、popでスタックから外し訪問済みにする
      if(color[v] == White){ 
	color[v] = Gray;
	tt++;
	d[v] = tt;
	S.push(v);
      }
    }else{
      S.pop();
      color[u] = Black;
      tt++;
      f[u] = tt;
    }
  }
}
  
void dfs(){
  tt = 0;

  for(int u = 0 ; u < n ; u++){
    if(color[u] == White) dfs_visit(u); //その頂点が未訪問なら
  }

  for(int i = 0 ; i < n ; i++){
    cout << i + 1 << " " << d[i] << " " << f[i] << endl;
  }
}

int main(){
  int u, k, v; //u = 頂点番号 k = 出次数 v = u に隣接する頂点番号

  cin >> n;
     
  for(int i = 0 ; i < n ; i++){
    cin >> u >> k; 
    u--;
    for(int j = 0 ; j < k ; j++){
      cin >> v; 
      v--;
      Graph[u][v] = 1;
    }
  }

  dfs();
     
  return 0;
}

Measured memory_bytes: 1240
N, M = map(int, input().split())
lights = [list(map(int, input().split())) for _ in range(M)]
p_values = list(map(int, input().split()))

switch_conbs = []
for i in range(2 ** N):
    conb = bin(i)[2:].zfill(N)
    switch_conbs.append(list(map(int, list(conb))))

for i, light in enumerate(lights):
    temp = []
    for switch_conb in switch_conbs:
        s = 0
        for v in light[1:]:
            s += switch_conb[v - 1]
        if s % 2 != p_values[i]:
            temp.append(switch_conb)
    
    for l in temp:
        switch_conbs.pop(switch_conbs.index(l))

print(len(switch_conbs))

Measured memory_bytes: 3188
using System;

class Myon{
    static void Main(string[] args){
        int N = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();

        int r = 0;

        for(int i = 0;i < N;i ++){
            if(s[i] == 'R')r++;
        }

        if(r > N / 2)Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GET_ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
#define LL long long
#define VI vector<int>
#define VL vector<LL>
#define VII vector< vector<int> >
#define VLL vector< vector<LL> >
#define VS vector<string>
#define PII pair<int,int>
#define PIS pair<int,string>
#define PSI pair<string,int>
#define PLL pair<ll,ll>
LL facctorialMethod(int k);
int main(){
    LL n,n_val,n_rem;
    string ans;
    VS s(26);
    cin >> n;
    for(int i = 0; i < 26; i++) {
        s[i] = i + 97;
    }
/*
    for(int i = 0; i < 26; i++) {
        cout << s[i] << endl;
    }
*/
    n_rem = (n-1)%26 ;
    ans = s[n_rem];
    n_val = n - n_rem;

//    cout << "n_val :" << n_val << endl;
//    cout << "n_rem :" << n_rem << endl;
    while (n_val >= 26) {
        n_val = (n_val-1) / 26;
        n_rem = (n_val-1) % 26;
        ans += s[n_rem];
//        cout << "n_val :" << n_val << endl;
//        cout << "n_rem :" << n_rem << endl;
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;

    return 0;
}

LL facctorialMethod(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i){
        sum *= i;
    }
    return sum;
}


Measured memory_bytes: 3568
import sys
for line in sys.stdin:
  xs = [int(x) for x in line.strip().split(',')]

  v2 = xs.pop()
  v1 = xs.pop()

  sumed = sum(xs)
  #print(sumed)
  #print('time', sumed/(v1+v2) )
  t = sumed/(v1+v2)
  #print('distance', t*v1)

  t = t*v1
  res = 0
  for index, x in enumerate(xs):
    t -= x
    if t == 0.0:
      res = index + 1
      break
    elif t < 0.0:
      res = index + 1
      break

  print(res)


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

using namespace std;
const int N=2e5+5,mod=1e9+7;
#define ll long long
ll a[N],b[N];
ll cum[N];
ll ans=0,R;
ll n,k;
bool valid(int r)
{
    ans=0;
    ll t=k;
    for(int i=0;i<n;i++)
    {
        ll idx=lower_bound(b,b+n,r-a[i])-b;
        if(idx==n) continue;
        idx=n-1-idx;
        if(idx<i) continue;
        ll sz=idx-i+1;
        t-=sz*2-1;
        ll sum=cum[idx];
        if(i) sum-=cum[i-1];
        ans+=sum*2+a[i]*(sz-1)*2;
    }
    R=t;
    return t>0;
}
ll bs()
{
    ll s=0,e=2e5+5,mid;
    while(s<e)
    {
        mid=(s+e)/2;
        if(valid(mid)) e=mid;
        else s=mid+1;
    }
    return s;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i],b[i]=a[i];
    sort(a,a+n);
    sort(b,b+n);
    reverse(a,a+n);
    cum[0]=a[0];
    for(int i=1;i<n;i++)
        cum[i]=cum[i-1]+a[i];

    ll B=bs();
    valid(B);
    cout<<ans+R*(B-1)<<endl;
    return 0;
}


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

int main()
{
	int n;
	cin >> n;
	priority_queue<double, vector<double>, greater<double>> ingredients;
	for (int i = 0; i < n; i++)
	{
		double ingredient;
		cin >> ingredient;
		ingredients.push(ingredient);
	}
	
	while (ingredients.size() != 1)
	{
		double firstMinIngredient = ingredients.top(); 
		ingredients.pop();
		double secondMinIngredient = ingredients.top();
		ingredients.pop();
		double mixIngredient = (firstMinIngredient + secondMinIngredient) / 2.0;
		ingredients.push(mixIngredient);
	}

	printf("%.5f", ingredients.top());


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m;
long long k;
long long x[N];
int v[N],p[N],vis[N],fin[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
    for(int i=1;i<n;i++) v[i]=x[i+1]-x[i],p[i]=i;
    scanf("%d%lld",&m,&k);
    for(int i=1,t;i<=m;i++){
        scanf("%d",&t);
        swap(p[t-1],p[t]);
    }
    for(int i=1;i<n;i++)
        if(vis[i]==0){
            vector<int> vec;vec.push_back(i);
            for(int j=p[i];j!=i;j=p[j]) vec.push_back(j);
            int num=k%vec.size();
            for(int j=0;j<vec.size();j++){
                fin[vec[j]]=vec[(j+num)%vec.size()];
                vis[vec[j]]=1;
            }
        }
    for(int i=1;i<n;i++) fin[i]=v[fin[i]];
    for(int i=2;i<=n;i++) x[i]=x[i-1]+fin[i-1];
    for(int i=1;i<=n;i++) printf("%lld\n",x[i]);
    return 0;
}

Measured memory_bytes: 3696
// https://atcoder.jp/contests/abc166/tasks/abc166_c
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    vector<pair<int, int>> P(N);
    REP(i, N) {
        cin >> H[i];
        P[i].first = H[i];
        P[i].second = i;
    }
    sort(ALLR(P));
    vector<vector<int>> v(N);
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        v[a].emplace_back(b);
        v[b].emplace_back(a);
    }
    vector<bool> flags(N, true);
    for (auto &x : P) {
        for (auto &y : v[x.second]) {
            if (x.first >= H[y]) {
                flags[y] = false;
            }
        }
    }
    int ans = 0;
    REP(i, N) {
        if (flags[i]) {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 11388