akhauriyash/Code-Regression huggingface dataset:
import Data.Time

solve :: Char -> Char
solve 'A' = 'T'
solve 'T' = 'A'
solve 'C' = 'G'
solve 'G' = 'C'

main :: IO ()
main = do
  s <- getLine
  date <- parseTimeM True defaultTimeLocale "%Y/%m/%d" s :: IO Day
  let threshold = fromGregorian 2019 4 30
  putStrLn $ if diffDays date threshold <= 0 then "Heisei" else "TBD"


Measured memory_bytes: 508
S = list(input())
ans = [0]*len(S)
odd_count = 0
even_count = 1
base_point = 0
for i in range(1, len(S)):
    if S[i-1] == 'R':
        if S[i] == 'R':
            if i%2 == 0:
                even_count += 1
            elif i%2 == 1:
                odd_count += 1
            base_point = i

        elif S[i] == 'L':
            if i%2 == 0:
                even_count += 1
            elif i%2 == 1:
                odd_count += 1
            if base_point%2 == 0:
                ans[base_point] += even_count
                ans[base_point+1] += odd_count
            else:
                ans[base_point] += odd_count
                ans[base_point+1] += even_count
            odd_count = 0
            even_count = 0

    elif S[i-1] == 'L':
        if S[i] == 'L':
            if i%2 == 0:
                even_count += 1
            if i%2 == 1:
                odd_count += 1
        elif S[i] == 'R':
            if base_point%2 == 0:
                ans[base_point] += even_count
                ans[base_point+1] += odd_count
            else:
                ans[base_point] += odd_count
                ans[base_point+1] += even_count
            if i%2 == 0:
                even_count = 1
                odd_count = 0
            elif i%2 == 1:
                odd_count = 1
                even_count = 0
            base_point = i

    if i == len(S)-1:
        if base_point%2 == 0:
            ans[base_point] += even_count
            ans[base_point+1] += odd_count
        elif base_point%2 == 1:
            ans[base_point] += odd_count
            ans[base_point+1] += even_count

ans = ' '.join(map(str, ans))
print(ans)

Measured memory_bytes: 11216
#include <iostream>
#include <string>
using namespace std;
string s;
int a[4],sum=0;
int main(){
	getline(cin,s);
	for(int i=0;i<4;i++)a[i]=s[i]-48;
	for(int i=0;i<2;i++){//+ - 
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				sum=a[0];
				if(i==0)sum+=a[1];
				if(i==1)sum-=a[1];
				if(j==0)sum+=a[2];
				if(j==1)sum-=a[2];
				if(k==0)sum+=a[3];
				if(k==1)sum-=a[3];
				if(sum==7){
					cout<<a[0];
					if(i==0)cout<<"+";
					else cout<<"-";
					cout<<a[1];
					if(j==0)cout<<"+";
					else cout<<"-";
					cout<<a[2];
					if(k==0)cout<<"+";
					else cout<<"-";
					cout<<a[3];
					cout<<"=7";
					return 0;
				}
				sum=0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }

vector<ll> all;

void dfs(int d,ll val){
    all.push_back(val);
    if(d == 10)return;
    repp(i,-1,2){
        int add = val%10 + i;
        if(0 <= add && add <= 9)dfs(d+1,val*10 + add);
    }
}

int main() {
    ll n;
    cin >> n;
    rep(i,9)dfs(1,i+1);
    sort(begin(all),end(all));
    cout << all[n-1] << endl;
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

int main()
{
	int k, t;
	cin >> k >> t;
	vector<int> a(t);
	REP(i, t) cin >> a[i];

	sort(ALL(a), greater<int>());

	cout << max(a[0]-1-(k-a[0]), 0) << endl;
}


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

namespace ProblemD
{
    class Program
    {
        static void Main(string[] args)
        {
            //var test = new long[1000];
            //long i = 101;
            //test[100] = 10000000000;
            //var find_test = false;
            //while(!find_test)
            //{
            //    test[i] = i * i * i * i * i;
            //    if (test[i] - test[i - 1] > 1000000000)
            //        find_test = true;
            //    i++;
            //}
            var x = long.Parse(Console.ReadLine());
            var memo = new Dictionary<long, long>();
            bool find = false;
            for (long i = 1; i < 122; i++)
            {
                if (!memo.ContainsKey(i))
                    memo[i] = i * i * i * i * i;
                var a = memo[i];
                for (long j = -121; j < i; j++)
                {
                    if (!memo.ContainsKey(j))
                        memo[j] = j * j * j * j * j;

                    if (x == a - memo[j])
                    {
                        Console.WriteLine(i + " " + j);
                        find = true;
                        break;
                    }
                }
                if (find) break;

            }
        }
    }
}


Measured memory_bytes: 27792
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
	int n, x;
	cin >> n;
	string command;
	list<int> a;
	for (int i = 0; i < n; ++i) {
		cin >> command;
		if ("delete" == command) {
			cin >> x;
			list<int>::iterator b = find(a.begin(), a.end(), x);
			if (a.end() != b) a.erase(b);
		}
		else if ("deleteFirst" == command) a.pop_front();
		else if ("deleteLast" == command) a.pop_back();
		else {
			cin >> x;
			a.push_front(x);
		}
	}
	for (list<int>::iterator i = a.begin(); i != prev(a.end()); ++i) cout << *i << ' ';
	cout << a.back() << endl;
}


Measured memory_bytes: 34436
s = gets.chomp

def count(str)
  a, d, count= 0, 0, 0
  str.chars.each do |chr|
    a+=1 if chr=='A'
    count+=a if chr=='D'
  end
  count
end

s = s.gsub('BC', 'D')

s = s.chars.map{|e|
  if e=='A' || e=='D'
    e
  else
    '|'
  end
}.join.split('|').reject{|e|e==''}

s = s.map{|a|count(a)}

s=[0] if s.empty?
s=s.inject(:+)

puts s

Measured memory_bytes: 34360
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    
    int count = 0;
    
    for(int i = 1; i <= N; i ++){
        if(i % 2 == 1){
            count ++;
        }
    }
    cout << (double)count/N << endl;    
}


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

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

