akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
#include <climits>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;

int n,m;

int pow2(int m){
    if(m==0)return 1;
    else return 2*pow2(m-1);
}
int main() {
    cin >> n >> m;
    int res = ((n-m)*100+m*1900)*pow2(m);
    put(res);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> A;
int N,M;
int P[100001],Y[100001];
int K[100001];  // K[市i]: 県の中で何番目か
signed main() {
    cin >> N >> M;
    vector<A>vec[100001]; // vec[県i]: (年, 市)のvector
    for(int i = 0; i < M; i++) {
        cin >> P[i] >> Y[i];
        vec[P[i]].push_back(A(Y[i], i));
    }
    for(int i = 1; i <= N; i++) {
        sort(vec[i].begin(),vec[i].end());
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < vec[i].size(); j++) {
            K[vec[i][j].second] = j;
        }
    }
    for(int i = 0; i < M; i++) {
        printf("%06d" "%06d\n",P[i],K[i]+1);
    }
}


Measured memory_bytes: 8192
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		System.out.println(x >= r && y >= r && x <= W - r && y <= H - r ? "Yes" : "No");
	}
}


Measured memory_bytes: 26324
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int i,j,n,m,x,y,a;
  while(cin >> n){
    cin >> m;
    n--;
    for(i=0;i<m;i++){
      cin >> x >> y;
      x--;
      y--;
      if(x > n/2) x = n - x;
      if(y > n/2) y = n - y;
      a = min(x,y);
      cout << a % 3 + 1 << endl;
    }

  }
  return 0;
}

Measured memory_bytes: 0
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))

A=np.array(a)
counter=np.bincount(A)
ct=counter[counter.nonzero()]
arr=ct.tolist()
arr=sorted(arr)

dis=len(set(A))-k

cnt=0
for i in range(dis):
    cnt+=arr[i]

print(cnt)



Measured memory_bytes: 44400
def compress(n, s)
  list = []
  
  obj = [s[0].to_i, 0]
  
  n.times do |i|
    if obj[0] != s[i].to_i then
      list.push(obj.dup)
      
      obj[0] = s[i].to_i
      obj[1] = 1
    else
      obj[1] += 1
    end
  end
  
  list.push(obj.dup)
  
  return list
end

def main(argv)
  (n, k) = gets.chomp.split(' ').map(&:to_i)
  s = gets.chomp
  
  list = compress(n, s)
  
  cumsum = [0] * (list.size + 1)
  list.size.times do |i|
    cumsum[i + 1] = cumsum[i] + list[i][1]
  end
  
  if list[0][0] == 0 then
    if list.size < (k + 2) then
      puts cumsum[list.size].to_s
    else
      max = 0
      
      i = 0
      while i < list.size do
        m = -1
        if list[i][0] == 0 then
          m = [list.size, (k + (k + 0)) + i].min
        else # list[i][0] == 1
          m = [list.size, (k + (k + 1)) + i].min
        end
        
        max = [max, cumsum[m] - cumsum[i]].max
        
        i += 1
      end
      
      puts max.to_s
    end
  elsif list[0][0] == 1 then
    if (list.size < (k + 3)) then
      puts cumsum[list.size].to_s
    else
      max = 0
      
      i = 0
      while i < list.size do
        m = -1
        if list[i][0] == 0 then
          m = [list.size, (k + (k + 0)) + i].min
        else # list[i][0] == 1
          m = [list.size, (k + (k + 1)) + i].min
        end
        
        max = [max, cumsum[m] - cumsum[i]].max
        
        i += 1
      end
      
      puts max.to_s
    end
  end
end

if self.to_s == 'main' then
  main(ARGV)
end

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

bool isPrime(int x) {
    if (x == 2) {
        return true;
    }
    if (x < 2 || (x % 2 == 0)) {
        return false;
    }

    int rt_x = (int)sqrt((double)x);
    for (int i =  3; i <= rt_x; i += 2) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int x;
    int cnt = 0;
    while (n > 0) {
        cin >> x;
        if (isPrime(x)) {
            cnt++;
        }
        n--;
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3084
_ = gets
$<.each_line do |line|
  x1, y1, x2, y2, x3, y3 = line.split.map(&:to_f)
  a = ((x2-x1)**2 + (y2-y1)**2)**0.5
  b = ((x3-x2)**2 + (y3-y2)**2)**0.5
  c = ((x1-x3)**2 + (y1-y3)**2)**0.5

  a1 = 2*(x2 - x1)
  b1 = 2*(y2 - y1)
  c1 = x1**2 - x2**2 + y1**2 - y2**2
  a2 = 2*(x3 - x1)
  b2 = 2*(y3 - y1)
  c2 = x1**2 - x3**2 + y1**2 - y3**2

  x = (b1*c2 - b2*c1) / (a1*b2 - a2*b1)
  y = (c1*a2 - c2*a1) / (a1*b2 - a2*b1)
  r = (a*b*c) / (((a+b+c)*(b+c-a)*(c+a-b)*(a+b-c))**0.5)

  printf "%.3f %.3f %.3f\n", x, y, r
end

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

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
        int k;
        string s;
        cin >> k >> s;

        if (s.size() <= k) {
                cout << s << endl;
        } else {
                cout << s.substr(0, k) + "..." << endl;
        }

        return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& base) {
    for (T const& i : base) {
        out << i << ' ';
    }
    return out;
}
vector<int> S;
vector<bool> visited;
vector<list<int>> G;
void DFS(int x){
    visited[x] = true;
    for(int y : G[x]){
        if(!visited[y]) DFS(y);
    }
    S.push_back(x);
}
int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N+1);
    visited.assign(N+1, false);
    for(int i = 0, x, y; i < M; ++i){
        cin >> x >> y;
        G[x].push_back(y);
    }
    for(int i = 1; i <= N; ++i){
        if(!visited[i]){
            DFS(i);
        }
    }
    int DP[N + 1];
    memset(DP, 0, sizeof DP);
    for(int i = 0; i < N; ++i){
        int node = S[i];
        for(int j : G[node]){
            DP[node] = max(DP[node], 1 + DP[j]);
        }
    }
    cout << *max_element(DP + 1, DP + N + 1) << endl;
}

