akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define endl '\n';
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("Yes"):fin("No");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main() {
    int n,l;
    cin>>n>>l;
    vs v(n);
    rep(i,n)cin>>v[i];
    Sort(v);
    rep(i,n)cout<<v[i];
    cout<<endl;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; print(tail...); }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n; string s;
	read(n, s);

	s = " " + s;
	vector<int> ce(n + 1), cw(n + 1);

	rep(i, 1, n + 1) {
		ce[i] = ce[i - 1] + (s[i] == 'E');
		cw[i] = cw[i - 1] + (s[i] == 'W');
	}

	int ans = 0x3f3f3f3f;
	rep(i, 1, n + 1) {
		int v = cw[i - 1] - cw[0] + ce[n] - ce[i];
		chmin(ans, v);
	}
	write(ans);
}


Measured memory_bytes: 3056
def dfs(li, cnt, digits):
    if len(li) == digits:
        n = int("".join(li))
        if n <= N and all(i in li for i in ("3", "5", "7")):
            cnt += 1
        return cnt
    for i in ("3", "5", "7"):
        cnt = dfs(li + [i], cnt, digits)
    return cnt


N = int(input())
ans = sum(dfs([], 0, i) for i in range(1, len(str(N)) + 1))
print(ans)


Measured memory_bytes: 9164
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
//#include<algorithm>
//#include<cmath>
using namespace std;
int main() {
	char bff[10];
	int a, b,c;
	while (cin >> a >> b)
		c = sprintf(bff, "%d", a + b),
		cout << c << endl;
	return 0;
}

Measured memory_bytes: 3136
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>

using namespace std;

int main()
{
	long N, A, B;
	cin >> N >> A >> B;
	
	long dist = B - A;
	
	if(dist % 2 == 0) cout << dist / 2 << endl;
	else{
		cout << min(A - 1, N - B) + 1 +  (dist - 1) / 2 << endl;  
		
	}
	
	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  ll a;
  cin>>a;
  vector<vector<double>>vec(a,vector<double>(2));
  ll b;
  cin>>b;
  ll e;
  cin>>e;
  for(ll i=0;i<a;i++){
    double c;
    cin>>c;
    vec.at(i).at(0)=b-c*0.006;
    vec.at(i).at(1)=i;
  }
  sort(vec.begin(),vec.end());
  ll f=a-1;
  for(ll i=0;i<a;i++){
    if(e<=vec.at(i).at(0)){
      f=i;
      break;
    }
  }
  if(f==0){
    cout<<vec.at(f).at(1)<<endl;
    return 0;
  }
  if(abs(vec.at(f).at(0)-e)>abs(vec.at(f-1).at(0)-e)){
    cout<<vec.at(f-1).at(1)+1<<endl;
  }
  else{
    cout<<vec.at(f).at(1)+1<<endl;
  }
  
    
  return 0;
}
    
    
  


Measured memory_bytes: 3752
#include<stdio.h>
#include<math.h>

int main() {

	int n;
	double r,h;
	double x_l,x_r;
	int i,j;
	double b[41];
	double t;
	double x,y;

	for(;;) {
		scanf("%lf %d",&r,&n);
		if(r==0&&n==0)
			break;

		for(i=0;i<41;i++)
			b[i]=0;

		//??????????????????????´?
		for(i=0;i<n;i++) {
			scanf("%lf %lf %lf",&x_l,&x_r,&h);
			for(j=x_l+20;j<x_r+20;j++) {
				if(b[j]<h)
					b[j]=h;
			}
		}

		//????????????????????????????????§???????????´????????????????????????????¨????
		t=100;
		for(j=(-r+20)+1;j<=(r+20)-1;j++) {
			x = j-20;
			if(b[j-1]<=b[j])
				y=b[j-1];
			else
				y=b[j];

			if(t>y+r-sqrt(r*r-x*x))
				t=y+r-sqrt(r*r-x*x);

		}
		printf("%f\n",t);
	}
	return 0;
}

Measured memory_bytes: 1812
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>
#include <string>

constexpr int64_t kMaxNumberOfTowns = 200000;
constexpr int64_t kMaxLog = 60;  // > log2(K)

void CallTeleporter(std::istream &input_stream) noexcept;

class Doubling {
 public:
  Doubling() noexcept;
  ~Doubling() noexcept;
  void SetNumberOfTowns(const int64_t number_of_towns) noexcept;
  void SetMapping(const int64_t from, const int64_t to) noexcept;
  void CreateTable() noexcept;
  int64_t SearchFinalTown(const int64_t start_town, const int64_t number_of_teleportations) noexcept;

 private:
  int64_t number_of_towns_;
  int64_t ported_to_[kMaxLog][kMaxNumberOfTowns];
};

