akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>

using namespace std;
typedef long long int ll;

ll n,hab[200],m,a,r,c,h;

string ss;

int main(){
    scanf("%lld",&n);
    for(int i=0;i<200;i++)hab[i]=0;
    for(int i=0;i<n;i++){
        cin>>ss;
        hab[int(ss[0])]++;
    }
    m=hab[int('M')];
    a=hab[int('A')];
    r=hab[int('R')];
    c=hab[int('C')];
    h=hab[int('H')];
    printf("%lld\n",m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h);
    
}

Measured memory_bytes: 256
# ABC066C - pushpush (ARC077)
def main():
    N, *A = open(0).read().split()
    if int(N) & 1:
        B = A[::2][::-1] + A[1::2]
    else:
        B = A[1::2][::-1] + A[::2]
    print(" ".join(B))


if __name__ == "__main__":
    main()

Measured memory_bytes: 26076
#[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)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $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, usize1) => {
        read_value!($next, usize) - 1
    };

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      ds: [usize; n],
    }

    let mut ans = 0;
    for i in 0..n {
        for j in i+1..n {
            ans += ds[i] * ds[j];
        }
    }
    puts!("{}\n", ans);
}


Measured memory_bytes: 4352
#include<iostream>
using namespace std;
  
int Merge(int A[],int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int i,j,k;
  int L[n1+1],R[n2+1];
    
  for(i=0;i<n1;i++)L[i]=A[left+i];
  for(i=0;i<n2;i++)R[i]=A[mid+i];
  L[n1]=1000000000;
  R[n2]=1000000000;
    
  i=j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
  }
  return right-left;
}
  
int Merge_Sort(int A[],int left,int right){
  int mid,res=0;
  if(left+1<right){
    mid=(left+right)/2;
  
    res+=Merge_Sort(A,left,mid);
    res+=Merge_Sort(A,mid,right);
    res+=Merge(A,left,mid,right);
      
  }
  return res;
}
  
int main(){
  int i,x,n,S[500000]; 
  cin>>n;
  for(i=0;i<n;i++)cin>>S[i];
  
  x=Merge_Sort(S,0,n);
    
  for(i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<S[i];
  }
  cout<<endl;
  cout<<x<<endl;
  return 0;
}

