akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include<climits>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

int i,j,k,l,m,n;
/////////////////////////////////////////////////////


ll N;
ll h[111][111];
int x[111],y[111];

int sub(int &x1,int &y1,int &x2,int &y2){
    return (x1>x2?x1-x2:x2-x1)+(y1>y2?y1-y2:y2-y1);
}

int main(){
    scanf("%lld",&N);
    fornum(i,0,111){
        fornum(j,0,111){
            h[i][j]=-1;
        }
    }
    fornum(i,0,N){
        scanf("%d%d",&x[i],&y[i]);
        scanf("%lld",&h[x[i]][y[i]]);
    }
    /*
    fornum(i,0,6){
        fornum(j,0,6){
            printf("%lld ",h[i][j]);
        }
        printf("\n");
    }
    */
    fornum(i,0,101){
        fornum(j,0,101){
            int flag=1;
            ll checkh=0;
            fornum(k,0,N){
                if(h[x[k]][y[k]]==0)
                    continue;
                checkh=h[x[k]][y[k]]+sub(i,j,x[k],y[k]);
                break;

            }

            fornum(k,0,N){
                if(h[x[k]][y[k]]==0&&checkh<sub(i,j,x[k],y[k]))
                    continue;
                if(checkh!=h[x[k]][y[k]]+sub(i,j,x[k],y[k])){
                    
                    flag=0;
                    break;
                }

            }
            /*
            fornum(k,0,101){
                fornum(l,0,101){
                    if(checkh==-1){
                        if(h[k][l]==-1)
                            continue;
                        else
                            checkh=h[k][l]+sub(i,j,k,l);
                    }
                    if(h[k][l]!=-1&&checkh!=h[k][l]+sub(i,j,k,l)){
                        flag=0;
                        break;
                    }
                }
                if(flag==0)
                    break;
            }
            */
            if(flag==1){
                printf("%d %d %lld",i,j,checkh);
                return 0;
            }
        }
    }

    return 0;
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	int n, k;
	cin >> n;
	vl a(n + 1, 0);
	a[1] = 1;
	for (k = 2; k <= n; k++) {
		int i = 2;
		int j = k;
		while (i <= k) {
			if (j%i != 0) {
				i++;
			}
			else {
				a[i]++;
				j /= i;
			}
		}
	}
	ll ans = 1;
	for (int i = 2; i <= n; i++) {
		if (a[i] != 0) {
			ans = (ans * (a[i] + 1)) % MOD;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;
constexpr LL kInf = 1e18;

int L;
struct Cost {
  LL cnt = kInf;
  LL dist = kInf;

  Cost () {}
  Cost (int d) : cnt(0), dist(d) {}

  Cost operator+(const Cost& right) const {
    Cost ret;
    ret.cnt = this->cnt + right.cnt;
    ret.dist = this->dist + right.dist;
    if (ret.dist > L) {
      ret.cnt++;
      ret.dist = right.dist;
    }

    return ret;
  }

  bool operator<(const Cost &right) const {
    if (this->cnt != right.cnt) return this->cnt < right.cnt;
    else                        return this->dist < right.dist;
  }
  bool operator>(const Cost &right) const {
    if (this->cnt != right.cnt) return this->cnt > right.cnt;
    else                        return this->dist > right.dist;
  }
};


template<typename T>
auto makeNdVector(int n) {
  return vector<T>(n);
}

template<typename T, typename N, typename... Tail>
auto makeNdVector(const N& n, const Tail&... tail) {
  auto vec = makeNdVector<T>(tail...);
  vector<decltype(vec)> vecs(n, vec);
  return vecs;
}

typedef pair<Cost, int> P;  // cost, vertex_idx
struct Edge {
  int to;
  Cost cost;
  Edge(int a, LL b) : to(a), cost(Cost(b)) {}
};

vector<Cost> dijkstra(int s, const vector<vector<Edge>>& G) {
  priority_queue<P, vector<P>, greater<P>> que;

  vector<Cost> d(G.size());
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    auto [dist, v] = que.top(); que.pop();

    if (d[v] < dist) continue;
    for (const auto& e : G[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }

  return d;
}

int main() {
  int N, M; cin >> N >> M >> L;
  vector<vector<Edge>> G(N);
  for (int i = 0; i < M; ++i) {
    int A, B, C; cin >> A >> B >> C; --A, --B;
    if (C <= L) {
      G[A].push_back(Edge(B, C));
      G[B].push_back(Edge(A, C));
    }
  }

  vector<vector<Cost>> ds(N);
  for (int i = 0; i < N; ++i) {
    ds[i] = dijkstra(i, G);
  }

  int Q; cin >> Q;
  for (int i = 0; i < Q; ++i) {
    int s, t; cin >> s >> t; --s, --t;
    if (ds[s][t].cnt == kInf) cout << -1 << endl;
    else                      cout << ds[s][t].cnt << endl;
  }
}


Measured memory_bytes: 9780
//<There are two ways to write error-free programs; only the third works!!>
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define I_L_Z_D ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
const int N = 2e5 + 7;

int32_t main(){
    I_L_Z_D ;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","rb",stdin);
    // #endif
int a , b , c;
cin >> a >> b >> c;
if(a==b && b==c){
    if(a + b > c && b + c > a && c + a > b ) cout << "Yes";
    else cout << "No";
}
else cout << "No";
return 0 ;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int  x1 ,  x2 , x3 , x4 ,  x5;
cin >> x1 >> x2 >> x3 >> x4 >> x5;
if(x1==0)
{
cout << "1";
}
else if(x2==0)
{
cout << "2";
}
else if(x3==0)
{
cout << "3";
}
else if(x4==0)
{
cout << "4";
}
else 
{
cout << "5";
}
return 0;
}

Measured memory_bytes: 3604
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD

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

int l[305];
vector<int> heights;
ll dp[305][305]; // <height index, num changes>
ll ndp[305][305];
void solve() {
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> l[i];
    heights.push_back(l[i]);
  }
  heights.push_back(0);
  sort(all(heights));
  heights.resize(unique(all(heights))-heights.begin());
  memset(dp, 1, sizeof(dp));
  dp[0][0] = 0;
  for(int i = 0; i < n; i++) {
    memset(ndp, 1, sizeof(ndp));
    // don't change the height
    int idx = lower_bound(all(heights), l[i]) - heights.begin();
    for(int a = 0; a < sz(heights); a++) {
      for(int b = 0; b <= k; b++) {
        if(a != idx) {
          ndp[idx][b] = min(ndp[idx][b], dp[a][b] + max(0, heights[idx] - heights[a]));
        }
        else {
          ndp[idx][b] = min(ndp[idx][b], dp[idx][b]);
        }
      }
    }
    // going up the thing
    for(int b = 0; b < k; b++) {
      ll curr = dp[0][b];
      ndp[0][b+1] = min(ndp[0][b+1], dp[0][b]);
      for(int a = 1; a < sz(heights); a++) {
        curr = min(curr + heights[a] - heights[a-1], dp[a][b]);
        ndp[a][b+1] = min(ndp[a][b+1], curr);
      }
    }
    memcpy(dp, ndp, sizeof(dp));
  }
  ll ret = 1e18;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= k; j++) ret = min(ret, dp[i][j]);
  }
  cout << ret << "\n";
}

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


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

int main(void){

  int n,i,ans=0,maxa=0;
  cin>>n;
  vector<int> a(n);
  
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  int c;
  rep(i,a[1]){
    c=0;
    rep(j,n){
      ans = a[1]-i;
      if(a.at(j)%ans!=0) ++c;
      if(c>2)break;
    }
    if(c<=1){cout<<ans;return 0;}
  }
  
}

Measured memory_bytes: 640
//  Friendly NUKE is ready!!
#include <bits/stdc++.h>
#define SPEED ios::sync_with_stdio(false); cin.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define dbg(x) cout<<#x<<": "<<x<<endl
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define mo 1000000007
#define inf 1e18
#define eps 0.0000000001
#define stp setprecision(20)
#define all(v) v.begin(),v.end()
#define endl '\n'
using namespace std;
//mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
 
#define N  int(1010)+10
ll dp[N][N];char s[N][N] ;
int main()
{    SPEED;
       int n,x;
       cin>>n>>x;
       loop(i,1,n+1){
       	 loop(j,1,x+1)
       	  cin>>s[i][j];
       }
       if(s[1][1]!='#')
       dp[1][1]=1;
      
       loop(i,1,n+1){
       	  
       	   loop(j,1,x+1){
       	   	 if(s[i][j+1]!='#')
       	   	  dp[i][j+1]+=dp[i][j], dp[i][j+1]%=mo;
       	   	  if(s[i+1][j]!='#')
       	   	  dp[i+1][j]+=dp[i][j],dp[i+1][j]%=mo;
       	   }
       }
       cout<<dp[n][x]; 
}

Measured memory_bytes: 12460
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define F first
#define S second
using namespace std;
typedef pair<int,int>p;

vector<p>g[103];
int d[103];
main()
{
  int n;
  int u, k, v, c;
  
  scanf("%d", &n);
  for (int i = 0; i < n ; ++i) {
    scanf("%d %d", &u, &k);
    for(int j = 0; j < k ; ++j) {
      scanf("%d %d", &c, &v);
      g[u].push_back(p(c,v));
    }
    d[i] = 1 << 21;
  }
  
  priority_queue< p, vector<p>, greater<p> >p_que;
  p_que.push(p(0,0));
  d[0] = 0;
  while ( !p_que.empty() ) {
    p now = p_que.top(); p_que.pop();
    int pos = now.F;
    int cost = now.S;
    for ( int i = 0; i < g[pos].size() ; ++i) {
      int ncost = cost + g[pos][i].S;
      if ( ncost < d[g[pos][i].F] ) {
	d[g[pos][i].F] = ncost;
	p_que.push(p(g[pos][i].F,ncost));
      }
    }
  }

  for ( int i = 0; i < n ; ++i) {
    printf("%d %d\n", i, d[i]);
  }

  return (0);
}



Measured memory_bytes: 3224
#include<stdio.h>
#include<string.h>
int main() {
	char a[100];
	scanf("%s",a);
	int n=strlen(a);
	for(int i=0;i<n;i++){
		if(a[i]==','){
			a[i]=' ';
		}
	}
	printf("%s",a);
	return 0;
}

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

int main(){
  string a, b;
  cin >> a >> b;
  int am, bm;
  am = a.size();
  bm = b.size();
  int n [1002][1002] = {};

  for(int i=0; i < bm; i++){
    char bi = b[i];
    for(int j = 0; j < am; j++){
      char ai = a[j];
      if(i == 0){
        if(ai == bi){
        
          n[i][j]++ ;
          n[i][j] %= 1000000007;
          n[i][j+1] = n[i][j];
        }else{
          n[i][j+1] = n[i][j];
        }
      }
      if(i != 0){
        if(ai == bi){
          n[i][j] = n[i-1][j-1]+n[i][j-1];
          n[i][j] %= 1000000007;
          n[i][j+1] = n[i][j];
        }else{
          n[i][j+1]=n[i][j];
        }
      }
      
    }
  }
  /* for(int i=0; i<bm ;i++){
   
    for(int j=0; j<am;j++){
      cout << n[i][j] <<" ";
    }
    cout << endl; 
    }*/
  cout << n[bm - 1][am - 1] << endl; 
}



Measured memory_bytes: 7128
#include<stdio.h>

/* 値を入れ替える関数 */
void swap (unsigned long *x, unsigned long *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (unsigned long array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (unsigned long array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}

int main() {
    unsigned long N, K, H[200000], sum=0;
    int i, enemy;

    scanf("%lu %lu", &N, &K);
    for (i=0; i<N; i++) {
        scanf("%lu", &H[i]);
    }

    quick_sort(H, 0, N-1);

    // printf("%lu %lu", N, K);

    enemy = N - K; 

    // 必殺技で減らした残りの敵の数(maxnode番目が最大体力)
    for (i=0; i<enemy; i++) sum += H[i];

    printf("%lu", sum);

    return 0;
}

Measured memory_bytes: 1664
#include <iostream>

using namespace std;

int main() {
    int n;  cin >> n;
    long long a;
    int cnt_2 = 0, cnt_4 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (!(a%2) && (a%4))
            cnt_2++;
        else if (!(a%2) && !(a%4))
            cnt_4++;
    }

    if (cnt_2 == 0) {
        if (cnt_4*2+1 >= n)
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
        return 0;
    }
    n -= cnt_2;

    if (cnt_4*2 >= n)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int p, q, r;
    cin >> p >> q >> r;
    int pq = p + q;
    int qr = q + r;
    int rp = r + p;
    int m = min({pq, qr, rp});
    printf("%d\n", m);
    return 0;
}


Measured memory_bytes: 256
n,m,c = list(map(int, input().strip().split()))
b= list(map(int, input().strip().split()))
s = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    s.append(array)
ans=0
for i in range(n):
    x=c
    for j in range(m):
        x+=b[j]*s[i][j]
    if x>0:
        ans=ans+1
print(ans)

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

using vi = vector<int>;
using vll = vector<long long>;

constexpr long long mod = 1000000007;

template <typename T>
vector<T> _divisor(T a) {
    vector<T> res;
    for (T i = 1; i * i <= a; i++) {
        if (a % i == 0) {
            res.push_back(i);
            if (i != 1 && i * i != a)
                res.push_back(a / i);
        }
    }

    sort(res.begin(), res.end());
    return res;
}

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

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

    long long n;
    cin >> n;

    long long cnt = 0;

    if (n == 2) {
        cout << 1 << endl;
    } else {
        vll v;

        v = _divisor(n - 1);

        vll d;
        d = _divisor(n);
        d.push_back(n);

        for (int i = 1; i < d.size(); i++) {
            long long t = n;

            while (t >= d[i]) {
                if (t % d[i] == 0) {
                    t /= d[i];
                    if (t == 1) {
                        cnt++;
                    }
                } else {
                    if (t % d[i] == 1) {
                        cnt++;
                    }
                    break;
                }
            }
        }

        cout << cnt + v.size() << endl;
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    vector<int> I = {0};
    for (int i = 0; i < N; i++) {
        if (A[i] > A[I.back()]) {
            I.push_back(i);
        }
    }
    vector<Int> X(I.size()), C(I.size()), R(I.size());
    for (int i = 0; i < I.size(); i++) X[i] = A[I[i]];
    for (int i = 0; i < N; i++) {
        int t = lower_bound(begin(X), end(X), A[i]) - begin(X);
        R[t] += A[i] - X[t];
        C[t] += 1;
    }
    for (int i = I.size()-2; i >= 0; i--) {
        C[i] += C[i+1];
    }
    vector<Int> ANS(N);
    for (int i = 0; i < I.size(); i++) {
        ANS[I[i]] = C[i] * (X[i] - (i-1 >= 0 ? X[i-1] : 0)) + R[i];
    }
    for (auto a : ANS) cout << a << '\n';
    return 0;
}

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

using namespace std;
int a[100050][3];
int dp[100050][3];
const int INF =1<<30;

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++)scanf("%d",&a[i][j]);
	}
	
	for(int i=0;i<3;i++)	dp[0][i]=a[0][i];
	
	for(int i=0;i<n-1;i++){
		for(int j=0;j<3;j++){
			int max1=0;
			for(int k=0;k<3;k++){
				if(k!=j)	max1=max(max1,dp[i][k]);
			}
			dp[i+1][j]=a[i+1][j]+max1; 
		}
	}
	
	int ans=0; 
	for(int i=0;i<3;i++)ans=max(ans,dp[n-1][i]);
	cout<<ans;
	
	return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define mod ((ll)1e9+7)