template<typename T, typename U>
istream& operator >> (istream& istr, pair<T,U>& p){
    istr >> p.first >> p.second;
    return istr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<T>& v){
    if(!v.empty()){
        ostr << v.front();
        for(auto itr = ++v.begin(); itr != v.end(); itr++)
            // ostr << *itr;
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, pair<T,U>& p){
    // ostr << p.first << p.second;
    // ostr << p.first << ", " << p.second;
    ostr << "(" << p.first << ", " << p.second << ")";
    return ostr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<vector<T>>& vv){
    if(!vv.empty()){
        ostr << vv.front();
        for(auto itr = ++vv.begin(); itr != vv.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, vector<pair<T,U>>& vp){
    if(!vp.empty()){
        ostr << vp.front();
        for(auto itr = ++vp.begin(); itr != vp.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<double> vd;
// vll v(n); v[i]=x;
typedef vector<vll> vvll;
typedef vector<vc> vvc;
typedef vector<vd> vvd;
// vvll v(m,vll(n)); v[i][j]=x;
typedef pair<ll,ll> pll;
typedef pair<double,double> pd;
typedef vector<pll> vpll;
typedef vector<pd> vpd;
// vpll v(n); v[i]=make_pair(x,y); v[i].first/second;
// v.front() : v[0]
// v.back()  : v[v.size()-1]

#define PI 3.1415926535897932
#define EPS 1e-12
#define INF ((ll)1e+12)
#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<=(b); i++)
#define FORR(i,a,b) for(ll i=(b); i>=(a); i--)
#define fix(x) cout << fixed << setprecision(x)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()

template<typename T> T sum(vector<T>& v){return accumulate(all(v), (T)0);}
template<typename T> inline void sort(vector<T>& v){sort(all(v));}
template<typename T> inline void rsort(vector<T>& v){sort(all(v), greater<T>());}
template<typename T> inline void chmin(T& a, T b){if(a>b) a=b;}
template<typename T> inline void chmax(T& a, T b){if(a<b) a=b;}

int main(){
    ll n, a, b;
    cin >> a >> b >> n;
    if(n%b==0){
        cout << (a*(n-1))/b-a*((n-1)/b) << endl;
    }
    else{
        ll ans = (a*n)/b-a*(n/b);
        n = (n/b)*b-1;
        ll ans2 = (a*n)/b-a*(n/b);
        chmax(ans, ans2);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
package main

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

func main() {
	sc := NewScanner()
	n := sc.NextInt()
	s := sc.NextLine()
	r := []rune(s)
	ans := ""
	for i := 0; i < len(r); i++ {
		tmp := (int(r[i]) + n)
		//		fmt.Printf("%+v\n", tmp) // output for debug
		if tmp >= 91 {
			tmp -= 26
		}
		//		fmt.Printf("%+v\n", tmp) // output for debug
		ans += string(rune(tmp))
	}
	fmt.Printf("%v\n", ans)

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 7680
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

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

	cin >> N;
	for (int i = 1; i < N; i++) {
		M += (N - 1) / i;
	}
	cout << M << endl;
}

Measured memory_bytes: 3636
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second
#define FOR(itr,data) for(__typeof((data).begin()) itr=(data).begin();itr!=(data).end();++itr)

typedef unsigned long long UInt64;
typedef long long Int64;

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

using namespace std;

typedef pair<int ,int > P;

int n;

class edge
{
	public:
	int to;
	int cost;
	edge(int _to,int _cost)
	{
		this->to=_to;
		this->cost=_cost;
	}
};

int d[10];
vector<edge> G[10];

int dijkstra(int s)
{
	priority_queue<P,vector<P>, greater<P> > que;
	fill(d,d+10,INF);
	d[s]=0;
	que.push(P(0,s));

	while(que.size())
	{
		P p=que.top();que.pop();

		rep(i,G[p.sc].size())
		{
			edge e=G[p.sc][i];
			if(d[e.to]>d[p.sc]+e.cost)
			{
				d[e.to]=d[p.sc]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		
		}
	}
	int res=0;
	rep(i,10)
	{
		if(d[i]!=INF)
			res+=d[i];
	}
	return res;
}


void solve()
{
	rep(i,10) G[i].clear();

	int mi=INF;
	int ans;
	set<int> city;

	rep(i,n)
	{
		int a,b,c;
		cin>>a>>b>>c;
		G[a].pb(edge(b,c));
		G[b].pb(edge(a,c));
		city.insert(a);
		city.insert(b);
	}

	FOR(it,city)
	{
		int tmp=dijkstra(*it);
		if(tmp<mi)
		{
			mi=tmp;
			ans=*it;
		}
	}
	cout<<ans<<" "<<mi<<endl;
}




int main()
{
	while(cin>>n)
	{
		if(!n) return 0;
		solve();


	}
		return 0;
}

Measured memory_bytes: 1196
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using P  = pair<ll,ll>;
ll r,c,n;

ll calc(ll x, ll y){
    if(x==0) return y;
    if(y==c) return x+c;
    if(x==r) return r+2*c-y;
    return 2*r+2*c-x;
}

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

    cin>>r>>c>>n;
    map<ll,int> mp;
    for(int i=1;i<=n;i++){
        ll sx,sy,gx,gy;
        cin>>sx>>sy>>gx>>gy;
        if((sx!=0 && sx!=r && sy!=0 && sy!=c)) continue;
        if((gx!=0 && gx!=r && gy!=0 && gy!=c)) continue;
        //cout<<i<<endl;
        mp[calc(sx,sy)]=i;
        //cout<<i<<" "<<calc(sx,sy)<<endl;
        mp[calc(gx,gy)]=i;
        //cout<<i<<" "<<calc(gx,gy)<<endl;
    }
    stack<int> st;
    for(auto itr=mp.begin();itr!=mp.end();itr++){
        int v=(*itr).second;
        //cout<<v<<endl;
        if(st.empty()){
            st.push(v);
            continue;
        }
        if(st.top()==v){
            st.pop();
            continue;
        }
        st.push(v);
    }
    if(st.empty()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


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

#define REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define RREP(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < ll(n); ++i)
#define RFOR(i, m, n) for (ll i = ll(n) - 1; i >= ll(m); --i)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vi v(n);
	REP(i, n) cin >> v[i];
	vi a(n + 1), b(n + 1);
	REP(i, n) {
		a[i + 1] = max(a[i], v[i]);
	}
	RREP(i, n) {
		b[i] = max(b[i + 1], v[i]);
	}
	REP(i, n) {
		cout << max(a[i], b[i + 1]) << endl;
	}
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, K, S);
  int ans = 0;
  rep(i, 0, min(K, S) + 1) {
    rep(j, 0, min(K, S - i) + 1) {
      int k = S - i - j;
      if (k >= 0 && k <= K) ans++;
    }
  }
  print(ans);
}


Measured memory_bytes: 256
def ceil(a, b):
	return -(-a//b)

n = int(input())
chokudai, aoki = 0, 0
for i in range(n):
	t, a = map(int,input().split())
	if i == 0:
		chokudai, aoki = t, a
		continue
	bairitsu = max(ceil(chokudai, t), ceil(aoki, a))
	t *= bairitsu
	a *= bairitsu
	#print(t, a)
	chokudai, aoki = t, a
print(chokudai + aoki)

Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define pb(a) push_back(a)
using namespace std;
typedef long long ll;

int main()
{
    ll N;
    cin >> N;
    ll ans = 0;
    ll r = (-1 + sqrt(1 + 4 * N)) / 2;
    for (ll i = 1; i < r + 1; i++)
    {
        if (N % i == 0 && N / i - 1 > i)
            ans += N / i - 1;
    }

    cout << ans;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;

  SegmentTree(){}
  SegmentTree(F f,T ti):f(f),ti(ti){}

  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }

  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  void set_val(int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(int a,int b){
    if(a>=b) return ti;
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  vector<int> ps(n);
  for(int i=0;i<n;i++) cin>>ps[i];

  vector<int> rev(n+1),v1(n),v2(n);
  for(int i=0;i<n;i++){
    rev[ps[i]]=i;
    if(i%2==0) v1[i]=ps[i],v2[i]=n+1;
    if(i%2==1) v2[i]=ps[i],v1[i]=n+1;
  }

  auto f=[&](int a,int b){return min(a,b);};
  SegmentTree<int> seg1(f,n+2),seg2(f,n+2);
  seg1.build(v1);
  seg2.build(v2);

  using P = pair<int, int>;
  using PP = pair<P, P>;
  priority_queue<PP, vector<PP>, greater<PP> > pq;
  auto push=
    [&](int l,int r){
      assert(l<=r);
      assert(~(r-l)&1);
      if(l==r) return;
      int x=((~l&1)?seg1:seg2).query(l,r);
      int y=(( l&1)?seg1:seg2).query(rev[x],r);
      pq.emplace(P(x,y),P(l,r));
    };
  push(0,n);

  vector<int> qs;
  while(!pq.empty()){
    PP pp=pq.top();pq.pop();
    qs.emplace_back(pp.first.first);
    qs.emplace_back(pp.first.second);
    int i=rev[pp.first.first];
    int j=rev[pp.first.second];
    int l=pp.second.first;
    int r=pp.second.second;
    push(l,i);
    push(i+1,j);
    push(j+1,r);
  }

  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<qs[i];
  }
  cout<<endl;
  return 0;
}


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

class Node{
    private:
        int data;
        Node* next;
        Node* prev;
    public:
        Node(){next = NULL; prev = NULL;}
        void setData(int data){this->data = data;}
        void setNext(Node* next){this->next = next;}
        void setPrev(Node* prev){this->prev = prev;}

        int getData(){return data;}
        Node* getNext(){return next;}
        Node* getPrev(){return prev;}
};

class List{
    private:
        Node* head;
        Node* tail;
    public:
        List(){
            head = new Node;
            tail = new Node;
            head->setPrev(tail);    //headの後ろがtail
            tail->setNext(head);
        }
        void insert(int x){
            Node* newNode;
            newNode = new Node;
            newNode->setData(x);
            newNode->setNext(head);
            newNode->setPrev(head->getPrev());
            head->getPrev()->setNext(newNode);
            head->setPrev(newNode);
        }
        void deleteNode(int x){
            tail->setData(x);
            Node* i = head->getPrev();
            while(i->getData()!=x)
                i = i->getPrev();
            if(i!=tail){
                i->getNext()->setPrev(i->getPrev());
                i->getPrev()->setNext(i->getNext());
                delete i;
            }
        }
        void deleteFirst(){
            Node* tmp = head->getPrev();
            tmp->getPrev()->setNext(head);
            head->setPrev(tmp->getPrev());
            delete tmp;
        }
        void deleteLast(){
            Node* tmp = tail->getNext();
            tmp->getNext()->setPrev(tail);
            tail->setNext(tmp->getNext());
            delete tmp;
        }
        void showList(){
            Node* i = head->getPrev()->getPrev();
            cout << head->getPrev()->getData();
            while(i!=tail){
                cout << " " << i->getData();
                i = i->getPrev();
            }
            cout << endl;
        }
        ~List(){
            Node* tmp = head->getPrev();
            while(tmp!=tail){
                delete tmp->getNext();
                tmp = tmp->getPrev();
            }
            delete tmp;
        }
};

int main(){
    List list;
    unsigned n;
    string command; //コマンド
    int x;  //値
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> command;
        if(command=="deleteFirst"){
            list.deleteFirst();
        }else if(command=="deleteLast"){
            list.deleteLast();
        }else if(command=="insert"){
            cin >> x;
            list.insert(x);
        }else if(command=="delete"){
            cin >> x;
            list.deleteNode(x);
        }else{
            cout << "Unknown command" << endl;
        }
    }
    
    list.showList();

    return 0;
}


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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    long long el = c - a - b;
    if (el < 0)
    {
        cout << "No\n";
        return 0;
    }
    long long foo = 4LL * a * b;
    if (foo < el * el)
    {
        cout << "Yes\n";
        return 0;
    }
    cout << "No\n";

    return 0;
}


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

typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 184467440737095516;

ll dp[100100], arr[100100], n, ans, cnt, sum;

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

	cin >> n;
	for (ll i = 1; i <= n; i++){
		cin >> arr[i];
	}
	dp[1] = 0;
	dp[2] = abs(arr[2] - arr[1]);
	for (ll i = 3; i <= n; i++){
		dp[i] = min(dp[i-1] + abs(arr[i] - arr[i - 1]), dp[i-2] + abs(arr[i] - arr[i-2]));
	}
	cout << dp[n] << '\n';
}
  

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

char maze[1010][1010];
int H,W;
int d[1010][1010];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int bfs(){
    // O(HW)
    queue<pair<int,int>> que;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            d[i][j]=INF;
        }
    }
    que.push(make_pair(0,0));
    d[0][0]=0;
    while(!que.empty()){
        pair<int,int> p=que.front();
        que.pop();
        for(int i=0;i<4;i++){
            int nx=p.first+dx[i];
            int ny=p.second+dy[i];
            if(0<=nx && nx<H && 0<=ny && ny<W && maze[nx][ny]!='#' && d[nx][ny]==INF){
                que.push(make_pair(nx,ny));
                d[nx][ny]=d[p.first][p.second]+1;
            }
        }
    }
}

int main(){
    cin>>H>>W;
    int cnt=0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>maze[i][j];
            if(maze[i][j]=='#') cnt++;
        }
    }
    bfs();
    if(d[H-1][W-1]==INF) cout<<-1<<endl;
    else cout<<H*W-cnt-(d[H-1][W-1]+1)<<endl;
}

Measured memory_bytes: 2432
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define log(i,n) log(n)/log(i);
using namespace std;
typedef long long ll;


int main()
{
	ll cnt = 0;
	string s;
	cin >> s;
	vector<char>stack;
	for (ll i = 0; i < s.length(); i++) {
		if (stack.size() == 0)stack.push_back(s[i]);
		else if (stack[stack.size() - 1] == '0' && s[i] == '1')cnt++, stack.pop_back();
		else if (stack[stack.size() - 1] == '1' && s[i] == '0')cnt++, stack.pop_back();
		else stack.push_back(s[i]);
	}
	cout << cnt * 2 << endl;
}



Measured memory_bytes: 640
#D
A, B = map(int, input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)
print(len(prime_factorize(A) & prime_factorize(B)) + 1)

Measured memory_bytes: 3064
#include<stdio.h>
int main(void){

int a,b,c,i=0,count=0;
scanf("%d %d %d",&a,&b,&c);
for(i=a;i<=b;i++){
if(c%i==0){
count=count+1;
}
}
printf("%d\n",count);

return(0);
}


Measured memory_bytes: 2104
a=int(input()) #500
b=int(input()) #100
c=int(input()) #50
x=int(input())

cnt=0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if (i*500+j*100+k*50)==x:
        cnt+=1
print(cnt)

Measured memory_bytes: 3064
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
use std::collections::HashMap;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let n: usize = read_as_vec()[0];
    let a: Vec<usize> = read_as_vec();

    if n == 3{
        if a[0] ^ a[1] == a[2]{
            println!("Yes");
        }else{
            println!("No");            
        }
        return;
    }

    if a.iter().all(|x| *x == 0){
        println!("Yes");
        return;
    }

    let mut hash: HashMap<usize, usize> = HashMap::new();

    for elem in a{
        *hash.entry(elem).or_insert(0) += 1;
    }

    //println!("{:?}", hash);

    if n%3 != 0 || (hash.len() != 2 && hash.len() != 3) {
        println!("No");
        return;
    }

    if hash.len() == 2{
        let another_key = *hash.keys().filter(|key| **key != 0).nth(0).unwrap();
        let zero_key = 0;

        if *hash.get(&zero_key).unwrap() == n/3 && *hash.get(&another_key).unwrap() == n*2/3{
            println!("Yes");            
        }else{
            println!("No");
        }
    }else{
        if hash.iter().any(|(_, value)| *value != n/3){
            println!("No");
            return;
        }

        let mut tmp: Vec<usize> = Vec::new();
        for key in hash.keys(){
            tmp.push(*key);
        }

        if tmp[0] ^ tmp[1] == tmp[2]{
            println!("Yes");
        }else{
            println!("No");
        }
    }
        
    return;        
}


Measured memory_bytes: 12540
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll mul(ll a, ll b){
    return ((a%mod) * (b%mod))%mod;
}
ll power(ll a, ll b){
    ll z = 1; ll x = a;
    while(b>0){
        if (b&1)z = mul(z, x);
        x = mul(x, x);
        b >>= 1;
    }
    return z;
}
int main()
{
    string s;
    cin>>s;
    ll n = s.length();
    ll l[n], r[n];
    l[n-1] = n-1;
    r[0] = 0;
    for (int i=1; i<n; i++)if (s[i] == 'R')r[i]=i; else r[i] = r[i-1];
    for (int i=n-2; i>=0; i--)if (s[i]=='L')l[i] = i; else l[i] = l[i+1];
    ll store[n]; memset(store, 0, sizeof(store));
    for (int i=0; i<n; i++){
        if (s[i] == 'L')continue;
        ll x = l[i] - i;
        if (x&1)store[l[i]-1]++;
        else store[l[i]]++;
    }
    for (int i=0; i<n; i++){
        if (s[i]=='R')continue;
        ll x = i - r[i];
        if (x&1)store[r[i]+1]++;
        else store[r[i]]++;
    }
    for (int i=0; i<n; i++)cout<<store[i]<<" ";
}

Measured memory_bytes: 6048
/*
“Being happy doesn't mean that everything is perfect.
It means that you decided to look beyond the imperfections.”
*/

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


#define int int64_t
#define pr(x) cout << x << endl;
#define vi vector<int>
#define vii vector< vector<int> >
#define mp make_pair
#define ii pair<int,int>
#define fr(i,x,n) for(i = x ; i< n ; i++)
#define f(i,n) for(i = 0 ; i< n ; i++) 
#define ff first
#define ss second
#define pb push_back
#define SIZE 200001
#define mod 1000000007
#define int_max 1e12
int i, j, k, l, n, a, c, nn, t, dot=0, toko=0, x, y, z;
// void solve();



int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
//	freopen("input.txt", "r",stdin);
//	freopen("output.txt", "w", stdout);
   cin >> n;
   k=0;
   for(i=1;i<=n;i++)
   {
       if(!(i%5==0 or i%3==0)) k+=i;

   }

   cout << k ;
}







Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
#define fo(i,n) for(ll int i=0;i<n;++i)
#define fos(j,i,n) for(ll int j=i;j<n;++j)
#define N 100004
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define abs(x) (x<0?(-x):x)
#define dis(k) cout << k << endl
#define forr(i,n) for( ll int i= n-1;i>=0;--i)
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl;
typedef vector< ll int > vi;
typedef vector< vi > vvi;
typedef pair< ll int,ll int > ii;
int main(){
	fast;
	int t;
	t=1;
	//cin >> t;
	while(t--){
		int n,mac=0;
		cin >> n;
		string s;
		map<string,int > m;
		fo(i,n){
			cin >> s;
			m[s]++;
			if(m[s]>mac)
				mac=m[s];
		}
		set<string> se;
		for(auto x: m){
			if(x.second==mac)
			se.insert(x.first);
		}
		for(auto c: se)
			dis(c);
	
	}
	return 0;
}



