akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, StdoutLock, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , bytes ) => { read_value ! ( $ next , String ) . into_bytes ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
#[allow(dead_code)]
pub fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
    let out = stdout();
    let writer = BufWriter::new(out.lock());
    f(writer)
}
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) } ; }
#[allow(dead_code)]
fn main() {
    input!{
        n: usize,
        xyh: [(i64, i64, i64); n],
    }
    for cx in 0..101 {
        for cy in 0..101 {
            let mut ok = true;
            let mut h_ans = 1;
            for &(x, y, h) in &xyh {
                if h == 0 {
                    continue;
                }
                h_ans = (x - cx).abs() + (y - cy).abs() + h;
                break;
            }
            for &(x, y, h) in &xyh {
                if h != max(h_ans - (x - cx).abs() - (y - cy).abs(), 0)  {
                    ok = false;
                    break;
                }
            }
            //debug!(cx);
            //debug!(cy);
            //debug!(h_ans);
            if ok {
                println!("{} {} {}", cx, cy, h_ans);
                return;
            }
        }
    }
}

Measured memory_bytes: 4352
#include<stdio.h>
int main(){
       int a, b,c,cnt=0;
       scanf("%d %d %d",&a, &b, &c);
       for (int i = a; i <= b; ++i) {
       if (c%i == 0) ++cnt;
       }
       printf("%d\n", cnt); 
       return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <vector>

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

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

int main()
{
  int D, T, S;
  cin >> D >> T >> S;

  if ((D + S - 1) / S <= T)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


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

bool isPrime(int x){
    ll up = sqrt(x);
    for(ll i=2;i<up;i++){
        if(x % i == 0) return false;
    }
    return true;
}

int main(){
    ll x;
    cin >> x;
    while(true){
        if(isPrime(x)){
            cout << x << endl;
            break;
        }
        x++;
    }
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
llong a[100001];
llong b[100001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", a + i, b + i);
    }
    llong sum = 0;
    for (int i = n; i; --i) {
        a[i] += sum;
        llong val = (b[i] - a[i] % b[i]) % b[i];
        sum += val;
    }
    printf("%lld\n", sum);
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    unsigned n, p_total, j_total, max_salary;
    unsigned p[65000], j[64999];
    while (true) {
        p_total = j_total = max_salary = 0;
        cin >> n;
        if (n == 0) {
            return 0;
        }
        for (unsigned i = 0; i < n; ++i) {
            cin >> p[i];
            p_total += p[i];
        }
        for (unsigned i = 0; i < n - 1; ++i) {
            cin >> j[i];
            j_total += j[i];
        }
        sort(p, p + n);
        sort(j, j + n - 1);
        for (unsigned i = 1; i <= n; ++i) {
            unsigned s = (p_total + j_total) * i;
            max_salary = max(max_salary, s);
            if (i < n) {
                j_total -= j[i - 1];
            }
        }
        cout << max_salary << endl;
    }
}

Measured memory_bytes: 1676
import java.util.*

fun rangesum(n: Int, m: Int): Long {
    return n.toLong() * (n.toLong() + 1) / 2 - m.toLong() * (m.toLong() + 1) / 2
}

fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val n = cin.nextInt()
    val a = Array<Int>(n, { cin.nextInt() })
    var pluser = a[0]
    var xorer = a[0]
    var l = 0
    var r = 0
    var extending = true
    var r_checkpoint = -1
    
    var ans: Long = 0
    while (n > r) {
        if (extending) {
            if (r != n-1) {
                r += 1
                pluser += a[r]
                xorer = xorer xor a[r]
                if (pluser != xorer) {
                    extending = false
                    ans += rangesum(r - l, r_checkpoint - l)
                    r_checkpoint = r
                }
            } else {
                ans += rangesum(r - l + 1, r_checkpoint - l)
                break
            }
        } else {
            if (n == r-1) {
                break
            }
            pluser -= a[l]
            xorer = xorer xor a[l]
            l += 1
            if (pluser == xorer) {
                extending = true
            }
        }
    }
    println(ans)
}

Measured memory_bytes: 73836
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
	char str[1050];

	scanf("%s",str);

	char b;
        int i;
	for (i = 0; i < strlen(str); i++) {
		if(str[i]=='A'||str[i]=='B'||str[i]=='C'){
			b=str[i] + 23;
		}
		else b=str[i] - 3;
		printf("%c", b);
	}
        printf("\n");

	return 0;
}

Measured memory_bytes: 524
S=input()
key='keyence'
if S[:7] == key or S[-7:] == key:
    print('YES')
    exit()
for i in range(len(S)):
    if S[i] != key[i]:
        left = i
        break
for i in range(len(S)):
    if S[-i-1] != key[-i-1]:
        right = i
        break
