akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int, input().split()))

q = int(input())
int_list = [list(map(int, input().split())) for _ in range(q)]
total = 0

# 数字の個数を保存しておくリスト
number = [0] * 100005
for e in a:
    number[e] += 1
    total += e

for i in range(q):

    total -= int_list[i][0] * number[int_list[i][0]]
    total -= int_list[i][1] * number[int_list[i][1]]



    number[int_list[i][1]] += number[int_list[i][0]]
    number[int_list[i][0]] = 0

    total += int_list[i][0] * number[int_list[i][0]]
    total += int_list[i][1] * number[int_list[i][1]]

    print(total)



Measured memory_bytes: 32080
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
using namespace std;

int main(void){
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    
    int ans=0,ct=0;
    rep(i,0,n){
        if(v[i]==1){
            ct=1;
            while(i+1<n && v[i]==v[i+1]){
                ct++;
                i++;
            }
            ans=max(ans,ct);
        }
    }
    cout<<ans+1<<endl;
    
    
    
    
    return 0;
}



Measured memory_bytes: 3092
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int n = sc.nextInt();
        int[] tList = new int[n];
        for(int i = 0; i < n; i++) {
          tList[i] = sc.nextInt();
        }
        int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
          // 出力
          int shortenIndex = sc.nextInt();
          int value = sc.nextInt();
          int sum = 0;
          for(int index = 0; index < n; index++) {
            if (index == shortenIndex - 1) {
              sum += value;
            } else {
              sum += tList[index];
            }
          }
		  System.out.println(sum);
        }
	}
}

Measured memory_bytes: 23252
i = gets.to_i
i.times do |i|
    x = i + 1
    if x % 3 == 0 then
        print " ", i+1
        next
    end
    while x > 0 do
        if x%10 == 3 then
            print " ", i+1
            break
        end
        x /= 10
    end
end
print "\n"


Measured memory_bytes: 6876
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 2e5 + 10;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    map < pair < int, int >, int > mp;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int c = -1;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '.') {
                c = j;
                break;
            }
        }
        if (c == -1) {
            s += '.';
            c = s.size() - 1;
        }
        ll num = 0;
        for (int a = 0; a < s.size(); a++) {
            if (s[a] == '.') continue;
            num = 10 * num + (s[a] - '0');
        }
        assert(num != 0);
        int d2 = 0;
        int d5 = 0;
        while (num % 2 == 0) {
            d2++;
            num /= 2;
        }
        while (num % 5 == 0) {
            d5++;
            num /= 5;
        }
        d2 -= (s.size() - c - 1);
        d5 -= (s.size() - c - 1);
        mp[make_pair(d2, d5)]++;
    }
    ll ans = 0;
    for (auto& it : mp) {
        for (auto& pit : mp) {
            if (it.first > pit.first) continue;
            if (it.first.first + pit.first.first < 0 || it.first.second + pit.first.second < 0) continue;
            if (it.first == pit.first) {
                ans += (1LL * it.second * (it.second - 1)) / 2;
            }
            else {
                ans += (1LL * it.second * pit.second);
            }
        }
    }
    cout << ans;
    return 0;
}

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

#define fast ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); 
 
using namespace std;
 
typedef  long long int lli; 

int main(){
    
    lli i,x,j,k,n,y,t,c,d;  
    fast;

  cin>>n;
  lli a[n];
  x=0;
  map<lli,lli>m;
  for(i=0;i<n;i++){
    cin>>a[i];
    x+=a[i];
    m[a[i]]++;
  }
  cin>>t;
  while(t--){
    cin>>c>>d;
    x=x-(c*m[c]);
    y=m[c];
    m[d]+=m[c];
    m[c]=0;
    x=x+(d*y);
    cout<<x<<'\n';
  }
  
  

  return 0;
}

Measured memory_bytes: 10260
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scan =new Scanner(System.in);
        
        
        while(scan.hasNext())
        {
            int n = scan.nextInt();
            int m = scan.nextInt();
            
            //終了条件
            if(n+m==0)
                break;
            
            int[] nFlg = new int[n];
            
            int total = n;
            int tmp=0,i=0;
            
            for(i=0;i<n;i++)
                nFlg[i]=0;
            
            while(total!=1)
            {
                for(i=0;i<m;i++)
                {
                    if(tmp+i>=n)
                    {
                        tmp=i*(-1);
                    }
                    
                    if(nFlg[tmp+i]==1)
                    {
                        i--;
                        tmp++;
                    }

                }
                nFlg[tmp+i-1]=1;
                tmp+=i;
                total--;
            }
            
            for(i=0;i<n;i++)
            {
                if(nFlg[i]==0)
                {
                   i++;
                   System.out.println(i);
                }
            }
        }
    }
}

