akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
map<int, int>mp;
int main()
{
	int n;
	cin >> n; bool flag = true;
	for (int i = 0, x; i < n; i++)
	{
		cin >> x;
		if (x % 2 == 0)
		{

			if (x % 3 != 0&& x % 5 != 0)
			{
				flag = false;
			}
		}
	}
	if (flag)
		cout << "APPROVED";
	else
		cout << "DENIED";
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n := readInt()
	k := readInt()

	answer := solve(n, k)
	fmt.Printf("%v\n", answer)
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	i, e := strconv.Atoi(readString())
	if e != nil {
		panic(e)
	}
	return i
}

func solve(n, k int) string {
	var count int
	for i := 1; i <= n; i++ {
		if !isEven(i) {
			count++
		}
	}
	if count >= k {
		return "YES"
	} else {
		return "NO"
	}
}

func isEven(n int) bool {
	return n%2 == 0
}

Measured memory_bytes: 640
//templates
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  vector<int> B(N);
  B = A;
  int first = *max_element(ALL(A));
  A.erase(max_element(ALL(A)));
  int second = *max_element(ALL(A));
  rep(i,N){
    if(B[i] == first) cout<< second << endl;
    else cout << first << endl;
  }
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main(){
    int n;
    cin>>n;
    vector<int> d(n);
    rep(i,n) cin>>d[i];
    sort(d.begin(),d.end());
    int ans = d[d.size()/2]-d[d.size()/2-1];
    cout << ans;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 200010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int h[n];
    rep(i, n) cin >> h[i];
    int cnt = 0;

    rep(aa, 101) {
        bool before_nothing = true;

        rep(i, n) {
            if (h[i] > 0 && before_nothing) {
                before_nothing = false;
                cnt++;
            } else if (h[i] <= 0) {
                before_nothing = true;
            }
        }
        rep(i, n) h[i]--;
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> h(n+1),ans(n+1);
    for(int i=1;i<=n;i++) cin>>h[i];
    ans[1]=0;ans[2]=abs(h[2]-h[1]);
    for(int i=3;i<=n;i++)
    {
        ans[i]=min(ans[i-1]+abs(h[i]-h[i-1]),ans[i-2]+min(abs(h[i]-h[i-2]),abs(h[i]-h[i-1])+abs(h[i-1]-h[i-2])));
    }
    cout<<ans[n];
    return 0;
}

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

int main(){
    int n,ans=0,in;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> in;
        while(in%2!=1) ans++,in/=2;
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const ll INF=1e9;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,n){cout<<arr[i][j]<<" ";}cout<<endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,q;
    cin>>n>>k>>q;
    Vec score(n,0);
    Vec a(q);
    ll tmp;
    rep(i,q){
        cin>>tmp;
        score[tmp-1]++;
    }
    rep(i,n){
       // dbg(k+score[i]-q);
        Yes(k+score[i]-q>0);
    }

    return  0;
}


Measured memory_bytes: 2176
import sys
import os
import collections
 
def input(f):
    global v, e, r, s, t, d, g
     
    v, e, r = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
         
    g = [list() for _ in range(v)]
    for i in range(e):
        g[s[i]].append(i)
 
def solve():
    inf = sys.maxint
    q = collections.deque()
    q.append(r)
    mincost = [inf]*v
    mincost[r] = 0
    while len(q) > 0:
        cur = q.popleft()
        for e in g[cur]:
            if mincost[t[e]] == inf or mincost[t[e]] > mincost[cur] + d[e]:
                mincost[t[e]] = mincost[cur] + d[e]
                q.append(t[e])
     
    for i in range(v):
        if mincost[i] == inf:
            print('INF')
        else:
            print(mincost[i])
 
with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()


Measured memory_bytes: 84332
extern crate core;

use std::io::{self, Read};

#[macro_use]
mod parser {
    macro_rules! input {
    ($s:expr=>$($t:tt)*) => {
        let mut lines=$s.split("\n");
        $(
            line_parse!(lines,$t);
        )*
    };
    }

    macro_rules! line_parse {
    ($lines:expr,($($name:ident:$t:tt)*)) => {
        let mut line=$lines.next().unwrap().split_whitespace();
        $(value_def!(line,$name,$t);)*
    };

    //複数行
    ($lines:expr,{$n:expr;$name:ident:$t:tt}) => {
        values_def!($lines,$n,$name,$t);
    };
    }

    macro_rules! value_def {
        ($line:expr, $name:ident, $t:tt) => {
            let $name = value!($line, $t);
        };
    }

    macro_rules! values_def {
        ($lines:expr, $n:expr, $name:ident, $t:tt) => {
            let $name = {
                let mut vec = Vec::new();
                for i in 0..$n {
                    let mut next = $lines.next().unwrap().split_whitespace();
                    vec.push(value!(next, $t));
                }
                vec
            };
        };
    }

