akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

#define NIL -1
#define N 500001

//struct Node{
//	int val;
//	Node *p, *l, *r;
//};

struct Node {
	int val;
	Node *p, *l, *r;
	Node(int v) :val(v), p(NULL), l(NULL), r(NULL){}
	Node() :val(0), p(NULL), l(NULL), r(NULL){}
};

Node T[N];
int D[N], H[N];

Node *root;

void insert(int k){
	Node *y = NULL;
	Node *x = root;
	Node *z = new Node(k);

	while (x != NULL && x->val != k){
		y = x;
		if (k > x->val) x = x->r;
		else x = x->l;
	}
	z->p = y;
	if (y == NULL) root = z;
	else{
		if (k < y->val) y->l = z;
		else y->r = z;
	}
}

Node *find(int val){
	Node *p = root;
	while (p != NULL && p->val != val) {
		if (val < p->val) p = p->l;
		else p = p->r;
	}
	return p;
}

void ino(Node *p){
	if (p == NULL) return;
	ino(p->l);
	printf(" %d", p->val);
	ino(p->r);
}

void preo(Node *p){
	if (p == NULL) return;
	printf(" %d", p->val);
	preo(p->l);
	preo(p->r);
}

Node *mi(Node *z){
	while (z->l != NULL) z = z->l;
	return z;
}

Node *suc(Node *z){
	return mi(z->r);
	//if (z->r != NULL) return mi(z->r);
	//Node *y = z->p;
	//while (y != NULL && z == y->r) {
	//	z = y;
	//	y = y->p;
	//}
	//return y;
}

void del(Node *z){
	Node *y = NULL;
	Node *x = NULL;

	if (NULL == z->l || NULL == z->r) y = z;
	else y = suc(z);

	if (NULL != y->l) x = y->l;
	else x = y->r;

	if (NULL != x) x->p = y->p;

	if (NULL == y->p) root = x;
	else {
		if (y == y->p->l) y->p->l = x;
		else y->p->r = x;
	}

	if (y != z) z->val = y->val;
	delete y;
}


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

	int val;
	string com;
	for (int i = 0; i < n; ++i) {
		cin >> com;
		if (com[0] == 'f'){
			cin >> val;
			Node *p = find(val);
			cout << ((p == NULL) ? "no" : "yes") << endl;
		}
		else if (com[0] == 'i'){
			cin >> val;
			insert(val);
		}
		else if (com[0] == 'p'){
			ino(root); cout << "\n";
			preo(root); cout << "\n";
		}
		else if (com[0] == 'd'){
			cin >> val;
			del(find(val));
		}
	}

	return 0;
}

//yes
//yes
//yes
//no
//no
//no
//yes
//yes
//1 2 3 7 8 22
//8 2 1 3 7 22
//1 2 8 22
//8 2 1 22

Measured memory_bytes: 37584
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include<algorithm>
//---------------------------------------------------------------
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
#define all(x) x.begin(),x.end()
#define fi first
#define se second
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
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; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

ll m = 1e18;

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

    int n;cin>>n;
    vll a(100005);
    rep(i,n){
        cin>>a[i];
        if(a[i]==0){
            cout<<0;
            return 0;
        }
    }

    ll ans=1;
    rep(i,n){
        if((long double)m/a[i] < ans){
            cout<<-1;
            return 0;
        }else{
            ans = ans*a[i];            
        }
    }

    cout<<ans;
    return 0;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s, t;
	cin >> s >> t;
	int64 res = 0;
	REP(i, s.size()) {
	  if (s[i] != t[i]) res++;
	}
	cout << res << endl;
}


Measured memory_bytes: 3768
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	var origin = make([]int, n)
	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)

		origin[i] = v
	}

	var max = 0
	for l := 0; l < k+1; l++ {
		for r := 0; r < k-l+1; r++ {

			for p := 0; p < k-l-r+1; p++ {

				var sum, _ = Sum(origin, l, r, p)

				if max < sum {
					max = sum
				}
			}
		}

	}

	fmt.Println(max)
}

func Sum(origin []int, l, r, d int) (int, []int) {
	var gems = origin

	var pick = 0
	var hand = sort.IntSlice{}

	for i := 0; len(gems) > 0 && i < l; i++ {
		gems, pick = lPop(gems)
		hand = append(hand, pick)
	}

	for i := 0; len(gems) > 0 && i < r; i++ {
		gems, pick = rPop(gems)
		hand = append(hand, pick)
	}

	hand.Sort()
	for i := 0; len(hand) > 0 && i < d; i++ {
		hand, _ = lPop(hand)
	}

	var sum = 0
	for _, h := range hand {
		sum += h
	}

	return sum, hand
}

func rPop(gems sort.IntSlice) (sort.IntSlice, int) {
	if len(gems) == 1 {
		return []int{}, gems[0]
	}
	return gems[:(len(gems) - 1)], gems[len(gems)-1]
}

func lPop(gems sort.IntSlice) (sort.IntSlice, int) {
	if len(gems) == 1 {
		return []int{}, gems[0]
	}
	return gems[1:], gems[0]
}


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

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}