Measured memory_bytes: 33280
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200006;
const int INF = (int)1e9;
int e_num = 1, S, T;
int hed[maxn], dep[maxn];
struct Edge {
  int from, to, nxt, c;
} edge[maxn * 4];
void addedge(int from, int to, int c) {
  edge[++e_num] = (Edge){from, to, hed[from], c};
  hed[from] = e_num;
}
void adde(int from, int to, int c) {
  addedge(from, to, c);
  addedge(to, from, 0);
}
int que[maxn + 5], head = 0, tail = 0;
int tim, vis[maxn];
bool bfs() {
  head = tail = 0;
  que[tail++] = S;
  tim++;
  dep[S] = 1;
  vis[S] = tim;
  while (head != tail) {
    int cur = que[head++]; head %= maxn;
    for (int i = hed[cur]; i; i = edge[i].nxt) {
      int to = edge[i].to;
      if (vis[to] != tim && edge[i].c) {
        dep[to] = dep[cur] + 1;
        vis[to] = tim;
        que[tail++] = to; tail %= maxn;
      }
    }
  }
  return vis[T] == tim;
}
int hed2[maxn];
int dfs(int x, int flow) {
  if (x == T) return flow;
  int ret = 0;
  for (int &i = hed2[x]; i; i = edge[i].nxt) {
    int to = edge[i].to;
    if (vis[to] == tim && dep[to] == dep[x] + 1 && edge[i].c) {
      int tmp = dfs(to, min(flow, edge[i].c));
      edge[i].c -= tmp;
      edge[i ^ 1].c += tmp;
      flow -= tmp;
      ret += tmp;
      if (!flow) {
        break;
      }
    }
  }
  if (!ret) dep[x] = 0;
  return ret;
}
int dinic() {
  int ret = 0;
  while (bfs()) {
    memcpy(hed2, hed, sizeof hed);
    ret += dfs(S, INF);
  }
  return ret;
}

