akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define For(i,a,b) for(int (i) = (a);(i) < (b);i++)
#define Rep(i,n) For((i),0,(n))
#define All(a) (a).begin(),(a).end()
#define sp " "
#define INF 1e18
#define INT_INF 1e9

typedef long long ll;
const ll MOD = 1000000007;
const ll MOD_9 = 998244353;

int main(){
    int N;
    cin >> N;
    vector<vector<int>> state(N,vector<int>(N,-1));
    Rep(i,N){
        int A;
        cin >> A;
        Rep(j,A){
            int x,y;
            cin >> x >> y;
            x--;
            state[i][x] = y;
        }
    }
    int ans = 0;
    int cnt = 0;
    bool judge = true;
    for(int i = 0;i < (1 << N);i++){
        judge = true;
        cnt = 0;
        for(int j = 0;j < N && judge == true;j++){
            if(i & (1 << j)){
                cnt++;
                for(int k = 0;k < N && judge == true;k++){
                    if(state[j][k] == 1){
                        if(!(i & (1 << k))){
                            judge = false;
                        }
                    }else if(state[j][k] == 0){
                        if(i & (1 << k)){
                            judge = false;
                        }
                    }
                }
            }
        }
        if(judge == true){
            ans = max(ans,cnt);
        }
    }
    cout << ans;
    //cin >> N;
}

Measured memory_bytes: 256
class Dice      
    @face = nil         
                        
    def initialize arr          
        @face = arr             
    end                                                         
    def top
        @face[0]
    end

    def rotate news       
        f = @face.dup
        case news
        when "N"
            @face = [f[1],f[5],f[2],f[3],f[0],f[4]]
        when "E"
            @face = [f[3],f[1],f[0],f[5],f[4],f[2]]
        when "W"
            @face = [f[2],f[1],f[5],f[0],f[4],f[3]]
        when "S"
            @face = [f[4],f[0],f[2],f[3],f[5],f[1]]
        end
    end
end

numbers = gets.chomp.split
dice = Dice.new numbers
directions = gets.chomp
directions.each_char{|c| dice.rotate c}

puts dice.top



Measured memory_bytes: 8908
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define isin(i,a,b) ((a) <= (i) && (i) <= (b))
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define fi first
#define se second
#define pb push_back
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll  = long long;          using vi  = vector<int>;
using unit= unsigned;           using vl  = vector<ll>;
using ull = unsigned long long; using vvi = vector<vi>;
using P   = pair<int,int>;      using vvl = vector<vl>;
                                using vp  = vector<P>;
void _main(); int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T>string join(const v(T)&v){ stringstream s; rep(i,0,sz(v))s<<' '<<v[i]; return s.str().substr(1); }
template<class T>istream &operator>>(istream&i, v(T)&v){ fore(x,v){ i >> v; } return i; }
template<class T>ostream &operator<<(ostream&o, const v(T)&v){ o<<"["; fore(x,v)o<<x<<","; o<<"]"; return o; }
template<class T>ostream &operator<<(ostream&o, const deque<T>&v){ o<<"deq["; fore(x,v)o<<x<<","; o<<"]"; return o; }
template<class T>ostream &operator<<(ostream&o, const set<T>&v){ o<<"{"; fore(x,v)o<<x<<","; o<<"}"; return o; }
template<class T>ostream &operator<<(ostream&o, const unordered_set<T>&v){ o<<"{"; fore(x,v)o<<x<<","; o<<"}"; return o; }
template<class T>ostream &operator<<(ostream&o, const multiset<T>&v){ o<<"{"; fore(x,v)o<<x<<","; o<<"}"; return o; }
template<class T>ostream &operator<<(ostream&o, const unordered_multiset<T>&v){ o<<"{"; fore(x,v)o<<x<<","; o<<"}"; return o; }
template<class T1,class T2>ostream &operator<<(ostream &o, const pair<T1,T2>&p){ o<<"("<<p.fi<<","<<p.se<<")"; return o; }
template<class TK,class TV>ostream &operator<<(ostream &o, const map<TK,TV>&m){ o<<"{"; fore(x,m)o<<x.fi<<"=>"<<x.se<<","; o<<"}"; return o; }
template<class TK,class TV>ostream &operator<<(ostream &o, const unordered_map<TK,TV>&m){ o<<"{"; fore(x,m)o<<x.fi<<"=>"<<x.se<<","; o<<"}"; return o; }
template<class T>void YES(T c){ if(c) cout<<"YES"<<endl; else cout<<"NO"<<endl; }
template<class T>void Yes(T c){ if(c) cout<<"Yes"<< endl; else cout<<"No"<<endl; }
template<class T>void POSS(T c){ if(c) cout<<"POSSIBLE"<<endl; else cout<<"IMPOSSIBLE"<<endl; }
template<class T>void Poss(T c){ if(c) cout<<"Possible"<<endl; else cout<<"Impossible"<<endl; }
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(b<a) a=b; }
template<class T>T gcd(T a, T b){ return (b==0) ? a : gcd(b,a%b); }
template<class T>T lcm(T a, T b){ return a * (b / gcd(a,b)); }
const double  EPS = 1e-10;
const double  PI  = acos(-1.0);
const int     INF = INT_MAX / 2;
const ll      INFL= 1LL << 60;
const int dx[] = { -1, 0, 1, 0 , -1,-1, 1, 1 };
const int dy[] = {  0, 1, 0,-1 , -1, 1,-1, 1 };