Measured memory_bytes: 11424
#include <iostream>
using namespace std;
int a,b,c;
int main()
{
	cin>>a>>b>>c;
	for (int i=1;i<=1000;i++)
	{
		if (i*a%b==c)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
}

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

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin>>n>>k;
    int c1 = 0 , c2 = 0, aa[100005]={0};
    map<int,int> ac,wrong;
    while(k--)
    {
        int a; string s;
        cin>>a>>s;
        if(ac[a]) continue;
        if(s=="AC")
        {
            if(!ac[a]){
                c1++; ac[a] = 1;
                c2+=aa[a];
            }
        }
        else{
            aa[a]++;
        }
    }
    cout<<c1<<" "<<c2;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14 100兆
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main(){
  double A, B, H, M;
  cin >> A >> B >> H >> M;
  double t = 60*H+M;
  double x = t/2;
  double y = M * 6;
  cout << fixed << setprecision(20);
  cout << sqrt(B*B + A*A - 2.0 * A * B * cos((y-x)*M_PI/180)) << endl;
}


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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')

typedef long long ll;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;
const int INF = 0x3f3f3f3f;
const int maxn = 110000;
int main()
{
    //检查有没有特判0,有没有越界限.
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    int A, B;
    cin >> A >> B;
    int res = (A - 2 * B) < 0 ? 0 : (A - 2 * B);
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 3640
import java.util.*;
public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		String[] str = new String[N];
		int L = scn.nextInt();
		for (int i = 0; i < N; i++) {
			str[i] = scn.next();
		}
		for (int i = 0; i < L; ++i) {
			for (int j = i + 1; j < N; ++j) {
				if (str[i].compareTo(str[j]) > 0) {
					String temp = str[i];
					str[i] = str[j];
					str[j] = temp;
				}
			}
		}
		Arrays.sort(str);
		String ans = "";
		for (int i = 0; i < N; i++) {
			ans = ans + str[i];
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 33420
#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define int long long
#define for0(i,n) for (int i=0; i<n; i++)
#define iter(c) for(auto it=c.begin(); it!=c.end(); it++)
#define iter2(c) for(auto it2=c.begin(); it2!=c.end(); it2++)
#define vec(x) vector< x >
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define sqr(x) 1LL*(x)*(x)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif

using namespace std;

typedef long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

int freq[100005];

int32_t main()
{
    #ifdef DEBUG
    freopen("A.txt","r",stdin);
    //freopen("","w",stdout);
    #endif

    ms(freq,0)0;
    int n;
    cin >> n;
    for0(i,n) {
        int x; read(x);
        freq[x]++;
    }
    
    int best = 0;
    for (int x=0; x<=100001; x++) {
        int cnt = freq[x] + freq[x+1] + (x > 0 ? freq[x-1] : 0);
        best = max(best,cnt);
    }
    cout<<best<<endl;
    return 0;
}


Measured memory_bytes: 1024
def main():
    from itertools import chain

    N, M, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())

    t = sum(B)
    ans = 0
    j = M
    for i, x in enumerate(chain([0], A)):
        t += x
        while j > 0 and t > K:
            j -= 1
            t -= B[j]
        if t > K: break
        if ans < i + j:
            ans = i + j
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 42192
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func gcdiv(a, b int) int {
	big := max(a, b)
	small := min(a, b)
	if small == 0 {
		return big
	}
	return gcdiv(big-small, small)
}

func main() {
	A := readint()
	B := readint()
	gcd := gcdiv(A, B)
	ans := A * B / gcd
	fmt.Println(ans)
}

const (
	iobufsize = 1 * 1024 * 1024 // 1 MB
)

var stdinsc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, iobufsize), iobufsize)
	sc.Split(bufio.ScanWords)
	return sc
}()

func readint() int {
	stdinsc.Scan()
	v, err := strconv.Atoi(stdinsc.Text())
	if err != nil {
		panic(err)
	}
	return v
}

