akhauriyash/Code-Regression huggingface dataset:
use std::io::stdin;
use std::str::FromStr;
use std::cmp::max;
use std::cmp::min;

fn read_line<T>() -> Vec<T>
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect()
}

fn read_str_as_char_vec() -> Vec<char> {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().chars().collect()
}

fn read_str_as_T<T>() -> T 
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().unwrap()
}

// fn binary_search(x: usize, a: usize, b: usize, n: usize) -> usize {
//     if x == 0 || x == n {
//         let left = a * x / b;
//         let right = a * (x / b);
//         left - right;
//     }
//     let left_x = x - 1;
//     let right_x = x + 1;
// 
//     let res = a * x / b - a * (x / b);
//     let left_res = a * left_x / b - a * (left_x / b);
//     let right_res = a * right_x / b - a * (right_x / b);
//     if left_res > res {
//         ;
//     }
// 
//     max(binary_search(), ())
// }

fn main() {
    let in_vec: Vec<usize> = read_line();
    let a = in_vec[0];
    let b = in_vec[1];
    let n = in_vec[2];

    let mut res = 0;
    let mut x: usize = 0;
    let fin = min(b, n);
    while x <= fin {
        // println!("{}", x);
        res = max(res, a * x / b - a * (x / b));
        x += max(min((b - a * x % b) / a, b - x % b), 1);
//         if x == 0 {
//             x += 1;
//             continue;
//         } else {
//             if max(b, a * x) >= min(a * x, b) {
//                 if b >= x{
//                     x += min(b - a * x % b, b - x % b);
//                     continue;
//                 }
//             }
//             break;
//             // x += min(max(b - a * x, 1), max(b - x, 1));
//         }
    }
    // for x in 0..=min(b, n) {
    //     let left = a * x / b;
    //     let right = a * (x / b);
    //     res = max(res, left - right);
    // }
    
    println!("{}", res);

    //let temp = 1_000_000_000_000 - (1_000_000_000_000 % b);
//    let temp = n - (n % b) - 1;
    // let x:usize;
    // let left:usize;
    // let right:usize;
    // if n >= n % b + 1 {
    //     x = n - (n % b) - 1;
    //     left = (a * x) / b;
    //     right = a * (x / b);
    //     println!("AA");
    // } else {
    //     let x_1 = 1;
    //     let left_1 = (a * x_1) / b;
    //     let right_1 = a * (x_1 / b);

    //     let x_2 = n;
    //     let left_2 = (a * x_1) / b;
    //     let right_2 = a * (x_1 / b);

    //     if left_1 - right_1 < left_2 - right_2 {
    //         left = left_2;
    //         right = right_2;
    //     println!("BB");
    //     } else {
    //         left = left_1;
    //         right = right_1;
    //     println!("CC");
    //     }
    // }
    // println!("{}, {}", left, right);
    // println!("{}", left - right);
}