#define inf ((ll)1e18+5)
#define maxx ((ll)1e6+5)
#define pb push_back
#define endl "\n"
#define time(i) cout<<"\nTime Elapsed "<<i<<" : " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
#define usefile freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test ll t; cin>>t; while(t--)
ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}
ll expm(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x%mod)%mod; x=(x*x)%mod; y/=2; } return res;}
/*
bool sv[maxx]={0};    // returns 0 if a num is prime
int sp[maxx]={0};     // gives smallest prime factor of the number
void Sieve() {for(int i= 2; i< maxx; i+= 2) sv[i]=1,sp[i] = 2;sv[2]=0;for(ll i = 3; i < maxx; i += 2){if (!sv[i]){sp[i] = i;for (ll j = i; (j*i) < maxx; j += 2){if (!sv[j*i])sv[j*i] = true, sp[j*i] = i;}}}}
ll fact[maxx]={0}; // returns factorial of that number
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<maxx;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncrm(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(expm(fact[r],mod-2)))%mod; res=(res*(expm(fact[n-r],mod-2)))%mod; return res;}
ll inv[maxx];   // returns the modular inverse of number
void inversify( ll m){inv[1]=1;for(int i=2;i<maxx;i++){inv[i]= m- m/i*inv[m%i]%m;}}
ll ncr(ll n,ll r,ll m){int ans=1;for (int i = 0; i < r; i++){ans=ans*(n-i)%m*inv[i+1]%m;}return ans;}
*/
signed main(){
  fast;
  //usefile;
  //test
  {
    int n;
    cin>>n;
    map<int,int>mp;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
      int temp;
      cin>>temp;
      v[i]=temp;
      mp[temp]++;
    }
    int ans=0;
    for(auto i:mp){
      ans+=i.second*(i.second-1)/2;
    }
    for(int i=0;i<n;i++)
    {
      int res=ans-mp[v[i]]+1;
      cout<<res<<endl;
    }
    
  }
  //time("");
  return 0; }


