akhauriyash/Code-Regression huggingface dataset:
#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <cctype>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <stack>
#include <ctime>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(ALL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
#define PB push_back
#define MP make_pair

using namespace std;

const double eps = 1e-8;

typedef map<int,int> MII;
typedef map<string,int> MSI;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long double> VD;
typedef pair<int,int> PII;
typedef long long int64;
typedef long long LL;
typedef unsigned int UI;
typedef long double LD;

int main() {
    int n;
    cin >> n;
    vector<int> d(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }
    sort(d.begin(), d.end());
    if (d[n / 2] == d[n / 2 - 1]) cout<<0<<endl;
    else cout<< d[n / 2] - d[n / 2 - 1]<<endl;
    return 0;
}


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

long long lcm(long long a, long long b) {
	long long old_old_a = a, old_old_b = b;
	long long old_a, old_b;
	while (b != 0) {
		old_a = a;
		a = b;
		old_b = b;
		b = old_a % b;
	}
	long long g = old_b;
	return old_old_a / g * old_old_b;
}

int main() {
	int n;
	cin >> n;
	long long t;
	long long ans = 1ll;
	for (int i = 0; i < n; i++) {
		cin >> t;
		ans = lcm(t, ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e3+5;
ll dp[N][N],n,k;
vector<pair<ll,ll> >v;

ll solve(ll l,ll r){
    if(r<l) return 0;
    if(dp[l][r]!=-1) return dp[l][r];
    ll i=l+n-r-1;
    return dp[l][r]=max(v[i].first*abs(v[i].second-l)+solve(l+1,r),v[i].first*abs(v[i].second-r)+solve(l,r-1));
}

int main(){
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>k;
        v.push_back({k,i});
    }
    sort(v.rbegin(),v.rend());
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,n-1);
    return 0;
}



Measured memory_bytes: 35192
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXC 100000

int main() {
  int N, M, R; cin >> N >> M >> R;
  vector<int> r(R);
  for (int i = 0; i < R; i++) { cin >> r[i]; r[i]--; }
  sort(r.begin(), r.end());
  int INF = MAXC * (N - 1);

  int d[N][N] = {};
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      d[i][j] = INF;
    }
  }

  for (int i = 0; i < M; i++) {
    int A, B, C; cin >> A >> B >> C; A--; B--;
    d[A][B] = C;
    d[B][A] = C;
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  int ans = INF * (R - 1);
  do {
    int res = 0;
    for (int i = 1; i < R; i++) res += d[r[i-1]][r[i]];
    ans = min(ans, res);
  } while (next_permutation(r.begin(), r.end()));
  cout << ans << endl;
}

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

