akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

vector<vector<ll>> g;
vector<ll> cost;

void dfs(int v, int p=-1, int sum=0){
    cost[v] += sum;
    for(auto x: g[v]){
        if(x==p) continue;
        dfs(x, v, cost[v]);
    }
}


int main(){
    int n, q;   cin >> n >> q;
    g.resize(n);    cost.resize(n);
    REP(i, n-1){
        int a, b;   cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    REP(i, q){
        int p, x;   cin >> p >> x;
        cost[p-1] += x;
    }
    dfs(0);
    REP(i, n)   cout << cost[i] << ' ';
    cout << endl;
}


Measured memory_bytes: 24320
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

vector<vector<int>> nCr(int n){
  vector<vector<int>> ret(n+1,vector<int>(n+1));
  for(int i=0;i<n+1;i++){
    for(int j=0;j<i+1;j++){
      if(j==0||j==1)ret[i][j]=i;
      else ret[i][j]=ret[i-1][j-1]+ret[i-1][j];
    }
  }
  return ret;
}

signed  main(){
  int n,a,b;
  cin>>n>>a>>b;
  vector<vector<int>> conbination=nCr(n);
  vector<int> v(n);
  REP(i,n)cin>>v[i];
  sort(ALL(v));
  reverse(ALL(v));
  int sum=0;
  REP(i,a)sum+=v[i];
  double ave=(double)sum/a;
  int l=0,r=0;

  for(int i=0;i<n;i++){
    if(v[i]==v[a-1]){
      l++;
      if(i<a)r++;
    }
  }
  int ans=0;
  if(r==a){
    for(int i=a;i<b+1;i++){
      ans+=conbination[l][i];
    }
  }else{
    ans+=conbination[l][r];
  }
  printf("%f\n",ave);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a;	//a[0]:A1
        a = new int[n];

        for (int i=1; i<n; i++) {
        	a[i] = 0;
        }

        for (int i=1; i<n; i++) {
        	a[(scan.nextInt())-1] += 1;
        }

        for (int i=0; i<n; i++) {
			System.out.println(a[i]);
        }
	    scan.close();	
    }
}

Measured memory_bytes: 60452
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int mx=2e6+5;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	/*freopen(".in", "r", stdin);
	freopen(".out", "w", stdout); 
    */
    int ans=0;
	string s,t;cin >> s >> t;
	for(int i=0;i<s.length();++i){
		if(s[i]!=t[i])++ans;
	}
    cout << ans << endl;
}
	


Measured memory_bytes: 3884
// 参考
// https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

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

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

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

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

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

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

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

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

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

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r"2017/01/07
" => r"2018/01/07",

r"2017/01/31
" => r"2018/01/31"
}

use std::cmp;
use std::collections::HashSet;
use std::f32::MAX;

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        s: String
    }
    let mut ans = String::from("");
    let mut i = 0;
    for c in s.chars() {
        if i == 3 {
            ans.push('8');
        } else {
            ans.push(c);
        }
        i += 1;
    }
    ans.to_string()
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;
typedef long long lint;

int main() {
    int N;
    lint A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    N -= 1;
    for (int i = 0; i < N; i++) {
        lint mini = A - i * D + (N - i) * C;
        lint maxi = A - i * C + (N - i) * D;
        if (mini <= B && B <= maxi) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
	static void Main(string[] args)
	{
		string[] input = Console.ReadLine().Split(' ');
		int N = int.Parse(input[0]);
		int Q = int.Parse(input[1]);

		string S = Console.ReadLine();

		int[] l = new int[Q];
		int[] r = new int[Q];

		for(int i=0; i<Q; i++) {
			string[] lr = Console.ReadLine().Split(' ');
			l[i] = int.Parse(lr[0]);
			r[i] = int.Parse(lr[1]);
		}

		int[] index = new int[100000];
		int foundCount = 0;
		for(int i=0; i<N; i++) {
			if(S[i]=='A' && i+1<N && S[i+1]=='C') {
				foundCount++;
			}
			index[i] = foundCount;
		}

		for(int i=0; i<Q; i++) {
			int startCount = (l[i]-2) >=0 ? index[ (l[i]-2) ] : 0;
			int endCount = (r[i]-2) >=0 ? index[ (r[i]-2) ] : 0;
			Console.WriteLine(endCount-startCount);
		}
	}
}

Measured memory_bytes: 17096
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int bit[N];

void add(int pos, int val) {
	for(;pos < N;pos+=pos&-pos)
		bit[pos] = max(bit[pos], val);
}

int qry(int pos) {
	int ret = 0;
	for(;pos;pos-=pos&-pos)
		ret = max(ret, bit[pos]);
	return ret;
}

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	vi h(n), a(n);
	for(int i = 0; i < n; i++) cin >> h[i];
	for(int i = 0; i < n; i++) cin >> a[i];
	int mx = 0;
	for(int i = 0; i < n; i++) {
		int dp = a[i] + qry(h[i]);
		add(h[i], dp);		
		mx = max(mx, dp);
	}
	cout << mx << endl;
}



