akhauriyash/Code-Regression huggingface dataset:
use proconio::fastout;
use whiteread::parse_line;

#[fastout]
fn main() {
    let _: usize = parse_line().unwrap();
    let mut a: Vec<usize> = parse_line().unwrap();
    a.sort();

    let n = a.last().unwrap();
    let mut min = n / 2;
    let mut min_idx = 0;
    for i in 0..(a.len() - 1) {
        let cand = if a[i] > n / 2 { n - a[i] } else { a[i] };
        if min > n / 2 - cand {
            min = n / 2 - cand;
            min_idx = i;
        }
    }
    println!("{} {}", a.last().unwrap(), a[min_idx]);
}


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



int main(){
    ll N; cin >> N;
    vector<ll> A(N), NUM(1e6);
    for(int i = 1; i < N; i++){
        cin >> A[i];
    }
    for(int i = 1; i < N; i++) {
        //cout << A[i] << endl;
        NUM[--A[i]]++;
    }
    for(int i = 0; i < N; i++) cout << NUM[i] << endl;
}

Measured memory_bytes: 12700
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int l[m], r[m], d[m];
  for (int i = 0; i < m; i++) cin >> l[i] >> r[i] >> d[i];
  vector<P> info[n];
  for (int i = 0; i < m; i++) {
    info[l[i] - 1].push_back(P(r[i] - 1, d[i]));
    info[r[i] - 1].push_back(P(l[i] - 1, -d[i]));
  }
  int x[n];
  memset(x, -1, sizeof(x));
  string res = "Yes";
  for (int i = 0; i < n; i++) {
    stack<int> q;
    if (x[i] != -1) continue;
    else {
      x[i] = (int) 1e9;
      q.push(i);
    }
    while (q.size()) {
      int v = q.top();
      q.pop();
      for (auto p : info[v]){
        int u = p.first;
        if (x[u] == -1) {
          x[u] = x[v] + p.second;
          q.push(u);
        } else {
          if (x[u] != x[v] + p.second) {
            cout << "No" << "\n";
            return 0;
          }
        }
      }
    }
  }
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 11776
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
#define check(n) reverse(all(n));rep(z,0,n.size())cout<<n[z];co("");reverse(all(n));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  ll n,m,x,ans=1000000000000,f=0;
  cin>>n>>m>>x;
  ll c[n],a[n][m],g=true;
  rep(i,0,n){
    cin>>c[i];
    rep(j,0,m) cin>>a[i][j];
  }
  ll b=1,e;
  rep(i,0,n) b*=2;
  rep(i,1,b+1){
    ll d[m]={};
    e=i;
    rep(j,0,n){
      if(e%2==1){
        f+=c[j];
        rep(k,0,m) d[k]+=a[j][k];
      }
      e/=2;
    }
    rep(j,0,m){
      if(d[j]<x) g=false;
    }
    if(g==true){
      ans=min(f,ans);
    }
    g=true;
    f=0;
  }
  if(ans!=1000000000000) co(ans);
  else co(-1);
  
  return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
string s,t;
int main(){
	cin>>s>>t;
	string res="";
	for(int i=0;i<s.size()-t.size()+1;i++){
		string s2=s;
		bool flag=true;
		for(int j=0;j<t.size();j++){
			if(s2[i+j]!='?'&&s2[i+j]!=t[j]){
				flag=false;
				break;
			}
			else s2[i+j]=t[j];
		}
		if(!flag)continue;
		for(int j=0;j<s2.size();j++){
			if(s2[j]=='?')s2[j]='a';
		}
		if(res==""||s2<res)res=s2;
	}
	if(res=="")cout<<"UNRESTORABLE"<<endl;
	else cout<<res<<endl;
	return 0;
}

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

int main(){
	int n, total;
	bool finish=false;
	cin >> n;
	for (int i=0; 4*i<=n; i++) {
		for (int j=0; 7*j<=n; j++) {
			total=4*i+7*j;
			if(total==n) {
				finish = true;
				break;
			}
		}
		if(finish) break;
	}
	if(finish) cout << "Yes" << endl;
	else cout <<"No" << endl;
}


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