int n, p[maxn], q[maxn], bp[maxn], bq[maxn], cnt;
void solve(int *p, int *bel) {
  for (int i = 1; i <= n; i++) if (!bel[i]) {
    int x = i;
    ++cnt;
    do {
      bel[x] = cnt;
      x = p[x];
    } while (x != i);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
    ++p[i];
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &q[i]);
    ++q[i];
  }
  solve(p, bp);
  solve(q, bq);
  S = 0, T = ++cnt;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (p[i] == i && q[i] == i) {
      ans++;
    } else if (q[i] == i) {
      adde(S, bp[i], 1);
    } else if (p[i] == i) {
      adde(bq[i], T, 1);
    } else {
      addedge(bq[i], bp[i], 1);
      addedge(bp[i], bq[i], p[i] == q[i]);
    }
  }
  ans += dinic();
  printf("%d\n", n - ans);
  return 0;
}



Measured memory_bytes: 13952
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include <string.h>
using namespace std;
int a[100005];
int main() {
	string s;
	cin >> s;
	string a = "abc";
	set<char> c;
	for (int i = 0; i < 3; i++) {
		c.insert(s[i]);
		if (a.find(s[i]) == string::npos) {
			cout << "No" << endl;
			return 0;
		}
	}
	if (c.size() != 3) {
		cout << "No" << endl;
		return 0;

	}
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
str = gets.chomp
n = gets.chomp.to_i
while line = gets
  cmd, a, b, p = line.chomp.split(' ')
  a = a.to_i
  b = b.to_i
  if cmd == 'print'
    puts str[a..b]
  elsif cmd == 'reverse'
    str[a..b] = str[a..b].reverse
  elsif cmd == 'replace'
    str[a..b] = p
  end
end

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

map<pair<ll,ll>,ll> mp;
ll knapsack01(ll N, ll W, vector<ll> v, vector<ll> w){
    if(N==0||W==0) return 0;
    if(mp.find({N,W})!=mp.end()){
        return mp[{N,W}];
    }
    else{
        if(w[N-1]>W){
            mp[{N,W}] = knapsack01(N-1,W,v,w);
            return mp[{N,W}];
        }
        else{
            mp[{N,W}] = max(v[N-1]+knapsack01(N-1,W-w[N-1],v,w),knapsack01(N-1,W,v,w));
            return mp[{N,W}];
        }
    }
}

ll t[101][100001];
ll DPknapsack01(ll N, ll W, vector<ll> v, vector<ll> w){
    for(int i = 0; i <= N; i++){
        t[i][0]=0;
    }
    for(int j = 0; j <= W; j++){
        t[0][j]=0;
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= W; j++){
            if(w[i-1]>j)
                t[i][j] = t[i-1][j];
            else
                t[i][j] = max(t[i-1][j],v[i-1]+t[i-1][j-w[i-1]]);
        }
    }
    return t[N][W];
}