    macro_rules! value {
    //配列
    ($line:expr,[$t:tt]) => {
        $line.map(|x|{
        let mut iter=::std::iter::once(x);
        value!(iter,$t)
        }).collect::<Vec<_>>()
    };
    //タプル
    ($line:expr,($($t:tt),*)) => {
        ($(value!($line,$t),)*)
    };
    //文字列
    ($line:expr,#) => {
        $line.next().unwrap()
    };
    //単一値
    ($line:expr,$t:ty) => {
        $line.next().unwrap().parse::<$t>().unwrap()
    };
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = solve(input.trim().to_string());
    println!("{}", output);
}

fn solve(input: String) -> String {
    input!(input=>(a:i64 b:i64));
    if a <= 8 && b <= 8 { "Yay!" } else { ":(" }.to_string()
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!($output.trim().to_string(),super::solve($input.trim().to_string()));
                }
            )*
        }
    }
}

tests! {
    test1: "5 4" => "Yay!",
    test2: "8 8" => "Yay!",
    test3: "11 4" => ":(",
}


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

void solve(long long N, long long K, std::vector<long long> p){
    sort(p.begin(),p.end());
    ll ans =0;
    for(int i=0;i<K;i++){
        ans += p[i];
    }
    cout << ans << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> p(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&p[i]);
    }
    solve(N, K, std::move(p));
    return 0;
}


Measured memory_bytes: 3692
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		
		if (n < 1200) {
			System.out.println("ABC");
		} else {
			System.out.println("ARC");
		}

	}
}

Measured memory_bytes: 20820
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;

lli gcd(lli a, lli b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}

