akhauriyash/Code-Regression huggingface dataset:
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        friends_chain.unite(a, b)
        friend_or_block[a] += 1
        friend_or_block[b] += 1

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

    def same(self, x, y): return self.root(x) == self.root(y)

    def count(self, x): return -self.parent[self.root(x)]

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()



Measured memory_bytes: 13420
import math
nd = input().split()
n = int(nd[0])
d = int(nd[1])

x = []
for i in range(n):
  x.append([])
  _x = input().split()
  for y in _x:
    x[i].append(int(y))

ans = 0
for i in range(n):
  for j in range(i+1, n):
    s = 0
    for k in range(d):
      s += (x[i][k]-x[j][k])**2
    distance = math.sqrt(s)
    if distance%1==0:
      ans += 1

print(ans)

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

int main(){
	int H,W;
    cin >> H >> W;
    char a[H][W];
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        cin >> a[i][j];
      }
    }
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        cout << a[i][j];
      }
      cout << endl;
      for(int j=0;j<W;j++){
        cout << a[i][j];
      }
      cout << endl;
    }    
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;
const long long MOD = (long long)1e9 + 7;

int main(){
    int n, x, y, ans = 0;
    cin >> n >> x >> y;
    vector<vector<int>> e(n);
    for(int i = 0; i < n - 1; i++){
        e[i].push_back(i + 1);
        e[i + 1].push_back(i);
    }
    x--; y--;
    e[x].push_back(y);
    e[y].push_back(x);
    vector<vector<int>> d(n, vector<int>(n, INF));
    for(int i = 0; i < n; i++){
        d[i][i] = 0;
    }
    for(int i = 0; i < n; i++){
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            for(auto&& j : e[t]){
                if(d[i][j] > d[i][t] + 1){
                    d[i][j] = d[i][t] + 1;
                    q.push(j);
                }
            }
        }
    }
    map<int, int> m;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            m[d[i][j]]++;
        }
    }
    for(int i = 1; i < n; i++){
        cout << m[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 16128
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1ll<<40;
const double EPS = 1e-8;
const int MOD = 1000000007;


int n, A, B;
ll r[200], s[200];
ll sum[200];

int solve(int player, int i, ll nut);

int dfs(int player, int i, ll nut){
	if(i == n) return 0;
	int res = s[i] + sum[n] - sum[i+1] - solve(!player, i+1, -(nut + r[i]));
	if(nut > 0) res = max(res, solve(player, i+1, (nut - r[i] - 1)));
	return res;
}

map<ll, int> memo[2][200];

void fillTable(int player, int i){
	map<ll, int> &tar = memo[player][i];
	int low = tar[-INF] = dfs(player, i, -INF/2);
	int hi = tar[INF] = dfs(player, i, INF/2)+1;
	for(int j=low+1;j<hi;j++){
		ll l=-INF, r = INF;
		while(l<r-1){
			ll med = (l+r)/2;
			if(dfs(player, i, med) < j) l = med;
			else r = med;
		}
		j = tar[r] = dfs(player, i, r);
	}
}

int solve(int player, int i, ll nut){
	if(i == n) return 0;
	if(memo[player][i].empty()) fillTable(player, i);
	auto it = (memo[player][i].upper_bound(nut));
	return (--it)->second;
}

main(){
	ios::sync_with_stdio(false);
	cin >> n >> A >> B;
	REP(i, n){
		cin >> r[i] >> s[i];
		sum[i+1] = sum[i] + s[i];
	}
	int res = solve(0, 0, A-B);
	cout << res << " " << sum[n] - res << endl;
	return 0;
}

Measured memory_bytes: 1436
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
    x=parseInt(readline())
    i=1
    while true
        if div(i*(i+1),2)>=x
            break
        end
        i+=1
    end
    println(i)
end
main()

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

int main(void){
  int n,team1,team2,Point[101],po1,po2,cnt;

  for( int i = 0 ; i < 101 ; i++ ) Point[i] = 0;
  
  cin >> n;
  for( int i = 0; i < n*(n-1)/2 ; i++ ){

      cin >> team1 >> team2 >> po1 >> po2;
      if( po1 > po2 ) Point[team1] += 3;
      else if( po1 < po2 ) Point[team2] += 3;
      else{
	Point[team1]++; Point[team2]++;
      }
      }

  for( int i = 1 ; i <= n ; i++ ){
    cnt = 1;
    for( int j = 1 ; j <= n ; j++ ){
      if( Point[i] < Point[j] ) cnt++;
    }
    cout << cnt << endl;
  }
 
  return 0;
}

Measured memory_bytes: 1160
import java.util.Scanner;
public class Main {

    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// 入力
    	String s = sc.next();
    	String[] ary = s.split("", 0);
    	StringBuilder ans = new StringBuilder();

    	for(int i = 0; i < ary.length; i++){
    		if (i % 2 == 1){
    			continue;
    		}
    		ans.append(ary[i]);
    	}
    	// 出力
    	System.out.println(ans);
    }
}

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

int main(){
  long long int n,t1,t2,a1,a2,b1,b2,sa1,sa2,kotae;
  cin>>t1>>t2>>a1>>a2>>b1>>b2;
  sa1=a1*t1-b1*t1;
  sa2=a2*t2-b2*t2+sa1;
  if(sa1>0&&sa2>0){
    cout<<0;
    return 0;
  }
  if(sa1<0&&sa2<0){
    cout<<0;
    return 0;
  }
  if(sa2==0){
    cout<<"infinity";
    return 0;
  }
  sa1=abs(sa1);
  sa2=abs(sa2);
  kotae=sa1/sa2*2+1;
  if(sa1%sa2==0){
    kotae--;
  }
  cout<<kotae;
}


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

const ll MOD=1000000007;

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear1(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p){
  ll n=solveLinear1(a,p,1);
  n=n%p;
  if(n<0)return n+p;
  return n;
}

ll L[51];
ll a[51];

ll patty(ll x,int n){
  if(x<=0)return 0;
  if(n==0)return 1;
  if(x>=L[n])return a[n];
  ll cnt=patty(x-1,n-1)+patty(x-2-L[n-1],n-1);
  if(x>L[n-1]+1)cnt++;
  return cnt;
}

int main(){
  int i,j,k;ll cnt=0;
  int n;
  cin>>n;
  int a[n],b[n],c[n];
  for(i=0;i<n;i++)cin>>a[i];
  for(i=0;i<n;i++)cin>>b[i];
  for(i=0;i<n;i++)cin>>c[i];
  sort(a,a+n);
  sort(b,b+n);
  sort(c,c+n);
  int left=0;
  int p[n];
  for(i=0;i<n;i++)p[i]=0;
  for(i=0;i<n;i++){
    while(n>left && b[i]>=c[left])left++;
    if(left==n)break;
    p[i]=n-left;
  }
  ll s[n+1];
  s[n]=0;
  for(i=n-1;i>=0;i--)s[i]=s[i+1]+p[i];
  left=0;
  for(i=0;i<n;i++){
    while(n>left && a[i]>=b[left])left++;
    if(left==n)break;
    cnt+=s[left];
  }
  cout<<cnt;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<1)+(s<<3)+(c^48);c=getchar();
	}
	return f*s;
}
map<string,bool>q;
int main(){
	int T=read(),ans=0;
	while(T--){
		string a;cin>>a;
		if(!q[a]){
			q[a]=true;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 19256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 5e36+7;
int mod = 998244353;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        cnt += (S[i] == 'I')?1:-1;
        ans = max(ans,cnt);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define pob pop_back
#define vi vector<ll>
#define mp make_pair
#define sz size()
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define rep(i,n) for(ll i=0;i<n;i++)
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define maxx 10005
#define se second
#define fi first
#define sortv(v) sort(v.begin(),v.end());
#define w() ll _;cin>>_;while(_--)
#define edge pair<ll,ll>
#define pq priority_queue<ll>
#define M 10000007
#define Endl "\n"
using namespace std;



int main()
{
	fast;
	
	ll x,y;
	cin>>x>>y;
	ll i;
	ll k=x*4;
	ll  j=x*2;
	y-=j;
	
	if(y%2==0 && y<=j && y>=0)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	
	

}

Measured memory_bytes: 3632
/*input
2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

*/

#include <bits/stdc++.h>


using namespace std;

#define ll long long





int main() {
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    ll p[a],q[b],r[c];
    vector<ll> v;
    for( ll i=0;i<a;i++)cin>>p[i];
    for( ll i=0;i<b;i++)cin>>q[i];
    for( ll i=0;i<c;i++)cin>>r[i];
    sort(p,p+a,greater<ll>());
    sort(q,q+b,greater<ll>());
    //reverse(v.begin(),v.end());
    for( ll i=0;i<x;i++)v.push_back(p[i]);
    for( ll i=0;i<y;i++)v.push_back(q[i]);
    for(ll i=0;i<c;i++)v.push_back(r[i]);
    sort(v.begin(),v.end(),greater<ll>());
    ll ans=0;
    for(ll i=0;i<x+y;i++){
        ll val = v[i];
        //cout<<val<<" ";
        ans+=val;
        
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8816
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
  ll A, B, K;
  cin >> A >> B >> K;
  if(B - A + 1 < 2 * K) {
    for(ll i = A; i <= B; i++) {
      cout << i << endl;
    }
  }
  else {
    for(ll i = 0; i < K; i++) {
      cout << A + i << endl;
    }
    for(ll i = K - 1; i >= 0; i--) {
      cout << B - i << endl;
    }
  }
}

Measured memory_bytes: 3636
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (value-a 0)
         (value-b 0)
         (value-c 0))
    (declare (uint31 n value-a value-b value-c))
    (dotimes (_ n)
      (let ((a (read-fixnum))
            (b (read-fixnum))
            (c (read-fixnum)))
        (psetq value-a (+ a (max value-b value-c))
               value-b (+ b (max value-c value-a))
               value-c (+ c (max value-a value-b)))))
    (println (max value-a value-b value-c))))

#-swank (main)


Measured memory_bytes: 8552
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,count=0;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
		if(i/10000==i%10&&i/1000%10==i/10%10)count++;
	}
	cout<<count<<endl;
}


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

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

    li x; cin >> x;

    for (li i=1000; i>=(-1000); i--) {
        for (li j=1000; j>=(-1000); j--) {
            if (x == (pow(i,5) - pow(j,5))){
                cout << i << " " << j << "\n";
                return 0;
            }
        }
    }
}