ll ans[100001];
ll DP2knapsack01(ll N, ll W, vector<ll> v, vector<ll> w){
    for(ll i = 0; i <= W; i++){
        ans[i]=0;
    }
    for(ll i = 1; i <= N; i++){
        ll temp[100001];
        temp[0]=0;
        for(ll j = 1; j <= W; j++){
            if(w[i-1]<=j)
                temp[j] = max(ans[j], v[i-1]+ans[j-w[i-1]]);
            //cout << ans[j] << ' ';
        }
        for(ll j = 0; j <=W; j++)
            ans[j]=temp[j];
        //cout << '\n';
    }
    return ans[W];
}


int main(){
    ll N,W;
    cin >> N >> W;
    vector<ll> v,w;
    vector<pair<ll,ll>> obj;
    for(ll i = 0; i < N; i++){
        ll x,y;
        cin >> x >> y;
        obj.push_back({x,y});
    }
    sort(obj.begin(), obj.end());
    for(ll i = 0; i < N; i++){
        w.push_back(obj[i].first);
        v.push_back(obj[i].second);
    }
    //cout << knapsack01(N,W,v,w) << '\n';
    //memset(t,0,sizeof(t));
    cout << DP2knapsack01(N,W,v,w);
    //cout << '\n';
    /*
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= W; j++){
            cout << t[i][j] << string(11-floor(log10((t[i][j])?t[i][j]:1)+1),' ');
        }
        cout << '\n';
    }*/
}