int main(){
    lli n,x;
    cin >> n >> x;
    lli ans;
    for(int i=0; i<n; i++){
        lli a;
        cin >> a;
        a = abs(a-x);
        if(i==0){
            ans = a;
        }else{
            ans = gcd(ans, a);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import math

K = int(input())
wa = []

for i in range(1,K+1):
    for j in range(1,K+1):
        double = math.gcd(i,j)
        for k in range(1,K+1):
            triple = math.gcd(double,k)
            wa.append(triple)

print(sum(wa))
        

Measured memory_bytes: 205812
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <numeric> //lcm


#define ERROR() cout << "ERROR!!" << endl; return 0;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)

#define debug(vec) for(auto v : vec) cout << v << " "; cout << endl;

#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cout << v << " "; cout << endl; } 

using namespace std;

typedef long long ll;

const long long int INF = 1000000000; //<10^10
//const ll MOD = 998244353;
const ll MOD = 1000000007;

inline bool maxch(int& a, int b) { if (a < b) { a = b; return true; } else return false; }

int main() {
	//int k, n, m;
	string s;
	cin >> s;

	bool a = false, b = false;
	for(char c : s) a = a || (c == 'A');
	for(char c : s) b = b || (c == 'B');
	if (a && b) 
	cout << "Yes" << endl;
	else cout << "No" << endl;
}




Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int L, R, D;
    cin >> L >> R >> D;
    int cnt = 0;
    for(int i = L; i <= R; i++) {
        if(i % D == 0)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <cstring>

using namespace std;

bool used[2000];
bool check(string s){
    for(int i = 0; i < s.size()/2; i++){
        if(s[i]==s[s.size()-1-i])
            continue;
        else
            return false;
    }
    return true;
}

int main(){

    string str;
    while(getline(cin,str)){

        memset(used,0,sizeof(used));
        string s;
        for(int i = 0; i < str.size(); i++){
            if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){
                s+=toupper(str[i]);
            }
        }
        set<string> ss;
        for(int i = s.size(); i >= 3; i--){
            for(int j = 0; j + i -1 < s.size(); j++){
                if(check(s.substr(j,i))){
                    ss.insert(s.substr(j,i));
                }
            }
        }
        vector<string> tmps=vector<string>(ss.begin(),ss.end());
        for(int i = 0; i < tmps.size(); i++){
            for(int j = i+1; j < tmps.size(); j++){
                if(tmps[i].size()<tmps[j].size()){
                    int diff=tmps[j].size()-tmps[i].size();
                    diff/=2;
                    if(tmps[j].substr(diff,tmps[i].size())==tmps[i]){
                        used[i]=true;
                    }
                }
                else{
                    int diff=tmps[i].size()-tmps[j].size();
                    diff/=2;
                    if(tmps[i].substr(diff,tmps[j].size())==tmps[j]){
                        used[j]=true;
                    }
                }
            }
        }
        ss.clear();
        for(int i = 0; i < tmps.size(); i++){
            if(!used[i])
                ss.insert(tmps[i]);
        }
        for(set<string>::iterator it=ss.begin();it!=ss.end();it++){
            cout<<*it;
            set<string>::iterator iit=it;
            iit++;
            if(iit==ss.end()){
                cout<<endl;
            }
            else
                cout<<" ";
        }
        if(ss.size()==0)cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=45;
const int MOD=1e9+7;
int add (int x,int y)   {x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {return (LL)x*y%MOD;}
int dec (int x,int y)   {x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
	if (y==1) return x;
	int lalal=Pow(x,y>>1);
	lalal=mul(lalal,lalal);
	if (y&1) lalal=mul(lalal,x);
	return lalal;
}
int f[N][1<<18];
int n,X,Y,Z;
int main()
{
	scanf("%d%d%d%d",&n,&X,&Y,&Z);
	int ans=Pow(10,n);
	int g=((1<<(X+Y+Z-1))|(1<<Y+Z-1)|(1<<Z-1));
	f[0][0]=1;
	int h=(1<<X+Y+Z)-1;
	for (int u=1;u<=n;u++)
	for (int i=0;i<h;i++)
	for (int j=1;j<=10;j++)
	{
		int t=(i<<j)|(1<<j-1);
		t&=h;
	//	printf("%d %d %d\n",t,g,t&g);
		if ((t&g)!=g)
		{
			f[u][t]=add(f[u][t],f[u-1][i]);
		}
	}
	for (int i=0;i<h;i++) ans=dec(ans,f[n][i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 41728
/**
        Bismilla- hir rahma-nir rahi-m
    @uthor Md Hasibur Rahman (Evan)
                JKKNIU
*/


#include<bits/stdc++.h>
#define         ll              long long
#define         FI              freopen("input.txt","r",stdin)
#define         FO              freopen("output.txt","w",stdout)
#define         PrintCase(i)    printf("Case %d: ",i)
#define         sc(a)           scanf("%d",&a)
#define         scl(a)          scanf("%lld",&a)
#define         rep(i,n)        for(int i=0;i<n;i++)
#define         pb              push_back
#define         MAX             1000000
#define         fast            ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define			endl			"\n"


using namespace std;

bool isPrime(ll a)
{
    for(ll i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}






bool isPowerOfTwo(ll a)
{
    if(a==1)
        return true;
    if(a&1)
        return false;
    while(a)
    {
        a/=2;
        if(a!=1 && a&1)
            return false;
        if(a==1)
            return true;
    }
    return true;
}




ll gcd(ll a, ll b)
{
    if(a<0 || b<0)
    {
        a = abs(a);
        b = abs(b);
    }
    if(a<b)
        swap(a,b);
    if(a%b==0 || b==0)
        return b;
    else
        return gcd(b,a%b);
}



ll lcm(ll a, ll b)
{
    return (a*b)/gcd(a,b);
}



ll power(ll base, ll exponent)
{
    ll ans = 1;
    for(ll i=1;i<=exponent;i++)
        ans*=base;
    return ans;
}




bool isPowerOfX(ll x, ll value)
{
    if(value==1)
        return true;
    while(value)
    {
        value/=x;
        if(value%x && value!=1)
            return false;
    }
    return true;
}





int main()
{
    fast;
    string s;
    cin>>s;
    int l = s.size();
    ll sum = 0;
    for(int i=0;i<l;i++) sum+=s[i]-'0';
    sum%9==0?cout<<"Yes\n":cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3784
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;

#define INF (1e9)

int N, ans;

void count(ll x, bool a, bool b, bool c) {
    if (x > N) return;
    if (a & b & c) ans++;
    count(x * 10 + 3, true, b, c);
    count(x * 10 + 5, a, true, c);
    count(x * 10 + 7, a, b, true);
}

int main() {
    cin >> N;
    ans = 0;
    count(0, false, false, false);

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using static System.Console;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		long a = long.Parse(Console.ReadLine());
		// スペース区切りの整数の入力
		//string[] NMK = Console.ReadLine().Split(' ');
		//long N = long.Parse(NMK[0]);
		//long K = long.Parse(NMK[1]);
		//string s = Console.ReadLine();
		long happy = 0;
		happy += a/500*1000;
		a = a%500;

		happy += a/5*5;

		Console.WriteLine(happy + "");

		// 文字列の入力
		//string s = Console.ReadLine();
		//出力
		//Console.WriteLine((a+b+c) + " " + s);
	}
}


Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		for (int i=0;i<N;i++) {
			String t = sc.next();
			System.out.println(t);
			System.out.println(t);
		}
	}
}

Measured memory_bytes: 37456
#include <bits/stdc++.h>
using namespace std;
int counter(int x){
  int cnt=0;
  while(x){
    x/=10;
    cnt++;
  }
  return cnt;
}
int main()
{
  int n;cin>>n;
  int cnt=0;
  for(int i=1;i<=n;i++){
    if(counter(i)%2){
      cnt++;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
  int N;
  cin >> N;
  
  vector <int> h(N);
  for (int i = 0; i < N; ++i) cin >> h[i];
  
  vector <int> dp(N);
  dp[0] = 0;
  dp[1] = abs(h[1] - h[0]);
  for (int i = 2; i < N; ++i) {
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), 
                dp[i - 2] + abs(h[i] - h[i - 2]));
  }
  cout << *dp.rbegin() << endl;
  return 0;
}

Measured memory_bytes: 3552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m[105];
int n;
int main()
{
    int sum=0;
    //printf("%d\n",30%10);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m[i]);
        sum+=m[i];
    }
    //cout<<sum<<endl;
    sort(m,m+n);
    int num=0;
    int flag=0;
    //printf("%d\n",sum%10);
    if(sum<10)
        printf("%d\n",sum);
    else if((sum%10)!=0)
        printf("%d\n",sum);
    else
    {
        for(int i=0;i<n;i++)
        {
            if((sum-m[i])%10!=0)
            {
                flag=1;
                printf("%d\n",sum-m[i]);
                break;
            }
            else
                continue;
        }
        if(!flag)
        printf("0\n");
    }

}


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

#define y1 dmytxdy
#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1000000007;
int n,a,b;
ll d[5005][5005],s[5005][5005],pw[5005];

ll mod(ll x){return x>=cys?x-cys:x;}

int main(){
	n=readint(); a=readint(); b=readint();
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=mod(pw[i-1]<<1);
	if(a<b) swap(a,b);
	ll ans=0;
	d[0][1]=s[0][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i-a+1;j++){
			int t=i-b-1<0?0:s[i-b-1][j];
			ans=mod(ans+(d[i-1][j]+t)*pw[n-i])%cys;
		}
		for(int j=max(1,i-a+2);j<=i;j++){
			int t=i-b-1<0?0:s[i-b-1][j];
			d[i][j]=mod(d[i-1][j]+t);
		}
		for(int j=1;j<=i;j++) d[i][i+1]=mod(d[i][i+1]+mod(cys+s[i-1][j]-(i-b<0?0:s[i-b][j])));
		for(int j=1;j<=i;j++) s[i][j]=mod(s[i-1][j]+d[i][j]);
	}
	for(int j=1;j<=n-a+1;j++) ans=mod(ans+(n-b<0?0:s[n-b][j]));
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 236984
s = input()

a="0"
b="1"
count=0
for i in range(len(s)):
  if i%2==0:
    count+= int(s[i]==a)
  else:
    count+= int(s[i]==b)
tmp1=count

a="1"
b="0"
count=0
for i in range(len(s)):
  if i%2==0:
    count+= int(s[i]==a)
  else:
    count+= int(s[i]==b)
tmp2=count

print(min(tmp1,tmp2))


Measured memory_bytes: 3188
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define rep(i,n) REP(i,1,n)
#define rep0(i,n) REP(i,0,n-1)
#define repG(i,x) for(ll i=pos[x];~i;i=e[i].next)
const ll N=2e5+7;
const ll INF=1e15;
ll pos1[N],pos2[N],dis1[N],dis2[N],ans[N];
bool vis[N];
ll n,m,s,t,num=0;
struct edge{ll v,next,c;}e[N*4];
void add1(ll x,ll y,ll c){e[num]=(edge){y,pos1[x],c}; pos1[x]=num++;}
void add2(ll x,ll y,ll c){e[num]=(edge){y,pos2[x],c}; pos2[x]=num++;}
void spfa(ll x0,ll *pos,ll *dis){
	memset(vis,1,sizeof(vis));
	rep(i,n)dis[i]=INF;
	dis[x0]=0;
	queue<int>q;
	q.push(x0);
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		vis[u]=1;
		repG(i,u){
			if(dis[e[i].v]>dis[u]+e[i].c){
				dis[e[i].v]=dis[u]+e[i].c;
				if(vis[e[i].v]){
					vis[e[i].v]=0;
					q.push(e[i].v);
				}
			}
		}
	}
}
int main(){
	memset(pos1,-1,sizeof(pos1));
	memset(pos2,-1,sizeof(pos2));
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	rep(i,m){
		ll x,y,a,b; scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		add1(x,y,a);
		add1(y,x,a);
		add2(x,y,b);
		add2(y,x,b);
	}
	spfa(s,pos1,dis1);
	spfa(t,pos2,dis2);
	ans[n+1]=INF;
	for(ll i=n;i;i--)ans[i]=min(ans[i+1],dis1[i]+dis2[i]);
	rep(i,n)printf("%lld\n",INF-ans[i]);
	return 0;
}


Measured memory_bytes: 20480
#include <iostream>
#include <vector>

using namespace std;


int main() {
  int N, K;
  vector<int> a;
  vector<vector<bool> > dp1, dp2;
  cin >> N >> K;
  a.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  dp1.resize(N + 1);
  dp2.resize(N + 1);
  for (int i = 0; i <= N; i++) {
    dp1[i].resize(K + 1, false);
    dp2[i].resize(K + 1, false);
  }
  dp1[0][0] = dp2[0][0] = true;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      dp1[i+1][j] = dp1[i][j] || (j >= a[i] && dp1[i][j-a[i]]);    
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      dp2[i+1][j] = dp2[i][j] || (j >= a[N-i-1] && dp2[i][j-a[N-i-1]]);    
    }
  }

  int ans = 0;

  for (int i = 0; i < N; i++) {
    bool flag = false;
    for (int j1 = 0; j1 < K; j1++) {
      if (!dp1[i][j1]) continue;
      int j2 = K - a[i] - j1;
      if (j2 < 0) j2 = 0;
      while (j1 + j2 < K) {
        if (dp1[i][j1] && dp2[N-i-1][j2]) {
          flag = true;
          break;
        }
        j2++;
      }
      if (flag) break;
    }
    if (!flag) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6912
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
check = [1 for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    info[a - 1].append(b - 1)
    info[b - 1].append(a - 1)


def plus(n, val):
    ans[n] += val
    check[n] = 0
    for i in info[n]:
        if check[i]:
            plus(i, val + Query[i])


Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))


Measured memory_bytes: 244004
using Base.Collections
const lines=readlines()
const N,M=map(x->parse(Int,x),split(shift!(lines)))
const A=Pair{Int,Int}[]
for s=lines
	a,b=map(x->parse(Int,x),split(s))
	push!(A,a=>b)
end
sort!(A)
const P=PriorityQueue(Int,Int)
ans=0
id=1
for i=1:M
	while id<=N&&A[id].first<=i
		P[id]=-A[id].second
		id+=1
	end
	if !isempty(P)
		ans-=peek(P).second
		dequeue!(P)
	end
end
println(ans)


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

#define rep(i,n)  for(int i = 0; i < (n); i++)
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
using vi = vector<int>;
using ll = long long;

const double EPS = 1e-8;

using P = complex<double>;
namespace std{
  bool operator <(const P &a, const P &b){
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P &a, const P &b){
  return imag(conj(a)*b);
}
double dot(const P &a, const P &b){
  return real(conj(a)*b);
}
struct L : public vector<P>{
  L(const P &a, const P &b){
    push_back(a);
    push_back(b);
  }
};
struct C{
  P p; double r;
  C(const P &p_, double r_) : p(p_), r(r_) {}
};

P projection(const L &l, const P &p){
  double t = dot(p-l[0],l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}

vector<P> crosspointCL(const C &c, const L &l){
  P h = projection(l, c.p);
  double d = abs(h - c.p);
  vector<P> res;
  if(d < c.r - EPS){
    P dir = l[1]-l[0];
    P x = dir / abs(dir) * sqrt(c.r*c.r - d*d);
    res.push_back(h + x);
    res.push_back(h - x);
  }else if(d < c.r + EPS){
    res.push_back(h);
  }
  return res;
}

int main(){
  int n; cin >> n;
  vector<double> rs(n); rep(i,n) cin >> rs[i];
  vector<C> res;
  res.push_back(C(P(rs[0],rs[0]),rs[0]));
  FOR(i,1,n){ // n番目の円の場所を確定させる
    P tmp(rs[i],rs[i]);
    rep(j,i){
      C tmpc(res[j].p,res[j].r+rs[i]);
      // cerr << tmpc.p.real() << " " << tmpc.p.imag() << " " << tmpc.r << endl;
      L tmpl(P(0,rs[i]),P(100,rs[i]));
      vector<P> cross = crosspointCL(tmpc, tmpl);
      sort(cross.begin(), cross.end());
      // cerr << cross.back().real() << " " << cross.back().imag() << endl;
      tmp = max(tmp, cross.back());
    }
    res.push_back(C(tmp,rs[i]));
  }
  double ans = 0;
  rep(i,n){
    ans = max(ans, res[i].p.real()+res[i].r);
    // cerr << i << " " << res[i].p.real() << endl;
  }
  //cout << ans << endl;
  printf("%.10lf\n",ans);
}


Measured memory_bytes: 3376
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;


int main(){
    int n;
    cin >> n;
    vector<int> a(3*n);

    for(int i=0; i<3*n;i++) cin >> a[i];

    long long sum = 0;

    sort(a.begin(),a.end(),greater<int>());



    for(int i=1;i<2*n;i+=2){
        sum += a[i];
    }

    cout << sum << endl;
    
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <bitset>
#include <map>
#include <math.h>
#include <utility>

using namespace std;

int main(){

    int N;
    cin >> N;

    vector<int> A(N);
    int max1 = 1, max2 = 1;

    for (int i = 0; i < N; i++){
        cin >> A[i];
        if (max1 <= A[i]){
            max2 = max1;
            max1 = A[i];
        } else if (max2 < A[i]){
            max2 = A[i];
        }
    }

    // cout << max1 << " : " << max2 << endl;

    for (int i = 0; i < N; i++){
        if (A[i] == max1){
            cout << max2 << endl;
        } else {
            cout << max1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 2432
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
int N, M;
pi P[300000];
vector<int> R[100001], pf[100001];
int A[100001], fw[100001], ans[100001];
int qry(int x){
    int r = 0;
    for(; x > 0; x -= x&-x) r += fw[x];
    return r;
}
void upd(int x, int v){
    for(; x <= 100000; x += x&-x) fw[x] += v;
}
int main(){
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d %d", &P[i].first, &P[i].second);
        A[P[i].first]++;
        R[P[i].second].push_back(P[i].first);
    }
    for(int i = 1; i <= M; ++i){
        for(int j = i; j <= M; j += i){
            pf[j].push_back(i);
        }
    }
    for(int i = 1; i <= M; ++i){
        upd(i, A[i]);
        for(auto j : pf[i]){
            ans[j] += qry(i) - qry(i - j);
        }
        for(auto j : R[i]) upd(j, -1);
    }
    for(int i = 1; i <= M; ++i){
        printf("%d\n", ans[i]);
    }
}
    


Measured memory_bytes: 20352
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    string s;
    cin >> s;
    int n = s.length();
    string sm = "keyence";
    
    rep(i, n) srep(j, i, n) {
        string st = s.substr(0, i) + s.substr(j, n);
        if (st == sm) {
            puts("YES");
            return 0;
        }
    } 
    puts("NO");
    return 0;
}

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

int x[3];
void solve() {
    int n;
    cin >> n;
    int rs[n];
    for (int i = 0; i < n; i++) {
        cin >> rs[i];
    }

    sort(x, x+3);
    int diag_pow_2 = x[0] * x[0] + x[1] * x[1];

    for (int i = 0; i < n; i++) {
        if ( (rs[i] * 2) * (rs[i] * 2) > diag_pow_2) 
            cout << "OK" << endl;
        else 
            cout << "NA" << endl;
    }
}

int main() {
    while (cin >> x[0] >> x[1] >> x[2]) {
        if (x[0] == 0) break;
        solve();
    }
    return 0;
}

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

int main() {
    // input 
    int n, m; cin >> n >> m;
    vector<long> x(n,0); vector<long> y(n,0); vector<long> z(n,0);
    vector<long> sum(n,0);
    vector<vector<long>> sum_sum(8,sum);
    bitset<3> bit;
    rep(i, n) {
        scanf("%ld %ld %ld", &x[i], &y[i], &z[i]);
        rep(j, 1<<3) {
            bit = j;
            long xi = x[i], yi = y[i], zi = z[i];
            if (bit.test(0)) {
                xi = -xi;
            }
            if (bit.test(1)) {
                yi = -yi;
            }
            if (bit.test(2)) {
                zi = -zi;
            }
            sum_sum[j][i] += xi + yi + zi;
        }
    }

    long max = 0;
    rep(i, 8) {
        long sum_i = 0;
        sort(sum_sum[i].rbegin(), sum_sum[i].rend());
        rep(j, m) {
            sum_i += sum_sum[i][j];
        }
        // printf("%ld\n", sum_i);
        if (sum_i > max) {
            max = sum_i;
        }
    }
    printf("%ld\n", max);
}

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

int main(){
    int a, b, c, i = 0;
    std::cin >> a >> b >> c;
    for(int j = a; j <= b; ++j){
        if(0 == c % j){
            ++i;
        }
    }

    std::cout << i << std::endl;
    
    return 0;
}


Measured memory_bytes: 3092
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

cnt = 0
c = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    if(i%2 == 0):
        for j in range(W):
            if(a[cnt] > 1):
                c[i][j] = cnt+1
                a[cnt] -= 1
            elif(a[cnt] == 1):
                c[i][j] = cnt+1
                a[cnt] -= 1
                cnt += 1
    else:
        for j in range(W-1, -1, -1):
            if(a[cnt] > 1):
                c[i][j] = cnt+1
                a[cnt] -= 1
            elif(a[cnt] == 1):
                c[i][j] = cnt+1
                a[cnt] -= 1
                cnt += 1
                
for i in range(H):
    print(*c[i])

Measured memory_bytes: 9520
n, m = map(int, input().split())
ab = []
for _ in range(n):
    p, c = map(int, input().split())
    ab.append((p, c))

ab = sorted(ab)

ans = 0
for p, c in ab:
    if m >= c:
        ans += p * c
        m -= c
    else:
        ans += p * m
        m = 0
        break

print(ans)

Measured memory_bytes: 17788
import sys
if sys.version_info[0]>=3: raw_input=input

cross=lambda a,b: (a.conjugate()*b).imag
dot=lambda a,b: (a.conjugate()*b).real

def solve(poly, p):
	f=False
	for i in range(len(poly)):
		a=poly[i]-p
		b=poly[(i+1)%len(poly)]-p
		if a.imag>b.imag: a,b=b,a
		if a.imag<=0 and 0<b.imag and cross(a,b)<0: f=not f
		if cross(a,b)==0 and dot(a,b)<=0: return 1
	return 2 if f else 0

checkio=lambda data: solve([complex(*e) for e in data[0]],complex(*data[1]))

n=int(raw_input())
poly=[[float(e) for e in raw_input().split()] for i in range(n)]
n=int(raw_input())
try:
	for i in range(n):
		print(checkio([poly,[float(e) for e in raw_input().split()]]))
except EOFError:
	pass



Measured memory_bytes: 5656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 200000000000
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()

bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll N;
    cin >>N;
    map<ll,ll> m;
    rep(i,N){
        ll a;
        cin >>a;
        if(m[a] == 1){
            cout << "NO"<< endl;
            return 0;
        }
        m[a] = 1;
    }
    
    cout << "YES"<< endl;
    

    return 0;
    
    

}

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

int main() {
    int p, q, r;
    cin >> p >> q >> r;
    int abc = p + q;
    int acb = r + q;
    int bac = p + r;
    int bca = q + r;
    int cab = r + p;
    int cba = q + p;
    cout << min(abc, min(acb, min(bac, min(bca, min(cab, cba))))) << "\n";
    return 0;
}

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

ll dp[100007];
ll vis[100007];
ll arr[100007];
int n;

ll rec( int now )
{
    if(now>=n)
        return inf;
    if(now==n-1)
        return 0;
    if(vis[now])
        return dp[now];

    ll q1=  llabs(arr[ now+1 ]-arr[ now ])+rec(now+1);
    ll q2=  llabs(arr[ now+2 ]-arr[ now ])+rec(now+2);

    vis[now]= 1;

    return dp[now]= min( q1,q2 );
}

int main()
{
   cin>>n;

   for(int i=0;i<n;i++)
        cin>>arr[i];

   cout<< rec( 0 ) <<endl;
}


Measured memory_bytes: 5760
import sys
s = list(input())
check =['dream','dreamer','erase','eraser']
while len(s) >= 8:
    if ''.join(s[-5:]) == check[0]:
        for _ in range(5): s.pop()
        continue
    if ''.join(s[-7:]) == check[1]:
        for _ in range(7): s.pop()
        continue
    if ''.join(s[-5:]) == check[2]:
        for _ in range(5): s.pop()
        continue
    if ''.join(s[-6:]) == check[3]:
        for _ in range(6): s.pop()
        continue
    print('NO')
    sys.exit()
if ''.join(s) == check[0] or ''.join(s) == check[1] or ''.join(s) == check[2] or ''.join(s) == check[3]:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 4084
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

map<ll, ll> memo;
ll a, b, c, d;

ll calc(ll n){
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return d;
    ll ret = 1e18;
    if (n < 1e9) chmin(ret, n * d);
    double tmp = (double)n * d;
    if (tmp < 1e18) chmin(ret, n * d);
    if (n % 2 == 0) chmin(ret, calc(n / 2) + a);
    else{
        chmin(ret, calc(n / 2) + a + d);
        chmin(ret, calc(n / 2 + 1) + a + d);
    }
    if (n % 3 == 0){
        chmin(ret, calc(n / 3) + b);
    }else{
        int r = n % 3;
        chmin(ret, calc(n / 3) + b + r * d);
        chmin(ret, calc(n / 3 + 1) + b + (3 - r) * d);
    }
    if (n % 5 == 0){
        chmin(ret, calc(n / 5) + c);
    }else{
        int r = n % 5;
        chmin(ret, calc(n / 5) + c + r * d);
        chmin(ret, calc(n / 5 + 1) + c + (5 - r) * d);
    }
    return memo[n] = ret;
}

ll solve(){
    ll n;
    cin >> n >> a >> b >> c >> d;
    memo.clear();
    return calc(n);
}

int main(void){
    int t;
    cin >> t;
    REP(i,t){
        cout << solve() << endl;
    }

    return 0;
}


Measured memory_bytes: 4356
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
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()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n; cin >> n;
  vector<int> a(n); REP(i, n) cin >> a[i];
  sort(ALL(a));
  if (count(ALL(a), 1) >= 1) {
    cout << (count(ALL(a), 1) == 1 ? 1 : 0) << '\n';
    return 0;
  }
  map<int, set<int>> mp;
  REP(i, n) mp[a[i]].emplace(i);
  REP(i, n) {
    if (mp[a[i]].count(i)) {
      mp.erase(a[i]);
      mp[a[i]].emplace(i);
    } else {
      mp.erase(a[i]);
    }
    for (int j = a[i] * 2; j <= 1000000; j += a[i]) mp.erase(j);
  }
  int ans = 0;
  for (auto [ignore, st] : mp) ans += st.size();
  cout << ans << '\n';
  return 0;
}


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

int main() {
    vector<int> list = {1, 1, 1, 2, 1, 2, 1, 5,  2, 2, 1, 5, 1, 2, 1, 14,
                        1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K;
    cin >> K;
    cout << list.at(K - 1);
    return 0;
}


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

int main(){
  int N;
  string S;
  cin>>N>>S;
  vector<ll> counter(26,0);
  for(int i=0;i<N;i++){
    int x=S.at(i)-'a';
    counter.at(x)++;
  }

  ll ans=1;
  for(int i=0;i<26;i++){
    ans*=counter.at(i)+1;
    ans%=MOD;
  }
  ans--;
  cout<<ans<<endl;
}


Measured memory_bytes: 512
while True:
    try:
        c1, c2, c3 = map(int, input().split())
    except:
        break
    nums = [i for i in range(1, 11)]
    for c in [c1, c2, c3]:
        nums.remove(c)
    cnt = 0
    for num in nums:
        if num + c1 + c2 <= 20:
            cnt += 1
    print('YES' if cnt > 3 else 'NO')

Measured memory_bytes: 7684
n,m=map(int,input().split())
a=[]
b=[]
for i in range(n):
  a.append(list(map(int,input().split(' '))))
for i in range(m):
  b.append(int(input()))


for i in range(n):
  c=0
  for j in range(m):
    c+=a[i][j]*b[j]
  print(c)


Measured memory_bytes: 6012
#include <iostream>

using namespace std;

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

    int fx = 0;
    int n = N;
    while(n / 10)
    {
        fx += (n % 10);
        n /= 10;
    }
    fx += n;

    cout << (N % fx ? "No" : "Yes") << endl;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"

using namespace std;

int A[30],n;

int solve(int i,int m){
  if(m == 0) return 1;
  if(i >= n) return 0;
  int  res = solve(i + 1,m) || solve(i + 1,m - A[i]);
  return res;
}

int main(){
  int m,q;
  cin >> n;
  for(int i = 0; i< n ; i++){
    cin >> A[i];
  }
  cin >> m;
    for(int i = 0; i< m ; i++){
      cin >> q;
      if(solve(0,q)) cout << "yes" << endl;
      else cout << "no" << endl;
    }
    return 0;;
}



Measured memory_bytes: 3124
import os
import sys
from collections import Counter


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()

counter = Counter(S)
# 回文にできるかどうかはかんたんに判定できる
if len(S) % 2 == 0:
    ok = True
    for c, cnt in counter.items():
        ok &= cnt % 2 == 0
else:
    odds = 0
    for c, cnt in counter.items():
        odds += cnt % 2 == 1
    ok = odds == 1
if not ok:
    print(-1)
    exit()

# 左右に寄せる。
# 左側か右側かだけで転倒数を数える
counts = [0] * 26
ls = ''
mid = ''
rs = ''
invs = 0
for c in S:
    n = ord(c) - ord('a')
    counts[n] += 1
    if counter[c] & 1:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        elif counts[n] == counter[c] // 2 + 1:
            mid += c
            invs += len(rs)
        else:
            rs += c
    else:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        else:
            rs += c

rs = rs[::-1]
# 目的の回文への置換回数と同じ回数で ls -> rs に置換できる
l_idx = [[] for _ in range(26)]
for i, c in enumerate(ls):
    n = ord(c) - ord('a')
    l_idx[n].append(i)
counts = [0] * 26
idx = []
for i, c in enumerate(rs):
    n = ord(c) - ord('a')
    idx.append(l_idx[n][counts[n]])
    counts[n] += 1

# idx を昇順にする == ls と同じ並びにするまでの回数
invs2 = 0
bit = BinaryIndexedTree(size=len(ls))
for i in reversed(idx):
    invs2 += bit.sum(i)
    bit.add(i, 1)
ans = invs + invs2
# print(invs, invs2)
# print(ls, rs)
# print(idx)
print(ans)


Measured memory_bytes: 10016
n = gets.to_i
array = gets.split.map(&:to_i)
s=0
sum=0
while s<n
  i=0
  brray=[]
  while i<s+1
    brray.push(array[i])
    i+=1
  end
  if brray[i-1] == brray.max
    sum+=1
  end
  s+=1
end
puts sum

Measured memory_bytes: 1788
# _*_ coding:utf-8 _*_
#  Atcoder_AISingProgramming_Contest-B
#  TODO https://aising2019.contest.atcoder.jp/tasks/aising2019_b

def solveProblem(problemSeed,FirstScore,SecondScore,ScoreList):
	firstBarrier = 0
	secondBarrier = 0
	lastBarrier = 0
	for problemNo in range(0,len(ScoreList),+1):
		problemScore = ScoreList[problemNo]
		if problemScore <= FirstScore:
			firstBarrier = firstBarrier + 1
		elif ( FirstScore+1 <= problemScore ) and ( problemScore <= SecondScore):
			secondBarrier = secondBarrier + 1
		else : # secondScore + 1 <= problemScore
			lastBarrier = lastBarrier + 1
	problemPattern = min(firstBarrier, secondBarrier,lastBarrier)
	answer = problemPattern
	return answer


if __name__ == '__main__':
	N = int(input().strip())
	A,B = map(int,input().strip().split(' '))
	Ps = list(map(int,input().strip().split(' ')))
	solution = solveProblem(N,A,B,Ps)
	print("{}".format(solution))


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            var b = int.Parse(Console.ReadLine());
            Console.WriteLine(6 - a - b);
        }
    }
}

Measured memory_bytes: 27072
A,B,M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for i in range(M):
  x,y,c = map(int, input().split())
  ans = min(ans, a[x-1]+b[y-1]-c)
print(ans)

Measured memory_bytes: 18736