Measured memory_bytes: 4132
#include<bits/stdc++.h>
#define REP(i,n)    for(int i = 0; i < (n); ++i)
#define RREP(i,n)   for(int i = (n); i >= 0; --i)
#define FOR(i,m,n) for(int i = (m); i < (n); ++i)
#define SZ(x)       ( (int)(x).size() )
#define BIT(n)      ( 1LL << (n) )
#define EXIST(x)    ( (x).find()		!= (x).end() )
#define DEBUG(n)    cerr << #n << " : " << n << '\n';
#define PB  push_back
#define UB  upper_bound			//k <
#define LB  lower_bound			//k	<= 
#define F   first
#define S   second
#define INF 1.0e9


using namespace std;

typedef long long			ll;
typedef pair<int, int>		pii;
typedef pair<long			long, long long>   pll;
typedef vector<int>			vi;
typedef vector<double>		vd;
typedef vector<long long>   vll;

template<class T> void chmax(T &	a, const T & b){ if( a < b ) a = b; }
template<class T> void chmin(T &	a, const T & b){ if( a > b ) a = b; }

int r_up(const int a, const int b){ return (a + b - 1) / b; }

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

int n,k;

long long getCount(int a){
  int c = 0;
  while(a < k){
	a *= 2;
	c++;
  }
  return c;
}