print('YES' if left + right >= 7 else 'NO')
        


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
long long k,l,m;
long long co=1;

int main(){
	cin>>k;
	l=k%50;
	m=k/50;
	cout<<50<<endl;
	for(int i=0;i<l;i++){
		if(co!=50){
			cout<<49+m+50-(l-1)<<" ";
		}else{
			cout<<49+m+50-(l-1)<<endl;
		}
	}
	for(int i=0;i<50-l;i++){
		if(co!=50){
			cout<<49+m-(l)<<" ";
		}
		else {
			cout<<49+m+-(l)<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define PI (3.14159265358979323846)
#define INF (2147483647)
#define INF_LL (9223372036854775807)
#define DIV_NUM (1000000007)


int main() {

	int N, M;
	cin >> N >> M;

	int strict[4];
	fill(strict, strict + 4, -1);
	for (int i = 0; i < M; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		if (strict[tmp1] != -1 && strict[tmp1] != tmp2) {
			cout << "-1" << endl;
			return 0;
		}
		else if (tmp1 == 1 && tmp2 == 0 && N != 1) {
			cout << "-1" << endl;
			return 0;
		}else {
			strict[tmp1] = tmp2;
		}
	}

	int ans[4];
	for (int i = 1; i < N + 1; i++) {
		if (strict[i] != -1) {
			ans[i] = strict[i];
		}
		else {
			if (i == 1 && N != 1) ans[i] = 1;
			else ans[i] = 0;
		}
	}

	for (int i = 1; i < N + 1; i++) {
		cout << ans[i];
	}
	cout << endl;

	return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll pati[51]={};
ll saizu[51]={};
ll patinum(ll N,ll X){
	if(N==0) return 1;
	else if(X==1) return 0;
	else if(1<X&&X<saizu[N-1]+2){
		return patinum(N-1,X-1);
	}
	else if(X==saizu[N-1]+2){
		return pati[N-1]+1;
	}
	else if(saizu[N-1]+2<X&&X<saizu[N]){
		return patinum(N-1,X-(saizu[N-1]+2))+pati[N-1]+1;
	}
	else{
		return pati[N];
	}
}
int main(){
	ll N,X;
	scan(N);scan(X);
	saizu[0]=1;
	pati[0]=1;
	rep(i,N){
		pati[i+1]=pati[i]*2+1;
		saizu[i+1]=saizu[i]*2+3;
	}
	prin(patinum(N,X));
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

struct data{
  int x, y;
}map[100][100];

int keisan(int, int,int);
int hantei[100][100];
int n, ans;
main(){
  int i, j, ans;

  while(1){
    scanf("%d", &n);
    if(n==0) break;

    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	scanf("%d%d", &map[i][j].x, &map[i][j].y);
      }
    }
    
    ans=0;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	hantei[i][j]=0;
      }
    }

    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	if(hantei[i][j]==0){
	  ans=keisan(i,j, ans);
	}
      }
    }

     printf("%d\n", ans);
  }
  return 0;
}

int keisan(int y, int x, int ans){
  int i, j, tx, ty, f=0, a, b;
  int hantei2[100][100];
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      hantei2[i][j]=0;
    }
  }
  while(1){
    if(y==0 && x==3){
    }
    if(hantei[y][x]==1 && hantei2[y][x]==1){
      f=1;
      hantei[y][x]=2;
    }
    else if(hantei[y][x]==1 && hantei2[y][x]==0){
      f=0;
      break;
    }
    else if(hantei[y][x]==2){ 
      break;
    }
    else{
      if(y==0 && x==3){
    }
      hantei[y][x]=1;
      hantei2[y][x]=1;
    }
    tx = map[y][x].x;
    ty = map[y][x].y;      
    x=tx;
    y=ty;
  }
  if(f){
    ans++;
  }
  return ans;
}

Measured memory_bytes: 564
#include <iostream>

using namespace std;
const int maxSize = 1e5 + 10;

class UnionFind {
public:
    UnionFind(int max) {
        for (int i = 0; i <= max; ++i) {
            roots[i] = i;
            rank[i] = 0;
            count[i] = 1;
        }
    }

    int find(int x) {
        int p = roots[x];
        while (p != roots[p]) {
            roots[p] = roots[roots[p]];
            p = roots[p];
        }

        return p;
    }

    void uni(int p, int q) {
        p = find(p);
        q = find(q);

        if (p == q) {
            return;
        }

        if (rank[p] < rank[q]) {
            roots[p] = q;
            count[q] += count[p];
            count[p] = 1;
        } else {
            roots[q] = p;
            count[p] += count[q];
            count[q] = 1;
            if (rank[p] == rank[q]) {
                rank[p]++;
            }
        }
    }

    int size(int p) {
        return count[find(p)];
    }

