akhauriyash/Code-Regression huggingface dataset:
/* ex 9_1 ABC 043 B
   nk777 */
 
#include<stdio.h>
#include <stdlib.h>
//スタックに格納するデータの最大数
#define SIZE 100

//スタックの定義
typedef struct stack{
    int size;
    int count;
    char data[SIZE];
    char *top;
} stack;

//スタックの初期化
void initialize_stack(stack *stk){
    // 要素数を0にする
    stk->count = 0;
    // スタックの大きさをSIZEにする
    stk->size = SIZE;
    // topを配列の末尾にする
    stk->top = &(stk->data[SIZE]);
}

//データの追加
void push(stack *stk, char elem){
    if(stk->count >= stk->size){
        // オーバーフローするとき
        exit(1);
    }
    else{
        // 配列の番号が若いほどデータが新しい
        stk->top--;
        *(stk->top) = elem;
        stk->count++;
    }
}

//データの取り出し(削除)
char pop(stack *stk){
    char latest;
    if(stk->count <= 0){
        // アンダーフローするとき
        exit(1);
    }
    else{
        latest = *(stk->top);
        stk->top++;
        stk->count--;
        return latest;
    }
}

// スタックの中身を古い方から印刷
void print_stack(stack *stk){
    for (int i = 0; i < stk->count; i++)
    {
        // 配列の後ろから出力
        printf("%c", stk->data[SIZE - i - 1]);
    }
    printf("\n");
} 

int main(void){
    // 表示する文字列を格納するスタックstk
    stack stk;
    // カウンタi
    int i = 0;
    // 読み取った文字列を一時的に格納するword
    char word[10];
    //スタックを初期化（ポインタ渡しで関数にわたすこと）
    initialize_stack(&stk);
    //入力されたデータをスタックに追加
    scanf("%s", word);
    while (word[i] != '\0')
    {
        if (word[i] == 'B')
        {
            if (stk.count > 0)
            {
                // スタックか空じゃないときだけpop
                pop(&stk);
            }
        }
        else
        {
            // 0と1のときは追加
            push(&stk, word[i]);
        }
        i++;
    }
    // 結果の出力
    print_stack(&stk);
    return 0;
}

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

int main()
{
    unsigned long long int n;
    cin >> n;
    int arr[n];
    for (unsigned long long int i=0;i<n;i++)
    {
        cin >> arr[i];
    }
    unsigned long long int prev=0,s=0,temp;
    for(unsigned long long int i=0;i<n;i++)
    {
        temp=arr[i];
        if(arr[i]<prev)
        {
            arr[i]=prev;
        }
        temp=arr[i]-temp;
        s=s+temp;
        prev=arr[i];
    }
    cout<<s;
    return 0;
}


Measured memory_bytes: 4324
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    map <int,int> p;
    for (int i=1; i<=99; i++){
        for (int j=1; j<=99; j++){
            for (int k=1; k<=99; k++){
                int temp=i*i+j*j+k*k+i*j+i*k+j*k;
                if (temp<=n) p[temp]++;
            }
        }
    }
    for (int i=1; i<=n; i++) cout<<p[i]<<endl;
}

Measured memory_bytes: 4020
#include <bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
#define SORT(arr) sort(arr, arr + ARRAY_LENGTH(arr))
using namespace std;


int N;