Measured memory_bytes: 6912
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
template <typename T>
void ce(initializer_list<T> v){for(T i : v) cerr << i << ' '; cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

ll cnt[500][500];

int main(void){
	string s;
	cin >> s;
	ll n = s.size();
	ll ans = 0;
	ll cntA = 0, cntB = 0, p = 1;
	rep(i, n){
		if(s[i] == 'A'){
			cntA += p;
			cntA %= MOD;
		}else if(s[i] == 'B'){
			cntB += cntA;
			cntB %= MOD;
		}else if(s[i] == 'C'){
			ans += cntB;
			ans %= MOD;
		}else{
			ans *= 3;
			ans += cntB;
			ans %= MOD;
			cntB *= 3;
			cntB += cntA;
			cntB %= MOD;
			cntA *= 3;
			cntA += p;
			cntA %= MOD;
			p *= 3;
			p %= MOD;
		}
		//co({cntA, cntB, ans});
	}
	co(ans);

	return 0;
}


Measured memory_bytes: 512
use proconio::input;

fn main() {
    input! {
        ss: [String],
    }

    let (mut ac, mut wa, mut tle, mut re) = (0, 0, 0, 0);

    for s in ss {
        match &*s {
            "AC" => ac += 1,
            "WA" => wa += 1,
            "TLE" => tle += 1,
            "RE" => re += 1,
            _ => unreachable!(),
        }
    }

    println!("AC x {}", ac);
    println!("WA x {}", wa);
    println!("TLE x {}", tle);
    println!("RE x {}", re);
}


Measured memory_bytes: 7800
abc = list(map(int, input().split()))
abc.sort()
a = 0
a += abc[2] - abc[1]
if (abc[1] - abc[0]) % 2 == 0:
    a += (abc[1] - abc[0]) // 2
else:
    a += (abc[1] - abc[0]) // 2 + 2
print(a)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define Sort(vec) sort(vec.begin(),vec.end())
#define tr1(i) cout<<i<<endl;
#define tr2(i,j) cout<<i<<" "<<j<<endl;
#define tr3(i,j,k) cout<<i<<" "<<j<<" "<<k<<endl;
#define all(st) st.begin(),st.end()
#define vpll vector<pair<lli,lli>>
#define vpii vector<pair<int,int>>
#define al vector<list<int>>
#define vs vector<string>
#define vi vector<int>
#define vb vector<bool>
#define vl vector<lli>
#define vc vector<char>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repit(st) for(auto it=st.begin();it!=st.end();it++)
#define ulli unsigned long long int
#define pb push_back
#define lli long long int
#define inf INT_MAX
#define minf INT_MIN
#define f first
#define se second
#define mod 1000000007
#define mx 200001
using namespace std;
void add_me(lli &a,lli b){
    a+=b;
    if(a>=mod) a-=mod;
}   
void sub_me(lli &a,lli b){
    a-=b;
    if(a<0) a+=mod;
}
struct disjointset{
    int parent[mx];
   	disjointset(){
        for(int i=1;i<mx;i++) parent[i]=i;
    }
    int find(int x){
      	int par=parent[x];
        if(par==x) return x;
        return find(parent[x]);
    }
    void union_(int x,int y){
   	    int par1=find(x);
     	int par2=find(y);
       	if(par1==par2) return;
       	parent[par2]=par1;
    }
};
lli mi(lli n,lli m){
	lli pw=n;
	lli ex=m-2;
	lli ans=1;
	while(ex){
		if(ex&1) ans = ans*pw%m;
		pw = pw*pw%m;
		ex>>=1;
	}
	return ans;
}
int main(){
	FIO;
	int n,k;cin>>n>>k;
	int r,s,p;cin>>r>>s>>p;
	string str;cin>>str;
	vc vec;
	rep(i,0,n){
		if(str[i]=='r'){
			if(i>=k && vec[i-k]=='p') vec.pb('a');
			else vec.pb('p');
		}
		else if(str[i]=='p'){
			if(i>=k && vec[i-k]=='s') vec.pb('a');
			else vec.pb('s');
		}
		else{
			if(i>=k && vec[i-k]=='r') vec.pb('a');
			else vec.pb('r');
		}
	}
	lli sc=0;
	rep(i,0,n){
		//cout<<vec[i];
		if(vec[i]=='r') sc+=r;
		else if(vec[i]=='p') sc+=p;
		else if(vec[i]=='s') sc+=s;
	}
	cout<<sc<<endl;
	
	
}

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

int main(){
    int n;
    cin >> n;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    for ( int i = n - 2; i >= 0; --i ) {
        if ( h[i+1] >= h[i] ) {
            continue;
        }
        if ( h[i+1] == h[i] - 1  ) {
            --h[i];
        }
        else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int rev(int x)
{
    int temp = 0;
    while(x) {
        (temp *= 10) += x %10;
        x /= 10;
    }
    return temp;
}

int main()
{
    int a, b, cnt = 0; cin >> a >> b;
    for( ; a <= b; a++) {
        if(a == rev(a)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


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

int N,M,X,Y,x[105],y[105];
int main(){
  std::cin>>N>>M>>X>>Y;
  for(int i=0;i<N;++i)
    std::cin>>x[i];
  for(int i=0;i<M;++i)
    std::cin>>y[i];
  
  bool check1,check2;
  for(int z=X+1;z<=Y;++z){
    check1=check2=true;
    for(int i=0;i<N;++i)
      if(x[i]>=z){
        check1=false;
        break;
      }
    for(int i=0;i<M;++i)
      if(y[i]<z){
        check1=false;
        break;
      }
    if(check1&&check2){
      std::cout<<"No War"<<std::endl;
      return 0;
    }
  }
  std::cout<<"War"<<std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(){
    string s,t; cin >> s >> t;
    map<char, char> mp, mp2;
    bool check = true;
    for(int i = 0; i < s.size(); i++){
        if(mp.count(s[i])){
            if(mp[s[i]] != t[i])check = false;
        }
        if(mp2.count(t[i])){
            if(mp2[t[i]] != s[i])check = false;
        }
        mp[s[i]] = t[i];
        mp2[t[i]] = s[i];
    }
    // string a;
    // for(int i = 0; i < s.size(); i++){
    //     //cout << s[i] << "->" << mp[s[i]] << endl;
    //     a.push_back(mp[s[i]]);
    // }
    // cout << a << endl;
    // cout << ((t == a) ? "Yes" : "No") << endl;
    cout << ((check)? "Yes":"No") << endl;
}

Measured memory_bytes: 776
import math
n,p=map(int,input().split())
c=0
for m in map(int,input().split()):
  if m%2==0:c+=1
d=2**(c)

e=0
for i in range(p,n-c+1,2):
  
  k=math.factorial(n-c) // (math.factorial(n-c - i) * math.factorial(i))
  k=max(k,1)
  e+=k

print(d*e)


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n,k; cin>>n>>k;
  ll ans=0;
  ireps(i,k,n+1){
    ll l=i*(i-1)/2;
    ll r=n*(n+1)/2-(n-i+1)*(n-i)/2;
    // cout<<l<<" "<<r<<endl;
    ans+=(r-l+1)%MOD;
    ans=(ans+MOD)%MOD;
  }
  cout<<ans<<endl;
 }

Measured memory_bytes: 3632
// Created by sz
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int n,m,k;

using ll = long long;
const int mod = 1e9 + 7;

ll quick_pow(ll a, ll b) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int comb(int n, int m){
    //n!/(m!(n-m)!)
    vector<int> fac(n+1), finv(n+1);
    fac[0] = finv[0] = 1;
    for(int i = 1; i <= n; ++i)fac[i]=(ll)fac[i-1]*i%mod;
    finv[n] = quick_pow(fac[n], mod-2);
    for(int i = n-1; i; --i)finv[i] = (ll)finv[i+1]*(i+1)%mod;
    
    return (ll)fac[n] * finv[m] % mod * finv[n - m]% mod;
}



int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m>>k;
    
    
    ll d = 0;
    for (int i = 1; i < n; i++){
        d += (ll)i*(n-i)%mod*m%mod*m%mod;
        d%= mod;
    }
    
    for (int i = 1; i < m; i++){
        d += (ll)i*(m-i)%mod*n%mod*n%mod;
        d %= mod;
    }
    
    cout<<d*comb(n*m-2, k-2)%mod<<endl;
    
    
    
    
    
    return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=1<<29,MOD=1e9+7;

//0~10000の頂点のroot
int v[10010];
//初期化(n頂点バラバラ)
void init(int n){
	rep(i,n) v[i]=i;
}

//頂点aが属するrootを求める
int root(int a){
	if(v[a]==a) return a; //aはroot
	return (v[a]=root(v[a])); //aの親のroot
}

//頂点aとbが同一グループか?
bool is_same_set(int a,int b){
	return root(a)==root(b);
}

//頂点aとbを同一グループにまとめる
void unite(int a,int b){
	v[root(a)]=root(b);
}

int main(){
	int fib[1010]; fib[0]=2;fib[1]=3;
	rep(i,1000) fib[i+2]=(fib[i+1]+fib[i])%1001;
	int V,d;
	while(cin>>V>>d){
		init(V);
		rep(i,V){
			for(int j=i+1;j<V;j++){
				if(abs(fib[i]-fib[j])<d) unite(i,j);
			}
		}
		//rep(i,V) cout<<root(i)<<endl;
		int cnt=0;
		rep(i,V){
			//cout<<root(i)<<endl;
			if(root(i)==i) cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}



Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include <unordered_map>  
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

void A();

int main() {
	int n;
	unsigned long long int lucas[86];
	cin >> n;
	lucas[0] = 2;
	lucas[1] = 1;
	for (int i = 2; i <= n; ++i) {
		lucas[i] = lucas[i-1] + lucas[i - 2];
	}
	cout << lucas[n] << endl;
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <set>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <iomanip>
#include <utility>

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n;
bool ans[40], ch;

char obr(char c)
{
	if (c == '0')
		return '1';
	return '0';
}

void pll(char c, int i)
{
	if (c == '0')
		return;
	if (!(i & 1))//chet
		if (ans[i])
			ans[i] = false;
		else
		{
			ans[i] = true;
			pll('1', i + 1);
		}
	else//nechet
		if (!ans[i])
			ans[i] = true;
		else
		{
			ans[i] = false;
			pll('1', i + 1);
		}
}

void pl(char c, int i)
{
	if (ch)
	{
		pll(c, i);
		return;
	}
	if (c == '0')
		return;
	if (!(i & 1))
		if (!ans[i])
			ans[i] = true;
		else
		{
			ans[i] = false;
			pl('1', i + 1);
		}
	else
		if (ans[i])
			ans[i] = false;
		else
		{
			ans[i] = true;
			pl('1', i + 1);
		}
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
	//freopen("river.in", "r", stdin);
	//freopen("river.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	if (n == 0)
	{
		cout << 0;
		return 0;
	}
	string s = "";
	if (n < 0)
	{
		n = abs(n);
		ch = true;
	}
	while (n > 0)
	{
		s += '0' + (n & 1);
		n >>= 1;
	}
		for (int i = 0; i < s.length(); i++)
		pl(s[i], i);
	int j = 0;
	for (int i = 0; i < 40; i++)
		if (ans[i])
			j = i;
	while (j >= 0)
	{
		cout << ans[j];
		j--;
	}
	return 0;
	return 0;
}

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

int main(){
	map<int,int> a;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int d;
		cin>>d;
		a[d]++;
	}
	bool seive[(int)1e6+30]={};
	for(auto &f:a){
		int temp = f.first;
		if(f.second!=1) seive[temp]=true;
		for(int i=temp*2;i<=1e6+20;i+=temp){
			seive[i]=true;
		}
	}
	int result=0;
	for(auto &f:a){
		if(!seive[f.first]){
			result++;
		}
	}
	cout<<result<<"\n";

}

Measured memory_bytes: 13924
n = int(input())
an = list(map(int, input().split()))
bn = list(map(int, input().split()))
cn = list(map(int, input().split()))

ans = 0
before_i = 100
for i in an:
    ans += bn[i-1]
    if (i-before_i) == 1:
        ans += cn[before_i-1]
    before_i = i
print(ans)

Measured memory_bytes: 3064
// Snuke's Coloring 2
// * frank_c1
// * 2017 / 10 / 04

#include <bits/stdc++.h>
using namespace std;

const int maxn = (int)(3e5) + 5;
int tb[maxn], tot;
int u[maxn], d[maxn], wu[maxn], wd[maxn];
int w, h, n, ret;

inline int hs(int x) {
	return lower_bound(tb + 1, tb + tot + 1, x) - tb;
}

struct node {
	int x, y;
} p[maxn];

bool operator < (node a, node b) {
	return a.x != b.x ? a.x < b.x : a.y < b.y;
}

int mx[maxn << 2], wx[maxn << 2];

inline void addv(int x, int v) {
	mx[x] += v; wx[x] += v;
}

inline void pu(int x) {
	mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

inline void pd(int x) {
	if (wx[x]) {
		addv(x << 1, wx[x]); addv(x << 1 | 1, wx[x]); wx[x] = 0;
	}
}

void M(int x, int l, int r, int s, int t, int v) {
	if (s <= l && r <= t) {
		addv(x, v); return;
	} pd(x); int mid = (l + r) >> 1;
	if (s <= mid) M(x << 1, l, mid, s, t, v);
	if (mid < t) M(x << 1 | 1, mid + 1, r, s, t, v);
	pu(x);
}

void calc() {
	sort(p + 1, p + n + 1);
	tot = 0; tb[++tot] = 0; 
	for (int i = 1; i <= n; ++i) tb[++tot] = p[i].x; tb[++tot] = w;
	tot = unique(tb + 1, tb + tot + 1) - tb - 1;
	int ps = 1, s = h >> 1; u[0] = d[0] = 0;
	memset(mx, 0, sizeof(mx)); memset(wx, 0, sizeof(wx));
	for (int i = 1; i <= tot; ++i) {
		if (i > 1) M(1, 1, tot, 2, i, tb[i] - tb[i - 1]); M(1, 1, tot, i, i, h); ret = max(ret, mx[1]); 
		int lo = 0, hi = h;
		for (; ps <= n && hs(p[ps].x) == i; ++ps) {
			int y = p[ps].y; 
			if (y <= s) lo = max(lo, y); if (y >= s) hi = min(hi, y);
		} wu[i] = hi - s; wd[i] = s - lo; if (i == 1) wu[i] = wd[i] = 0; 
		while (u[0] && wu[u[u[0]]] > wu[i]) M(1, 1, tot, u[u[0] - 1] + 1, u[u[0]], wu[i] - wu[u[u[0]]]), --u[0]; 
		while (d[0] && wd[d[d[0]]] > wd[i]) M(1, 1, tot, d[d[0] - 1] + 1, d[d[0]], wd[i] - wd[d[d[0]]]), --d[0]; 
		u[++u[0]] = i; M(1, 1, tot, i, i, wu[i] - h + s); d[++d[0]] = i; M(1, 1, tot, i, i, wd[i] - s); 
	} 
}

int main() {
	scanf("%d%d%d", &w, &h, &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].x, &p[i].y);
	calc(); 
	swap(w, h); for (int i = 1; i <= n; ++i) swap(p[i].x, p[i].y);
	calc();
	return printf("%d\n", ret << 1), 0;
}

Measured memory_bytes: 17920
n=int(input())
num=[]
for i in range(n-1):
    num.append(list(map(int,input().split())))
for i in range(n-1):
    ans=0
    for j in range(i,n-1):
        if ans<=num[j][1]:
            ans=num[j][1]
        else:
            ans=num[j][1]+((-((ans-num[j][1])//-num[j][2]))*num[j][2])
        ans+=num[j][0]
    print(ans)
print(0)


Measured memory_bytes: 9188
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,pair<int,int> > P;
int main(void){
  pair<int,pair<int,int> > p;
  vector<P> v;
  int n,a,b;
  cin >> n;
  for(int i = 0;i < n; i++){
    cin >> p.second.second >> p.first;
    p.second.first = 100 - p.second.second;
    v.push_back(p);
  }
  sort(v.begin(),v.end());
  cout << v[v.size()-1].second.second << " " << v[v.size()-1].first << endl;
}


Measured memory_bytes: 1204
#include "bits/stdc++.h"

#pragma warning(disable:4996)
using namespace std;


int main() {
	int H,W,x,y;cin>>H>>W>>x>>y;
	bool ok=((H*W%2)==1)&&((x+y)%2==1);
	if(ok)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}



Measured memory_bytes: 3096
N = int(input())
B = list(map(int, input().split()))

A = [0]*N
A[0] = B[0]
for i in range(N-2):
     A[i+1] = min(B[i], B[i+1])
A[N-1] = B[N-2]
#print(A)
print(sum(A))


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		
		int a[] = new int[3], cost = 0;
		for (int i = 0; i < 3; i++)
		{
			a[i] = scan.nextInt();
		}
		scan.close();
		java.util.Arrays.sort(a);
		cost += a[1] - a[0];
		cost += a[2] - a[1];
		System.out.println(cost);
	}
}



Measured memory_bytes: 21844
#include <stdio.h>
int main(void)
{
    char O[51];
    char E[51];
    scanf("%s\n", O);
    scanf("%s", E);

    char *O_ptr = O;
    char *E_ptr = E;
    while(*O_ptr && *E_ptr ) {
        printf("%c%c",*O_ptr,*E_ptr);
        O_ptr++;
        E_ptr++;
    }
    if(*O_ptr){
        printf("%c",*O_ptr);
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, Q, a, b, res[200000];
vector<int>v[200000];

void dfs(int x) {
	for (int i : v[x]) {
		res[i] += res[x];
		dfs(i);
	}
}

int main() {
	cin >> N >> Q;
	for (int i = 1; i < N; ++i) {
		cin >> a >> b;
		--a;
		--b;
		v[a].push_back(b);
	}
	while (Q--) {
		cin >> a >> b;
		--a;
		res[a] += b;
	}
	dfs(0);
	for (int i = 0; i < N; ++i) {
		cout << res[i];
		if (i != N - 1)cout << sp;
	}
	cout << endl;
}


Measured memory_bytes: 20352
#include <iostream>
using namespace std;
int main()
{
	int dp[31]={},n,ans;
	dp[1]=1;
	dp[2]=2;
	dp[3]=4;
	for(int i=4;i<=30;i++){
		dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	}
	while(cin>>n){
		if(n==0)break;
		ans=dp[n]/3650;
		ans+=dp[n]%3650!=0?1:0;
		cout<<ans<<endl;
	}
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    int main(){
      ll n;
      cin>>n;
      ll a[n];ll dp[n];
      ll sum=0;
      for(int i=0;i<n;i++){cin>>a[i];dp[i]=10000000007;}
      dp[0]=0;
      dp[1]=abs(a[1]-a[0]);
      for(int i=2;i<n;i++)
        {
          dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]));
      }
      
      cout<<fixed;
      cout<<dp[n-1]<<endl;
      }

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

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

signed main(){
	int n=read();
	vi a(n);
	REP(i,n)
		a[i]=read();
	int ans=0;
	for(int i=0;i<n;){
		int j=i;
		while(j<n&&a[i]==a[j])
			j++;
		ans+=(j-i)/2;
		i=j;
	}
	print(ans);
}


Measured memory_bytes: 256
//k_k_dubey_
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define inf 999999999999
#define mx 200005
#define gcd __gcd
#define pb push_back
#define mk make_pair
#define bs binary_search
#define ub upper_bound
#define lb lower_bound
#define endl "\n"
#define vl vector<ll>
#define vs vector<string>
#define non __builtin_popcount
#define ml map<ll, ll> 
#define ms map<string , ll> 
using namespace std;

bool isp[mx];

void sv(){

	ll i,j;
	memset(isp, true, sizeof(isp));
	
	isp[1]= false;
	for(i=2;i*i<mx;i++){
		if(isp[i]){
			for(j=i*i;j<mx;j+=i)
			isp[j]= false;
		}
	}
}

ll powr(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	//sv();
	
	ll n,x,i,j,l[mx], cm[mx];
	cm[0]= 0;
	cin>>n>>x;
	for(i=1; i< n+1;i ++)
	{
	    cin>>l[i];
	    cm[i]= cm[i-1] + l[i];
	}
	auto it= ub(cm, cm+n+1, x);
	ll ans= it- cm;
	cout<<ans;
    return 0;
}























Measured memory_bytes: 2304
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ADigitSum2 solver = new ADigitSum2();
        solver.solve(1, in, out);
        out.close();
    }

    static class ADigitSum2 {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            String n = in.string();
            int ans = 0;
            boolean filled = true;
            for (int i = 1; i < n.length(); i++) {
                if (n.charAt(i) != '9') {
                    filled = false;
                }
                ans += 9;
            }
            ans += Integer.parseInt(n.substring(0, 1));
            if (!filled) {
                ans -= 1;
            }
            out.println(ans);
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}



Measured memory_bytes: 21460
MOD = 10**9+7


N = 10 ** 5+1  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD


def solve(n, k, a):
    a.sort()
    sum_max = 0
    sum_min = 0

    for i in range(n):
        sum_max += cmb(i, k-1) * a[i]
        sum_min += cmb(n-1-i, k-1) * a[i]

    return (sum_max - sum_min) % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    result = solve(n, k, a)
    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 94632
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  double sum=0.0;
  double ave;
  
  vector<double> nums(N);
  
  for(int i=0; i<N; i++){
  	cin >> nums[i];
  }
  
  while(nums.size() > 1){
  	sort(nums.begin(), nums.end());
    ave = (nums[0] + nums[1]) / 2;
    sum += ave;
    sort(nums.rbegin(), nums.rend());
    nums.pop_back();
    nums.pop_back();
    nums.push_back(ave);    
  }
  
  cout << nums[0];
}

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

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nm = Console.ReadLine().Split(' ').Select(n => int.Parse(n)).ToArray();
            var paths = new Dictionary<int, HashSet<int>>();
            for (var i = 0; i < nm[1]; i++)
            {
                var pair = Console.ReadLine().Split(' ').Select(n => int.Parse(n)).ToArray();
                if (paths.TryGetValue(pair[0], out var l1))
                {
                    l1.Add(pair[1]);
                }
                else
                {
                    paths[pair[0]] = new HashSet<int> { pair[1] };
                }

                if (paths.TryGetValue(pair[1], out var l2))
                {
                    l2.Add(pair[0]);
                }
                else
                {
                    paths[pair[1]] = new HashSet<int> { pair[0] };
                }
            }

            var symbols = new Dictionary<int, int>();
            Hoge(new HashSet<int> { 1 });
            for (var i = 0; i < nm[0]; i++)
            {
                if (i == 0)
                    Console.WriteLine("Yes");
                else
                    Console.WriteLine(symbols[i + 1]);
            }

            void Hoge(HashSet<int> bro)
            {
                var children = new HashSet<int>();
                foreach (var b in bro)
                {
                    var list = paths[b].Where(e => !bro.Contains(e) && !symbols.ContainsKey(e)).ToList();

                    list.ForEach(e =>
                    {
                        symbols[e] = b;
                        children.Add(e);
                    });
                }

                if (symbols.Count == nm[0]) return;
                else Hoge(children);
            }
        }
    }
}

Measured memory_bytes: 116984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//priority_queueが重複許すと初めて知った顔

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


	int X, Y, Z;
	cin >> X >> Y >> Z;

	pair<int, int> BA[100000];
	int CA[100000];
	int CB[100000];

	ll goukeiA = 0;
	rep(i, X + Y + Z) {
		int a, b, c;
		cin >> a >> b >> c;
		BA[i] = mp(b - a, i);
		CA[i] = c - a;
		CB[i] = c - b;
		goukeiA += a;
	}

	sort(BA, BA + X + Y + Z);

	ll C[100000] = {};
	priority_queue<int> que;
	rep(i, X) {
		que.push(CA[BA[i].second]);
	}
	rep(i, Z) {
		que.push(CA[BA[X + i].second]);
		C[i + 1] = C[i] + que.top();
		que.pop();
	}

	priority_queue<int> que2;
	reverse(BA, BA + X + Y + Z);
	ll B[100000] = {};
	rep(i, Y) {
		B[0] += BA[i].first;
		que2.push(CB[BA[i].second]);
	}
	rep(i, Z) {
		que2.push(CB[BA[Y + i].second]);
		B[i + 1] = B[i] + BA[Y + i].first + que2.top();
		que2.pop();
	}

	ll saidai = 0;
	rep(i, Z + 1) saidai = max(saidai, goukeiA + B[i] + C[Z - i]);

	co(saidai);

	cin >> X;

	Would you please return 0;
}

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

const int N = 1002, VV = 1e5 + 2 ;
int w[N], v[N];
long long dp[101][VV] ;
int n, V;
const long long MAX = 1e17 ;
long long K ;

long long sum(int i, int val)
{
    if(i >= n)
    {
        if(val >= V) return 0;
        else return MAX ;
    }
    if(dp[i][val] != -1) return dp[i][val] ;
    long long ans = min(sum(i+1, val), w[i] + sum(i+1, val + v[i]));
    return dp[i][val] = ans ;
}

int main()
{
    cin >> n >> K ;
    for(int i = 0; i < n; i++)
        cin >> w[i] >> v[i] ;
    int low = 0, high = 1e5 + 2 ;
    while((high - low) > 1)
    {
        V = (high + low) >> 1 ;
        memset(dp, -1, sizeof(dp));
        long long wt = sum(0, 0);
        if(wt <= K) low = V ;
        else high = V ;
    }
    cout << low ;
}

/*
double rec(int i, int last)
{
    if(i >= n)
    {
        if(last > ( n - last)) return 1.0 ;
        else return 0.0 ;
    }
    if(dp[i][last] != -1) return dp[i][last] ;

    double head = p[i] * rec(i+1, last + 1);
    double tail = (1 - p[i]) * rec(i+1, last);

    dp[i][last] = (head + tail) ;
}
*/


Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
const int SZ=100005;
int arr[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL); 
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	sort(arr,arr+n);
	cout<<arr[n/2]-arr[n/2-1];
	return 0;
}

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

int main() {
    int N, Y;
    cin >> N >> Y;

    for (int i = 0; i <= Y / 10000; i++) {
        for (int j = 0; j <= Y / 5000; j++) {
            int k = (Y - i * 10000 - j * 5000) / 1000;
            if (k >= 0 && i + j + k == N) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

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

int main() {
	int n, m; cin >> n >> m;
	vector<vector<char>>a(n, vector<char>(n)), b(m, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m; i++)for (int j = 0; j < m; j++)cin >> b[i][j];

	bool exist = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i + m - 1 >= n || j + m - 1 >= n)continue;

			bool match = true;
			for (int by = 0; by < m; by++) {
				for (int bx = 0; bx < m; bx++) {
					if (a[i+by][j+bx] != b[by][bx])match = false;
				}
			}
			if (match)exist = true;
		}
	}
	cout << (exist ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;

auto get_base(std::vector<i64> v) {
    std::vector<i64> ret;
    const int n = v.size();
    int r = 0;
    for (i64 j = 0; j < 60; j++) {
        int p = -1;
        for (int i = r; i < n; i++) {
            if (v[i] & (1ll << j)) {
                p = i;
                break;
            }
        }

        if (p < 0) continue;
        std::swap(v[p], v[r]);
        ret.push_back(v[r]);

        for (int i = 0; i < n; i++) {
            if (i != r && (v[i] & (1ll << j))) v[i] ^= v[r];
        }
        r++;
    }

    return ret;
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<i64> a(n);
        for (auto &e : a) std::cin >> e;
        std::string s;
        std::cin >> s;

        if (s.back() == '1') {
            std::cout << "1\n";
            continue;
        }

        std::vector<std::vector<i64>> v[2];
        for (int i = 0; i < n; ) {
            int j = i;
            const int t = s[i] - '0';
            while (j < n && s[j] == s[i]) j++;

            std::vector<i64> sub(a.begin() + i, a.begin() + j);
            v[t].push_back(get_base(sub));

            i = j;
        }

        std::vector<i64> bs;
        while (!v[1].empty()) {
            for (const i64 e : v[0].back()) bs.push_back(e);
            bs = get_base(bs);

            const int r = bs.size();
            for (const i64 e : v[1].back()) {
                bs.push_back(e);
                if (get_base(bs).size() != r) {
                    std::cout << "1\n";
                    goto next;
                }
                bs.pop_back();
            }

            v[0].pop_back();
            v[1].pop_back();
        }

        std::cout << "0\n";

next:;
    }

    return 0;
}


Measured memory_bytes: 3644
N, M = map(int, input().split())

C = []
for i in range(M):
    p, y = map(int, input().split())
    C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))

ans = []
k = C[0][1]
n = 1
for i in range(M):
    city = C[i][1]
    if k != city:
        k = city
        n = 1
    number = f'{city:06}{n:06}'
    ans.append([C[i][0], number])
    n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
    print(ans[i][1])


Measured memory_bytes: 46144
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int main()
{
    int h,w,k,i,j,n,a[12],n1,count,ans;
    string s;
    cin>>h>>w>>k;
    int c[h][w],c1[h][w];
    for (i = 0; i < h; i++) for (j = 0; j < w; j++) c[i][j]=0;
    for (i = 0; i < h; i++)
    {
        cin>>s;
        for (j = 0; j < w; j++) if (s[j]=='#') c[i][j]=1;
    }
    n=0;
    ans=0;
    while (n<pow(2,h+w))
    {
        for (i = 0; i < h; i++) for (j = 0; j < w; j++) c1[i][j]=c[i][j];
        n1=n;
        for (i = 0; i < h+w; i++)
        {
            a[i]=n1%2;
            n1/=2;
        }
        n++;
        for (i = 0; i < h; i++) if (a[i]==1) for (j = 0; j < w; j++) c1[i][j]=0;
        for (i = h; i < h+w; i++) if (a[i]==1) for (j = 0; j < h; j++) c1[j][i-h]=0;
        count=0;
        for (i = 0; i < h; i++) for (j = 0; j < w; j++) if (c1[i][j]==1) count++;
        if (count==k) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4104
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for (auto &v : vec)
    cin >> v;
  sort(vec.begin(), vec.end(), greater<int>());

  int sa = 0;
  int sb = 0;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      sa += vec[i];
    else
      sb += vec[i];
  }

  cout << sa - sb << endl;
}


Measured memory_bytes: 3596
n = int(input())
a = list(map(int, input().split()))

judge = 'equal'
cnt = 1
for i in range(n-1):
  if a[i] < a[i+1]:
    if judge == 'equal':
      judge = 'high'
    elif judge == 'low':
      judge = 'equal'
      cnt += 1
  elif a[i] > a[i+1]:
    if judge == 'equal':
      judge = 'low'
    elif judge == 'high':
      judge = 'equal'
      cnt += 1

      
print(cnt)

Measured memory_bytes: 14252
using System;

class Program
{
	static void Main(string[] args)
	{
		int n = int.Parse(Console.ReadLine());
		long[] r = new long[n];
		for (int i=0; i<n; i++)
		{
			r[i] = long.Parse(Console.ReadLine());
		}

		long min = r[0];
		long max = r[1] - min;

		for(int i=1; i<n; i++)
		{
			long x = r[i] - min;
			if(x > max)
			{
				max = x;
			}
			if(r[i] < min)
			{
				min = r[i];
			}
		}

		Console.WriteLine(max);
	}
}

Measured memory_bytes: 12328
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;

const int maxn = (int)2e5 + 3;
int n, dp[maxn][2];
char buf[maxn];

int main() {
	scanf("%s", buf);
	n = strlen(buf);
	dp[0][0] = INT_MIN;
	dp[0][1] = 0;
	for(int i = 0; i < n; ++i) {
		int L = buf[i] == 'D';
		int R = buf[i] != 'P';
		for(int j = L; j <= R; ++j)
			dp[i + 1][j] = max(dp[i][0] + (j << 1), dp[i][1] + j);
	}
	int pos = dp[n][0] < dp[n][1];
	for(int i = n - 1; i >= 0; --i) {
		if(buf[i] == '?')
			buf[i] = "PD"[pos];
		for(int j = 0; j < 2; ++j)
			if(dp[i][j] + (pos << (j ^ 1)) == dp[i + 1][pos]) {
				pos = j;
				break;
			}
	}
	puts(buf);
	return 0;
}

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

#define EPS 1e-6
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f

#define fi first
#define se second
#define pb push_back
#define ende '\n'

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(x, y) memset(&x, (y), sizeof(x))

using namespace std; 

using ll = long long;
using ii = pair<int,int>;

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

  ll a, b; cin >> a >> b;
  ll g = __gcd(a, b); 

  auto prime = [](ll x) {
    if (x == 2) return true;
    if (x == 1) return false;
    if (x % 2 == 0) return false;

    for (ll i = 3; i*i <= x; i += 2)
      if (x % i == 0) return false;
    return true;
  };

  int ans = 0;
  for (ll i = 1; i*i <= g; ++i) {
    if (g % i == 0) {
      ans += prime(i);
      if (i != (g / i))
        ans += prime(g/i);
    }
  }
  
  cout << ans + 1 << ende;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  n%=10;
  if(n==2||n==4||n==5||n==7||n==9) std::cout << "hon" << '\n';
  else if(n==3) std::cout << "bon" << '\n';
  else std::cout << "pon" << '\n';
  return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    

    int n;
    cin >> n;
    int ary[n];
    rep(i,n) cin >> ary[i];

    int sum = 0;
    int non_zero_itr = -1;
    sort(ary, ary+n);
    rep(i,n)
    {
        if(ary[i]%10!=0)
        {
            non_zero_itr = i;
            break;
        }
    }
    rep(i,n) sum += ary[i];

    if (sum%10==0)
    {

        if (non_zero_itr==-1)
        {
            cout << 0 << endl;
        }
        else
        {
            cout << sum - ary[non_zero_itr] << endl;
        }
        
    }
    else
    {
        cout << sum << endl;
    }
}