Measured memory_bytes: 5200
using System;
using System.Linq;

namespace AGC004B{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var N = sr.Next<int>();
            var X = sr.Next<long>();
            var A = sr.Next<long>(N);

            var dp = new long[N];
            for(var i = 0; i < N; i++){
                dp[i] = A[i];
            }

            var res = long.MaxValue;
            for(var k = 0; k < N; k++){
                for(var i = 0; i < N; i++){
                    dp[i] = Math.Min(dp[i], A[(i - k + N) % N]);
                }
                res = Math.Min(res, dp.Sum() + k * X);
            }

            Console.WriteLine(res);
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];
        private readonly System.IO.StreamReader _sr = new System.IO.StreamReader(Console.OpenStandardInput());

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = _sr.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }

        public T[][] Next<T>(int y, int x){
            var ret = new T[y][];
            for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
            return ret;
        }
    }
}

Measured memory_bytes: 3288
using System;

namespace A
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			var x = int.Parse(Console.ReadLine());
			var a = int.Parse(Console.ReadLine());
			var b = int.Parse(Console.ReadLine());

			Console.WriteLine(x - a - (x - a) / b * b);
		}
	}
}

Measured memory_bytes: 13140
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
int divide(int x, int y);

int main() {
	int H, W;
	cin >> H >> W;
	if ((H == 2) && (W == 2)) {
		cout << 1 << endl;
		return 0;
	}
	if (H % 3 == 0 || W % 3 == 0) {
		cout << 0 << endl;
		return 0;	
	}

	cout << min(divide(H, W),divide(W, H)) << endl;
	return 0;
}