func readstr() string {
	stdinsc.Scan()
	return stdinsc.Text()
}

func pow(x, y int) int {
	if y < 1 {
		return 1
	}
	return x * pow(x, y-1)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}


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

bool flag[60];
bool wake = true;

bool check(int c)
{
	return flag[c - 1];
}

int solve(int a, int b, int c)
{
	int count = 0;
	int cur = 0;
	int time = 0;
	while (true) {
		flag[cur] = wake;
		count++;
		cur++;
		if (count == a&&wake == true) {
			wake = false;
			count = 0;
		}
		if (count == b&&wake == false) {
			wake = true;
			count = 0;
		}

		if (cur == 60) {
			if (check(c) == true) {
				time += c;
				break;
			}
			else {
				time += 60;
				cur = 0;
			}
		}

		if (time >= 3600) {
			break;
		}
	}

	if (time >= 3600) {
		return -1;
	}
	else {
		return time;
	}
}

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

	for (int i = 0; i < 60; i++) {
		flag[i] = false;
	}

	cout << solve(a, b, c) << endl;

	return 0;
}

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

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
  SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while (n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while (k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
  // func(unit) == false
  // min left: st <= res && func(seg.query(res,n))
  template <typename C>
  int find_left(int st, C &func, T acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(acc, dat[k]);
      return func(acc) ? l : -1;
    }
    int mid = (l + r) >> 1;
    if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);
    if (st <= l && !func(f(acc, dat[k]))) {
      acc = f(acc, dat[k]);
      return -1;
    }
    int nres = find_left(st, func, acc, (k << 1), l, mid);
    if (~nres) return nres;
    return find_left(st, func, acc, (k << 1) | 1, mid, r);
  }
  template <typename C>
  int find_left(int st, C &func) {
    T acc = unit;
    return find_left(st, func, acc, 1, 0, n);
  }

  // max right: res <= st && func(seg.query(0,res))
  template <typename C>
  int find_right(int st, C &func, T acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(dat[k], acc);
      return func(acc) ? r : -1;
    }
    int mid = (l + r) >> 1;
    if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);
    if (r <= st && !func(f(dat[k], acc))) {
      acc = f(dat[k], acc);
      return -1;
    }
    int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);
    if (~nres) return nres;
    return find_right(st, func, acc, k << 1, l, mid);
  }
  template <typename C>
  int find_right(int st, C &func) {
    T acc = unit;
    return find_right(st, func, acc, 1, 0, n);
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &p : a) cin >> p;
  auto f = [](int l, int r) { return max(l, r); };
  SegmentTree<int> seg(a, f, -1);
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1)
      seg.update(x - 1, y);
    else if (t == 2)
      cout << seg.query(x - 1, y) << endl;
    else {
      auto c = [&](int p) { return p >= y; };
      int res = seg.find_left(x - 1, c);
      if (res < 0) res = n;
      cout << res + 1 << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 6112
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define dbg(n) cout<<#n<<' '<<n<<endl;
int power(ll x,ll y){ll res = 1;while(y>0){if(y&1)res = (res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}

int main(){ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int d;
	cin>>d;
	int a[26];
	vector<pair<int,int>>b[d];
	for(int i=0;i<26;i++)cin>>a[i];
	for(int i=0;i<d;i++){
		int x;
		for(int j=0;j<26;j++){
			cin>>x;
			b[i].pb(mp(x,j));
		}
	}
	for(int i=0;i<d;i++){
		sort(b[i].begin(),b[i].end());
	}
	for(int i=0;i<d;i++){
		cout<<b[i][25].S+1<<endl;
	}
}



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

int main(){
	cin.tie(nullptr) ;
	ios::sync_with_stdio(false) ;
	int n ; cin >> n ;
	int ans = 1000 ;
	for(int i=0;i<n;i++){
		int a ; cin >> a ;
		int cnt = 0 ;
		while(1){
			if(a&1) break ;
			cnt++ ;
			a /= 2 ;
		}
		if(ans>cnt) ans = cnt ;
	}
	cout << ans << "\n" ;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	scanner.Scan()
	s := scanner.Text()
	sEnd := string(s[len(s)-1])

	result := ""
	if sEnd == "s" {
		result = s + "es"
	} else {
		result = s + "s"
	}

	fmt.Println(result)
}


Measured memory_bytes: 1776
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

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

int main(void) {
  int i,j;
  int n;
  cin>>n;
  vi c(n-1),s(n-1),f(n-1);
  rep(i,n-1)cin>>c[i]>>s[i]>>f[i];
  rep(i,n-1){
    ll t=s[i]+c[i];
    loop(j,i+1,n-1){
      if(t<s[j])t=s[j];
      if(t%f[j])t+=f[j]-t%f[j];
      t+=c[j];
    }
    cout<<t<<endl;
  }
  cout<<0<<endl;
}


Measured memory_bytes: 256
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+5)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Measured memory_bytes: 44996
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int MOD = 1000000007;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		sc.close();

		Calc calc = new Calc(MOD);
		int result = calc.subtract(calc.subtract(calc.subtract(calc.pow(2, n), 1), calc.combine(n, a)), calc.combine(n, b));
		System.out.println(String.format("%d", result));
	}

	public static class Calc {
		int mod;

		public Calc(int mod) {
			this.mod = mod;
		}

		public int add(int a, int b) {
			return (int) (((long) a + b) % mod);
		}

		public int subtract(int a, int b) {
			return (int) (((long) a - b + mod) % mod);
		}

		public int multiply(int a, int b) {
			return (int) (((long) a * b) % mod);
		}

		public int divide(int a, int b) {
			return multiply(a, pow(b, mod - 2));
		}

		public int pow(int n, int k) {
			if (k == 0) {
				return 1;
			} else if (k % 2 == 0) {
				int p = pow(n, k / 2);
				return multiply(p, p);
			} else {
				int p = pow(n, (k - 1) / 2);
				return multiply(multiply(p, p), n);
			}
		}

		public int combine(int n, int k) {
			int sum1 = 1;
			int sum2 = 1;
			for (int i = 0; i < k; i++) {
				sum1 = multiply(sum1, n - i);
				sum2 = multiply(sum2, i + 1);
			}
			return divide(sum1, sum2);
		}
	}
}