Measured memory_bytes: 11136
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = [v]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_u = dfs(u)
    dist_v = dfs(v)

    d = 1
    for i in range(1, n+1):
        if dist_v[i] >= dist_u[i]:
            d = max(d, dist_v[i])
    ans = d - 1
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 36284
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>


//セグ木
ll dat[5010000], sz;

void init(ll n) {
	sz = 1;
	while (sz < n)sz *= 2;
	REP(i, sz * 2 - 1) dat[i] = 0; //初期値
}

void update(ll k, ll a) { //場所(0-indexed), 値
	k += sz - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; //更新
	}
}

ll query(ll a, ll b, ll k, ll l, ll r) { //[a, b) 呼ぶとき (a, b, 0, 0, sz)
	if (r <= a or b <= l)return 0;
	if (a <= l and r <= b)return dat[k];
	ll v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
	ll v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
	return v1 + v2; //戻り値
}

ll n, k, s[210000], r[210000], now, ans;
map<ll, ll> mp;
int main() {
	init(210000);
	cin >> n >> k;
	mp[0] = 0;
	REP(i, n) {
		cin >> s[i];
		s[i] -= k;
		r[i + 1] = r[i] + s[i];
		mp[r[i + 1]] = 0;
	}
	for (auto& i : mp) {
		i.second = now;
		now++;
	}
	REP(i, n + 1) {
		ans += query(0, mp[r[i]] + 1, 0, 0, sz);
		update(mp[r[i]], query(mp[r[i]], mp[r[i]] + 1, 0, 0, sz) + 1);
	}
	cout << ans << endl;

}


