akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramD
    {
        struct Info
        {
            public int next;
            public int dist;
        }

        static List<Info>[] _graph;
        static bool[] _seen;
        static int[] _d;

        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(" ");
            var n = int.Parse(inputs[0]);
            var m = int.Parse(inputs[1]);

            _graph = new List<Info>[n];
            for (var i = 0; i < n; i++)
            {
                _graph[i] = new List<Info>();
            }

            for (var i = 0; i < m; i++)
            {
                var inputsM = Console.ReadLine().Split(" ");
                var l = int.Parse(inputsM[0]) - 1;
                var r = int.Parse(inputsM[1]) - 1;
                var d = int.Parse(inputsM[2]);

                // 辺追加(無効グラフ)
                _graph[l].Add(new Info()
                {
                    next = r,
                    dist = d,
                });
                _graph[r].Add(new Info()
                {
                    next = l,
                    dist = -d,
                });
            }

            _seen = new bool[n];
            _d = new int[n];
            for (var i = 0; i < n; i++)
            {
                // 探索
                if (_seen[i]) continue;
                if (dfs(i, 0))
                {
                    Console.WriteLine("No");
                    return;
                }
            }

            Console.WriteLine("Yes");
        }

        // dfs
        // trueが返ったら矛盾
        static bool dfs(int v, int dist)
        {
            if (_seen[v])
            {
                return _d[v] != dist;
            }

            _seen[v] = true;
            _d[v] = dist;
            foreach (var i in _graph[v])
            {
                if (dfs(i.next, _d[v] + i.dist))
                {
                    return true;
                }
            }

            return false;
        }
    }
}


Measured memory_bytes: 61908
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,N;
	while((cin>>n)){
		if(n==0)return 0;
		int l2[4],s2[4],c=0;
		while(n!=6174){
			int L=0,S=0;
			l2[0]=n/1000;
			n%=1000;
			l2[1]=n/100;
			n%=100;
			l2[2]=n/10;
			l2[3]=n%10;
			sort(l2,l2+4);
			s2[0]=l2[3];
			s2[1]=l2[2];
			s2[2]=l2[1];
			s2[3]=l2[0];
			int j=0;
			if(l2[0]==l2[1]&&l2[1]==l2[2]&&l2[2]==l2[3]){
			cout<<"NA"<<endl;
			goto masatoy;
			}
			for(int i=1000;i>=1;i/=10){
				L+=l2[j]*i;
				S+=s2[j]*i;
				j++;
			}
//cout<<c<<"?????????"<<n<<endl;
			n=S-L;
			c++;
		}
		cout<<c<<endl;
masatoy:;
	}
}

Measured memory_bytes: 3148
#include<iostream>
using namespace std;
int main(){
    int p,q,r,min;
    cin>>p>>q>>r;
    min=p+q+r;
    if(min>p+q){
        min=p+q;
    }
    if(min>q+r){
        min=q+r;
    }
    if(min>r+p){
        min=r+p;
    }
    cout<<min<<endl;

    return 0;
}

Measured memory_bytes: 256
use std::io;

macro_rules! get {
    ($t: ty) => {
        {
            let mut x = String::new();
            io::stdin().read_line(&mut x).ok();
            x = x.trim_right().to_owned();
            x.parse::<$t>().unwrap()
        }
    };
}