int main(){
  cin>>n>>k;
  double p = 0;
  for(int i = 1; i <= n; ++i){
	p += (1.0/n) * pow(0.5,getCount(i));
  }
  cout<<setprecision(10)<<p<<endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define el '\n'

int main() {
  int n, l;
  cin >> n >> l;
  int sum = 0, mn = INT_MAX, idx;
  for (int i = 0; i < n; i++) {
    sum += l+i;
    if (abs(l+i) < mn) {
      mn = abs(l+i);
      idx = i;
    }
  }
  cout << sum-(l+idx) << el;
  return 0;
}

Measured memory_bytes: 256
var lines =[];


var readline = require("readline");
var rl = readline.createInterface({
  input:  process.stdin,
  output: process.stdout
});

rl.on('line',function(x){
  lines.push(x);
});

rl.on('close',function(){

  var tmp = lines[0].split(" ");
  
  var a = Number(tmp[0]);
  var b = Number(tmp[1]);
  var c = Number(tmp[2]);
  
  if(b/a>=c){console.log(c);}
  else{console.log(Math.floor(b/a));}
});

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

int main(int argc, const char * argv[]) {
    vector<int> sum;
    int A, B, C; cin >> A >> B >> C;
    
    sum.push_back(10 * A + B + C);
    sum.push_back(10 * A + C + B);
    sum.push_back(10 * B + C + A);
    sum.push_back(10 * B + A + C);
    sum.push_back(10 * C + A + B);
    sum.push_back(10 * C + B + A);
    
    sort(sum.begin(), sum.end());
    reverse(sum.begin(), sum.end());
    
    cout << sum[0] << endl;

    return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

double minSpanningTree(const vector<vector<double> >& graph)
{
    int n = graph.size();
    vector<bool> used(n, false);
    int usedNum = 0;
    vector<double> minCost(n, DBL_MAX);
    priority_queue<pair<double,int> ,vector<pair<double,int> >, greater<pair<double,int> > > q;
    q.push(make_pair(0, 0));

    double ret = 0;
    while(!q.empty()){
        pair<double, int> p = q.top();
        q.pop();
        int v = p.second;
        if(used[v])
            continue;
        ret += p.first;
        used[v] = true;
        if(++usedNum == n)
            return ret;
        for(int i=0; i<n; ++i){
            if(!used[i] && graph[v][i] >= 0 && graph[v][i] < minCost[i]){
                minCost[i] = graph[v][i];
                q.push(make_pair(graph[v][i], i));
            }
        }
    }
    return -1;
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<double> x(n), y(n), z(n), r(n);
        for(int i=0; i<n; ++i)
            cin >> x[i] >> y[i] >> z[i] >> r[i];

        vector<vector<double> > dist(n, vector<double>(n));
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                dist[i][j] = sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0) + pow(z[i]-z[j], 2.0));
                dist[i][j] -= r[i] + r[j];
                dist[i][j] = max(dist[i][j], 0.0);
            }
        }

        double ret = minSpanningTree(dist);
        printf("%.3f\n", ret);
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)