Measured memory_bytes: 20864
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=100005;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
struct node{int sum,id;bool operator <(const node &a)const{return sum>a.sum;}}a[N],b[N];
int main(){
	int n=Getint();
	for(int i=1;i<=n;i++){
		int x=Getint();
		if(i&1)b[x].sum++,b[x].id=x;
		else a[x].sum++,a[x].id=x;
	}	
	sort(a+1,a+1+100000);
	sort(b+1,b+1+100000);
	if(b[1].id!=a[1].id)cout<<n-b[1].sum-a[1].sum;
	else cout<<min(n-b[1].sum-a[2].sum,n-b[2].sum-a[1].sum);
}

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

#define F first
#define S second
#define prev azaza
#define MP make_pair
#define PB push_back

using namespace std;
typedef long long ll;
typedef long double ld;

const int max_n = 1, inf = 1000111222;

string s[3];

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    cin >> s[0] >> s[1] >> s[2];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        set<char> ss;
        ss.insert(s[0][i]);
        ss.insert(s[1][i]);
        ss.insert(s[2][i]);
        if (ss.size() == 1) continue;
        if (ss.size() == 2) ans += 1;
        else ans += 2;
    }
    cout << ans << endl;
    return 0;
}





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

int main()
{
	int n;
	int d[200];
	int max=0;

	cin >> n;
	for (int i = 0;i < n;i++)
		cin >> d[i];
	for (int i = 0;i < n - 1;i++)
	{
		for (int j = i + 1;j < n;j++)
		{
			max += d[i] * d[j];
		}
	}

	cout << max;
	return 0;
}