Measured memory_bytes: 20080
import math
import fractions
import sys
import itertools
import numpy as np
from collections import Counter
import datetime
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1


k,x=input2()

if 500*k>=x:
	print("Yes")
else:
	print("No")






Measured memory_bytes: 19560
#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main()
{
    int a,b;
    cin>>a>>b;

    int g=__gcd(a,b);
    set<int>s;
    int ans=0;
    for (int i = 2; i*i <=g ; ++i) {
        if(g%i==0)
        {
            ans++;
            while (g%i==0)
            {
                g/=i;
            }
        }
    }
    if(g!=1)
        ans++;
    cout<<ans+1;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;


int main()
{
	int N;
	cin>>N;
	int *d = new int[N];
	for(int i = 0; i < N; i++){
		cin>>d[i];
	}
	sort(d,d + N);
	int left,right;
	left = d[(N/2)-1];
	right = d[(N/2)];
	int ans = max(0,right-left);
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 640
n=int(input())
city=[]
for i in range(n):
  l = list(map(lambda x: int(x),input().split()))
  #print(l)
  city.append(l)
  
#print(city)

dist=0
for i in range(n):
  for j in range(i,n):
    #print(l[i])
    dist += ((city[i][0]-city[j][0])**2+(city[i][1]-city[j][1])**2)**0.5
    #print(dist)

x = n*(n-1)/2

def fac(n):
  if n==1:
    return 1
  else:
    return n*fac(n-1)

#print(1-2/(n*(n-1)))

if x==1:
  print(dist)
else:
  print(dist*2/n)


    
  

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
1 2 2 2 9 3 0 4 8 9 
左にあわせてとりゃいいきがする
あれ、違った。
1 2 1
2
1 10 10 10 1
1 0 0 0 1になるか。だめだ
9 2 2 2 1
*/
int main(){
  ll N, ans=0; cin>>N;
  vector<ll> Z(N,0);
  for(int i=0; i<N; i++){
    ll A; cin>>A;
    Z[i]=A;
  }
  for(int i=0; i<N-1; i++){
    if(Z[i]<=Z[i+1]){
      ans+=Z[i];
      Z[i+1]-=Z[i];
      Z[i]=0;
    }
    else if(Z[i]>Z[i+1]){
      ans+=Z[i]/2;
      if(Z[i]%2==1){
        Z[i]=1;
        if(Z[i+1]>=1){
          ans++;
          Z[i]=0;
          Z[i+1]--;
        }
      }
      else Z[i]=0;
    }
//    cout<<"i:"<<i<<" ans:"<<ans<<endl;
  }
  ans+=Z[N-1]/2;
  cout<<ans<<endl;
}

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

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


int main()
{
  A();
  return 0;
}

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

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) reps(i,0,((n)+1))
#define repst(i,s,n) reps(i,s,((n)+1))
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (i==n-1?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ');}}

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

ll n, k, a[5050], s, r;

signed main() {
	cin >> n >> k;
	rep(i,n) cin >> a[i];
	sort(a,a+n);
	r = n;
	repr(i,n-1) {
		if (s+a[i]<k) s += a[i];
		else r = i;
	}
	cout << r << ln;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
ll amari=998244353LL;


void solve(){
    ll n;
    cin>>n;
    vector<ll>d(n);
    map<ll,ll>mp;
    rep(i,n){
        cin>>d[i];
        mp[d[i]]++;
    }
    ll ans=1;
    ll cnt=0;
    if(d.front()!=0){
        cout<<0<<"\n";
        return;
    }
    for(auto x:mp){
        if(x.first!=cnt){
            cout<<0<<"\n";
            return;
        }
        if(x.first==0){
            if(x.second>1){
                cout<<0<<"\n";
                return;
            }
        }
        if(x.first>0){
            for(ll i=0;i<mp[x.first];++i){
                ans*=mp[x.first-1];
                ans%=amari;
            }
        }
        ++cnt;
    }
    cout<<ans<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}

Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 50;
int n, k, ans;
 
int main() {
	
	cin >> n >> k;
	
	int x;
	for(int i = 1; i <= n; i++) {
		cin >> x;
		if(k - x < x) {
			ans += (k-x)*2;
		}else ans += 2*x;
	}
	cout << ans << endl;
	return 0;
} 


Measured memory_bytes: 3220
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

    long long int q;
    cin >> q;
    vector<long long int> b;
    vector<long long int> c;
    for (int i = 0; i < q; i++) {
        cin >> temp;
        b.push_back(temp);
        cin >> temp;
        c.push_back(temp);
    }

    for (int i = 0; i < q; i++) {
        ans += a[b[i]] * (c[i] - b[i]);
        cout << ans ;
        if (i != q - 1)cout << "\n";
        a[c[i]] += a[b[i]];
        a[b[i]] = 0;
    }



    return 0;
}

Measured memory_bytes: 5808
#include<stdio.h>

int main(void)
{
    int a,b,t,x=0,n;
    scanf("%d %d %d",&a,&b,&t);
    if(t>=a)
    {
        for(n=1;n<=t;n++)
        {
            if(t>=a*n)
            {
                x+=b;
            }
        }
    }
    else
    {
        x=0;
    }
    printf("%d",x);
    return 0;
}

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

#define MOD 1000000007

template<typename T>
T power(T a, T b)
{
    T res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

using namespace std;

int main()
{
    long N;
    long A[100001];
    map<long, long> count;

    cin >> N;
    for(long i = 1; i <= N; ++i) {
        cin >> A[i];
        count[A[i]]++;
    }

    if(N % 2 == 1) {
        if(count[0] != 1) goto fail;
        for(long i = 1; i < N; i++) {
            if(i % 2 == 1) {
                if(count[i] != 0) goto fail;
            }
            else {
                if(count[i] != 2) goto fail;
            }
        }
    }
    else {
        for(long i = 0; i < N; ++i) {
            if(i % 2 == 1) {
                if(count[i] != 2) goto fail;
            }
            else {
                if(count[i] != 0) goto fail;
            }
        }
    }

    cout << (N % 2 == 1 ? power(long(2), (N-1)/2) : power(long(2), (N/2))) << endl;
    return 0;

fail:
    cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 7296
#include<stdio.h>

int main(void)
{
	int n,s=0,n2;
	scanf("%d",&n);
	n2=n;
	while(n2!=0){
		s+=n2%10;
		n2=n2/10;
	}
	if(n%s==0)
		printf("Yes");
	else
		printf("No");
	return 0;
}

Measured memory_bytes: 128
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    long[] ts, xs, ys;
    foreach (_; 0..N) {
        auto txy = readln.split.to!(long[]);
        ts ~= txy[0];
        xs ~= txy[1];
        ys ~= txy[2];
    }

    long t, x, y;
    foreach (i; 0..N) {
        auto d = ts[i] - t;
        auto dd = abs(xs[i]-x) + abs(ys[i]-y);
        if (dd > d || (d-dd)%2 != 0) {
            writeln("No");
            return;
        }
        t = ts[i];
        x = xs[i];
        y = ys[i];
    }
    writeln("Yes");
}

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

int main(void)
{
    set<int> aSet;
    int number; 
    for (int i = 0; i < 3; i++)
    {
        cin >> number;
        aSet.insert(number);
    }
    cout << aSet.size() << endl;
    

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;

int main() {
    vector<string> s={"Sunny","Cloudy","Rainy"};
    string ss;
    cin >> ss;
    rep(i,3){
        if (s.at(i)==ss) cout << s.at((i+1)%3) << endl;
    }
}


Measured memory_bytes: 256
use proconio::{fastout, input, marker::Bytes};
use std::cmp;

#[fastout]
fn main() {
    input! {
        _: usize,
        cs: Bytes,
    }

    let nr = cs.iter().filter(|&&c| c == b'R').count();
    let nw = cs.iter().filter(|&&c| c == b'W').count();

    let goal = itertools::repeat_n(b'R', nr).chain(itertools::repeat_n(b'W', nw));

    let mut s = 0;
    let mut t = 0;

    for (c1, c2) in itertools::zip(cs, goal) {
        match (c1, c2) {
            (b'W', b'R') => s += 1,
            (b'R', b'W') => t += 1,
            _ => {}
        }
    }

    let ans = s + t - cmp::min(s, t);
    println!("{}", ans);
}


Measured memory_bytes: 2428
n = int(input())

i = 0
while (i < n):
    L = map(int, raw_input().split())
    L.sort(reverse = True)

    if (pow(L[0], 2) == pow(L[1], 2) + pow(L[2], 2)):
        print "YES"
    else:
        print "NO"

    i += 1

Measured memory_bytes: 4212
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	ll x, y;
	cin >> x >> y;
	if(abs(x - y) <= 1) cout << "Brown" << endl;
	else cout << "Alice" << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    set<int> curr;
    for(int i = 1; i <= n; i++) curr.insert(i);
    while(k--) {
        int d; cin >> d;
        for(int i = 0; i < d; i++) {
            int x; cin >> x;
            curr.erase(x);
        }
    }
    cout << curr.size() << "\n";

    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int mod=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,s;cin >> n >> s;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    ll dp[n+1][s+1][3]={};
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=s;j++){
            (dp[i+1][j][0]+=dp[i][j][0])%=mod;
            (dp[i+1][j][1]+=dp[i][j][0]+dp[i][j][1])%=mod;
            (dp[i+1][j][2]+=dp[i][j][0]+dp[i][j][1]+dp[i][j][2])%=mod;
            if(j+a[i]<=s){
                (dp[i+1][j+a[i]][1]+=dp[i][j][0]+dp[i][j][1])%=mod;
                (dp[i+1][j+a[i]][2]+=dp[i][j][0]+dp[i][j][1])%=mod;
            }
        }
    }
    cout << dp[n][s][2] << endl;
}

Measured memory_bytes: 211328
#pragma GCC optimize "-O3"
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 

#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int N = 2001;

using bb = bitset<N>;

int n, m;

vector<int> eds[N];


queue<pair<int, int>> qu;
int Was[N][N];

bb cn[N];

void add(int x, int y) {
	if (x > y)
		swap(x, y);
	if (Was[x][y])
		return;
	cn[x][y] = cn[y][x] = 1;
	Was[x][y] = 1;
	qu.emplace(x, y);
}

bb st[N];
bb pt[N];
int tin[N];
int tout[N];
int tm1;

int is_p(int a, int b) {
	return tin[a] <= tin[b] && tin[b] < tout[a];
}
int pp[N];

vector<int> sst;
int sj[N][N];

void dfs1(int v, int p) {
	sst.push_back(v);
	for (int i = 0; i + 1 < sst.size(); ++i)
		sj[sst[i]][v] = sst[i + 1];

	tin[v] = tm1++;
	if (p != -1)
		pt[v] = pt[p];
	pp[v] = p;
	pt[v][v] = 1;
	st[v][v] = 1;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		dfs1(u, v);
		st[v] |= st[u];
	}
	tout[v] = tm1;
	sst.pop_back();
}

