akhauriyash/Code-Regression huggingface dataset:
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int BIG = 1e9;
const int maxN = 200 * 1000 + 9;
const string FILENAME = "sample";

int n;
pair<ll, ll> jobs[maxN];

void read(){
	cin >> n;
	for(int i = 0; i < n; i++){
		ll a, b;  cin >> a >> b;
		jobs[i] = make_pair(b, a);
	}
}

void solv(){
	sort(jobs, jobs + n);
	ll psum = 0;
	for(int i = 0; i < n; i++){
		psum += jobs[i].second;
		if(psum > jobs[i].first){
			cout << "No\n";
			return;
		}
	}

	cout << "Yes\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
#ifdef h4h4
	freopen((FILENAME + ".inp").c_str(), "r", stdin);
	freopen((FILENAME + ".out").c_str(), "w", stdout);
#endif

	read();
	solv();

	return 0;
}

Measured memory_bytes: 3328
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>
#include <map>   
#include <stdio.h>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ull unsigned long long
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807
#define sortR(a,b) sort(a, b, greater<int>())

using namespace std;

//最大公約数
	long long GCD(long long a, long long b) {
		if (a < b)
			swap(a, b);
		if (b == 0) return a;
		else return GCD(b, a % b);
	}
	//素数判定
	bool sosuu_check(int num) {
		int i;
		for (i = 2; i <= sqrt(num); ++i) {
			if (num%i == 0)
				return false;
		}
		return (num < 2) ? false : true;
	}
	
	int check(int N, int a, int b) {
		int A,B,i;
		if (a > b) {
			A = a;
			B = b;
		}
		else {
			A = b;
			B = a;
		}
		for (i = N / b; i > 0; i--) {
			if ((N - b * i) % a == 0) {
				return i;
			}
		}
		return 0;
	}
	//コンビネーション(n,r)
	ull combination(int n, int r) {
		if (r * 2 > n) r = n - r;
		ull dividend = 1;
		ull divisor = 1;
		for (int i = 1; i <= r; ++i) {
			dividend *= (n - i + 1);
			divisor *= i;
		}
		return dividend / divisor;
	}

int main() {
	ll N, M, C, i, j, ans = 0, A, sum;
	cin >> N >> M >> C;
	vector<ll>  B(20);
	REP(i, M) {
		cin >> j;
		B[i] = j;
	}
	REP(i, N) {
		sum = 0;
		REP(j, M) {
			cin >> A;
			sum += A * B[j];
		}
		if ((sum + C) > 0)
			ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 自分の得意な言語で
		// Let's チャレンジ！！

		Scanner sc = new Scanner(System.in);
		int nm1 = sc.nextInt();
		int nm2 = sc.nextInt();
		
		int kane = nm1 * 500;
		
		String str = "Yes";
		
		if (kane < nm2) {
			str = "No";
		}
		
		System.out.println(str);

	}
}

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

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

int
main()
{
  string S;
  cin >> S;
  int i = 0;
  for (char c : S)
  {
    i += (c == '+' ? 1 : -1);
  }
  cout << i << endl;
  return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)  
#define outdeb(fir, sec, thr) cout << fir << ":" << sec << ":" << thr << endl