Measured memory_bytes: 256
//itp1_8-d
#include <iostream>
#include <string>
using namespace std;

int main(){
 string s,s2,p;
 getline(cin,s);
 getline(cin,p);

 s2=s+s;
 if(s2.find(p)!=string::npos) cout<<"Yes"<<endl;
 else cout<<"No"<<endl;

 return 0;
}

Measured memory_bytes: 1184
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    string s;
    cin>>s;
    for(char c:s) if(c=='7') return cout<<"Yes",0;
    cout<<"No";
    return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>

int main(void){
  
  int N;
  int a[N];
  int i;
  int s=0;
  
  scanf("%d",&N);
  
  for(i=0;i<=N;i++){
      
	scanf("%d ",&a[i]);

	s+=a[i];    
    
  }
  

  
  
  
  printf("%d\n",s-N);
    
  return 0;
  
}

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

#define int long long

int n;
char c;

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	while (n--) {
		cin >> c;
		if (c == 'Y')
			return cout << "Four" << endl, 0;
	}
	cout << "Three" << endl;
}

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

int main() {
  int A, B, Q; cin >> A >> B >> Q;
  vector<long long> s(A+2), t(B+2), x(Q);
  for (int i = 0; i < A; i++) cin >> s.at(i);
  for (int i = 0; i < B; i++) cin >> t.at(i);
  for (int i = 0; i < Q; i++) cin >> x.at(i);
  long long INF = 1LL << 50;
  s.at(A) = INF; s.at(A+1) = -INF;
  t.at(B) = INF; t.at(B+1) = -INF;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  for (int i = 0; i < Q; i++) {
    vector<long long> sh(2), te(2);
    int sh_idx = lower_bound(s.begin(), s.end(), x.at(i)) - s.begin();
    sh.at(0) = s.at(sh_idx-1);  // west side
    sh.at(1) = s.at(sh_idx);  // east side
    int te_idx = lower_bound(t.begin(), t.end(), x.at(i)) - t.begin();
    te.at(0) = t.at(te_idx-1);
    te.at(1) = t.at(te_idx);
    long long ans = 1LL << 50;
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        ans = min(ans, abs(sh.at(j) - x.at(i)) + abs(te.at(k) - sh.at(j)));
        ans = min(ans, abs(te.at(k) - x.at(i)) + abs(te.at(k) - sh.at(j)));
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 3712
n = int(input())
t, a = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]


m = abs(50-0.006*10**5)
ans = -1
for j in range(n):
    if abs(a - (t-h[j]*0.006)) < m:
        m = abs(a - (t-h[j]*0.006))
        ans = j
    else:
        pass

print(ans+1)

Measured memory_bytes: 3060
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;


void main() {
    int n, q;
    scan(n, q);

    while (q--) {
        int vi, wi;
        scan(vi, wi);
        solve(n, vi, wi);
    }
}

void solve(int n, int v, int w) {
    if (n == 1) {
        writeln(min(v, w));
        return;
    }

    auto va = new int[](0);
    va ~= v;

    while (v > 1) {
        v = (v + n - 2) / n;
        va ~= v;
    }

    auto wa = new int[](0);
    wa ~= w;

    while (w > 1) {
        w = (w + n - 2) / n;
        wa ~= w;
    }

    debug {
        writeln(va);
        writeln(wa);
    }

    int ans = 0;

    foreach (vi ; va) {
        foreach (wi ; wa) {
            if (vi == wi) {
                ans = max(ans, vi);
            }
        }
    }

    writeln(ans);
}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 2300
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
L = sorted(l, key = lambda x:x[1])
cumsum = 0
for i in range(n):
    cumsum += L[i][0]
    if cumsum > L[i][1]:
        print('No')
        exit()
print('Yes')

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

int main() {
  int N;
  cin >> N;
  vector<pair<string, int>> rest1(N), rest2(N);
  for (int i = 0; i < N; i++)
    cin >> rest1.at(i).first >> rest1.at(i).second;
  for (int i = 0; i < N; i++)
    rest1.at(i).second *= -1;
  rest2 = rest1;
  sort(rest2.begin(), rest2.end());
  for (int i = 0; i < N; i++) {
    rest1.at(i).second *= -1;
    rest2.at(i).second *= -1;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (rest2.at(i) == rest1.at(j))
        cout << j + 1 << endl;
    }
  }
    
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<stdio.h>
#include<cmath>
using namespace std;

#define max(a,b) a > b ? a : b

int main() {

    int A,B;

    cin >> A;
    cin >> B;

    if (A == 1)
    {
        if (B == 2)
        {
            cout << 3 << endl;
        }
        else {
            cout << 2 << endl;
        }
    }
    else if (A == 2)
    {
        if (B == 1) {
            cout << 3 << endl;
        }
        else
        {
            cout << 1 << endl;
        }
    }
    else
    {
        if (B == 1)
        {
            cout << 2 << endl;
        }
        else
        {
            cout << 1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main()
{
	ll h,w;
	cin >> h >> w;
	
	ll A,B,C;
	ll ans=LLONG_MAX;
	for(ll i=1;i<h;i++)
	{
		A=i*w;
		B=((h-i)/2)*w;
		C=w*h-A-B;
		ll ma= max(max(A,B),C);
		ll mi= min(min(A,B),C);
		ans=min(ans,ma-mi);

		B=(h-i)*(w/2);
		C=w*h-A-B;

		ma= max(max(A,B),C);
		mi= min(min(A,B),C);
		ans=min(ans,ma-mi);
	}
	swap(w,h);
	for(ll i=1;i<h;i++)
	{
		A=i*w;
		B=((h-i)/2)*w;
		C=w*h-A-B;
		ll ma= max(max(A,B),C);
		ll mi= min(min(A,B),C);
		ans=min(ans,ma-mi);

		B=(h-i)*(w/2);
		C=w*h-A-B;

		 ma= max(max(A,B),C);
		 mi= min(min(A,B),C);
		ans=min(ans,ma-mi);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#組み合わせ個数
def choose(n, r, mod)
  return 0 if not (0 <= r and r <= n)
  return 1 if r == 0 or r == n
  fact(n, mod) * inverse(fact(r, mod) * fact(n-r, mod) % mod, mod) % mod
  #fact2(n, r, mod) * inverse(fact(r, mod) % mod, mod) % mod
end
#階乗(MODあり)
@fact = [1]
def fact(n, mod)
  if n > @fact.size then
    f = @fact[-1]
    (@fact.size+1..n).each{|i|
      f = (f * i) % mod
      @fact << f
    }
  end
  @fact[n-1]
end
def fact2(n, r, mod)
  f = 1
  n.downto(n-r+1){|i|
    f = (f * i) % mod
  }
  f
end

#逆元(MODあり)
def inverse(x, mod)
  pow(x, mod-2, mod)
end
#べき乗(MODあり)(繰り返し２乗法)
def pow(x, n, mod)
  ans = 1
  while n > 0
    ans = ans * x % mod if n.odd?
    x = x * x % mod
    n >>= 1
  end
  ans
end

N, K = gets.chomp.split(" ").map(&:to_i)
MOD = 10 ** 9 + 7

ans = 0
s = N > K-1 ? N - K : 1
(s..N).each{|n|
  ans = (ans + (choose(N, n, MOD) ** 2) * n) % MOD
}
ans = (ans * inverse(N, MOD)) % MOD

puts ans


Measured memory_bytes: 3452
//Don't have to see. start------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin, output: process.stdout
});
var obj; var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error('\n↑入力 ↓出力');
  Main();
});
function makeClone(obj){return (obj instanceof Set) ? new Set(Array.from(obj)) : JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  return {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(this.hasNext()){return this.list[this.index++];}else{throw 'ArrayIndexOutOfBoundsException ‚There is no more input';}}
  };
}
function myout(s){console.log(s);}
function myerr(s){console.error('debug:' + require('util').inspect(s,false,null));}
//param "no" is
//unknown or outlier : return i. 1: parseInt.
//2: split space. 4: split space and parseInt.
//6: split 1 character. 7: split 1 character and parseInt.
//8: join space. 9: join nextline. 0: join no character.
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(' ');case 4:return i.split(' ').map(Number);case 6:return i.split('');case 7:return i.split('').map(Number);case 8:return i.join(' ');case 9:return i.join('\n');case 0:return i.join('');default:return i;}}catch(e){return i;}}