    bool isConnected(int p, int q) {
        return find(p) == find(q);
    }

private:
    int roots[maxSize];
    int rank[maxSize];
    int count[maxSize];
};

pair<int, int> fs[maxSize];
pair<int, int> bs[maxSize];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    UnionFind uf(n + 1);
    int bsCount[maxSize];
    int fsCount[maxSize];

    for (int i = 1; i <= m; ++i) {
        cin >> fs[i].first >> fs[i].second;
        uf.uni(fs[i].first, fs[i].second);
        fsCount[fs[i].first]++;
        fsCount[fs[i].second]++;
    }

    for (int i = 1; i <= k; ++i) {
        cin >> bs[i].first >> bs[i].second;
        if (uf.isConnected(bs[i].first, bs[i].second)) {
            bsCount[bs[i].first]++;
            bsCount[bs[i].second]++;
        }
    }

    for (int j = 1; j <= n; ++j) {
        cout << max(0, uf.size(j) - (fsCount[j] + bsCount[j]) - 1) << " ";
    }
}


Measured memory_bytes: 4352
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
#include <set>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  std::string S;
  std::cin >> S;

  // Main
  std::set<char> mp;
  for (int i = 0; i < 4; ++i) {
    mp.insert(S[i]);
  }

  std::string res;
  if (mp.size() == 2)
    res = "Yes";
  else
    res = "No";

  // Output
  std::cout << res << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;


vector<string> split(const string &s, char delim) {
    vector<string> elems;
    string item;
    for (char ch: s) {
        if (ch == delim) {
            if (!item.empty())
                elems.push_back(item);
            item.clear();
        }
        else {
            item += ch;
        }
    }
    if (!item.empty())
        elems.push_back(item);
    return elems;
}

bool compare_by_b(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<2>(a) != get<2>(b)){
        return get<2>(a) > get<2>(b);
    }
}

bool compare_by_string(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<1>(a) != get<1>(b)){
        return get<1>(a) < get<1>(b);
    }else{
      	return get<2>(a) > get<2>(b);
    }
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
  	cin >> n;
  	vector<long> S;
  	int idx=0;
  	long s;
  	while(cin >> s)
    {
      S.push_back(s);
      idx++;
      if(idx == n) break;
    }
  	int q;
  	cin >> q;
  	vector<long> T(q);
  	idx=0;
  	while(cin >> T[idx])
    {
      idx++;
      if(idx == q) break;
    }
  	
  	int count = 0;
  	for(int i=0;i<q;i++)
    {
      	int left = 0;
      	int right = S.size();
      	while(left < right)
        {
          int mid = (left + right) / 2;
      	  if(T[i] == S[mid])
          {
            count++;
          	break;
          }
      	  else if(T[i] < S[mid])
            right = mid;
      	  else
            left = mid+1;
        }
    }
  	cout << count << endl;
  	return 0;
}



Measured memory_bytes: 4208
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
int e[1048576],o[1048576];
int main(void)
{
  REP(i,1048576) e[i]=1048576;
  REP(i,1048576) o[i]=1048576;
  e[0]=0;
  o[0]=0;
  REP(i,1024){
    int gap=i*(i+1)*(i+2)/6;
    for(int j=0;j+gap<1048576;++j) e[j+gap]=min(e[j+gap],e[j]+1);
    if(gap%2==1) for(int j=0;j+gap<1048576;++j) o[j+gap]=min(o[j+gap],o[j]+1);
  }    
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    cout << e[n] << ' ' << o[n] << endl;
  }
}

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

int main() {
    int N; cin >> N;
    vector<int> A(N), B(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) B[i] = A[i];
    sort(B.begin(), B.end(), greater<int>());
    rep(i, 0, N) {
        if(A[i] == B[0]) cout << B[1] << '\n';
        else cout << B[0] << '\n';
    }
    return 0;
}


Measured memory_bytes: 3200
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct Node {
	Node *l = 0, *r = 0;
	int val, y;
	int first, max;
	bool monotone;
	Node(int val) : val(val), y(rand()) {
		first = max = val;
		monotone = 1;
	}
	void reset() {
		first = max = val;
		monotone = 1;
	}
	void recalc();
	void recalc3();
};

inline void Node::recalc() {
	first = l ? l->first : val;
	int max = val;
	bool mon = 1;
	if (l) {
		max = std::max(max, l->max);
		if (!l->monotone || l->max > val) mon = 0;
	}
	if (r) {
		max = std::max(max, r->max);
		if (mon && (!r->monotone || r->first < val)) mon = 0;
	}
	this->max = max;
	monotone = mon;
}

inline void Node::recalc3() {
	first = l ? l->first : val;
	int max = val;
	if (l) {
		max = std::max(max, l->max);
	}
	if (r) {
		max = std::max(max, r->max);
	}
	this->max = max;
	monotone = 1;
}