int main(){
	cin >> N;
	int d[N];
	for(int i=0;i<N;i++)cin >> d[i];
	SORT(d);
	int ans = 1;
	for(int i=1;i<N;i++){
		if(d[i]>d[i-1])ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) x
#define WATCH(x) TRACE( cout << #x" = " << x << endl)
#define PRINT(x) TRACE(printf(x))
#define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end()); } )
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define fi first
#define se second 

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using ld = long double;
using pll = pair<ll, ll>;

void buff() { ios::sync_with_stdio( false ); cin.tie( nullptr ); }

constexpr ll MOD = 1e9 + 7;

inline ll pow_mod( ll a, ll b, ll mod = MOD) {
    ll res = 1; a %= mod; assert(b >= 0);
    for(;b;b>>=1) {
        if(b&1) res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

constexpr int ms = 2013;
ll memo[ms][ms];
vector< pair<long long, long long> > v;
int n;

ll solve(int l, int r) {
    if( l > r ) return 0ll;
    if( memo[l][r] != -1 ) return memo[l][r];
    int tot = (r - l + 1);
    int prox = n - tot;
    return memo[l][r] = max(solve(l + 1, r) + v[prox].first * abs(v[prox].second - l),
                            solve(l, r - 1) + v[prox].first * abs(v[prox].second - r) );
}

int main() 
{
    buff();
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        ll num;
        cin >> num;
        v.emplace_back(num, i);
    }
    sort(v.rbegin(), v.rend());
    for(int i = 0; i < ms; ++i) for(int j = 0; j < ms; ++j) memo[i][j] = -1; 
    cout << solve(0, n - 1) << endl;    
}


Measured memory_bytes: 35460
import java.util.*;
import java.io.*;

public class Main {
    public static long MOD = 1000000007L;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st  = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        ArrayList<Long> pos = new ArrayList<Long>();
        ArrayList<Long> neg = new ArrayList<Long>();
        Long[] arr = new Long[n];
        st = new StringTokenizer(f.readLine());
        long currp = 1L;
        for(int i = 0; i < n; i++){
            long elem = Long.parseLong(st.nextToken());
            arr[i] = elem;
            currp*=elem;
            currp%=MOD;
            currp+=MOD;
            currp%=MOD;
            if(elem > 0) pos.add(elem);
            else neg.add(elem);
        }
        if(k == n){
            out.println(currp);
            out.close();
            System.exit(0);
        }
        Collections.sort(neg);
        long prod = 1L;
        if(pos.size() == 0 && k % 2 == 1){
            for(int i = neg.size()-1; i > neg.size()-1-k; i--){
                prod*=neg.get(i);
                prod%=MOD;
                prod+=MOD;
                prod%=MOD;
            }
            out.println(prod);
            out.close();
            System.exit(0);
        }
        Arrays.sort(arr);
        int a = 0;
        int b = n-1;
        if(k % 2 == 1){
            prod*=arr[b];
            prod%=MOD;
            prod+=MOD;
            prod%=MOD;
            b--;
            k--;
        }

        k/=2;
        for(int i = 0; i < k; i++){
            long left = arr[a]*arr[a+1];
            long right = arr[b]*arr[b-1];
            if(left > right){
                prod*=arr[a];
                prod%=MOD;
                prod+=MOD;
                prod%=MOD;
                prod*=arr[a+1];
                prod%=MOD;
                prod+=MOD;
                prod%=MOD;
                a+=2;
            }else{
                prod*=arr[b];
                prod%=MOD;
                prod+=MOD;
                prod%=MOD;
                prod*=arr[b-1];
                prod%=MOD;
                prod+=MOD;
                prod%=MOD;
                b-=2;
            }
        }




        out.println(prod);
        out.close();
    }
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n; cin >> n;
    vector<ll> a(n), b(n), c(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    ll ans = 0;
    rep(i, n) {
        ll x = lower_bound(all(a), b[i]) - a.begin();
        ll y = upper_bound(all(c), b[i]) - c.begin();
        ans += x * (n - y);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <stdio.h>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
long long int pos(long long int a  ){
    if( a>=0){return a;}
    return -a;
}
long long int dp[100005];
int main(){
    int n;
    cin>>n;
    vector <long long int> v;
    for(int i = 0;i<n;i++){
        long long int z;cin>>z;
        v.push_back(z);
    }
    dp[0] = 0;
    dp[1] = pos(v[1]-v[0] );
    for(int i = 2;i<n;i++){
        dp[i] = min(dp[i-1]+pos(v[i]-v[i-1]),dp[i-2]+pos(v[i]-v[i-2]) );
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 1908
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  vector<int> vec(n);
  int cnt=0;
  for(int i=0;i<n;i++){
    cin>>vec.at(i);
    if(vec.at(i)>=k){
      cnt++;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(int argc, char const *argv[]) {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<bool> win(K + 1);
    for (int i = 0; i <= K; i++) {
        if (*min_element(A.begin(), A.end()) > i) {
            win[i] = false;
        } else {
            bool win_flag = false;
            for (int a: A) {
                if (i < a) {
                    continue;
                } else {
                    if (!win[i - a]) {
                        win_flag = true;
                        break;
                    }
                }
            }
            win[i] = win_flag;
        }
    }
    if (win[K]) {
        cout << "First" << endl;
    } else {
        cout << "Second" << endl;
    }
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];

    vector<int> ans(n);
    int num_ball = 0;
    for(int i = n; i >= 1; i --)
    {
        int cnt = 0;
        for (int j = 2 * i; j <= n; j += i)
            cnt += ans[j - 1];
        ans[i - 1] = int(bool(cnt % 2) != a[i - 1]);
        // cout << ans[i - 1] << endl;
        // cout << "&*&&&" << endl;
        num_ball += ans[i - 1];
        // cout << cnt << ' ' << a[i-1] << ' ' <<ans[i-1] << ' ' << num_ball << endl;
    }
    cout << num_ball << endl;
    rep(i, 0, ans.size())
    if (ans[i] == 1)
        cout << i + 1 << ' ' << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <cmath>

int main(void)
{
  int a,b,C;
  double S,L,h,d,rad;

  scanf("%d %d %d", &a, &b, &C);
  rad=C/180.0*M_PI;

  S=a*b*sin(rad)/2;
  d=sqrt(a*a+b*b-2*a*b*cos(rad));
  L=a+b+d;
  h=2*S/a;

  printf("%f\n", S);
  printf("%f\n", L);
  printf("%f\n", h);

  return 0;
}


Measured memory_bytes: 1064
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

const int INF = 10000000;
using namespace std;
typedef long long  ll;
const int MAX = 1000010;

/** Problem0185 : Goldbach's Conjecture II **/
int main()
{
	bool prime[MAX];
	int  input, count;
	
	for (int i=0; i<MAX; i++)
		prime[i] = true;
	
	prime[0] = false; prime[1] = false;
	
	for (int i=2; i<MAX; i++) {
		if (prime[i]) {
			for (int j=2; i*j<MAX; j++) {
				prime[i*j] = false;
			}
		}
	}
	
	while (1) {
		cin >> input;
		if (input == 0) break;
		
		count = 0;
		for (int i=2; i<=input/2; i++) {
			if (prime[i] && prime[input - i])
				count++;
		}
		
		cout << count << endl;
	}
	return 0;
}

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

typedef long long ll;

ll _gcd(ll a, ll b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}

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

int main(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        ll a,b;
        cin >> a >> b;

        ll res = 0;
        ll n = gcd(a,b);

        //cout << n <<endl;
        for(ll i=2;i*i<=n;++i){ //因数分解
                //cout <<n << " " << i <<endl;
                if(n%i==0){     
                        res++;
                        //n/=i;
                        while(n%i==0){
                                n/=i;
                        }
                }
        }
        if(n != 1) res++;

        cout<< res + 1  <<endl;

        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    int n; cin >> n;
    using BA = tuple<int, int>;

    vector<BA> ba(n); for(auto& e : ba){ int a, b; cin >> a >> b; e = BA(b, a); }
    sort(_all(ba));

    int T = 0;
    string res = "Yes";
    for(auto& e : ba){
        int a, b; tie(b, a) = e;
        T += a;
        if(T > b){
            res = "No";
        }
    }

    cout << res << endl;

    return 0;
}


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

using namespace std;

#define pb push_back

const int N = 1e5 + 5, inf = 1e7;
int n, K, l[N], r[N];
bool sta[N];
vector<int> gr[N];
queue<int> q;

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i <= n; ++i) l[i] = -inf, r[i] = inf;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        gr[u].pb(v); gr[v].pb(u);
    }
    cin >> K;
    while(K --) {
        int v, p; cin >> v >> p;
        l[v] = r[v] = p;
        sta[v] = (p % 2 != 0);
        q.push(v);
    }

    while(!q.empty() ) {
        int u = q.front(); q.pop();
        for (int v : gr[u]) {
            if(l[v] != -inf) {
                if(r[v] < l[u] - 1 || r[u] < l[v] - 1 || sta[u] == sta[v]) { cout << "No"; return 0; }
            }
            sta[v] = (1 ^ sta[u]);
            if(l[v] < l[u] - 1) q.push(v);
            l[v] = max(l[v], l[u] - 1);
            if(l[v] >= l[u] - 1 && r[v] > r[u] + 1) q.push(v);
            r[v] = min(r[v], r[u] + 1);
            if(l[v] > r[v]) { cout << "No"; return 0; }
        }
    }

    cout << "Yes\n";
    for(int i = 1; i <= n; ++i) {
        if( (l[i] - sta[i]) % 2 != 0 ) l[i] ++;
        cout << l[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 8056
from sys import stdin

def binSearch(k, p_min, p_max):
    global w
    while p_max-p_min > 1:
        mid = p_min + (p_max-p_min)//2
        if k >= countTrack(w, mid):
            p_max = mid
        else:
            p_min = mid

    return p_max

def countTrack(w, p):
    rest = []
    for wi in w:
        if len(rest) != 0 and rest[-1] >= wi:
            rest[-1] -= wi
        else:
            rest.append(p-wi)

    return len(rest)

n, k = [int(x) for x in stdin.readline().rstrip().split()]
w = [int(stdin.readline().rstrip()) for _ in range(n)]
print(binSearch(k, max(w)-1, 10000*100000+1))


Measured memory_bytes: 9580
import java.util.*;
class Main{
	public static void main(String[]$){
		Scanner s=new Scanner(System.in);
		int v=Math.min(s.nextInt()*4,Math.min(s.nextInt()*2,s.nextInt())),d=s.nextInt();
		long n=s.nextInt();
		System.out.println(Math.min(n*v,n/2*d+n%2*v));
	}
}

Measured memory_bytes: 25684
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)
#define pb push_back
#define eb emplace_back

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    else return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

int INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

int main(){
    int n;
    cin >> n;
    vector<int> dp(n+10,INF);
    dp[0] = 0;
    rep(i,n+10){
        int j = 1;
        while(j<=i){
            chmin(dp[i],dp[i-j]+1);
            j*=6;
        }
        int k = 1;
        while(k<=i){
            chmin(dp[i],dp[i-k]+1);
            k*=9;
        }
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define int long long
#define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
# define mo 1000000007
int pa[100005],dis[100005];
bool vis[100005];
int c=0;
vector<int> v[100005];
void dfs(int x,int p)
{
    c++;
    vis[x]=true;
    pa[x] = p;
    for(int i=0;i<v[x].size();i++)
    {
        if(!vis[v[x][i]])
        {
            dfs(v[x][i],p);
        }
    }
}
 signed main(){
    gok
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        pa[i]=i;
        vis[i]=false;
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            c=0;
            dfs(i,i);
            dis[i]=c;
        }
    }

    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        if(pa[x]==pa[y])
        {
            v[x].push_back(y);
            v[y].push_back(x);
           // dis[pa[x]]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int an = dis[pa[i]] - v[i].size() - 1;
        cout<<an<<" ";
    }
    return 0;
}


Measured memory_bytes: 11264
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<char> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s,t;
    cin >> s >> t;
    int k=s.size();
    int n=t.size();
    ll ans=INF;
    rep(i,k-n+1){
        ll cnt=0;
        rep(j,n){
            if(s[i+j]!=t[j]){
                cnt++;
            }
            //cout << i+j << endl;
        }
        chmin(ans,cnt);
    }
    cout << ans << endl;
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 3660
module M = Map.Make (
    struct
       type t = int * int
       let compare (a1, a2) (b1, b2) = compare (a1 lsr a2) (b1 lsr b2)
    end)
let () =
    let split s =
        let rec loop i cur flag acc =
            if i = String.length s then ( if flag then cur :: acc else acc) else (
                match flag, s.[i] with
                | true,  ' ' -> loop (i + 1) "" false (cur :: acc)
                | false, ' ' -> loop (i + 1) "" false acc
                | true,  v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
                | false, v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
            )
        in
        List.map int_of_string (List.rev (loop 0 "" false []))
    in
    let add key v map = M.add key (v + try M.find key map with _ -> 0) map in
    let main () =
        let n, m = Scanf.sscanf (read_line ()) "%d %d" (fun n m -> n, m) in
        let list = split (read_line ()) in
        let map = List.fold_left (fun map a -> add (a, 0) 1 map) M.empty list in
        let rec loop rest map =
            if rest = 0 then map else
                let ((a1, a2) as mk, mv) = M.max_binding map in
                if rest < mv then (
                    let map = M.remove mk map in
                    let map = add mk (mv - rest) map in
                    let map = add (a1, a2 + 1) rest map in
                    map
                ) else (
                    let map = M.remove mk map in
                    let map = add (a1, a2 + 1) mv map in
                    loop (rest - mv) map
                )
        in
        let map = loop m map in
        let r = M.fold (fun (a1, a2) v acc -> acc + v * (a1 lsr a2)) map 0 in
        Printf.printf "%d\n" r
    in
    main ()

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,N) for(int i=0; i<N; i++)
#define cinv(v,N) vector<int> v(N); for(int i=0; i<N; i++){ cin >> v[i]; }
#define mt make_tuple
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define all(v) (v).begin(),(v).end()
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
  //input
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll A, B, M; cin >> A >> B >> M;
  vector<ll> a(A), b(B); 
  FOR(i,A){ cin >> a[i]; }
  FOR(i,B){ cin >> b[i]; }
  vector<vector<ll>> m(M,vector<ll>(3));
  FOR(i,M){ cin >> m[i][0] >> m[i][1] >> m[i][2]; }
  
  //main
  ll ans = 1e18;
  FOR(i,M){ ans = min(ans,a[m[i][0]-1]+b[m[i][1]-1]-m[i][2]); }
  sort(all(a)); sort(all(b));
  //cout << a[0] << b[0] << endl;
  ans = min(ans,a[0]+b[0]);
  
  // output
  cout << ans << endl;

  return 0;
}



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

int main()
{
  int N;
  cin >> N;
  string S;
  cin >> S;
  int ans = 0;
  int x = 0;
  for(int i = 0; i < N; i++){
    x += ((S[i] == 'I')?1:-1);
    ans = max(ans,x);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
static Scanner inp=new Scanner(System.in);
static String c[]=new String [100000];
static String x[]=new String [100000];
static int a[]=new int[100000];
	public static void main(String args[]) {
		int n=inp.nextInt();
		while (n>0){
			int mx1=0;
			int mx2=0;
			for (int i=1;i<=28;i++)a[i]=0;
			for (int i=1;i<=n;i++)	
				c[i]=inp.next();
			for (int i=1;i<=n;i++){
				a[c[i].charAt(0)-64]++;
				x[c[i].charAt(0)-64]=c[i];
				mx1=0;
				mx2=0;
				for (int j=1;j<=28;j++){if (a[mx1]<a[j])mx1=j;}
				for (int j=1;j<=28;j++){if ((j!=mx1)&(a[mx2]<a[j]))mx2=j;}
				if (a[mx2]+n-i<a[mx1]){
					System.out.println(x[mx1]+" "+i);
					break;
				}
			}
			if (a[mx2]==a[mx1]) System.out.println("TIE");
			n=inp.nextInt();
		}
	}

}

Measured memory_bytes: 49528
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};


/*
 * 0©çm-1ÜÅÌfÉÖ·éCu
 * templateÅTCYðwè·éÌÅá±¢?
 * Prime<1000> p; Å999ÜÅÌfÌe[uªÅ«é
 * p[k] : kÔÚÌfÍ½©
 * p.isPrime(k) : kªf©Ç¤©
 */
template<int m>
class Prime{
  std::vector<bool> p;
  std::vector<int> ps;
public:
  Prime(){
    p = std::vector<bool>(m,true);
    assert(m>1);
    p[0]=p[1]=false;
    for(int i=4;i<m;i+=2)
      p[i]=false;
    ps.push_back(2);
    for(int i=3;i<m;i+=2){
      if(p[i]){
        ps.push_back(i);
        for(int j=i+i;j<m;j+=i)
          p[j]=false;
      }
    }
  }

  bool isPrime(int n){
    assert(m>n);
    return p[n];
  }

  int operator [] (int n){
    if(n<ps.size()) return ps[n];
    else return 0;
  }

  int size(){
    return ps.size();
  }
};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

int main(){
  Prime<1001000> p;
  int a,b;
  while(a = getInt(), b = getInt(), a+b){
    int mp = 0;
    int i = 0;
    int ansa = 0;
    int ansb = 0;
    while(a >= p[i]){
      if(a % p[i] == 0){
        ansa -= p[i];
        mp    = p[i];
      }
      while(a % p[i] == 0)
        a /= p[i];
      i++;
    }
    ansa += mp + mp;

    mp = i = 0;
    while(b >= p[i]){
      if(b % p[i] == 0){
        ansb -= p[i];
        mp    = p[i];
      }
      while(b % p[i] == 0)
        b /= p[i];
      i++;
    }
    ansb += mp + mp;

    printf("%c\n",ansa > ansb ? 'a' : 'b');
  }
  return 0;
}

Measured memory_bytes: 1552
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
sys.setrecursionlimit(150000)

N, M, X = map(int, sys.stdin.readline().split())
a = []
for i in range(N):
    a.append(inpl())
b = [0] * M
res = float("INF")
def DFS(cost, start, temp):
    global res
    if min(temp) >= X:
        res = min(res, cost)
        return res
    for i in range(start, N):
        c = temp.copy()
        d = [i + j for i, j in zip(c, a[i][1:])]
        DFS(cost + a[i][0], i + 1, d)
    return res

ans = DFS(0,0,b)
if ans != float("INF"):
    print(ans)
else:
    print(-1)

Measured memory_bytes: 9236
use proconio::{input};

fn main() {
    input! {
        n: i32,
        k: i32,
        p: [i32; n]
    }

    let mut vec:Vec<i32> = Vec::from(p);
    vec.sort();
    let s = &vec[0..k as usize];

    let sum:i32 = s.into_iter().sum();
    println!("{}",sum)
}


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

int main() {
    long long N, K; cin >> N >> K;
    long long nums[100010] = {0};
    for(int i = 0; i < N; ++i) {
        int a, b; cin >> a >> b;
        nums[a] += b;
    }
    
    long long res = 0;
    for(int i = 0; i < 100010; ++i) {
        res += nums[i];
        if(res >= K) {
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,r) RFOR(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lower(a,x) lower_bound(all(a), x) - a.begin();
#define COUNT(a,x)  upper_bound(all(a), x) - lower_bound(all(a), x);
#define MCOUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x);
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end());
#define scan(x) scanf("%lld",&x);
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
typedef double D;
const ll inf = 5555555555555555555;
const ll mod = 1000000007;
const D pi = acos(-1);
const D eps = 1e-10;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool ok, flag;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111


int main(void) {
  cin >> s;
  n = s.length();
  if (n > 9) {
	cout << "NO" << endl;
	return 0;
  }

  ok = false;
  rep(bit, 1 << 4) {
	string ss = "";
	if (bit >> 0 & 1)ss += 'A';
	ss += "KIH";
	if (bit >> 1 & 1)ss += 'A';
	ss += 'B';
	if (bit >> 2 & 1)ss += 'A';
	ss += 'R';
	if (bit >> 3 & 1)ss += 'A';
	if (ss == s) ok = true;
  }

  if (ok) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef pair<int,int> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr> PQ;
const int SIZE=5+4*1e5;
const int INF=10+1e9;
const LL p =7+1e9;
int A[SIZE];
int num[SIZE];
bool isnP[SIZE];
int BIT[SIZE];
void add(int x,int c){
	while(x<=SIZE){
		BIT[x]+=c;
		x+=x&-x;
	}
}
int get(int x){
	int ans=0;
	while(x>0){
		ans+=BIT[x];
		x-=x&-x;
	}
	return ans;
}
void add(int a,int b,int x){
	add(a,x);
	add(b+1,-x);
}
int main(){
	int N,M,l,r;
	cin.tie(0);
	cin >> N >> M;
	Vpr v;
	REP(i,N){

		cin >> l >> r;
		v.PB(pr(r-l,l));
	}
	sort(ALL(v));
	int now=1;
	v.PB(pr(SIZE-2,1));
	REP(i,N+1){
		while(now<=v[i].first+1 && now<=M){
			int ans=0;
			for(int j=now;j<=M;j+=now){
				ans+=get(j);
			}
			now++;
			cout << ans+N-i << endl;
		}
		add(v[i].second,v[i].second+v[i].first,1);

	}
	return 0;
}

Measured memory_bytes: 4592
#include<iostream>

using namespace std;

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

	int x = (a == b) + 2 * (a > b);

	switch (x) {
	case 0:
		cout << "a < b\n";
		break;
	case 1:
		cout << "a == b\n";
		break;
	case 2:
		cout << "a > b\n";
		break;
	}


	return 0;
}

Measured memory_bytes: 3080
import java.io.*;
import java.util.*;

public class  Main{
	static int mod=(int)1e9+7;
    public static void main(String[] args) throws Exception{
        //MScanner sc = new MScanner("chess.in");
        MScanner sc = new MScanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        int n=sc.nextInt();
        int m=sc.nextInt();
        char[][]in=new char[n][m];
        for(int i=0;i<n;i++)in[i]=sc.nextLine().toCharArray();
        int[][]cumr=new int[n+1][m+1];
        int[][]cumu=new int[n+1][m+1];
        int[][]cuml=new int[n+1][m+1];
        int[][]cumd=new int[n+1][m+1];
        for(int i=0;i<n;i++) {
        	for(int j=0;j<m;j++) {
        		if(in[i][j]=='.') {
        			if(j==0) {
        				cuml[i][j]=1;
        			}
        			else {
        				cuml[i][j]=cuml[i][j-1]+1;
        			}
        		}
        	}
        }
        for(int i=0;i<n;i++) {
        	for(int j=m-1;j>=0;j--) {
        		if(in[i][j]=='.') {
        			if(j==m-1) {
        				cumr[i][j]=1;
        			}
        			else {
        				cumr[i][j]=cumr[i][j+1]+1;
        			}
        		}
        	}
        }
        for(int i=0;i<n;i++) {
        	for(int j=0;j<m;j++) {
        		if(in[i][j]=='.') {
        			if(i==0) {
        				cumu[i][j]=1;
        			}
        			else {
        				cumu[i][j]=cumu[i-1][j]+1;
        			}
        		}
        	}
        }
        for(int i=n-1;i>=0;i--) {
        	for(int j=0;j<m;j++) {
        		if(in[i][j]=='.') {
        			if(i==n-1) {
        				cumd[i][j]=1;
        			}
        			else {
        				cumd[i][j]=cumd[i+1][j]+1;
        			}
        		}
        	}
        }
        int ans=0;
        for(int i=0;i<n;i++) {
        	for(int j=0;j<m;j++) {
        		
        		ans=Math.max(ans,cuml[i][j]+cumr[i][j]+cumu[i][j]+cumd[i][j]-3);
        	}
        }
        pw.println(ans);
        pw.flush();
    }
    static class MScanner {
		StringTokenizer st;
		BufferedReader br;
 
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

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

typedef long long  LL;
const int mo=int(1e9+7);
int h,w,a[1010][1010],ty,A,B,C,x[4],y[4],z[4];
LL k;
char ch;

int qpow(int a,int b)
{
	int x=a;  a=1;
	while (b)
		{
			if (b&1)  a=1LL*a*x%mo;
			x=1LL*x*x%mo,b>>=1;
		}
	return a;
}

void mul(int *a,int *b)
{
	z[0]=(1LL*a[0]*b[0]+1LL*a[1]*b[2])%mo;
	z[1]=(1LL*a[0]*b[1]+1LL*a[1]*b[3])%mo;
	z[2]=(1LL*a[2]*b[0]+1LL*a[3]*b[2])%mo;
	z[3]=(1LL*a[2]*b[1]+1LL*a[3]*b[3])%mo;
	a[0]=z[0],a[1]=z[1],a[2]=z[2],a[3]=z[3];
}

void qpow(LL b)
{
	while (b)
		{
			if (b&1)  mul(x,y);
			mul(y,y),b>>=1;
		}
}

void work()
{
	scanf("%d %d %lld",&h,&w,&k);
	if (k==0)  puts("1"),exit(0);
	for (int i=1; i<=h; i++)
		for (int j=1; j<=w; j++)
			{
				do  ch=getchar();  while ((ch!='#')&&(ch!='.'));
				a[i][j]=(ch=='#'),A+=a[i][j];
			}
	for (int i=1; i<=h; i++)
		if ((a[i][1])&&(a[i][w]))
			ty|=1,C++;
	for (int i=1; i<=w; i++)
		if ((a[1][i])&&(a[h][i]))
			ty|=2,C++;
	if (ty==3)  puts("1"),exit(0);
	if (ty==0)  printf("%d",qpow(A,(k-1)%(mo-1))),exit(0);
	if (ty==2)
		{
			for (int i=1; i<=h; i++)
				for (int j=1; j<=w; j++)
					if ((i<=j)==(h<=w))
						swap(a[i][j],a[j][i]);
			swap(h,w);
		}
	for (int i=1; i<=h; i++)
		for (int j=1; j<w; j++)
			B+=(a[i][j])&&(a[i][j+1]);
	x[0]=x[3]=1,y[0]=A,y[2]=mo-B,y[3]=C;
	qpow(k-1);
	printf("%d",(x[0]+x[2])%mo);
}

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


Measured memory_bytes: 4224
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long[] arr = new long[5];
        long min = Long.MAX_VALUE;
        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextLong();
            min = Math.min(arr[i], min);
        }

        long ans = n % min == 0 ? n / min - 1 + 5 : n / min + 5;

        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
using ll = long long;
const ll MOD = 1000000007;
template <class T>
struct fenwick_tree {
    public:
	fenwick_tree() : _n(0) {}
	fenwick_tree(int n) : _n(n), data(n) {}

	void add(int p, T x) {
		assert(0 <= p && p < _n);
		p++;
		while (p <= _n) {
			data[p - 1] += T(x);
			p += p & -p;
		}
	}

	T sum(int l, int r) {
		assert(0 <= l && l <= r && r <= _n);
		return sum(r) - sum(l);
	}

    private:
	int _n;
	std::vector<T> data;

	T sum(int r) {
		T s = 0;
		while (r > 0) {
			s += data[r - 1];
			r -= r & -r;
		}
		return s;
	}
};
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	fenwick_tree<ll> fw(n);
	rep(i, n) {
		ll a;
		scanf("%lld", &a);
		fw.add(i, a);
	}
	while (q--) {
		ll a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		if (a) {
			printf("%lld\n", fw.sum(b, c));
		} else {
			fw.add(b, c);
		}
	}
}

Measured memory_bytes: 8216
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] n = line.split(" ");

		int a = Integer.parseInt(n[0]);
		int b = Integer.parseInt(n[1]);
		int c = Integer.parseInt(n[2]);

		int count = 0;

		for (int i = a; i <= b; i++) {
			if (c % i == 0) {
				count++;
			}

		}
		System.out.println(count);

	}

}



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

using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vb = vector<bool>;
using vs = vector<string>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const ld eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i, a, b) for (ll i=(a); i<(b);i++)
#define FORD(i, a, b) for (ll i=ll(b)-1; i>=(a); i--)
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

double p[3000];
double dp[3005][3005];

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

	cout << fixed << setprecision(12);

	ll n;
	cin >> n;

	FOR(i, 0, n) {
		cin >> p[i];
	}

	dp[0][0] = (1 - p[0]);
	dp[0][1] = p[0];

	FOR(curNum, 1, n) {
		dp[curNum][0] = dp[curNum - 1][0] * (1 - p[curNum]);
	}

	FOR(numHeads, 1, n + 1) {
		FOR(curNum, 1, n) {
			dp[curNum][numHeads] =
					dp[curNum - 1][numHeads] * (1 - p[curNum]) + dp[curNum - 1][numHeads - 1] * p[curNum];
		}
	}

	double sum = 0;
	FOR(numHeads, ceil(n / 2.0f), n + 1) {
		sum += dp[n - 1][numHeads];
	}
	cout << sum;

}

Measured memory_bytes: 70656
from collections import deque

N,M,Q = map(int,input().split())
QUERY = [0]*Q
for i in range(Q):
    QUERY[i] = tuple(map(int,input().split()))

ans = 0
D = deque()
D.append(-1)
D.append(1)
dlen = 2
A = deque()
Alen = 0
while dlen != 0:
    f = D.pop()
    dlen -= 1
    if f == -1:
        A.pop()
        Alen -= 1
        continue
    A.append(f)
    Alen += 1
    if Alen == N:
        e = 0
        for a,b,c,d in QUERY:
            a -= 1
            b -= 1
            if A[b] - A[a] == c:
                e += d
        ans = max(ans,e)
    else:
        for AA in range(A[-1],M+1):
            D.append(-1)
            D.append(AA)
            dlen += 2

print(ans)


Measured memory_bytes: 68684
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int[] dp;
		while(scan.hasNext()){
			int n = scan.nextInt();
			if(n == 0){
				break;
			}
			int[] a = new int[n];
			for(int i = 0;i < n;i++){
				a[i] = scan.nextInt();
			}
			dp = new int[n];
			int res = dp[0] = a[0];
			for(int i = 0;i < n;i++){
				for(int j = 0;j < i;j++){
					dp[i] = maximum(a[i],a[i]+dp[j]);
				}
				res = maximum(res,dp[i]);
			}
			System.out.println(res);
		}
	}
	public static int maximum(int a,int b){
		return (a > b)?a:b;
	}
}