Measured memory_bytes: 23892
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[105],sum=0;
int main() {
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	sort(a,a+n);
	int p=0;
	while(sum>0&&sum%10==0&&p<n) {
		if (a[p]%10!=0)
			sum=sum-a[p];
		p++;
	}
	if(sum%10==0)	printf("0");
	else	printf("%d",sum);
	return 0;
}

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

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

int ans[100005];

int main(void) {
    int N;
    cin >> N;

    for (int x=1; x<=100; x++) {
        for (int y=1; y<=100; y++) {
            for (int z=1; z<=100; z++) {
                int sum = x*x+y*y+z*z+x*y+y*z+z*x;
                if (sum<=10005) ans[sum]++;
            }
        }
    }

    rep(i, 1, N+1) cout << ans[i] << endl;
    

    return 0;
}



Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
int main()
{
  string s;
  cin>>s;
  if(s=="Sunny")
  {
    cout<<"Cloudy"<<endl;
  }
  else if(s=="Cloudy")
  {
    cout<<"Rainy"<<endl;
  }
  else if(s=="Rainy")
  {
    cout<<"Sunny"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)

int main()
{
    int n, g[100][100], k, v;
    scanf("%d", &n);
    fill(g[0], g[100], 0);

    rep(i, n){
        scanf("%d", &k); scanf("%d", &k);
        rep(j, k){
            scanf("%d", &v);
            g[i][v-1] = 1;
        }
    }

    rep(i,n){
        rep(j, n) printf((j ? " %d" : "%d"), g[i][j]);
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2800
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                    # ll = deepcopy(l)
from heapq import *                    # heappush(hp,x)
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                # minn = -maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                # pre = [0] + list(accumulate(l))
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(l):
	a,b = l
	p = a*b
	return p
	

l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)



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

using namespace std;
const int N = 1e5 + 3;
int n;
char s[N];
bool valid() {
	for (int i = 0; i <= n / 2; ++i)
		if (s[i] != s[n - i])
			return false;
	return s[1] == '1';
}
int main() {
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	scanf("%s", s + 1);
	s[0] = '0';
	n = strlen(s + 1);
	if (!valid()) {
		puts("-1");
		return 0;
	}
	vector<pair<int, int>> edges;
	edges.emplace_back(1, 2);
	int leaf = 2, prevRoot = 1;
	for (int i = 2; i <= n - 2; ++i) {
		if (s[i] == '1') {
			edges.emplace_back(prevRoot, ++leaf);
			prevRoot = leaf;
		} else {
			edges.emplace_back(prevRoot, ++leaf);
		}
	}
	while (leaf < n)
		edges.emplace_back(prevRoot, ++leaf);
	for (auto p: edges) {
		printf("%d %d\n", p.first, p.second);
	}
	return 0;
}

Measured memory_bytes: 2420
str = gets.chomp

prev_s = ''
ans = 0
str.each_char.with_index do |s, i|
  if prev_s != ''
    if prev_s == s
      if s == '0'
        prev_s = '1'
      else
        prev_s = '0'
      end
      ans += 1
    else
      prev_s = s
    end
  else
    prev_s = s
  end
end
puts ans


Measured memory_bytes: 1916
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1, 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    int N;
    cin >> N;
    vector<int> a(N);
    for (auto &&i : a) {
        cin >> i;
        i--;
    }
    vector<bool> ok(N);
    ok[0]     = true;
    int light = 0;
    int ans   = 1;
    while (!ok[a[light]]) {
        int nxt = a[light];
        if (nxt == 1) {
            print(ans);
            return 0;
        }
        ok[light] = true;
        light     = nxt;
        ans++;
    }
    print(-1);

    return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] str = sc.next().split("");
        
        Map<String, Integer> map = new HashMap<>();
        for (String s : str) {
            if (map.containsKey(s)) {
                map.put(s, map.get(s)+1);
            } else {
                map.put(s, 1);
            }
        }
        
        System.out.println(map.containsKey("1") ? map.get("1") : 0);
    }
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
	llong N;
	cin >> N;

	for (int i = 0; i <= N; ++i) {
		if (llong(i*1.08) == N) {
			cout << i << endl;
			return 0;
		}
	}

	cout << ":(" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXV = 300;