Node* merge2(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge2(l->r, r) : r;
		l->recalc();
		return l;
	} else {
		r->l = r->l ? merge2(l, r->l) : l;
		r->recalc();
		return r;
	}
}

inline Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge2(l, r);
}

Node* merge32(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge32(l->r, r) : r;
		l->recalc3();
		return l;
	} else {
		r->l = r->l ? merge32(l, r->l) : l;
		r->recalc3();
		return r;
	}
}

inline Node* merge3(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge32(l, r);
}

pair<Node*, Node*> split2(Node* n, int lo) {
	if (!n) return {0, 0};
	if (n->max < lo) return {0, n};
	if (n->monotone) {
		if (lo < n->first) return {n, 0};
		if (!n->l) {
			if (!n->r) return {0, n};
			assert(lo >= n->val);
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->reset();
			pa.second = merge(n, pa.second);
			return pa;
		}

		if (lo < n->val) {
			auto pa = split2(n->l, lo);
			n->l = 0;
			n->recalc();
			pa.first = merge3(pa.first, n);
			return pa;
		}
		else {
			// if (!n->r) return {0, n};
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->recalc();
			pa.second = merge(n, pa.second);
			return pa;
		}
	}

	Node *left = n->l, *right = n->r;
	n->l = n->r = 0;
	n->recalc();
	auto pa = split2(left, lo);
	if (pa.first) lo = pa.first->max;
	if (n->val > lo) {
		pa.first = merge3(pa.first, n);
		lo = n->val;
	}
	else {
		pa.second = merge(pa.second, n);
	}
	auto pa2 = split2(right, lo);
	return {merge3(pa.first, pa2.first), merge(pa.second, pa2.second)};
}

int main() {
	srand(2);
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N;
	vector<Node> nodes;
	rep(i,0,N) {
		int p;
		cin >> p;
		nodes.emplace_back(p);
	}

	Node* t = 0;
	rep(i,0,N)
		t = merge(t, &nodes[i]);

	int res = 0;
	while (!t->monotone) {
		++res;
		auto pa = split2(t, 0);
		t = merge(pa.second, pa.first);
	}

	cout << res << endl;
	exit(0);
}


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


#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))
#define  nl "\n";

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



template <class T> inline T biton(T n, T pos)
{
	return n | ((T)1 << pos);
}
template <class T> inline T bitoff(T n, T pos)
{
	return n & ~((T)1 << pos);
}
template <class T> inline T ison(T n, T pos)
{
	return (bool)(n & ((T)1 << pos));
}
template <class T> inline T gcd(T a, T b)
{
	while (b)
	{
		a = a % b;
		swap(a, b);
	}
	return a;
}
template <class T> inline T bigmod(T p, T e, T m)
{
	T ret = 1;
	for (; e > 0; e >>= 1)
	{
		if (e & 1)
			ret = (ret * p) % m;
		p = (p * p) % m;
	}
	return (T)ret;
};



#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1)
{
	cerr << name << " is " << arg1 << std::endl;
}
template < typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " is " << arg1 << " | ";
	__f(comma + 1, args...);
}
#else
#define debug(...)
#endif


long long area(vector<pair<long long, long long>> items) {

	long long sum = 0;

	for (int i = 0; i < (int)items.size(); i++) {
		auto n1 = items[i];
		auto n2 = items[(i + 1) % (int)items.size()];
		sum += n1.first * n2.second - n1.second * n2.first;
	}

	return sum;
}