void _main() {
  int A, B, C;
  cin >> A >> B >> C;

  int ans = C - min((A-B), C);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;
/*
struct point
{
long long dist; long long name;
bool operator<(const point& rhs) const {
return dist > rhs.dist;
}
};
*/
ll MOD;
ll const MAX = 5000;
ll mod_p(ll x, ll y) {
	return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
	return x * y%MOD;
}

ll minusone(ll x) {
	if (x % 2 == 0) {
		return 1;
	}
	else return -1;
}

ll fuct[MAX];
ll inv_fuct[MAX];
ll pow22[MAX];
// 2 4 16 256
ll mod_pow(ll x, ll t) {
	if (t == 0) {
		return 1;
	}
	else {
		ll s = mod_pow(x, t / 2);
		if (t % 2 == 1) {
			return s * s%MOD*x%MOD;
		}
		else {
			return s * s %MOD;
		}
	}
}
ll mod_inv(ll x) {
	return mod_pow(x, MOD - 2);
}

ll comb(ll x, ll y) {
	return mod_m(fuct[x], mod_m(inv_fuct[y], inv_fuct[x - y]));
}
void init(ll n) {
	fuct[0] = inv_fuct[0] = 1;
	REP(i, 1, n) {
		fuct[i] = mod_m(fuct[i - 1], i);
		inv_fuct[i] = mod_inv(fuct[i]);
	}
	pow22[0] = 2;
	REP(i, 1, n) {
		pow22[i] = mod_m(pow22[i - 1], pow22[i - 1]);
	}
}
ll T[MAX] = {};
ll S[MAX][MAX];

void solve_s(ll n) {
	S[1][1] = S[1][0] = 1;
	REP(j, 2, n) {
		S[1][j] = 0;
	}
	REP(i, 2, n) {
		S[i][0] = 1;
		REP(j, 1, n) {
			S[i][j] = mod_p(S[i - 1][j] * (j+1), S[i - 1][j - 1]);
		}
	}
}

void solve_t(ll n) {
	solve_s(n);
	ll g = 1;
	REP(i, 1, n) {
		g = g * 2 % MOD;
	}
	T[0] = pow22[n];
	REP(i, 1, n) {
		T[i] = 0;
		ll q = mod_pow(2, n - i);
		ll t = 1;
		REP(j, 0, i) {
			T[i] = mod_p(T[i],mod_m(S[i][j],t));
			t = mod_m(t, q);
		}
		T[i] = mod_m(T[i], pow22[n - i]);
	}
}

int main() {
	ll n;
	cin >> n >> MOD;
	init(n);
	solve_t(n);
	ll ans = 0;
	REP(i, 0, n) {
		ans = mod_p(ans, minusone(i)*mod_m(comb(n, i), T[i]));
	}
	cout << ans << endl;
}



Measured memory_bytes: 118528
#include<stdio.h>
#include<stdlib.h>
int main()
{
	char a[3][3];
	int i,j;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			scanf("%c", &a[i][j]);
		}
		getchar();
	}
	printf("%c%c%c", a[0][0], a[1][1], a[2][2]);
	system("pause");
	return 0;

}

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

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

void solve() {
  int x, a;
  cin >> x >> a;

  if (x < a) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }
}

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

  solve();
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    int n,count,max = 0;
    bool a[26][2];
    rep(i, 26){a[i][0] = false; a[i][1] = false;}
    string s;
    cin >> n >> s;
    rep(i, n){
        a[s[i] - 97][0] = true;
        count = 0;
        rep(i, 26)a[i][1] = false;
        nfor(j, i + 1, n){
            if (a[s[j] - 97][0] && !a[s[j] - 97][1]) {
                a[s[j] - 97][1] = true;
                ++count;
            }
        }
        if (count > max) {
            max = count;
        }
    }
    cout << max << endl;
    return 0;
}


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

typedef long long ll;
 
const int INF= 1001001001;
const ll LINF= 1e18;

const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  int t[n+1] = {0};
  for (int i = 0; i < n; i++){
    if(s[i]=='<') t[i+1] = max(t[i+1],t[i]+1);
  }
  for (int i = n-1; i >= 0; i--){
    if(s[i] == '>') t[i] = max(t[i],t[i+1]+1);
  }
  ll ans = 0;
  for(int i = 0; i <= n; i++){
		ans += t[i];
	}
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 2844
d = {
  'MON':1,
  'TUE':2,
  'WED':3,
  'THU':4,
  'FRI':5,
  'SAT':6,
  'SUN':7
}

s = str(input())

if s == 'SUN':
  print(7)
else:
  print(d['SUN']-d[s])

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((ll)(1e15))
#define pi (2*acos(0))
#define mp make_pair
#define M ((ll)(998244353))
#define xx first
#define yy second
#define NN ((ll)(305))
#define N ((ll)(1e5 + 5))
#define pq priority_queue
///#define Q queue
#define eps 0
#define log 20
#define pb push_back
#define MOD 998244353


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long lu;


typedef tree < pair < ll,ll >,  null_type,  less < pair < ll,ll > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;

ll cnt[70], prof[70], ar[N];