void CallTeleporter(std::istream &input_stream) noexcept {
  input_stream.tie(0);
  std::ios::sync_with_stdio(false);
  Doubling *teleporter = new Doubling();

  int64_t number_of_towns, number_of_teleportations;
  input_stream >> number_of_towns >> number_of_teleportations;

  teleporter->SetNumberOfTowns(number_of_towns);
  for (int64_t from = 0L; from < number_of_towns; ++from) {
    int64_t to_plus_1;
    input_stream >> to_plus_1;
    teleporter->SetMapping(from, to_plus_1 - 1);
  }
  teleporter->CreateTable();

  constexpr int64_t kInitialTown = 1L - 1L;
  const int64_t final_town = teleporter->SearchFinalTown(kInitialTown, number_of_teleportations);
  std::cout << final_town + 1 << std::endl;

  delete teleporter;
}

Doubling::Doubling() noexcept : number_of_towns_(0) {}

Doubling::~Doubling() noexcept {}

void Doubling::SetNumberOfTowns(const int64_t number_of_towns) noexcept {
  number_of_towns_ = number_of_towns;
}
void Doubling::SetMapping(const int64_t from, const int64_t to) noexcept {
  ported_to_[0][from] = to;
}

void Doubling::CreateTable() noexcept {
  for (int64_t pow = 1LL; pow < kMaxLog; ++pow) {
    for (int64_t from = 0LL; from < kMaxNumberOfTowns; ++from) {
      const int64_t via = ported_to_[pow - 1LL][from];
      const int64_t to = ported_to_[pow - 1LL][via];
      ported_to_[pow][from] = to;
    }
  }
}

int64_t Doubling::SearchFinalTown(const int64_t start_town, const int64_t number_of_teleportations) noexcept {
  int64_t remaining_teleportations = number_of_teleportations;
  int64_t ctown = start_town;
  for (int64_t pow = kMaxLog - 1LL; pow >= 0LL; --pow) {
    int64_t powered = 1LL << pow;
    if (powered <= remaining_teleportations) {
      ctown = ported_to_[pow][ctown];
      remaining_teleportations -= powered;
    }
  }
  return ctown;
}

int main() {
  try {
    CallTeleporter(std::cin);
  } catch (...) {
    std::cerr << "ERROR: main()" << std::endl;
  }
  return 0;
}


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

int main() {
	int n, dig, num = 0;
	cin >> n;
	dig = log10(n);

	vector<int> semi(3); semi[0] = 3; semi[1] = 5; semi[2] = 7;
	for (int i = 0; i < dig; i++) {
		int n_p = semi.size();
		for (int j = 3 * (pow(3, i) - 1) / 2; j < n_p; j++) {
			semi.push_back(semi[j] * 10 + 3);
			semi.push_back(semi[j] * 10 + 5);
			semi.push_back(semi[j] * 10 + 7);
		}
	}
	for (int x : semi) {
		int temp = x, f = 0;
		while (temp != 0) {
			if (temp % 10 == 3)
				f |= 1;
			else if (temp % 10 == 5)
				f |= 2;
			else if (temp % 10 == 7)
				f |= 4;
			temp /= 10;
		}
		if (f == 7 && x <= n)
			num++;
	}
	cout << num << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
typedef pair<int, int> Pii;
typedef pair<int, Pii> Pip;
typedef vector<int> Vi;
const int INF = (1<<25);
const int MAX_V = 101;
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

struct edge {
  int to, cost;
  edge(int _to, int _cost) {
    to = _to; cost = _cost;
  }
};

int V;
vector<edge> G[MAX_V];

int dij(int s, int c, int g) {
  priority_queue<Pip, vector<Pip>, greater<Pip> > q;

  int d[11][101];
  for(int i=0; i<11; i++) {
    for(int j=0; j<101; j++) {
      d[i][j] = INF;
    }
  }

  d[c][s] = 0;
  q.push(Pip(0, Pii(s, c)));

  int result = INF;
  while( !q.empty() ) {
    Pip p = q.top(); q.pop();
    int now_cost = p.fr;
    int v = p.sc.fr;
    int c = p.sc.sc;

    if( v == g ) {
      result = now_cost;
      break;
    }

    for(int i=0; i<G[v].size(); i++) {
      edge e = G[v][i];

      int next_cost = d[c][v] + e.cost;
      if( next_cost < d[c][e.to] ) {
	d[c][e.to] = next_cost;
	q.push(Pip(next_cost, Pii(e.to, c)));
      }
      if( c ) {
	next_cost = d[c][v] + e.cost/2;
	if( next_cost < d[c-1][e.to] ) {
	  d[c-1][e.to] = next_cost;
	  q.push(Pip(next_cost, Pii(e.to, c-1)));
	}
      }
    }
  }
  return result;
}

int main() {
  int c, n, m, s, g;
  while( cin >> c >> n >> m >> s >> g, c || n || m || s || g ) {
    for(int i=0; i<n+1; i++) {
      G[i].clear();
    }
      
    s--; g--;
    for(int i=0; i<m; i++) {
      int u, v, cost;
      cin >> u >> v >> cost;
      u--; v--;
      G[u].pb(edge(v, cost));
      G[v].pb(edge(u, cost));
    }
    int ans = dij(s, c, g);
    cout << ans << endl;
  }
}

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

int main() {
  int n, k;
  cin >> n >> k;
  
  vector<int> v;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  
  int mn = 1e9;
  for (int i = 0; i < v.size(); ++i) {
    int j = i + k - 1;
    if (j >= v.size()) continue;
    mn = min(mn, v[j] - v[i]);
  }
  cout << mn << endl;
}


Measured memory_bytes: 892
N, A, B = map(int, input().split())

X = list(map(int, input().split()))

fatigue = 0
for i in range(1, N):
    if (X[i]-X[i-1])*A < B:
        fatigue += (X[i]-X[i-1])*A
    else:
        fatigue += B

print(fatigue)

Measured memory_bytes: 14252
#include <iostream>
using namespace std;
int main() {   
    int a[4][3][10];
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 10; ++k) {
                a[i][j][k] = 0;
            }
        }
    }
    
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int b, f, r, v;
        cin >> b >> f >> r >> v;       
        a[b - 1][f - 1][r - 1] += v;
    }
    
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 10; ++k) {
                cout << " " << a[i][j][k];
            }
            cout << endl;
        }
        if (i != 3) {
            cout << "####################" << endl;
        }
    }
    
    return 0;
}