void solve()
{
	int a, b, c;
	cin >> a >> b >> c;
	swap(a, b);
	swap(a, c);

	cout << a << " " << b << " " << c << nl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(10);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int t = 1;

	while (t--)
	{
		solve();
	}

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int k,cnt = 0;
  cin >> k;
  for(int i=1; i <= k; i++){
    for(int j=i+1; j <= k; j+=2){
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
/*
      author  : nishi5451
      created : 15.08.2020 01:07:40
*/

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


int main(){
    int n;
    cin >> n;
    vector<tuple<string,int,int>> a;
    for(int i=1; i<=n; i++){
        string s;
        int p;
        cin >> s >> p;
        p = -p;
        a.push_back(tie(s,p,i));
    }
    sort(a.begin(),a.end());
    for(int i=0; i<n; i++){
        cout << get<2>(a[i]) << endl;
    }
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main()
{
    int x;
    cin >> x;
    if(x >= 1800) cout << 1 << endl;
    else if(x >= 1600) cout << 2 << endl;
    else if(x >= 1400) cout << 3 << endl;
    else if(x >= 1200) cout << 4 << endl;
    else if(x >= 1000) cout << 5 << endl;
    else if(x >= 800) cout << 6 << endl;
    else if(x >= 600) cout << 7 << endl;
    else if(x >= 400) cout << 8 << endl;
}


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

namespace AGC015_A {
    class Program {
        static void Main(string[] args) {
            var s = Console.ReadLine().Split();
            var n = long.Parse(s[0]);
            var a = long.Parse(s[1]);
            var b = long.Parse(s[2]);
            if (a > b) {
                Console.WriteLine(0);
                return;
            }else if (n == 1) {
                if (a == b) {
                    Console.WriteLine(1);
                } else {
                    Console.WriteLine(0);
                }
                return;
            } else {
                Console.WriteLine(((n - 2) * (b - a) + 1));
                return;
            }
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll k, t;
  cin >> k >> t;
  
  vector<ll> a(t);
  for (int i = 0; i < t; i++){
    cin >> a[i];
  }
  
  sort(a.begin(), a.end());
  
  ll s = 0;
  for (int i = 0; i < t - 1; i++){
    s += a[i];
  }

  cout << max(0LL, a[t-1] - s - 1) << endl;
  

  return 0;
}


Measured memory_bytes: 256
N=int(input())
a=list(map(int,input().split()))
ans=10000000000000000000
c=0
s=sum(a)
for i in range(N-1):
    c+=a[i]
    s-=a[i]
    if abs(c-s)<ans:
        ans=abs(c-s)
print(ans)


Measured memory_bytes: 30680
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		while (sc.hasNext()) {
			int V = sc.nextInt();
			int d = sc.nextInt();
			int N = 1001;
			boolean[] has = new boolean[N];
			int cur = 2;
			int prev = 1;
			for (int i = 0; i < V; ++i) {
				has[cur] = true;
				int tmp = cur;
				cur = (cur + prev) % N;
				prev = tmp;
			}
			int ans = 0;
			int back = -10000;
			for (int i = 0; i < N; ++i) {
				if (!has[i]) continue;
				if (i - back >= d) ++ans;
				back = i;
			}
			System.out.println(ans);
		}
	}

}

Measured memory_bytes: 12000
r, c = gets.split.map(&:to_i)
sums = Array.new(c + 1, 0)
r.times do
  line = gets.split.map(&:to_i)
  line << line.inject(:+)
  sums = sums.zip(line).map{ |a, b| a + b }
  puts "#{line.join(" ")}"
end
puts sums.join(" ")

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

int main ()
{
    int n, k;
    cin >> n >> k;
    int ans;
    if (k == 1)
    {
        ans = 0;
    }
    else
    {
        ans = n - k;
    }
    
    cout << ans << endl;
    return 0;
}

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

namespace AtCoder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			int H = vs[0];
			int W = vs[1];

			cell[][] map = new cell[H][];
			for (int y = 0; y < H; y++) {
				map[y] = new cell[W];
				string str = Console.ReadLine();
				for (int x = 0; x < W; x++) {
					map[y][x] = new cell() { Mark = str[x] };
					if (map[y][x].Mark == '.') {
						map[y][x].xCount++;
						map[y][x].yCount++;
						if (x > 0 && map[y][x - 1].Mark == '.') {
							map[y][x].xCount += map[y][x - 1].xCount;
						}
						if (y > 0 && map[y - 1][x].Mark == '.') {
							map[y][x].yCount += map[y - 1][x].yCount;
						}
					}
				}
			}
			int ans = 0;
			for (int y = H - 1; y >= 0; y--) {
				for (int x = W - 1; x >= 0; x--) {
					if (map[y][x].Mark == '.') {
						ans = Math.Max(ans, map[y][x].Count);
						if (x > 0 && map[y][x - 1].Mark == '.') {
							map[y][x - 1].xCount = map[y][x].xCount;
						}
						if (y > 0 && map[y - 1][x].Mark == '.') {
							map[y - 1][x].yCount = map[y][x].yCount;
						}
					}
				}
			}
			Console.WriteLine(ans - 1);
		}
	}

	public class cell
	{
		public char Mark;
		public int xCount = 0;
		public int yCount = 0;
		public int Count { get { return xCount + yCount; } }
	}
}


Measured memory_bytes: 177196
import java.util.Scanner;

public class Main {

	static long bignum = 1000000000+7;

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int[] ans = new int[10001];
		for(int i =0;i<ans.length;i++) {
			ans[i]=0;
		}

		for(int i =1;i<100;i++) {
			for(int j=1;j<100;j++) {
				for(int k=1;k<100;k++) {
					int target = i*i+j*j+k*k+i*j+j*k+k*i;
					if(target<10001)ans[target]++;
				}
			}
		}

		for(int i =1;i<n+1;i++) {
			System.out.println(ans[i]);
		}
	}

	static long yuclid(long a, long b) {
		long ans;
		if(a<b) {
			long aa = a;
			a=b;
			b=aa;
		}
		while(true) {
			if(b%a==0) {
				ans = a;
				break;
			}else {
				long aa =a;
				a= b%a;
				b=aa;
			}
		}
		return ans;
	}


	static long divn(int target, int times) {//10_9+7のあまり累乗版
		int sqtimes = (int)Math.sqrt(times);
		long ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans * target)%(bignum);
		}
		long holder = ans;
		ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans*holder)%(bignum);
		}
		for(int i=0;i<times - sqtimes*sqtimes;i++) {
			ans = (ans * target)%(bignum);
		}
		return ans;
	}

	static long div(long a) {//10_9+7のあまり
		if(a<0)a+=bignum;
		return a%(bignum);
	}

}
/*
class City{
	int order;
	int prefecture;
	int year;
	int number;
	City(int order,int prefecture, int year){
		this.order = order;
		this.prefecture = prefecture;
		this.year = year;
	}
}
*/