int main(){
    ll n, k; cin >> n >> k;
    vector<ll> a(n); cin >> a;
    sort(a.begin(), a.end());
    if(a[n-1] < k){
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    ll g = 0;
    rep(i, n){
        if(i == 0) g = a[i];
        else g = gcd(g, a[i]);
    }
    if(k%g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 3936
#include <bits/stdc++.h>
    typedef long long ll;
    #define pb push_back
    #define f first
    #define s second
    #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define endl '\n'
    #define mem(a , v)  memset(a , v , sizeof(a))

using namespace std;
const int MAX=1002;
const int inf = 1e9+77;
const int MOD = 1e9+7;
//ll x[MAX];

char ALPH[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};


char ALPH_C[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char vowels[6]={'a','e','i','o','u','y'};

ll power(ll x,ll y){
         if(y==0)
         return 1;
         ll s=power(x,y/2);
         s*=s;
         if(y%2==1)
         s*=x;
         return s;
}
void sortString(string &str)
{
   sort(str.begin(), str.end());
   //cout << str;
}
  ll dp[MAX][MAX];
  ll n,m;
  char x[MAX][MAX];
  bool valid(int i,int j){
    return(i>=0&&i<n&&j>=0&&j<m&&x[i][j]!='#');

  }
ll solve(int i ,int j){
    if(i==n-1&&j==m-1) return 1;
    ll &res=dp[i][j];
    if(res!=-1) return res;
    //if(i<n-2&&j<m-2) res=max(solve(i+1,j),solve(i,j+1));
    res=0;
    if(valid(i+1,j)) res=(res+solve(i+1,j))%MOD;
    if(valid(i,j+1)) res=(res+solve(i,j+1))%MOD;

    return res%MOD;


  }

int main()
{  IOS
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);

   mem(dp,-1);
   cin>>n>>m;

   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cin>>x[i][j];
    }
   }
   cout<<(solve(0,0)%MOD);

    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a;
  int ac = 0, wa = 0, tle = 0, re = 0;
  string s;
  for(int i = 0;i < a;i++){
    cin >> s;
    if(s == "AC"){
      ac++;
    }
    if(s == "WA"){
      wa++;
    }
    if(s == "TLE"){
      tle++;
    }
    if(s == "RE"){
      re++;
    }
  }
  cout << "AC x " << ac << endl;
  cout << "WA x " << wa << endl;
  cout << "TLE x " << tle << endl;
  cout << "RE x " << re << endl;
}


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

int n;
int a[200005];
int ans[200005];

void work1()
{
	int time=0,add=2;
	ans[n/2+1]=1;
	int p=n/2,q=n/2+2;
	
	while (time<=n/2)
	{
		ans[p--]=add++;
		ans[q++]=add++;
		time++;
	}
	
	ans[p]=add;
}

void work2()
{
	int time=0,add=2;
	ans[n/2+1]=1;
	int p=n/2,q=n/2+2;
	
	while (time<=n/2)
	{
		ans[q++]=add++;
		ans[p--]=add++;
		time++;
	}
}

int main()
{
	
	scanf ("%d",&n);
	for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
	
	if (n%2==0) work1();
	else work2();
	
	//for (int i=1;i<=n;i++)
		//cout<<ans[i]<<' ';
	//cout<<endl;
	
	for (int i=1;i<=n;i++) printf("%d ",a[ans[i]]);
}

Measured memory_bytes: 3712
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  int a,b;
  cin >> a >> b;
  int ak = 1;
  int res = 0;
  while(ak < b){
    res ++;
    ak += a - 1;
  }
  cout << res << "\n";
}


Measured memory_bytes: 256
from collections import deque, defaultdict
import sys
input = sys.stdin.buffer.readline

n, m, k = map(int, input().split())

#先ずは連結成分の数を調べる
G = defaultdict(lambda:deque([]))
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

NIL = -1
color = [NIL]*n
def dfs(r, c):
    S = deque([])
    S.append(r)
    color[r] = c
    while S:
        u = S.popleft()
        for v in G[u]:
            if color[v] == NIL:
                color[v] = c
                S.append(v)
                
def make_color():
    id = 1
    for u in range(n):
        if color[u] == NIL:
            dfs(u, id)
            id += 1
            
make_color()
#グラフの塗り分け完了

#各色ごとの連結成分の数を数える
count = defaultdict(lambda:0)
for i in range(n):
    count[i] = 0
for i in range(n):
    count[color[i]] += 1

#ブロック関係の辞書を作成
block = defaultdict(lambda:deque([]))
for _ in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    block[c].append(d)
    block[d].append(c)

temp = []
for i in range(n):
    x = count[color[i]] - 1#自分以外の連結成分の和
    y =  len(G[i])#友達の数
    z = 0 #連結内のブロック数
    for v in block[i]:
        if color[i] == color[v]:
            z += 1
    temp.append(x-y-z)
print(*temp)