Measured memory_bytes: 3080
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) ((ll)v.size())
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define pii pair<ll,ll> 
const ll mod = 1000000007;
const ll mod1= 1000000009;
const ll base= 2323233;
const ll base1=3424424;
#define MAXN 2000004
#define trace1(x)                cerr << #x << ": " << x << "\n";
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << "\n";
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << "\n";
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << "\n";
ll a[3000002];
bool cmp(const pair<pii,ll> &x,const pair<pii,ll> &y){
  if(x.F.F==y.F.F) return x.F.S>y.F.S;
  return x.F.F<y.F.F;
}
ll L[100002][2], R[100002][2];
int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ll n,m,i;
   cin>>n;
   for(i=1;i<=n;i++) cin>>a[i];
   stack<ll> s;
   priority_queue<pii,vector<pii>,greater<pii>> pq;
   for(i=1;i<=n;i++){
    while(!pq.empty() and pq.top().F<a[i]){
      R[pq.top().S][1]=i;
      pq.pop();
    }
    while(!s.empty() and a[s.top()]<a[i]) {
      R[s.top()][0]=i;
      pq.push({a[s.top()],s.top()});
      s.pop();
    }
    s.push(i);
   }

   while(!s.empty()) R[s.top()][0]=R[s.top()][1]=n+1, s.pop();
   while(!pq.empty()) R[pq.top().S][1]=n+1, pq.pop();

   for(i=n;i>=1;i--){
    while(!pq.empty() and pq.top().F<a[i]){
      L[pq.top().S][1]=i;
      pq.pop();
    }
    while(!s.empty() and a[s.top()]<a[i]) {
      L[s.top()][0]=i;
      pq.push({a[s.top()],s.top()});
      s.pop();
    }
    s.push(i);
   }

   while(!s.empty()) L[s.top()][0]=L[s.top()][1] = 0 , s.pop();
   while(!pq.empty()) L[pq.top().S][1]=0, pq.pop();

   ll ans=0;
   for(i=1;i<=n;i++){
    //trace4(L[i][0],L[i][1],R[i][0],R[i][1]);
    if(L[i][0]) ans+=a[i]*(L[i][0]-L[i][1])*(R[i][0]-i);
    if(R[i][0]) ans+=a[i]*(R[i][1]-R[i][0])*(i-L[i][0]);
   }
   cout<<ans;
 }