int main()
{
  char x;
  cin >> x ;

  if(x >= 'a' && x <= 'z')  cout << fixed << 'a' << endl;
  else cout << fixed << 'A' << endl;

  return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;

int main(){
    int N, T;
    cin >> N >> T;
    vector<int> t(N);
    for(int i = 0; i < t.size(); i++){
        cin >> t[i];
    }
    ll sum = 0;
    for(int i = 0; i < t.size() - 1; i++){
        sum += t[i + 1] - t[i] > T ? T : t[i + 1] - t[i];
    }
    sum += T;
    cout << sum << endl;
    return 0;
}


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

const int N = 1e5 + 5;

char s[N];

int ans = 0;

int main() {
	scanf("%s", s + 1);
	int l = strlen(s + 1);
	for(int i = 1; i < l; ++ i)
	ans += (s[i] != s[i + 1]);
	cout << ans << endl;
}

Measured memory_bytes: 3804
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  string s;
  cin >> s;

  int len = s.length();
  cout << s[0] << len-2 << s[len-1] << endl;
  return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>

using namespace std;

int main() {

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

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

	int L[n];
	L[0] = A[0];
	int length = 1;
	for (int i = 1; i < n; ++i) {
		if (A[i] > L[length - 1]) {
			L[length++] = A[i];
		} else {
			int left = 0;
			int right = length;
			while (left < right) {
				int mid = (left + right) / 2;
				if (L[mid] >= A[i]) {
					right = mid;
				} else {
					left = mid + 1;
				}
			}
			L[right] = A[i];
		}
	}
	cout << length << endl;

	return 0;
}

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

int main() {
  string S,T;
  cin >> S >> T;
  int n = S.size();
  int count=0;
  for(int i=0; i<n; i++){
  if(S.at(i) != T.at(i)){
  T.at(i) = S.at(i);
    count++;
  }
  }
  cout << count << endl;
}

Measured memory_bytes: 3804
//47
#include<iostream>
#include<sstream>
#include<string>
#include<map>
#include<algorithm>
#include<set>

using namespace std;

int main(){
  for(string si;getline(cin,si),si!="";){
    string s;
    do{
      s+=si;
      getline(cin,si);
    }while(si!="");
    string k;
    getline(cin,k);
    cin.ignore();
    map<char,int> m;
    int f=0,l=1<<30;
    int n=0;
    set<long long> st;
    for(int i=0;i<s.size();i++){
      for(int j=0;j<k.size();j++){
	if(k[j]==s[i]){
	  m[s[i]]=i;
	}
      }
      if(m.size()!=k.size())continue;
      int cl=0,cf=1<<30;
      for(int j=0;j<k.size();j++){
	cl=max(cl,m[k[j]]);
	cf=min(cf,m[k[j]]);
      }
      if(!st.insert((long long)cl<<32|cf).second)continue;
      if(cl-cf<=l-f){
	if(cl-cf<l-f){
	  f=cf;
	  l=cl;
	  n=0;
	}
	n++;
      }
    }
    cout<<n<<endl<<endl;
    if(n){
      string t=s.substr(f,l-f+1);
      for(int i=0;i<t.size();i+=72){
	cout<<t.substr(i,72)<<endl;
      }
      cout<<endl;
    }
  }
  return 0;
}
    

Measured memory_bytes: 3424
def main():
    import sys
    input = sys.stdin.readline
    import numpy as np
    from scipy.sparse import csr_matrix

    N, M = map(int, input().split())
    H = np.array(list(map(int, input().split())))

    AB = [[] for i in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        AB[a].append(b)
        AB[b].append(a)
    count = 0
    for i, ab in enumerate(AB):
        ind = list(set(ab))
        if ind == []:
            count += 1
            continue
        if np.max(H[ind]) < H[i]:
            count += 1
    print(count)

    # AB = np.array([list(map(int, input().split())) for i in range(M)])-1

    # ab0 = list(AB[:, 0])
    # ab1 = list(AB[:, 1])
    # csr = csr_matrix(
    #     ([1]*(2*M), (ab0+ab1, ab1+ab0)), shape=(N, N)).toarray()

    # count = 0
    # for i, indices in enumerate(csr):
    #     if (indices == 0).all():
    #         count += 1
    #         continue
    #     if np.max(H[indices != 0]) < H[i]:
    #         count += 1

    # print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 57492
n, y = gets.split.map(&:to_i)
if n * 10000 < y || n * 1000 > y
  puts '-1 -1 -1'
  exit
end
(y / 10000).downto(0) do |a|
  ((y - a * 10000) / 5000).downto(0) do |b|
    if (y - a * 10000 - b * 5000) % 1000 == 0 && a + b + (y - a * 10000 - b * 5000) / 1000 == n
      puts "#{a} #{b} #{(y - a * 10000 - b * 5000) / 1000}"
      exit
    end
  end
end
puts '-1 -1 -1'

Measured memory_bytes: 14212
import java.util.Scanner;

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

		int a = sc.nextInt();//一回
		int b = sc.nextInt();//所持
		int c = sc.nextInt();//満足
		if(b>=a*c){
			System.out.println(c);
		}else{
			c=b/a;
			System.out.println(c);
		}

	}}

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

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

  ll H; cin >> H;
  ll W; cin >> W;
  ll w0 = (W + 1) / 2;
  ll w1 = W / 2;

  ll ans = 0;
  ans += (H / 2) * (w0 + w1);
  if (H % 2) ans += w0;
  if (H == 1 || W == 1) ans = 1;
  cout << ans << '\n';
  return 0;
}

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