Measured memory_bytes: 256
import math
import sys

input = sys.stdin.readline


def main():
    s = input().strip()
    if len(s) % 2 == 1:
        print('No')
        return

    for idx in range(len(s)):
        if idx % 2 == 0 and s[idx] != 'h':
            print('No')
            return
        elif idx % 2 == 1 and s[idx] != 'i':
            print('No')
            return
    print('Yes')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
sx,sy,tx,ty=map(int,input().split())

if tx > sx and ty > sy:mode=0
elif tx > sx and ty < sy:mode=1
elif tx < sx and ty > sy:mode=3
else: mode=2
  
directions=[('R','U'),('R','D'),('L','D'),('L','U'),('R','U'),('R','D'),('L','D'),('L','U')]

ans=[]
d_go,d_re = directions[mode],directions[mode+2]
dx,dy=abs(tx-sx),abs(ty-sy)
go1 = dx*d_go[0] + dy*d_go[1]
re1 = dx*d_re[0] + dy*d_re[1]
go2 = d_re[1]+(dx+1)*d_go[0] + (dy+1)*d_go[1] + d_re[0]
re2 = d_go[1]+(dx+1)*d_re[0] + (dy+1)*d_re[1] + d_go[0]

ans.extend(go1)
ans.extend(re1)
ans.extend(go2)
ans.extend(re2)