macro_rules! insert_vec {
    ($t: ty) => {
        {
            let mut x = String::new();
            io::stdin().read_line(&mut x).ok();
            x = x.trim_right().to_owned();
            x.split_whitespace().map(|x| x.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

fn main() {
    let n = get!(usize);
    let mut p = insert_vec!(i32);
    let mut ans; 
    p.sort();
    if p[ n / 2 - 1] == p[ n /2 ] {
        println!("0");
    } else {
        ans = p[n/2] - p [n/2 -1];
        println!("{}", ans);
    };
}



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

// グラフを隣接行列で管理する
bool G[10][10];

int main() {
    int N, M; cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = true;
    }

    // 順列
    vector<int> ord(N);
    for (int i = 0; i < N; ++i) ord[i] = i;

    // 順列を全部試すa
    int res = 0;
    do {
        if (ord[0] != 0) break;

        bool ok = true;
        for (int i = 0; i + 1 < N; ++i) {
            int from = ord[i];
            int to = ord[i+1];
            if (!G[from][to]) ok = false;
        }
        if (ok) ++res;
    } while (next_permutation(ord.begin(), ord.end()));

    cout << res << endl;
}

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

int main() {
  int n;
  cin >> n;
  set<string> s;
  rep(i, n) {
    string S;
    cin >> S;
    s.insert(S);
  }
  cout << s.size() << endl;
  return 0;
}
      

Measured memory_bytes: 19208
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

typedef tuple<ll,ll,ll> T;
int main(int argc, char const *argv[]) {
    int n,q; cin>>n>>q;
    vector<T> a;
    rep(i,n) {
        ll s,t,x; cin>>s>>t>>x;
        a.emplace_back(s-x, 0, x);
        a.emplace_back(t-x, 1, x);
    }
    a.emplace_back(-LINF,0,LINF);
    a.emplace_back(LINF,1,LINF);
    vector<ll> d(q);
    rep(i,q) cin>>d[i];

    sort(a.begin(), a.end());
    sort(d.begin(), d.end());

    multiset<ll> st;
    int idx = 0;
    for (auto &&e: a) {
        ll time, b, x;
        tie(time, b, x) = e;
        while (time > d[idx] && idx < q) {
            if (st.empty() || *st.begin() == LINF) cout << -1 << '\n';
            else cout << *st.begin() << '\n';
            ++idx;
        }
        if (b==0) st.insert(x);
        else {
            auto itr = st.lower_bound(x);
            st.erase(itr);
        }
    }

    return 0;
}

Measured memory_bytes: 23528
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

const int MAX = 5100000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];


// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


/*
int main()
{
	COMinit();
	int a,b;
	cin >> a >> b;
	cout << COM(a,b) << endl;
}
*/
int main()
{
	long long x,y;
	cin >> x >> y;
	if((x+y)%3!=0)
	{
		cout << 0 << endl;
		return 0;
	}

	COMinit();

	cout << COM((x+y)/3,x-(x+y)/3) << endl;



}

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

int main(){
  int n;
  cin >> n;
  
  int count=0;
  rep(i,n+1){
    if(i%2==0) continue;
    int div=0;
    rep(j,i){
      if(i%(j+1)==0) div++;
    }
    if(div==8) count++;
  }
  
  cout << count << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <queue>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
    int n, q;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    cin >> q;
    vector<pair<int, int>> bc(q);
    rep(i, q) cin >> bc[i].first >> bc[i].second;

    vector<int> qty(100001);
    rep(i, n) qty[a[i]]++;
    long long sum = 0;
    for (int j = 1; j < qty.size(); j++) {
        sum += qty[j] * j;
    }
    rep(i, q) {
        int before = bc[i].first;
        int after = bc[i].second;

        sum += (after - before) * qty[before];

        qty[after] += qty[before];
        qty[before] = 0;
        
        cout << sum << endl;
    }
}


Measured memory_bytes: 4764
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

const int N = 200001;

int A[N];
int X[N];

int main() {
  int n;
  S(n);
  rep(i,1,n+1) {
    S(A[i]);
  }
  int mx = 0;
  rep(i,1,n+1) {
    X[A[i]] = X[A[i] - 1] + 1;
    mx = max(mx, X[A[i]]);
  }
  P(n - mx);
  return 0;
}


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

int main() {
	int num_of_mt;
	int max = 0;
	int height = 0;
	int count = 0;

	cin >> num_of_mt;
	for (int i = 0; i < num_of_mt; i++) {
		cin >> height;
		if (height >= max)
			count++;
		if (max < height)
			max = height;
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <fstream>

using namespace std;

const uint32_t N_MAX = 200000;

class BIT
{
private:
	uint32_t dataSize;
	vector<uint32_t> bit;

public:
	BIT(uint32_t n)
	: dataSize(n) {
		bit.resize(dataSize + 1);
		fill(bit.begin(), bit.end(), 0);
	}
	BIT()
	: BIT(0) {}

	void add(const uint32_t index, const uint32_t x);
	uint64_t sum(const uint32_t N) const;
};

inline uint32_t getLSB(uint32_t num) { return num & (~num + 1); }
inline uint32_t getIndex(vector<uint32_t> vec, uint32_t val) {
	return (uint32_t)distance(vec.begin(), lower_bound(vec.begin(), vec.end(), val));
}

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

	uint32_t n, input;
	vector<uint32_t> A;

	cin >> n;
	for(uint32_t i = 0; i < n; i++) {
		cin >> input;
		A.emplace_back(input);
	}

	// fstream fin;
	// fin.open("InputFiles/ALDS1_5_D_19.txt");
	// if(!fin) {
	// 	return 1;
	// }
	// fin >> n;
	// for(uint32_t i = 0; i < n; i++) {
	// 	fin >> input;
	// 	A.emplace_back(input);
	// }

	auto sorted_A = A;
	sort(sorted_A.begin(), sorted_A.end());

	unordered_map<uint32_t, uint32_t> index;
	for(uint32_t i = 0; i < n; i++) {
		index[sorted_A[i]] = i + 1;
	}

	uint64_t totalCount = 0;
	BIT bit(n);
	for(uint32_t i = 0; i < n; i++) {
		totalCount += ((uint64_t)i - bit.sum(index[A[i]]));
		bit.add(index[A[i]], 1);
	}

	cout << totalCount << endl;

	return 0;
}

void BIT::add(const uint32_t index, const uint32_t x) {
	for(uint32_t i = index; i <= dataSize; i += getLSB(i)) {
		bit[i] += x;
	}
}

uint64_t BIT::sum(const uint32_t N) const {
	uint64_t ret = 0;

	for(uint32_t i = N; i > 0; i -= getLSB(i)) {
		ret += (uint64_t)bit[i];
	}
	return ret;
}



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

class Team{
public:
	int id,score;
	string name;
	Team(){}
	Team(int _id,int _score,string _name){
		id = _id;
		score = _score;
		name = _name;
	}
	bool operator<(const Team t)const{
		if(score == t.score) return id < t.id;
		return score > t.score;
	}
};

int main(void){
	int n;
	bool first = true;

	while(cin>>n,n){
		if(first) first = false;
		else cout<<endl;

		Team t[n];
		for(int i=0;i<n;i++){
			string name;
			int a,b,c;
			cin>>name>>a>>b>>c;
			t[i] = Team(i,3*a+c,name);
		}
		sort(t,t+n);
		for(int i=0;i<n;i++){
			cout<<t[i].name<<","<<t[i].score<<endl;
		}
	}

	return 0;
}

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

int main() {
    int A, B;
    string op;
    cin >> A >> op >> B;

    if (op == "+") {
       cout << A + B << endl;  
    }
    else if (op == "-") {
        cout << A - B << endl;
    }
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <fstream>

#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
//constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) {
    if(b==0) return a;
    else return GCD(b, a%b);
}

ll LCM(ll a, ll b) {
    return a/GCD(a,b)*b;
}

class BMultiplication2 {
public:
	void solve(std::istream& in, std::ostream& out) {
	        ll mx = 1e18;
            ll n;
            in>>n;
            uint64_t res=1;
            vector<ll> v(n);
            rep(i,n) in>>v[i];
            sort(all(v));
            rep(i,n){
                ll tmp = v[i];
                if(tmp==0){
                    out<<0<<endl;
                    return;
                }
                if(res*tmp >mx || res*tmp < res){
                    out<<-1<<endl;
                    return;
                }
                res*=tmp;
            }
            out<<res<<endl;

	}
};


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


Measured memory_bytes: 3708
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;



int main()
{
    
    string S;
    cin >> S;
    map<char, ll> m;
    rep(i, 4) {
        m[S[i]]++;
    }
    if (m.size() == 2 && m[S[0]] == 2)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;

int mod=1e9+7;
long long modpow(long long x,long long n,long long mod)
{
  if(n==0)return 1;
  long long res=modpow(x*x%mod,n/2,mod);
  if(n&1)res=res*x%mod;
  return res;
}
long long modinv(long long a,long long m=mod)//extgcdの方がいいらしい
{
  return modpow(a,m-2,m);
}
vector<ll>cal(200001);

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

  int h,w,a,b;
  cin>>h>>w>>a>>b;
  cal[0]=1;
  repi(i,1,200001)
  {
    cal[i]=(ll)cal[i-1]*i%mod;
  }
  ll res=0;
  ll tres=cal[h-a-1+b]*cal[a+w-b-1]%mod;
  ll m=min(h-a,w-b);
  rep(i,m)
  {
    res+=(ll)modinv(cal[b+i])*tres%mod*modinv(cal[h-a-1-i])%mod*modinv(cal[a+i])%mod*modinv(cal[w-b-1-i])%mod;
    res%=mod;
  }
  cout<<res<<endl;



  return 0;

}


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

using namespace std;

int dp[(int)(1e5)+2], a[105];

bool call(int rem, int n)
{
    if(rem<0) return 1;
    if(dp[rem]!=-1) return dp[rem];
    dp[rem] = 1;
    for(int i = 0; i<n; i++) dp[rem] &= call(rem-a[i],n);
    return dp[rem] = !dp[rem];
}

int main()
{
    int n, k;
    scanf("%d %d",&n,&k);
    for(int i = 0; i<n; i++){
        scanf("%d",&a[i]);
    }
    memset(dp,-1,sizeof dp);
    if(call(k,n)) printf("First\n");
    else printf("Second\n");
    return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int a[N];
int cmp(int a,int b){
    return a>b;
}
typedef long long ll;
int main(){

    ll a,b;
    cin>>a>>b;
    a=a%b;
    ll ans=a;
    ans=min(ans,abs(a-b));
    cout<<ans;
}


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

using ll = long long;
constexpr ll INF = 1000000000;
constexpr 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; }

using namespace std;

//fixed << setprecision(10)

/////////////////////////////////////////////////////////////////////////////////////////////////////////

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

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

	map<string, int>seq;

	int cnt = 0;

	for (int i = 0; i < n; i++) {
		if (seq[s[i]] == 0) {
			seq[s[i]]++;
			cnt++;
		}
	}

	cout << cnt << endl;
}

Measured memory_bytes: 25044
s = input().rstrip()
n = len(s)
if n % 2 == 1:
  print("No")
  exit()
for a, b in zip(s[:n//2], s[::-1]):
  if a == "p" and b == "q":
    continue
  elif a == "q" and b == "p":
    continue
  elif a == "b" and b == "d":
    continue
  elif a == "d" and b == "b":
    continue
  else:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

const int MAX_Y = 55;
const int MAX_P = 5050;
vector<vector<double> > dp(MAX_Y, vector<double>(MAX_P));


int main()
{
	int x, y, z;
	while(cin >> x >> y >> z && x)
	{		
		rep(i, MAX_Y)
			fill(ALL(dp[i]), 0.0);

		vector<pint> g(y, make_pair(false, 0));
		vint v(x);
		rep(i, x)
			cin >> v[i];


		rep(i, z)
		{
			int n, e, a;
			cin >> n >> e >> a;

			g[n] = make_pair(e == 1, (e == 3 ? -a : a));
		}


		dp[0][0] = 1.0;
		rep(i, y) rep(j, MAX_P)
		{
			if(dp[i][j] == 0)
			{
				continue;
			}
			/*
			else if(g[i].first)
			{
				int ny = min(i + g[i].second, y);
				int np = j;

				if(ny < y && !g[ny].first)
					np += g[ny].second;
				

				dp[ny][max(0, np)] += dp[i][j];
			}
			*/
			else 
			{
				rep(k, x)
				{
					int ny = min(i + v[k], y);
					int np = j;

					if(ny < y)
					{
						if(g[ny].first) 
							ny += g[ny].second;
						else
							np += g[ny].second;
					}


					dp[min(ny, y)][max(0, np)] += dp[i][j] / x;
				}
			}
		}


		double res = 0;
		rep(i, MAX_P)
			res += dp[y][i] * i;


		cout << int(res) << endl;
	}
}

Measured memory_bytes: 3116
#include <iostream>

using namespace std;

int main() {
	int x, n, p;
  	bool arr[102];
  	cin >> x >> n;
  	for (int i = 0; i < 102; i++) arr[i] = false;
    for (int i = 0; i < n; i++) {
      cin >> p;
      arr[p] = true;
    }
  	int i = 0;
  	int result;

  	while (true) {
      if (!arr[x-i]) {
        result = x - i;
        break;
      } else if (!arr[x+i]) {
        result = x + i;
        break;
      }
      i++;
    }
    cout << result;
	return 0;
}

Measured memory_bytes: 3116
/* *
 *
 * Author: Hamkor
 *
 * */

#include <bits/stdc++.h>

using namespace std;

/* * * *   * * *   	* * * */
typedef long long ll;
const int oo = 1e9;
const ll mod = 100000000;
typedef complex<ll> P;
#define X real()
#define Y imag()
/* * * *   * * *   	* * * */

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int a, b, c; cin>>a>>b>>c;
    cout<<max(c*10 + a + b, max(a*10 + b + c, a + b*10 + c));
	return 0;
}

Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
# S = input()
#n = int(input())
A,B,C  = map(int, input().split())
#a = list(map(int, input().split()))
# LR = [list(map(int, input().split())) for _ in range(M)]

ans = 0

D = A+B

if D >= C -1:
    print(B+C)
else:
    print(B+D+1)






Measured memory_bytes: 6032
L = list(input())

results = []

for i in range(2**(len(L)-1)) :
    calc = ""
    for j in range(len(L)-1) :
        calc += L[j]
        if i % 2 != 0 :
            calc += "+"
        i >>= 1
    f = calc + L[-1]
    results.append(eval(f))
print(sum(results))


Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>

typedef struct{
    int *list;
    int elm;
}block;

typedef struct{
    int par;
    int size;
}uf_node;

static inline int root(int index,uf_node *uf){
    if(uf[index].par == index)return index;
    return uf[index].par = root(uf[index].par,uf);
}

static inline void marge(int x,int y,uf_node *uf){
    int rt_x = root(x,uf);
    int rt_y = root(y,uf);
    if(rt_x== rt_y)return;
    uf[rt_x].par = rt_y;
    uf[rt_y].size += uf[rt_x].size;
}

static inline int jud_same(int x,int y,uf_node *uf){
    return root(x,uf) == root(y,uf);
}

int main(void){
    int n,m,b;
    scanf("%d %d %d",&n,&m,&b);
    int tmp,tmp_;
    block bl[n];
    int friend[n];
    uf_node uf[n];
    for(int i = 0;i < n;i++){
        bl[i].elm = 0;
        bl[i].list = NULL;
        friend[i] = 0;
        uf[i].par = i;
        uf[i].size = 1;
    }
    for(int i = 0;i < m;i++){
        scanf("%d %d",&tmp,&tmp_);
        tmp--;
        tmp_--;
        friend[tmp]++;
        friend[tmp_]++;
        marge(tmp,tmp_,uf);
    }
    for(int i = 0;i < b;i++){
        scanf("%d %d",&tmp,&tmp_);
        tmp--;
        tmp_--;
        bl[tmp].elm++;
        bl[tmp_].elm++;
        bl[tmp].list = (int*)realloc(bl[tmp].list,sizeof(int)*bl[tmp].elm);
        bl[tmp_].list = (int*)realloc(bl[tmp_].list,sizeof(int)*bl[tmp_].elm);
        bl[tmp].list[bl[tmp].elm-1] = tmp_;
        bl[tmp_].list[bl[tmp_].elm-1] = tmp;
    }
    for(int i = 0;i < n;i++){
        int bl_num = 0;
        for(int j = 0;j < bl[i].elm;j++)if(jud_same(i,bl[i].list[j],uf))bl_num++;
        printf("%d ",(uf[root(i,uf)].size - friend[i] - bl_num - 1>0)?uf[root(i,uf)].size-friend[i]-bl_num-1:0);
    }
    return 0;
}

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

typedef long long ll;
typedef double d;

#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (abs(a*b)/gcd(a,b))
#define sqr(a) (a*a)

#define tt int t; cin>>t; while(t--)
#define lo(i, a, b) for(int i=a; i<b; i++)
#define rlo(i, a) for(int i=a; i>0; i--)
#define be(a) a.begin(),a.end()
#define sz(x) x.size()
#define nl cout<<"\n";
#define sp cout<<" ";

#define op() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

int main()
{
    op();
    int n,cnt=0;
    cin>>n;
    string s[n];
    int p[n+1]={0};
    lo(i,0,n)
    cin>>s[i];
    sort(s,s+n);
    lo(i,0,n)
    {
        if(s[i]==s[i+1])
                p[i+1]=1;
    }
    lo(i,0,n)
    {
        if(p[i]==0)
            cnt++;
    }
    cout<<cnt;
    nl;
    return 0;
}



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

int N;

int main() {
	scanf("%d", &N);
	int prv = 0;
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		if (x && prv) {
			x--;
			ans++;
		}
		ans += x/2;
		prv = x%2;
	}
	printf("%lld\n", ans);
	
	return 0;
}

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

int main(){
    int N;
    cin>>N;
    vector<int> W(N);
    for(int i=0;i<N;i++){
        cin>>W[i];
    }
    int sum=0;
    for(int i=0;i<N;i++){
        sum+=W[i];
    }
    int S1=0;
    int ans=1000;
    for(int i=0;i<N;i++){
        S1+=W[i];
        ans=min(ans,abs(sum-2*S1));
    }
    cout<<ans<<endl;
}

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

using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr ll mod = static_cast<ll>(1e9 + 7);

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

    std::cin >> a >> b;

    if (std::abs(a - b) % 2 != 0)
        std::cout << "IMPOSSIBLE" << std::endl;
    else
        std::cout << std::min(a, b) + std::abs(a - b) / 2 << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset

using namespace std;

int main() {

	long a[100002], sum, n, flag = 0, m, count = 0;

	cin >> n;


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

	for (int i = 0; i < n; i++) {
		cin >> m;
		if (a[i] >= m) {
			count = count + m;
			continue;
		}
		else {
			if (m >= a[i] + a[i + 1]) {
				count = count + a[i] + a[i + 1];
				a[i + 1] = 0;
			}
			else {
				a[i + 1] = a[i + 1] - (m - a[i]);
				count = count + m;
			}
		}
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string.h>
using namespace std;
int main() {
    string str;
    cin >> str;

    if(str.length() == 2) {
        cout << str;
    } else {
        for(int i=str.length()-1; i>=0; i--)
            cout << str[i];
    }
    
    return 0;
}

Measured memory_bytes: 256
temp = input().split()
a, b, k = int(temp[0]), int(temp[1]), int(temp[2])

takahashi = a-k
if takahashi < 0:
    aoki = b + takahashi
    takahashi = 0
    if aoki <= 0:
        aoki = 0
else:
    aoki = b

print("{} {}".format(takahashi, aoki))


Measured memory_bytes: 3064
using System;

public class Program
{
    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());
        int c = int.Parse(Console.ReadLine());
        int x = int.Parse(Console.ReadLine());
        int ans = 0;
        for (int i = 0; i <= a; i++)
        {
            for (int j = 0; j <= b; j++)
            {
                for (int k = 0; k <= c; k++)
                {
                    if (500 * i + 100 * j + 50 * k == x)
                        ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}   

Measured memory_bytes: 11092
#include <iostream>
#include <bitset>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	int N; cin >> N;
	int a[100];
	int b[101];
	rep(i, 0, 101) {
		b[i] = 0;
	}

	rep(i, 0, N) {
		cin >> a[i];
		b[a[i]]++;
	}
	int A = 0, B = 0;

	int turn = 0;
	for (int i = 100; i >= 0; i--) {
		for (int j = 0; j < b[i]; j++) {
			if (turn % 2 == 0) {
				A += i;
				turn++;
			}
			else {
				B += i;
				turn++;
			}
		}
	}

	cout << A - B << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec){
    os << "[";
    for(int i = 0; i < vec.size(); i++){
        os << vec[i] << ",";
    }
    os << "]";
    return os;
}

template<typename T>
T input(){
    T t;
    cin >> t;
    return t;
}

template<typename T>
vector<T> input(const int N){
    vector<T> v(N);
    repeat(i,N) cin >> v[i];
    return v;
}

long long gcd(long long a, long long b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}

long long lcm(long long a, long long b){
    return (a / gcd(a, b)) * b;
}

long long mul(const long long& a, const long long& b, const long long& mod) {
    return ((a % mod) * (b % mod)) % mod;
}

long long power(const long long& x, const long long& y, const long long& mod) {
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % mod;
    } else {
        long long value = power(x, y / 2, mod);
        if (y % 2 == 0) {
            return mul(value, value, mod);
        } else {
            return mul(value, value, mod) * x % mod;
        }
    }
}

long long div(const long long& a, const long long& b, const long long& mod) {
    return mul(a, power(b, mod - 2, mod), mod);
}

map<long long, long long> factorials;
long long factorial(const long long& n, const long long& mod) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (factorials[n] != 0) {
        return factorials[n];
    }
    factorials[n] = n * factorial(n - 1, mod) % mod;
    return factorials[n] % mod;
}

long long combination(const long long& n, const long long& x, const long long& mod) {
    long long numerator = 1;
    long long denominator = 1;
    repeat(i, x) {
        numerator *= (n - i) % mod;
        numerator %= mod;
        denominator *= (i + 1) % mod;
        denominator %= mod;
    }
    return div(numerator, denominator, mod);
}

int main(){
    int leftA, leftB, rightC, rightD;
    cin >> leftA >> leftB >> rightC >> rightD;

    int leftTotal = leftA + leftB;
    int rightTotal = rightC + rightD;

    string result = "";
    if (leftTotal < rightTotal) {
        result = "Right";
    } else if (rightTotal < leftTotal) {
        result = "Left";
    } else {
        result = "Balanced";
    }
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 384
import sys
input = lambda : sys.stdin.readline().strip()

from collections import deque
from operator import le, ge

class Convex_Hull_Trick():
    def __init__(self, op=ge):
        self.que = deque()
        self.op = op

    @staticmethod
    def f(f1, x):
        return f1[0]*x + f1[1]

    def check(self, f1, f2, f3):
        a = (f2[0] - f1[0]) * (f3[1] - f2[1])
        b = (f2[1] - f1[1]) * (f3[0] - f2[0])
        return self.op(a, b)

    def add_line(self, a, b):
        que = self.que
        fi = (a, b)
        while len(que) >= 2 and self.check(que[-2], que[-1], fi):
            que.pop()
        que.append(fi)

    def get(self, x):
        que = self.que
        f = self.f
        while len(que) >= 2 and self.op(f(que[0], x), f(que[1], x)):
            que.popleft()
        return f(que[0], x)

n,c = map(int, input().split())
h = list(map(int, input().split()))

CHT = Convex_Hull_Trick()
CHT.add_line(-2*h[0], h[0]**2)

DP = [0]*n

for i in range(1, n):
    min_cost = CHT.get(h[i])
    DP[i] = min_cost + h[i]*h[i] + c
    CHT.add_line(-2*h[i], h[i]**2+DP[i])

print(DP[-1])

Measured memory_bytes: 78248
#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main(void){
    int num[4];
    string s;
    cin >> s;
    for(int i = 0; i < 4; i++) num[i]=s[i]-'0';

    for(int i = 0; i < (1<<3); i++){
        int sum = num[0];
        for(int j = 1; j <= 3; j++){
            if((i&(1<<(j-1))) != 0) sum += num[j];
            else sum -= num[j];
        }

        if(sum == 7){
            cout << num[0];
            for(int j = 1; j <= 3; j++){
                if((i&(1<<(j-1))) != 0) cout << '+' << num[j];
                else cout << '-' << num[j];
            }
            cout << "=7\n";
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	string s, t;
	cin >> s;
	cin >> t;
	int n = s.size();
	int m = t.size();
	unordered_map<char, VI> cmap;
	REP(i, n) { cmap[s[i]].push_back(i); }
	ll result = 0;
	int prev = -1;
	REP(i, m) {
		char c = t[i];
		if(cmap.find(c) == cmap.end()) {
			cout << -1 << endl;
			return 0;
		}
		VI indexes = cmap[c];
		auto found = upper_bound(ALL(indexes), prev);
		int index;
		if(found == indexes.end()) {
			index = indexes[0];
			result += index + n - prev;
		} else {
			index = *found;
			result += index - (prev < 0 ? 0 : prev);
		}

		prev = index;
	}
	cout << result + 1 << endl;
	return 0;
}


Measured memory_bytes: 4388
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, x, n) for (int i = x; i < (n); i++)
#define ALL(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int c1, c2;
    c1 = ceil((double)C / (double)B);
    c2 = ceil((double)A / (double)D);

    if (c1 <= c2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3640
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int n,i,j,pm[10000],pe[10000],pj[10000],flg;
	
	while(1){
		
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++) scanf("%d %d %d",&pm[i],&pe[i],&pj[i]);
		for(i=0;i<n;i++){
			flg=0;
			if(pm[i]==100 || pe[i]==100 || pj[i]==100) {
				printf("A\n");
				flg=1;
			}
			else if((double)(pm[i]+pe[i])/2>=90){
				printf("A\n");
				flg=1;
			}
			else if((double)(pm[i]+pe[i]+pj[i])/3>=80){
				printf("A\n");
				flg=1;
			}
			else if((double)(pm[i]+pe[i]+pj[i])/3>=70){
				printf("B\n");
				flg=1;
			}
			else if((double)(pm[i]+pe[i]+pj[i])/3>=50){
				if(pm[i]>=80 || pe[i]>=80){
					printf("B\n");
					flg=1;
				}
			}
			if(flg==0){
				printf("C\n");
			}
		}
	}
	return 0;
}
	

Measured memory_bytes: 1028
modulus = 10**9+7
p = modulus-2
n = int(input())
factorial = [1]
for i in range(1, n+2):
    factorial.append((factorial[-1] * i) % modulus)

factorial_inv = [pow(f, p, modulus) for f in factorial]

def nCr(n, r):
    return (factorial[n] * factorial_inv[r]) % modulus * factorial_inv[n-r] % modulus

xs = list(map(int, input().split()))
d = {}
s = set()
for i, x in enumerate(xs):
    if x in s:
        dup1 = d[x]
        dup2 = i
    else:
        s.add(x)
        d[x] = i

outer = n+1 - (dup2 - dup1 + 1)
print(n)
for k in range(2, outer+2):
    print((nCr(n+1, k) - nCr(outer, k-1))%modulus)
for k in range(outer+2, n+2):
    print(nCr(n+1, k))

Measured memory_bytes: 73052
#include<stdio.h>

int main(void){
	
	char s[3];
	int i,n=0;
	scanf("%s",s);
	
	for(i=0;i<=3;i++){
		if(s[i]=='+')n++;
		if(s[i]=='-')n--;
	}
	printf("%d\n",n);
	return 0;
}

Measured memory_bytes: 128
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

ans = 10 ** 5
for bit in range(2 ** (H - 1)):    
    group = [0] * H
    gnum = 0

    # Group each row
    for i in range(H - 1):
        if not bit >> i & 1:
            group[i + 1] = group[i]
        else:
            group[i + 1] = group[i] + 1
            gnum += 1

    gok = True
    add = 0  # Vertical split num
    nums = [0] * (gnum + 1)  # Number of '1' in previous blocks
    # For each column
    for j in range(W):
        ones = [0] * (gnum + 1)
        ok = True
        # For each row
        for i in range(H):
            ones[group[i]] += int(S[i][j])
            nums[group[i]] += int(S[i][j])
            if ones[group[i]] > K: gok = False;
            if nums[group[i]] > K: ok = False;

        if not ok:
            add += 1
            nums = ones[:]
            
    if gok:
        ans = min(ans, gnum + add)
                
    
print(ans)


Measured memory_bytes: 44764
#include<stdio.h>

int main(){
    int N, M;
    int L[110000], R[110000];
    int max = 1, min = 110000;
    int i;

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

    for(i=0; i<M; i++){
        scanf("%d %d", &L[i], &R[i]);
        if(max < L[i]){
            max = L[i];
        }
        if(min > R[i]){
            min = R[i];
        }
    }
    if(min-max < 0){
        printf("%d", 0);
    }else{
        printf("%d", min-max+1);
    }

    return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    int m=max(max(a,b),c);
    if(3*m%2!=(a+b+c)%2)m++;
    int ans=((3*m)-(a+b+c))/2;
    cout<<ans<<endl;
    return 0;
}


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

res = S.count('R') * S.count('G') * S.count('B')

for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if k < N and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            res -= 1

print(res)


Measured memory_bytes: 9188
/* it was worth becoming a chemist */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned int uni;
typedef unsigned long long unll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<int> vi;
typedef vector<long long> vll;

#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define NAME "cardgame"
#define F first
#define S second

const ll INF = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
const db EPS = (db) 1e-9;
const db pi = acos(-1.0);
const int MAXN = 1e5 + 5;

int n;
ll t[MAXN], c, k;

int main() {	
    // #ifndef ONLINE_JUDGE
	//~ freopen(NAME".in", "r", stdin);
    //~ freopen(NAME".out", "w", stdout);
    // #endif

	cin >> n >> c >> k;	
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	sort (t + 1, t + 1 + n);
	ll T = t[1] + k, ct = 1, res = 0;
	for (int i = 2; i <= n; i++) {
		if (T >= t[i] && T <= t[i] + k && ct < c) ct++;
		else {
			if (ct != 0) {
				res++;
				ct = 1;
			}
			T = t[i] + k;
		}
	}
	if (ct != 0) res++;
	cout << res;
	return 0;
}


Measured memory_bytes: 1024
import heapq

N,K = map(int,input().split())

ans = 0

dt = []
maxt = 0

for i in range(N):

    t,d = map(int,input().split())

    dt.append([d,t])

    maxt = max(maxt,t)

dt.sort()
dt.reverse()

nsum = 0
nx = 0
uflag = [0] * (maxt+1)
up2mins = []
amari = []

for i in range(N):

    nt = dt[i][1]
    nd = dt[i][0]

    if i < K:

        nsum += nd

        if uflag[nt] == 0:
            uflag[nt] += 1
            nx += 1

        else:
            heapq.heappush(up2mins,nd)

    else:

        if uflag[nt] == 0:
            heapq.heappush(amari,-1 * nd)
            uflag[nt] += 1

ans = nsum + nx ** 2

#print (up2mins,amari,nsum,nx)

for i in range(N-K+1):

    if len(amari) == 0 or len(up2mins) == 0:
        break

    mnd = heapq.heappop(up2mins)

    pnd = -1 * heapq.heappop(amari)

    nx += 1

    nsum = nsum - mnd + pnd

    ans = max(ans , nsum + nx ** 2)


print (ans)
            



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

int main() {
  int h1,h2,k1,k2,a,b,c,d;
  cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;
  int d1=h1*a+h2*b+h1/10*c+h2/20*d;
  int d2=k1*a+k2*b+k1/10*c+k2/20*d;
  if(d1>d2) cout << "hiroshi" << endl;
  else if(d1<d2) cout << "kenjiro" << endl;
  else cout << "even" << endl;
  return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f,maxn=30010;
vector<int>v[11];
//map<int,string>mp[maxn];
//queue<int>q[maxn];
string s;
int a[maxn],n,m;
int main()
{
	int i,j,k,ans=0,w;
	cin>>n;
	cin>>s;
	for(i=0;i<n;i++)
	{
		v[s[i]-'0'].push_back(i);
	}
	//for(i=0;i<10;i++)
	//	cout<<v[i].size()<<" ";
	//cout<<endl;
	for(i=0;i<10;i++)
		for(j=0;j<10;j++)
			for(k=0;k<10;k++)
			{
				if(v[i].size()==0 || v[j].size()==0 || v[k].size()==0)
					continue;//cout<<"dasd";
				for(w=0;w<v[j].size();w++)
				{
					//out<<v[i][0]<<" "<<v[j][w]<<" "<<v[k][v[k].size()-1]<<" "<<w<<endl;
					if(v[i][0]<v[j][w] && v[j][w]<v[k][v[k].size()-1])
					{
						ans++;
						break;
					}
					
				}
			//	cout<<i<<j<<k;
			}
	cout<<ans;
	
	
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n;
  cin >> n;
  vector<ll> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
    v[i] -= i;
  }
  sort(v.begin(), v.end());
  ll b = v[v.size() / 2];
  ll ans = 0;
  for(ll i: v)ans += abs(i - b);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
c = [[int(x) for x in input().split()] for _ in range(3)]

a = c[0][1] - c[0][0]
b = c[0][2] - c[0][0]

if c[1][2] - c[1][0] != b or c[1][1] - c[1][0] != a:
    print("No")
elif c[2][2] - c[2][0] != b or c[2][1] - c[2][0] != a:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3064
a,b = map(int,input().split())
t = b-a+1
if a < 0 and b < 0:
    if t % 2 == 0:
        print('Positive')
    else:
        print('Negative')
elif a<0 and b>0 or a>0 and b<0:
    print('Zero')
else:
    print('Positive')

Measured memory_bytes: 9184
h,w=map(int,input().split())
a_list=[]
for i in range(h):
    sub_list=list(map(int,input().split()))
    a_list.append(sub_list)
i=0
j=0
count=0
answer=[]
while not count==h*w-1:
    count=count+1
    if i%2==0:
        if j==w-1:
            i_n=i+1
            j_n=j
        else:
            i_n=i
            j_n=j+1
    else:
        if j==0:
            i_n=i+1
            j_n=j
        else:
            i_n=i
            j_n=j-1
    if a_list[i][j]%2==0:
        pass
    else:
        a_list[i_n][j_n]=a_list[i_n][j_n]+1
        answer.append('%s %s %s %s' %(i+1,j+1,i_n+1,j_n+1))
    i=i_n
    j=j_n
print(len(answer))
for i in answer:
    print(i)
    



Measured memory_bytes: 65884
#include <iostream>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
 
  int less = 0;
  if(c > (a-b)) {
    less = c - (a - b); 
  }
  
  cout << less << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    for(int i=0;i<s.length()-1;i++){
        if(s.at(i) == s.at(i+1)){
            cout << "no" << endl;
            return 0;
            break;
        }
    }
    cout << "yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod = 1e9+7;



int main() {
    ll m = 1e7+2;
    vector<ll> p(m, 0);
    for (ll i=2;i <= m; ++i) {
        for (int j = i; j <= m; j+=i) {
           p[j]++;
        }
    }

    rep (i, 1, m) {
        p[i]++;
        p[i] *= 1ll * i;
        p[i] += p[i-1];
    }
    int a;
    cin >> a;
    cout << p[a] << endl;
}




Measured memory_bytes: 81216
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll a,b,c,k;
  cin>>a>>b>>c>>k;
  if(a>=k)
    cout<<k<<"\n";
  else
    if((a+b)>=k)
      cout<<a<<"\n";
  else
    cout<<a-(k-(a+b))<<"\n";
}

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

string s;
int res = 0;

int main(){
  cin >> s;
  rep(i, s.size()){
    if(s.at(i) == '1'){
      res++;
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256