Measured memory_bytes: 5016
#include<bits/stdc++.h>
using namespace std;
int f(string s){
    int ret = 0;
    for(int i = 0; i < s.length(); i++)ret = ret * 10 + s[i] - '0';
    return ret;
}
int main(){
    int ans = 100000;
    string s,t;
    cin >> s;
    for(int i = 0; i < s.length() - 2; i++){
        t = "";
        for(int j = i; j < i + 3; j++)t += s[j];
        ans = min(ans,abs(753 - f(t)));
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
As = list(map(int, input().split()))

over_count = 0
gray = 0
brawn = 0
green = 0
lightblue = 0
blue = 0
yellow = 0
orange = 0
red = 0

for a in As:
  if 1 <= a <= 399:
    gray = 1
  elif 400 <= a <= 799:
    brawn = 1
  elif 800 <= a <= 1199:
    green = 1
  elif 1200 <= a <= 1599:
    lightblue = 1
  elif 1600 <= a <= 1999:
    blue = 1
  elif 2000 <= a <= 2399:
    yellow = 1
  elif 2400 <= a <= 2799:
    orange = 1
  elif 2800 <= a <= 3199:
    red = 1
  elif 3200 <= a <= 4800:
    over_count += 1
    
min_count = gray + brawn + green + lightblue + blue + yellow + orange + red
max_count = min_count + over_count

if min_count == 0 and over_count >= 1:
  min_count = 1

print("{} {}".format(min_count, max_count))



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

int main() {
  int N,K,x;
  cin >> N >> K;
  int sum = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> x;
    if (x > K/2) {
      if (x > K) 
        sum += 2*(x-K);
      else 
        sum += 2*(K-x);
    }
    else 
      sum += 2*x;
  }
  cout << sum << endl;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define arep(i, x, n) for (int i = int(x); i < (int)(n); i++)
#define rep(i, n) for (long long i = 0; i < n; ++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9 + 7
using ll = long long;

int main() {
    ll n;
    cin >> n;
    vector<float> vect(n);
    rep(i, n) { cin >> vect[i]; }

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

    float sum;
    sum = (vect[0] + vect[1]) / 2;
    if (n > 2) {
        for (ll i = 2; i < n; i++) {
            sum = (sum + vect[i]) / 2;
        }
    }

    cout << sum << endl;
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,t,a,b,ans=1e18;
    cin>>n>>t;
    int i;
    for(i=0;i<n;i++)
    {
        cin>>a>>b;
        if(b<=t)
        {
            ans=min(ans,a);
        }
    }
    if(ans==1e18)
    {
        cout<<"TLE\n";
        return 0;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#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 = 1e12;


const int MAX_N = 1e5 + 10;
int prime[MAX_N];
bool is_prime[MAX_N + 1];
void sieve(int n){
   int p = 0;
   for(int i = 0; i <= n; i++) is_prime[i] = true;
   is_prime[0] = is_prime[1] = false;
   for(int i = 2; i <= n; i++){
   if(is_prime[i]){
           prime[p++] = i;
           for(int j = 2*i; j <= n; j += i) is_prime[j] = false;
       }
   }
}
int a[MAX_N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve(MAX_N);
    rep(i, 0, MAX_N){
        if(is_prime[i] && is_prime[(i + 1) / 2]) a[i] = 1;
    }
    rep(i, 1, MAX_N) a[i] += a[i - 1];
    int n;
    cin >> n;
    rep(i, 0, n){
        int l, r;
        cin >> l >> r;
        cout << a[r] - a[l - 1] << endl;
    }
}

Measured memory_bytes: 1664
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class question {
public:
	int N;
	vector<ll> A, B;

	ll f(int n) {
		static vector<ll> memo(N + 1);
		if (!memo[n]) {
			if ((A[n] + memo[n + 1]) % B[n] == 0) memo[n] = memo[n + 1];
			else memo[n] = B[n] - (A[n] + memo[n + 1]) % B[n] + memo[n + 1];
		}
		if (n > 0) return f(n - 1);
		return memo[0];
	}
	
	void ans() {
		cin >> N;
		A.resize(N);
		B.resize(N);
		REP(i, N) cin >> A[i] >> B[i];
		cout << f(N - 1) << "\n";
	}
};

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

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1001,INF=1<<30;
int dis[MAX][MAX],cnt=0,H,W;
queue<pair<int,int>> Q;
vector<int> dx={-1,0,1,0},dy={0,-1,0,1};

void BFS(){
    while(cnt<H*W){
        int a=Q.front().first,b=Q.front().second;
        Q.pop();
        for(int i=0;i<4;i++){
            if(0<=a+dx[i]&&a+dx[i]<=H-1&&0<=b+dy[i]&&b+dy[i]<=W-1){
                if(dis[a+dx[i]][b+dy[i]]==INF){
                    dis[a+dx[i]][b+dy[i]]=dis[a][b]+1;
                    Q.push(make_pair(a+dx[i],b+dy[i]));
                    cnt++;
                }
            }
        }
    }
}

int main(){
    
    cin>>H>>W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            dis[i][j]=INF;
        }
    }
    
    for(int i=0;i<H;i++){
        string a;cin>>a;
        for(int j=0;j<W;j++){
            if(a[j]=='#'){
                cnt++;
                dis[i][j]=0;
                Q.push(make_pair(i,j));
            }
        }
    }
    
    BFS();
    
    int ans=0;
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            ans=max(ans,dis[i][j]);
        }
    }
    
    cout<<ans<<endl;
    
    
    
}




Measured memory_bytes: 12304
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;

// Mod int
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
//

int main() {
  string s;
  cin>>s;
  int m = 13;
  vector<mint> dp(m);
  dp[0] = 1;
  for (char c : s) {
    vector<mint> p(m);
    swap(dp,p);
    rep(i,10) {
      if (c == '0'+i || c == '?') {
        rep(j,m) {
          dp[(j*10+i)%m] += p[j];
        }
      }
    }
  }
  cout<<dp[5]<<endl;
  return 0;
}



Measured memory_bytes: 3704
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    public struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        int[] P = Enumerable.Range(0, N).Select(v => NextInt()).ToArray();
        int[] Q = Enumerable.Repeat(0, N + 1).ToArray();
        for (int i = 0; i < N; i++)
            Q[P[i]] = Q[P[i] - 1] + 1;
        //最長部分連続列の数
        Console.WriteLine(N - Q.Max());
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 20544
#include <cstdio>


int N, map[10][10], dx[3] = {0, 1, 0}, dy[3] = {1, 1, 2};
int x[12], y[12], bl[12];


int abs(int n){
    if(n < 0) n = -n;
    return n;
}