Measured memory_bytes: 8020
using System;

namespace A___Security
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine().ToCharArray();

            for (int i = 1; i < 4; i++)
            {
                if (S[i] == S[i - 1])
                {
                    Console.WriteLine("Bad");
                    return;
                }
            }

            Console.WriteLine("Good");
        }
    }
}


Measured memory_bytes: 11092
def main():
    S, T = map(str, input().split())
    A, B = map(int, input().split())
    U = input()
    if S == U:
        print(A-1, B)
    elif T == U:
        print(A, B-1)
    else:
        print(A, B)

if __name__ == '__main__':
    main()


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

ll dp[1010][1010];
const int mod = 1e+9+7;

int main() {
  int h,w; cin >> h >> w;
  string a[h];
  REP(i,h) cin >> a[i];

  dp[0][0] = 1;
  REP(i,h) REP(j,w) {
    if (a[i+1][j] == '.') {
      if (j > 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j]+dp[i+1][j-1]);
      else dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      dp[i+1][j]%=mod;
    }
    if (a[i][j+1] == '.') {
      if (i > 0) dp[i][j+1] = max(dp[i][j+1], dp[i][j]+dp[i-1][j+1]);
      else dp[i][j+1] = max(dp[i][j+1], dp[i][j]);
      dp[i][j+1]%=mod;
    }
  }
  cout << dp[h-1][w-1] << endl;
}


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

int main(){
    ll n, m, i, total=0;
    vector<pair<ll, ll>> v;
    cin >> n >> m;
    for(i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end());
    for(auto p: v){
        if(p.second > m){
            total += m * p.first;
            break;
        }
        total += p.first * p.second;
        m -= p.second;
    }
    cout << total << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n;
	cin >> n;
	vector<pair<int, int>> P;
	int in;
	for (int i = 1; i <= n; ++i)
	{
		cin >> in;
		P.push_back(make_pair(in, i));
	}
	sort(P.begin(), P.end());
	for (auto o : P)
	{
		cout << o.second << " ";
	}
	cout << endl;
	return 0;
}

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

int main(){
  int N,M;cin>>N>>M;
  vector<pair<int,int> > S(N);
  for(int i=0;i<N;i++){
    int A,B;
    cin>>A>>B;
    S[i]=make_pair(A,B);
  }
  sort(S.begin(),S.end());
  long long cm=0;
  int cb=0;
  for(int i=0;i<N;i++){
    if(M-cb>S[i].second){
      cb+=S[i].second;
      cm+=(long long)S[i].first*(long long)S[i].second;
    }
    else{
      cm+=(long long)(S[i].first)*(long long)(M-cb);
      break;
    }
  }
  cout<<cm<<endl;
  return 0;
}

Measured memory_bytes: 1024
// By Mohit Gupta
#include <bits/stdc++.h>
using namespace std;
//DEBUG 
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define printint(v) copy(begin(v), end(v), ostream_iterator<int>(cout," "))
#define printintv(s,e) copy(s,e, ostream_iterator<int>(cout," "))
#define forstl(i,v) for(auto &i: v)
#define all(v) (v).begin(), (v).end()
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for ll)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define pb push_back
#define fi first
#define se second
#define int long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
#pragma GCC optimize ("-O2")
const int LIM = 5e5+5, MOD = 2019;
int t,n,m,k,x,y; 
 
int32_t main()
{
    IOS;
    string s;
    cin>>s;
    n=s.size();
    v32 freq((int)2019,0);
    int ans=0;
    forn(i,n){
      char ch=s[i];
      v32 next(2019,0);
      forn(i,2019){
        next[(10*i + ch-'0')%MOD]+=freq[i];
      }
      next[ch-'0']++;
      ans+=next[0];
      freq=next;
    }
    cout<<ans<<ln;
}


Measured memory_bytes: 3784
a = str(input())

if a[0]=="A":
    if "C" in a[2:len(a)-1]:
        ad = a[1:].replace("C","")
        if len(ad)==len(a)-2:
            if ad.islower():
                print("AC")
            else:
                print("WA")
        else:
            print("WA")
    else:
        print("WA")
else:
    print("WA")
            

Measured memory_bytes: 3060
using System;
using System.Linq;
using CompLib.Util;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        long a = sc.NextLong();
        string b = sc.Next();
        long bb = 0;
        for (int i = 0; i < 4; i++)
        {
            if (i == 1) continue;
            bb *= 10;
            bb += b[i] - '0';
        }

        long ans = a * bb / 100;
        Console.WriteLine(ans);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 27488
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <string>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <functional>
 