Measured memory_bytes: 26456
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

ans = 0
for i in range(K, N + 2):
    ans += (N + N - i + 3) * i // 2 - i * (i + 1) // 2 + 1
    ans %= MOD
print(ans)


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

int main() {
  int n; cin >>n;
  string s; cin>>s;
  ll ans=0;
  for(int i=0; i<n;i++) {
    set<char> cs;
    for(int j=0;j<=i;j++) {
      cs.insert(s[j]);
    }
    set<char> acc;
    for(int j=i+1; j<n; j++) {
      if(cs.find(s[j])!=cs.end()) acc.insert(s[j]);
    }
    ans=max(ans,(ll)acc.size());
  }
  cout << ans <<'\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MN 201000
#define MM 801000

int h[MN], nxt[MM], to[MM], cap[MM], K = 1;
int iter[MN], d[MN], q[MN], hh = 0, tt = 0;
std::vector<int> B[MN];
int x[MN], y[MN];
bool used[MN]; int mat[MN];

void ins(int u, int v, int c) {nxt[++K] = h[u]; h[u] = K; to[K] = v; cap[K] = c;}
void insw(int u, int v, int c) {ins(u, v, c); ins(v, u, 0);}

bool bfs(int S, int T)
{
	memset(d, 0, sizeof(d));
	hh = tt = 0; d[S] = 1; q[tt++] = S;
	while(hh < tt)
	{
		int u = q[hh++];
		for(int i = h[u]; i; i = nxt[i])
			if(cap[i] && !d[to[i]])
			{
				d[to[i]] = d[u] + 1;
				if(to[i] == T) return 1;
				q[tt++] = to[i];
			}
	}
	return 0;
}

int dfs(int u, int T, int f)
{
	if(u == T) return f;
	int used = 0;
	for(int &i = iter[u]; i; i = nxt[i])
		if(cap[i] && d[to[i]] == d[u] + 1)
		{
			int w = dfs(to[i], T, std::min(f - used, cap[i]));
			if(w)
			{
				cap[i] -= w; cap[i ^ 1] += w; used += w; 
				if(used == f) return f;
			}
		}
	return used;
}

int dinic(int S, int T)
{
	int flow = 0;
	while(bfs(S, T))
	{
		memcpy(iter, h, sizeof(h));
		int f;
		while(f = dfs(S, T, 1e9)) flow += f;
	}
	return flow;
}

int main()
{
	int n; scanf("%d", &n);
	int S = 2 * n, T = S + 1; 
	for(int i = 1; i < n; i++)
	{
		int o; scanf("%d", &o);
		for(int j = 1; j <= o; j++) 
		{
			int k; scanf("%d", &k);
			B[k].push_back(i);
			insw(i, n - 1 + k, 1); 
		}
		insw(S, i, 1);
	}
	for(int i = n; i < 2 * n; i++) insw(i, T, 1);
	if(dinic(S, T) != n - 1) return 0 * puts("-1");
	for(int i = 1; i < n; i++)
		for(int j = h[i]; j; j = nxt[j])
			if(!cap[j] && n <= to[j] && to[j] < 2 * n) mat[i] = to[j] - n + 1;
	for(int i = 1; i < n; i++) used[mat[i]] = 1;
	hh = tt = 0;
	for(int i = 1; i <= n; i++) if(!used[i]) q[tt++] = i; 
	memset(used, 0, sizeof(used));
	while(hh < tt)
	{
		int u = q[hh++];
		for(int i = 0; i < B[u].size(); i++)
		{
			if(!used[B[u][i]]) 
			{
				used[B[u][i]] = 1;
				x[B[u][i]] = mat[B[u][i]]; y[B[u][i]] = u;
				q[tt++] = mat[B[u][i]];
			}
		}
	}
	for(int i = 1; i < n; i++) if(!used[i]) return 0 * puts("-1");
	for(int i = 1; i < n; i++) printf("%d %d\n", x[i], y[i]);
}

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

using namespace std;

using ll = long long int;
using P = pair<int, int>;

int main() {
    // Input
    int N, M;
    vector<int> A, B;

    cin >> N >> M;
    A = vector<int>(M);
    B = vector<int>(M);
    rep(i, M) cin >> A[i] >> B[i];

    // Process
    vector<vector<int>> nexts(N, vector<int>());
    rep(i, M) {
        nexts[A[i] - 1].emplace_back(B[i] - 1);
        nexts[B[i] - 1].emplace_back(A[i] - 1);
    }

    vector<int> ans(N, -1);
    queue<int> room_queue;
    ans[0] = 0;
    room_queue.push(0);

    while (!room_queue.empty()) {
        int room = room_queue.front();
        room_queue.pop();

        for (int i : nexts[room]) {
            if (ans[i] == -1) {
                room_queue.push(i);
                ans[i] = room + 1;
            }
        }
    }

    // Output
    cout << "Yes" << endl;
    for (int i = 1; i < N; i++) cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 11736
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Graph vector<vector<ll>>
constexpr ll INF=(1ll<<60);
constexpr ll mod=1000000007;
constexpr double pi=3.14159265358979323846;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
	ll n;cin>>n;
	vector<ll> x(n),ins(n);
	rep(i,n){
		cin>>x[i];
		ins[i]=x[i];
	}
	sort(ins.begin(),ins.end());

	double mid=(ins[n/2-1]+ins[n/2])/2;//真の中央値
	ll mid1=ins[n/2];
	ll mid2=ins[n/2-1];

	rep(i,n){
		if(mid-x[i]>=0.0) cout<<mid1<<endl;
		else cout<<mid2<<endl;
	}

    return 0;
}

Measured memory_bytes: 6348
from itertools import combinations

int(input())
a = list(map(int, input().split()))

n = max(a)
s = n
r = n
d = n

for i, x in enumerate(a):
    if d >= abs(x - n / 2) and x != s:
        d = abs(x - n / 2)
        r = x

print(n)
print(r)

Measured memory_bytes: 14348
#include <bits/stdc++.h>
#define int long long
#define all(c) (c).begin(),(c).end()
#define pii pair<long long,long long>
#define endl '\n'

using namespace std;

signed main(){
    std::ios::sync_with_stdio(false);
    int a,b,c,x,y;
    cin >> x >> y >> a >> b >> c;
    vector<int> A(a,0);
    vector<int> B(b,0);
    vector <int> C(c,0);
    for(int i=0;i<a;i++){
        cin >>A[i];
    }
    for(int i=0;i<b;i++){
        cin >> B[i];
    }
    for(int i=0;i<c;i++){
        cin >> C[i];
    }
    vector<int> L(x+y,0);
    sort(all(A));
    sort(all(B));
    sort(all(C));
    for(int i=0;i<x;i++){
        L[i]=A[a-1-i];
    }
    for(int i=0;i<y;i++){
        L[i+x]=B[b-1-i];
    }
    sort(all(L));
    for(int i=0;i<min(x+y,c);i++){
        if(L[i]<C[c-1-i]){
            L[i]=C[c-1-i];
        }
        else break;
    }
    int ans=0;
    for(int i=0;i<x+y;i++){
        ans+=L[i];
    }
    cout << ans;
}

Measured memory_bytes: 3968