int main() {
  string S;
  cin >> S;
  int cnt_0 = 0, cnt_1 = 0, N = (int)(S.length());
  
  for(int i = 0; i < N; i++) {
    if(S[i] == '0') cnt_0++;
    else cnt_1++;
  }
  
  cout << min(cnt_0, cnt_1) * 2;
  
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;

string sort(string str){
  	map<char, int> count;
	for(int i=0;i<str.length();i++){
    	count[str[i]]++;
    }
  	string ans="";
  	for(auto itr=count.begin();itr!=count.end();itr++){
    	ans += string(itr->second, itr->first);
    }
  	return ans;
}

ll combination(ll num){
	return (num*(num-1LL))/2LL;
}

int main(){
	int n;cin>>n;
  	map<string, int> mp;
  	while(n--){
    	string s;cin>>s;
        mp[sort(s)]++;
    }
  	ll ans=0LL;
  	for(auto itr=mp.begin();itr!=mp.end();itr++){
    	ans += combination(itr->second);
    }
  	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 12416
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#define LL long long
const int N=100005;
using namespace std;
 
LL n,m,a[N],b[N],la=0,ans,lb=0,x;
 
int main(){
	scanf("%lld%lld",&n,&m);
	for(LL i=1;i<=n;i++){
		scanf("%lld",&x);
		if(x<0)a[++la]=0-x;
		else b[++lb]=x;
	}
	sort(a+1,a+la+1);
	ans=1e14;
	if(la>=m)ans=min(ans,a[m]);
	if(lb>=m)ans=min(ans,b[m]);
	//if(b[1]==0)if(la>=m-1)ans=min(ans,a[m-1]);
	for(LL i=1;i<=la;i++){
		if(m-i>lb)continue;
		if(m-i<=0)break;
		ans=min(ans,a[i]*2+b[m-i]);
	}
	for(LL i=1;i<=lb;i++){
		if(m-i>la)continue;
		if(m-i<=0)break;
		ans=min(ans,b[i]*2+a[m-i]);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct stu
{
	int i;
	int m;
};
stu s[100010];
bool compare(stu a,stu b)
{
	return a.m<b.m;
}
int main()
{
	cin>>n;
	for(int j=0;j<n;j++)
	{
		int t;
		cin>>t;
		s[j].i=j;
		s[j].m=t;
	}
	sort(s,s+n,compare);
    for(int j=0;j<n;j++)
    	cout<<s[j].i+1<<" ";
}


Measured memory_bytes: 1536
#include <stdio.h>

typedef struct {
  int left;
  int right;
  int d;
  int p;
} node;

node a[100000];

int x(int y)
{
  
  if(a[y].d != -1){
    return a[y].d;
  }
  
  if(a[y].p == -1){
    a[y].d = 0;
    return 0;
  }
  
  a[y].d = x(a[y].p)+1;
  return a[y].d;
  
}


int main()
{

  int n, id, i, k, j, c1, c2;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    a[i].d = -1;
    a[i].p = -1;
    a[i].right = -1;
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&id,&k);
    if(k==0){
      a[id].left = -1;
    }
    else{
      for(j=0;j<k;j++){
	if(j==0){
	  scanf("%d",&c1);
	  a[id].left = c1;
	  a[c1].p = id;
	}
	else{
	  scanf("%d",&c2);
	  a[c2].p = id;
	  a[c1].right = c2;
	  c1 = c2;
	}
      }
    }
  }

  for(i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,a[i].p,x(i));
    if(a[i].p==-1){
      printf("root, [");
    }
    else if(a[i].left==-1){
      printf("leaf, [");
    }
    else{
      printf("internal node, [");
    }

    c1 = a[i].left;

    if(c1!=-1){
      while(1){
	c2 = a[c1].right;
	if(c2==-1){
	  printf("%d",c1);
	  break;
	}
	else{
	  printf("%d, ",c1);
	  c1 = c2;
	}
      }
    }

    printf("]\n");
  }

  return 0;
  
}
    



Measured memory_bytes: 3416
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;
using P = pair<int, int>;


ull E = 1000000007;

int Rect[101][101];

int main() {
    int W, H, N;
    cin >> W >> H >> N;
    for (int h = 1; h <= H; ++h) {
        for (int w = 1; w <= W; ++w) {
            Rect[h][w] = 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            for (int h = 1; h <= H; ++h) {
                for (int w = 1; w <= x; ++w) {
                    Rect[h][w] = 0;
                }
            }
        } else if (a == 2) {
            for (int h = 1; h <= H; ++h) {
                for (int w = x + 1; w <= W; ++w) {
                    Rect[h][w] = 0;
                }
            }
        } else if (a == 3) {
            for (int w = 1; w <= W; ++w) {
                for (int h = 1; h <= y; ++h) {
                    Rect[h][w] = 0;
                }
            }
        } else if (a == 4) {
            for (int w = 1; w <= W; ++w) {
                for (int h = y + 1; h <= H; ++h) {
                    Rect[h][w] = 0;
                }
            }
        }
    }
    int ans = 0;
    for (int h = 1; h <= H; ++h) {
        for (int w = 1; w <= W; ++w) {
            ans += Rect[h][w];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define init(n) int n;cin>>n;int a[n];rep(i,n)cin>>a[i];
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
const int inf=1e9;
int main() {
   
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T=1;
    // cin>>T;
    while(T--){
    	int n,m;cin>>n>>m;int ans=n*(n-1)/2+m*(m-1)/2;
    	cout<<ans;
    }   
    return 0;   
}   

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 500001

void exchange(int *a,int *b){
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}

void maxHeapify(int A[],int i,int H){
  int l,r,largest;
  l = 2*i;
  r = 2*i+1;
  // 左の子、自分、右の子で値が最大のノードを選ぶ
  if (l <= H && A[l] > A[i]) largest = l;
  else 	largest = i;
  if (r <= H && A[r] > A[largest])
    largest = r;
  if (largest != i){ // i の子の方が値が大きい場合
    exchange(&A[i],&A[largest]);
    maxHeapify(A, largest,H); // 再帰的に呼び出し
  }
}
void buildMaxHeap(int A[],int H){
  int i;
  for (i = H/2;i>=1;i--){
    maxHeapify(A,i,H);
  }
}


int main(){
  int a[MAX],h,i;
  scanf("%d",&h);
  for(i=1;i<=h;i++) scanf("%d",&a[i]);
  buildMaxHeap(a,h);
  for(i=1;i<=h;i++) printf(" %d",a[i]);
  printf("\n");
  return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <random>
#include <chrono>
#include <algorithm>
#include <unordered_map>

int dp[401][401];
int main(void){
	int n;
	int ma, mb;
	std::cin >> n >> ma >> mb;
	std::vector<int> a(n), b(n), c(n);
	for(int i=0;i<n;i++){
		std::cin >> a[i] >> b[i] >> c[i];
	}
	for(int i=0;i<401;i++){
		for(int j=0;j<401;j++){
			dp[i][j] = 1000 * 1000;
		}
	}
	dp[0][0] = 0;
	for(int i=0;i<n;i++){
		for(int j=i * 10;j>= 0; j--){
			for(int k=i * 10;k >= 0;k--){
				dp[j + a[i]][k + b[i]] = std::min(dp[j + a[i]][k + b[i]] , dp[j][k] + c[i]);
			}
		}
	}
	int A = ma, B = mb;
	int ans = 1000 * 1000;
	while(A < 401 && B < 401){
		ans = std::min(dp[A][B], ans);
		A += ma;
		B += mb;
	}
	if(ans == 1000 * 1000)ans = -1;
	std::cout << ans << std::endl;

}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

V<int> getMinimalCycleDirected(const VV<int>& G){
	using P = pair<int,int>;
	int N = G.size();
	V<int> vis(N);	//0:yet 1:now 2:done
	V<int> par(N,-1);
	V<int> d(N);

	P U(-1,-1);	// min distance backward edge

	function<void(int)> dfs = [&](int v){
		vis[v] = 1;
		for(int u: G[v]){
			if(vis[u] == 0){	// dfs edge
				par[u] = v;
				d[u] = d[v]+1;
				dfs(u);
			}else if(vis[u] == 1){	// up
				if(U.fs == -1 || d[U.fs] - d[U.sc] > d[v] - d[u]){
					U = P(v,u);
				}
			}else{}	// left, down
		}
		vis[v] = 2;
	};
	rep(v,N) if(vis[v] == 0){
		dfs(v);
	}
	if(U.fs == -1) return {};
	V<bool> in_cycle(N);
	V<int> c;
	{
		int v = U.fs;
		while(true){
			c.pb(v); in_cycle[v] = true;
			if(v == U.sc) break;
			v = par[v];
		}
	}
	reverse(all(c));
	V<int> nc;
	{
		int v = c[0];
		while(true){
			nc.pb(v);
			if(v == c.back()) break;
			int nxt = v;
			for(int u: G[v]) if(in_cycle[u] && d[u] > d[nxt]) nxt = u;
			v = nxt;
		}
	}
	return nc;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N,M; cin >> N >> M;
	VV<int> G(N);
	rep(i,M){
		int x,y;
		cin >> x >> y;
		x--,y--;
		G[x].pb({y});
	}
	auto c = getMinimalCycleDirected(G);
	if(c.empty()) cout << -1 << endl;
	else{
		cout << c.size() << endl;
		for(int v: c) cout << v+1 << endl;
	}
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define rep(i, a, b) for(int i = a; i < b; ++i)

main() {
    string s;
    cin >> s;
    int n = s.size();
    vector <int> a(n + 1, -1), ind;
    rep(i, 0, n + 1) {
        if ((i == 0 || s[i - 1] == '>') && (i == n || s[i] == '<')) {
            a[i] = 0;
            ind.push_back(i);
        }
    }
    for (auto i : ind) {
        int j = i + 1;
        while (j < n + 1 && s[j - 1] == '<') {
            a[j] = max(a[j], j - i); ++j;
        }
        j = i - 1;
        while (j >= 0 && s[j] == '>') {
            a[j] = max(a[j], i - j); --j;
        }
    }
    int ans = 0;
    rep(i, 0, n + 1) {
        assert(a[i] != -1);
        ans += a[i];
    }
    cout << ans << '\n';
}

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

int main(int argc, const char * argv[]) {
    unsigned long int N;
    cin >> N;
    
    string name = "";
    while (true) {
        N--;
        char c = 'a' + N % 26;
        
        name = c + name;
        N /= 26;
        if (N <= 0) break;
    }
    cout << name << endl;
    
    return 0;
}


Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int>v(n);
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		sum += v[i];
	}
	sort(v.begin(), v.end());
	if (sum % 10 != 0) {
		cout << sum << endl;
		return 0;
	}
	else
	{
		for (int i = 0; i < n; i++) {
			if ((sum - v[i]) % 10 != 0) {
				cout << sum - v[i] << "\n" << endl;
				return 0;
			}
		}
	}
	cout << "0" << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>                   // below comment for pbds
#include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
#include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); // number of 
#define ll long long                      //element strictly smaller than it;
#define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort  use as s.f();
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;                     
using namespace __gnu_pbds;
// assert(a[i]<n ) // if we want to check for special cond , used for debug
// make less_equal in order to make a multiset pbds
const ll Mod = (int)1e9;
ll CaseN=1;
ll fast_power(ll a,ll b,ll mod){
	ll ans=1;
	while(b>0){
	if(b&1){
	ans=(a*ans)%mod;
	}
	b=b>>1;
	a=(a*a)%mod;
	}
	return ans;
	}


ll nCr(ll n ,ll r)
{
ll p= n;
r = min(r,n-r);
ll a =1;
ll b=1;	
while(r)
{
	a = a*p;
	b = b*r;
	
	int g = __gcd(a,b);
	
	a = a/g;
	b = b/g;
	
	p--;
	r--;	
}	
return a;
	
}



void solve()
{
    ld a,b;
    cin>>a>>b;
    ll ans = (ll)(a*b);

  //cout<<"Case #"<<CaseN<<": ";
   CaseN++;
	// print your ans below;
 cout<<ans<<endl;
return ;
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--)
	{
	solve();	
	}
}


Measured memory_bytes: 3748
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<queue>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

// 解法: ソートして二分探索 O(NK log N)
// 戻す dp O(NK)

const int MOD = 1e9+7;
int A[5555];
int N, K;
ll dp[2][5050];

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	sort(A, A+N);
	int n = 0;
	for (; n < N; n++) {
		if (A[n] >= K) break;
	}
	N = n;
	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		int cur = i%2, tar = cur^1;
		memset(dp[tar], 0, sizeof(dp[tar]));
		for (int j = K; j >= 0; j--) {
			(dp[tar][j] += dp[cur][j]) %= MOD;
			if (j+A[i] > K) continue;
			(dp[tar][j+A[i]] += dp[cur][j]) %= MOD;
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int cur = N%2, tar = cur^1;
		memset(dp[tar], 0, sizeof(dp[tar]));
		for (int j = 0; j <= K; j++) {
			dp[tar][j] = dp[cur][j];
		}
		for (int j = 0; j <= K; j++) {
			if (j+A[i] <= K) {
				(dp[tar][j+A[i]] += MOD - dp[tar][j]) %= MOD;
			}
		}
		bool need = false;
		for (int j = K-A[i]; j < K; j++) {
			need |= dp[tar][j] > 0;
		}
		if (!need) ++ans;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define INF 1<<30

struct edge{
  int to,cost;
};
struct road{
  int now,to,cost;
};
typedef pair<int , int> P; //最短,場所
int id[3333];
vector<road> ro;
vector<edge> cost[3333];
priority_queue<P, vector<P> , greater<P> >que;

int n,m,k;
int res=-1;

int main(void){
  int h,t,c,s;
  fill(id,id+3333,INF);
  scanf("%d %d %d",&n,&m,&k);
  for(int i=0;i<m;i++){
    scanf("%d %d %d",&h,&t,&c);
    edge temp={t,c};
    road tamp={h,t,c};
    ro.push_back(tamp);
    cost[h].push_back(temp);
    temp.to=h;
    cost[t].push_back(temp);
  }
  for(int i=0;i<k;i++){
    scanf("%d",&s);
    id[s]=0;
    que.push(P(0,s));
  }

  while(!que.empty()){
    P p=que.top();
    que.pop();
    int v=p.second;
    if(id[v]<p.first)continue;
    for(int i=0;i<cost[v].size();i++){
      edge e=cost[v][i];
      if(id[e.to]>id[v]+e.cost){
	id[e.to]=id[v]+e.cost;
	que.push(P(id[e.to],e.to));
      }
    }
  }
  //  for(int i=1;i<=n;i++)printf("::%d\n",id[i]);
  for(int i=0;i<ro.size();i++){
    road r=ro[i];
    int z=id[r.now]-id[r.to];
    z*=(z<0)?-1:1;
    z+=r.cost;
    z=(int)(((double)z/2)+0.5);
    res=max(res,min(id[r.now]+z,id[r.to]+z));
    /*
      for(int j=0;j<=r.cost;j++){
      int ti=l.;
      res=max(res,min(id[r.now]+j,id[r.to]+r.cost-j));
      }
    */

    /*
      int co=(int)((double)r.cost/2+0.5);
      res=max(res,min(id[r.now],id[r.to])+co);
    */
  }
  printf("%d\n",res);
}

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

public class Main {
	

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		// (n-1) *L -(n-1) + 2+3+4+..+n
		int n=sc.nextInt(), L=sc.nextInt();
		int g0 = (n)*L-(n)+n*(n+1)/2;
		int g1 = (n - 1)*L-(n - 1)+n*(n+1)/2;
		int diff = g0 - g1;
		if(diff >= 0) {
			out.println(g1 - 1);
		} else {
			out.println(g1 + Math.max(-n, diff));
		}
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef unsigned long long ll;
ll B=1e9+7;
ll invB=13499267949257065399ULL;
int S[100000];
ll hs[100001];
map<ll,ll> has;		//has->num
map<ll,ll> D,E;
map<ll,ll> nxt;
map<ll,vector<ll> > prv;
set<ll> doll;	//$..$
void Manacher(string s){
	int i=0,j=0;
	while(i<s.size()){
		while(i-j>=0&&i+j<s.size()&&s[i-j]==s[i+j]) ++j;
		S[i]=j;
		int k=1;
		while(i-k>=0&&i+k<s.size()&&k+S[i-k]<j) S[i+k]=S[i-k],++k;
		i+=k,j-=k;
	}
}
ll ex(ll x,ll p){
	ll a=1;
	while(p){
		if(p%2) a*=x;
		x*=x;
		p/=2;
	}
	return a;
}
ll H(int x,int y){	//[x,y)
	return hs[y]-hs[x]*ex(B,y-x);
}
void dfs(ll h){
	for(ll x:prv[h]){
		dfs(x);
		has[h]+=has[x];
	}
}
void solve(){
	string s,s_;
	cin>>s_;
	int N=s_.size();
	s=s_[0];
	rep1(i,N-1) s+="$",s+=s_[i];
	N=s.size();
	Manacher(s);
	rep(i,N) hs[i+1]=hs[i]*B+s[i];
	rep(i,N){
		int x=S[i];
		ll h=H(i-x+1,i+x);
		bool fst=1;
		while(!has.count(h)){
			if(fst) has[h]++,fst=0;
			has[h];		//access
			if(s[i-x+1]=='$') doll.insert(h);
			x--;
			if(x==0) break;
			ll nh=H(i-x+1,i+x);
			nxt[h]=nh;
			prv[nh].pb(h);
			h=nh;
		}
		if(fst) has[h]++;
	}
	for(auto p:has){
		ll h=p.fs;
		if(!nxt.count(h)) dfs(h);
	}
}
int main(){
	solve();
	D=has;
	rep(i,100000) S[i]=0;
	rep(i,100001) hs[i]=0;
	has.clear();
	nxt.clear();
	prv.clear();
	solve();
	E=has;
	ll ans=0;
/*	for(auto p:E){
		ll h=p.fs;
		show(h);
		show(E[h]);
	}*/
	for(auto p:D){
		ll h=p.fs;
		if(doll.count(h)) continue;
		if(E.count(h)){
			ans+=D[h]*E[h];
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MAX=100005;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,n){cout<<arr[i][j]<<" ";}cout<<endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

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

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    Vec h(n);
    rep(i,n)cin>>h[i];
    ll ans=0;
    ll max = 0;
    rep(i,n){
        chmax(max,h[i]);
        if(max<=h[i])ans++;
    }

    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 764
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print_vector(vector<int> v);
void sort(vector<int> &v);
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v);
}
void print_vector(vector<int> v){
    for(int i=0;i<v.size();i++){
        cout<<v[i];
        if(i!=v.size()-1)cout<<" ";
    }
    cout<<"\n";
}
void sort(vector<int> &v){
    int flag=1;
    int cnt=0;
    while(flag!=0){
        flag=0;
        for(int i=v.size()-1;i>0;i--){
            if(v[i]<v[i-1]){
                int tmp=v[i];
                v[i]=v[i-1];
                v[i-1]=tmp;
                flag=1;
                cnt++;
            }
        }
    }
    print_vector(v);
    cout<<cnt<<"\n";
}


Measured memory_bytes: 3140
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        (x, a, b): (i32, i32, i32)
    }
    if (x-a).abs() < (x-b).abs() {
        println!("A");
    } else {
        println!("B");
    }
}


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

int main(){
	string s;
	cin >> s;
	int f = 0;
	rep(i, s.size()-1){
		if(s.at(i) == 'A' && s.at(i+1) == 'C') f = 1;
	}
	if(f == 1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
A=input()
N=len(A)

for i in range(2**(N-1)):
  s=A[0]
  for j in range(N-1):
    if (i>>j)&1:
      s+="+"
    else:
      s+="-"
    s+=A[j+1]
  if eval(s)==7:
    print(s+"=7")
    break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;  
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define F first
#define S second
 
const int MOD = 1e9 + 7; 
const int N = 1e5; 
const int INF = 1e9 + 5; 

int main(void) 
{

	#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
	#endif

	ll n, k; 
	cin >> n >> k; 
	
	if (n>=k) n%=k; 
	
	ll mini=n; 
	
	while (true) 
	{
		ll tmp = abs(n-k); 
		if (tmp >= mini) break;
		mini = tmp; 
	}

	cout << mini << '\n';

	return false; 
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
ll c=1e18,i,j,x,n,tmp=0,m,a[21][21],g[21],f[21];
bool check()
{
	for (ll i=1;i<=m;++i) if (f[i]<x) return 0;
	return 1;
}
void solve(ll k)
{
	for (ll i=k;i<=n;++i)
	{
		tmp+=g[i];
		for (ll j=1;j<=m;++j) f[j]+=a[i][j];
		if (check()) c=min(c,tmp);
		else solve(i+1);
		tmp-=g[i];
		for (ll j=1;j<=m;++j) f[j]-=a[i][j];
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&x);
	for (i=1;i<=n;++i) 
	{
		scanf("%lld",&g[i]);
		for (j=1;j<=m;++j) scanf("%lld",&a[i][j]);
	}
	solve(1);
	if (c==1e18) printf("-1");
	else printf("%lld",c);
}

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

using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1e9
// #define long long long long long long

typedef long long ll;
ll mod = 1e9 + 7;

long long fast_exp(long long a, long long b)
{
	if(b <= 0)
	   return 1;
	else
	{
	   long long res = 1;
	   res = fast_exp(a,b/2);
	   res = (res*res)%mod;
	   if(b%2 == 1)
		  res = (res*a)%mod;
	   return res;
 
	}
}


typedef long double ld;
const ll N = 1e5+5;
long long num_strictly_less(vector <long long> &v, long long val)
{
	long long n = v.size();
	long long truecount = 0;
	for(long long i = 0; i < n-1 ; i++)
	{
		long long l = i+1, r = n-1;
		long long cnt = 0;
		if(v[i] < 0)
		{	
			while(l < r)
			{
				long long mid = (l+r)/2;
				if(v[mid] * v[i] < val)
					r = mid;
				else
					l = mid + 1;
				
			}
			if(v[l]*v[i] < val)
				cnt += n-l;

		}
		else if(v[i] == 0)
		{
			if(val > 0)
				cnt += r - l + 1;
		}
		else
		{
			while(l < r)
			{
				long long mid = (l+r+1)/2;
				if(v[mid] * v[i] < val)
					l = mid;
				else
					r = mid - 1;
			}
			if(v[l] * v[i] < val)
				cnt += l - i;
		}
		truecount += cnt;

	}
	return truecount;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	vector <long long> v;
	long long x,n,k;
	cin>>n>>k;
	k--;
	for(long long i = 0 ; i<n ; i++)
	{
		cin>>x;
		v.pb(x);
	}
	sort(v.begin(),v.end());
	long long l = -1e18 , r = 1e18;
	while(l < r)
	{
		long long mid = (l+r+1)/2;
		long long lesser = num_strictly_less(v,mid);
		
		if(lesser <= k)
			l = mid;
		else
			r = mid - 1;
	}
	cout<<l<<endl;


return 0;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s; cin >> s;
  int a = 0;
  for (int i = 0; i < (int)s.size(); i++) {
    a = i;
    if (s[i] == 'A') break;
  }
  int n = (int)s.size();
  int z = n - 1;
  for (int i = n - 1; i >= 0; i--) {
    z = i;
    if (s[i] == 'Z') break;
  }
  cout << z - a + 1 << endl;
  return 0;
}


Measured memory_bytes: 720
#pragma GCC diagnostic ignored "-Wunused-result"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = (int)1e6 + 34;
const ll INF = (ll)1e18 + 41;
//const int INF = (int)1e9 + 41;
const ll MD = (ll)1e9 + 7;
bool D = false;

void solve() {
	int n;
	ll sum = 0;
	ll mx = -1;
	cin >> n;
	while (n--) {
		ll x;
		cin >> x;
		sum += x;
		mx = max(mx, x);
	}
	cout << sum - mx / 2 << "\n";
}

int main() {
#ifdef LOCAL
	freopen("a.in", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tst = 1;
	//scanf("%d", &tst);
	//cin >> tst;
#ifdef MADE_BY_SERT
	D = true;	
	tst = 2;
	while (tst--) {
		solve();
	}
#else
	while (tst--) solve();
#endif
}


Measured memory_bytes: 256
n = gets.to_i
arr = gets.split.collect{|item| item.to_i}  #「配列の要素を置き換えるメソッド」a.collect{|item|...} または a.map{|item|...}
                                            # arr = gets.split.map(&:to_i) または　arr = gets.split.collect(&:to_i) も可能
sum = 0

arr.each do |i|
    sum += i
end

print arr.min, " ", arr.max, " ", sum, "\n"


Measured memory_bytes: 7176
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
 
 
#define F first
#define S second
#define ll long long
#define pb push_back
#define db double
#define ld long double
#define ppb pop_back
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define all(x) (x).begin(),(x).end()
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TEST int T; cin >> T; while(T--)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//#define int long long
 
const int N = 1e5 + 1, inf = 2e9 + 7, mod = 1e9 + 7;
const ll INF = 2e18 + 7, MOD = 1e15 + 7;

int n;
int dp[1 << 21];
bool v[21][21], was[1 << 21];

bool has(int mask, int i) {
    return (mask >> i) & 1;
}

int rec(int mask) {
    if (was[mask]) return dp[mask];
    int ans = 0;
    int bits = __builtin_popcount(mask);
    for (int i = 0; i < n; i++) {
        if(!has(mask, i) && v[bits][i])
            ans = (ans * 1LL + rec(mask | (1 << i))) % mod;
    }
    dp[mask] = ans;
    was[mask] = 1;
    return ans;
}

signed main() { __
//    freopen("lcm.in", "r", stdin);
//    freopen("lcm.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }
    dp[(1 << n) - 1] = 1;
    was[(1 << n) - 1] = 1;
    cout << rec(0);
    return 0;
}



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

namespace AtCoderCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int X = int.Parse(input[1]);

            string[] L = Console.ReadLine().Split();
            List<int> LList = new List<int>();
            for (int i = 0; i < N; i++)
                LList.Add(int.Parse(L[i]));

            int sum = 0;
            int count = 1;

            for (int i = 0; i < N; i++)
            {
                sum += LList[i];
                if ( sum <= X)
                {
                    ++count;
                }
            }

            Console.WriteLine(count);
        }
    }
}


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

int main() {
   scanf("%d" , &n);
   int sol = 0, currMin = INT_MAX;
   for (int i = 0 ; i < n ; i++) {
      int x; scanf("%d" , &x);
      if (currMin == INT_MAX) {
         ++sol;
      } else {
         if (currMin >= x) sol++;
      }
      currMin = min(currMin , x);
   }
   printf("%d\n" , sol);
}


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

char g(char a, char b) {
	return (char)((int)'R' + (int)'G' + (int)'B' - (int)a - (int)b);
}

int n, c[128];
string s;
long long fp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	s = " " + s;
	for(int i = 1; i <= n; ++i) {
		for(int j = i + 1; j <= n; ++j) ++c[(int)s[j]];
		for(int j = i + 1; j <= n; ++j) {
			--c[(int)s[j]];
			if(s[i] != s[j]) {
				char cc = g(s[i], s[j]);
				if(j + j - i <= n && s[j + j - i] == cc) {
					--fp;
				}
				fp += c[(int)cc];
			}
		}
	}
	cout << fp << endl;
	return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;


public class Main
{

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		
		int count=0;
		
		for(int i=0;i<S.length();i++)
		{
			if(S.charAt(i)=='1')
			{
				count++;
			}
		}
		
		System.out.println(count);
		sc.close();

	}

}


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

using namespace std;

#define ll long long

int m=1e9+7;

int main()
{
	  #ifndef ONLINE_JUDGE
	  freopen("input.txt", "r", stdin);
	  freopen("output.txt", "w", stdout);

	  #endif
	  ll limit,sum;
	  cin>>limit>>sum;
	  if(sum>3*limit)
	  		cout<<0;
	  else
	  {
	  		ll res=0;
	  		for(int i=0;i<=limit;i++)
	  		{
	  			if(sum-i<=2*limit && sum-i>=0)
	  			{
	  				for(int j=0;j<=limit;j++)
	  				{
	  					if(sum-i-j<=limit && sum-i-j>=0)
	  						res++;
	  				}
	  			}

	  		}
	  		cout<<res;
	  }
}

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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  char x, y;
  cin >> x >> y;
  int X , Y;
  if (x == 'A') X = 10;
  if (x == 'B') X = 11;
  if (x == 'C') X = 12;
  if (x == 'D') X = 13;
  if (x == 'E') X = 14;
  if (x == 'F') X = 15;

  if (y == 'A') Y = 10;
  if (y == 'B') Y = 11;
  if (y == 'C') Y = 12;
  if (y == 'D') Y = 13;
  if (y == 'E') Y = 14;
  if (y == 'F') Y = 15;

  if (X == Y) cout << '=' << "\n";
  else if (X < Y) cout << '<' << "\n";
  else cout << '>' << "\n";

  return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    int S, W;
    cin >> S >> W;

    if (S <= W) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
}

Measured memory_bytes: 3648
#include <iostream>
#include <stdio.h>
#define MAX_NODES 2000000
#define INFTY 2000000010

using namespace std;
//think easy make easy
//think stupid

int n=0;//num of nodes

//iを根とするMaxヒープをつくる関数.初期状態はiを根とする二分木
void maxHeapify(int A[],int i){//i is index of root
	int l,r;
	int largest;
	int tmp;

	l = 2 * i;
	r = l + 1;

	if(l <= n && A[l] > A[i]) largest = l;
	else largest = i;

	if(r <= n && A[r] > A[largest]) largest = r;

	if(largest != i){
		tmp = A[i];
		A[i] = A[largest];
		A[largest] = tmp;
		maxHeapify(A,largest);
	}

	
}

void buildMaxHeap(int A[]){//AをMaxヒープにする関数
	for(int i=n/2;i>0;i--){//1~n/2が左右の子少なくとも一方が存在する範囲
		maxHeapify(A,i);
	}
}

void heapIncreasingKey(int A[]){
	int tmp;
	int tmp_n;
	for(int i=n;i>1;i=i/2){
		if(A[i/2] < A[i]){
			tmp = A[i];
			A[i] = A[i/2];
			A[i/2] = tmp;
		}else break;
	}
}



void insert(int A[],int num){
	n++;
	A[n] = num;
	heapIncreasingKey(A);
}

void extract(int A[]){
	cout <<A[1] <<endl;
	A[1] = A[n];
	n--;
	maxHeapify(A,1);

}

void swap(){

}
int main(){
	//1オリジン(添え字が1からはじまる)のためナル文字分の+1に加えさらに+1する
	int H[MAX_NODES+1+1];
	int num;
	char type[100];

	while(true){
		scanf("%s",&type);

		if(type[0] == 'i'){
			scanf("%d",&num);
			insert(H,num);
		}
		else if(type[1] == 'x'){
			extract(H);
		}else break;
	}

	return 0;
}

Measured memory_bytes: 5648
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;

int N, M, A, B, C, T;

void init(mat &D) {
        D[N-1][N-2]           = A;
        D[0][0] = D[N-1][N-1] = B;
        D[0][1]               = C;
        REP(i,1,N-1) {
            D[i][i-1] = A;
            D[i][i]   = B;
            D[i][i+1] = C;
    }
}

mat mul(mat &A, mat&B) {
    mat C(A.size(), vec(B[0].size()));
    rep(i, A.size()) {
        rep(k, B.size()) {
            rep(j, B[0].size()) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    return C;
}

mat pow(mat A, int n) {
    mat B(A.size(), vec(A.size()));
    rep(i, A.size()) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main(void){
    while (cin >> N >> M >> A >> B >> C >> T, N) {
        mat S(N, vec(1));
        rep(i, N) cin >> S[i][0];
        mat D(N, vec(N,0));
        init(D);
        D = pow(D, T);
        S = mul(D, S);
        rep(i, N) cout << (i ? " ":"") << S[i][0];
        cout << endl;
    }
    return 0;    
}

Measured memory_bytes: 1288
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <math.h>
#include <array>
#include <list>
#include <set>
#define MOD 1000000007
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> p;
typedef vector<int> vi;
set <int> st;
int n;
char s[105];
bool yellow=false;
int main(int argc,char const* argv[])
{
  cin >> n;
  for(int i=0;i<n;i++)
    {
      cin >> s[i];
      if(s[i]=='Y') yellow=true;
    }
  
  if(yellow)
    {
      cout << "Four" << endl;
      return 0;
    }
  else
    {
      cout << "Three" << endl;
      return 0;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n; cin >> n;
  vector<int> v(n+2, 0);
  for(int i = 1; i <= n; i++) cin >> v[i];
  ll sum = 0;
  for(int i = 0; i < n+1; i++){
    sum += abs(v[i]-v[i+1]);
  }
  for(int i = 1; i <= n; i++){
    cout << sum - abs(v[i]-v[i-1])-abs(v[i]-v[i+1])+abs(v[i+1]-v[i-1]) << endl;
  }

  system("pause");
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-7
#define inf 0x3f3f3f3f
#define mod 1000000007ll
using namespace std;

int main() {
	speed;
	int x, a;
	cin >> x >> a;
	return cout << (x < a ? 0 : 10), 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void)
{
	int d;

	scanf("%d", &d);

	if (d == 25){
		printf("Christmas");
	}
	else if (d == 24){
		printf("Christmas Eve");
	}
	else if (d == 23){
		printf("Christmas Eve Eve");
	}
	else if (d == 22){
		printf("Christmas Eve Eve Eve");
	}

	return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
ll h,w;
string s[105][105];
ll dp[105][105];
const ll inf=1e5;
int main(void){
    cin>>h>>w;
    rep(0,i,h){
        string s0;
        cin>>s0;
        rep(0,j,w)s[i][j]=s0.substr(j,1);
    }
    rep(0,i,h)rep(0,j,w)dp[i][j]=inf;
    rep(0,i,h){
        rep(0,j,w){
        if(i==0&&j==0){
            if(s[i][j]=="#")dp[i][j]=1;
            else dp[i][j]=0;
        }
        bool T=true;
        if(s[i][j]=="#")T=false;
        if(i<h-1){
            if(s[i+1][j]=="#"&&T)dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);
            else dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            //cout<<dp[i+1][j]<<endl;
        }
        if(j<w-1){
            if(s[i][j+1]=="#"&&T)dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
            else dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
        }
        }
    }
    cout<<dp[h-1][w-1];
}

Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <math.h>
#include <deque>
#include <queue>
#include <map>
#include <iterator>
#include <set>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }
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; }

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

	int n; string s;
	cin >> n >> s;
	int ans = 0;
	for (int i = 0; i < 1000; i++) {
		int c[3] = { i / 100, (i / 10) % 10, i % 10 };
		int f = 0;
		for (int j = 0; j < n; j++) {
			if (s[j] == (char)('0' + c[f])) f++;
			if (f == 3) break;
		}
		if (f == 3) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>

typedef  long long ll;
#define mop 1000000007
#define mop2 998244353

using namespace std;

ll fastPow(ll a, ll b, ll mod = 0) {
	if (a == 0 and b == 0) {
		return -1;
	}
	if (a == 0) {
		return 0;
	}
	if (b == 0) {
		return 1;
	}
	long long tmp = fastPow(a, b / 2, mod);
	if (mod != 0) {
		if (b % 2 == 0) {
			return (tmp * tmp) % mod;
		}
		else {
			return ((tmp*tmp) % mod * (a % mod)) % mod;
		}
	}
	else {
		if (b % 2 == 0) {
			return (tmp*tmp);
		}
		else {
			return tmp * tmp * a;
		}
	}
}

int main() {
	ll cost = INT64_MAX;
	ll n, m, x;
	cin >> n >> m >> x;
	vector<vector<ll>> a;
	a.resize(n);
	vector <ll> c;
	c.resize(n);
	for (ll i = 0; i < n; i++) {
		a[i].resize(m);
		cin >> c[i];
		for (ll j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	for (ll i = 0; i < fastPow(2,n); i++) {
		ll tmp = i;
		ll tmp_ans = 0;
		vector <ll> tmp_a;
		tmp_a.resize(m,0);
		for (ll j = 0; j < n; j++) {
			if (tmp % 2 == 1) {
				for (ll k = 0; k < m; k++) {
					tmp_a[k] += a[j][k];
				}
				tmp_ans += c[j];
			}
			tmp /= 2;
		}
		if (tmp_ans < cost) {
			bool flag = true;
			for (ll j = 0; j < m; j++) {
				if (tmp_a[j] < x) {
					flag = false;
				}
			}
			if (flag) {
				cost = tmp_ans;
			}
		}
		
	}
	if (cost == INT64_MAX) {
		cout << -1 << endl;
	}
	else {
		cout << cost << endl;
	}
} 

Measured memory_bytes: 3640
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;

int k;

void func(ll cur,vll &a){
    if(to_string(cur).size()>10)return;
    a.push_back(cur);
    if(cur%10>0)func(10*cur+cur%10-1,a);
    func(10*cur+cur%10,a);
    if(cur%10<9)func(10*cur+cur%10+1,a);
}

int main(){
    cin>>k;
    vll a;
    rep2(i,1,10)func(i,a);
    sort(all(a));
    cout<<a[k-1]<<endl;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define endl '\n'
#define mod 998244353
#define inf -1000000000000000000
const int sz = 200006;
ll n,k;
vector<ll>h, dp;
ll solve(ll n) {
	if(n == 0) return 0;
	if(dp[n] != -1) return dp[n];
	return dp[n] = min(solve(n-1) + abs(h[n]-h[n-1]), solve(n-2)+abs(h[n] - h[n-2]));
}
int main() {
	io
	cin>>n;
	h.resize(n);
	dp.resize(n, -1);
	for(int i = 0; i<n; i++) {
		cin>>h[i];
	}
	dp[0] = 0;
	cout<<solve(n-1);
}




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

int main( )
{
    int x, a, b;
    cin >> x >> a >> b;
    if (b - a <= 0) {
        cout << "delicious\n";
    }
    else if (b - a <= x) {
        cout << "safe\n";
    }
    else {
        cout << "dangerous\n";
    }
    return 0;
}


Measured memory_bytes: 256