Measured memory_bytes: 2144
#include<cstdio>
#include<algorithm>
long long int abs(long long int n){
	if(n<0)return -n;
	return n;
}
int main(){
	int n;
	scanf("%d",&n);
	long long int a[n]={};
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		a[i]=a[i]-i;
	}
	long long int ans=0;
	std::sort(a,a+n);
	if(n%2==1){
		long long int l=a[n/2];
		for(int i=0;i<n;i++){
			ans+=abs(a[i]-l);
		}
	}else{
		long long int l=a[n/2-1];
		long long int m=a[n/2];
		long long int anss=0;
		for(int i=0;i<n;i++){
			ans+=abs(a[i]-l);
		}
		for(int i=0;i<n;i++){
			anss+=abs(a[i]-m);
		} 
		ans=std::min(ans, anss);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<stdio.h>

using namespace std;

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

  string s;
  cin >> s;
  string res = "NA";

  int num = atoi(s.c_str());

  int bottom2 = num % 100;
  int top2 = num/100;

  bool flag_bottom = false;
  bool flag_top = false;

  if(bottom2 <= 12 && bottom2 >= 1) flag_bottom = true;
  if(top2 <= 12 && top2 >= 1) flag_top = true;

  if(flag_bottom){
    if(flag_top){
       res = "AMBIGUOUS";
     }else{
       res = "YYMM";
  }
  }else{
    if(flag_top) res = "MMYY";
  }

  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
using pii=pair<int,int>;
using vs=vector<string>;
using vpii=vector<pii>;
using si=set<int>;

#define REP(i,a) for(int i=0;i<a;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rREP(i,a) for(int i=(a)-1;i>=0;i--)
#define rFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define out(S) cout<<(S)<<endl;
#define beginend(v) (v).begin(),(v).end()
#define IfOut(condition,text) if(condition){out(text);return 0;}
#define IfOutElse(condition,if_text,else_text) if(condition){out(if_text);return 0;}else{out(else_text);return 0;}
#define mod(s) ((s)%(ll)(1e9+7))
ll modpow(ll i, ll j) { ll tmp = 1; while (j) { if (j % 2)tmp = mod(tmp*i); i = mod(i*i); j /= 2; }return tmp; }
#define divmod(a,b) (mod(a*modpow((ll)b,(ll)(1e9+5))))
#define pb(i) push_back(i)
#define fst first
#define snd second
#define Foreach(item,collection) for(auto item:collection)
#define INF 1e10
#define removeAll(vec,deleg) auto itr=remove_if(beginend(vec),deleg);vec.erase(itr,vec.end());
void removeAt(string& s, int index) { s.erase(index, 1); }
template<typename T> void removeAt(vector<T>& v, int index) { v.erase(v.begin() + index); }
ll manhattanDistance(ll x1, ll y1, ll x2, ll y2) { return (abs(x2 - x1) + abs(y2 - y1)); }
vector<ll> sieveOfEratosthenes(int max) {ll prime;double sqrtmax = sqrt(max);vector<ll> primeVec, searchVec;FOR(i, 2, max + 1) searchVec.push_back(i);do{prime = searchVec[0];primeVec.push_back(prime);auto itr = remove_if(beginend(searchVec), [=](ll x)->bool {return x%prime == 0; });searchVec.erase(itr, searchVec.end());} while (prime < sqrtmax);primeVec.reserve(primeVec.size() + searchVec.size());primeVec.insert(primeVec.end(), beginend(searchVec));return primeVec;}
ll sum(vi v) {ll sum=0;Foreach(i,v){sum+=i;}return sum;}
#define ShowAll(v) Foreach(i,v) out(i);

int shouhi(int v,int x,int y){
    double motone=(double)v*100.0/(100.0+x);
    return motone*(100.0+y)/100.0;
}

int main(){
    vi ans;
    int m,nmin,nmax;
    while (cin>>m>>nmin>>nmax,(m||nmin||nmax))
    {
        vi P(m);
        REP(i,m)cin>>P[i];
        int n=nmin-1,pmax=0;
        FOR(i,nmin-1,nmax){
            if(pmax<=P[i]-P[i+1]){
                pmax=P[i]-P[i+1];
                n=i;
            }
        }
        ans.pb(n+1);
    }
    
    ShowAll(ans);
    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int cek(double x,double need)
{
	int i=0;
	while(x<need)
	{
		x*=2;
		i++;
	}
	return i;
}
int main()
{
	double long n,k;
	cin>>n>>k;
	int x;
	double long ans=0;
	for(x=1;x<=n;x++)
	{
		if(x<k)
		{
		ans+=1/((pow(2,cek(x,k))));
		}
		else
		{
			ans+=1;
		}
	}
	
	cout<<fixed<<setprecision(9)<<(1/n)*ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional> //sort(A,A.end(),greater<int>());???????????????
#include <queue>
#include <stack>
#include <vector>

#define INF 10 << 10

int dp[2048] = { 0 };

int main() {

	int n, k;
	cin >> n >> k;
	vector<int> cg[16],list[16];
	for (int i = 0; i < n; ++i) {
		int c, g;
		cin >> c >> g;
		cg[g].push_back(c);
	}
	for (int i =1; i <= 10; ++i) {
		if (cg[i].empty()) continue;
		sort(cg[i].begin(), cg[i].end(), greater<int>());
		list[i].push_back(cg[i][0]);
		for (int i2 = 1; i2 < cg[i].size(); ++i2) {
			int sum = 0, cnt = 0;
			for (int j = i2; j >= 0; --j) { sum += cg[i][j]; cnt++; }
			list[i].push_back(sum + (cnt - 1)*cnt);
		}
	}
	for (int i = 1; i <= 10; ++i) {
		if (list[i].empty()) continue;
		for (int j = k; j >= 0; --j) {
			for (int i2 = 0; i2 < list[i].size() && j - (i2 + 1) >= 0; ++i2) {
				dp[j] = max(dp[j - (i2+1)] + list[i][i2], dp[j]);
			}
		}
	}

	cout << dp[k] << endl;

	return 0;
}

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

//#define int long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

int main(){
    int N,K;
    cin>>N>>K;
    string S;
    cin>>S;
    S[K-1]=S[K-1]+0x20;
    cout<< S <<endl;
}

Measured memory_bytes: 256
//============================================================================
// Name        : ProjG.cpp
// Author      : Yong Kiat
// Version     :
// Copyright   : By Algotae.
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>

using namespace std;

int n, m, dp[100001], x, y, res;
vector<int> adj[100001];

int f(int u) {
	if (dp[u]) return dp[u];

	for (int v : adj[u]) {
		dp[u] = max(dp[u], f(v));
	}
	dp[u]++;

	return dp[u];
}

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

    cin >> n >> m;

    while (m--) {
    	cin >> x >> y, x--, y--;
    	adj[x].push_back(y);
    }

    for (int i = 0; i < n; i++) {
    	res = max(res, f(i));
    }

    cout << res - 1;
}


Measured memory_bytes: 7424
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#include<map>
#include<cctype>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

char a;
int main(void) {
	cin >> a;
	if (a == 'a' || a == 'i' || a == 'u' || a == 'e' || a == 'o')ct("vowel");
	else ct("consonant");
	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
    char A[3];
    scanf("%s",A);
    if(A[0] == A[1] && A[1] == A[2]){
        printf("%s","No");
    }else printf("%s","Yes");
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();
        if(X >= Y){
            System.out.println("War");
            return;
        }
        int a = -100;
        int b = 100;
        for(int i = 0;i < N;i++)    a = Math.max(a, sc.nextInt());
        for(int i = 0;i < M;i++)    b = Math.min(b, sc.nextInt());
        if(a < b && a < Y && X < b)   System.out.println("No War");
        else    System.out.println("War");
    }
}

Measured memory_bytes: 21844
fun main(args: Array<String>) {
    val aArray = Array(3) { readIntegerList().map { Pair(it, false) }.toTypedArray() }
    val n = readInteger()
    repeat(n) {
        val b = readInteger()
        for (i in aArray.indices) {
            for (j in aArray[i].indices) {
                if (aArray[i][j].first == b) {
                    aArray[i][j] = Pair(aArray[i][j].first, true)
                }
            }
        }
    }
    
    for (i in 0..2) {
        val trueCount = aArray[i].count { it.second }
        if (trueCount == 3) {
            println("Yes")
            return
        }
    }

    for (i in 0..2) {
        var trueCount = 0
        for (j in 0..2) {
            if (aArray[j][i].second) {
                trueCount++
            }
        }

        if (trueCount == 3) {
            println("Yes")
            return
        }
    }

    if (aArray[0][0].second && aArray[1][1].second && aArray[2][2].second) {
        println("Yes")
        return
    }

    if (aArray[0][2].second && aArray[1][1].second && aArray[2][0].second) {
        println("Yes")
        return
    }
    
    println("No")
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 37756
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair <int,int> PAIR;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
int p[maxn];

int main()
{	
	int n,x;
	ll ans = 0;
	scanf("%d",&n);
	memset(p,0,sizeof(p));
	for(int i = 1;i <= n;++i){
		scanf("%d",&x);
		ans += x;
		p[x]++;
	}
	
	int q,u,v;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&u,&v);
		if(!p[u]) printf("%lld\n",ans);
		else{
			ans -= (ll)p[u]*(ll)u;
			ans += (ll)p[u]*(ll)v;
			p[v] += p[u];
			p[u] = 0;
			printf("%lld\n",ans);
		}
	}
	return 0;
}