Measured memory_bytes: 38776
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1e9 + 7;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    vector<string> v(h);
    rep(i, 0, h) cin >> v[i];
    cout << string(w + 2, '#') << endl;
    ;
    rep(i, 0, h) cout << "#" << v[i] << "#" << endl;
    cout << string(w + 2, '#') << endl;
    return 0;
}

Measured memory_bytes: 892
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
if n%2 == 0:
    print(n//2 - 1)
else:
    print((n+1)//2 - 1)


Measured memory_bytes: 10400
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <cfloat>
using namespace std;

#define FOR(i, j, k) for(int i=j ; i<k ; i++)
#define REP(i, j) FOR(i, 0, j)
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

ll s(ll n) {
    ll res = 0;
    while (n > 0) {
        res += n % 10;
        n /= 10;
    }
    return res;
}

long double snuke(ll n) {
    return n / (long double)s(n);
}

int main() {

    ll k; cin >> k;
    ll K = 100000000000000000LL;
    int digit = to_string(K).length();
    int top = atoi(to_string(K).substr(0, 4).c_str());

    // cout << K << endl;
    // cout << top << " " << digit << endl;
    
    vll res;

    double s = LDBL_MAX;

    while (digit > 6) {

        while (top >= 1000) {

            std::ostringstream oss;
            oss << std::setw(digit) << std::setfill('9') << std::left << to_string(top);

            ll a = atol(oss.str().c_str());
            // cout << top << " " << digit << " " << a << endl;

            long double _s = snuke(a);
            // cout << a << " " << _s << endl;
            if (_s <= s) {
                s = _s;
                res.push_back(a);
            }
            top--;
        }

        top = 9999;
        digit--;
    }

    for (int i = 999999LL; i > 0; i--) {
        long double a = snuke(i);
        if (a <= s) {
            s = a;
            res.push_back(i);
        }
    }

    sort(res.begin(), res.end());

    REP(i, k) cout << res[i] << endl;

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;

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

double dp[3005][3005];

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

  double p[n];
  rep(i, n) cin >> p[i];

  dp[0][0] = 1;

  rep(i, n) {
    rep(j, n) {
      dp[i + 1][j] += dp[i][j] * (1 - p[i]);
      dp[i + 1][j + 1] += dp[i][j] * p[i];
    }
  }

  double ans = 0;
  for (int i = (n + 1) / 2; i <= n; ++i) { ans += dp[n][i]; }

  printf("%.10f\n", ans);
  return 0;
}


Measured memory_bytes: 70656
#include<bits/stdc++.h>
int a[30], t;
char s[5];
bool ok = true;
int main(){
	scanf("%s", s);
	for(int i = 0; i < 4; i++) a[s[i]-'A']++;
	for(int i = 0; i < 27; i++){
		if(a[i] == 1 || a[i] == 4 || a[i] == 3) ok = false;
	}
	puts(ok ? "Yes" : "No");
}

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

using namespace std;

int main(int argc, char *argv[])
{

  int a = 0, v = 0;
  cin >> a;
  for (int i = 6; i >= 0; i--) {
    if (((a >> i) & 1) == 1) {
      printf("%d\n", 1 << i);
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
count = 0
for i in range(n):
    sum = 0
    for j in range(m):
        sum += a[i][j]*b[j]
    sum += c
    if sum > 0:
        count += 1
print(count)


Measured memory_bytes: 38384
#include <iostream>

using namespace std;

int main(){
  int n = 50;
  long long a[50];
  int r;
  long long k, m;
  cin >> k;
  for (int i=0;i<n;i++) {
    a[i] = i;
  }
  m = k / n + 1;
  for (int i=0;i<n;i++) {
    a[i] += m;
  }
  r = n*m - k;
  for (int h=0;h<r;h++) {
    int max_index;
    long long max_a = -1;
    for (int i=0;i<n;i++) {
      if (a[i] > max_a) {
	max_a = a[i];
	max_index = i;
      }
      a[i]++;
    }
    a[max_index]--;
    a[max_index] -= n;
  }
  cout << n << endl;
  for (int i=0;i<(n-1);i++) {
    cout << a[i] << " ";
  }
  cout << a[n-1] << endl;
  return(0);
}


Measured memory_bytes: 256
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)


h, w = map(int, input().split())
f(h, w)


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


void dfs(int digit,long sum,vector<long> &A)
{
  A.push_back(sum);
  if(digit==10)
    return;
  
  for(int j=-1;j<=1;j++)
  {
    int number_add=sum%10+j;
    if(number_add>=0&&number_add<=9)
      dfs(digit+1,sum*10+number_add,A);
  }
}

int main()
{
  int k;
  cin>>k;
  vector<long> A;
  for(int i=1;i<10;i++)
    dfs(1,i,A);
  sort(A.begin(),A.end());
  cout<<A[k-1]<<endl;
}

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
  #include "dbgtoki.hpp"
  #define DUMP(i) DEB dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i)  
#else
  #define DUMP(i)  
#endif

#define GETTYPE(i) 
#define TOSTRING(x) #x
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a):i<(b);i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

int main (){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b;
  while(cin >> a >> b){
    cout << (a + b)/2 << endl;
  }
  return 0;
}



Measured memory_bytes: 3220
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    r1,c1,r2,c2 = LI()
    N = 3*10**6
    f = [1]
    for i in range(N):
        f.append(f[-1]*(i+1)%mod)
    inv = [None]*(N+1)
    inv[-1] = pow(f[-1],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = 0
    for i in range(r1,r2+1):
        s = 0
        ans += comb(i+1+c2,i+1)-comb(i+c1,i+1)
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 124940
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] list = new int[n - 1];
    int[] results = new int[n];

    for (int i = 0; i < list.length; i++) {
      list[i] = sc.nextInt();
    }
    for (int i = 1; i < results.length; i++) {
      results[i] = 0;
    }

    for (int i = 0; i < list.length; i++) {
      results[(list[i]) - 1]++;
    }
    for (int i = 0; i < results.length; i++) {
      System.out.println(results[i]);
    }
    sc.close();
  }
}

Measured memory_bytes: 62700
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

#define NUM 2147483647

int N = 1;
int* data;

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right){
	if(update_right < node_left || update_left > node_right)return;
	else if(update_left <= node_left && update_right >= node_right){
		data[node_id] = new_value;
	}else{
		if(data[node_id] >= 0){
			data[2*node_id+1] = data[node_id];
			data[2*node_id+2] = data[node_id];
			data[node_id] = -1;
		}
		update(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2);
		update(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right);
	}
}