print(''.join(ans))

Measured memory_bytes: 9272
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

#define INF 1e9

int main(){
  long long n;
  long long k;
  string s;
  cin >> s;
  cin >> k;
  n = s.length();
  long long count = 1;
  vector<long long> r;
  for(int i=0;i<n-1;i++){
    if(s[i] == s[i+1]){
      count += 1;
    }
    else{
      r.push_back(count);
      count = 1;
    }
  }

  if(count >= 1) r.push_back(count);

  count = 0;
  for(int i=0;i<r.size();i++){
    count += r[i]/2*k;
  }

  if(s[0] == s[n-1]){
    if(r.size() == 1){
      count = (k*n)/2;
    }
    else{
      count += ((r[0]+r[r.size()-1])/2 - (r[0]/2 + r[r.size()-1]/2))*(k-1);
    }
  }

  cout << count << endl;

  return 0;

}

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

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print((sum(DPLIST)-DPLIST[-1]*3)%mod)
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod)

Measured memory_bytes: 42972
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	std::vector<int> l(n);
	rep(i,n) std::cin >> l[i];
	std::sort(all(l));
	std::vector<int> a;
	rep(i,n) rep(j,n) {
		if(i<j) a.emplace_back(l[i]+l[j]);
	}
	int count = n*(n-1)*(n-2)/6;
	for(auto i:a) {
		count -= (l.end() - std::lower_bound(all(l),i));
	}
	print(count);
	return 0;
}


Measured memory_bytes: 18540