int main()
{
    ll n;
    ll k;
    scanf("%lld %lld",&n,&k);
    ll a = k;
    ll c = 0;
    while(a){
        c++;
        a = a>>1;
    }
    for(ll i = 0; i<n; i++){
        ll a;
        scanf("%lld",&a);
        ar[i] = a;
        for(ll j = 0; a>0; j++){
            if(((1ll<<j)&a)!=0){
                cnt[j]++;
                a -= (1ll<<j);
            }
        }
    }
    ll ans = 0;
    for(ll j = 0; j<c; j++){
        if(cnt[j]<n-cnt[j]){
            ans |= (1ll<<j);
            prof[j] = (1ll<<j)*(n-cnt[j]*2);
        }
        else prof[j] = -1;
    }
    if(ans>k){
        ll mn = -1, tmp = -1;

        ll sum = 0;

        ll keep, aa = 0, f;
        for(ll i = c-1; i>=0; i--){

            if((mn==-1 || prof[i]<mn) && prof[i]>=0 && ((1ll<<i)&k)!=0){
                mn = prof[i];
                keep = aa|(1ll<<i);
                if(tmp==-1 || tmp>sum+mn){
                    tmp = sum+mn;
                    f = keep;
                }
            }
            if(((1ll<<i)&k)==0 && ((1ll<<i)&ans)!=0){
                ///if(keep==-1) keep = i;
                sum += prof[i];
                mn = -1;
                aa |= 1ll<<i;
            }
            else if(((1ll<<i)&k)!=0 && ((1ll<<i)&ans)==0){
                if(tmp==-1 || tmp>sum){
                    f = aa;
                }
                break;
            }
            if(ans-aa==k){
                if(tmp==-1 || tmp>sum) f = aa;
                break;
            }
        }
        ///if(keep==-1) return -1;
        ans -= f;
    }
    ///if(ans>k) return -1;
    ///printf("%lld\n",ans);
    ll sum = 0;
    for(ll i = 0; i<n; i++){
        sum += (ans^ar[i]);
    }
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 1024
'''
参考
https://qiita.com/c-yan/items/d1b19114d411755f25b5
https://qiita.com/easychoco/items/7f1f00d9221bd3ab0a6c
数列は以下で表すことができる
a[n+1] = a[n] * 10 + 7
a[n] % K == 0となれば、その時点でのnが解となる
'''
K = int(input())
if K % 2 == 0:
    print(-1)
    exit()

num = 0

for i in range(K):
    num = (num * 10 + 7) % K
    if num == 0:
        print(i+1)
        exit()

print(-1)


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

int main() {
  int H, W, M;
  cin >> H >> W >> M;

  set<P> points;
  rep(i,0,M-1) {
    int h, w;
    cin >> h >> w;
    points.insert(P(h, w));
  }

  map<int, int> mp_rows, mp_columns;
  int max_row_cnt = 0;
  int max_column_cnt = 0;

  for (P point : points) {
    max_row_cnt = max(max_row_cnt, ++mp_rows[point.first]);
    max_column_cnt = max(max_column_cnt, ++mp_columns[point.second]);
  }

  vector<int> max_row_indices;
  for (auto mp_row : mp_rows) {
    if (max_row_cnt == mp_row.second)
      max_row_indices.push_back(mp_row.first);
  }

  vector<int> max_column_indices;
  for (auto mp_column: mp_columns) {
    if (max_column_cnt == mp_column.second)
      max_column_indices.push_back(mp_column.first);
  }

  int ans = max_row_cnt + max_column_cnt;
  for (auto h : max_row_indices) {
    for (auto w : max_column_indices) {
      if (points.find(P(h, w)) == points.end()) {
        cout << ans << endl;
        return 0;
      }
    }
  }

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


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<pii, int> ppiii;

inline int can(vector<int>& v, int inc, int lhs, int rhs) {
  lhs -= inc;
  rhs -= inc;
  int a = lower_bound(v.begin(), v.end(), lhs) - v.begin();
  int b = upper_bound(v.begin(), v.end(), rhs) - v.begin();
  assert(a <= b);
  return b-a;
}

bool valid(vector<int> a, vector<int> b, int t) {
  for(int i = 0; i < a.size(); i++) a[i] %= (2*t);
  for(int i = 0; i < a.size(); i++) b[i] %= (2*t);
  sort(b.begin(), b.end());
  ll amt = 0;
  int aa = t;
  int bb = 2*t-1;
  int cc = 3*t;
  int dd = 4*t-1;
  for(int out: a) {
    amt += can(b, out, aa, bb);
    amt += can(b, out, cc, dd);
  }
  return amt%2;
}

void solve() {
  int n;
  cin >> n;
  vector<int> a, b;
  a.resize(n);
  b.resize(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  int ret = 0;
  for(int t = 1; t <= 1<<28; t*=2) {
    if(valid(a, b, t)) ret |= t;
  }
  cout << ret << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

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


Measured memory_bytes: 3456
import java.util.*;

public class Main {

  public static void main(String[] args) {
    int N = scanner.nextInt();
    int res = 0;
    for (int i = 1; i <= N; i++) {
      int num = scanner.nextInt();
      if (i % 2 != 0 && num % 2 != 0) {
        res++;
      }
    }
    System.out.println(res);
  }

  private static final Scanner scanner = new Scanner(System.in);
}


Measured memory_bytes: 35864
#include<iostream>

using namespace std;

int main(){
    long long a, b, c, k;
    cin >> a >> b >> c >> k;

    long long score = 0;
    if(k > 0){
        if(a > k){
            score = k;
            k = 0;
        } else {
            score = a;
            k -= a;
        }
    }

    if(k > 0){
        if(b > k){
            k = 0;
        } else {
            k -= b;
        }
    }

    if(k > 0){
        if(c > k){
            score -= k;
            k = 0;
        } else {
            score -= c;
            k -= b;
        }
    }

    cout << score << endl;
    return 0;
}

Measured memory_bytes: 3632
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string ans = "";
    REP(i,3){
        string s;
        cin >> s;
        ans+={s[i]};
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    return ret;
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = std::string::String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}
fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() }

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { parse(&get_word()) }

fn main() {
    let n: usize = get();
    let a: Vec<i64> = (0 .. n).map(|_| get::<i64>()).collect();
    let mut sum: i64 = 0;
    let mut tmp: i64 = 0;
    for i in 0 .. n {
        if a[i] >= 1 {
            tmp += a[i];
        } else {
            tmp = 0;
        }
        sum += tmp / 2;
        tmp %= 2;
    }
    println!("{}", sum);
}


Measured memory_bytes: 1148
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue> 
#include <tuple>
#include <map>
 
using namespace std;

typedef long long ll;

int main() {
	cin.tie(0);

    int N, M;

    cin >> N >> M;

    priority_queue<int, vector<int>, less<int> > q;
    vector<vector<int> > r(100005);

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        r[a].push_back(b);
    }

    int c = 0;

    for(int i = 1; i <= M; i++) {
        for(int j = 0; j < r[i].size(); j++) {
            q.push(r[i][j]);
        }
        if(!q.empty()) {
            c += q.top();
            //cerr << q.top() << endl;
            q.pop();
        }
    }

    cout << c << endl;
}


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

#define pb            push_back
#define mp            make_pair
#define ins           insert
#define endl          '\n'
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<endl<<(#X)<<" = "<<(X)<<endl; }
//#define cerr if(0)cerr

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,a,b,s=LLONG_MAX;
    cin >> n;

    for (ll i=sqrt(n); i>=1; --i)
        if (!(n%i)) {
            a = n/i;
            b = i+a-2;
            s = (b<s?b:s);
        }


    cout << s << endl;
}



Measured memory_bytes: 256
def setGroup(a):
    l = len(a)
    i = 0
    b = []
    while i < l:
        if a[i] < a[i+1]:
            b.append(a[i + 1] - a[i])
        elif  a[i] > a[i+1]:
            b.append(a[i] - a[i+1])
        else:
            b.append(a[i])
        i += 2
    return b
        
n = int(input())
i = 0
a =[]
while i < 2**n:
    a.append(int(input()))
    i += 1
while len(a) > 1:
    a = setGroup(a)
print(a[0])

Measured memory_bytes: 18720
#include <stdio.h>
int main(){
    int n, k;
    int sum, tmp;

    sum = 0;

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

    int  p[n];

    for(int i=0; i<n; i++){
        scanf("%d", &p[i]);
    }

    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(p[i] > p[j]){
                tmp = p[i];
                p[i] = p[j];
                p[j] = tmp;
            }
        }
    }  
   

    for(int j=0; j<k; j++){
        sum = sum + p[j];
    }

    printf("%d\n", sum);
    

    return 0;

}