bool check(int x, int y, int t){
    int u = 1;
    if(t > 0) u = 2;
    for(int i = -u; i <= u; i++){
        for(int j = -u; j <= u; j++){
            if(abs(i) + abs(j) > u) continue;
            if(t == 1 && (i == 0 && abs(j) == 2 || j == 0 && abs(i) == 2)) continue;
            if(x + j >= 10 || y + i >= 10 || x + j < 0 || y + i < 0) return false;
            if(!map[y + i][x + j]) return false;
        }
    }
    return true;
}

void ss(int x, int y, int t, int v){
    //v???-????????????????????????+?????????????????????
    int u = 1;
    if(t > 0) u = 2;
    for(int i = -u; i <= u; i++){
        for(int j = -u; j <= u; j++){
            if(abs(i) + abs(j) > u) continue;
            if(t == 1 && (i == 0 && abs(j) == 2 || j == 0 && abs(i) == 2)) continue;
            if(x + j >= 10 || y + i >= 10 || x + j < 0 || y + i < 0) continue;
            map[y + i][x + j] += v;
        }
    }
}

bool solve(int n){
    if(n == N){
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(map[i][j]) return false;
            }
        }

        for(int i = 0; i < N; i++){
            printf("%d %d %d\n", x[i], y[i], bl[i]);
        }
        return true;
    }

    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            if(!map[i][j]) continue;

            for(int k = 0; k < 3; k++){
                if(!check(j + dx[k], i + dy[k], k)) continue;
                ss(j + dx[k], i + dy[k], k, -1); //???????????????

                x[n] = j + dx[k]; y[n] = i + dy[k]; bl[n] = k + 1;
                if(solve(n + 1)) return true;
                ss(j + dx[k], i + dy[k], k, 1); //???????????????
            }
            return false;
        }
    }

    return false;
}

int main(){
    scanf("%d", &N);
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            scanf("%d", &map[i][j]);
        }
    }

    solve(0);


    return 0;
}

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

using namespace std;

int main() {
  long long x, ans;
  cin >> x;
  ans = (x / 11) * 2;
  x %= 11;
  if (x) {
    ans++;
    x -= 6;
    if (x > 0) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
	const int nmax = 5001;
	int n;
	int nums[nmax];
	while(cin >> n){
		if(n == 0) break;
		int a;
		for(int i = 1;i <= n; i++){
			cin >> a;
			nums[i] = a;
		}
		int total_max = -2147483648;
		for(int i = 1; i <= n; i++){
			int total = 0;
			for(int j = i; j <= n; j++){
				total += nums[j];
				total_max = max(total_max, total);
			}
		}
		cout << total_max << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N,a,b,c,d; cin>>N>>a>>b>>c>>d;
	--a; --b; --c; --d;
	string s; cin>>s;
	bool free_space = false;
	bool can = true;
	for(int i = min(a,b); i<max(c,d); ++i){
		if(s[i] == '#' && s[i+1] == '#')can = false;
		if(i>d || i<b)continue;
		if(s[i-1] == '.' && s[i] == '.' && s[i+1] == '.')free_space = true;
	}
	bool ans = false;
	if(c<d){
		if(can){ans = true;}
	}else{
		if(free_space && can){ans = true;}
	}
	cout<<((ans)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 640
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	private Set<Long> divisors(long x) {
		Set<Long> result = new HashSet<>();

		for (int i = 1; i <= Math.sqrt(x) + 1; i++) {
			if (x % i == 0) {
				result.add((long) i);
				result.add(x / i);
			}
		}

		return result;
	}

	// 最大公約数
	private static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	private boolean isPrime(long x) {
		if (x < 2)
			return false;
		else if (x == 2)
			return true;
		else if (x % 2 == 0)
			return false;
		for (int i = 3; i <= Math.sqrt(x); i += 2) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}

	private List<Long> prime(List<Long> x) {
		List<Long> result = new ArrayList<>();
		result.add((long) 1);
		for (long n : x) {
			if (isPrime(n)) {
				result.add(n);
			}
		}
		return result;
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		long A = sc.nextLong();
		long B = sc.nextLong();

		sc.close();

		Set<Long> cd = divisors(A);
		cd.retainAll(divisors(B));

		List<Long> arr = new ArrayList<>(cd);

		arr = prime(arr);

		out.println(arr.size());

	}

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


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

using namespace std;
using ll = long long;

int main() {
	ll n, a, b; scanf("%lld %lld %lld", &n, &a, &b);
	ll ans = (n / (a + b)) * a;
	ans += min(a, n % (a + b));
	printf("%lld\n", ans);
	return 0;
}


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

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

ll nums[100];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	nums[0] = 2;
	nums[1] = 1;
	for(int i = 2; i <= 86; i++) {
		nums[i] = nums[i-1]+nums[i-2];
	}
	cout << nums[n];
	//cout << (good ? "YES" : "NO");
	return 0;
}



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

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

  int count = 0;

  for(int i = 1;i <= N;i++){
    if(i != P[i-1])count++;
  }

  if(count == 2 || count == 0)cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
bool t[100005];

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    char ch;
    cin>>ch;
    t[i]=(ch=='T');
  }
  bool res=t[0];
  for(int i=1;i<n;i++){
    res= ( !res || t[i] );
  }
  if( res )cout<<'T'<<endl;
  else cout<<'F'<<endl;
  return 0;
}



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

using namespace std;

double distance(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<double> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }
  double res = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      res += distance(X[i], Y[i], X[j], Y[j]);
    }
  }
  cout << setprecision(10) << res / N << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=(1e6)+10;