struct Graph {
  vector<vector<int>> edge;
  Graph(int n = 0) { resize(n); }
  void resize(int n) { edge.resize(n); }
  void addEdge(int from, int to) {
    edge[from].push_back(to); edge[to].push_back(from);
  }
  vector<int>& operator[](int from) { return edge[from]; }
};

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

  Graph G(N);
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    G.addEdge(a, b);
  }

  vector<int> before(N, 1e6); before[0] = -1;
  queue<int> q; q.push(0);

  while (!q.empty()) {
    int from = q.front(); q.pop();
    for (auto& to:G[from]) {
      if (before[to] != 1e6)
        continue;
      before[to] = from;
      q.push(to);
    }
  }

  cout << "Yes\n";
  rep(i, N-1)
    cout << before[i+1] + 1 << endl;

  return 0;
}


Measured memory_bytes: 10188
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>


using namespace std;
typedef long long ll;

ll N;
ll M;
vector<vector<ll> > G;
vector<ll > dp;

ll dfs(ll n){

    if(dp[n] > 0){
        return dp[n];
    }

    ll mx = 0;
    
    for(ll i = 0; i < G[n].size(); i++){
        mx = max(mx, dfs(G[n][i]) + 1);
        //cout << n << "," << i << endl;
        //if(G[n][i] == 1){
            //cout << n << "," << i << endl;
        //    mx = max(mx, dfs(i) + 1);
        //}      
    }

    dp[n] = mx;
    return dp[n];
}