Measured memory_bytes: 1728
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()

    M = [1] * (N + 1)
    for i in range(N):
        M[i + 1] = (M[i] - A[i]) * 2

    m = [1] * (N + 1)
    m[-1] = A[-1]
    for i in range(N, 0, -1):
        m[i - 1] = (m[i] + 1) // 2 + A[i - 1]
    
    res = 0
    t = 0
    for i in range(N, -1, -1):
        if M[i] <= 0:
            print(-1)
            return

        t = min(t + A[i], M[i])
        if t < m[i]:
            print(-1)
            return

        res += t

    print(res)


if __name__ == "__main__":
    main()



Measured memory_bytes: 679160
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    ll n,m,s=0,p,x;
    cin>>n;
    vector<ll> t(n);
    for(ll i=0;i<n;i++){
        cin>>t[i];
        s+=t[i];
    }
    cin>>m;
    for(ll i=0;i<m;i++){
        cin>>p>>x;
        cout<<s-t[p-1]+x<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
typedef long long int64;

int h, w;
int64 ans = 1LL << 62;

int main()
{
    scanf("%d%d", &h, &w);
    switch (h % 3) {
        case 0: ans = std::min(ans, 0LL); break;
        case 1: case 2: ans = std::min(ans, (int64)w); break;
    }
    switch (w % 3) {
        case 0: ans = std::min(ans, 0LL); break;
        case 1: case 2: ans = std::min(ans, (int64)h); break;
    }

    if (w > 1) for (int i = 1; i < h; ++i) {
        int64 s[3] = { (int64)i * w, (int64)(h - i) * (w / 2), (int64)(h - i) * (w - w / 2) };
        std::sort(s, s + 3);
        ans = std::min(ans, s[2] - s[0]);
    }
    std::swap(h, w);
    if (w > 1) for (int i = 1; i < h; ++i) {
        int64 s[3] = { (int64)i * w, (int64)(h - i) * (w / 2), (int64)(h - i) * (w - w / 2) };
        std::sort(s, s + 3);
        ans = std::min(ans, s[2] - s[0]);
    }

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)

using namespace std;

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

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int N, A, B, C;
	ll sum, n;
	vector<int> topping;
	cin >> N >> A >> B >> C;;
	REP(i, N){
		int a;
		cin >> a;
		topping.push_back(a);
	}
	sort(topping.begin(), topping.end(), greater<int>());
	n = A;
	sum = C;
	REP(i, N){
		if(topping[i] / B > sum / n){
			sum += topping[i];
			n += B;
		}else{
			break;
		}
	}
	cout << sum / n << endl;
}