int lca[N][N];

void findlca(int x, int y) {
	if (is_p(x, y)) {
		lca[x][y] = x;
		return;
	}
	if (is_p(y, x)) {
		lca[x][y] = y;
		return;
	}
	findlca(pp[x], y);
	lca[x][y] = lca[pp[x]][y];
}

bb path, opt;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	for (int i = 0; i < n; ++i)
		cn[i][i] = 1;
	dfs1(0, -1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		add(a, b);
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			lca[i][j] = -1;
	}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (lca[i][j] == -1)
				findlca(i, j);
	int ans = 0;
	while (!qu.empty()) {
		++ans;
		int a, b;
		tie(a, b) = qu.front();
		qu.pop();
		path.reset();
		if (is_p(b, a))
			swap(a, b);
		if (is_p(a, b)) {
			path = st[b] | pt[b] | ~st[sj[a][b]];
		}
		else {
			int x = lca[a][b];
			path = st[a] | st[b] | (pt[a] ^ pt[b]);
			path[x] = 1;
		}
		opt = (cn[a] ^ cn[b]) & path;
		int x = opt._Find_first();
		while (x < n && x >= 0) {
			add(x, a);
			add(x, b);
			x = opt._Find_next(x);
		}
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 64692
n ,c = map(int,input().split())
wt =[]; val=[]
wt.append(0);val.append(0)
for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][V+1] = 0 
INF = 10 **10
max_val = sum(val)
dp = [[INF for i in range(max_val+1)]for j in range(n+1)]