int query(int search_left,int search_right,int node_id,int node_left,int node_right){
	if(search_right < node_left || search_left > node_right){
		return -1;
	}else if(node_left <= search_left && node_right >= search_right && data[node_id] >= 0){
		return data[node_id];
	}else{
		int left = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
		int right = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);
		return max(left,right);
	}
}

int main(){
	int first_N,Q;
	scanf("%d %d",&first_N,&Q);

	init(first_N);

	data = new int[270000];

	for(int i = 0; i <= 2*N-2; i++)data[i] = NUM;

	int command,left,right,value,loc;

	for(int i = 0; i < Q; i++){
		scanf("%d",&command);

		if(command == 0){
			scanf("%d %d %d",&left,&right,&value);
			update(left,right,value,0,0,N-1);
		}else{
			scanf("%d",&loc);
			printf("%d\n",query(loc,loc,0,0,N-1));
		}
	}
}

Measured memory_bytes: 3780
#include<iostream>
#include<math.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<long> a(n+1,0);
	a[0]=2;
	if(n==0){
		cout << "2" << endl;
		return 0;
	}
	if(n==1){
		cout << "1" << endl;
		return 0;
	}
	a[1]=1;
	if(n>=2){
		for(int i=2;i<=n;i++){
			a[i]=a[i-1]+a[i-2];
		}
	}
	long ans=a[n];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<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 rrep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define Size(x) ((int)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo,gyakugen
//mint,dijkstra
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll n,s;
        cin>>n>>s;
        vl A(n);
        rep(i,n)cin>>A[i];
        const ll MOD=998244353;
        vvl DP(n+1,vl(s+1,0));//DP[何番目まで][合計]
        //操作前から0は出来ている
        DP[0][0]=1;
        rep(i,n){
            rep(j,s+1){
                //選んでも選ばないでも使わなければいい
                //i番目まででjを作れる集合にi+1番目を追加するorしないの2通りができる
                DP[i+1][j]+=DP[i][j]*2;
                DP[i+1][j]%=MOD;
                if(j+A[i]<=s){
                    //選ぶ場合
                    //1つ前まででjを作れた集合全てからj+A[i]が作れる
                    DP[i+1][j+A[i]]+=DP[i][j];
                    DP[i+1][j+A[i]]%=MOD;
                }
            }
        }
        //n番目まで選んでsを作れる集合の数
        cout<<DP[n][s]<<endl;
    }