//Don't have to see. end------------------------------------------
function Main(){
  var one = nextIntArray();
  var N = one[0];
  var M = one[1];
  var list = new Array(M);
  for(var i = 0; i < M; i++){
    list[i] = nextIntArray();
  }
  list.sort(function(a,b){
    if(b[1] == a[1]){
      return a[0] - b[0];
    }else{
      return a[1] - b[1];
    }
  });
  
  var output = 0;
  var down = -1;
  for(var i = 0; i < M; i++){
    if(down < list[i][0]){
      down = list[i][1] - 1;
      output++;
    }
  }
  myout(output);
}



Measured memory_bytes: 61796
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i =0;i<n;i++)
#include <iostream>
using namespace std;
struct UnionFind {
	vector<int> par;
	UnionFind(int n) : par(n, -1) { }
	void init(int n) { par.assign(n, -1); }
	int root(int x) {
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y); // merge technique
		par[x] += par[y];
		par[y] = x;
		return true;
	}
	int size(int x) {
		return -par[root(x)];
	}
};
int main(){
	int n, m,a,b; cin >> n >> m;
	UnionFind uf(n + m);
	rep(i, n) {
		cin >> a;
		rep(j, a) {
			cin >> b;
			b--; uf.unite(i, b + n);
		}
	}rep(i, n) {
		if (!uf.same(0, i)) {
			cout << "NO" << endl;
			return 0;
		}
	}cout << "YES" << endl;
}

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