using namespace std;
 
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
//#define scanf scanf_s
 
int n, a[105];
ll int dp[105][25];
 
ll int sagasitehappy(int i, int j)
{
    if (j > 20 || j < 0) return 0;
    if (dp[i][j] >= 0) return dp[i][j];
    if (i == n - 1)
    {
        if (j == a[n-1]) return 1;
        else return 0;
    }
    else
    {
        dp[i][j] = sagasitehappy(i + 1, j + a[i]) + sagasitehappy(i + 1, j - a[i]);
        return dp[i][j];
    }
}
 
int main()
{
    cin >> n;
    REP(i, n) cin >> a[i];
    REP(i, 105)REP(j, 25)dp[i][j] = -1;
    cout<<sagasitehappy(1, a[0]) << endl;
    return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  int n;
  cin>>n;
  vector<pair<int,int>> vec;
  int m, sum;
  if (n%2==0) {
    sum=n+1;
    m=(n-2)*n/2;
  } else {
    sum=n;
    m=(n-1)*(n-1)/2;
  }
  cout<<m<<endl;
  vector<vector<bool>> used(n+5,vector<bool>(n+5,false));
  for (int i = 1; i <= n; ++i)
  {
    used[i][i]=true;
  }
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= n ; ++j)
    {
      if (used[i][j]) continue;
      if (i+j==sum) continue;
      cout<<i<<" "<<j<<endl;
      used[i][j]=true;
      used[j][i]=true;
    }
  }

  for (int i = 0; i < vec.size(); ++i)
  {
    for (int j = 1; j <=n ; ++j)
    {
      if (vec[i].first==j||vec[i].second==j) continue;
      cout<<vec[i].first<<" "<<j<<endl;
    }
  }
}

Measured memory_bytes: 3484
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<int> > mat;

int fib[9] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
const ll mod = 1e9 + 7;

int main()
{
  ll h, w, k;
  cin >> h >> w >> k;
  k--;
  ll dp[110][10];
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      dp[i + 1][j] += dp[i][j] * fib[j] * fib[w - j - 1];
      dp[i + 1][j] %= mod;
      if (j < w - 1)
      {
        dp[i + 1][j + 1] += dp[i][j] * fib[j] * fib[w - j - 2];
        dp[i + 1][j + 1] %= mod;
      }
      if (j > 0)
      {
        dp[i + 1][j - 1] += dp[i][j] * fib[j - 1] * fib[w - j - 1];
        dp[i + 1][j + 1] %= mod;
      }
    }
  }
  cout << ((dp[h][k] % mod) + mod) % mod << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#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 all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int main() {
	int N,M;
	cin>>N>>M;
	vector<P> v;
	rep(i,M){
		int a,b;
		cin>>a>>b;
		v.push_back({a,b});
	}
	sort(v.rbegin(), v.rend());
	printpair(v);
	int ans = 0;
	int r = INF;
	rep(i,M){
		if(v[i].second<=r){
			ans++;
			r = v[i].first;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1400
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int[] array = new int[3];
        for (int i = 0; i < 3; i++) {
            array[i] = scanner.nextInt();
        }

        Arrays.sort(array);
        final int a = array[0];
        final int b = array[1];
        final int c = array[2];

        int result = 0;
        result += c - b;
        if ((b - a) % 2 == 1) {
            result += 2;
        }
        result += (b-a) / 2;

        System.out.println(result);
    }
}


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int a, b, c, d; cin >> a >> b >> c >> d;

    bool taka_turn = true;

    while (a > 0 && c > 0) {
        if (taka_turn) {
            if (c - b <= 0) {
                puts("Yes");
                return 0;
            }

            c -= b;
            taka_turn = false;
        } else {
            if (a - d <= 0) {
                puts("No");
                return 0;
            }

            a -= d;
            taka_turn = true;
        }
    }
}

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