int n,k,tot;
bool vis[maxn];
int b[maxn],t2;
int a[maxn],t1;
int fa[maxn];
struct node { int x,y,z; } d[maxn];
void WA() { printf("-1\n"); exit(0); }
void insert(int x) {
	if (vis[x]) WA();
	vis[x]=1;
}
int find(int x) {
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void add(int x) {
	vis[x]=1;
	if (find(x)==x) fa[x]=find(x-1);
	if (find(x+1)==x) fa[x+1]=find(x-1);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(k);
	if (n+1<2*k) WA();
	int i,j1,j2;
	for (int i=k;i<=k+3*n-1;i++) fa[i]=i;
	for (i=k+2*n,j1=k,j2=2*n;i<=k+3*n-1&&j1<j2&&j2<k+2*n;i+=2,j1++,j2++) {
		//printf("%d %d %d\n",j1,j2,i);
		add(j1),add(j2),add(i);
		d[++tot]=(node){j1,j2,i};
	}
	//printf("\n");
	for (i=k+2*n+1;i<=k+3*n-1;i+=2,j1++) {
		if (vis[j1]) continue;
		//printf("%d\n",i);
		j2=min(k+2*n-1,i-j1);
		j2=find(j2);
		//while (vis[j2]) j2--;
		add(j1); add(j2); add(i);
		d[++tot]=(node){j1,j2,i};
		//printf("%d %d %d\n",j1,j2,i);
	}
	t1=t2=0;
	for (int i=k;i<=k+2*n-1;i++)
		if (!vis[i]) a[++t1]=i;
	for (int i=k+2*n;i<=k+3*n-1;i++)
		if (!vis[i]) b[++t2]=i;
	for (i=1,j1=1,j2=t1;i<=t2;i++,j1++,j2--) {
		d[++tot]=(node){a[j1],a[j2],b[i]};
		add(a[j1]);
		add(a[j2]);
		add(b[i]);
	}
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=tot;i++) {
		if (d[i].x+d[i].y>d[i].z) WA();
		insert(d[i].x);
		insert(d[i].y);
		insert(d[i].z);
	}
	if (tot!=n) WA();
	for (int i=1;i<=tot;i++) printf("%d %d %d\n",d[i].x,d[i].y,d[i].z);
	return 0;
}
/*
  REMEMBER:
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Array size? Integer overflow? Time complexity? Memory usage? Precision error?
*/

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

int main()
{
       int a,b,k,n;
       cin>>a>>b>>k;
       n=b-a+1;
       if(n>k*2){
        for(int i=0;i<k;i++){
            cout<<a<<endl;
            a++;
        }

        for(int j=b-k+1;j<=b;j++){
        if(a-1!=j)
            cout<<j<<endl;
        }
       }
       else {
       for(int i=a;i<=b;i++)
        cout<<i<<endl;
       }
        return 0;
}

Measured memory_bytes: 3560
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int N;
vector<ll> A;
vector<ll> B;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < N; i++){
        ll a, b;
        cin >> a >> b;
        if(N % 2 == 0) a *= 2, b *= 2;
        A.push_back(a);
        B.push_back(b);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int h = (N - 1) / 2;
    if(N % 2){
        cout << B[h] - A[h] + 1 << endl;
    }else{
        cout << (B[h] + B[h + 1]) / 2 - (A[h] + A[h + 1]) / 2 + 1 << endl; 
    }
    return 0;
}

Measured memory_bytes: 6688
/***
بسم الله الرحمن الرحيم
اللهم ما صلّ على سيدنا محمد
اذكر الله
واتقوا يوما ترجعون فيه إلى الله ثم توفى كل نفس ما كسبت وهم لا يظلمون
****/

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define shalaby ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);cerr.tie(0);

using namespace std;

inline int D()
{
    int t;
    scanf("%d",&t);
    return t;
}
inline ll llD()
{
    ll t;
    scanf("%lld",&t);
    return t;
}

const ll OO=-1e18;
int xt[4]= {1,0,0,-1};
int yt[4]= {0,1,-1,0};
////////////////////////////////////////////////////////////////////////////////////
const int N = 1e6+1;
int mem[200005],n,m,mod=1e9+7,cnt;
bool valid(int x,int y)
{
    return x>-1 && y>-1 && x<n && y<m;
}
void init()
{
    memset(mem,-1,sizeof mem);
}
bool visited[200005];
vector <int> adj[200005];
int dfs(int s)
{
   /// cout<<" S " <<s <<endl;
    int &ret=mem[s];
    if(~ret)return ret;
       ret=0;
      /// visited[s] = true;

    for(int i = 0; i < adj[s].size(); ++i)
    {
        if(visited[adj[s][i]] == false)
        {
            ret= max(ret, dfs(adj[s][i])+1);
        }
    }
    return ret;
}
int main()
{
    init();
    int x,y;
    cin >> n;
    cin >> m;
    for(int i = 0; i < m; ++i)
    {
        cin >> x >> y;
        adj[x].push_back(y);
    }
    int mx=0,mn=2000006;
    for(int i = 1; i <= n; ++i)
    {
            cnt= dfs(i);
          ///  cout<<cnt<<endl<<endl<<endl;
            mx=max(cnt,mx);
        }

    cout<<endl<<mx;
}




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