int divide(int x, int y) {
	vector<int> S, S1(3), S2(3), S3(3), S4(3), S5(3);

	S1[0] = (x / 3) * y;
	S1[1] = (x / 3) * y;
	S1[2] = (x / 3 + 1) * y;

	S2[0] = (x / 3) * y;
	S2[1] = (x / 3 + 1) * y;
	S2[2] = (x / 3 + 1) * y;
	
	S3[0] = (x / 3 + 1) * y;
	S3[1] = ((x / 3) * 2 ) * (y / 2);
	S3[2] = ((x / 3) * 2 ) * ((y / 2) + y % 2);

	S4[0] = (x / 3 + 1) * y;
	S4[1] = ((x / 3) * 2 + 1) * (y / 2);
	S4[2] = ((x / 3) * 2 + 1) * ((y / 2) + y % 2);

	S5[0] = (x / 3) * y;
	S5[1] = ((x / 3) * 2 + 1) * (y / 2);
	S5[2] = ((x / 3) * 2 + 1) * ((y / 2) + y % 2);

	sort(S1.begin(), S1.end());
	sort(S2.begin(), S2.end());
	sort(S3.begin(), S3.end());
	sort(S4.begin(), S4.end());
	sort(S5.begin(), S5.end());

	if (accumulate(S1.begin(), S1.end(), 0) == x * y) S.push_back(S1[2] - S1[0]);
	if (accumulate(S2.begin(), S2.end(), 0) == x * y) S.push_back(S2[2] - S2[0]);
	if (accumulate(S3.begin(), S3.end(), 0) == x * y) S.push_back(S3[2] - S3[0]);
	if (accumulate(S4.begin(), S4.end(), 0) == x * y) S.push_back(S4[2] - S4[0]);
	if (accumulate(S5.begin(), S5.end(), 0) == x * y) S.push_back(S5[2] - S5[0]);

	sort(S.begin(), S.end());
	return S[0];
}