int main(){
    string s,t;
    cin>>s>>t;
    int ls=s.length(),lt=t.length();
    int dp[ls+1][lt+1];
    for(int i=0;i<=ls;i++){
        for(int j=0;j<=lt;j++){
            if(i==0 || j==0)dp[i][j]=0;
            else if(s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int i=ls,j=lt;
    int index=dp[ls][lt];
    char ans[index+1];
    ans[index]='\0';
    while(i>0 && j>0){
        if(s[i-1]==t[j-1]){
            ans[index-1]=s[i-1];
            i--,j--,index--;
        }
        else if(dp[i-1][j]>dp[i][j-1]){
            i--;
        }
        else j--;
    }
    cout<<ans;
    //cout<<"!";
}


Measured memory_bytes: 35456
import java.util.Scanner;

public class Main{

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

	private Scanner scan;
	private int N,Q;
	private long[] A;

	private void mainrun() {
		scan = new Scanner(System.in);

		N = scan.nextInt();
		Q = scan.nextInt();

		A = new long[N+1];

		A[N] = 0;
		
		for(int i = 0;i < N;i++) {
			A[i] = scan.nextLong();
		}

		for(int i = 0;i < Q;i++) {
			System.out.println(Calculation(scan.nextLong()));
		}

		scan.close();
	}

	private long Calculation(long border) {
		long sum = 0,cnt = 0;
		int cursor_r = 0,cursor_l = 0;

		while(cursor_l < N) {
			if(sum + A[cursor_r] <= border && cursor_r < N) {
				sum += A[cursor_r++];
			}else {
				cnt += cursor_r - cursor_l;
				sum -= A[cursor_l++];
			}
		}

		return cnt;
	}
}



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

using namespace std;

#define LL long long 
#define ULL unsigned long long 
#define LD long double 

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, a, b;
	cin>>n>>a>>b;
	int w1 = n*a;
	int w2 = b;
	cout<<min(w1, w2);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
#define int long long
#define endl '\n'
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repA(i, a, n) for (int i = a; i <= (n); ++i)
#define repD(i, a, n) for (int i = a; i >= (n); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre()
{
}

void solve()
{
    int n;
    cin >> n ; 
    cout << (n+1)/2 << endl;
}

signed main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);

    pre();
    int tests = 1;
    // cin >> tests;
    while (tests--)
    {
        solve();
    }

    return 0;
}

Measured memory_bytes: 256
/*   Then, everything changed when the Fire Nation attacked. */

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define mod 1000000007
#define fi first
#define se second
using namespace std;
int n,x;
int gcd(int a, int b)
{
    while(b)
    {
        int c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // shuffle(permutation.begin(), permutation.end(), rng);
    cin>>n>>x;
    int sol=0;
    for(int i=1;i<=n;++i)
    {
        int nr;
        cin>>nr;
        if(i==1)
            sol=abs(x-nr);
        else
        {
            int dist=abs(x-nr);
            sol=gcd(sol, dist);
        }
    }
    cout<<sol;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[200010];
long long ans,sum;
int main()
{
	scanf("%s",a);
	int len=strlen(a);
	for (int i=len-1;i>=0;i--)
	 if (a[i]=='W') sum++; else ans+=sum;
	cout << ans << endl; 
}

Measured memory_bytes: 384
#include<stdio.h>
#include<math.h>
int main(void) {
  int N,T,A,n=0,H[1000];
  scanf("%d",&N);
  scanf("%d %d",&T,&A);
  for(int j=0;j<N;j++) {
    scanf("%d",&H[j]);
  }
  for(int i=1;i<N;i++) {
    if(pow(T-H[n]*0.006-A,2.0) > pow(T-H[i]*0.006-A,2.0))n=i;
  }
  printf("%d\n",n+1);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>

using namespace std;

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

  string A, B, C;
  cin >> A >> B >> C;
  if(A.back() == B.front() && B.back() == C.front()){
	cout << "YES" << endl;
  }else{
	cout << "NO" << endl;
  }

  return 0;
}


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

int main(int argc, char const *argv[])
{
  while(1)
  {
    int n;
    cin >> n;
    if(n == 0) break;

    vector<int> s(n);
    for(int i = 0; i < n; i++)
      cin >> s[i];

    double m = 0;
    for(int i = 0; i < n; i++)
      m += s[i];
    m /= n;

    double a2 = 0;
    for(int i = 0; i < n; i++)
      a2 += (s[i] - m)*(s[i] - m) / n;

    cout << fixed << setprecision(10) << sqrt(a2) << endl;
  }
  return 0;
}

Measured memory_bytes: 3240
// https://atcoder.jp/contests/abc140/tasks/abc140_b
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, [ next / $t:tt ]) => {
        {
            let len = read_value!($iter, usize);
            (0..len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! dvec {
    ($t:expr ; $len:expr) => {
        vec![$t; $len]
    };

    ($t:expr ; $len:expr, $($rest:expr),*) => {
        vec![dvec!($t; $($rest),*); $len]
    };
}

#[allow(unused_macros)]
macro_rules! ifv {
    ($t:expr, $a:expr, $b: expr) => {
        if $t { $a } else { $b }
    }
}

#[allow(unused_macros)]
macro_rules! fill {
    ($t:expr, $v:expr) => {
        for i in 0..$t.len() {
            $t[i] = $v;
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
        n: usize,
        a: [usize1; n],
        b: [i32; n],
        c: [i32; n-1]
    };

    let mut total = 0;
    for i in 0..n {
        total += b[a[i]];
        if i >= 1 && a[i-1] + 1 == a[i] {
            total += c[a[i-1]];
        }
    }

    println!("{}", total);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
const long double PI = acos(-1);
const long long INF = (1 << 30);
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;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  string s;
  cin >> s;
  
  ll o = 0, z = 0;
  for(ll i = 0; i < s.size(); i++){
    if(s[i] == '0') z++;
    else o++;
  }
  cout << s.size() - (max(o, z) - min(o, z)) << endl;
  return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		double p = 0;

		for(int i=1;i<=N;i++) {
			double pi = 1;
			int temp = i;
			while(temp < K) {
				pi /= 2;
				temp *= 2;
			}
			p += pi;
		}
		p /= N;
		System.out.println(p);
    }
}

Measured memory_bytes: 22868
#include <iostream>
#include <vector>
using namespace std;
vector<int> g[200001];
long long ans[200001]={0};
int dfs(int v, int p=-1){
    for(int u : g[v]){
        if(u==p) continue;
        ans[u]+=ans[v];
        dfs(u, v);
    }
}
int main(){
    int n, q, i, p, a, b, x;
    cin >> n >> q;
    for(i=0;i<n-1;i++){
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(i=0;i<q;i++){
        cin >> p >> x;
        p--;
        ans[p] += x;
    }
    dfs(0);
    for(i=0;i<n;i++){
        cout << ans[i] <<endl;
    }
    return 0;

}

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

int main() {
	int n,current,cnt=0,s,ret=0,tmp;
	cin >> n;
	int* a[2];
	a[0] = new int[n];
	a[1] = new int[n];
	for (int i = 0; i < n; i++)	cin >> a[0][i];
	for (int i = 0; i < n; i++)	cin >> a[1][i];

	for (int i = 0; i < n; i++) {
		tmp = s = 0;
		for (int j = 0; j < n; j++) {
			tmp += a[s][j];
			if (i == j && s == 0) {
				s = 1;
				tmp += a[s][j];
			}
		}
		if (ret < tmp) {
			ret = tmp;
		}
	}
	cout << ret << endl;
	return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
  llong N;
  vector<llong> A;

  cin >> N;
  A.resize(N);
  bool ok = true;
  for (auto &in: A) {
    cin >> in;
    ok &= (in & 1) || in % 3 == 0 || in % 5 == 0;
  }

  if (ok) {
    cout << "APPROVED" << endl;
  }
  else {
    cout << "DENIED" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h> 
int main()
{
	int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(a<b&&b<c)
    {
    	printf("Yes\n");	
	}
	else 
	{
		printf("No\n");
	}
	
	return 0;	
}


Measured memory_bytes: 2032
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

fn main() {
    input! {
        h: usize, w: usize, m: usize,
        target: [(Usize1, Usize1); m],
    }

    let mut tset = HashSet::new();
    let mut ynum = vec![0; h];
    let mut xnum = vec![0; w];
    let mut ymax = 0;
    let mut xmax = 0;
    for &(y, x) in &target {
        tset.insert((x, y));
        ynum[y] += 1;
        ymax = max(ymax, ynum[y]);
        xnum[x] += 1;
        xmax = max(xmax, xnum[x]);
    }
    let mut ymaxpos = Vec::new();
    for (i, &num) in (0..).zip(&ynum) {
        if num == ymax {
            ymaxpos.push(i);
        }
    }
    let mut xmaxpos = Vec::new();
    for (i, &num) in (0..).zip(&xnum) {
        if num == xmax {
            xmaxpos.push(i);
        }
    }

    let mut ans = 0;
    'out: for &xpos in &xmaxpos {
        for &ypos in &ymaxpos {
            if tset.contains(&(xpos, ypos)) {
                ans = max(ans, xmax + ymax - 1);
            } else {
                ans = max(ans, xmax + ymax);
                break 'out;
            }
        }
    }
    println!("{}", ans);

}


Measured memory_bytes: 26340
use proconio::{input, fastout};
use std::cmp::max;

#[fastout]
fn main() {
    input!{
        N: i32,
        H: [i32; N],
    };
    let mut m: i32 = 0;
    let mut c: i32 = 0;
    let mut r: i32 = 0;

    for h in H.iter() {
        if *h <= m {
            c += 1;
        } else {
            c = 0;
        }
        m = *h;
        r = max(r, c);
    }
    println!("{}", r);
}


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

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

using namespace std;

using ll = long long;
using P = pair<int , int>;
  
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int r; cin >> r;
  cout << r * 2 * 3.1415926535897 << endl;
}


Measured memory_bytes: 3804
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,x[N],a[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > Q;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		a[x[i]]=i;
		for (int j=1;j<i;j++) Q.push(pii(x[i],i));
	}
	for (int i=1;i<=n*n;i++)
	if (a[i]){
		int id=a[i];
		for (int j=0;j<n-id;j++) Q.push(pii(1e9,id));
	}
	else{
		if (Q.empty()) return puts("No"),0;
		if (i>Q.top().first) return puts("No"),0;
		a[i]=Q.top().second;
		Q.pop();
	}
	puts("Yes");
	for (int i=1;i<=n*n;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}

Measured memory_bytes: 3696
L,N,*x=`dd`.split.map &:to_i
y=[r=0]+x.map{|e|L-e}.reverse
x=[0]+x
sx=[0]
sy=[0]
N.times{|i|sx<<sx[i]+x[i+1];sy<<sy[i]+y[i+1]}
N.times{|i|
	j=N-i
	k=[(i+1)-1,(j-1)].min
	r=[r,x[(i+1)]+2*(sx[(i+1)-1]-sx[(i+1)-k-1]+sy[(j-1)]-sy[(j-1)-k-((j-1)>k ? 1 : 0)])].max
}
N.times{|i|
	j=N-i
	k=[i,j-1].min
	r=[r,y[j]+2*(sx[i]-sx[i-k-(i>k ? 1 : 0)]+sy[j-1]-sy[j-k-1])].max
}
p r

Measured memory_bytes: 32960
#include<stdio.h>

int main(void) {

	int i,j;
	int h, w;

	while (1) {
		scanf("%d %d", &h, &w);

		if (h == 0 && w == 0) {
			break;
		}

		for (i = 0; i < h; i++) {
			for (j = 0; j < w; j++) {
				if (i == 0 || i == h - 1) {
					printf("#");
				}
				else if (j == 0 || j == w - 1) {
					printf("#");
				}
				else {
					printf(".");
				}
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;

}

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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

mt19937 rng( (int)chrono::steady_clock::now().time_since_epoch().count() );

struct Bit {
  vector<LL> a;
  Bit(int nNode) { a.assign(nNode, 0); }

  void upd(int pos, int val) {
    for (int i = pos; i < sz(a); i |= i + 1) a[i] += val;
  }
  LL get(int pos) {
    LL ret = 0;
    for (int i = pos; ~i; i = (i & (i + 1) ) - 1) ret += a[i];
    return ret;
  }
};

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafClover

  int n, m; cin >> n >> m;
  vector<LL> a(n);
  for (int i = 1; i < n; ++i) cin >> a[i], a[i] += a[i - 1];

  vector<vector<int> > b(n, vector<int>(m) );
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) cin >> b[i][j];
  }

  vector<stack<int> > st(m);
  for (int i = 0; i < m; ++i) st[i].emplace(n);

  LL ans = 0;
  Bit bit(n);
  for (int l = n - 1; ~l; --l) {
    for (int i = 0; i < m; ++i) {
      while (st[i].top() < n && b[ st[i].top() ][i] <= b[l][i]) {
        int tmp = st[i].top();
        st[i].pop();
        bit.upd(tmp, -b[tmp][i]);
        bit.upd(st[i].top(), b[tmp][i]);
      }
      bit.upd(l, b[l][i]);
      bit.upd(st[i].top(), -b[l][i]);
      st[i].emplace(l);
    }

    for (int r = l; r < n; ++r) asMx(ans, bit.get(r) - (a[r] - a[l]) );
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
string s, t;
ll dp2[3005][3005];
ll dp[3005][3005];
vector<char> v;
ll go(int i, int j) {
    if(i == s.length()) return 0;
    if(j == t.length()) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    ll ans;
    if(s[i] == t[j]) {
        ans = 1 + go(i+1, j+1);

        dp2[i][j] = 3;
    } else {
        ll x1 = go(i+1, j);
        ll x2 = go(i, j+1);
        ans = max(x1, x2);
        if(x1 > x2) {
            dp2[i][j] = 1;
        } else {
            dp2[i][j] = 2;
        }
    }
    return dp[i][j] = ans;
}
int main() {
    memset(dp, -1, sizeof(dp));
    cin>>s>>t;
    int i = 0, j = 0;
    go(0, 0);
    for(int i=0;i<s.length();i++) {
        for(int j=0;j<t.length();j++) {
            //cout<<dp2[i][j]<<" ";
        }
        //cout<<endl;
    }
    v.clear();
    while(i < s.length() && j < t.length()) {
        int goo = dp2[i][j];
        if(goo == 3) {
            //cout<<"i "<<i<<" j "<<j<<" "<<goo<<endl;
            v.pb(s[i]);
            i++;
            j++;
        } else if(goo == 2) {
            j++;
        } else if(goo == 1){
            i++;
        }
    }
    for(int i=0;i<v.size();i++) {
        cout<<v[i];
    }
    cout<<endl;
}


Measured memory_bytes: 141568
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const int INF=1e9;


int main(){
  int x,y;
  cin>>x>>y;

  if((y-2*x)%2==0 && y>=2*x && 2*x-y/2>=0){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;

  return 0;
  
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdint>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::pair;

using std::vector;
using std::sort;
using std::lower_bound;
using std::upper_bound;
using std::find_if;
using std::copy;
using std::copy_if;

int main(){
    long n;
    cin >> n;

    long max=0;
    for(long i=1;i*i<=n;i++){
        if(n%i==0){
            max=std::max(max,i);
        }
    }

    int count=0;
    long a=n/max;
    while(a>0){
        a/=10;
        count++;
    }

    cout << count << endl;
    return 0;
}



Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};



int main() {
    int N, M;
    cin >> N >> M;
    vector<string> f;
    vector<string> g;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        f.push_back(s);        
    }
    for (int i = 0; i < M; i++) {
        string s;
        cin >> s;
        g.push_back(s);        
    }

    bool ans = false;
    for (int i = 0; i < N - M + 1; i++) {
        for (int j = 0; j < N - M + 1; j++) {
            bool flag = true;
            for (int k = 0; k < M; k++) {
                for (int l = 0; l < M; l++) {
                    if (g[k][l] != f[k + i][j + l]) {
                        flag = false;
                    }
                }
            }
            if (flag) {
                ans = true;
            }
        }
    }
    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
	int N; cin >> N;
	int a[110], S=0;
	for(int i=0; i<N; ++i){
	    cin >> a[i];
	    S += a[i];
	}
	int out=0;
	for(int i=1; i<N; ++i){
	    if(abs(S-a[out]*N)>abs(S-a[i]*N)) out=i;
	}
	cout << out << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

import itertools

A = []
for i in range(1,n+1):
    A.append(i)
    
p = itertools.permutations(A,n)
p = list(p)

for i in range(len(p)):
    p[i] = list(p[i])


print(abs(p.index(P)-p.index(Q)))

Measured memory_bytes: 12276
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i++)
	{
		cout << "x";
	}

	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pii pair<int,int>
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second

int main()
{   fastio ;
    int n,i ;
    cin>>n ;
    int a[n] ;
    for (i = 0; i < n; ++i)
    {
    	cin>>a[i] ;
    }
    int dp[n] ;
    dp[0]=0 ;
    dp[1]=abs(a[1]-a[0]) ;
    for (i = 2; i < n; ++i)
    {   dp[i]=min(abs(a[i]-a[i-1])+dp[i-1],abs(a[i]-a[i-2])+dp[i-2]) ;
    	
    }
    cout<<dp[n-1]<<"\n" ;
    return 0;
}    

Measured memory_bytes: 1024
#include <string>
#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  int num_queue, num_query;
  int cmd, index, val;

  cin >> num_queue >> num_query;
  queue<int> q[num_queue];

  for (int i = 0; i < num_query; i++) {
    cin >> cmd;

    switch (cmd) {
      // enqueue
      case 0:
        cin >> index >> val;
        q[index].push(val);

        break;

      case 1:
        cin >> index;
        if (!q[index].empty()) {
          cout << q[index].front() << endl;
        }

        break;

      case 2:
        cin >> index;
        if (!q[index].empty()) {
          q[index].pop();
        }
        break;
    }
  }
}




Measured memory_bytes: 4460
//https://codeforces.com/contest/1083/problem/E
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

struct Line {
        mutable ll k, m, p;
        bool operator<(const Line& o) const { return k < o.k; }
        bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
        // (for doubles, use inf = 1/.0, div(a,b) = a/b)
        const ll inf = LLONG_MAX;
        ll div(ll a, ll b) { // floored division
                return a / b - ((a ^ b) < 0 && a % b); }
        bool isect(iterator x, iterator y) {
                if (y == end()) { x->p = inf; return false; }
                if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
                else x->p = div(y->m - x->m, x->k - y->k);
                return x->p >= y->p;
        }
        void add(ll k, ll m) {
                auto z = insert({k, m, 0}), y = z++, x = y;
                while (isect(y, z)) z = erase(z);
                if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
                while ((y = x) != begin() && (--x)->p >= y->p)
                        isect(x, erase(y));
        }
        ll query(ll x) {
                assert(!empty());
                auto l = *lower_bound(x);
                return l.k * x + l.m;
        }
};
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N; ll C; 
        cin >> N >> C;
	vector<ll> A(N);
        for(auto &x : A)cin >> x;
	LineContainer dp; dp.add(2ll*A[0],-A[0]*A[0]);
	ll res = 0;
	forn(i,1,N){
		ll tmp = A[i]*A[i]-dp.query(A[i])+C;
                //cout << i+1 << ' ' << dp.query(A[i]) << ' ' << tmp << ":D\n";
                if(i == N-1)res = tmp;
		dp.add(2ll*A[i],-tmp-A[i]*A[i]);
	}
	cout << res << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
*/

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

const int mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> C(n);
    rep(i, n) cin >> C[i];
    sort(C.begin(), C.end(), greater<int>());
    vector<ll> twoexp(n);
    twoexp[0] = 1;
    rep(i, n-1) twoexp[i+1] = (twoexp[i]*2)%mod;
    ll ans = 0;
    rep(i, n) {
      ll tmp = twoexp[i];
      if (i > 0) tmp += twoexp[i-1] * i;
      tmp %= mod;
      tmp *= C[i];
      tmp %= mod;
      tmp *= twoexp[n-i-1];
      tmp %= mod;
      ans += tmp;
      ans %= mod;
    }
    ans *= twoexp[n-1] * 2;
    ans %= mod;
    cout << ans << endl;
}

Measured memory_bytes: 5640
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }

int main() {
   int A, B, T;
   cin >> A >> B >> T;
   cout << T / A * B << endl;
   return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define mp make_pair
#define pb(x) push_back(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()

#define INF 2123456789
#define IINF 9123456789123456789

void use_cio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}
// template <typename... Args>
// void dbg(Args... args) {
//     ((cout << args << " "), ...);
//     cout << endl;
// }

//--------------------------------------------------//
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << max({a, b, c}) - min({a, b, c});
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int len = s.length();
    int k = 0;
    if(s.charAt(0) == s.charAt(len - 1)) k = 1;
    String ans = "First";
    if(((len - k) % 2) == 0) ans = "Second";
    System.out.println(ans);
  }
}

Measured memory_bytes: 24432
#include"bits/stdc++.h"
//#include<boost/multi_array.hpp>
//#include<boost/optional.hpp>
//#include<boost/range/irange.hpp>
//#include<boost/range/algorithm.hpp>
//#include<boost/range/adaptors.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();

void Main() {
	string n;
	cin >> n;
	int sum = 0;
	rep(i, n.size()){
		sum += int(n[i] - '0');
	}
	
	if (sum % 9 == 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

int main() {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3740
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define ABS(x) (((x) > 0 ) ? (x) : (-(x)))
#define MAX2(x, y) (((x) > (y)) ? (x) : (y))
#define MIN2(x, y) (((x) < (y)) ? (x) : (y))
#define MAX3(x, y, z) ( (x) > (y)  ? ( (x) > (z) ? (x) : (z)  ) : ( (y) > (z) ? (y) : (z) )  )
#define MIN3(x, y, z) ( (x) < (y)  ? ( (x) < (z) ? (x) : (z)  ) : ( (y) < (z) ? (y) : (z) )  )
#define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2))


#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 987654321
#define IINF 987654321987654321

int N,M,K,T;
char a[100][100]; char b[100][100];
int main(void){
	geti(N,M);
	rep(i,N) scanf("%s",a[i]);
	rep(j,M) scanf("%s",b[j]);

	for(int i=0;i+M-1<N;i++){
		for(int j=0;j+M-1<N;j++){
			bool ok = true;
			for(int ii=0;ii<M;ii++){
				for(int jj=0;jj<M;jj++){ 
					if( a[i+ii][j+jj] != b[ii][jj] ) ok = false;
				}
			}
			if( ok ){
				cout << "Yes" << endl; return 0;
			}
		}
	}
	cout << "No" << endl;

}

Measured memory_bytes: 256
/*------------------------------------
.......Bismillahir Rahmanir Rahim.....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <functional>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi   vector<int> 
#define   co(x)  cout << x << '\n' 
#define   dbg(x)  cerr << #x << " = " << x << '\n' 
#define   bitcount(x)  (int)__builtin_popcount(x) 
#define   fast  ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
#define   sz(x)  (int)x.size()
#define   all(a) a.begin(),a.end() 
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve() { 
    int  n, goal ; 
    cin >> n >> goal ; 
    vi  b(n), bonus(n) ; 
    for (int i=0;i<n;i++) { 
        cin >> b[i] >> bonus[i] ; 
    } 
    int ans = 1e9 ; 
    for (int bit=0;bit<(1<<n);bit++) { 
        int cur = 0, cnt = 0 ; 
        int k = bitcount(bit) ; 
        vi  curb(k), curbb(k), curbonus(k) ; 
        int i = 0 ; 
        for (int j=0;j<n;j++) { 
            if (bit&(1<<j)) { 
                cur += b[j]*(j+1)*100 + bonus[j] ; 
                cnt += b[j] ; 
                curb[i] = b[j] ; 
                curbb[i] = (j+1)*100 ; 
                curbonus[i] = bonus[j] ; 
                i++;
            } 
        } 
        if (cur >= goal) { 
            for (int i=0;i<(1<<k);i++) { 
                int tmp = cur, c = cnt ; 
                for (int j=0;j<k;j++) { 
                    if (i&(1<<j)) { 
                        if (tmp - curbonus[j] - curbb[j] >= goal ) { 
                            c--; tmp -= (curbonus[j] + curbb[j]) ; 
                            int x = curb[j]-1;
                            while ((x>0) and (tmp - curbb[j] >= goal) ){
                                tmp -= curbb[j] ; 
                                c-- ; x-- ; 
                            }
                        } 
                    }
                }
                if (tmp>=goal) ans = min(ans, c) ; 
            }
        }
    } 
    co ( ans ) ; 
} 
 
signed main() 
{ 
    // fast ; 
    int n=1; // cin>>n; 
    while (n--) solve(); 
    return 0; 
} 
 

Measured memory_bytes: 3612
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#include <bitset>
#define LL long long

using namespace std;

int main() {
    int n, count = 0, rem = 0;
    cin >> n;
    map<string, int> map;
    for (size_t i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if (tmp <= 399)
        {
            if (map.find("灰") == map.end())
            {
                map.insert(make_pair("灰", 1));
                count++;
            }
        }
        else if (tmp <= 799)
        {
            if (map.find("茶") == map.end())
            {
                map.insert(make_pair("茶", 1));
                count++;
            }
        }
        else if (tmp <= 1199)
        {
            if (map.find("緑") == map.end())
            {
                map.insert(make_pair("緑", 1));
                count++;
            }
        }
        else if (tmp <= 1599)
        {
            if (map.find("水") == map.end())
            {
                map.insert(make_pair("水", 1));
                count++;
            }
        }
        else if (tmp <= 1999)
        {
            if (map.find("青") == map.end())
            {
                map.insert(make_pair("青", 1));
                count++;
            }
        }
        else if (tmp <= 2399)
        {
            if (map.find("黄") == map.end())
            {
                map.insert(make_pair("黄", 1));
                count++;
            }
        }
        else if (tmp <= 2799)
        {
            if (map.find("橙") == map.end())
            {
                map.insert(make_pair("橙", 1));
                count++;
            }
        }
        else if (tmp <= 3199)
        {
            if (map.find("赤") == map.end())
            {
                map.insert(make_pair("赤", 1));
                count++;
            }
        }
        else
        {
            rem++;
        }
    }
    if (rem>0&& map.size()==0)
    {
        count = 1;
        rem--;
    }

    int count2 = count;
    for (;rem > 0;)
    {
            count2++;
            rem--;
    }
    cout << count << " " << count2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn (int)(2e5)
#define i64 long long
#define pii pair<i64,i64>
#define all(x) x.begin(),x.end()
#define LB(x,v) lower_bound(all(x), v) - x.begin()
#define fread() freopen("in.txt", "r", stdin);
using namespace std;

struct Point { 
    double x,y; 
    // Constructor 
    //Point(double _x, double _y) : x(_x), y(_y) {} 
}point[10]; 

int pos[10];

void init(int n){
    for(int i=1;i<=n;i++) pos[i] = i;
}

int fac(int n){
    return n <= 1 ? 1 : n*fac(n-1);
}

double dist(Point p1, Point p2){
    double dx = p1.x - p2.x, dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}
int main() {
    /*BEFORE SUBMIT, CHECK
    sample i/o format
    statements for debugging are removed/comment out
    global values / stl containers are initialized/cleared for each test (if needed)
    all array size are sufficient
    loop variable or output value doesn't cross min/max limit of input
    */
    // #ifndef ONLINE_JUDGE
    //     fread();
    // #endif

    int n;    

    while(scanf("%d",&n)==1){
        init(n);
        for(int i=1;i<=n;i++){
            scanf("%lf %lf", &point[i].x , &point[i].y);
        }
        double total = 0.0;
        do{
            //double sum = 0.0;
            for(int i=1;i<n;i++){
                total += dist(point[pos[i]], point[pos[i+1]]);
            }
        }while(next_permutation(pos+1,pos+n+1));  

        printf("%lf\n", total / fac(n));  
    }   
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll dfs(ll x, vector<vector<ll>> &g, vector<bool> &see,vector<ll> &cl,vector<ll> &ans,vector<ll> &c,vector<stack<ll>> &cn,vector<ll> &par)
{
  ll chi=0;
  //点xに対する処理
  see[x] = 1;
  ll p=-1;
  if(!cn[c[x]].empty())p=cn[c[x]].top();
  cn[c[x]].push(x);
  for (auto r : g[x])
  {
    if (see[r])continue;
    //進む辺に対する処理（これは木構造でオイラーツアーするために使う）
    cl[x]=0;
    ll chit=dfs(r, g, see,cl,ans,c,cn,par)+1;
    ans[c[x]]-=(chit+cl[x])*(chit+cl[x]+1)/2;
    //戻る辺に対する処理
    chi+=chit;
  }
  //点xの親に戻る時の処理
  if(p==-1){
    par[c[x]]-=chi+1;
  }
  else{
    cl[p]-=chi+1;
  }
    cn[c[x]].pop();
  return chi;
}

int main()
{
ll n;
cin >> n ;
vector<ll> ans(n,n*(n+1)/2);
vector<ll> cl(n,0);
vector<ll> par(n,n);
vector<stack<ll>> cn(n);
vector<bool> see(n,0);
vector<ll> c(n,0);
rep(i, n){
  ll cc;
  cin >> cc;
  c[i]=cc-1;
}
vector<vector<ll>> g(n);
rep(i, n-1)
{
  ll a, b;
  cin >> a >> b;
  g[a - 1].push_back(b - 1);
  g[b - 1].push_back(a - 1); 
}
dfs(0,g,see,cl,ans,c,cn,par);
rep(i,n)cout << ans[i]-par[i]*(par[i]+1)/2 << endl;
return 0;
}

Measured memory_bytes: 178208
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste

// #include "UnionFind.hpp"
// #include "power.hpp"

bool sorting(pair<int, int> &a, pair<int, int> &b) {
    return a.second > b.second;
}

signed main() {
    int N, M;
    cin >> N >> M;
    priority_queue<int, vector<int>, greater<int>> A;
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        A.push(temp);
    }
    vector<pair<int, int>> swapNumber(M);
    for (int i = 0; i < M; i++) {
        cin >> swapNumber[i].first >> swapNumber[i].second;
    }
    sort(swapNumber.begin(), swapNumber.end(), sorting);
    int ans = 0;
    int coordinate = 0;
    while(!A.empty()) {
        int swapSize = swapNumber[coordinate].first;
        int number = swapNumber[coordinate].second;
        for (int i = 0; i < swapSize; i++) {
            if (A.empty()) break;
            if (A.top() >= number) {
                break;
            } else {
                ans += number;
                A.pop();
            }
        }
        ++coordinate;
        if (coordinate == M) break;
    }
    while (!A.empty()) {
        ans += A.top();
        A.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 2676
import heapq
N,K = map(int,input().split())
td = [list(map(int,input().split())) for i in range(N)]
td.sort(key = lambda x:-x[1])
sumn = [[] for i in range(N)]
for i in range(N):
    heapq.heapify(sumn[i])
ans = 0
kind = {}
for t,d in td[:K]:
    if t not in kind:
        kind[t] = 1
    else:
        kind[t] += 1
    heapq.heappush(sumn[t-1],d)
kinds = len(kind)
ans = sum(sum(i) for i in sumn)
ans1 = ans +kinds**2
rem = td[K:]
nex = 0
candel = []
heapq.heapify(candel)
for k,v in kind.items():
    for i in range(v-1):
        heapq.heappush(candel,heapq.heappop(sumn[k-1]))
if candel:
    qd = heapq.heappop(candel)
    while K+nex < N:
        if td[K+nex][0] not in kind:
            kind[td[K+nex][0]] = 1
            kinds += 1
            ans = ans - qd + td[K+nex][1]
            ans1 = max(ans1,ans+kinds**2)
            nex += 1
            if candel:
                qd = heapq.heappop(candel)
            else:
                break
        else:
            nex += 1
print(ans1)

Measured memory_bytes: 40120
import sys
input = sys.stdin.readline


def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out


def main():
    n, k = map(int, input().split())
    print(len(Base_10_to_n(n, k)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
k = int(input())
s =  "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1,  51"
l = s.split(",")
print(int(l[k-1]))

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
string arr[3]={"3","5","7"};
int ans=0;
long long N;
bool check_753(string s)
{
  	bool flag_7=false, flag_5=false, flag_3=false;
  	for(long long i=s.size()-1; i >=0; --i){
     	if(s[i]=='7'){
          	flag_7 = true;
        }
      	else if (s[i]=='5'){
         	 flag_5 = true;
        }
      	else if (s[i]=='3'){
         	flag_3 = true; 
        }
      	else{
         	return false; 
        }
    }
  	if (flag_7 && flag_5 && flag_3)
  		return true;
  	else
      	return false;
}
 
int func(string s)
{
  	long long num=stoll(s);
 	if(num>N){
      	return 0; 
    }
  	if (check_753(s)){
     	 ans+=1;
    }
  
  	for(int i=0; i < 3;++i)
    {
     	ans+= func(s+arr[i]);
    }
  	
  	return 0;
}


int main(){

  	cin >> N;
	if(N < 10){
      cout << 0 << endl;
  	  return 0;
    }
  	for(int i=0; i < 3; ++i)
  		func(arr[i]);
 
 
  	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

class AABCARC {
public:
	void solve(istream& in, ostream& out) {
        int x;
        in >> x;
        if(x < 1200) out << "ABC" << endl;
        else out << "ARC" << endl;
	}
};

int main() {
	AABCARC solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Measured memory_bytes: 256