int main(){

    cin >> N;
    cin >> M;

    G = vector<vector<ll> >(N);
    dp = vector<ll > (N , 0);

    ll x = 0, y = 0;
    for(ll i = 0; i < M; i++){
        cin >> x >> y;
        G[x-1].push_back(y-1);
        //G[x - 1][y - 1] = 1;
    }

    //確認
    /*
    for(ll i = 0; i < N; i++){
        for(ll j = 0; j < N; j++){
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
    */

    ll ans = 0;
    for(ll i = 0; i < N; i++){
        //cout << "ウェイ" <<  "," << i << endl;
        if(dp[i] == 0){
            ans = max(ans, dfs(i));
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 8576
def is_ok(X):
    cnt = 0
    for a in A:
        cnt += -(-a//X)-1
    if cnt <= k:
        return True
    else:
        return False


def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n, k = map(int,input().split())
A = list(map(int,input().split()))

print(meguru_bisect(0,max(A)+1))

Measured memory_bytes: 104088
n = int(input())
count = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == b:
        count += 1
    else:
        if count >= 3:
            print("Yes")
            exit()
        count = 0
if count >= 3:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9080
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }
#define int ll


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

    int h,n;cin>>h>>n;
    vector<ll> dam(n),cost(n);
    rep(i,n){
        cin>>dam[i]>>cost[i];
    }
    ll hmax=10010;
    ll dp[hmax*2];
    rep(i,hmax*2){
        dp[i]=LINF;
    }
    dp[0]=0;
    rep(i,n){
        rep(j,hmax){
            chmin(dp[j+dam[i]],dp[j]+cost[i]);
        }
    }
    ll ans=LINF;
    for(int i=h;i<hmax;i++){
        chmin(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
  int i,j,c=0;
  int N1,N2;
  int A[10000];
  int B[500];

  scanf("%d",&N1);
  for(i=0;i<N1;i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&N2);
  for(i=0;i<N2;i++){
    scanf("%d",&B[i]);
  }

  for(i=0;i<N1;i++){
    for(j=i+1;j<N1;j++){
      if(A[i]==A[j])A[j]=0;
    }
  }

  for(i=0;i<N1;i++){
    if(i!=0&&A[i]==0)continue;
    for(j=0;j<N2;j++){
      if(A[i]==B[j]){
	c++;
      }
    }
  }

  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 408
using System;
class ProgramC
    {
        static void Main(string[] args)
        {
            
            string input = Console.ReadLine();
            long n = long.Parse(input);

            
            string[] input_h = Console.ReadLine().Split(' ');
            long[] h = new long[n];
            for(int i = 0;i < n;i++)
                h[i] = long.Parse(input_h[i]);

            long count = 0;
            long max = 0;

            for(int i = 1;i < n;i++)
            {
                if(h[i] <= h[i-1])
                    count++;
                else
                {
                    if(max < count)
                        max = count;
                    count = 0;
                }

                if(i == n - 1)
                {
                    if(max < count)
                        max = count;
                }

            }

            Console.WriteLine(max);
        }
    }

Measured memory_bytes: 29532
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>

using namespace std;
using ll=long long int;

void dfs(vector<vector<int>> &g, vector<int> &c, vector<int> &ans, int v, int p, int val) {
    ans[v] = val + c[v];
    for (auto u: g[v]) {
        if (p == u) continue;
        dfs(g, c, ans, u, v, ans[v]);
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int> c(n, 0);
    for (int i = 0; i < q; ++i) {
        int p, x;
        cin >> p >> x;
        --p;
        c[p] += x;
    }
    vector<int> ans(n);
    dfs(g, c, ans, 0, -1, 0);

    for (auto e: ans) cout << e << " ";
    cout << endl;

    return 0;
}


Measured memory_bytes: 30464
#include<bits/stdc++.h>
using namespace std;
int dp[100000];
int solve(int h[],int i,int n,int k)
{
	if(i>=(n-1))
	return 0;
	if(dp[i]!=-1)
	return dp[i];
		int ans=INT_MAX;
		for(int j=1;j<=k;j++)
		{
			if(i+j<n)
         ans=min(abs(h[i+j]-h[i])+solve(h,i+j,n,k),ans);
		}
		return dp[i]=ans;
}
int main()
{
	for(int i=0;i<100000;i++)
	{
		dp[i]=-1;
	}
	int n,k;
	cin>>n>>k;
	int h[n];
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	cout<<solve(h,0,n,k);
}

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

using namespace std;

int main()
{
  int A, B, K;
  cin >> A >> B >> K;
  int cnt = 0;
  for (int i = A; 0 < i; i--)
  {
    if (A % i == 0 && B % i == 0)
      cnt++;
    if (cnt == K)
    {
      cout << i << endl;
      break;
    }
  }

  return 0;
}


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

using namespace std;

#define rep(i, a, b) for (int i = (a); i <= (b); i++)

int m, d, ans;

int main() {
  cin >> m >> d;
  rep(i, 1, m) {
    rep(j, 1, d) {
      int d0 = j % 10, d1 = j / 10;
      if (d0 < 2) continue ;
      if (d1 < 2) continue ;
      if (d0 * d1 != i) continue ;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n,m;
  cin>>n>>m;
  cout<<n*(n-1)/2+m*(m-1)/2<<endl;

  return 0;
}




Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String T = sc.nextLine();
        sc.close();
        String[] A = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
        boolean res = true;
        for(String s:A){
            int sIdx = S.indexOf(s);
            if(sIdx < 0) continue;
            String t = String.valueOf(T.charAt(sIdx));
            int idx = 0;
            while(idx < S.length()){
                if(S.indexOf(s, idx) >=0){
                    if(S.indexOf(s, idx) != T.indexOf(t, idx)){
                        res = false;
                        break;
                    }else{
                        idx = S.indexOf(s, idx) + 1;
                    }
                } else if(T.indexOf(t, idx) >=0){
                    res = false;
                    break;
                }
                else break;
            }
            if(!res) break;
        }
        if(res) System.out.println("Yes");
        else System.out.println("No");

    }

}


Measured memory_bytes: 30444
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110;
int n;
int a[MAXN];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    if(a[i]%2==0&&a[i]%3!=0&&a[i]%5!=0)
    {
        cout<<"DENIED"<<endl;
        return 0;
    }
    cout<<"APPROVED"<<endl;
	return 0;
}


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

int main() {
  int N, D;
  cin >> N >> D;
  int X = N / ((2 * D) + 1);
  if(N % ((2 * D) + 1) != 0) cout << X+1 << endl;
    else cout << X << endl;
}

Measured memory_bytes: 256
//
//  main.cpp
//  2
//
//  Created by RISHAV SINGH MEHTA on 09/02/20.
//  Copyright © 2020 RISHAV SINGH MEHTA. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define ll long long
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    ll int T,i,j,k,l,N,a,b,c;
    string S;
    cin>>S;
    for (i=0; i<S.length(); i++) {
        cout<<"x";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int INF = 1 << 30;
typedef pair < int , int > Pi;
int n, m, mas[101][101], hoge[4][51][51];

bool isfind( const int& k, const int& y, const int& x, Pi& exitp)
{
  for(int i = 0 ; i < m ; i++ ){
    for(int j = 0 ; j < m ; j++ ){
      if( hoge[k][i][j] == -1) continue;
      if( mas[i + y][j + x] != hoge[k][i][j]) return false;
      if(exitp == Pi(-1,-1)) exitp = Pi(i + y + 1,j + x + 1);
    }
  }
  return true;
}

Pi solve()
{
  Pi ret = Pi( INF, INF);

  for(int i = 0 ; i <= n - m ; i++ ){
    for(int j = 0 ; j <= n - m ; j++ ){
      for(int k = 0 ; k < 4 ; k++ ){
        Pi p = Pi( -1, -1);
        if(isfind( k, i, j, p)){
          ret = min( ret, p);
        }
      }
    }
  }
  return ret;
}
int main()
{
  while(cin >> n >> m, n){
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j < n ; j++ ){
        cin >> mas[i][j];
      }
    }
    for(int i = 0 ; i < m ; i++ ){
      for(int j = 0 ; j < m ; j++ ){
        cin >> hoge[0][i][j];
      }
    }

    for(int k = 1 ; k < 4 ; k++ ){
      for(int i = 0 ; i < m ; i++ ){
        for(int j = 0 ; j < m ; j++ ){
          hoge[k][j][m - i - 1] = hoge[k - 1][i][j];
        }
      }
    }

    Pi pos = solve();
    if(pos.first == INF) cout << "NA" << endl;
    else cout << pos.second << " " << pos.first << endl;
  }
  return 0;
}

Measured memory_bytes: 1244
n,k = map(int,input().split())
S = input()
p = S[k-1]
if p == 'A':
  print(S[:k-1]+'a'+S[k:])
elif p == 'B':
  print(S[:k-1]+'b'+S[k:])
else:
  print(S[:k-1]+'c'+S[k:])

Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}
func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0
	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 3
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}
	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	xx := make([]int, n)
	for i := 0; i < n; i++ {
		xx[i] = getNextInt(scanner)
	}
	var ans, a mint
	ans = 1
	s := -1
	for i := 0; i < n; i++ {
		a++
		if s+2 <= xx[i] {
			s += 2
			continue
		}
		ans.mulAs(a)
		a--
	}
	for a > 0 {
		ans.mulAs(a)
		a--
	}
	fmt.Fprintln(writer, ans)
}

type mint int64

func (mt mint) mod() mint {
	m := mint(1e9 + 7)
	mt %= m
	if mt < 0 {
		return mt + m
	}
	return mt
}
func (mt mint) inv() mint {
	var m, y mint
	m.subAs(2)
	dbl := mt
	y = 1
	for i := 0; i < 31; i++ {
		if m%2 == 1 {
			y.mulAs(dbl)
		}
		m >>= 1
		dbl.mulAs(dbl)
	}
	return y
}
func (mt mint) add(x mint) mint {
	return (mt + x).mod()
}
func (mt mint) sub(x mint) mint {
	return (mt - x).mod()
}
func (mt mint) mul(x mint) mint {
	return (mt * x).mod()
}
func (mt mint) div(x mint) mint {
	return mt.mul(x.inv())
}
func (mt *mint) addAs(x mint) *mint {
	*mt = mt.add(x)
	return mt
}
func (mt *mint) subAs(x mint) *mint {
	*mt = mt.sub(x)
	return mt
}
func (mt *mint) mulAs(x mint) *mint {
	*mt = mt.mul(x)
	return mt
}
func (mt *mint) divAs(x mint) *mint {
	*mt = mt.div(x)
	return mt
}


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

typedef char                SINT8;
typedef unsigned char       UINT8;
typedef short               SINT16;
typedef unsigned short      UINT16;
typedef int                 SINT32;
typedef unsigned int        UINT32;
typedef long long           SINT64;
typedef unsigned long long  UINT64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))