int main(void){
    map<ll, ll> f;
    ll s;
    cin >> s;
    f[s]++;

    ll count = 1;
    while(true){
        count++;
        if(s % 2 == 1){
            s = 3 * s + 1;
        }else{
            s = s / 2;
        }
        f[s]++;
        if(f[s] == 2) break;
    }

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


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define max(a,b)((a)>(b)?(a):(b))
const int N=2e5+3;
struct edge{int v,nxt;}g[N+N];
int n,dfn[N],siz1[N],ord[N],p[N],siz[N],f[N],fa[N],bt[N],head[N],k,t;
inline int Sum(int k){int s=0;for(;k;k-=k&-k)s+=bt[k];return s;}
inline void Add(int k,int a){for(;k&&k<=n;k+=k&-k)bt[k]+=a;}
int Find(int u){return p[u]==u?u:p[u]=Find(p[u]);}
struct query{int u,a,f;}q[N+N];
bool Cmp(const query&a,const query&b){return a.a<b.a;} 
inline void Insert(int u,int v){g[++k]=(edge){v,head[u]};head[u]=k;}
void Dfs0(int u){
	int v;
	ord[dfn[u]=++t]=u,siz1[u]=1;
	for(int i=head[u];i;i=g[i].nxt)if((v=g[i].v)!=fa[u])
	  fa[v]=u,Dfs0(v),siz1[u]+=siz1[v];
}
void Dfs1(int u,int x){
	int v;
	x=max(x,fa[fa[u]]);
	if(u<x)f[u]--,q[++k]=(query){u,x,-1};
	f[u]++,q[++k]=(query){u,max(fa[u],x),1};
	for(int i=head[u];i;i=g[i].nxt)if((v=g[i].v)!=fa[u])
	  Dfs1(v,x);
}
signed main(){
	int u,v,j;
	scanf("%d",&n);
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),Insert(u,v),Insert(v,u);
	for(u=1;u<=n;u++)p[u]=u,siz[u]=1;
	t=0,Dfs0(1);
	k=0,Dfs1(1,0);
	std::sort(q+1,q+1+k,Cmp);
	for(u=1,j=1;u<=n;u++){
	  for(;q[j].a<=u&&j<=k;j++)f[q[j].u]+=q[j].f*(Sum(dfn[q[j].u]+siz1[q[j].u]-1)-Sum(dfn[q[j].u]-1));
	  p[u]=Find(fa[u]),siz[Find(fa[u])]+=siz[u];
	  Add(dfn[fa[u]],siz[u]),Add(dfn[fa[Find(fa[u])]],-siz[u]);
	}
	for(int i=2;i<=n;i++)f[ord[i]]+=f[fa[ord[i]]];
	for(u=2;u<=n;u++)printf("%d ",f[u]-1);
	return 0;
}

Measured memory_bytes: 32212
#include <bits/stdc++.h>
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
#ifdef _WIN32
#include <windows.h>
#define print(x) PRINT(x, #x)
template<typename T> inline const void PRINT(T VARIABLE, string NAME)
{
#ifndef ONLINE_JUDGE /// ONLINE_JUDGE IS DEFINED ON CODEFORCES
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, 10);
    cerr << NAME << " = " << VARIABLE;
    SetConsoleTextAttribute(hConsole, 7);
    cerr << '\n';
#endif
}
#else
#define print(x) 0
#endif
struct pair_hash
{
    template<typename T1, typename T2>
    size_t operator () (const pair<T1, T2> &p) const
    {
        auto h1 = hash<T1> {}(p.first);
        auto h2 = hash<T2> {}(p.second);
        return h1 ^ h2;
    }
};
typedef long long ll;
typedef unsigned long long ull;
const ll INFLL = 2 * (ll)1e18 + 100;
const int INFINT = 2 * (int)1e9 + 100;
//ifstream fin(".in");
//ofstream fout(".out");
void die()
{
    cout << "-1\n";
    exit(0);
}
const int NMAX = 2 * 1e5 + 5;
const int MOD = 1e9 + 7; /// careful here (7 or 9, 66.. etc)
const double PI = atan(1) * 4;
const double EPS = 1e-12;

ll n;