int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for (int i=0; i<N; i++){
    cin >> H[i];
  }
  // H[i-1] - H[i] > 2 の場合不可能？
  string ans = "Yes";
  int h = H[N-1];
  for (int i=N-2; i>=0; i--){
    if (H[i] - h > 1){
      ans = "No";
      break;
    } else if (H[i] - h == 1){
      // H[i]を一段下げればよい
      h = H[i] - 1;
    } else{
      h = H[i];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

  int ans = 1;
  for (int i = 1; i < n; i ++) {
    if (s[i - 1] != s[i]) ans ++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
    int n,a,b;cin >> n >> a >> b;
    cout << min(a,b) << " " << max(0ll,a+b-n) << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top = 0, S[1000];

void push(int x) {
  S[++top] = x;
}

int pop(void) {
  top--;
  return S[top+1];
}

int main(void) {
  int a, b;
  top = 0;
  char s[100];
  while(scanf("%s",s) != EOF) {
    if(s[0] == '+') {
      a = pop();
      b = pop();
      push(a + b);
    } else if(s[0] == '-') {
      b = pop();
      a = pop();
      push(a - b);
    } else if(s[0] == '*') {
      a = pop();
      b = pop();
      push(a * b);
    } else {
      push(atoi(s));
    }
  }
  printf("%d\n",pop());

  return 0;
}


Measured memory_bytes: 2032
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//子の数が分かるUnionFind
struct UFT {
private:
	vector<int> par, rank;
	vector<int> c_n; //子の数
	void init(int n = 1) {
		par.resize(n); rank.resize(n); c_n.resize(n);
		for (int i = 0; i < n; i++)par[i] = i, rank[i] = 0, c_n[i] = 1;
	}
	void update(int x) {
		if (par[x] == x)return;
		else {
			int r = root(par[x]);
			c_n[par[x]] += c_n[x];
			par[x] = r;
			return;
		}
	}
	int root(int x) {
		if (par[x] == x)return x;
		else {
			int r = root(par[x]);
			return par[x] = r;
		}
	}
public:
	UFT(int n = 1) {
		init(n);
	}
	int weight(int x) {
		return c_n[root(x)];
	}
	bool issame(int x, int y) {
		return root(x) == root(y);
	}
	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y)false;
		if (rank[x] < rank[y])swap(x, y);
		if (rank[x] == rank[y])rank[x]++;
		par[y] = x;
		update(y);
		return true;
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> p(N);
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}
	UFT t(N + 1);
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		t.merge(x, y);
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (t.issame(p[i], i + 1))ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define dump(x)  cerr << #x << " => " << (x) << endl
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
typedef long long LL;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double eps = 1e-10;
constexpr long mod = 998244353;
typedef vector<long> VL;
typedef vector<vector<long>> VLL;
typedef vector<vector<vector<long>>> VLLL;
// LONG_MAX,LLONG_MAX
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class Key,class Value> ostream& operator << (ostream &s, map<Key,Value> M)
{ for ( auto itr = begin(M); itr != end(M); ++itr) { s << itr->first << ":" << itr->second; } return s;}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> a(N);
    int s = 0;
    REP (i,N) {
        cin >> a[i];
        s += a[i];
    }
    
    vector<vector<long>> dp(N+1,vector<long>(s+1,0));
    dp[0][0] = 1;
    REP(i,N) {
        REP(R,s+1) {
            if (R >= a[i]) {
                dp[i+1][R] += dp[i][R-a[i]];
            }
            dp[i+1][R] += (2 * dp[i][R]);
            dp[i+1][R] %= mod;
        }
    }
    
    vector<vector<long>> dp2(N+1,vector<long>(s+1,0));
    dp2[0][0] = 1;
    REP(i,N) {
        REP(R,s+1) {
            if (R >= a[i]) dp2[i+1][R] += dp2[i][R-a[i]];
            dp2[i+1][R] += (dp2[i][R]);
            dp2[i+1][R] %= mod;
        }
    }

    int f = (s+1) / 2;
    long long int ans = 1;
	for (int i = 0; i < N; i++) {
		ans *= 3;
		ans %= mod;
	}
    FOR(R,f,s+1) {
        ans += (mod-dp[N][R]);
        ans %= mod;
        ans += (mod-dp[N][R]);
        ans %= mod;
        ans += (mod-dp[N][R]);
        ans %= mod;

    }
    if (s % 2 == 0) {
        ans += 3*dp2[N][s/2];
        ans %= mod;
    }

    cout << ans%mod << endl;
}


Measured memory_bytes: 423872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    int n;
    cin >> n;
    int h = 0, l = 1000000001;
    while(n--){
        int a;
        cin >> a;
        h = max(h, a);
        l = min(l, a);
    }
    cout << h - l << endl;
}