SINT32 main() {
    SINT32 max = 100;

    SINT32 n;
    scanf("%d",&n);

    SINT32 sosu[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
    SINT32 sosukazu[25] = {0};
    
    for (SINT32 i = 1; i < n+1; i++) {
        SINT32 buf = i;
        for (SINT32 j = 0; j < 25; j++) {

            if (buf == 1) {
                break;
            }

            while (buf%sosu[j] == 0) {
                buf = buf/sosu[j];
                sosukazu[j] = sosukazu[j] + 1;
            }
        }
    }

    SINT32 count2 = 0;
    SINT32 count4 = 0;
    SINT32 count14 = 0;
    SINT32 count24 = 0;
    SINT32 count74 = 0;

    for (SINT32 j = 0; j < 25; j++) {
        if (sosukazu[j] >= 2) {
            count2++;
        }
        if (sosukazu[j] >= 4) {
            count4++;
        }
        if (sosukazu[j] >= 14) {
            count14++;
        }
        if (sosukazu[j] >= 24) {
            count24++;
        }
        if (sosukazu[j] >= 74) {
            count74++;
        }
    }
 /*   for (SINT32 j = 0; j < 25; j++) {
        printf("%d ",sosukazu[j]);
    }
    printf("\n");

    printf("%d %d %d %d %d\n",count2,count4,count14,count24,count74);
*/

    if (count4 == 0) {
        printf("0");
    } else {
        SINT32 ans = count74+count24*(count2-1) + count14*(count4-1) + count4*(count4-1)*(count2-2)/2;
        printf("%d\n",ans);
    }

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }

int main() {
  int n; cin>>n;
  int dp[100010];
  rep(i, 100010) dp[i] = i;
  for (int i = 6; i < 100010; i *= 6) {
    for (int j = 0; j+i < 100010; ++j) dp[j+i] = min(dp[j+i], dp[j]+1);
  }
  for (int i = 9; i < 100010; i *= 9) {
    for (int j = 0; j+i < 100010; ++j) dp[j+i] = min(dp[j+i], dp[j]+1);
  }
  print(dp[n]);
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC targett("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define prnt(m) for(auto it = m.begin() ; it != m.end() ; ++it){cout<<*it<<endl;}
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define DBG(x) cout<<"# # #     "<<x<<'\n';
#define fri(i,s,n) for(ll i=s;i<n;i++)
#define mod 1000000007LL
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 4e18
#define five 100005;
#define six 1000005;
#define prllclock cerr<<"Time"<<1000*(ld)clock()(ld)CLOCKS_PER_SEC<<"ms\n";
//_______________________________________________________________________________
ll power(ll a,ll b,ll m)
{
   ll ans=1;
   while(b>0)
   {
       if(b%2)
       {
           ans=(ans*a)%m;
       }
       a=(a*a)%m;
       b=b/2;
   }
   return ans;
}
ll inverse(ll a,ll m)
{
       return (power(a,m-2,m));
}
const int N = 300005;
ll fct[N];
ll invf[N];
ll C(ll n,ll r)
{
       if(r>n){return 0;}
       ll xx = (invf[r]*invf[n-r])%mod;
       xx *= fct[n];
       xx %= mod;
       return xx;
}
void initialize()
{
       fct[0] = 1;
       invf[0] = 1;
       fri(i,1,N){
              fct[i] = (i*fct[i-1])%mod;
              invf[i] = inverse(fct[i],mod);
       }
}
int main()
{
       initialize();
       ll n,k;
       cin>>n>>k;
       ll ans = 0;
       fri(i,k,n+2)
       {
              ll ii = i-1;
              ll mini = (ii*(ii+1))/2;
              ll px = n-i+1;
              px *= i;
              px += mini;
              ans += px - mini+1;
              ans %= mod;
       }
       cout<<ans<<endl;
}


Measured memory_bytes: 8328
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-6;
struct vec
{
    double x,y;
    vec(double x=0,double y=0):x(x),y(y){}
    vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);}
    vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);}
    double operator*(const vec&o)const{ return x*o.x+y*o.y;}
    double operator^(const vec&o)const{ return x*o.y-y*o.x;}
    vec operator/(const double&o)const{ return vec(x/o,y/o);}
    vec operator*(const double&o)const{ return vec(x*o,y*o);}
    void sc(){scanf("%lf%lf",&x,&y);}
    double len(){return sqrt(x*x+y*y);}
};
bool line(vec a,vec b)
{
    return  fabs(a.y*b.x-b.y*a.x)<eps;
}
int n;
vec ans,v[N];
double r;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) v[i].sc();
    random_shuffle(v+1,v+1+n);
    ans=v[1];
    for(int i=1;i<=n;i++)
        if((ans-v[i]).len()>r)
    {
        ans=v[i];r=0;
        for(int j=1;j<i;j++)
            if((ans-v[j]).len()>r)
            {
                ans=(v[i]+v[j])/2;
                r=(ans-v[j]).len();
                for(int k=1;k<j;k++)
                    if((ans-v[k]).len()>r)
                    {
                        double x1=v[j].x-v[i].x;
                        double y1=v[j].y-v[i].y;
                        double x2=v[k].x-v[j].x;
                        double y2=v[k].y-v[j].y;
                        double z1=v[j].x*v[j].x-v[i].x*v[i].x+v[j].y*v[j].y-v[i].y*v[i].y;
                        double z2=v[k].x*v[k].x-v[j].x*v[j].x+v[k].y*v[k].y-v[j].y*v[j].y;
                        double x=(z2*y1-z1*y2)/(x2*y1-x1*y2)/2.0;
                        double y=(z2*x1-z1*x2)/(y2*x1-y1*x2)/2.0;
                        ans=vec(x,y);
                        r=(ans-v[i]).len();
                    }
            }
    }
    printf("%.10f\n",r);
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
long long inf=1000000000000000000;
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    long long dp[n+1][3][2];
    for(int i=0;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)dp[i][j][k]=-inf;
    dp[0][0][0]=0;
    //i番目まで見て、選べるはずの要素をj個捨て、次に数を{k=0:選べる、k=1:選べない}
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            //選べる
            if(j<2)dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][0]);//捨てる
            dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][0]+a[i]);//選ぶ
            //選べない
            dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][1]);
        }
    }
    if(n%2)cout<<max({dp[n][1][0],dp[n][1][1],dp[n][2][0],dp[n][2][1]})<<endl;
    else cout<<max({dp[n][0][0],dp[n][0][1],dp[n][1][0],dp[n][1][1]})<<endl;
    return 0;
}