Measured memory_bytes: 178236
/*-----lusar98-----*/
#include<bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define eps 1e-9
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
using namespace std;
int main()
{
    //fast();
    ll n,w;
    cin>>n>>w;
    ll arr[n][2];
    for(ll i=0;i<n;i++)
    	cin>>arr[i][0]>>arr[i][1];
    ll dp[n+2][w + 10];
    memset(dp,-1,sizeof dp);
    dp[0][ arr[0][0] ]=arr[0][1];
    dp[0][0] = 0;
    for(ll i=1;i<n;i++)
    {
    	for(ll j =0 ;j<=w;j++)
    	{
    		if(dp[i-1][j]!=-1)
    		{
    			if(j+arr[i][0]<=w)
    				dp[i][j+arr[i][0]] = max(dp[i-1][j] + arr[i][1],dp[i][j+arr[i][0]]);
    			dp[i][j] = max(dp[i-1][j],dp[i][j]);
    		}
    	}
    }
    ll ans=-1;
    for(ll i=0;i<=w;i++)
    {
    	ans=max(ans, dp[n-1][i]);
    }
    cout<<ans<<endl;

    
}


Measured memory_bytes: 80000
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
#include <chrono>
 
using namespace std;
using namespace __gnu_pbds;
 
#define endl '\n'
 
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template<typename T>
static T randint(T lo, T hi){
	return uniform_int_distribution<T>(lo, hi)(rng);
}



int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);


	const int maxn = 1e6 + 5;
	vector<vector<int>> d(maxn);
	vector<int> f(maxn);

	for(int i = 1; i < maxn; i++){
		for(int j = i; j < maxn; j += i){
			d[j].push_back(i);
		}
	}

	int n;
	cin >> n;

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

	int ans = 0;
	for(int i = 1; i < maxn; i++){
		if(f[i] == 1){
			bool ok = true;
			for(auto &j : d[i]){
				if(j != i && f[j] > 0)
					ok = false;
			}

			ans += ok;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 121464
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;

int main(){
  int N,B[100];
  cin>>N;
  for (int i(0);i<N-1;i++) cin>>B[i];
  int cnt(B[0]+B[N-2]);
  for (int i(1);i<N-1;i++){
    cnt+=min(B[i],B[i-1]);
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back
#define pp pair<int,int>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define int long long
 main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt.txt","r",stdin);
	// freopen("output.txt.txt","w",stdout);
	// #endif
	int n;
	cin>>n;
	vi a(n);
	rep(i,0,n) cin>>a[i];
	int dp[n][n],dp2[n][n];
	rep(len,1,n+1)
	{
		rep(st,0,n-len+1)
		{
			int en = st+len-1;
			dp[st][en] = 0;
			if(st==en)
			{
				dp[st][en] = a[st];
				dp2[st][en] = 0;
				continue;
			}

			dp[st][en] = max(dp2[st+1][en]+a[st],dp[st][en]);
			dp[st][en] = max(dp2[st][en-1]+a[en],dp[st][en]);
			dp2[st][en] = min(dp[st][en-1],dp[st+1][en]);

		}
	}
	cout<<2*dp[0][n-1]-accumulate(all(a),0ll)<<endl;
 
}

Measured memory_bytes: 140160
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let n: usize = read();
    let s: Vec<char> = read::<String>().into_bytes().into_iter().map(|a| a as char).collect();

    let mut res = vec![false; n];
    let mut is_ok = false;
    for ptn in 0..4 {
        res[0] = ptn & 1 == 1;
        res[1] = ptn & 2 == 2;
        fill(&mut res, &s);
        if is_valid(&mut res, &s) {
            is_ok = true;
            break;
        }
    }

    if is_ok {
        for i in 0..n {
            print!("{}", if res[i] { 'S' } else { 'W' });
        }
        println!();
    } else {
        println!("-1");
    }
}

fn fill(animals: &mut Vec<bool>, statement: &Vec<char>) {
    let n = animals.len();
    for ri in 2..n {
        let li = ri-2;
        let i = ri-1;
        animals[ri] = animals[i] ^ animals[li] ^ (statement[i] == 'o');
    }
}

fn is_valid(animals: &Vec<bool>, statement: &Vec<char>) -> bool {
    let n = animals.len();
    for i in 0..n {
        let li = (i+n-1)%n;
        let ri = (i+1)%n;
        if animals[i] ^ (animals[li] == animals[ri]) ^ (statement[i] == 'x') {
            return false;
        }
    }
    true
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <string>
#include <typeinfo>
#include <cmath>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define ii pair<int,int>
#define MAX 1000000007
using namespace std;


int main(){
	int n,m,x;
	cin >> n >> m >> x;
	int a[n+1];
	rep(i,n+1) a[i] = 0;
	rep(i,m){
		int tmp;
		cin >> tmp;
		a[tmp] = 1;
	}

	int cur = x, cost = 0, ans;
	while(cur != n){
		if(a[cur]) cost++;
		cur++;
	}
	ans = cost;
	cur = x;
	cost = 0;
	while(cur != 0){
		if(a[cur]) cost++;
		cur--;
	}

	if(ans < cost) cout << ans << endl;
	else cout << cost << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(sc.nextLong());
        }
        a.sort(Collections.reverseOrder());
        long sum = 0;
        for (int i = 1; i < n; i++) {
            sum += a.get(i / 2);
        }
        System.out.println(sum);
    }

}


Measured memory_bytes: 66476
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <complex>
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    vector<int> cnt(n, 0);
    vector<int> ans_index(n);
    int max = 0;
    int num = 1;

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




    cnt[0] = 0;
    for(int i = 1; i < n; ++i){
        if(s[i] == s[i-1]){
            ++num;
        }
        else if(s[i] != s[i-1]){
            cnt[i-1] = num;
            if(cnt[i-1] > max){
                max = cnt[i-1];
            }

            num = 1;
        }
    }
    cnt[n-1] = num;
    if(cnt[n-1] > max){
                max = cnt[n-1];
    }

    rep(i,n){
        if(cnt[i] == max){
            cout << s[i] << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define prArr(Arr,n) for(int _=0;_<n;_++)   cout<<(Arr)[_]<<" ";
using namespace std;
const int INF=(int)1e9+10;
const int MOD=998244353;
vector<vector<int>> idx(26);
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long ptr=-1,cnt=0;
    string a,b;
    cin>>a>>b;
    for(int i=0;i<a.size();i++)
        idx[a[i]-'a'].push_back(i);
    for(int i=0;i<b.size();i++)
    {
        if(idx[b[i]-'a'].empty())
            return cout<<"-1", 0;
        int x=upper_bound(idx[b[i]-'a'].begin(),idx[b[i]-'a'].end(),ptr)-idx[b[i]-'a'].begin();
        if(x==idx[b[i]-'a'].size())
            cnt++,
            ptr=idx[b[i]-'a'][0];
        else
            ptr=idx[b[i]-'a'][x];
    }
    cout<<cnt*a.size()+ptr+1;
    return 0;
}


Measured memory_bytes: 1228
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define co(x) cout << (x) << "\n"
#define pb push_back
#define Never
#define To

using namespace std;

int main(){

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

	long long r, D, x;

	cin >> r >> D >> x;

	for(int i = 0; i <10; i++){
		x = r*x - D;
		cout << x << endl;
	}

	Never To return 0;
}


Measured memory_bytes: 256
N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

dp = [-INF] * (T + 1)
dp[0] = 0

for a, b in AB:
    newDp = dp[::]
    for t, d in enumerate(dp[:T]):
        newDp[min(T, t + a)] = max(newDp[min(T, t + a)], d + b)
    dp = newDp

print(max(dp))

Measured memory_bytes: 58072
import java.util.Scanner;

//20180508
//08

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

		while (scanner.hasNextLine()) {
			int h = scanner.nextInt();
			int w = scanner.nextInt();

			if(h == 0 && w == 0) {
				break;
			}

			for (int y = 1; y <= h; y++) {
				for (int x = 1;x <= w;x++) {
					if((x + y) % 2 == 0) {
						System.out.print("#");
					} else {
						System.out.print(".");
					}
				}
				System.out.println();
			}
			System.out.println();
		}

    	scanner.close();
    }
}