Measured memory_bytes: 3156
#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

using namespace std;

int main() {
  int n;
  cin >> n;
  int mod = 1e9 + 7;

  ll ans = 1;
  for (int i = 1; i < n+1; i++) {
    ans = (ans * i) % mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n=int(input())
s=input()
t=input()
flg=True
tmp=0
if s==t:
    print(n)
    exit()
for i in range(1,n):
    ss=s[i:]
    tt=t[:-i]
    if ss==tt:
        print(2*n-len(ss))
        exit()
print(n*2)

Measured memory_bytes: 8956
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
const int MOD=1e9+7;
const int INF=1e20;

signed main(){
    int N;cin>>N;
    vector<int>A(N);
    REP(i,N)cin>>A[i];
    int ans=0;
    REP(i,N){
        int d=A[i]-1;
        if(A[d]-1==i)ans++;
    }
    cout<<ans/2<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>

using namespace std;

int so(int n){
  int count,c=0;
  int n1;
  //nが奇数であるようにする
  if(n==1)return 1;
  n1=n;
  n1++;
  if(n%2!=0)n1++;
  //nから２ずつ足していく
  for(int i = n1 ; i < n*2 ; i+=2){
    count=0;
    //その値を素数判定し素数ならカウントする
    for(int j = 1;j*j <= i; j+=2){
      if(i%j==0)count++;
    }
    if(count==1){
      //    cout<<i<<endl;
      c++;
    }
  }
  return c;
}


int main(){
  int n;
  while(true){
    cin>>n;
    if(n==0)break;
    cout<<so(n)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
ab=[]
n,m=map(int,input().split())
for i in range(n):
	x,y=map(int,input().split())
	ab.append([x,y])
ab.sort()
cost=0
for i in range(n):
	if m>0:
		cost+=min(ab[i][1],m)*ab[i][0]
		m-=ab[i][1]
	else:
		break
print(cost)


Measured memory_bytes: 20048
#include<iostream>

using namespace std;

int main() {
	int N, H, W;
	cin >> N >> H >> W;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		if (a >= H && b >= W)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
from itertools import product

read = sys.stdin.readline
X, Y, Z, K = map(int, read().split())
lst_A = list(map(int, read().split()))
lst_B = list(map(int, read().split()))
lst_C = list(map(int, read().split()))


lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

for i in range(K):
    print(lst_ABC_K[i])


Measured memory_bytes: 237188
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
ll dp[10005][105][2];
string s;
ll d;

ll solve(ll pos, ll sum, bool tight){
    if(pos==s.length()){
        return sum==0;
    }
    if(dp[pos][sum][tight]!=-1) return dp[pos][sum][tight];

    ll ans=0;
    ll end = ((tight)?(s[pos]-'0'):9);
    for(ll i=0; i<=end; i++){
        ans = (ans + solve(pos+1,(sum+i)%d, tight&(i==end)))%mod;
    }
    return dp[pos][sum][tight]=ans;
}
int main() {
    cin>>s>>d;
    memset(dp,-1,sizeof (dp));
    cout<<(solve(0,0,1)-1 +mod)%mod<<endl;
    // cout<<(res-1 + mod)%mod<<endl;   // -1 coz one number whose sum will be equal to 0 is 0000000000000 and so on.
}


Measured memory_bytes: 17408
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define esp 1e-9
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",(n/2)*(n-(n/2)));
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main(void)
{
    int x, y, z, ans=0;
    cin >> x >> y >> z;

    for(int i = 1; i*y + z*(i+1) <= x;i++)
        ans = i;

    cout << ans << endl;  
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main() {
	char s[51], t[51];
	gets(s);
	gets(t);
	int len_t = strlen(t);
	int len_s = strlen(s);
	if(len_t>len_s) {
		printf("UNRESTORABLE");
		return 0;
	}
	int i;
	//int flag = 0;
	for(i=len_s-len_t;i>=0;i--) {
		int j;
		int flag = 0;
		for(j=len_t-1;j>=0;j--) {//判断能不能嵌入 
			if(s[j+i]!=t[j] && s[j+i]!='?') {
				flag = 1;
				break;
			}
		}
		if(flag==0) {//如果每一位都相等，就替换掉 
			for(j=len_t-1;j>=0;j--) {
				s[j+i] = t[j];
			}
			break;
		}
		if(flag==1 && i == 0) {/////不满足条件的情况 
			printf("UNRESTORABLE");
			return 0;
		}
	}//已经把一部分问号替换为字母了 
	for(i=0;i<len_s;i++) {
		if(s[i]=='?') {
			s[i] = 'a';
		}
	}
	puts(s);
	
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define X first
#define Y second

using namespace std;

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

int x[15];
int type[15];
string s;
int num;

int parse(int l, int r){
	if (r-l == 1) return x[s[l] - '1'];

	int sp = -1, nest = 0;
	for (int i = l+1; i < r-1; ++i){
		if (s[i] == '(') ++nest;
		if (s[i] == ')') --nest;
		if (!nest && s[i] == ' ') sp = i;
	}

	int res1 = parse(l + 1, sp);
	int res2 = parse(sp + 1, r - 1);

	int ret = -1;
	if (type[num] == 0) ret = res1 | res2;
	if (type[num] == 1) ret = res1 & res2;
	if (type[num] == 2) ret = res1 ^ res2;
	++num;
	return ret;
}


int ans;
int m;
void rec(int n){
	if (n == m){
		num = 0;
		//cout << parse(0, s.size()) << endl;
		ans += parse(0, s.size()) == 15;
		return;
	}
	rep(i, 3){
		type[n] = i;
		rec(n + 1);
	}
}

int main(){
	while (getline(cin, s), s != "END"){
		int n;
		cin >> n;

		MEMSET(x, 0);
		rep(i, n) rep(j, 4){
			int t;
			cin >> t;
			x[i] |= (t << j);
		}
		ans = 0;
		m = count(ALL(s), ' ');
		rec(0);
		cout << ans << endl;
		cin.ignore();
	}


	return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, vs[1000009], c[1000009];
vector<int> v[1000009];
queue<pair<int, int> > q;
bool cc = false;

int vn(int a, int b)
{
	if (a > b) swap(a, b);
	return (a - 1) * n + b;
}

void dfs(int hn)
{
	vs[hn] = 2;
	for (int i = 0; i < v[hn].size(); i++) {
		int tn = v[hn][i];
		if (vs[tn] == 2) cc = true;
		if (!vs[tn]) dfs(tn);
	}
	vs[hn] = 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int b; cin >> b;
		for (int j = 2; j < n; j++) {
			int a; cin >> a;
			v[vn(i, b)].push_back(vn(i, a));
			c[vn(i, a)]++;
			b = a;
		}
	}
	for (int i = 1; i <= n * n; i++) {
		if (!vs[i])
			dfs(i);
		if (!c[i])
			q.push(make_pair(i, 1));
	}
	if (cc) {
		cout << -1 << '\n';
		return 0;
	}
	int ans = 1;
	while (!q.empty()) {
		int hn = q.front().first;
		ans = q.front().second; q.pop();
		for (int i = 0; i < v[hn].size(); i++) {
			int tn = v[hn][i];
			c[tn]--;
			if (!c[tn]) 
				q.push(make_pair(tn, ans + 1));
		}
	}
	cout << ans << '\n';
	return 0;
}	

Measured memory_bytes: 51328
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
left_sum = 0
ans = float('inf')
for i in range(N):
    left_sum += A[i]
    right_sum = total - left_sum
    ans = min(ans, abs(left_sum - right_sum))
print(ans)

Measured memory_bytes: 26024
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
#define chmax(x,y) (x = max(x, y))
void solve(); int main() { solve(); return 0; }

void solve() {
  int a, b;cin >> a >> b;
  cout << max(a+b, max(a-b, a*b)) << endl;
}


Measured memory_bytes: 3556
#define first f
#define second s
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n, k, q, l;
	cin >> n >> k >> q;
	vector <int> s(n);
	for (int i = 0; i < q; i++) {
		cin >> l;
		s[l-1]++;
	}
	for (int i = 0; i < n; i++) {
		if (s[i] + k - q <= 0) cout << "No" << endl;
		else cout << "Yes"<<endl;
	}
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
  map<string, vector<int> > i;
  string str;
  int n;
  int j;

  while(cin >> str >> n){
	i[str].push_back(n);
  }

  map<string, vector<int> >::iterator it = i.begin();
  while(it != i.end()){
	cout << (*it).first << endl;
	sort((*it).second.begin(), (*it).second.end());
	for(j=0;j<(*it).second.size()-1;j++){
	  cout << (*it).second[j] << " ";
	}
	cout << (*it).second[j] << endl;
	++it;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll dp[ohara];
unordered_map<ll,ll> out;

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>m;
    rep(i,m)cin>>a[i];
    rep(i,m)out[a[i]]=1;
    dp[0]=1;
    rrep(i,1,n+1){
        if(out[i]==1)continue;
        if(i==1)(dp[i]=dp[i-1])%=MOD;
        else {
            if(out[i-1]==1&&out[i-2]==1)continue;
            else if(out[i-1]==1){
                (dp[i]=dp[i-2])%=MOD;
            }
            else if(out[i-2]==1){
                (dp[i]=dp[i-1])%=MOD;
            }
            else{
                (dp[i]=(dp[i-1]+dp[i-2]))%=MOD;
            }
        }
    }
    Cout(dp[n]);
    return 0;
}


Measured memory_bytes: 9252
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<map>
using namespace std;

char other(char i, char j) {
    map<char, int> mp;
    mp['R'] = 0;
    mp['G'] = 0;
    mp['B'] = 0;

    mp[i]++;
    mp[j]++;

    for (auto it = mp.begin(); it != mp.end(); it++)
        if (it->second == 0)
            return it->first;

    return 0;
}

int countUp(const vector<int>& v, int index, int d) {
    int cnt = v.end() - upper_bound(v.begin(), v.end(), index);

    //auto it = find(v.begin(), v.end(), index + d);
    //if (it != v.end())
    //    cnt--;

    //auto it = lower_bound(v.begin(), v.end(), index + d);
    //if (it == v.end() || *it == index + d) {
    //    cnt = max(0, cnt - 1);
    //}

    return cnt;
}

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

    string S;
    cin >> S;

    vector<int> r, g, b;
    for (int i = 0; i < N; i++)
        if (S[i] == 'R')
            r.push_back(i);
        else if (S[i] == 'G')
            g.push_back(i);
        else
            b.push_back(i);

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            char ci = S[i];
            char cj = S[j];
            if (ci == cj)
                continue;

            int prev = ans;
            char ck = other(ci, cj);
            if (ck == 'R')
                ans += countUp(r, j, j - i);
            else if (ck == 'G')
                ans += countUp(g, j, j - i);
            else if (ck == 'B')
                ans += countUp(b, j, j - i);

            int index = j + j - i;
            if (index < N && S[index] == ck)
                ans--;

            //cout << ci << " " << cj << " " << ck << " " << ans - prev << endl;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3640
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,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-'0',ch=getchar();
    return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
const int mod=998244353;
inline int ad(int x){return x>=mod?x-mod:x;}
inline int dec(int x){return x<0?x+mod:x;}
char ss[200010];
int n,top,sta[110],f[110];
inline bool pd(int x)
{
	for(int i=1;i<=n;i++)
	{
		int p=i%x,uf=i/x;if(!p)p=x,uf++;
		if(((uf&1)^(ss[p]-'0'))>(ss[i]-'0'))return false;
		if(((uf&1)^(ss[p]-'0'))<(ss[i]-'0'))return true;
	}
	return true;
}
int main()
{
    //freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	n=read();
	scanf("%s",ss+1);
	for(int i=1;i<=n;i++)if(n%i==0 && (n/i)&1)sta[++top]=i,f[top]=i;
	for(int i=top;i>=1;i--)
	{
		for(int j=i+1;j<=top;j++)if(sta[j]%sta[i]==0 && (sta[j]/sta[i])&1)f[i]=dec(f[i]-f[j]);
	}
	int ans=0;
	for(int i=1;i<=top;i++)
	{
		int now=0;
		for(int j=1;j<=sta[i];j++)now=ad((now<<1)+ss[j]-'0');
		if(pd(sta[i])==true)now++;
		ans=ad(ans+1LL*f[i]*now%mod);
	}pr2(ad(ans<<1));
	return 0;
}

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

pos = [[int(w) for w in input().split()] for _ in range(n)]

dist = [[0] * n for i in range(n)]

for i in range(n):
    for j in range(i+1, n):
        d = ((pos[i][0]-pos[j][0])**2 + (pos[i][1]-pos[j][1])**2)**0.5
        dist[i][j] = d

ave = sum(map(sum, dist))/((n**2-n)//2)

print(ave*(n-1))


Measured memory_bytes: 9468
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define MN 200000
using namespace std;
inline int read()
{
    int x=0,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-'0',ch=getchar();
    return x*f;
}
int q[MN+5],top,L[MN+5],R[MN+5],n,a[MN+5];
long long ans=0;
int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        while(top&&a[i]<=a[q[top]]) --top;
        L[i]=q[top]+1;q[++top]=i;
    }
    q[top=0]=n+1;
    for(int i=n;i;--i)
    {
        while(top&&a[i]<a[q[top]]) --top;
        R[i]=q[top]-1;q[++top]=i;
        ans+=1LL*a[i]*(R[i]-i+1)*(i-L[i]+1);
    }
    printf("%lld\n",ans);
    return 0;
}


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

int main() {
	int a[100000];
	int b[100000];
	int n, m;
	cin >> n >> m;

	if (n >= m) {
		cout << "0" << endl;
		return 0;
	}

	for (int i = 0;i < m;i++)cin >> a[i];
	sort(a, a + m);
	for (int i = 0;i < m-1;i++)b[i]=abs(a[i+1]-a[i]);
	sort(b, b + (m - 1),greater<int>());
	int ans = a[m - 1] - a[0];
	for (int i = 0;i < n - 1;i++)ans-=b[i];
	cout << ans << endl;
	return 0;
}

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

const int M=1e6;
const auto PI=acosl(-1);
const auto R=1e12l;
long double x[101], y[101];
int cnt[101];
int main()
{
    int n; cin>>n;
    for(int i=0; i<n; ++i) cin>>x[i]>>y[i];

    for(int i=0; i<M; ++i) {
        auto a=i/(2*PI)*M;
        auto ax=R*cosl(a);
        auto ay=R*sinl(a);
        int k=-1;
        decltype(ax) mind=0;
        for(int j=0; j<n; ++j) {
            auto dx=x[j]-ax;
            auto dy=y[j]-ay;
            auto d=dx*cosl(a)+dy*sinl(a);
            if (mind>d) {
                mind=d;
                k=j;
            }
        }
        ++cnt[k];
    }
    for(int i=0; i<n; ++i) printf("%.9f\n", (double)cnt[i]/M);
}


Measured memory_bytes: 512
#include <cmath>
#include <iostream>
#include <numeric>

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int main() {
  int N, p[1001]{};
  cin >> N;
  for (int i = 2; i <= N; ++i) {
    int I = i;
    for (int j = 2, n = sqrt(I) + 1; I != 1 && j != n; ++j) {
      while (I % j == 0) {
        I /= j;
        ++p[j];
      }
    }
    if (I != 1) ++p[I];
  }

  cout << accumulate(begin(p), end(p), 1ll, [&](ll a, ll x) {
    return a * (x + 1) % MOD;
  }) << endl;
}


Measured memory_bytes: 3676
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  if (x + a < b) P("dangerous");
  else if (a >= b) P("delicious");
  else P("safe");

  return 0;
}

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

int main(){
    int A,B,C;

    cin >> A >> B >> C;

    if( (A < B && (B < C || C < A) )|| (B < A && (B > C || C > A) ) ){
        cout << "No";
    }else{
        cout << "Yes";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <vector>
#include <cstdio>
#include<set>
using namespace std;
set<string> lst;

int main()
{
	int lst[10000];
	int a,b,w, n; cin >> w >> n;
	for (int i = 0; i < w; i++)
	{
		lst[i] = i + 1;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d,%d", &a, &b);
		swap(lst[a - 1], lst[b - 1]);
	}
	for (int i = 0; i <w; i++)
	{
		cout << lst[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3132
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;
typedef long long LL;
typedef pair<int,int> mp;
const int maxn = 200005;
const int inf = 1<<30;
#define fi first
#define se second

mp c[maxn*2];int n,minx,miny,maxx,maxy;LL ans;
int bac[maxn],cnt[maxn],sum;
void insert(int x) {if (!cnt[x]++) sum++;}
void remove(int x) {if (!--cnt[x]) sum--;}
int main()
{
	#ifdef Amberframe
		freopen("arc073e.in","r",stdin);
		freopen("arc073e.out","w",stdout);
	#endif
	scanf("%d",&n);
	minx=miny=inf;maxx=maxy=-inf;
	for (int x,y,i=1;i<=n;i++) {
		scanf("%d %d",&x,&y);if (x>y) swap(x,y);
		minx=min(minx,x);maxx=max(maxx,x);
		miny=min(miny,y);maxy=max(maxy,y);
		c[i*2-1]=mp(x,i);c[i*2]=mp(y,i);
	}
	sort(c+1,c+n*2+1);
	ans=(LL)(maxx-minx)*(maxy-miny);
	for (int i=2,pos=1;i<=2*n;i++)
	{
		while (pos<=2*n&&sum<n) ++pos,insert(c[pos].se);
		if (pos>2*n) break;
		ans=min(ans,(LL)(maxy-minx)*(c[pos].fi-c[i].fi));
		remove(c[i].se);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 4096
#!/usr/bin/env python3
from functools import reduce
from operator import mul

mod = 10**9 + 7


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(lambda a, b: a * b % mod, range(n, n - r, -1))
    under = reduce(lambda a, b: a * b % mod, range(1, r + 1))
    return over * pow(under,mod-2,mod)


n, a, b = map(int, input().split())
print((pow(2, n, mod) - 1 - cmb(n, a) - cmb(n, b)) % mod)


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

const int N = 1e4 + 10, M = 100, MOD = 1e9 + 7;

string str;
int n, mod, ch[N], pos[N][M];

signed main() {
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> str >> mod;
    n = str.size();
    
    for(int i = 0; i < n; i++)
        ch[i] = str[i] - '0';
    
    pos[0][0] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < mod; j++)
            for(int k = 0; k < 10; k++) {
                pos[i+1][(j + k) % mod] += pos[i][j];
                pos[i+1][(j + k) % mod] %= MOD;
            }
    int sum = 0, t = 0;
    for(int i = 0; i < n; i++) {
        int i2 = n - i - 1;
        for(int j = 0; j < ch[i]; j++, t++) {
            t %= mod;
            sum += pos[i2][(mod - t) % mod];
            sum %= MOD;
        }
        t %= mod;
    }
    if(t % mod == 0)
        sum++;
    cout << (sum-1 + MOD) % MOD;
}

Measured memory_bytes: 8192
#include<cstdint>
#include<iostream>
#include<vector>
#include<memory>
#include<algorithm>
#include<utility>

using namespace std;

int64_t N;

int64_t Q, H, S, D;

int main()
{
	cin >> Q >> H >> S >> D >> N;

	int64_t minimum1L = min({ 4 * Q, 2 * H, S });
	int64_t minimum2L = min({ 2*minimum1L, D });

	int64_t ans = ((N / 2)*minimum2L) + ((N % 2)*minimum1L);

	cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
using namespace std;


int N;
long A[100000];

long long int rain[100000];//山iに降った雨の量をrain[i]とする
 
void solve(){
	rain[1] = 0;
	for(int i=1;i<=N;i++){
		if(i%2==1) rain[1] = rain[1] + A[i];
		else rain[1] = rain[1] - A[i];
	}
	rain[1] /= 2;

	for(int i=2;i<=N;i++) rain[i] = A[i-1] - rain[i-1];
	for(int i=1;i<=N;i++) rain[i] *= 2;
}
 
int main(){
	cin >> N;
	for(int i=1;i<=N;i++) cin >> A[i];
 
	solve();
 
	for(int i=1;i<=N;i++) cout << rain[i] << " ";
	return 0;
}


Measured memory_bytes: 2816
#include <iostream>

using namespace std;
const int max_n = 1 << 17;
int dat[max_n * 2 -1];



void init() {
	for (int i = 0; i < max_n * 2 -1; i++) {
		dat[i] = 0;
	}
}

void update(int i, int v) {
	i += max_n - 1;
	dat[i] += v;

	while (i > 0) {
		i = (i -1) / 2;
		dat[i] += v;
	}
}

int find(int a, int b, int k, int l, int r) {
	if (r <= a || b <= l) {
		return 0;
	}
	if (a <= l &&  r <= b) {
		//cout << " a:" << a << " b:" << b << " k:" << k <<" l:" << l << " r:"  << r << " dat[k]:" << dat[k] << endl;
		return dat[k];
	}

	int lv = find(a,b,k * 2 + 1,l,(r + l) / 2);
	int lr = find(a,b,k * 2 + 2,(r + l) / 2,r);
	return lv + lr;
}




int main() {
	init();

	int n,q;
	cin >> n >> q;

	for (int i = 0; i < q; i++) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com == 0) {
			update(x,y);
		} else {
			cout << find(x,y + 1,0,0,max_n) << endl;
		}

	}


	return 0;
}

Measured memory_bytes: 2188