Measured memory_bytes: 256
N = int(input())

ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

# case
# すべて a > b
# すべて b < a
# 2個  a > b
# 1個  a > b

# weight:ga price:gb どんぐり weight:1 price:1


vmax = 0
for g in range(0,N + 1, ga):
    for s in range(0,N + 1 - g, sa):
        v = (g // ga) * gb + (s // sa) * sb
        amari = N - g - s
        if amari < 0:
            break
        if ba < bb:
            v += amari // ba * bb
            amari %= ba
        v += amari

        vmax = max(vmax, v)

D = vmax
vmax = D

if ba < bb:
    tmp = sa,sb
    sa,sb = ba,bb
    ba,bb = tmp

for g in range(0,D + 1, gb):
    if ga < gb and g > 0:
        break
    for s in range(0, D + 1 - g, sb):
        if sa < sb and s > 0:
            break
        v = (g // gb) * ga + (s // sb) * sa
        amari = D - g - s
        if amari < 0:
            break
        if ba > bb:
            v += amari // bb * ba
            amari %= bb
        v += amari

        vmax = max(vmax, v)

print(vmax)


Measured memory_bytes: 41580
import sys

input = sys.stdin.readline


def main():
    n = int(input())
    B = list(map(int, input().split()))
    B = [10 ** 5] + B + [10 ** 5]
    print(sum([min(i, j) for i, j in zip(B[:-1], B[1:])]))


if __name__ == "__main__":
    main()


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

int main() {
 int A,B,C,D;
 cin >> A >> B >> C >> D;
 if(A+B>C+D)
    cout <<"Left" << endl;
    else if(A+B<C+D)
            cout << "Right" << endl;
            else
            cout <<"Balanced"<< endl;
  
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int n;
	int h[251];
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&(h[i]));
	}
	for(i=1;i<=n;i++){
		printf("node %d: key = %d, ",i,h[i]);
		if(i>=2){
			printf("parent key = %d, ",h[i/2]);
		}
		if(i*2<=n){
			printf("left key = %d, ",h[i*2]);
		}
		if(i*2+1<=n){
			printf("right key = %d, ",h[i*2+1]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ri(x) scanf("%d", &x)
#define FORR(i, a, b) for(int i = a; i > b; i -= 1)
#define FOR(i, a, b) for(int i =a; i < b; i += 1)
#define pb push_back
#define ll long long int
#define vi vector<int>
#define MAXN 5005
#define INF 10000000000004
using namespace std;
int n, H[MAXN], P[MAXN];
vi a;
ll dp[MAXN][MAXN];

void read(){
	ri(n);
	FOR(i, 0, n)
	{
		ri(H[i]); ri(P[i]);
		a.pb(i);
	}
}

bool comp(int i, int j){
	return H[i] + P[i] < H[j] + P[j];
}


ll DP(int i, int k)
{
	if(i < 0 && k > 0) return INF;
	if(k == 0) return 0;
	if(dp[i][k] != -1) return dp[i][k];
	
	ll with = DP(i-1, k-1);
	ll without = DP(i-1, k);
	
	if( with <= H[a[i]])
		dp[i][k] = min(with + P[a[i]], without);
	else
		dp[i][k] = without;
		
	return dp[i][k]; 
}

int main() {
	read();
	FOR(i, 0, n) FOR(j, 0, n+1) dp[i][j] = -1;
	sort(a.begin(), a.end(), comp);
	FORR(k, n, -1)
	{
		ll e = DP(n-1, k);
		if(DP(n-1, k) != INF)
		{
			printf("%d\n",k);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 196096
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
#include<utility>
#include<bits/stdc++.h>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(A) A.begin(),A.end()
bool comparator(P a, P b) {
	return a.first / a.second < b.first / b.second;
}


int main() {
	int n;
	cin >> n;
	for (int i = 0; i < 3; i++) {
		int a = n % 10;
		if (a == 7) {
			cout << "Yes" << endl;
			return 0;
		}
		n = n / 10;
	}
	cout << "No" << endl;
}


Measured memory_bytes: 3584
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
  int H, i;
  int *A;
  int parent, left, right;

  scanf("%d", &H);
  A = (int *)malloc(sizeof(int) * (H + 1));
  for (i = 1; i <= H; i++) scanf("%d", &A[i]);

  for (i = 1; i <= H; i++) {
    printf("node %d: key = %d, ", i, A[i]);
    parent = (int)floor(i/2.0);
    left = 2 * i;
    right = 2 * i + 1;
    if (1 <= parent && parent <= H) printf("parent key = %d, ", A[parent]);
    if (1 <= left && left <= H) printf("left key = %d, ", A[left]);
    if (1 <= right && right <= H) printf("right key = %d, ", A[right]);
    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 600