Measured memory_bytes: 34492
package main

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

var A int
var B int

func main() {
	A = nextInt()
	B = nextInt()
	rst := B % A
	if rst != 0 {
		fmt.Printf("%v", B-A)
	} else {
		fmt.Printf("%v", B+A)
	}

}

func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}

func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func Min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func MaxIn2Values(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func MinIn2Values(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func Abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}


Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
    
# しゃくとり法
right = 0
ans = 0
sum_A = 0

for left in range(N):    
  while right < N and (sum_A^A[right]) == (sum_A+A[right]):
    sum_A += A[right]
    right += 1
  ans += right - left
  if left == right:
    right += 1
  else:
    sum_A -= A[left]

print(ans)

Measured memory_bytes: 23560
n = int(input())

ls = list(map(int,input().split()))

tot = sum(ls)

p = 0
for i in range(n):
  p += ls[i]
  if p>= tot/2:
    break
tmp = 2*p-tot

p = 0
for i in range(n-1,-1,-1):
  p += ls[i]
  if p>= tot/2:
    break
print(min(tmp,2*p-tot))



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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 998244353;
 
////////////////////////////////////////////////////////////////////

const int N = 4e3 + 5;

int C[N][N], P[N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	C[0][0] = 1;
	for (int i = 1; i < N; i++) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}
	P[0] = 1;
	for (int i = 1; i < N; i++) P[i] = 2LL * P[i - 1] % MOD;

	int k, n; cin >> k >> n;
	for (int i = 2; i <= (k << 1); i++) {
		int ans = 0, x = (min(k, i - 1) - (i - min(k, i - 1)) + 1), rem = k - x; x /= 2;
		for (int y = 0; y <= x; y++) ans = (ans + 1LL * P[y] * C[x][y] % MOD * C[n + rem - 1][y + rem - 1] % MOD) % MOD;
		if ((i & 1) == 0) for (int y = 0; y <= x; y++) ans = (ans + 1LL * P[y] * C[x][y] % MOD * C[n + rem - 2][y + rem - 1] % MOD) % MOD;
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 61440
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

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


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


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<(n);i++)
#define P pair<int,int>
#define mod 1000000007
#define S second
#define F first
#define int long long
using namespace std;
pair<int,int> p[50];
bool bo[50];
signed main(){
	int a,b,ans=0,z;
	cin>>a>>b;
	z=a-1;
	p[0].F=1;
	p[0].S=1;
	f(i,49){
		p[i+1].F=p[i].F*2+3;
		p[i+1].S=p[i].S*2+1;
	}
	b--;
	JOI:;
	if(b==0) goto IOI;
	else if(b<p[z].F){
		b--;
		z--;
		goto JOI;
	}
	else{
		ans+=p[z].S;
		b-=p[z].F;
		if(b&&!bo[z]){
			ans++;
			b--;
			bo[z]=true;
		}
		else if(bo[z]) goto IOI;
		goto JOI;
	}
	IOI:;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n,m; cin >> n >> m;
    vector<string> A(n);
    vector<string> B(m);
    for(ll i=0;i<n;i++) cin >> A[i];
    for(ll i=0;i<m;i++) cin >> B[i];
    bool ok = false;

    for(ll i=0;i<n-m+1;i++){
        for(ll j=0;j<n-m+1;j++){
            ll flag = 0;
            //左上のマスがi,j
            for(ll k=0;k<m;k++){
                if(A[i+k].substr(j,m) == B[k]) flag++;
            }
            if(flag == m) ok = true;
        }
    }

    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 3656
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
//#include <algorithm>
#include <vector>

#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))

using namespace std;

int main(int argc, char* argv[])
{
    char str0[3001]={0};
    scanf("%s", str0);
    long len0 = strlen(str0);

    char str1[3001]={0};
    scanf("%s", str1);
    long len1 = strlen(str1);

    vector<vector<long> > aa(len0+1, vector<long>(len1+1, 0));
    vector<vector<long> > flag(len0+1, vector<long>(len1+1, 0));

    long i, j;
    for(i=1; i<=len0; i++) {
        for(j=1; j<=len1; j++) {
            if(str0[i-1]==str1[j-1]) {
                aa[i][j] = aa[i-1][j-1] + 1;
            }
            else {
                if( aa[i][j-1] > aa[i-1][j] ) {
                    aa[i][j] = aa[i][j-1];
                    flag[i][j] = 1;
                }
                else {
                    aa[i][j] = aa[i-1][j];
                    flag[i][j] = 2;
                }
            }
        }
    }

    long tmp = aa[len0][len1];
    vector<char> str(tmp+1, 0);
    i = len0;
    j = len1;
    long k = tmp;
    while(i>0 && j>0) {
        if(flag[i][j]==1) {
            j--;
        }
        else if (flag[i][j]==2) {
            i--;
        }
        else {
            str[tmp-1] = str0[i-1];
            tmp--;
            i--;
            j--;
        }
    }
    printf("%s\n", &(str[0]));
    return 0;
}


Measured memory_bytes: 141184
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <iomanip>
#include <unordered_map>
#include <queue>
#include <bitset>
using namespace std;

#define REP(i,n) for (int i=0;i<(n);i++)
#define PII pair<int,int>
#define LL long long
#define vi vector<int>
#define vii vector<PII>

int bitCount(LL bits){
    /*    int c = bits - ((bits >> 1) & 0x0055);
    c = (c & 0x0333) + ((c >> 2) & 0x0033);
    c = (c + (c >> 4)) & 0x0f0f;
    c = c + (c >> 8);
    
    return c;*/
    int num  = 0;

    for ( ; bits != 0 ; bits &= bits - 1 ) {
        num++;
    }
    
    return num;
}


int main(){
    LL n, m;
    vi p,s;
    //    vector<vi> s;

    LL k,ts;

    cin >> n >> m;
    REP(i,m){
        cin >> k;
        LL tts = 0b0;
        REP(j,k){
            cin >> ts;
            tts |= (1 << (ts-1));
        }
        s.push_back(tts);
    }
    REP(i,m){
        int tp;
        cin >> tp;
        
        p.push_back(tp);
    }

    LL count = 0;
    REP(i, pow(2,n)){
        LL t;
        bool ok = true;
        REP(j,m){
            t = bitCount(i & s[j]);
            if(t%2 != p[j]){
                ok = false;
                break;
            }
        }
        if (ok ) count++;
    }
    
    cout << count << endl;
    
    
    return 0;
     
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
const ll MOD = 1e9 + 7;
const int MAX = 1000000;

// fac[n]: n!
// finv[n]: (n!)^-1
// inv[n]: nの逆元
ll fac[MAX], finv[MAX], inv[MAX];

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

// 二項係数計算 (combination)
// nCk = (n!) * (k!)^-1 * ((n-k)!)^-1 として計算
ll comb(int n, int k) {
  if (n < k) {
    return 0;
  }
  if (n < 0 || k < 0) {
    return 0;
  }
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll X, Y;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> X >> Y;
  if ((X + Y) % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  ll n = (X + Y) / 3;
  if (abs(X - Y) > n) {
    cout << 0 << endl;
    return 0;
  }

  comb_init();
  ll ans = 0;
  ans = comb(n, (n / 2) - abs(X - Y) / 2);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 23680
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
			　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <memory>
#include <iomanip>

#define rep(i, n) for(Int (i) = 0; (i) < (n); ++(i))
using Int = int64_t;


void calc() {

	std::string S; std::cin >> S;
	Int N = S.size();
	std::string fir = S.substr(0, (N - 1) / 2);
	std::string sec = S.substr((N + 3) / 2 - 1, N - (N + 3) / 2 + 1);
	bool flag = true;

	{
		std::string tmp = S;
		std::reverse(tmp.begin(), tmp.end());
		if (tmp != S)flag = false;
	}

	{
		std::string tmp = fir;
		std::reverse(tmp.begin(), tmp.end());
		if (tmp != fir)flag = false;
	}

	{
		std::string tmp = sec;
		std::reverse(tmp.begin(), tmp.end());
		if (tmp != sec)flag = false;
	}

	if (flag)std::cout << "Yes";
	else std::cout << "No";

}


int main() {

	calc();

	return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc043/tasks/abc043_b

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  string s, ro = "";
  vector<char> r;

  cin >> s;

  for (size_t i = 0; i < s.length(); i++)
  {
    if (s[i] != 'B')
      r.push_back(s[i]);
    else if (0 < r.size())
      r.pop_back();
  }

  for (char c : r)
  {
    ro += c;
  }

  cout << ro << '\n';

  return 0;
}


Measured memory_bytes: 256
def main():
    PointNum = int(input())
    
    rPoint = []
    bPoint = []
    for i in range(PointNum):
        rPoint.append([int(i) for i in input().split()] )
    for i in range(PointNum):
        bPoint.append([int(i) for i in input().split()] )
        
#    print(rPoint)
#    print(bPoint)
    sorted_rPoint = sorted(rPoint)
    sorted_bPoint = sorted(bPoint)
#    print(sorted_rPoint)
#    print(sorted_bPoint)
    
    count = 0
    for bp in sorted_bPoint:
        ans_p = [-1, -1]
        IsAnsFind = False
        for rp in sorted_rPoint:
            if(bp[0]>rp[0] and bp[1]>rp[1]):
#                print(bp)
#                print(rp)
                IsAnsFind = True
                if(rp[1] > ans_p[1]):
                    ans_p = rp[:]
        if(IsAnsFind):
            count += 1
            sorted_rPoint.remove(ans_p)
    
    print(count)
    
if __name__=="__main__":
    main()

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

int left(int i){
  return 2 * i;
}

int right(int i){
  return 2 * i + 1;
}

void maxHeapify(int* h, int i, int n){
  
  int l, r, x, largest;
  
  l = left(i);
  r = right(i);
  
  if(l <= n && h[l] > h[i]) largest = l;
  else largest = i;
  
  if(r <= n && h[r] > h[largest]) largest = r;
  
  if(largest != i){
    x = h[i];
    h[i] = h[largest];
    h[largest] = x;
    
    maxHeapify(h, largest, n);
    
  }
  
}

void buildMaxHeap(int* h, int n){

  int i;
  
  for(i = n / 2; i > 0; i--) maxHeapify(h, i, n);

}
     
int main(){

  int i, n;
  int* h;

  scanf("%d", &n);

  h = malloc(sizeof(int) * n);

  for(i = 1; i <= n; i++) scanf("%d", &h[i]);

  buildMaxHeap(h, n);

  for(i = 1; i <= n; i++) printf(" %d", h[i]);

  printf("\n");

  return 0;

}

Measured memory_bytes: 2556
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const N = Number(input[0][0]);

  return N >= 1000 ? "ABD" : "ABC";
};

console.log(main(read()));


Measured memory_bytes: 29476
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  int n; cin >> n;
  vector<long long> l(n), r(n), mids;
  REP(i, n) {
    cin >> l[i] >> r[i];
    mids.emplace_back((l[i] + r[i]) / 2);
  }
  sort(ALL(mids));
  mids.erase(unique(ALL(mids)), mids.end());
  vector<vector<int> > mid(mids.size());
  REP(i, n) mid[lower_bound(ALL(mids), (l[i] + r[i]) / 2) - mids.begin()].emplace_back(i);
  if (mids.size() == 1) {
    long long len_mn = INF, len_mx = 0;
    REP(i, n) {
      len_mn = min(len_mn, r[i] - l[i] + 1);
      len_mx = max(len_mx, r[i] - l[i] + 1);
    }
    cout << len_mn + len_mx << '\n';
    return 0;
  }
  long long L = -LINF, R = LINF, ans = 0;
  map<long long, int> ls, rs;
  REP(i, n) {
    ++ls[l[i]];
    ++rs[r[i]];
  }
  REP(i, n) {
    --ls[l[i]];
    if (ls[l[i]] == 0) ls.erase(l[i]);
    --rs[r[i]];
    if (rs[r[i]] == 0) rs.erase(r[i]);
    long long now = max((*rs.begin()).first - (*ls.rbegin()).first + 1, 0LL);
    ans = max(ans, r[i] - l[i] + 1 + now);
    ++ls[l[i]];
    ++rs[r[i]];
  }
  REP(i, mid.size() - 1) {
    for (int e : mid[i]) {
      L = max(L, l[e]);
      R = min(R, r[e]);
      --ls[l[e]];
      if (ls[l[e]] == 0) ls.erase(l[e]);
      --rs[r[e]];
      if (rs[r[e]] == 0) rs.erase(r[e]);
    }
    long long now = max(R - L + 1, 0LL) + max((*rs.begin()).first - (*ls.rbegin()).first + 1, 0LL);
    ans = max(ans, now);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 20596
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define reps(i, s, n) for(int i = (s); i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, s, n) for(int i = (n) - 1; i >= (s); i--)
#define INF ~(1 << 31)
#define INFL ~(1LL << 63)
#define mod 998244353LL

int main()
{
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> d(k);
    rep(i, k){
        cin >> d[i].first >> d[i].second;
    }

    vector<ll> dp(n+1);
    dp[1] = 1;
    reps(i, 2, n+1){
        rep(j, k){
            int f = i - d[j].first, s = max(i - d[j].second, 1);
            if(f < 1) continue;
            else if(s == 1) dp[i] = (dp[i] + dp[f]) % mod;
            else dp[i] = (dp[i] - dp[s-1] + dp[f]) % mod;
        }
        dp[i] = (dp[i] + dp[i-1]) % mod;
    }
    if(dp[n] < dp[n-1]) dp[n] += mod;
    cout << dp[n] - dp[n-1] << endl;
}

Measured memory_bytes: 4840
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xとyを統合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    # xとyが同じグループかどうか判定する
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xのメンバーの要素を返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

U = UnionFind(N + 1)

for a, b in AB:
    if not U.same(a, b):
        U.union(a, b)

ans = 0
for i in range(1, N + 1):
    ans = max(ans, U.size(i))

print(ans)



Measured memory_bytes: 47196
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

template<typename T>
std::vector<std::vector<T>> mk2d(size_t s1, size_t s2, T const& val) {
  std::vector<T> tmp(s2, val);
  return std::vector<std::vector<T>>(s1, tmp);
}

bool next_choice(std::vector<int>& ixh, int N) {
  int h = ixh.size();
  for(int i = h-1, n = N; i >= 0; --i, --n) {
    if(ixh[i]+1 < n) {
      int v = ixh[i]+1;
      for(int j = i; j < h; ++j) ixh[j] = v++;
      return true;
    }
  }
  return false;
}

int calc(std::vector<int>& ix) {
  int res = 0;
  for(int i = 0; i < ix.size()-1; ++i) {
    if(ix[i] == i) continue;
    for(int j = i+1; j < ix.size(); ++j) if(ix[j]==i) {
      res += j-i;
      for(int k = j; k > i; --k) ix[k]=ix[k-1];
      break;
    }
  }
  return res;
}

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  auto ab = mk2d<int>(2, N, 0);
  for(int i = 0; i < N; ++i) std::cin >> ab[i%2][i];
  for(int i = 0; i < N; ++i) std::cin >> ab[(i+1)%2][i];
  std::vector<int> ix(N), ixh((N+1)/2), ixe((N+1)/2), ixo(N/2);
  std::vector<bool> used(N);
  std::iota(ix.begin(), ix.end(), 0);
  std::iota(ixh.begin(), ixh.end(), 0);
  
  int ans = 10000;
  // check all possibility; MAX: comb(18,9) < 50000
  for(;;) {
    // prepare even
    std::copy(ixh.begin(), ixh.end(), ixe.begin());
    std::sort(ixe.begin(), ixe.end(), 
      [&](int l, int r){ return ab[0][l] < ab[0][r]; });
    
    // prepare odd
    std::fill_n(used.begin(), N, false);
    for(int i: ixh) used[i] = true;
    ixo.resize(0);
    for(int i = 0; i < N; ++i) if(!used[i]) ixo.push_back(i);
    std::sort(ixo.begin(), ixo.end(),
      [&](int l, int r){ return ab[1][l] < ab[1][r]; });
    
    // check if sorted
    bool sorted = true;
    for(int i = 0; i < ixo.size(); ++i) {
      if(ab[0][ixe[i]] > ab[1][ixo[i]]) { sorted = false; break; }
      if(i+1 < ixe.size() &&  ab[1][ixo[i]] > ab[0][ixe[i+1]]) { sorted = false; break; }
    }
    if(sorted) {
      // merge
      for(int i = 0; i < ixe.size(); ++i) ix[i*2] = ixe[i];
      for(int i = 0; i < ixo.size(); ++i) ix[i*2+1] = ixo[i];
      ans = std::min(ans, calc(ix));
    }
    
    if(!next_choice(ixh, N)) break;
  }
  if(ans > 9999) ans = -1;
  fin(ans);
  return 0;
}


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

int n,m;
char A[55][55];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>A[i][j];
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(A[i][j]=='#')
            {
                if((j!=m-1&&A[i][j+1]=='#')||(i!=n-1&&A[i+1][j]=='#')||(i!=0&&A[i-1][j]=='#')||(j!=0&&A[i][j-1]=='#'))
                    continue;
                else
                {
                    cout<<"No\n";
                    return 0;
                }
            }

        }
    cout<<"Yes\n";
    return 0;
}


Measured memory_bytes: 256
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import ceil
def I(): return int(input())
def MI(): return map(int, input().split())

def main():
    H, W = MI()
    if H==1 or W==1:
        print(1)
    else:
        print(ceil(H*W/2))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
const int maxn = 200200;
int arr[maxn];
int main(){
    long long sum = 0;
    int n;
    cin >> n;
    n++;
    for(int e = 2; e <= n; e++) cin >> arr[e];
    arr[1] = 0;
    arr[n+1] = 0;
    n++;
    for(int e = 2; e <= n; e++) sum += abs(arr[e] - arr[e-1]);
    for(int e = 1; e <= n; e++){
        if(e == 1 || e == n) continue;
        long long now = sum;
        if(e + 1 <= n) now -= abs(arr[e+1] - arr[e]);
        if(e - 1 >= 1) now -= abs(arr[e-1] - arr[e]);
        if(e + 1 <= n && e - 1 >= 1) now += abs(arr[e+1] - arr[e-1]);
        cout << now << endl;
    }
    // cout << endl;
    return 0;
}


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

int main()
{
	int N;
	int X[200010]={};
	int s[200010]={};
	
	cin >> N;
	for(int i=1;i<=N;i++)
	{
		cin >> X[i];
		s[i]=X[i];
	}
	
	sort(s+1,s+N+1);
	
	for(int i=1;i<=N;i++)
	{
		if(X[i]<=s[N/2])
			cout << s[N/2+1];
		else
			cout << s[N/2];
		cout << endl;
	}
	return 0;
}


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

int res = 0;

const int maxn = 500500;
int d[maxn][3];

void uax(int& a, int b) {
  a = max(a, b);
}

void solve(string s) {
  //cerr << "str: " << s << '\n';
  int n = int(s.size());
  int cnt = 0;
  vector<int> b;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '1') {
      ++cnt;
    } else {
      b.push_back(cnt);
      cnt = 0;
    }
  }
  b.push_back(cnt);
  if (int(b.size()) <= 1)
    return;
  for (int i = 0; i < int(b.size()) + 5; ++i) {
    for (int j = 0; j < 3; ++j) {
      d[i][j] = -1e9;
    }
  }
  d[0][0] = 0;
  for (int i = 0; i < int(b.size()) - 1; ++i) {
    for (int j = 0; j < 3; ++j) {
      bool can = b[i] > 1 || j != 1;
      for (int k = 0; k < 3; ++k) {
        if (!can && k != 0)
          continue;
        if (j == 2 && k == 1)
          continue;
        if (k == 0) {
          uax(d[i + 1][k], d[i][j]);
        } else if (k == 1) {
          uax(d[i + 1][k], d[i][j] + b[i] - (j != 0));
        } else if (k == 2) {
          uax(d[i + 1][k], d[i][j] + b[i + 1] - (j == 2));
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i < 3; ++i) {
    res = max(res, d[int(b.size()) - 1][i]);
  }
  //cerr << res << '\n';
  ::res += res;
}

signed main() {
#ifdef LOCAL
  assert(freopen("d.in", "r", stdin));
#endif
  int n;
  string s;
  cin >> n >> s;
  for (int l = 0; l < n; ++l) {
    if (s[l] != '1')
      continue;
    int r = l + 1;
    while (r < n) {
      if (s[r] == '1') {
        ++r;
        continue;
      }
      if (r + 1 < n && s[r + 1] == '1') {
        r += 2;
        continue;
      }
      break;
    }
    solve(s.substr(l, r - l));
    l = r - 1;
  }
  cout << res << '\n';
}

Measured memory_bytes: 1412
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//const MAX:usize = 100006;
//const INF:u64 = u64::max_value();

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

fn main() {
    let n:u32 = read();
    let mut v:Vec<f64> = (0..n).map(|_| read::<f64>()).collect();

    v.sort_by_key(|&x| Total(x));
    //v.reverse();
    //println!("{:?}", v);

    let mut ans:f64 = v[0];
    for i in 1..n {
        ans /= 2.0;
        ans += v[i as usize]/2.0;
        //println!("{}", ans);
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352