int main() {
  string s;cin>>s;
  int n=s.size();
  ll ans=0;
  for(int bit=0;bit<(1<<n-1);bit++){
    ll cnt=s[0]-'0';
    rep(i,n-1){
      if(bit&(1<<i)){
        ans+=cnt;
        cnt=0;
      }
      cnt=cnt*10+s[i+1]-'0';
    }
    ans+=cnt;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include <iomanip>
#include <iostream>
#include <vector>

using Real = long double;

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

int main() {
    int n, m;
    std::cin >> n >> m;

    Graph<> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        graph[u].emplace_back(u, v);
    }

    std::vector<Real> effect(n);
    // 頂点vに到達する確率

    for (int r = 0; r < n; ++r) {
        std::vector<Real> dp(n, 0);
        for (int v = n - 2; v >= 0; --v) {
            for (auto e : graph[v]) {
                dp[v] += dp[e.dst];
            }
            dp[v] /= graph[v].size();
            if (v == r) dp[v] += 1;
        }
        effect[r] = dp[0];
    }

    std::vector<Real> dp(n, 0);
    // 何も削除しないときのE
    for (int v = n - 2; v >= 0; --v) {
        int sz = graph[v].size();
        for (auto e : graph[v]) {
            dp[v] += dp[e.dst];
        }
        dp[v] /= sz;
        dp[v] += 1;
    }

    Real maxeffect = 0;
    for (int v = 0; v < n - 1; ++v) {
        int sz = graph[v].size();
        if (sz == 1) continue;

        for (int k = 0; k < graph[v].size(); ++k) {
            // k番目を削除した場合
            Real sum = 0;
            for (int i = 0; i < sz; ++i) {
                int u = graph[v][i].dst;
                sum += (i == k ? 0 : dp[u]);
            }
            Real diff = dp[v] - (sum / (sz - 1) + 1);
            maxeffect = std::max(maxeffect, diff * effect[v]);
        }
    }

    std::cout << std::fixed << std::setprecision(10)
              << dp[0] - maxeffect << std::endl;
    return 0;
}


Measured memory_bytes: 3584
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

while True:
    n,m = inpl()
    if n == 0:
        break
    else:
        aa = [inp() for _ in range(n)]
        bb = [inp() for _ in range(m)]
        Sa = sum(aa)
        Sb = sum(bb)
        for a in aa:
            for b in bb:
                if Sa-a+b == Sb+a-b:
                    print(a,b)
                    break
            else:
                continue
            break
        else:
            print(-1)



Measured memory_bytes: 7456
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long x = sc.nextLong();
		
		int r = 0;
		if(x%11>0){
			r = x%11<=6 ? 1 : 2;
		}
			
		System.out.println(x/11*2+r);
	}
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)
#define EPS         (1e-10)
#define EQ(a, b)    (abs((a)-(b)) < EPS)

using P   = pair<int, int>;
using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    int x;cin >> x;
    int k;cin >> k;
    vector<int> r, a, b, c;
    r.push_back(0);
    a.push_back(0);
    b.push_back(x);
    c.push_back(0);
    for(int i=0;i<k;i++){
        int rr;cin >> rr;
        int d = rr-r[i];
        int aa = a[i];
        int bb = b[i];
        int cc = c[i];
        if(i%2 == 0){
            // down
            cc = max(0, c[i]-d);
            aa = min(b[i], a[i] + max(0, 0-(c[i]-d)));
        }else{
            // up
            cc = min(x, c[i]+d);
            bb = max(a[i], b[i] - max(0, c[i]+(b[i]-a[i])+d-x));
        }
        r.push_back(rr);
        a.push_back(aa);
        b.push_back(bb);
        c.push_back(cc);
        //cout << r[i+1] << " " << a[i+1] << " " << b[i+1] << " " << c[i+1] << endl;
    }
    int q;cin >> q;
    for(int i=0;i<q;i++){
        int t, aa;cin >> t >> aa;
        int j = int(upper_bound(r.begin(), r.end(), t) - r.begin()) - 1;
        int d = t-r[j];
        int f;
        if(aa <= a[j]){
            f = c[j];
        }else if(aa <= b[j]){
            f = c[j] + (aa - a[j]);
        }else{
            f = c[j] + (b[j]-a[j]);
        }
        //cout << "j " << j << " d " << d << " f " << f << endl;
        int ans;
        if(j%2 == 0){
            // down
            ans = max(0, f-d);
        }else{
            // up
            ans = min(x, f+d);
        }
        cout << ans << endl;
    }
    return 0;
}


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

bool c[5000+2][5000+2];

bool t(int x,int y){
	if(x<0)return false;
	if(x>5000)return false;
	if(y<0)return false;
	if(y>5000)return false;
	return c[x][y];
}

int main(){
	while(1){
		int n,ans=0;
		pair<int,int> p[3002];
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<5002;i++)for(int j=0;j<5002;j++)c[i][j]=false;
		for(int i=0;i<n;i++){
			scanf("%d%d",&p[i].first,&p[i].second);
			c[p[i].first][p[i].second]=true;
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(t(p[i].first+p[i].second-p[j].second,p[i].second+p[j].first-p[i].first))if(t(p[j].first+p[i].second-p[j].second,p[j].second+p[j].first-p[i].first))ans=max(ans,(p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second));
				//if(t(p[i].first-p[i].second+p[j].second,p[i].second-p[j].first+p[i].first)&&t(p[j].first-p[i].second+p[j].second,p[j].second-p[j].first+p[i].first))ans=max(ans,(p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second));
			}
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 25624
#include<stdio.h>
#include<stdlib.h>
#define ll long long
ll po(ll a){
    return a * a * a * a * a;
}
ll roo(ll a){
    ll i = 0;
    for(; ; i++){
        ll p = po(i);
        if(a == p)
            return i;
        if(a < p)
            return -1;
    }
}
int main(){
    ll x, i;
    ll a, b;
    scanf("%lld",&x);
    for(i = 0; i < 10000 ; i++){
        ll p = po(i);
        ll q = p - x;
        ll r = roo(q);
        if(q > 0){
            r = roo(q);
            if(r != -1){
                a = i;
                b = r;
                break;
            }
        }
        else if(q == 0){
            a = i;
            b = 0;
            break;
        }
        else{
            ll w = -1 * q;
            ll rr = roo(w);
            if(rr != -1){
                a = i;
                b = -1 * rr;
                break;
            }
        }
    }
    printf("%lld %lld\n",a, b);
    return 0;
}

Measured memory_bytes: 1736
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String op;
      String[] words;
      Tree tree = new Tree();

      for(int i=0,k=0; i<n; i++,k=0){
        words = br.readLine().split(" ");
        op  = words[k++];
        if ( op.equals("insert") ) { 
          tree.insert(Integer.parseInt(words[k++]));
        }
        else {
          tree.dispRoundPath();
        }
      }

    }
    catch(IOException e) {
      System.out.println("IOException!");
    }
  }
}