for i in range(n+1):
  dp[i][0]=0
  

for i in range(1,n+1):
  wi = wt[i];vi = val[i]
  for V in range(1,max_val+1):
    if vi<=V:
      dp[i][V] = min(wi+dp[i-1][V-vi] , dp[i-1][V])
    else:
      dp[i][V] = dp[i-1][V]
      
res = 0
for i in range(max_val+1):
  if dp[n][i] <= c:
    res = i
    
print(res)


  
  
  
  


Measured memory_bytes: 171372
#define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto&& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto&& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<int> a(n); std::cin>>a;
  std::sort(all(a));
  int K = a.back();
  int max = 0, k = 0;
  for (int y : a) {
    if (cmx(max, std::min(y,K-y))) {
      k = y;
    }
  }
  std::cout << K << " " << k << std::endl;
  return 0;
}

/*
binom(n,k) は、n に関して単調増加です。
なので、n は最大のもので、k は min(k,n/2-k) が最大になるものです。
*/

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<int>a(3);
  for(int i=0;i<3;i++){
    cin >> a.at(i);
  }
  swap(a.at(0),a.at(1));
  swap(a.at(0),a.at(2));
  cout << a.at(0) << " " << a.at(1) << " " << a.at(2) << endl;    
}

Measured memory_bytes: 256
A, B, C, D = gets.chomp.chars.map(&:to_i)
op = ['+', '-']
(0..1).each do |aop|
  ab = aop == 0 ? A + B : A - B
  (0..1).each do |bop|
    abc = bop == 0 ? ab + C : ab - C
    (0..1).each do |cop|
      abcd = cop == 0 ? abc + D : abc - D
      if abcd == 7
        puts "#{A}#{op[aop]}#{B}#{op[bop]}#{C}#{op[cop]}#{D}=7"
        exit
      end
    end
  end