int main()
{
    FASTIO;
    cin >> n;
    for(ll x = 1; x <= 3500; x++) for(ll y = x; y <= 3500; y++)
    {
        if((4 * x * y - n * x - n * y) > 0 && n * x * y % (4 * x * y - n * x - n * y) == 0)
            return cout << x << ' ' << y << ' ' << n * x * y / (4 * x * y - n * x - n * y), 0;
    }


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    class ForStudy
    {
        public static void Main(string[] args)
        {
            string W = Console.ReadLine().ToLower();
            string T;
            int count = 0;
            while ((T = Console.ReadLine()) != "END_OF_TEXT")
            {
                string[] words = T.ToLower().Split(' ').ToArray();
                foreach(string word in words)
                {
                    if(word.Length==W.Length&& word.Contains(W))
                    
                    {
                        count++;
                    }
                }

            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 18212
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
const int MOD = 1000000007;

int main()
{
  int X,Y;
  cin >> X >> Y;
  cout << (X+Y/2) << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}



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

int main()
{
	int N, X;

	cin >> N >> X;

	int L[N + 1];

	for (int i = 1; i <= N; i++)
	{
		cin >> L[i];
	}

	int D[N + 2];
	int count;

	D[1] = 0;

	if (D[1] <= X)
	{
		count = 1;
	}
	else
	{
		count = 0;
	}

	for (int i = 2; i <= N + 1; i++)
	{
		D[i] = D[i - 1] + L[i - 1];
		if (D[i] <= X)
		{
			count++;
		}
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 256
N = int(input())

x = {1}
for k in [6, 9]:
    v = k
    while v <= N:
        x.add(v)
        v *= k

dp = [999 for _ in range(N+1)]
dp[0] = 0
for k in range(N+1):
    for v in x:
        if 0 <= k - v:
            dp[k] = min(dp[k-v]+1, dp[k])
print(dp[N])


Measured memory_bytes: 3864
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iomanip>
using namespace std;
int main(){
	string s;
	cin >> s;
	if((int)s.find("a")==-1){
		cout << "a" <<endl; return 0;
	}
	if((int)s.find("b")==-1){
		cout << "b" <<endl; return 0;
	}
	if((int)s.find("c")==-1){
		cout << "c" <<endl; return 0;
	}
	if((int)s.find("d")==-1){
		cout << "d" <<endl; return 0;
	}
	if((int)s.find("e")==-1){
		cout << "e" <<endl; return 0;
	}
	if((int)s.find("f")==-1){
		cout << "f" <<endl; return 0;
	}
	if((int)s.find("g")==-1){
		cout << "g" <<endl; return 0;
	}
	if((int)s.find("h")==-1){
		cout << "h" <<endl; return 0;
	}
	if((int)s.find("i")==-1){
		cout << "i" <<endl; return 0;
	}
	if((int)s.find("j")==-1){
		cout << "j" <<endl; return 0;
	}
	if((int)s.find("k")==-1){
		cout << "k" <<endl; return 0;
	}
	if((int)s.find("l")==-1){
		cout << "l" <<endl; return 0;
	}
	if((int)s.find("m")==-1){
		cout << "m" <<endl; return 0;
	}
	if((int)s.find("n")==-1){
		cout << "n" <<endl; return 0;
	}
	if((int)s.find("o")==-1){
		cout << "o" <<endl; return 0;
	}
	if((int)s.find("p")==-1){
		cout << "p" <<endl; return 0;
	}
	if((int)s.find("q")==-1){
		cout << "q" <<endl; return 0;
	}
	if((int)s.find("r")==-1){
		cout << "r" <<endl; return 0;
	}
	if((int)s.find("s")==-1){
		cout << "s" <<endl; return 0;
	}
	if((int)s.find("t")==-1){
		cout << "t" <<endl; return 0;
	}
	if((int)s.find("u")==-1){
		cout << "u" <<endl; return 0;
	}
	if((int)s.find("v")==-1){
		cout << "v" <<endl; return 0;
	}
	if((int)s.find("w")==-1){
		cout << "w" <<endl; return 0;
	}
	if((int)s.find("x")==-1){
		cout << "x" <<endl; return 0;
	}
	if((int)s.find("y")==-1){
		cout << "y" <<endl; return 0;
	}
	if((int)s.find("z")==-1){
		cout << "z" <<endl; return 0;
	}

	cout << "None" << endl;	return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
    static int n, m;
    static int[] p;
    static int modP = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        p = new int[n];

        UF uf = new UF(n);
        for(int i = 0; i < n; i++) p[i] = in.nextInt();
        for(int i = 0; i < m; i++) {
            int x = in.nextInt()-1;
            int y = in.nextInt()-1;
            uf.union(x, y);
        }

        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(uf.same(i, p[i]-1)) cnt++;
        }
        print(cnt);
    }

    static void print(String s) {
        System.out.println(s);
    }

    static void print(int i) {
        System.out.println(i);
    }
}

class UF {
    int[] table, ranks;

    UF(int s) {
        table = new int[s];
        ranks = new int[s];
        for(int i = 0; i < s; i++) {
            table[i] = i;
        }
    }

    public int find(int x) {
        if(table[x] != x) table[x] = find(table[x]);

        return table[x];
    }

    public void union(int x , int y) {
        int xR = find(x);
        int yR = find(y);
        if(xR == yR) return;

        if(ranks[xR] < ranks[yR]) {
            table[xR] = yR;
        }else{
            table[yR] = xR;
            if(ranks[xR] == ranks[yR]) ranks[xR]++;
        }
    }

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

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

typedef long long ll;

const int E = 50;

int n, cnt[E][E];
ll ans;
char s[E];

int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", s + 1); int l = strlen(s + 1);
		ll tmp = 0; int c2 = -9, c5 = -9, c = 9; bool is = 0;
		for (int i = 1; i <= l; i++)
			if (s[i] == '.') {is = 1; continue;}
			else if (is) tmp = tmp * 10 + s[i] - '0', c--;
			else tmp = tmp * 10 + s[i] - '0';
		while (c--) tmp *= 10;
		while (tmp % 2 == 0) tmp /= 2, c2++;
		while (tmp % 5 == 0) tmp /= 5, c5++;
		for (int i = 36; i >= -c2 && i >= -9; i--)
			for (int j = 20; j >= -c5 && j >= -9; j--)
				ans += cnt[i + 9][j + 9];
		cnt[c2 + 9][c5 + 9]++;
	}
	return std::cout << ans << std::endl, 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int dh[4] = {-1, 0, 1, 0},
    dw[4] = {0, 1, 0, -1};

int main() {
    cout << fixed << setprecision(10);
    
    int H, W; cin >> H >> W;
    vector<vector<int>> a(H, vector<int>(W));
    rep(i, H) rep(j, W) cin >> a[i][j];

    stack<P> stk;
    stk.push(make_pair(0, 0));
    vector<vector<int>> thr(H, vector<int>(W));
    thr[0][0] = 1;
    int has_odd = 0;
    vector<P> troute;
    if (a[0][0] % 2 == 1) {
        has_odd = 1;
        troute.emplace_back(make_pair(0, 0));
    }

    vector<vector<P>> route;
    int n = 0;

    while (!stk.empty()) {
        auto p = stk.top(); stk.pop();
        int ch = p.first, cw = p.second;
        rep(i, 4) {
            int nh = ch + dh[i], nw = cw + dw[i];
            if (nh >= 0 && nw >= 0 && nh < H && nw < W && thr[nh][nw] == 0) {
                stk.push(make_pair(nh, nw));
                thr[nh][nw] = 1;
                if (has_odd) {
                    troute.emplace_back(make_pair(nh, nw));
                    if (a[nh][nw] % 2 == 1) {
                        route.emplace_back(troute);
                        n += troute.size() - 1;
                        troute.clear();
                        has_odd = 0;
                    }
                } else {
                    if (a[nh][nw] % 2 == 1) {
                        troute.emplace_back(make_pair(nh, nw));
                        has_odd = 1;
                    }
                }
                break;
            }
        }
    }

    cout << n << endl;
    rep(i, route.size()) {
        rep(j, route[i].size()-1) {
            cout << route[i][j].first + 1 << " " << route[i][j].second + 1 << " ";
            cout << route[i][j+1].first + 1 << " " << route[i][j+1].second + 1 << endl;
        }
    }


    return 0;
}

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


#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

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

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

int main(){

    bool flag=true;
    ll ans=0,sum=0;

    int n,l;
    cin>>n>>l;
    vector<int> a(n);

    int mxl=0,lstn;
    cin>>a[0];
    rep(i,n-1){
        cin>>a[i+1];

        if( a[i+1]+a[i] > mxl){
            mxl = a[i+1]+a[i];
            lstn = i+1;
        }
    }

    if(mxl < l)flag=false;

    vector<int>ansarr;
    if(flag){
        rep(i,lstn)ansarr.eb(lstn-i);
        rep1(i,lstn+1,n)ansarr.eb(i);
        reverse(all(ansarr));
        
        cout<<"Possible"<<endl;
        for(int ai:ansarr)cout<<ai<<endl;
    
    }else{
        cout<<"Impossible"<<endl;
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 1784
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

constexpr ll mod = 998244353LL;

template<typename T>
struct SegmentTree {
private:
	int sz, n;
	vector<T> data;
	function<T(T, T)> f;
	T identity_element;
public:
	/* constructor */
	SegmentTree(
		const vector<T>& v, // initial data
		T identity_element, // identity element
		function<T(T, T)> f // operation
	) {
		sz = v.size();
		n = 1; while (n < sz) n <<= 1;
		this->f = f;
		this->identity_element = identity_element;
		data.resize(2 * n - 1, identity_element);
		for (int i = 0; i < sz; ++i)
			data[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; --i)
			data[i] = f(data[2 * i + 1], data[2 * i + 2]);
	}
	/* update query */
	void update(int idx, const T val) {
		idx += n - 1;
		data[idx] = val;
		while (idx) {
			idx = (idx - 1) >> 1;
			data[idx] = f(data[2 * idx + 1], data[2 * idx + 2]);
		}
	}
	/* get query */
	T get(int left, int right, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (r <= left || right <= l) return identity_element;
		if (left <= l && r <= right) return data[k];
		T val_l = get(left, right, 2 * k + 1, l, (l + r) / 2);
		T val_r = get(left, right, 2 * k + 2, (l + r) / 2, r);
		return f(val_l, val_r);
	}
};

int main(void){
	int N, K; cin >> N >> K;
	vector<int> L(K), R(K);
	for (int i = 0; i < K; ++i)
		cin >> L[i] >> R[i];
	
	SegmentTree<ll> dp(
		vector<ll>(N, 0LL), 0LL,
		[](ll a, ll b){ return (a + b) % mod; }
	);
	dp.update(0, 1LL);
	for (int i = 1; i < N; ++i){
		ll tmp = 0;
		for (int j = 0; j < K; ++j){
			int l = i - R[j];
			int r = i - L[j];
			if (r < 0) continue;
			l = max(0, l);
			tmp += dp.get(l, r + 1);
			tmp %= mod;
		}
		dp.update(i, tmp);
	}

	ll res = dp.get(N - 1, N);
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 9076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

template<class T>
struct BellmanFord {
    const T INF = numeric_limits<T>::max() / 2 - 1;
    vector<vector<pair<int, T>>> edges;
    int vertex_number;
    bool iinc = false;
    vector<vector<bool>> reachable;
    
    BellmanFord(int n) : edges(n) {
        vertex_number = n;
    }
    
    void add_edge(int from, int to, T cost) {
        edges[from].emplace_back(to, cost);
    }
    
    vector<T> get_distance(int from, int to = -1) {
        vector<T> dist(vertex_number, INF);
        dist[from] = 0;
        for (int i = 0; i < vertex_number; i++) {
            for (int ii = 0, e = edges.size(); ii < e; ii++) {
                if ((to != -1) && (!is_reachable(from, ii))) continue;
                for (int iii = 0, ee = edges[ii].size(); iii < ee; iii++) {
                    if ((to != -1) && (!is_reachable(edges[ii][iii].first, to))) continue;
                    if ((dist[ii] + edges[ii][iii].second) < dist[edges[ii][iii].first]) {
                        if (i != (vertex_number - 1)) {
                            dist[edges[ii][iii].first] = dist[ii] + edges[ii][iii].second;
                        }
                        else {
                            iinc = true;
                            break;
                        }
                    }
                }
            }
        }
        return dist;
    }
    
    bool is_include_negative_circle() {
        return iinc;
    }
    
    void get_reachable_dfs(int from, int to) {
        if (reachable[from][to]) return;
        reachable[from][to] = true;
        for (pair<int, T> e : edges[to]) {
            get_reachable_dfs(from, e.first);
        }
    }
    
    void get_reachable() {
        for (int i = 0; i < reachable.size(); i++) {
            get_reachable_dfs(i, i);
        }
    }
    
    bool is_reachable(int from, int to) {
        if (reachable.size() == 0) {
            reachable.resize(vertex_number, vector<bool>(vertex_number, false));
            get_reachable();
        }
        return reachable[from][to];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    int n, m, p;
    cin >> n >> m >> p;
    BellmanFord<ll> bf(n);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        c = (c - p) * -1;
        bf.add_edge(a, b, c);
    }
    vector<ll> d = bf.get_distance(0, n - 1);
    if (bf.is_include_negative_circle()) {
        cout << -1 << endl;
        return 0;
    }
    cout << max(0LL, d[n - 1] * -1) << endl;
    return 0;
}


Measured memory_bytes: 1536
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]

rm = list(sorted(L))

n = 0
sum = 0
for i in range(M):
  if rm[n][1] == 0:
    n += 1
  rm[n][1] -= 1
  sum += rm[n][0]
  
print(sum)

Measured memory_bytes: 29024
N, A, B = map(x->parse(Int,x), split(readline(STDIN)))
S = rstrip(readline(STDIN), '\n')
c1 = 0
c2 = 0
for i in 1:length(S)
    if c1 < A+B && S[i] == 'a'
        c1 += 1
        println("Yes")
    elseif c1 < A+B && c2 < B && S[i] == 'b'
        c1 += 1
        c2 += 1
        println("Yes")
    else
        println("No")
    end
end

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i = 0; i<n;i++) cin>>arr[i];
    int dp[n];
    dp[0] = 0;
    if(k>=n-1){
        cout<<abs(arr[n-1]-arr[0]);
    }
    else{
        for(int i = 1; i<=k;i++) dp[i] = abs(arr[0]-arr[i]);
        for(int i = k+1; i<n;i++){
            int least =INT_MAX;
            for(int j =i-k;j<i;j++){
                least = min(least,dp[j]+abs(arr[j]-arr[i]));
            }
            dp[i] = least;
        }
        cout<<dp[n-1];
    }
}


Measured memory_bytes: 4372
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

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

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

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

    int cnt = B / A;
    if (cnt >= C) {
        cout << C << endl;
    } else {
        cout << cnt << endl;
    }
}


Measured memory_bytes: 256
import itertools
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=float('inf')
for bit in itertools.product([0,1],repeat=N):
    if bit[0]==1 and bit.count(1)>=K:
        cost=0
        cr=a[0]
        for i in range(1,N):
            if bit[i]==1:
                if cr+1>=a[i]:
                    cost+=(cr+1-a[i])
                    cr=cr+1
                else:
                    cr=a[i]
            else:
                cr=max(cr,a[i])
        ans=min(ans,cost)
print(ans)

Measured memory_bytes: 9168
#include<stdio.h>

int main(){
    int W,H,x,y,r;

    scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
    if(0<=(x-r) && (x+r)<=W && 0<=(y-r) && (y+r)<=H)
        printf("Yes\n");
    else
        printf("No\n");

return 0;
}

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int

int main(){
	int n, m;
	cin >> n >> m;
	int ps[n+1];
	REP(i, n+1) ps[i] = 0;
	REP(i, m){
		int r, l;
		cin >> r >> l;
		r--;
		l--;
		ps[r]++;
		ps[l+1]--;
	}
	REP(i, n) ps[i+1] += ps[i];
	int ans = 0;
	REP(i, n+1) if(ps[i] == m) ans++;
	cout << ans << endl; 
	return 0;
} 


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
//ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
//ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*POW(a,b-1)%mod;ll k=POW(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve(){
  ll n; cin>>n;
  vi a(n);
  rep(i,n) cin>>a[i];
  vi sum(n);
  rep(i,n){
    if(i==0) sum[0]=a[n-1];
    else sum[i]=sum[i-1]+a[n-1-i];
    sum[i]%=mod;
  }
  reverse(all(sum));
  ll ans=0;
  rep(i,n-1){
    ans+=(a[i]*sum[i+1])%mod;
    ans%=mod;
  }
  //outv(sum);
  out(ans);
}

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


Measured memory_bytes: 6364
#include <bits/stdc++.h>
#define lli long long int
#define inf 2147483647
#define infll LLONG_MAX
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    string s;
    cin >> s;
    bool ans = true;
    if(s[2] != s[3] || s[4] != s[5]) ans = false;
    if(ans) Yes();
    else No();
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n, x, y int
	fmt.Scan(&n, &x, &y)
	ans := make([]int, n-1)

	for i := 1; i < n; i++ {
		for j := i + 1; j <= n; j++ {
			d := j - i
			if i <= x {
				if y <= j {
					d -= y - x - 1
				} else if j > x {
					if y-j+1 < j-x {
						d -= j - x
						d += y - j + 1
					}
				}
			} else if i < y && y <= j {
				if i-x+1 < y-i {
					d -= y - i
					d += i - x + 1
				}
			} else if j < y {
				if i-x+y-j+1 < d {
					d = i - x + y - j + 1
				}
			}
			ans[d-1]++
		}
	}

	for _, a := range ans {
		fmt.Println(a)
	}
}


Measured memory_bytes: 512
//abc042_a.cpp
//Fri Oct 19 22:26:06 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int a[3];
	int fivecount = 0;
	int sevencount = 0;
	for (int i=0;i<3;i++){
		cin >> a[i];
		if (a[i] == 5){
			fivecount++;
		}else if (a[i] == 7){
			sevencount++;
		}
	}

	if (fivecount == 2 && sevencount == 1){
		cout << "YES" << endl;
	}else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let p = 1.0 / n as f64;
    let mut dp = vec![vec![vec![0.0; n + 1]; n + 1]; n + 1];
    for i in 0..(n + 1) {
        for j in 0..(n + 1 - i) {
            for k in 0..(n + 1 - i - j) {
                if i == 0 && j == 0 && k == 0 {
                    continue;
                }
                let mut local = 1.0;
                if i > 0 {
                    local += p * (i as f64) * dp[i - 1][j + 1][k];
                }
                if j > 0 {
                    local += p * (j as f64) * dp[i][j - 1][k + 1];
                }
                if k > 0 {
                    local += p * (k as f64) * dp[i][j][k - 1];
                }
                dp[i][j][k] = local * n as f64 / (i + j + k) as f64;
            }
        }
    }
    let mut a = vec![0; 4];
    for s in it {
        let k: usize = s.parse().unwrap();
        a[k] += 1;
    }
    let ans = dp[a[3]][a[2]][a[1]];
    println!("{:.10}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 237820
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int main(){

	int N;
	scanf("%d",&N);

	int* table = new int[N+1];
	for(int i = 1; i <= N; i++)scanf("%d",&table[i]);

	priority_queue<int> LEFT,RIGHT;
	queue<int> ANS;

	for(int i = 1; i <= N; i++){
		LEFT.push(table[i]);
		RIGHT.push(table[N+1-i]);

		while(LEFT.empty() == false && RIGHT.empty() == false && LEFT.top() == RIGHT.top()){
			LEFT.pop();
			RIGHT.pop();
		}
		if(LEFT.empty() == true && RIGHT.empty() == true){
			ANS.push(i);
		}
	}

	printf("%d",ANS.front());
	ANS.pop();

	while(!ANS.empty()){
		printf(" %d",ANS.front());
		ANS.pop();
	}
	printf("\n");

	return 0;
}



Measured memory_bytes: 3880
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const ll oo = 1e18;
const ll mod = 1e9 + 7,maxn = 100000000;
const double PI = acos(-1);

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

    for (int i=0; i<a.size(); i++){
        cout << a[i];
        if (i < b.size())cout << b[i];
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256