Measured memory_bytes: 256
import time
import random


class Problem:

    def __init__(self, D, s, c):
        self.last_days = [0] * 26
        self.D = D
        self.s = s
        self.c = c
        self.answer = [0] * self.D
        self.best_answer = [0] * self.D

    def scoring(self, day, ind):
        day_score = self.s[day][ind]
        minus_score = 0
        for i in range(26):
            if i != ind:
                minus_score += self.c[i] * (day + 1 - self.last_days[i])
        day_score -= minus_score
        return day_score

    def get_all_scores(self, day):
        """全ての選択肢のscoreを返す"""
        minus_score = 0
        all_scores = [0, 0] * 26
        for i in range(26):
            if i == 0:
                for j in range(1, 26):
                    minus_score += self.c[j] * (day + 1 - self.last_days[j])
                all_scores[0] = self.s[day][0] - minus_score

            else:
                minus_score += self.c[i - 1] * (day + 1 - self.last_days[i - 1])
                minus_score -= self.c[i] * (day + 1 - self.last_days[i])
                all_scores[i] = self.s[day][i] - minus_score
        return all_scores

    def _strategy_greedy(self, day):
        all_scores = self.get_all_scores(day)

        ind = random.randint(0, 25)
        score = self.scoring(day, ind)
        return score, ind

    def solve(self):
        self.init()

        sum_score = 0
        for i in range(self.D):
            score, ind = self._strategy_greedy(i)
            self.last_days[ind] = i + 1
            self.answer[i] = ind
            sum_score += score
        return sum_score, self.answer

    def _strategy_perturbation(self):
        # ランダムに１日を取り出し、一番その日の期待コストが大きくなるよう変化させる
        # 貪欲法に摂動を加えてみる
        day = random.randint(0, 3)

        # scores = [self.scoring()]

        random.randint(0, 3)

    def solve_greed(self):
        self.init()

    def init(self):
        self.last_days = [0] * 26
        self.answer = [0] * self.D


def main():
    time_start = time.time()
    DO_TIME = 2 * 0.90
    D = int(input())
    c = list(map(int, input().split()))
    s = []

    for _ in range(D):
        s.append(list(map(int, input().split())))

    max_score = 0

    problem = Problem(D, s, c)
    ite = 0
    while time.time() - time_start < DO_TIME:
        ite += 1
        score, answer = problem.solve()

        if score > max_score:
            # print("hit")
            # print(max_score)
            max_score = score
            problem.best_answer = answer

    for i in range(D):
        # problem.best_answer[i] += 1
        # print(problem.best_answer[i])
        if i == D - 1:
            print(1, end="")
        else:
            print(1)
    # print(ite)
    # print(max_answer)
    # print(max_score)
    # print(problem.get_all_scores(1))


main()


Measured memory_bytes: 87132
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = (int)(a);(i) > (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, n) &((x)[0]), &((x)[n])
#define BRK(x) { (x); break; }
#define ADD(a, b) ((((a)%MOD)+((b)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mt make_tuple
#define fi first
#define se second
#define EPS (1e-20)
#define INF 2147483647
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using VLL = std::vector<llint>;
using MCI = std::map<char, int>;
using namespace std;


int N, x;
int a[100010];
int b[100010];


llint solve(){
	if(b[0] > x) b[0] = x;
	llint ans = 0;
	rep(i, 0, N-1){
		if(b[i]+b[i+1] <= x) continue;
		b[i+1] = x-b[i];
	}
	rep(i, 0, N) ans += a[i]-b[i];
	return ans;
}


signed main(){
	cin >> N >> x;
	rep(i, 0, N) cin >> a[i], b[i] = a[i];

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 1024
n = int(input())
import collections
dat = list(map(int, input().split()))
dat.sort(reverse=True)
dat = collections.deque(dat)
resa , resb = 0,0

while len(dat) != 0:
    resa += dat.popleft()
    if len(dat) ==0:
        break
    resb += dat.popleft()

print(resa - resb)


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

int main() {
  int n;
  cin >> n;
  int l = pow(10, 6) + 3;
  int ok = 1;
  int r = 0;
  int ans = 0;
  vector<int> A(n);
  vector<int> B(l);
  for (int i = 0; i < n; i++) {
    cin >> A.at(i);
  }

  for (int i = 0; i < n; i++) {
      B.at(A.at(i)) += 1;
  }

  for (int i = 0; i < n; i++) {
      ok = 1;
      if ((A.at(i) != 1 && B.at(1) > 0) || B.at(A.at(i)) > 1) {
        ok = 0;
      }
      if (ok == 1) {
         r = pow(A[i], 0.5) + 1;
         for (int j = 2; j < r; j++) {
           if (A.at(i) % j == 0 && (B.at(j) > 0 || B.at(A.at(i)/j) > 0)) {
             ok = 0;
             break;
           }
         }
      }
    ans += ok;
  }
  cout << ans << endl;
}


Measured memory_bytes: 7972