class Tree {

  static final BTreeNode NIL = new BTreeNode(-1);
  BTreeNode root;
  StringBuilder buf;

  public Tree() {
    root = NIL;
    buf = new StringBuilder();
  }

  public void insert(int val) {
    BTreeNode y = NIL;
    BTreeNode x = root;
    BTreeNode z = new BTreeNode(val);

    while( !x.equals(NIL) ) {
      y = x;
      if( z.key < x.key )
        x = x.left;
      else
        x = x.right;
    }
    z.parent = y;

    if( y.equals(NIL) ){
      root = z;
    }
    else if( z.key < y.key )
      y.left = z;
    else
      y.right = z;
  } 
  void preParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      buf.append(" ").append(u.key);
      preParse(u.left);
      preParse(u.right);
    }
  }
  void inParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      inParse(u.left);
      buf.append(" ").append(u.key);
      inParse(u.right);
    }
  }

  void dispRoundPath() {

    inParse(root);
    buf.append("\n");
    preParse(root);
    buf.append("\n");

    System.out.print(buf);
    buf.setLength(0);
  }
}

class BTreeNode {
  int key;
  BTreeNode parent,left,right;

  public BTreeNode(int key) {
    this.key = key;
    this.parent =
    this.left =
    this.right = Tree.NIL;
  }

  @Override
  public boolean equals(Object o) {
    if(o == this) return true;
    if(o == null) return false;
    if(!(o instanceof BTreeNode)) return false;

    BTreeNode node = (BTreeNode)o;
    if(!(this.key == node.key)) return false;

    return true;
  }
}


Measured memory_bytes: 125840
package main

import "fmt"

func main() {
	var n, x int
	fmt.Scanln(&n)
	min, max := 2000, 0
	for ; n > 0; n-- {
		fmt.Scan(&x)
		if x < min {
			min = x
		}
		if x > max {
			max = x
		}
	}
	fmt.Println((max - min + 1) / 2)
}


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

class RAQ {
public:
	struct Node {
		long long min; long long buf;
		Node(long long s, long long b) : min(s), buf(b) {}
	};
private:
	vector<Node> node;
	long long defval;
	long long nega;
	int N;
	int n;
public:
	void init(int n, long long defval = 0) {
		N = 1;
		while (N < n)N <<= 1;
		this->n = n;
		this->defval = defval;
		node.assign(N * 2 - 1, Node(defval, 0));
		nega = INT64_MAX;
	}
	long long query(int a, int b, int l = 0, int r = -1, int i = 0) {
		if (r == -1) r = N;
		if (b <= l || r <= a) return nega;
		if (a <= l && r <= b) return node[i].min;
		//int rag = min(r, b) - max(l, a);
		return min(query(a, b, l, (l + r) / 2, i * 2 + 1), query(a, b, (l + r) / 2, r, i * 2 + 2)) + node[i].buf;
	}
	void update(int a, int b, long long v, int l = 0, int r = -1, int i = 0) {
		if (r == -1) r = N;
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) { node[i].buf += v; node[i].min += v; return; }

		update(a, b, v, l, (l + r) / 2, i * 2 + 1);
		update(a, b, v, (l + r) / 2, r, i * 2 + 2);

		node[i].min = min(node[i * 2 + 1].min, node[i * 2 + 2].min) + node[i].buf;
	}

};