Measured memory_bytes: 13672
import sys


def main(lines=None):
    # ここは変えない
    if not lines:
        lines = sys.stdin.readlines()
    lines = [line.split() for line in lines]
    # ここまで
    lines_int = [sorted(list(map(int, line))) for line in lines]

    answers = []
    for line in lines_int:
        if line[0] != 0 or line[1] != 0:
            answers.append("{0} {1}".format(line[0], line[1]))

    print("\n".join(answers))
    return "\n".join(answers)


def test_main():
    test_inputs = """
0 1
1 0
10 10
5758 6838
7515 113
5627 1051
7419 3010
4086 6212
2767 2749
2060 9084
7543 2225
1183 5089
5566 5137
4978 6966
""".strip()
    test_inputs = test_inputs.split("\n")
    answer = main(test_inputs)
    expect = """
0 1
0 1
10 10
5758 6838
113 7515
1051 5627
3010 7419
4086 6212
2749 2767
2060 9084
2225 7543
1183 5089
5137 5566
4978 6966
""".strip()

    assert answer == expect


if __name__ == "__main__":
    main()



Measured memory_bytes: 6540
#include <stdio.h>
int main(){
    char s[200010];
    long long int ans = 0, cnt = 0;
    scanf("%s",s);
    for(long long int i = 0; s[i] != '\0' ; i++)
    {
        if(s[i] == 'W'){
            cnt++;
            ans += i;
        }
    }
    for(long long int i = 0; i < cnt; i++)
    {
        ans -= i;
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 384
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <time.h>
using namespace std;
long double esp=1e-11;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define cle(a) while(!a.empty())a.pop()
#define mem(p,c) memset(p,c,sizeof(p))
#define mp(A, B) make_pair(A, B)
#define pb push_back
typedef long long int LL;
const long double PI = acos((long double)-1);
const LL INF=0x3f3f3f3f3f3f3f3fll;
const int MOD =1000000007ll;
const int maxn=100100;
vector<int>node[maxn];
int cnt[maxn],f[maxn],s[maxn],ans[3];
void dfs(int u,int fa)
{
	s[u]=1;
	f[u]=fa;
	for(auto x:node[u])
		if(x!=fa)
		{
			dfs(x,u);
			s[u]+=s[x];
		}
}
void dfs1(int u,int fa)
{
	ans[cnt[u]]++;
    for(auto x:node[u])
		if(x!=fa)
		{
			if(!cnt[x])
				cnt[x]=cnt[u];
			dfs1(x,u);
		}
}
deque<int>q;
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("in1.txt", "w", stdout);
    //::iterator iter;                  %I64d
    //for(int x=1;x<=n;x++)
    //for(int y=1;y<=n;y++)
    //scanf("%d",&a);
    //printf("%d\n",ans);
    int n;
	scanf("%d",&n);
	cnt[1]=1;
	cnt[n]=2;
	ans[1]=ans[2]=0;
	for(int x=1;x<n;x++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		node[u].pb(v);
		node[v].pb(u);
	}
	dfs(1,0);
	q.clear();
	int t=n;
	while(t!=0)
	{
		q.pb(t);
		t=f[t];
	}
	q.pop_front();
	q.pop_back();
	while(!q.empty())
	{
		if(!q.empty())
		{
			cnt[q.back()]=1;
			q.pop_back();
		}
		if(!q.empty())
		{
			cnt[q.front()]=2;
			q.pop_front();
		}
	}
	dfs1(1,0);
	if(ans[1]>=ans[2]+1)puts("Fennec");
	else puts("Snuke");
    return 0;
}


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


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

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  // ll N; cin >> N;
  // ll N, K; cin >> N >> K;
  // ll x, y, z; cin >> x >> y >> z;
  // ll a, b, c; cin >> a >> b >> c;
  string s, t; cin >> s >> t;
  
  ll ans = INF;

  rep(i, s.size() - t.size() + 1) {
    ll cnt = 0;
    rep(j, t.size()) {
      if(s[i + j] != t[j]) cnt++;
    }
    ans = min(ans, cnt);
  }
  
  cout << ans << endl;

}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3612