end


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

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
#define fcout cout<<fixed<<setprecision(10)
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
//template<typename T>void pp(T x){cout<<x<<endl;}

using namespace std;

int main(){
    int n,k;
    while(cin>>n>>k&&n&&k){
        vector<int> v(n+1,0);
        rep(i,0,n){
            cin>>v[i+1];
            if(i)v[i+1]+=v[i];
        }

        int ans=0;
        rep(i,k+1,n+1){
            ans=max(ans,v[i]-v[i-k]);
        }
        cout<<ans<<endl;
    }

    
    return 0;
}


Measured memory_bytes: 3104
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    final Scanner scanner = new Scanner(System.in);
    final int n = scanner.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
    Arrays.sort(a);
    List<Comb> combs = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      int r = upperBound(a, a[i] / 2);
      if (r >= 0) {
        if (r + 1 < i && Math.abs(a[r + 1] * 2 - a[i]) < Math.abs(a[r] * 2 - a[i])) combs.add(new Comb(a[i], a[r + 1]));
        else combs.add(new Comb(a[i], a[r]));
      }
    }
    combs.sort((c1, c2) -> {
      if (c1.n < c2.n && c1.r < c2.r) return -1;
      if (c1.n > c2.n && c1.r > c2.r) return 1;
      if (c1.r == c2.r) return c1.n - c2.n;
      throw new IllegalStateException();
    });
    Comb largest = combs.get(combs.size() - 1);
    System.out.printf("%d %d\n", largest.n, largest.r);
  }

  public static int upperBound(int[] a, int k) {
    int left = -1;
    int right = a.length;
    while (right - left > 1) {
      int mid = (left + right) / 2;
      if (a[mid] <= k) {
        left = mid;
      } else {
        right = mid;
      }
    }
    return left;
  }

  private static class Comb {
    private final int n;
    private final int r;

    private Comb(int n, int r) {
      this.n = n;
      this.r = r;
    }

    @Override public String toString() {
      return "Comb{" +
          "n=" + n +
          ", r=" + r +
          '}';
    }
  }
}


Measured memory_bytes: 53924
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <tuple>
//#include <functional>
#include <cstring>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i <= n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i <= n; i++)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<double> v_double;
typedef std::vector<std::vector<double> > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<std::vector<bool> > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

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

using namespace std;

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) { 
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
        n >>= 1;
    }
    return res;
}

ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