int main() {
	int n, q; cin >> n >> q;
	RAQ tr; tr.init(n);

	vector<long long> ans;

	for (int i = 0; i < q; i++) {

		int c; cin >> c;
		if (c == 0) {
			int s, t, x; cin >> s >> t >> x;
			tr.update(s, t + 1, x);
		}
		else {
			int s, t; cin >> s >> t;
			ans.push_back(tr.query(s, t + 1));
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}

	return 0;
}




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

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

dp = [[[0.0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]
            if j>0: tmp += j*dp[i+1][j-1][k]
            if k>0: tmp += k*dp[i][j+1][k-1]
            dp[i][j][k] = tmp/(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])




Measured memory_bytes: 260104
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

ll n, k;
vll w, d;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    w.resize(n), d.resize(n);
    for (ll i = 0; i < n; i++) cin >> w[i] >> d[i];
    ll low = 1, high = 2 * HIGHINF + 1;
    while (low < high) {
        ll mid = (low + high) >> 1;
        ll tmpk = 0;
        for (ll i = 0; i < n; i++) {
            if (mid < w[i]) continue;
            else {
                tmpk += (mid - w[i]) / d[i] + 1;
            }
        }
        if (tmpk < k) low = mid + 1;
        else high = mid;
    }
    cout << low << '\n';
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

int countIndentLevel(const string& s) {
    rep(j, s.size()) {
        if (s[j] != '.') {
            return j;
        }
    }
}

int updateCnt(V& cnt, const string& s) {
    for (const auto c : s) {
        switch(c) {
            case '(': cnt[0]++; break;
            case ')': cnt[0]--; break;
            case '{': cnt[1]++; break;
            case '}': cnt[1]--; break;
            case '[': cnt[2]++; break;
            case ']': cnt[2]--; break;
        }
    }
}

bool checkValid(const map<V, int>& rule, int R, int C, int S) {
    for (const auto& p : rule) {
        V cnt;
        int indent;
        tie(cnt, indent) = p;
        if (R * cnt[0] + C * cnt[1] + S * cnt[2] != indent) {
            return false;
        }
    }
    return true;
}

void updateAns(V& ans, const VV& brackets, int R, int C, int S) {
    int Q = brackets.size();
    V temp(Q);
    rep(i, Q) {
        temp[i] = R * brackets[i][0] + C * brackets[i][1] + S * brackets[i][2];
    }

    if (ans.empty()) ans = temp;
    rep(i, Q) {
        if (ans[i] != temp[i]) ans[i] = -1;
    }
}

void solve(const int P, const int Q) {
    map<V, int> rule;
    V cnt(3);
    rep(i, P) {
        string s;
        cin >> s;
        rule[cnt] = countIndentLevel(s);
        updateCnt(cnt, s);
    }

    cnt.assign(3, 0);
    VV brackets(Q, V(3));
    rep(i, Q) {
        brackets[i] = cnt;
        string s;
        cin >> s;
        updateCnt(cnt, s);
    }

    V ans;
    rep2(R, 1, 21) {
        rep2(C, 1, 21) {
            rep2(S, 1, 21) {
                if (!checkValid(rule, R, C, S)) continue;
                updateAns(ans, brackets, R, C, S);
            }
        }
    }

    rep(i, ans.size()) {
        cout << (i != 0 ? " " : "") << ans[i];
    }
    cout << endl;
}

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

    int P, Q;
    while (cin >> P >> Q, P) {
        solve(P, Q);
    }
}

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

#define st first
#define nd second
#define pb push_back

typedef long long   ll;
typedef double      db;
typedef long double ldb;

typedef pair <int, int> pii;
typedef pair <ll,  ll>  pll;
typedef pair <ll,  db>  pdb;
typedef pair <ldb, ldb> pldb;

template <typename T>
void   Debug (T begin, T end);
int    si    ();
ll     sl    ();
string ss    (int); 
db     sf    ();
ldb    slf   ();
void   pi    (int, char = '\n');
void   pl    (ll, char = '\n');
void   pf    (db, char = '\n');
void   plf   (ldb, char = '\n');
void   ps    (string, char = '\n');

ll russian(ll, ll, ll);
ll fast_power(ll, ll, ll);
ll slow_power(ll, ll, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);

const int INF  = 1e9;
const ll  LINF = 1e18;

int main()
{
    int n = si();
    if (n & 1)
        pf((db)(n / 2 + 1) / n);
    else
        pf(0.5);

    return 0;
}

template <typename T>
void Debug(T begin, T end)
{
    printf("\nDEBUG:\n");
    while (begin != end)
        printf("%d ", *begin),
        begin++;
    printf("\n\n");
}

template <typename T>
T scanf_t(string s)
{
    T a;
    scanf(s.c_str(), &a);
    return a;
}

template <typename T>
void printf_t(T a, string s, char end_l)
{
    s.push_back(end_l);
    printf(s.c_str(), a);
}

int si() { return scanf_t<int>("%d"); }
ll sl() { return scanf_t<ll>("%lld"); }
db sf() { return scanf_t<db>("%f"); }
ldb slf() { return scanf_t<ldb>("%Lf"); }

void pi(int a, char end_l) { printf_t<int>(a, "%d", end_l); }
void pl(ll a, char end_l) { printf_t<ll>(a, "%lld", end_l); }
void pf(db a, char end_l) { printf_t<db>(a, "%lf", end_l); }
void plf(ldb a, char end_l) { printf_t<ldb>(a, "%Lf", end_l); }

void ps(string a, char end_l)
{
    string s = "%s";
    s.push_back(end_l);
    printf(s.c_str(), a.c_str());
}

string ss(int NN)
{
    char T[NN];
    scanf("%s", T);
    return (string)T;
}

ll fast_power(ll a, ll k, ll m)
{
    ll r = 1LL;
    while (k)
    {
        if (k & 1LL)
            r = (r * a) % m;
        a = (a * a) % m;
        k >>= 1LL;
    }
    return r;
}

ll slow_power(ll a, ll k, ll m)
{
    ll r = 1LL;
    while (k)
    {
        if (k & 1LL)
            r = russian(r, a, m);
        a = russian(a, a, m);
        k >>= 1LL;
    }
    return r;
}

ll russian(ll a, ll k, ll m)
{
    ll r = 0LL;
    while (k)
    {
        if (k & 1LL)
            r = (r + a) % m;
        a = (a + a) % m;
        k >>= 1LL;
    }
    return r;
}

ll gcd(ll a, ll b)
{
    while (b)
        swap(a %= b, b);
    return a;
}

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


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

int main()
{
	int N, K;
	cin >> N >> K;
	int d[K];
	int A[K][N];
	int have_bool[N];
	for (int i = 0; i < N; i++)
	{
		have_bool[i] = false;
	}
	
	for (int i = 0; i < K; ++i)
	{
		cin >> d[i];
		
		for (int j = 0; j < d[i]; ++j)
		{
			cin >> A[i][j];
			have_bool[A[i][j] - 1] = true;
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		if (!have_bool[i]) cnt++;
	}
	
	cout << cnt << endl;
	
	return 0;
}


Measured memory_bytes: 3660
/*input
1
1

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  string str;
  set<string> s;
  for (int i = 0; i < n; i++) {
    cin >> str;
    s.insert(str);
  }
  cout << s.size() << endl;

  return 0;
}

Measured memory_bytes: 19136
from collections import deque
H, W = map(int ,input().split())
A = [input() for _ in range(H)]
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
inf = float("inf")

dp = [[inf]*W for _ in range(H)]
q = deque()
for y, row in enumerate(A):
    for x, c in enumerate(row):
        if c == "#":
            dp[y][x] = 0
            q.append((x, y))

while q:
    x, y = q.popleft()
    d = dp[y][x]
    for dx, dy in dxy:
        nx, ny = x+dx, y+dy
        if (not 0 <= nx < W) or (not 0 <= ny < H):
            continue
        if dp[ny][nx] <= d+1:
            continue
        dp[ny][nx] = d+1
        q.append((nx, ny))

print(max(max(row) for row in dp))



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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<(int)n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;

void solve(){
   int k;
   cin >> k;
   string s;
   cin >> s;
   if(sz(s) <= k) cout << s;
   else cout << s.substr(0,k)  << "...";
}

int32_t main(){
   fast;
   int t = 1;
   // cin >> t;
   while(t--)  solve();   
}

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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;
int a, b, c;
int minPrice()
{
	return min({a + b, b + c, c + a});
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
//	freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
	cin >> a >> b >> c;

	cout << minPrice() << endl;
	
	return 0;
}

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

using namespace std;

#define MAX_SIZE 1005

char source[MAX_SIZE], target[MAX_SIZE];

int main() {
  scanf("%s%s", source, target);
  int minChange = MAX_SIZE;
  for (int si = 0; si <= strlen(source) - strlen(target); ++si) {
    int change = 0;
    for (int ti = 0; ti < strlen(target); ++ti) {
      change += target[ti] != source[si+ti];
    }
    if (change < minChange) {
      minChange = change;
    }
  }

  printf("%d\n", minChange);  

  return 0;
}

Measured memory_bytes: 3640
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int,int>;
using PLL = pair<LL, LL>;
const int INF = 1e9;
const int MXN = 2e6 + 5;
const int MXV = 0;
const int MOD = 1e9 + 7;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for(int i = L; i != (int)R; ++i)
#define FORD(i, L, R) for(int i = L; i != (int)R; --i)
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);
LL comb[MXN], invcomb[MXN];
 
LL extgcd(LL a, LL b, LL &x, LL &y)
{
    LL d = a;
    if (b)
    {
        d = extgcd(b, a % b, y, x), y -= (a / b) * x;
    }
    else
        x = 1, y = 0;
    return d;
} // ax+by=1 ax同餘 1 mod b
 
LL inv(LL a)
{
    LL x, y, b = MOD;
    extgcd(a, b, x, y);
    while(x >= MOD)
    {
        x -= MOD;
    }
    while(x < 0)
    {
        x += MOD;
    }
    return x;
}
 
void pre()
{
    comb[0] = 1;
    invcomb[0] = 1;
    for(int i = 1; i < MXN; ++i)
    {
        comb[i] = (comb[i - 1] * i) % MOD;
        invcomb[i] = inv(comb[i]);
    }
}
 
LL choose(int m, int n)
{
    LL ans = comb[m];
    ans = (ans * invcomb[m - n]) % MOD;
    ans = (ans * invcomb[n]) % MOD;
    return ans;
}

LL G(int m, int n) { return choose((m + 1) + (n + 1), n + 1) - 1; }

int main()
{
    IOS;
    pre();

    int r1, r2, c1, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    --r1;
    --c1;

    LL ans = G(r2, c2) - G(r2, c1) - G(r1, c2) + G(r1, c1);
    while(ans <= 0)
    {
        ans += MOD;
    }
    ans %= MOD;
    cout << ans << '\n';
}


Measured memory_bytes: 31488
#include<iostream>
#define MAXN 200000+10
using namespace std;
int s[MAXN];
int t[MAXN];
int ns,nt;
int tot,l,r,mid;
int main(){
	int i,now;
	cin>>ns;
	for (i = 0;i < ns;++i)
		cin>>s[i];
	cin>>nt;
	for (i = 0;i < nt;++i)
		cin>>t[i];
	
	for (i = 0;i < nt;++i){
		now=t[i];
		l=0;
		r=ns;
		while (l < r){
			mid=l+(r-l)/2;
			if (s[mid] == now) {
				tot++;
				break; 
			}
			if (s[mid] < now) l=mid+1;
			else r=mid;
		}
	}
	cout<<tot<<endl;
	return 0;
}

Measured memory_bytes: 3652
n,k=list(map(int,input().split(" ")))
h=[]
h_d=[]
for i in range(n):
    h.append(int(input()))  
h.sort()
for count in range(n-k+1):
    h_d.append(h[count+k-1]-h[count])
print(min(h_d))

Measured memory_bytes: 11288
#include <iostream>
#include <math.h>
using namespace std;
int a[105];
int main() {
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n - 2; i++)
        for(int j = i + 1; j <= n - 1; j++)
            for(int k = j + 1; k <= n; k++) {
                if(a[i] == a[j] || a[j] == a[k] || a[i] == a[k])
                    continue;
                int tmp = max(a[i], max(a[j], a[k]));
                int sum = a[i] + a[j] + a[k];
                if(tmp < sum - tmp)
                    ans++;
            }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::string s, t;
    std::getline(std::cin, s);
    std::getline(std::cin, t);
    int l = s.length();
    int p = 0;
    for (int i = 0; i < l; i++) {
        char ch = s[l - 1];
        for (int j = l - 1; j > 0; j--)
            s[j] = s[j - 1];
        s[0] = ch;
        if (s.compare(t) == 0) {
            p = 1;
            break;
        }
    }
    if (p == 1)
        std::cout << "Yes";
    else
        std::cout << "No";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e9
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, s;
    cin>>n;
    vector<int> l;
    rep(i, n){
        cin>>s;
        l.eb(s);
    }
    sort(all(l));
    int ans = 0, a, b, c, cnt = 0, k, mi1, mi2, ma;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            /*
            k = n-1-cnt;
            a = l[i];
            b = l[j];
            c = l[k];
            mi1 = a;
            mi2 = b;
            ma = c;
            if(mi1 + mi2 > c){
                ans += 1;
            }
            else{
                cnt 
            }
            */
            for(int k = j+1; k < n; k++){
                a = l[i];
                b = l[j];
                c = l[k];
                if(a < b+c && b < c+a && c < a+b){
                    ans += 1;
                }
                else{
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n,x,y=map(int,input().split())

ans=0
ans=[0]*(n-1)
for i in range(1,n+1):
  for j in range(i+1,n+1):
    now=min(j-i,abs(j-y)+abs(i-x)+1)
    ans[now-1]+=1

for i in ans:
  print(i)


Measured memory_bytes: 9204
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
#define fi first
#define se second
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001

int main(void) {
	int n,m; cin >> n >> m;
	priority_queue<P> q;
	rep(i,n){
		int a; cin >> a;
		q.emplace(a,1);
	}
	rep(i,m){
		int b,c;
		cin >> b >> c;
		q.emplace(c,b);
	}
	ll ans = 0;
	rep(i,n){
		if(q.top().se>1){
			ans += q.top().fi;
			int b = q.top().se;
			int c = q.top().fi;
			q.pop();
			q.emplace(c,b-1);
		}else{
			ans += q.top().fi;
			q.pop();			
		}
	}
	cout << ans << endl;
}




Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < 4; i++)
    {
        cout << s[i];
    }
    cout << " ";
    for(int j = 4; j < 12; j++)
    {
        cout << s[j];
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pi 3.14159265358979323846264
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define vi vector <int>
#define vl vector <long long>
#define vpii vector <pair <int, int> >
#define ll long long
#define fi first
#define se second
#define FOR(i, x, y) for (int i=x; i<=y; i++)
#define FORI(i, x, y) for (int i=y; i>=x; i--)
#define debug printf("OK\n")
ll n;
int main() {
    cin >> n;
    cout << 3 * n * n << endl;
    return 0;
}

Measured memory_bytes: 256
n,A,B,C=map(int,input().split())
L=[int(input()) for i in range(n)]
INF=10**9

def dfs(cnt,a,b,c):
  if cnt==n:
    if min(a,b,c)>0:
      return abs(A-a)+abs(B-b)+abs(C-c)-30
    else:
      return  INF
  else:
    res0=dfs(cnt+1,a,b,c)
    res1=dfs(cnt+1,a+L[cnt],b,c)+10
    res2=dfs(cnt+1,a,b+L[cnt],c)+10
    res3=dfs(cnt+1,a,b,c+L[cnt])+10
    return min(res0,res1,res2,res3)

print(dfs(0,0,0,0))
    

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

int main()
{
    int a,b,c,d,cnt=0;
    cin>>a>>b>>c>>d;
    while(a>0&&c>0)
    {
        cnt++;
        if(cnt%2==1) c-=b;
        else a-=d;
    }
    cout<<(a<=0 ? "No":"Yes");
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
	int a, b;
	char op;
	while (true) {
		cin >> a >> op >> b;
		if (op == '?') break;
		switch (op) {
		case '+':
			printf("%d", a + b);
			break;
		case '-':
			printf("%d", a - b);
			break;
		case '/':
			printf("%d", a / b);
			break;
		case '*':
			printf("%d", a * b);
			break;
		}
		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 3204
using System;

class B{
  static void Main(){
            int x = int.Parse(Console.ReadLine());
    if (x == 1){
      Console.WriteLine("1");
      return;
    }
            for (int i = x; i > 0; i--)
            {
                for(int j = 2; j <= Math.Sqrt(x);j++)
                {
                    if(i % j == 0)
                    {
                        int t = i;
                        while (t % j == 0)
                            t /= j;
 
                        if(t == 1)
                        {
                            Console.WriteLine(i);
                            return;
                        }
                    }
                }
            }
  }
}



Measured memory_bytes: 27544
h,w=map(int,input().split())
s=[input() for _ in range(h)]
a=[[0]*w for _ in range(h)]
for i in range(h):
  cnt=0
  for j in range(w):
    if s[i][j]=='.':cnt+=1
    else:
      for k in range(cnt):
        a[i][j-k-1]=cnt
      cnt=0
  for k in range(cnt):
    a[i][j-k]=cnt
for i in range(w):
  cnt=0
  for j in range(h):
    if s[j][i]=='.':cnt+=1
    else:
      for k in range(cnt):
        a[j-k-1][i]+=cnt
      cnt=0
  for k in range(cnt):
    a[j-k][i]+=cnt
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,a[i][j])
print(ans-1)

Measured memory_bytes: 111524
#include "bits/stdc++.h"
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;*/
//#define int long long
#define fastr ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(int i = a; i < b; i++)
#define rrep(i,a,b) for(int i = (a-1); i >= b; i--) 
#define fi first
#define se second
#define tit(v,i,c) get<c>(v[i])
#define mt make_tuple 
#define pb push_back
#define mp make_pair
double jk=0.4;
#define power(x,y) pow(x,y)+jk
#define endl "\n"
#define mod 1000000007
#define N 1000000000
int in(){
int n;cin>>n;
return n;}
void _do_(){
		int n,m;
		cin>>n>>m;
		int a[n+1];
		rep(i,1,n+1){
			cin>>a[i];
		}
		bool good[n+1];
		memset(good,true,sizeof(good));
		while(m--){
			int x,y;cin>>x>>y;
			if(a[x]<=a[y])good[x]=false;
			if(a[y]<=a[x])good[y]=false;
		}int count=0;
		rep(i,1,n+1){
			//cout<<good[i]<<" ";
			if(good[i])count++;
		}
		cout<<count<<endl;

}signed main(){fastr
//int tc=in();
int tc=1;
while(tc--)_do_();
cerr<<"Time elapsed:";
cerr<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
return 0;}

Measured memory_bytes: 4136
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ITP1_9_D
{
    class Program
    {
        static string a = "";
        static void Main(string[] args)
        {
            string asd = Console.ReadLine();
            a = asd;
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string[] s = Console.ReadLine().Split();
                if (s[0] == "replace") { replace(int.Parse(s[1]), int.Parse(s[2]), s[3]); }
                if (s[0] == "reverse") { reverse(int.Parse(s[1]), int.Parse(s[2])); }
                if (s[0] == "print") { print(int.Parse(s[1]), int.Parse(s[2])); }



            }
            Console.ReadLine();
        }
        static void replace(int x, int b, string str)
        {
            a = a.Substring(0, x) + str + a.Substring(b+1);
        }
        static void reverse(int x, int b)
        {
            string gh = new string(a.Substring(x, b - x+1).Reverse().ToArray());
            a = a.Substring(0, x) + gh + a.Substring(b+1);
        }
        static void print(int x, int b)
        {
            Console.WriteLine(a.Substring(x,b-x+1));
        }
    }
}

Measured memory_bytes: 9444
#include<stdio.h>

int main(){

  int w0,r0,c,r,i;

  while(1){
    scanf("%d%d%d%d",&r0,&w0,&c,&r);
    if(r0==0 && w0==0 && c==0 && r==0)break;

    //    printf("%d %d %d %d\n",r0,w0,c,r);
    //  printf("%f\n",(double)r0/w0);
    if(c <= (double)r0/w0){
      printf("0\n");
    }else{
      //  printf("1\n");
      for(i=1;;i++){
        //printf("%d\n",i);
        if( (double)(r0 + r*i)/w0 - c >= 0 ){
            printf("%d\n",i);
            break;
        }

      }
    }


  }


  return 0;

}

Measured memory_bytes: 612
from bisect import bisect_left
import sys
n, Q = [int(x) for x in sys.stdin.readline().split()]
stx = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
q = [int(sys.stdin.readline()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end:
    if skip[begin]==-1:
      ans[begin] = x
      skip[begin] = end
      begin += 1
    else:
      begin = skip[begin]
for e in ans:
  print(e)

Measured memory_bytes: 61696