ll N;
vector<ll> A;

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // Globalなvectorのリサイズ
  //A.resize(N);

  ll n, k;
  cin >> n >> k;
  rep(i, 10000) {
    if (pow(k, i) > n) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) ll(i.size())
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

template<class T> inline bool cmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool cmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll MAXN=3000+5;
const ll MAXLG=__lg(MAXN)+2;

ll n;
double dp[MAXN][MAXN];
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> n;
    dp[0][0] = 1;
    REP1 (i,n) {
        double p;
        cin >> p;
        for (ll j=0;j<=i;j++) {
            dp[i][j] = (j?p*dp[i-1][j-1]:0) + (1-p)*dp[i-1][j];
        }
    }

    double ans = 0;
    for (ll i=n/2+1;i<=n;i++) {
        ans += dp[n][i];
    }

    cout << fixed << setprecision(20) << ans << endl;
    return 0;
}


Measured memory_bytes: 68992
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<stdlib.h>
using namespace std;

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

    long min = 1000000001;
    int mini=0;
    for(int i=0; i<n; i++) {
        if(min > abs(a[n-1]-2*a[i])) {
            min = abs(a[n-1]-2*a[i]);
            mini = i;
        } else{
            break;
        }
    }
    cout << a[n-1] <<" " << a[mini] << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  long long N, A, B, C, D, E;
  cin >> N >> A >> B >> C >> D >> E;
  cout << max({ (N - 1) / A, (N - 1) / B, (N - 1) / C, (N - 1) / D, (N - 1) / E }) + 5 << endl;
  return 0;
}

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

using namespace std;
using ll = long long int;

int main()
{
  int n, a, b;
  cin >>n >> a >> b;
  int maxn = min(a, b);
  int temp = a + b;
  if(temp >= n){
    cout <<  maxn << " " << temp - n << endl;
  }else{
    cout << maxn << " " << 0 << endl;
  }
}


Measured memory_bytes: 888
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define sort(vvv) sort(vvv.begin(),vvv.end())
#define rvs(vvv) reverse(vvv.begin(),vvv.end())

using namespace std;