const int MAXE = MAXV * MAXV;
const int MAXF = (1<<29);
typedef int F;

struct MaxFlow {
    F cap[MAXE], flow[MAXE];
    int V, E, level[MAXV], prev[MAXE], edge[MAXV], to[MAXE];
    MaxFlow(int n) : E(0) {
        V = n;
        memset(flow, 0, sizeof(flow));
        memset(prev, -1, sizeof(prev));
        memset(edge, -1, sizeof(edge));
    }
    void add_edge(int s, int t, F f, F g = 0) {
        cap[E] = f; to[E] = t; prev[E] = edge[s]; edge[s] = E; E++;
        cap[E] = g; to[E] = s; prev[E] = edge[t]; edge[t] = E; E++;
    }
    void make_level(int s) { // make level graph (bfs)
        memset(level, -1, sizeof(level));
        queue<int> q; q.push(s); level[s] = 0;
        while(!q.empty()) {
            int v = q.front(); q.pop();
            for (int e = edge[v]; e != -1; e = prev[e]) {
                if (cap[e] - flow[e] > 0 && level[to[e]] == -1)
                    q.push(to[e]), level[to[e]] = level[v]+1;
            }
        }
    }
    int augment(int s, int t, F f) { // find augment path (dfs)
        if (s == t || f == 0) return f;
        for (int e = edge[s]; e != -1; e = prev[e]) {
            if (level[to[e]] > level[s] && cap[e] - flow[e] > 0) {
                F g = augment(to[e], t, min(f, cap[e] - flow[e]));
                if (g > 0) {
                    flow[e] += g, flow[e^1] -= g;
                    return g;
                }
            }
        }
        return 0;
    }
    int max_flow(int s, int t) {
        int f, ret = 0;
        for (bool cont = true; cont; ) {
            cont = false;
            make_level(s);
            while ((f = augment(s, t, MAXF)) > 0) {
                cont = true;
                ret += f;
            }
        }
        return ret;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int x[MAXE], y[MAXE];
    int N,M,a,b;
    cin>>N>>M;
    MaxFlow mf(N);
    for (int i=0; i<M; ++i) {
        cin>>a>>b; a--, b--;
        mf.add_edge(a, b, 1, 1);
        x[i] = a, y[i] = b;
    }
    cin>>a>>b; a--, b--;
    cout<<mf.max_flow(a, b)<<endl;
    vector<int> rev;
    for (int i=0; i<M; ++i) {
        int e = mf.edge[y[i]];
        while(e != -1) {
            if (mf.to[e] == x[i] && mf.flow[e] > 0) rev.push_back(i);
            e = mf.prev[e];
        }
    }
    cout<<rev.size()<<endl;
    for (int i=0; i<rev.size(); ++i) cout<<rev[i]+1<<endl;
}

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

int main() {
  
  int N=0, K=0, X=0, Y=0;
  int sum=0, day=0;
  
  cin >> N;
  cin >> K;
  cin >> X;
  cin >> Y;
  
  if(N<=K) {
    
    sum = N*X;
    
    cout << sum << endl;
    
  } else {
    
    int day = N-K;
    
    sum = K*X + day*Y;
    
    cout << sum << endl;
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

const long long mod = 1000000007;

int main() {
  int A, B;
  cin >> A >> B;
  cout << max(A + B, 2 * max(A, B) - 1) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long k,_min,_max,x_y,x,y,fib[2],a,i;double mid;
#define MOD 1000000007
int dp[3];
int main(){
    cin>>k;
    a=sqrt(k)/16;
    x_y=(long long)(2*sqrtl(k-a-0.01))-1;
    _max=(x_y+2)*(x_y+2)/4;
    _min=(x_y+1)*(x_y+1)/4+1;
    mid=1.0*(_max+_min)/2;
    if(k<=mid){y=(k-_min)*2;}
    else{y=(_max-k)*2+1;}
    x=x_y-y;
    if(x<3){
        fib[0]=x+1;
    }
    else{
        dp[0]=1;
        dp[1]=2;
        dp[2]=3;
 
        for(i=3;i<=x;i+=3)
        {
            dp[0]=(dp[1]+dp[2])%MOD;
            dp[1]=(dp[2]+dp[0])%MOD;
            dp[2]=(dp[0]+dp[1])%MOD;
        }
 
        fib[0]=dp[x%3];
    }
    if(y<3)
    {
        fib[1]=y+1;
    }
    else{
        dp[0]=1;
        dp[1]=2;
        dp[2]=3;
 
        for(i=3;i<=y;i+=3)
        {
            dp[0]=(dp[1]+dp[2])%MOD;
            dp[1]=(dp[2]+dp[0])%MOD;
            dp[2]=(dp[0]+dp[1])%MOD;
        }
 
        fib[1]=dp[y%3];
    }
 
    cout<<(fib[0] * fib[1])%MOD<<endl;
}

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

#define REP(i,n) for(long long i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(long long i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int N, C;
vector<int> s, t, c;
vector<vector<pair<int, int>>> ch;

int main(){
  cin >> N >> C;
  s.resize(N), t.resize(N), c.resize(N), ch.resize(C);
  REP(i, N){
    cin >> s[i] >> t[i] >> c[i];
    s[i]-= 0.5;
    c[i]--;
    ch[c[i]].push_back(make_pair(s[i], t[i]));
  }
  REP(i, C){
    ch[i].push_back(make_pair(1e6, 1e7));
    sort(ch[i].begin(), ch[i].end());
  }
  vector<int> cu(N, 0);
  int ans = 0;
  REP(i, 100001){
    int cnt =0;
    REP(j, C){
      // cout <<"i: " << i << " j: " << j << " cu[j]: " << cu[j] << endl;
      // cout << ch[j][cu[j]].first << " " << ch[j][cu[j]].second << endl;
      while(ch[j][cu[j]].second < i){
        // cout << cu[j] << endl;
        cu[j]++;
      }
      if(ch[j][cu[j]].first <= i && i < ch[j][cu[j]].second){
        cnt++;
      }
    }
    ans = max(cnt, ans);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    int n; cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        if(i %3 != 0 && i %5 != 0) sum += i;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int main(){
	int n;
	cin >> n;
	vector<string>ss(n);
	bool ok = true;
	for (int i = 0; i < n; i++) {
		cin >> ss[i];
		for (int j = 0; j < i; j++) {
			if (ss[i] == ss[j]) {
				//cout << "No" << endl;
				//return 0;
				ok = false;
			}
		}
	}
	if (ok == false) {
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < n-1; i++) {
		//int a = ss[i].size();
		if (ss[i][ss[i].size()-1] != ss[i + 1][0]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

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

    long double ans = 0;

    for (int i = 1; i <= n; i++) {
        int value = i;
        long double temp = 1.0 / n;

        while (value < k) {
            value *= 2;
            temp /= 2.0;
        }

        ans += temp;
    }

    printf("%.10Lf\n", ans);
}


Measured memory_bytes: 256
N = int(input())
dp = [[0] * 3 for _ in range(N)]

dp[0][0], dp[0][1], dp[0][2] = list(map(int, input().split()))
for i in range(1,N):
  abc = list(map(int, input().split()))
  for j,k,l in ((0,1,2), (1,0,2), (2, 0, 1)):
    dp[i][j] = abc[j] + max(dp[i-1][k], dp[i-1][l])

print(max(dp[N-1]))

Measured memory_bytes: 22900
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
string s;
int k;
set<string> ses;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> s >> k;
  REP(i, s.length()) {
    string ss;
    ss.push_back(s[i]);
    ses.insert(ss);
    for(int j=1; i + j < s.length() && j < k; j++) {
      ss.push_back(s[i + j]);
      ses.insert(ss);
    }
  }

  int i = 1;
  for(auto x : ses) {
    if(i++ == k) cout << x << endl;
  }
}


Measured memory_bytes: 1664
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
long long n,k;
int main()
{
	scanf("%lld %lld",&n,&k);
	long long hh=n/k;
	long long ans=hh*hh*hh;
	if((k&1)==0)
	{
		n+=k/2;
		hh=n/k;
		ans+=hh*hh*hh;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
#define ll long long 

int main() {
	ll int n;
	cin>>n;
	ll int ans = 0;
	for(int i = 1; i <= n;i++)
	{
		if(i%3 == 0 && i%5 == 0){}
		else
		if(i%3 == 0){}
		else
		if(i%5 == 0){}
		else
		{
			ans += i;
		}
	}
	cout<<ans;

	return 0;
}

Measured memory_bytes: 3624
// Contest No.: ABC177
// Problem No.: B
// Solver:      Jinmin Goh
// Date:        20200829

#include <cstring>
#include <iostream>
#include <cstdlib>
#include <list>
#include <array>
#include <atomic>
#include <algorithm>
#include <deque>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <valarray>
#include <vector>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int nums[100010];

int main() {
    char s[1010], t[1010];
    scanf("%s", s);
    scanf("%s", t);
    int maxVal = 0;
    for(int i = 0; i < strlen(s) - strlen(t) + 1; i++) {
        int tempVal = 0;
        for(int j = 0; j < strlen(t); j++) {
            if(s[i + j] == t[j]) {
                tempVal++;
            }
        }
        maxVal = max(maxVal, tempVal);
    }
    printf("%ld", strlen(t) - maxVal);
    return 0;
}

Measured memory_bytes: 3812
#!/usr/bin/env python3
from collections import deque

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    white_count = 0

    for s in S:
        for ss in s:
            if ss == ".":
                white_count+=1

    vector = [[1,0],[-1,0],[0,-1],[0,1]]
    min_distance = [[float('inf')]*W for _ in range(H)]
    queue = deque([[0,0]])
    min_distance[0][0] = 0

    while queue:
        q = queue.popleft()
        for v in vector:
            nqy = q[0]+v[0]
            nqx = q[1]+v[1]

            if nqx>=0 and nqy>=0 and nqx<=W-1 and nqy<=H-1 and min_distance[nqy][nqx]==float('inf') and S[nqy][nqx]!="#":
                queue.append([nqy,nqx])
                min_distance[nqy][nqx]=min_distance[q[0]][q[1]]+1

    if min_distance[H-1][W-1] == float('inf'):
        print(-1)
    else:
        print(white_count - min_distance[H-1][W-1]-1)



if __name__ == '__main__':
    main()


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

template<class Monoid> struct SegmentTree {
	using Function = function< Monoid(Monoid, Monoid) >;

	int N; vector<Monoid> segment;
	const Function func;
	const Monoid id;

	SegmentTree(int n, const Function func, const Monoid id) : func(func), id(id) {
		N = 1;
		while (N < n) N <<= 1;
		segment.assign(2 * N, id);
	}

	void set(int num, Monoid x) {
		segment[N + num] = x;
	}
	void build() {
		for (int k = N - 1; k > 0; k--) {
			segment[k] = func(segment[2*k], segment[2*k+1]);
		}
	}
	void update(int k, Monoid x) {
		k = k + N; segment[k] = x;
		while(k >>= 1) {
			segment[k] = func(segment[2*k], segment[2*k+1]);
		}
	}

	// query:[a, b)
	Monoid query(int a, int b) {
		Monoid L = id; Monoid R = id; a += N; b += N;
		for (; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = func(L, segment[a++]);
			if (b & 1) R = func(segment[--b], R);
		}
		return func(L, R);
	}
	// 0-based numbering;
	Monoid operator[](const int k) const {
		return segment[N+k];
	}
};

int main() {
    int n; cin >> n;
    vector<int> b(n), diff(n+1, 0); int all = 0;
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = n-1; i >= 0; i--) {
        int a = b[i] == 0 ? 1 : -1;
        all += b[i];
        diff[i] = diff[i+1] + a;
    }
    int q; cin >> q;
    set<pair<int, int>> query;
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        query.insert({a-1, b-1});
    }
    vector<int> dp(n+1, 1e9);
    SegmentTree<int> st(n+1, [](int a, int b){return min(a, b);}, 1e9);
    // st[x] = dp[0, x) + diff[x, n)
    dp[0] = all; st.update(0, all+diff[0]);
    st.build();
    for (int left = 0; left < n; left++) {
        while (!query.empty() && query.begin()->first == left) {
            int right = query.begin()->second;
            query.erase(query.begin());
            // query: [left, right]
            int ret = st.query(left, right+1);
            dp[right+1] = min(dp[right+1], ret - diff[right+1]);
            st.update(right+1, dp[right+1] + diff[right+1]);
        }
        
        dp[left+1] = min(dp[left+1], dp[left]);
        st.update(left+1, min(st[left+1], dp[left+1] + diff[left+1]));
    }
    cout << dp[n] << endl;
    return 0;
}

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


using namespace std;

#ifdef CLION
ifstream ifs("/home/kyuridenamida/CLionProjects/project/input.txt");
#define cin ifs
#define scanf DONT_USE_SCANF
#endif

string S;

long long dp[111][2][4];

long long dfs(int pos, int ub, int kk) {
    if (kk < 0) return 0;
    if (pos == S.size()) return kk == 0;

    if (dp[pos][ub][kk] != -1)
        return dp[pos][ub][kk];

    long long ans = 0;
    if (ub == 1) {
        for (int i = 0; i <= S[pos] - '0'; i++) {
            bool nub = i == S[pos] - '0';
            ans += dfs(pos + 1, nub, kk - (i != 0));
        }
    } else {
        for (int i = 0; i <= 9; i++) {
            ans += dfs(pos + 1, 0, kk - (i != 0));
        }
    }
    return dp[pos][ub][kk] = ans;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> S;
    int K;
    cin >> K;

    cout << dfs(0, 1, K);

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char c[2]={'C','F'};
string s;
long long op=0;
int main()
{
    cin>>s;
    for(long long i=0;i<s.size();i++)
    {
        if(op==2)
        {
            printf("Yes");
            return 0;
        }
        if(s[i]==c[op])
        {
            op++;
        }
    }
    if(op==2)
    {
        printf("Yes");
        return 0;
    }
    printf("No");
    return 0;
}


Measured memory_bytes: 256
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for i, (Ai, Bi) in enumerate(AB):
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq
MY_INF = 10 ** 18

q = [(0, u - 1)]
d_u = [MY_INF] * N
d_u[u - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_u[dst] > dist_tmp:
            d_u[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

q = [(0, v - 1)]
d_v = [MY_INF] * N
d_v[v - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_v[dst] > dist_tmp:
            d_v[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

# print("#", d_u)
# print("#", d_v)
            
ans = 0
for i in range(N):
    if d_u[i] < d_v[i] and ans < d_v[i] - 1:
        ans = d_v[i] - 1

print(ans)

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

int n, L, cnt, tmp, e[80][3];

int main() {
	scanf("%d", &L);
	tmp = L;
	while (tmp) tmp /= 2, n++;
	for (int i = 1; i < n; i++) {
		e[++cnt][0] = i; e[cnt][1] = i + 1; e[cnt][2] = 1 << i - 1;
		e[++cnt][0] = i; e[cnt][1] = i + 1; e[cnt][2] = 0;
	}
	tmp = 1 << n - 1;
	for (int i = n - 1; i >= 1; i--) {
		if (L & (1 << i - 1)) {
			e[++cnt][0] = i; e[cnt][1] = n; e[cnt][2] = tmp;
			tmp += 1 << i - 1;
		}
	}
	printf("%d %d\n", n, cnt);
	for (int i = 1; i <= cnt; i++)
		printf("%d %d %d\n", e[i][0], e[i][1], e[i][2]);
	return 0;
}

Measured memory_bytes: 3768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int d = 10, p[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}, z = 0;
    char c;
    for (int i = 0; i < 10; i++) {
        cout << '?' << ' ' << p[i] << endl;
        cin >> c;
        if (c == 'N') {d = i; break;}
    }
    if (d == 10) {
        for (int i = 1; i < 10; i++) {
            cout << '?' << ' ' << p[i] - 1 << endl;
            cin >> c;
            if (c == 'Y') {cout << '!' << ' ' << p[i - 1] << endl; return 0;}
        }
        cout << '!' << ' ' << 1000000000 << endl;
        return 0;
    }
    for (int i = 0; i + 1 < d; i++) {
        int l = 0, r = 10;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            cout << '?' << ' ' << z + m << endl;
            cin >> c;
            if (c == 'Y') l = m;
            else r = m;
        }
        z += l;
        z *= 10;
    }
    for (int i = 0; i < 10; i++) {
        if (!i && !z) continue;
        cout << '?' << ' ' << (ll)z * 10 + i * 10 << endl;
        cin >> c;
        if (c == 'Y') {z += i; break;}
    }
    cout << '!' << ' ' << z << endl;
}


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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int N, K, Z=0, A;
    cin >> N >> K;
    int D[N], h[N];
    for (int i = 0; i < N; i++)
    {
        cin >> h[i];
    }
    D[0] = 0;
    D[1] = fabs(h[1]-h[0]);
    for (int i = 2; i < N; i++)
    {
        D[i] = 2000000000;
        for (int y = max(Z,i-K); y < i; y++)
        {
            A = fabs(h[y]-h[i]);
            D[i] = min(D[y]+A,D[i]);
        }
    }
    cout << D[N-1];
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();

        System.out.println("" + A.charAt(0) + B.charAt(0) + C.charAt(0));

        sc.close();

    }

}


Measured memory_bytes: 10192
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	int d=s.length();
	int e=t.length();
	int f=min(d,e);
	if(abs(e-d)!=1){
		cout<<"No\n";
}
	else{
		int count=0;
		for(int i=0;i<f;i++){
				if(s[i]!=t[i])
				count++;
	
}
		if(count==0)
		cout<<"Yes\n";
		else
		cout<<"No\n";
	}
	return 0;
}

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

using ll = long long;
using G = vector<vector<int>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
using pci = pair<char, int>;

ll GCD(ll x, ll y){
	return y ? GCD(y, x%y) : x;	
}

int main() {
	int n; cin >> n;
	string s; cin >> s;
	int r[4005], g[4005], b[4005];
	int rcnt = 0, gcnt = 0, bcnt = 0;
	for(int i=0;i<n;i++){
		r[i] = rcnt;
		g[i] = gcnt;
		b[i] = bcnt;
		if(s[i]=='R') rcnt++;
		if(s[i]=='G') gcnt++;
		if(s[i]=='B') bcnt++;
	}
	r[n] = rcnt;
	g[n] = gcnt;
	b[n] = bcnt;

	ll ans =0LL;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if((s[i]=='R' && s[j]=='G') || (s[i]=='G' && s[j]=='R')){
				ans += b[n]-b[j];
				if(s[2*j-i]=='B') ans--;
			}
			if((s[i]=='G' && s[j]=='B') || (s[i]=='B' && s[j]=='G')){
				ans += r[n]-r[j];
				if(s[2*j-i]=='R') ans--;
			}
			if((s[i]=='B' && s[j]=='R') || (s[i]=='R' && s[j]=='B')){
				ans += g[n]-g[j];
				if(s[2*j-i]=='G') ans--;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3664
n,m=gets.chomp.split(" ").map(&:to_i)
A = []
n.times do
    row=gets.chomp.split(" ").map(&:to_i)
    A.push(row)
end
(0..(m-1)).each do |j|
    a = gets.to_i
    (0..(n-1)).each do |i|
        A[i][j] = A[i][j] * a
    end
end

A.each do |row|
    puts row.inject(:+)
end



Measured memory_bytes: 8932