Measured memory_bytes: 4148
#include<iostream>
#include<string>
#include<map>
#include<vector>
#define rep(i,a) for(int i=0;i<a;i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
	int n,m;
	cin>>n;
	map<string,int>tmp;
	vi ne(n);
	rep(i,n){
		string s;
		cin>>s>>ne[i];
		tmp[s]=i;
	}
	cin>>m;
	vi in1,in2;
	rep(i,m){
		string a,b;
		cin>>a>>b;
		in1.pb(tmp[a]);
		in2.pb(tmp[b]);
	}
	rep(i,m)
		rep(j,m)
			ne[in1[j]]=ne[in2[j]]=min(ne[in1[j]],ne[in2[j]]);
	int sum=0;
	rep(i,n)sum+=ne[i];
	cout<<sum<<endl;
}

Measured memory_bytes: 1836
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int min(int a, int b) {
    if(a >= b) {
        return b;
    }
    else {
        return a;
    }
}


int main(void) {
    int N;
    scanf("%d", &N);
    int *h, *dp, *c;
    h = (int*)malloc(N * sizeof(int));
    dp = (int*)malloc(N * sizeof(int));
    c = (int*)malloc((N-1) * sizeof(int));

    int i;
    for(i=0; i<N; i++) {
        scanf("%d", &h[i]);
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    dp[1] = abs(h[1]-h[0]);

    for(i=2; i<N; i++) {
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    }

    printf("%d\n", dp[N-1]);

    return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

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

  if(a == b)
    cout << "H" << endl;
  else
    cout << "D" << endl;
  ret 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007

int h,w;

int main(){
  int ans=0;
  cin >> h >> w;
  vector<vector<int>> vv = vector<vector<int>>(h, vector<int>(w, 0));
  vector<vector<int>> vvl = vector<vector<int>>(h, vector<int>(w, 0));
  vector<vector<int>> vvr = vector<vector<int>>(h, vector<int>(w, 0));
  vector<vector<int>> vvu = vector<vector<int>>(h, vector<int>(w, 0));
  vector<vector<int>> vvd = vector<vector<int>>(h, vector<int>(w, 0));
  string s;
  REP(i,h){
    cin>>s;
    REP(j,w){
       if (s[j]=='.') vv[i][j]=1;
    }
  }
  
  int flg=0;
  REP(i,h){
    flg=0;
    REP(j,w){
      if (vv[i][j]==1){
        flg++;
      }else{
        flg=0;
      }
      vvl[i][j]=flg;
    }
  }
  
  
  REP(i,h){
    flg=0;
    for(int j=w-1;j>=0;j--){
      if (vv[i][j]==1){
        flg++;
      }else{
        flg=0;
      }
      vvr[i][j]=flg;
    }
  }
  
  REP(j,w){
    flg=0;
    REP(i,h){
      if (vv[i][j]==1){
        flg++;
      }else{
        flg=0;
      }
      vvu[i][j]=flg;
    }
  }
  
  
  REP(j,w){
    flg=0;
    for(int i=h-1;i>=0;i--){
      if (vv[i][j]==1){
        flg++;
      }else{
        flg=0;
      }
      vvd[i][j]=flg;
    }
  }
  
  REP(i,h){
    REP(j,w){
      vv[i][j]=vvr[i][j]+vvl[i][j]+vvu[i][j]+vvd[i][j]-3;
      ans=max(ans,vv[i][j]);
    }
  }
  
  
  
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 78720
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
#include <iostream>  
using namespace __gnu_pbds;  
using namespace std;
#define ll long long
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update>  ordered_set;
using namespace std;
 
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (long long i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
#define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define fillinf(ar, n) fr(i,0,(n)) ar[i] = INF
#define debug(x) cout<<#x<<": "<<x<<endl
#define arr1d(a,n) cout << #a << " : "; fr(_,1,n) cout << a[_] << ' '; cout << endl;
#define arr1d0(a,n) cout << #a << " : "; rep(_,n) cout << a[_] << ' '; cout << endl;
#define arr2d(a,n,m) cout << #a << " :" << endl; fr(_,1,n) {fr(__,1,m) cout << a[_][__] << ' '; cout << endl;}
#define arr2d0(a,n,m) cout << #a << " :" << endl; rep(_,n) {rep(__,m) cout << a[_][__] << ' '; cout << endl;}


#define ull unsigned long long
#define ld long double
#define ui unsigned int
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define y0 yyyyyy0
auto clk=clock();
#define y1 yyyyyy1
#define setb __builtin_popcount
#define BIT(n) (1<<(n))
#define SQR(x) ((x) * (x))
#define CUBE(x) ((x) * (x) * (x))
#define LSOne(S) (S) & (-S)
inline bool EQ(double a, double b) {return fabs(a - b) < 1e-9;}
 
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;


 
inline int two(int n) {return 1 << n;}
inline int isOnBit(int n, int b) {return (n >> b) & 1;}
inline void onBit(int & n, int b) {n |= two(b);}
inline void offBit(int & n, int b) {n &= ~two(b);}
inline int lastBit(int n) {return n & (-n);}
inline int cntBit(int n) {int res = 0; while(n && ++res) n -= n &(-n); return res;}
 
#define INP "test.inp"
#define OUT "test.out"
 
#define PI 3.1415926535897932385
#define INF 10000000000000000ll
#define EPS 1e-7
#define MAXN 100000
#define MOD 998244353
#define dec decr
#define endl '\n'
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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


    int n;
    cin>>n;
    vector<long long> dp(n+1);
    vi v(n);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        dp[i]=2LL*dp[i-1];
    }
    rep(i,n){
        cin>>v[i];
    }
    sort(all(v));
    double ans=0;
    for(int i=n-1;i>0;i--){
        ans+=(double)((double)v[i]/(double)dp[(n)-i]);
    }
    ans+=(double)((double)v[0]/(double)dp[(n-1)]);
    cout<<ans;
    
    return 0;
}   

Measured memory_bytes: 256
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

ll solve(ll i)
{
	if (i == 1)
		return 1;
	return (1 + 2 * solve(i / 2));
}

void solve()
{
	ll h;
	cin >> h;
	cout << solve(h) << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t start, stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for (int tc = 1; tc < t + 1; tc++)
		solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ACはうれCすぎてうれD */

int main(void){ 
    int n;
    cin >> n;
    vector<ll> A;
    for(int i=0; i<n; i++){
        ll tmp_a;
        cin >> tmp_a;
        A.push_back(tmp_a);
    }

    // 上からの累積わ
    vector<ll> top;
    top.push_back(0);
    for(int i=0; i<n; i++){
        top.push_back(top[i] + A[i]);
    }

    // 下からの累積わ
    vector<ll> bottom;
    bottom.push_back(0);
    for(int i=n-1; i>=0; i--){
        bottom.push_back(bottom[n-i-1] + A[i]);
    }

    ll ans = 10000000000;
    for(int i=1; i<n; i++){
        ll tmp_ans = abs(top[i] - bottom[n-i]);
        if(tmp_ans < ans){
            ans = tmp_ans;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 6384
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define INF 1000000007
using namespace std;

int main(void){
	int n,ans=0;
	string s;
	cin >> n >> s;
	for(int i=0; i<n; i++){
		int count=0;
		for(char c='a'; c<='z'; c++){
			int flag1=0,flag2=0;
			for(int j=0; j<i; j++){
				if(s[j]==c)flag1=1;
			}
			for(int j=i; j<n; j++){
				if(s[j]==c)flag2=1;
			}
			if(flag1&&flag2)count++;
		}
		ans=max(ans,count);
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
    int n; cin >> n;
    vector<int>p(n);
    vector<int>a(n,0),b(n);
    for(auto & e : p) cin >> e;
    int base = 20000;//minimum value
    int maxi = 1000000000;
    for(int i = 0; i < n;i++){
        a[i] += base*(i+1);
        b[i] =  maxi - a[i];
    }
    for(int i = 0; i < n;i++){
        a[p[i]-1] += i;
    }
    for(int i = 0; i < n;i++)
        cout << a[i] << (i != n-1 ? " " : "\n");
    for(int i = 0; i < n;i++)
        cout <<b[i] << (i != n-1 ? " " : "\n");
}


Measured memory_bytes: 896
h, w = map(int, input().split())
dp = [[0]] * h
m = [''] * h
inf = h * w

for i in range(h):
  dp[i] = [0] * w 
  m[i] = input()
# print(h, w)
# print(m)

    
if m[0][0] == '#':
  dp[0][0] = 1

# print(dp)
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue
    
    current = m[i][j]
    ue = '' if i == 0 else m[i-1][j]
    ue_val = inf if i == 0 else dp[i-1][j]
    left = '' if j == 0 else m[i][j-1]
    left_val = inf if j == 0 else dp[i][j-1]
    
    if current == '#' and ue == '.':
      ue_val += 1
    if current == '#' and left == '.':
      left_val += 1
    
    dp[i][j] = min(ue_val, left_val)
        
        

# print(dp)
print(dp[h-1][w-1])

Measured memory_bytes: 41712
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main (String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		
		scanner.close();
		
		List<Integer> list = new ArrayList<>();
		
		for (int i = 1; i < n + 1; i++) {
			
			if (i % 3 == 0 && i % 5 == 0) {
				list.add(0);
			} else if (i % 3 == 0 && i % 5 != 0) {
				list.add(0);
			} else if (i % 3 != 0 && i % 5 == 0) {
				list.add(0);
			} else {
				list.add(i);
			}
		}
		
		System.out.println(list.stream().mapToLong(x -> x)
			     .sum());
	}

}


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

int main(){
  string s;
  cin>>s;
  int cnt=0;
  for(int i=0;i<s.size();i++)
    if(s[i]=='x') cnt++;
  cout<<(cnt<=7?"YES":"NO")<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1010;
int n;
LL x[maxn],y[maxn],u[maxn],v[maxn],bs[35];

LL power_int(int a, int b) {
  LL x = 1;
  while (b > 0) {x *= a;b--;}
  return x;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

  LL parity = (x[0] + y[0]) % 2;

  bool check = true;
  for (int i = 0; i < n; i++) if ((x[i] + y[i] - parity) % 2 != 0) check = false;

  if (check) {
    if (parity == 0) {
      cout << 32 << endl;
      for (int i = 30; i > -1; i--) {
        cout << power_int(2, i) << " ";
      }
      cout << 1 << endl;
      for (int i = 0; i < n; i++) {
        x[i]++;
      }
    }
    else {
      cout << 31 << endl;
      for (int i = 30; i > -1; i--) {
        cout << power_int(2, i) << " ";
      }
      cout << endl;
    }

    for (int i = 0; i < n; i++) {
      u[i] = x[i] + y[i];
      v[i] = x[i] - y[i];
    }

    for (int i = 0; i < n; i++) {
      for (int j = 30; j > -1; j--) {
        if (u[i] > 0 && v[i] > 0) {
          cout << 'R';
          u[i] -= power_int(2, j);
          v[i] -= power_int(2, j);
        }
        else if (u[i] > 0 && v[i] < 0) {
          cout << 'U';
          u[i] -= power_int(2, j);
          v[i] += power_int(2, j);
        }
        else if (u[i] < 0 && v[i] > 0) {
          cout << 'D';
          u[i] += power_int(2, j);
          v[i] -= power_int(2, j);
        }
        else {
          cout << 'L';
          u[i] += power_int(2, j);
          v[i] += power_int(2, j);
        }
      }
      if (parity == 0) cout << 'L';
      cout << endl;
    }
  }

  else {
    cout << "-1" << endl;
  }
}


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

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    int alice = 0;
    int bob = 0;
    for(int i=0; i<N; i++){
        if(i%2==0) alice += a[i];
        if(i%2==1) bob += a[i];
    }
    cout << alice-bob << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int md=1000000007;
int n,ans,i,j,k,f[1000005],s[1000005];
int main()
{
	scanf("%d",&n);
	f[1]=n;
	s[1]=(n-1+n)%md;
	for(i=2;i<=n;++i)
	{
		f[i]=f[i-1];
		if(i-3>=0)
			f[i]=(1ll*f[i]+s[i-3])%md;
		f[i]=(f[i]+1ll*(n-max(2,i-1)+1)*n)%md;
		s[i]=(1ll*s[i-1]+n-1+f[i])%md;
	}
	printf("%d",f[n]);
	return 0;
}


Measured memory_bytes: 7936
A_num = int(input())
B_num = int(input())
C_num = int(input())
X_value = int(input()) # 50の倍数

A_value = 500
B_value = 100
C_value = 50

counter = 0
for i in range(A_num+1):
    remain_value1 = X_value - i * A_value
    if remain_value1 == 0:
        counter += 1
    elif remain_value1 < 0:
        break
    else:
        for j in range(B_num+1):
            remain_value2 = remain_value1 - j * B_value
            if remain_value2 == 0:
                counter += 1
            elif remain_value2 < 0:
                break
            else:
                for k in range(C_num+1):
                    remain_value3 = remain_value2 - k * C_value
                    if remain_value3 == 0:
                        counter += 1
                    elif remain_value3 < 0:
                        break
            
print(counter)

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

#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
#define N 	 100005
void solve(){
	int n, p;
	cin>>n>>p;
	cout<<(n*3 + p)/2<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
     t =1;
//     cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix_2
# CreatedDate:  2020-07-30 18:19:19 +0900
# LastModified: 2020-07-30 18:49:07 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import groupby


def main():
    n = int(input())
    H = list(map(int, input().split()))
    A = []
    for i in range(max(H)+1):
        A.append([1 if h > i else 0 for h in H])

    cnt = 0
    for a in A:
        ans = groupby(a)
        for k, g in ans:
            if 1 in list(g):
                cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9216
m,n,X,Y=map(int,input().split())
*x,=map(int,input().split())
*y,=map(int,input().split())
for z in range(X+1,Y+1):
	if z <= min(y) and max(x) < z:
		print('No War')
		exit(0)
print('War')

Measured memory_bytes: 3060
/*input
SSTTST

*/
#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 

using namespace std;
long long mod=1e9+7;
 
typedef long long unsigned llu;
typedef long long int lld;
typedef long ld;
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define scd(a) scanf("%d",&a)
#define scd2(a,b) scanf("%d%d",&a,&b)
#define scd3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scf(a) scanf("%lf",&a)
#define scf2(a,b) scanf("%lf%lf",&a,&b)
#define scf3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define prfL(a) printf("%lf\n",a)
#define prfS(a) printf("%lf ",a)
#define Error(x) cerr << #x << " = " << (x) <<endl;
#define Error2(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define Error3(a,b,c) cerr<<"("<<#a<<" , "<<#b<<" , "<<#c<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<")\n";
#define Error4(a,b,c,d) cerr<<"("<<#a<<" , "<<#b<<" , "<<#c<<" , "<<#d<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<" , "<<(d)<<")\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define popcount __builtin_popcountll
// #define swap(a,b,t) t=a;a=b;b=t
typedef pair<lld,lld> PA;
 
#define lim 1000003
#define lim2 3003
// inline lld sqr(lld x) { return x * x; }
// map<lld,lld> M;
// deque<PA> Q;
// map<lld,lld>::iterator it;
// std::ios::sync_with_stdio(false);
 
// multiset<lld> S;
// set<lld> S;
vector<PA> V[lim];
// priority_queue<PA> Q;
lld A[lim];
// lld dp[103][103];
// char B[103][103];
// string S[lim],R[lim];
// PA P[lim];
// lld dp[1<<18];
// lld one,zero,ansR,numNodes;

lld powP(lld a,lld b){
    if(b==0) return 1%mod;
    lld k;
    k=powP(a,b/2);
    k=k*k%mod;
    if(b%2==0) return k;
    else return a*k%mod;
}
priority_queue<PA,vector<PA>,greater<PA> > Q;


int main(){
    // std::ios::sync_with_stdio(false);
    lld T,i,j,h,l,r,k,s,b,c,a,d,q,p,n,m,w,x,y,v,z,t,curr,prev,sum,ans,pos,val,countA,secondMin,indicator;
    string S;
    cin>>S;
    ans=0;
    n=S.size();
    rep(i,0,n-1){
        if(S[i]=='T') countA++;
        else countA--;
        ans=max(ans,countA);
    }
    prL(ans*2);
    return 0;
}


Measured memory_bytes: 24192
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    ll n,k,q;
    cin >> n >> k >> q;
    ll a[q];
    rep(i,q){
        cin >> a[i];
        a[i]--;
    }
    ll cnt[n];
    rep(i,n)cnt[i]=0;
    rep(i,q){
        cnt[a[i]]++;
    }
    rep(i,n){
        cnt[i]+=k-q;
        if(cnt[i]>0)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
return 0;}

Measured memory_bytes: 2176
// https://atcoder.jp/contests/abc090/tasks/abc090_a

#include <iostream>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  string s, r = "";

  for (size_t i = 0; i < 3; i++)
  {
    cin >> s;
    r += s[i];
  }

  cout << r << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int search(int a[100][100],int stamp[100][2],int n,int num,int ntime){
    int i;
    stamp[num][0] = ntime;
    for(i=0;i<n;i++){
        if(a[num][i]==1&&stamp[i][0]==0){
            ntime = search(a,stamp,n,i,ntime+1);
        }
    }
    stamp[num][1] = ntime+1;
    return ntime+1;
}

int main(void){
    int n,i,j,u,k,l,time=0;
    int a[100][100];
    int stamp[100][2];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        stamp[i][0]=0;
        stamp[i][1]=0;
        for(j=0;j<n;j++){
            a[i][j] = 0;
        }
    }
    for(i=0;i<n;i++){
        scanf("%d",&u);
        scanf("%d",&k);
        for(j=0;j<k;j++){
            scanf("%d",&l);
            a[u-1][l-1] = 1;
        }
    }
    for(i=0;i<n;i++){
        if(stamp[i][0]==0){
            time = search(a,stamp,n,i,time+1);
        }
    }
    for(i=0;i<n;i++){
        printf("%d %d %d\n",i+1,stamp[i][0],stamp[i][1]);
    }
}


Measured memory_bytes: 2092
MAX_LEN = 1000
dp = Array.new (MAX_LEN + 1) { Array.new MAX_LEN + 1 }
gets.to_i.times do
  x, y = gets.chomp.chars, gets.chomp.chars
  m, n = x.size, y.size
  for i in 0..m
    dp[i][0] = 0
  end
  for j in 0..n
    dp[0][j] = 0
  end
  for i in 1..m
    for j in 1..n
      a, b = dp[i-1][j], dp[i][j-1]
      dp[i][j] = (a > b ? a : b)
      if x[i-1] == y[j-1]
        c = dp[i-1][j-1] + 1
        dp[i][j] = c if dp[i][j] < c
      end
    end
  end
  p dp[m][n]
end


Measured memory_bytes: 14780
S = input()
T = input()
lst = []
for i in range(len(S) - len(T) + 1):
    pS = S[i:i + len(T)]
    for j in range(len(T)):
        if pS[j] != '?' and pS[j] != T[j]:
                break
    else:
        S_2 = S[0:i] + T + S[i + len(T):len(S)]
        lst.append(S_2.replace('?', 'a'))
if lst:
    lst.sort()
    print(lst[0])
else:
    print('UNRESTORABLE')


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e18)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    ll n;
    cin >> n;
    ll ans = INF;
    for (ll i=1; i*i<=n; ++i) {
        if (n%i==0) ans = min(ans, i+n/i);
    }
    cout << (ans-2) << endl;
    return 0;
}


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

int main(int argc, char const *argv[]) {
  int A, B, C;
  long long K;
  std::cin >> A >> B >> C >> K;
  int ans = (K%2==0)?A-B:B-A;
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>

using namespace std;

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

int main() {
    int H,W; cin >> H >> W;
    vector<vector<int>> map(H, vector<int>(W, -1));
    deque<pair<int,int>> dq;

    for (int i = 0; i < H; ++i) {
        string s; cin >> s;
        for (int j = 0; j < W; ++j) {
            if (s[j] == '#') {
                dq.push_back(pair<int,int>(j,i));
                map[i][j] = 0;
            }
        }
    }

    long unsigned int idx = 0;
    pair<int,int> pos;
    do {
        pos = dq.at(idx);
        for (int i = 0; i < 4; ++i) {
            int x = pos.first  + dx[i];
            int y = pos.second + dy[i];
            if (x < 0 || W <= x || y < 0 || H <= y) continue;
            if (map[y][x] == -1) {
                dq.push_back(pair<int,int>(x,y));
                map[y][x] = map[pos.second][pos.first] + 1;
            }
        }
    } while (++idx < dq.size());
    pos = dq.back();

    cout << map[pos.second][pos.first] << endl;
}


Measured memory_bytes: 12544
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 参加できるリスト
		int[] l = {111,222,333,444,555,666,777,888,999};
		// 整数の入力
        	int b = sc.nextInt();
	        for ( int i : l ) {
        	    if ( b <= i ) {
    			System.out.println(i);
	    		break;
        	    }
	        }
		}
}

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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n, i##_len=(n); i>=0; i--)
#define FOR(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)

//最大公約数 
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main(){
string S;
cin >> S;
int N = S.size();
vector<int>ans(N);
int cnt = 0;

REP(j, 2){
  REP(i, N){
    if(S.at(i) == 'R') cnt++;
    else{
      ans.at(i) += cnt / 2;
      ans.at(i - 1) += (cnt + 1) / 2;
      cnt = 0;
    }
  }

reverse(all(ans));
reverse(all(S));
REP(i, N){
  if(S.at(i) == 'R') S.at(i) = 'L';
  else S.at(i) = 'R';
}

}

REP(i, N) cout << ans.at(i) << ' ';

}





Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define FOR(i, m, n) for(int i = (m); i < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;
typedef long long ll;

signed main() {
  ll n, k, next = 0, mod = -1, cycle;
  cin >> n >> k;
  ll a[n], flags[n];
  REP(i, n) {
    cin >> a[i];
    flags[i] = -1;
  }
  vector<int> visited, t;

  if(k <= n) {
    REP(i, k) { next = a[next] - 1; }
    cout << next + 1 << endl;
  } else {
    REP(i, n) {
      if(flags[next] != -1) {
        cycle = visited.size() - flags[next];
        mod = (k - flags[next]) % cycle;
        for(int j = flags[next]; j < flags[next] + cycle; j++) {
          t.push_back(visited[j]);
        }
        break;
      } else {
        visited.push_back(next);
        flags[next] = i;
        next = a[next] - 1;
      }
    }

    if(mod == -1) {
      cout << 1 << endl;
    } else {
      cout << t[mod] + 1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 7948
#include <bits/stdc++.h>
#include <fstream>
#include <cstdio>
using namespace std;
// cin.ignore();//twice getline(cin,s);
// g++ iterator.cpp -std=c++17
// cout<<(A + B == C ? "YES" : "NO")<<endl;
// __gcd(a,b)
// string s=to_string(i);
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);}


int main(void)
{
    fast();
    int n,m;
    cin>>n>>m;
    int a[n];
    int s=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s = s+a[i];
    }
    double l = s/(4.0*m);
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<l)
        {
            continue;
        }
        else
        {
            cnt++;
        }
        if(cnt==m)
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int i, j, n, flag=0, swap, minj, A[36], B[36];
  char C1[36], C2[36], tmp;

  scanf("%d",&n);
  for( i=0 ; i<n ; i++ ){
    scanf(" %c%d",&C1[i],&A[i]);
    C2[i] = C1[i];
    B[i] = A[i];
  }

  for( i=0 ; i<n ; i++ ){
    for( j=n-1 ; j>=i+1 ; j-- ){
      if(A[j]<A[j-1]){
	swap = A[j];
	A[j] = A[j-1];
	A[j-1] = swap;
	tmp = C1[j];
	C1[j] = C1[j-1];
	C1[j-1] = tmp;
      }
    }
  }
  for( i=0 ; i<n-1 ; i++ )
    printf("%c%d ",C1[i],A[i]);
  printf("%c%d\n",C1[i],A[i]);
  printf("Stable\n");
  

  for( i=0 ; i<n ; i++ ){
    minj = i;
    for( j=i ; j<n ; j++ ){
      if(B[j]<B[minj]){
	minj = j;
      }
    }
    swap = B[i];
    B[i] = B[minj];
    B[minj] = swap;
    tmp = C2[i];
    C2[i] = C2[minj];
    C2[minj] = tmp;    
  }
  for( i=0 ; i<n-1 ; i++ )
    printf("%c%d ",C2[i],B[i]);
  printf("%c%d\n",C2[i],B[i]);

  for( i=0 ; i<n ; i++ ){
    if(C1[i]!=C2[i] || A[i]!=B[i])
      flag = 1;
  }
  if(flag==1) printf("Not stable\n");
  else printf("Stable\n");

  return 0;
}

Measured memory_bytes: 608
//All nearest smaller values
//http://codeforces.com/contest/547/submission/18224310
//http://wcipeg.com/wiki/All_nearest_smaller_values
//http://codeforces.com/blog/entry/18126
/*
stack s // initially empty
for i = 1 to n
     while s is not empty and a[s.top()] >= a[i]
          do s.pop()
     if s is empty
          then l[i] = 0
     otherwise
          l[i] = s.top()
     s.push(i)
*/
#include <bits/stdc++.h>
using namespace std;
const long long Maxn = 200005;
const long long inf = 1e9;
long long a[Maxn];
vector <long long> NSVL, NSVR;
int main() {
   long long n;
   scanf("%lld", &n);
   for(long long i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
   }      
   a[0] = -inf;
   a[n + 1] = -inf;

   NSVL.resize(n + 2), NSVR.resize(n + 2);

   stack <long long> s;
   s.push(0);
   for(long long i = 1; i <= n; i++) {
      while(a[s.top()] >= a[i]) {
         s.pop();
      }
      NSVL[i] = s.top();
      s.push(i);
   }
   while(!s.empty()) {
      s.pop();
   }

   s.push(n + 1);
   for(long long i = n; i >= 1; i--) {
      while(a[s.top()] >= a[i]) {
         s.pop();
      }
      NSVR[i] = s.top();
      s.push(i);
   }
   while(!s.empty()) {
      s.pop();
   }
    
    long long ans = 0LL;
   for(long long i = 1; i <= n; i++) {
    ans += a[i] * 1LL * (NSVR[i] - i) * (i - NSVL[i]);
   }
   cout << ans<< endl;
   
   return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    string S;
    cin >> S;
    cout << string(S.size(), 'x') << endl;
    return 0;
};

Measured memory_bytes: 256
@F=map[glob<>],1..<>;
@P=map[glob],<>;
printf sort{$b-$a}map{
	$x=!//;
	for$f(@F){
		$c+=$'>>$_&1&&@$f[$_]for($c=0)..9;
		$x+=$P[$i++%@P][$c]
	}
	$x
}1..1023


Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int a,b,c,d,f;
    scanf("%d%d%d%d",&a,&b,&c,&d);
	if(c>b||a>d) 
		printf("0");
    else{
		f=min(d,b)-max(a,c);
    	printf("%d",f);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
const int nmax=100005;
int p[nmax],viz[nmax];
vector<int> v[nmax];
int n,a,b,i;
void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(!viz[v[x][i]])
    {
        dfs(v[x][i]);
        if(!(p[v[x][i]]+p[x]))
        {
            p[x]=p[v[x][i]]=1;
        }
    }
}
int main()
{
    cin>>n;
    for(i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    for(i=1;i<=n;i++)
        if(!p[i])
    {
        cout<<"First";
        return 0;
    }
    cout<<"Second";
    return 0;
}

Measured memory_bytes: 6656