int main() {
	int a;
	cin >> a;
	double n = a;
	double ans = (a/2) / n;
	ans = 1 - ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def search_dijkstra(mat, start = 0, inf = Float::INFINITY)
	d = [inf] * mat.size
	d[start] = 0
	q = [*0...mat.size]
	until q.empty?
		i = q.min_by { |j| d[j] }
		q.delete i
		mat[i].each_with_index do |c, j|
			d[j] = d[i] + c if d[j] > d[i] + c
		end
	end
	d
end


h, w = gets.split.map &:to_i
graph = 10.times.map {gets.split.map &:to_i}
wall = h.times.map {gets.split.map &:to_i}
dists = search_dijkstra(graph.transpose, 1, 2000000000)
p wall.sum { |line| line.sum { |n| n == -1 ? 0 : dists[n] } }

Measured memory_bytes: 14588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int ji = 100001;
int n;
int a[100005], b[100005], c;
inline int rd() {
	char ch = getchar();
	int s = 0, c = 1;
	while(!isdigit(ch)) {
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s * c;
}
int tr[200005];
void add(int x, int w) {
	for(; x <= 200000; x += x & (-x)) tr[x] += w;
}
int que(int x) {
	int ans = 0;
	for(; x; x -= x & (-x)) ans += tr[x];
	return ans;
}
int cal(int mid) {
	memset(tr, 0, sizeof(tr));
	int sum = 0, ans = 0, i;
	add(0 + ji, 1);
	for(i = 1; i <= n; ++i) {
		if(a[i] > mid) ++sum;
		if(a[i] <= mid) --sum;
		ans += que(ji + ji) - que(sum + ji);
		add(sum + ji, 1);
		//if(mid == 20) cout << ans << endl;
	}
	return ans;
}
main() {
	int i;
	n = rd();
	for(i = 1; i <= n; ++i) a[i] = b[i] = rd();
	sort(b + 1, b + 1 + n);
	c = n * (n + 1) / 2;
	c = c / 2 + 1;
	int l = 1, r = n, mid;
	while(l < r) {
		mid = l + r >> 1;//cout << b[mid] << " " << cal(b[mid]) << endl; 
 		if(cal(b[mid]) < c) l = mid + 1;
		else r = mid;
	} 
	cout << b[l];
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s; cin>>s;
	string t; cin>>t;
	int ans = 0;
	for(int i =0; i<s.size(); ++i)
		if(s[i] == t[i]) ans++;
	cout<<ans;
  return 0;
}


Measured memory_bytes: 256
import sys

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


P = str(input()).upper()
line = []

while True:
    tmp_line = str(input())
    if tmp_line == 'END_OF_TEXT':
        break
    line += tmp_line.upper().split()

ans = 0

for tmp_word in line:
    if tmp_word == P:
        ans += 1

print("%d"%(ans))



Measured memory_bytes: 5572
import itertools

H,W,K = map(int, input().split())
p = 1000000007

if K - 1 > H:
    print(0)
    exit(0)
if W == 1:
    print(1)
    exit(0)

R = []
for r in itertools.product( [0,1], repeat=(W-1) ):
    if 1 not in list(map(lambda i : r[i]*r[i+1], range(len(r)-1)) ):
        R.append(r)


M = [ (
    len( list( filter( lambda r:r[0]==0, R) ) ),
    len( list( filter( lambda r:r[0]==1, R) ) ),
    0
) ]
for c in range(1,W-1):
    M.append((
        len( list( filter( lambda r:r[c]==0 and r[c-1]==0, R) ) ),
        len( list( filter( lambda r:r[c]==1, R) ) ),
        len( list( filter( lambda r:r[c-1]==1, R) ) )
    ))
M.append((
    len( list( filter( lambda r:r[W-2]==0, R) ) ),
    0,
    len( list( filter( lambda r:r[W-2]==1, R) ) )
))

count = [1] + [0]*(W-1)
for h in range(H):
    count_ = [0] * W
    for num,c in zip(count, range(len(count))):
        for m,n in zip(M[c], [0,+1,-1]):
            if c+n >= 0 and c+n < W:
                count_[c+n] += num * m
    count = count_
        
print(count_[K-1]%p)    
    


Measured memory_bytes: 3188
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

    using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

const ll mod = 1e9 + 7;


const ll nmax = 10e4 + 5;
ll dp[nmax + 1];

int main() {
  fill(dp, dp + nmax + 1, INF);

  ll n, m;
  cin >> n >> m;

  vll cs(m);

  rep(i, m + 1) cin >> cs[i];
  
  dp[0] = 0;
  rep(i, nmax + 1) rep(j, m) {
    bool cond = i - cs[j] >= 0;
    if (cond) chmin(dp[i], dp[i - cs[j]] + 1);
  }  // j

  cout << dp[n] << endl;

  return 0;
}



Measured memory_bytes: 3912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
#define pi 3.141592653589793
#define mod 998244353
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

int main() {
	fast_io;
	int n;
	cin >> n;
	vl a(n), b(n);
	for (int i = 0;i < n;i++)
		cin >> a[i] >> b[i];
	sort(all(a));
	sort(all(b));
	if (n & 1)
		cout << b[n/2] - a[n/2] + 1 << '\n';
	else {
		cout << b[n/2] + b[n/2 - 1] - a[n/2] - a[n/2 - 1] + 1 << '\n';
	}
}


Measured memory_bytes: 6368
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


MOD = 10**9 + 7


def main():
    n = _i()
    a = list(_ia())
    s = [0] * n
    for i in range(n-2, -1, -1):
        s[i] = s[i+1] + a[i+1]

    ans = 0
    for ai, si in zip(a, s):
        ans = (ans + (ai * si)) % MOD
    return ans


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 94132
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
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; }
// ---------------------------------------------------------------------------

int main(){
    string S;
    cin >> S;
    int N = S.size();
    int l = N;
    for(int i=2; i<N; i++){
        if(S[i-2] != S[i]){
            l = i;
            break;
        }
    }    
    int r;
    for(int i=N-3; i>=0; i--){
        if(S[i] != S[i+2]){
            r = i;
            break;
        }
    }
    if(l == r && l!=0){
        if(S[l-1] == S[l+1]){
            cout << "Second\n";
        }else{
            cout << "First\n";
        }
        return 0;
    }
    if((N-2 - (S[0]==S[N-1]))%2){
        cout << "First\n";
    }else{
        cout << "Second\n";
    }
    return 0;
}

Measured memory_bytes: 3760