ll nCr(ll n, ll r, ll mod) 
{
    ll x = 1, y = 1;
    
    lrep(i, r) {
        x *= n-i;
        x %= mod;

        y *= i+1;
        y %= mod;
    }

    ll rtn = (x * modinv(y, mod)) % mod;
    return rtn;
}

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    
    ll ans = modpow(2,n,IMOD)-1;

    ans -= nCr(n,a,IMOD);
    ans %= IMOD;
    ans -= nCr(n,b,IMOD);
    ans %= IMOD;

    if(ans < 0) { 
        ans += IMOD;
    }

    cout << ans << endl;

    return 0;
}
/** atcoder **/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
const ll INF = ll(1e18);
const int MOD = 998244353;

const int MAXN = 100005;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	string s; cin>>s;
	cout<<s.substr(0,3)<<'\n';
	
	return 0;
}


Measured memory_bytes: 3652
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>

using namespace std;
typedef long long ll;
typedef pair<int, int> p_ii;

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;

int f(int x){
    int sum = 0;
    while(x!=0){
        sum+=x%10;
        x/=10;
    }
    return sum;
}

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

    if(N%f(N)==0)puts("Yes");
    else puts("No");

    return 0;
}

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

char dp[1 << 24];
int main() {
    int n;
    while (cin >> n, n) {
        memset(dp, -1, sizeof(dp));
        int x[n], y[n], r[n], c[n];
        int b[25] = {};
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i] >> r[i] >> c[i];
            for (int j = 0; j < i; j++) {
                int dx = x[i] - x[j];
                int dy = y[i] - y[j];
                int dr = r[i] + r[j];
                if (dx * dx + dy * dy < dr * dr) {
                    b[i] |= (1 << j);
                }
            }
        }
        int ans = -1;
        dp[0] = 0;
        for (int bit = 0; bit < 1 << n; bit++) {
            if (dp[bit] == -1) continue;
            ans = max(ans, (int)dp[bit]);
            for (int i = 0; i < n; i++) {
                if ((bit >> i & 1) != 0 || (bit & b[i]) != b[i]) continue;
                for (int j = i + 1; j < n; j++) {
                    if ((bit >> j & 1) != 0 || (bit & b[j]) != b[j]) continue;
                    if (c[i] != c[j]) continue;
                    int nx = bit | (1 << i) | (1 << j);
                    dp[nx] = max((int)dp[nx], dp[bit] + 2);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 19488
N = int(input())
T = list(map(int,input().split()))
M = int(input())
d = [list(map(int,input().split())) for i in range(M)]
t = sum(T)
for i in range(len(d)):
    time = t + d[i][1] - T[d[i][0]-1]
    print(time)

Measured memory_bytes: 38256
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans
  print(ans%mod)

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

n,k=map(int,input().split())
a=list(map(int,input().split()))
print(solve(n,k,a))

"""
from random import randint
for i in range(10000):
  n=randint(1,10)
  k=randint(1,n)
  a=sorted([randint(-10,10)for _ in range(n)])
  print(n,k,a)
  ans1=solve(n,k,a)
  ans2=solve2(n,k,a)
  if ans1==ans2:print("ok")
  else:
    print("error")
    print(n,k)
    print(*a)
    print(ans1,ans2)
    exit()
"""

Measured memory_bytes: 109308
using System;

namespace ABC
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            for (var i = 0; i < 25; i++)
            {
                for (var j = 0; j < 15; j++)
                {
                    if ((i * 4) + (j * 7) == N)
                    {
                        Console.WriteLine("Yes");
                        return;
                    }
                }
            }
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>

#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int h[n];
  for (int i = 0; i < n; i++) {
    int cur;
    cin >> cur;
    h[i] = cur;
  }
  int minCosts[n];
  minCosts[0] = 0;
  minCosts[1] = abs(h[1]-h[0]);
  for (int i = 2; i < n; i++) {
    minCosts[i] = min(abs(h[i]-h[i-2])+minCosts[i-2], abs(h[i]-h[i-1])+minCosts[i-1]);
  }
  cout << minCosts[n-1] << "\n";
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define trace(x) {cerr << #x << "=" << x <<endl;}
#define trace2(x, y) {cerr << #x << "=" << x << " " << #y << "=" << y <<endl;}
#define trace3(x, y,z) {cerr << #x << "=" << x << " " << #y << "=" << y <<" " << #z << "=" <<z<<endl;}
/*
template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "[ "; for (T x: p) os << x << " "; os << "]" << endl; return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
template <typename T> ostream& operator<<(ostream& os, const ordered_set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const map<Tk, Tv> &p){os << "{ "; for (pair<Tk, Tv> x: p) os << x << " "; os << "}" << endl; return os;}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const pair<Tk, Tv> &p){os << "{" << p.first << ',' << p.second << "}";return os;}
*/
/*
template<typename It>
class Range
{
    It b,e;
public:
    Range(It b,It e):b(b),e(e) {}
    It begin() const
    {
        return b;
    }
    It end() const
    {
        return e;
    }
};
template<typename ORange,typename OIt=decltype(std::begin(std::declval<ORange>())),typename It=std::reverse_iterator<OIt>>
Range<It>reverse(ORange && originalRange)
{
    return Range<It>(It(std::end(originalRange)),It(std::begin(originalRange)));
}
*/
#define pi pair<int,int>
#define pipi pair<int,pair<int,int> >
#define fi first
#define se second
#define mod 1000000007
#define ll long long
const int MAX=2e5+7;
const int dx4[]= {0,1,0,-1};
const int dy4[]= {1,0,-1,0};
#define inf 10000000000000000LL

int n,a[MAX];
long long sum[MAX],x[MAX];

int func(int i)
{
    int beg=i,last=n,mid,ans=-1;
    while(beg<=last)
    {
        mid=(beg+last)/2;
        if(sum[mid]-sum[i-1]>(x[mid]^x[i-1]))
            last=mid-1;
        else
        {
            beg=mid+1;
            ans=mid;
        }
    }
    assert(ans!=-1);
    return ans;
}

long long func()
{
    for(int i=1; i<=n; i++)
    {
        sum[i]=sum[i-1]+a[i];
        x[i]=x[i-1]^a[i];
    }
    long long ans=0;
    for(int i=1; i<=n; i++)
    {
        int pos=func(i);
        ans+=(pos-i+1);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
  //  freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    cout<<func()<<endl;
    return 0;
}



Measured memory_bytes: 4224
from collections import Counter
N = int(input())
 
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table
 
T = prime_factorization(N)
C = Counter(T)
 
cnt = 0
for v in C.values():
    next = 1
    while v >= next:
        v -= next
        cnt += 1
        next += 1
 
print(cnt)

Measured memory_bytes: 66440
#include<bits/stdc++.h>
using namespace std;
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,k,l,m,n,o,p,q;
    while(cin>>m)
    {cout<<(24-m)+24<<endl;
    }
    return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  int N;
  cin >> N;
  vector<double> vec(N);

  for (int i = 0; i < N; i++) {
    cin >> vec[i];
  }
 
  double ans=0;
  
  for ( int i = 0; i < N; i++){
    ans += 1/vec[i];
  }
  
  cout << 1/ans << endl;
}
    
    

Measured memory_bytes: 256
import math

N = int(input())
P = [list(map(int,input().split())) for i in range(N)]
p = P
r = 0
n = (N*(N-1))/2
s = N * (N -1)

while len(p) != 1:
    for i in range(len(p)-1):
        r = r + math.sqrt(pow((p[0][0]-p[i+1][0]),2) + (pow((p[0][1]-p[i+1][1]),2)))
    p = p[1:len(p)]

print((r*((s*2)/N))/s)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define ll                   long long int
#define ld                   long double
#define scl(n)               scanf("%lld",&n)
#define scd(n)               scanf("%lf",&n)
#define eb                   emplace_back
#define pb                   push_back
#define pf                   push_front
#define ppf                  pop_front
#define ppb                  pop_back
#define pi                   acos(-1.0)
#define mod                  1000000007
#define eps                  0.0000000001
#define inf                  9000000000000000
#define en                   "\n"

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

    ld n, d; cin>>n>>d;
    ll c=0;
    while (n--) {
        ld x, y; cin>>x>>y;
        ld D=sqrt(x*x+y*y);
        if (D<=d) c++;
    }
    cout<<c<<en;

    return 0;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const ll INF = 1LL << 60;


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

    int n = s.size();
    bool flag = true;
    ll sum = 0;
    ll cnt = 1, fcnt = 0;
    for(int i = 0; i < n - 1; i++){
        if(s[i] == s[i + 1]) cnt++;
        else{
            if(flag){
                fcnt = cnt;
                flag = false;
            }else{
                sum += cnt / 2;
            }
            cnt = 1;
        }
    }

    ll sum2 = 0;
    ll ecnt = 0;
    ll bcnt = 0;
    if(s[0] == s[n - 1]){
        sum2 = (fcnt + cnt) / 2;
        bcnt = fcnt / 2;
        ecnt = cnt / 2;
    }else{
        sum += fcnt / 2;
        sum += cnt / 2;
    }

    if(n == cnt) cout << cnt * k / 2 << endl;
    else cout << sum * k + sum2 * (k - 1) + bcnt + ecnt << endl;


    return 0;
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() {
    /*#ifndef ONLINE_JUDGE
      // for getting input from input.txt
      freopen("input.txt", "r", stdin);
      // for writing output to output.txt
      freopen("output.txt", "w", stdout);
  #endif*/
fast();
  ll n,c=0;
  cin>>n;
  string s;
  cin>>s;
  string t=s.substr(0,n/2);
  string tt=s.substr(n/2,s.length());
  if(tt==t)
    Yes
  else
    No
  


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string> 
using namespace std;
int main(){
  int n;
  cin >> n;
  int A[n];
  for(int i = 0; i < n; i++){
    cin >> A[i];
  }
  int i,j,m;
  int ans = 0;
    for(int i = 0; i < n; i++) {
    for(int j = n - 1; j > i; j--) {
      if(A[j] < A[j - 1]) {
        m = A[j];
        A[j] = A[j - 1];
        A[j - 1] = m;
        ans++;
      }
    }
    }
  for(i = 0; i < n; i++){
    cout << A[i];
    if(i < n - 1){
      cout << " ";
    }
  }
  cout << endl;
      cout << ans << endl;
      return 0;
}



Measured memory_bytes: 3084
#include <stdio.h>
#include <string.h>
int main(){
    char data[1100];
    int i = 0;
    fgets(data,sizeof(data),stdin);
    for(i = 1;data[i] != 0;i++){
        if(i >= 4){
            if(data[i-4] == 'a'){
                if(data[i-3] == 'p'){
                    if(data[i-2] == 'p'){
                        if(data[i-1] == 'l'){
                            if(data[i] == 'e'){
                                data[i-4] = 'p';
                                data[i-3] = 'e';
                                data[i-2] = 'a';
                                data[i-1] = 'c';
                                data[i] = 'h';
                                continue;
                            }
                        }
                    }
                }
            }
        }
        if(i >= 4){
            if(data[i-4] == 'p'){
                if(data[i-3] == 'e'){
                    if(data[i-2] == 'a'){
                        if(data[i-1] == 'c'){
                            if(data[i] == 'h'){
                                data[i-4] = 'a';
                                data[i-3] = 'p';
                                data[i-2] = 'p';
                                data[i-1] = 'l';
                                data[i] = 'e';
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%s",data);
    return 0;
}

Measured memory_bytes: 520
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int d = sc.nextInt();
		int a = sc.nextInt();
		
		Monster[] m = new Monster[n];
		for(int i=0;i<n;i++) {
			int x = sc.nextInt();
			int h = sc.nextInt();
			int t = (int)Math.ceil((double)h/a);
			m[i] = new Monster(x, t);
		}
		
		Arrays.sort(m, new Comparator<Monster>() {

			@Override
			public int compare(Monster o1, Monster o2) {
				if(o1.x>o2.x)
					return 1;
				else if(o1.x==o2.x)
					return 0;
				else
					return -1;
			}
			
		});
		
		int[] attack = new int[n];
		int l = 0, r = 1;
		while(l<n && r<n) {
			if(m[r].x - m[l].x <= 2*d) {
				r++;
			}
			else {
				attack[l] = r-1;
				l++;
			}
		}
		for(int i=l;i<n;i++) {
			attack[i] = r-1;
		}
		
		
		int[] reduce = new int[n+1];
		int sum = 0;
		long time = 0;
		for(int i=0;i<n;i++) {
			sum += reduce[i];
			int t = m[i].t + sum;
			if(t>0) {
				time += t;
				sum -= t;
				reduce[i] -= t;
				reduce[attack[i]+1] += t;
			}
		}
		
		System.out.println(time);
	}
}
class Monster{
	int x, t;
	Monster(int x, int t){
		this.x = x;
		this.t = t;
	}
}

Measured memory_bytes: 111112
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>
#include <iterator>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define dprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define dprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

//const double PI = 3.1415926535897932384626433832795;

int main() {
  LL r;
  cin >> r;

  cout << 3 * r * r << '\n';
  return 0;
}


Measured memory_bytes: 256