Measured memory_bytes: 73604
from collections import *
h, w, m = map(int, input().split())
mh = [0 for _ in range(h)]
mw = [0 for _ in range(w)]

z = []
for _ in range(m):
    x, y = map(int, input().split())
    z.append((x-1, y-1))
    mh[x-1] += 1
    mw[y-1] += 1

hc = Counter(mh)
wc= Counter(mw)
hm = max(mh)
wm= max(mw)

ans = hm + wm
tmp = 0
for x, y in z:
    if mh[x] + mw[y] == ans:
        tmp += 1

if tmp == hc[hm] * wc[wm]:
    print(ans - 1)
else:
    print(ans)


Measured memory_bytes: 117496
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=N*20;
int n,a[N][2],id[M],cnt;
int vis[M],dfn[M],scc[M],low[M],idx,co; stack<int> s;
vector<int> g[M]; vector<pair<int,int> > v;
#define mid (l+r>>1)
void build(int p,int l,int r){
	if(l==r){id[p]=v[l-1].second; return ;}
	id[p]=++cnt;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	g[id[p]].push_back(id[p<<1]),g[id[p]].push_back(id[p<<1|1]);
}
void link(int p,int l,int r,int ql,int qr,int v){
	if(l==ql&&r==qr){g[v].push_back(id[p]); return ;}
	if(qr<=mid) link(p<<1,l,mid,ql,qr,v);
	else if(ql>mid) link(p<<1|1,mid+1,r,ql,qr,v);
	else link(p<<1,l,mid,ql,mid,v),link(p<<1|1,mid+1,r,mid+1,qr,v);
}
#undef mid
void Tarjan(int x){
	dfn[x]=low[x]=++idx; vis[x]=1; s.push(x);
	for(int to:g[x]){
		if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);
		else if(vis[to]) low[x]=min(low[x],dfn[to]);
	}
	if(dfn[x]==low[x]){
		int u; co++;
		do{
			u=s.top(); s.pop(); vis[u]=0; scc[u]=co;
		}while(u!=x);
	}
}
inline int check(int mid){
	cnt=2*n; build(1,1,2*n);
	for(int i=1;i<=n;i++) for(int j=0;j<2;j++){
		int l=lower_bound(v.begin(),v.end(),make_pair(a[i][j]-mid+1,0))-v.begin()+1;
		int r=upper_bound(v.begin(),v.end(),make_pair(a[i][j]+mid,0))-v.begin();
		int m=lower_bound(v.begin(),v.end(),make_pair(a[i][j],i+(j^1)*n))-v.begin()+1;
		if(l<m)	link(1,1,2*n,l,m-1,i+j*n);
		if(m<r) link(1,1,2*n,m+1,r,i+j*n);
	}
	while(s.size())	s.pop();
	for(int i=1;i<=cnt;i++) dfn[i]=low[i]=scc[i]=0; idx=co=0;
	for(int i=1;i<=cnt;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=cnt;i++) g[i].clear();
	for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) return 0;
	return 1;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1];
	for(int i=1;i<=n;i++) v.push_back({a[i][0],i+n}),v.push_back({a[i][1],i});
	sort(v.begin(),v.end());
	int l=0,r=1e9;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}


Measured memory_bytes: 60136
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>

int main(int argc, char *argv[]){
    std::string S;
    std::cin >> S;
    int N = S.size();
    int HW = 0;
    for(const auto &s :S){
        HW += s - '0';
    }
    std::cout << 2*std::min(HW,N-HW) << std::endl;
    return 0;
}


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

#define int long long int
#define ff first
#define ss second
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod = 1e9 + 7;
const int cmod = 998244353;
const int N = 2e5 + 5;
const int inf = 1e16 + 2;

void solve(int ze) {
    int n , k ;
    cin >> n >> k;
    int arr[n];
    for(int i = 0 ; i < n ; i ++) cin >> arr[i];
    sort(arr , arr + n);
    int ans = 0;
    for(int i = 0 ; i < k ; i ++) ans += arr[i];
    cout << ans << '\n'
    ;}
/*
 */

int32_t main()
{
    fastio
    int testcase = 1;
    //cin >> testcase;
    int x = 1;
    while(testcase --) {
        solve(x ++);
    }
    return 0;
}
 



Measured memory_bytes: 3636