akhauriyash/Code-Regression huggingface dataset:
N,K = map(int, input().split())
A = list(map(int, input().split()))

def f(X):
    res = 0
    for a in A:
        res += X ^ a
    return res

ans = max(f(0), f(K))

for d in range(60, 0, -1):
    if K & (1<<d) == 0:
        continue

    
    # X = K & ( (1<<d)-1)
    X = K &  ~((1<<d+1)-1)
    if d == 0:
        ans = max(f(0), f(K-1))

    # print("d: ", d, "X: ", X, "bitmask: {0:010b}".format((1<<d)-1), "uppermask: {0:010b}".format(int("1111111",2)& ~((1<<d+1)-1)))


    for j in range(d): 
        count_should_raise = 0
        mask = 1<<j
        for a in A:
            if a & mask == 0: count_should_raise += 1
        if count_should_raise > N//2:
            # print("\t1j: ", j, "1<<j: ", 1<<j)
            X |= 1<<j

    # if ans < f(X):
    #     print("f(X): ", f(X), "X: " , X, "d: ", d)
    ans = max(ans, f(X))
print(ans)


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


Measured memory_bytes: 2036
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

int main(){

    int N;
    cin >> N;
    vector<int> A(N);
    int ans = 0;
    int pointA=0;
    int pointB=0;


    for(int i=0; i<N;i++)  cin >> A.at(i);
    sort(A.begin(),A.end());

    for(int i=0; i<N; i++){

        if(i%2==0){
            pointB += A.at(i);
        }else{
            pointA += A.at(i);
        }

    }
    ans = abs(pointA - pointB);

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

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

    long long res = 0;
    for (int i = 0; i < n; i++) {
        if ((k | a[i]) <= k) {
            res += b[i];
        }
    }

    for (int i = 0; i <= 31; i++) {
        if ((k & (1LL << i)) > 0) {
            long long r = 0, s = ((k | ((1LL << i) - 1)) ^ (1LL << i));
            for (int j = 0; j < n; j++) {
                if ((s | a[j]) <= s) {
                    r += b[j];
                }
            }
            res = max(res, r);
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 4828
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;
#define endl '\n'
#define pi pair<long double, long double>

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout << setprecision(9) << fixed;
	
	int n;
	cin >> n;
	
	long double f[n + 1];
	f[0] = 1;
	for(int i = 1; i <= n; i++) f[i] = i * f[i - 1];
	
	pi p[n];
	long double ret = 0;
	for(int i = 0; i < n; i++){
		cin >> p[i].first >> p[i].second;
		for(int j = 0; j < i; j++){
			ret += 2 * f[n - 1] * sqrtl(powl(p[i].first - p[j].first, 2) + powl(p[i].second - p[j].second, 2));
		}
	}
	
	cout << (ret / f[n]) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<long double, long double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int MOD = 1000000007;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int mood(int a, int b){
    if (a % b == 0) return b;
    else return a % b;
}

int main() {
    int n, m, k; cin >> n >> m >> k;
    if (n+m+k<=21) cout << "win" << endl;
    else cout << "bust" << endl;
}

Measured memory_bytes: 256
package main

import(
    "fmt"
    "sort"
    "strings"
)



func main() {
    var a,b int
    fmt.Scan(&a,&b)
    d := b-a
    fmt.Println(d*(d+1)/2-b)
}





// Pairsort
type Pair struct {
    first int
    second int
}

type By func(p1, p2 *Pair) bool

func (by By) Sort(pairs []Pair) {
    ps := &pairSorter{
            pairs : pairs,
            by: by,
    }
    sort.Sort(ps)
}

type pairSorter struct {
    pairs []Pair
    by func(p1, p2 *Pair) bool
}

func (s *pairSorter) Len() int {
    return len(s.pairs)
}

func (s *pairSorter) Swap(i, j int) {
    s.pairs[i], s.pairs[j] = s.pairs[j], s.pairs[i]
}

func (s *pairSorter) Less(i, j int) bool {
    return s.by(&s.pairs[i], &s.pairs[j])
}

func first (p1, p2 *Pair) bool {
        return p1.first < p2.first
}

func second (p1, p2 *Pair) bool {
        return p1.second < p2.second
}
// end



func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

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

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

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func scanTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}

func SortString(s string) string{
    t := strings.Split(s, "")
    sort.Strings(t)
    return strings.Join(t, "")
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define ALL(x) x.begin(),x.end()
#define fs first
#define sd second
#define couts(x) cout << (x) << (" ")
#define coutn(x) cout << (x) << ("\n")
#define endl "\n"

template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T1, typename T2> std::istream &operator>>(std::istream &is, std::pair<T1,T2> &p){is >> p.first >> p.second; return is; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::deque<T> &vec){ os << "deque["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }

template<class T> using V = vector<T>;
template<class T> using V2 = V<V<T>>;
template<class T> using V3 = V<V2<T>>;

int gcd(int x, int y){
  if(y==0) return x;
  return gcd(y, x % y);
}
void solve(){
  int k; cin >> k;++k;
  ll ans = 0;
  FOR(i,1,k){
    FOR(j,1,k){
      FOR(l,1,k) ans += gcd(i,gcd(j,l));
    }
  }
  couts(ans);
}


int main(void){
  solve();
  return 0;
}


Measured memory_bytes: 3624
readlines.each do |l|
  y,m,d = l.split.map(&:to_i)
  t = Time.new(y,m,d)
  puts case
  when t<Time.new(1868,9,8); "pre-meiji"
  when t<Time.new(1912,7,30); "meiji #{y-1867} #{m} #{d}"
  when t<Time.new(1926,12,25); "taisho #{y-1911} #{m} #{d}"
  when t<Time.new(1989,1,8); "showa #{y-1925} #{m} #{d}"
  else "heisei #{y-1988} #{m} #{d}"
  end
end

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

int main() {
  string s, t;
  cin >> s >> t;
  int c = 0;
  for(int i = 0; i < 3; i++) {
    if(s[i] == t[i]) {
      c++;
    }
  }
  cout << c;
}

Measured memory_bytes: 256
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus >= 201703L
#        pragma GCC target("avx2")
#    else
#        pragma GCC target("avx")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    Int k, a, b;
    cin >> k >> a >> b;

    Int ans = 1;
    if (b - a <= 2 || k + 1 <= a) {
        ans += k;
    } else {
        ans += a - 1;
        k -= a - 1;

        ans += (b - a) * (k / 2) + (k % 2);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;

signed main() {
	int n, k; cin >> n >> k;
	int ans = 1;
	for (int i = 0; i < n; i++) {
		ans = min(ans * 2, ans + k);
	}
	cout << ans << endl;
}


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

class C
{
	static void Main()
	{
		Console.ReadLine();
		var a = Console.ReadLine().Split().Select((x, i) => new { x = int.Parse(x), i = i + 1 }).OrderBy(_ => _.x).ToArray();
		Console.WriteLine(string.Join(" ", a.Select(_ => _.i)));
	}
}


Measured memory_bytes: 34652
from collections import deque
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    S = input()
    Q = int(input())

    s = deque(S)
    left, right = s.appendleft, s.append
    rev = 0
    for _ in [0] * Q:
        T = input().split()
        if T[0] == '1':
            left, right = right, left
            rev += 1
        else:
            f, c = T[1], T[2]
            if f == '1':
                left(c)
            else:
                right(c)

    if rev % 2:
        s.reverse()
    print(''.join(s))


main()


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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll K, A, B;
  cin >> K >> A >> B;
  if (B - A > 2 && A < K)
    cout << A + (B - A) * max(1LL * 0, (K - (A - 1)) / 2) + ((K - (A - 1)) % 2)
         << '\n';
  else
    cout << K + 1 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    double A,B;
    cin >> A >> B;
    printf("%.9lf\n",A / B);
}

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

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  ll n, a = 0, b, ans;
  ll aa[200002];
  cin >> n;
  rep(i, 0, n) cin >> aa[i];
  rep(i, 0, n - 1) a += aa[i];
  b = aa[n - 1];
  if(a >= 0 && b >= 0 || a < 0 && b < 0) {
    ans = abs((abs(a) - abs(b)));
  }else {
    ans = abs(a) + abs(b);
  }
  dep(i, n - 2, 1) {
    a -= aa[i];
    b += aa[i];
    ll kans;
    if(a >= 0 && b >= 0 || a < 0 && b < 0) {
      kans = abs((abs(a) - abs(b)));
    }else {
      kans = abs(a) + abs(b);
    }
    ans = min(ans, kans);
  }
  cout << ans << endl;
}


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

public class Main {
 
	public static void main(String[] args) {
 
		    Scanner scanner = new Scanner(System.in);
		    
		    int H = scanner.nextInt();
		    int N = scanner.nextInt();
		    int sum=0;
		    List<Integer> list = new ArrayList<Integer>();
		    for(int i=0;i<N;i++){
		    	list.add(i,scanner.nextInt());
		    	sum = sum + list.get(i);
		    }
		     Collections.sort(list);
		    		 
		    if(H>sum) {
			    System.out.println("No");
		    	
		    }else {
	    	 System.out.println("Yes");
		    }
		  }
}


Measured memory_bytes: 50264
using System;

    class Program
    {
        static void Main(string[] args)
        {
            // get a int p
            string[] ap = Console.ReadLine().Split(' ');
            int a = Convert.ToInt32(ap[0]);
            int p = Convert.ToInt32(ap[1]);

            int result = (a * 3 + p) / 2;

            Console.Write(result);
        }
    }

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

using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<n; i++)


int main() {
    long long A, B, C, K;

    cin >> A >> B>> C >> K ;


    long long ans=0;
        if(A >= K) {
            ans += K;
            cout << K << endl;
            return 0;
        }else {
            ans += A;
            if (B >= K-A){
                cout << ans << endl;
                return 0;
            }else{
                cout << ans + (K-A-B) *-1 << endl;
                return 0;
            }
        }
    

 
}


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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, ll> P;
const ll INF = 10e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<string, vector<string>, greater<string> > PQ_ASK;

const int column = 50;

struct Solution {
    double water, sugar;

    double rate() {
        return (100 * sugar) / (water + sugar);
    }
};

int main() {
    double w1, w2, s1, s2, mr, b;
    cin >> w1 >> w2 >> s1 >> s2 >> mr >> b;

    w1 *= 100;
    w2 *= 100;

    set<double> sugars;
    for (int s1i = 0; s1i * s1 <= b; s1i++) {
        for (int s2i = 0; (s1i * s1) + (s2i * s2) <= b; s2i++) {
            sugars.insert(s1 * s1i + s2 * s2i);
        }
    }

    auto check_rate = [&](double w) {
        double b = w * mr / 100;
        auto it = sugars.upper_bound(b);
        assert(it != sugars.begin());
        it--;
        double l = *it;
        assert((100 * l) / (w + l) <= mr);
        return l;
    };

    auto check_b = [&](double w) {
        double nokori = b - w;
        assert(nokori >= 0);
        auto it = sugars.upper_bound(nokori);
        if (it == sugars.begin()) return 0.0;
        it--;
        double l = *it;
        assert(w + l <= b);
        return l;
    };

    vector<Solution> solutions;

    for (int w1i = 0; w1i * w1 <= b; w1i++) {
        for (int w2i = 0; w1i * w1 + w2i * w2 <= b; w2i++) {
            if (w1i == 0 && w2i == 0) continue;
            double w = w1i * w1 + w2i * w2;
            double s_r = check_rate(w);
            double r_b = check_b(w);
            double now = min(s_r, r_b);
            solutions.push_back(Solution{w, now});
        }
    }


    sort(solutions.rbegin(), solutions.rend(), [](Solution &s, Solution &t) {
        return s.rate() < t.rate();
    });
    Solution s = solutions.front();
//    Solution s = *max_element(solutions.begin(), solutions.end(), [](Solution &s, Solution &t) {
//        return s.rate() < t.rate();
//    });

    assert(s.water + s.sugar <= b);
    assert(s.water * mr / 100 >= s.sugar);
    cout << s.water + s.sugar << ' ' << s.sugar << endl;

}



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

int dp[128][128][1024];
int n;
int P[128];

void init() {
  for(int i = 0; i < 128; ++i) {
    for(int j = 0; j < 128; ++j) {
      for(int k = 0; k < 1024; ++k) {
        dp[i][j][k] = -1;
      }
    }
  }
}

int main() {
  for(;;) {
    init();
    scanf("%d", &n);
    if( n == 0 ) break;
    for(int i = 0; i < n; ++i) {
      scanf("%d", &P[i]);
    }
    dp[0][0][0] = 0;
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        for(int k = 0; k < 1024; ++k) {
          if( dp[i][j][k] == -1 ) continue;
          // step 1
          dp[i+1][j][k] = std::max(dp[i+1][j][k], dp[i][j][k]);
          // step 2
          int n1kyen = (P[i] + 999) / 1000;
          int rem = dp[i][j][k] + n1kyen * 1000 - P[i];
          int next_num500yen = j + (rem >= 500 ? 1 : 0);
          int next_num1kyen  = k + n1kyen;
          int next_rem       = rem >= 500 ? rem - 500 : rem;
          int& next = dp[i+1][next_num500yen][next_num1kyen];
          next = std::max(next, next_rem);
        }
      }
    }    
    int res = (1 << 28);
    int max = -1;
    for(int j = n; j >= 0; --j) {
      for(int k = 0; k < 1024; ++k) {
        if( dp[n][j][k] == -1 ) continue;
        int cost = k * 1000 - 500 * j - dp[n][j][k];
        res = std::min(res, cost);
      }
      if( res != (1 << 28) ) {
        max = j;
        break;
      }
    }
    printf("%d %d\n", max, res);
  }
         
        

  return 0;
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin >> N;
	string S;
	cin >> S;
	int x = 0, mx = 0;
	for (int i = 0; i < N; ++i) {
		if (S[i] == 'I') {
			++x;
		} else {
			--x;
		}
		mx = max(mx, x);
	}
	cout << mx << '\n';
	
	return 0;
}


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

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

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }


const long long INF = 1LL<<60;
 
int N, M;
vector<long long> a, b;
vector<int> c;
 
 
long long dp[1100][5000];
 
int main() {
    int N, M; cin >> N >> M;
    vector<long long> a(M), b(M), c(M, 0); // c はビットで表す
    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i];
        for (int j = 0; j < b[i]; ++j){
            int t; cin >> t; --t;
            c[i] += (1<<t);
        }
    }
 
    for (int i = 0; i < 1100; ++i) for (int j = 0; j < 5000; ++j) dp[i][j] = INF;
    dp[0][0] = 0;
    
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < (1<<N); ++j) {
            chmin(dp[i+1][j], dp[i][j]);
            
            int nj = j | c[i];
            chmin(dp[i+1][j | c[i]], dp[i][j] + a[i]);
        }
    }
 
    cout << (dp[M][(1<<N)-1] < INF ? dp[M][(1<<N)-1] : -1) << endl;               
}

Measured memory_bytes: 43264
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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

    std::vector<int> vec(n);
    for(int i = 0; i < n; ++i){
        std::cin >> vec.at(i);
    }

    std::sort(vec.begin(), vec.end());
    *(vec.end() - 1) = *(vec.end() - 1) / 2;

    std::cout << std::accumulate(vec.begin(), vec.end(), 0) << std::endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
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; }


int main() {
    int l, r, d;
    cin >> l >> r >> d;
    int up = r/d;
    int down = (l-1)/d;
    cout << up-down << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

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

    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    vector<int> sorted(N);
    sorted = A;
    sort(sorted.begin(), sorted.end(), greater<int>());

    for (int i = 0; i < N; i++)
    {
        if (A[i] != sorted[0])
        {
            cout << sorted[0] << endl;
        }
        else
        {
            cout << sorted[1] << endl;
        }
    }
    return (0);
}

Measured memory_bytes: 3200
#include<iostream>
using namespace std;
int main(){
	int k,x;
  	cin >> k >> x;
  	for ( int i = max(-1000000,x-k+1);i<=min(1000000,x+k-1);i++){
    	cout << i ;
      	if(i!=min(1000000,x+k-1)) cout <<" ";
    }
  	return 0;
}


Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 1
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}

	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	k := getNextInt(scanner)
	ss := make([]int, n)
	for i := 0; i < k; i++ {
		d := getNextInt(scanner)
		for j := 0; j < d; j++ {
			a := getNextInt(scanner) - 1
			ss[a]++
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		if ss[i] == 0 {
			ans++
		}
	}
	fmt.Fprintln(writer, ans)
}


Measured memory_bytes: 1836
#pragma region Include
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma endregion

using namespace std;

#pragma region Macros
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define all(c) (c).begin(), (c).end()
#define dump(x) \
  cout << "Line " << __LINE__ << " : " << #x << " = " << (x) << endl
template <class T>
using VV = vector<vector<T>>;

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  os << "[";
  rep(i, vec.size()) os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  os << "]";
  return os;
}

template <typename T>
ostream& operator<<(ostream& os, vector<vector<T>>& mat) {
  os << "[";
  rep(i, mat.size()) os << mat[i] << (i + 1 == mat.size() ? "" : ",\n ");
  os << "]";
  return os;
}

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

template <typename V, typename H>
void resize(vector<V>& vec, const H head) {
  vec.resize(head);
}

template <typename V, typename H, typename... T>
void resize(vector<V>& vec, const H& head, const T... tail) {
  vec.resize(head);
  for (auto& v : vec) resize(v, tail...);
}
constexpr double EPS = 1e-10;
const int INF = 0x3f3f3f3f;
#pragma endregion

long long GCD(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return GCD(b, a % b);
}

int main() {
  ll A, B;
  cin >> A >> B;
  ll d = GCD(A, B);
  ll n = sqrt(d);
  bool is_prime[n + 1];
  for (ll i = 0; i < n + 1; ++i) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  ll div = 0;
  for (ll i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      if (d % i == 0) {
        ++div;
        while (d % i == 0) {
          d /= i;
        }
      }
      for (ll j = 2 * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  if (d != 1) {
    ++div;
  }
  cout << div + 1 << endl;
  return 0;
}

Measured memory_bytes: 1280
#include <stdio.h>
#include <math.h>

struct Point
{
    double x;
    double y;
};


void koch(int n, struct Point p1, struct Point p2)
{
    if (n == 0)
    {
        return;
    }
    struct Point s, t, u;
    double th = M_PI * 60.0 / 180.0;  // 度からラジアンへ単位を変更
    // p1, p2 -> s, t, u
    s.x = (2.0*p1.x + 1.0*p2.x) / 3.0;
    s.y = (2.0*p1.y + 1.0*p2.y) / 3.0;
    t.x = (1.0*p1.x + 2.0*p2.x) / 3.0;
    t.y = (1.0*p1.y + 2.0*p2.y) / 3.0;
    u.x = (t.x - s.x)*cos(th) - (t.y - s.y)*sin(th) + s.x;
    u.y = (t.x - s.x)*sin(th) + (t.y - s.y)*cos(th) + s.y;

    koch(n - 1, p1, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n - 1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n - 1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n - 1, t, p2);
}

int main(void)
{
    struct Point p1, p2;
    int n;
    p1.x = 0;
    p1.y = 0;
    p2.x = 100;
    p2.y = 0;
    scanf("%d", &n);
    printf("%.8f %.8f\n", p1.x, p1.y);
    koch(n, p1, p2);
    printf("%.8f %.8f\n", p2.x, p2.y);
    return 0;
}


Measured memory_bytes: 2084
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>

using namespace std;

int main() {
	int n,h,max,answer;
	cin>>n;
	max=0;
	answer=0;
	for(int i=0; i<n; i++){
		cin>>h;
		if(max<=h){
			max=h;
			answer+=1;
		}
	}
	
	cout<<answer<<endl;
}


Measured memory_bytes: 256
#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 INF 1e9;
using namespace std;
typedef long long ll;

ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

int main() {
  ll N, M;
  cin >> N >> M;

  cout << (100 * N + 1800 * M) * mod_pow(2, M, 1e9 + 7);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 1000000007
#define eps 1e-8
int n,k;
ll a[110],dp[110][100100],sum[100100];

int read()
{
    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;
}

int main()
{
	n=read();k=read();
	rep(i,1,n) a[i]=read();
	dp[0][0]=1;sum[0]=1;
	rep(i,1,k) sum[i]=(sum[i-1]+sum[i])%maxd;
	rep(i,1,n)
	{
		rep(j,0,k) 
		{
			dp[i][j]=sum[j];
			if (j>a[i]) dp[i][j]-=sum[j-a[i]-1];
			dp[i][j]=(dp[i][j]%maxd+maxd)%maxd;
		}
		sum[0]=dp[i][0];
		rep(j,1,k) sum[j]=(sum[j-1]+dp[i][j])%maxd;
		//rep(j,0,k) cout << dp[i][j] << " ";cout << endl;
	}
	printf("%lld",dp[n][k]);
	return 0;
}


Measured memory_bytes: 79360
#include<cstdio>
#include<cstring>
#include<algorithm>

#define Fast register
#define uint unsigned int
#define LL long long
template<class T>inline T Abs(const T&x){return x<0?-x:x;}
template<class T>inline T Min(const T&x,const T&y){return x<y?x:y;}

struct IO{
	#define ISIZE 262144

	char IBUF[ISIZE],*IS,*IT;

	IO():IS(IBUF),IT(IBUF){}
	~IO(){}
	
	inline char Getchar(){return(IS==IT)&&(IT=(IS=IBUF)+fread(IBUF,1,ISIZE,stdin),IS==IT)?EOF:*IS++;}
	template<class T>inline IO&operator>>(T&x){
		Fast T s=0;Fast char c;
		if(IS+25<IT){
			do c=*IS++;while(c<48||c>57);
			do s=s*10+c-48,c=*IS++;while(c>47&&c<58);
		}else{
			do c=Getchar();while(c<48||c>57);
			do s=s*10+c-48,c=Getchar();while(c>47&&c<58);
		}return(x=s,*this);
	}

	#undef ISIZE
}io;

#define Maxn 200001

int a[Maxn];

int main(){
	Fast int n;io>>n;
	for(Fast int i=1;i<=n;++i)io>>a[i];
	std::sort(a+1,a+n+1);
	printf("%d ",a[n]);
	Fast int Ans=0,v=a[n];
	for(Fast int i=1;i<n;i++)
		if(Min(a[i],v-a[i])>Min(Ans,v-Ans))
			Ans=a[i];
	return(printf("%d",Ans),0);
}

Measured memory_bytes: 768
N = int(input())
A = [int(input()) for i in range(N)]

ans = 0
for i in range(N-1):
    ans += A[i] // 2
    if A[i] % 2 and A[i+1]:
        ans += 1
        A[i+1] -= 1

print(ans + A[-1]//2)

Measured memory_bytes: 7072
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

i64 solve(vector<pair<int,i64>> d){
    int n = d.size();
    vector<int> k(n);
    vector<i64> v(n);
    for(int i = 0; i < n; ++i){
        tie(k[i], v[i]) = d[i];
    }
    vector<vector<i64>> res(n);
    for(int i = 0; i < n; ++i)
        res[min(n - 1, k[i])].emplace_back(v[i]);
    i64 ans = 0;
    priority_queue<i64> que;
    for(int i = n - 1; i >= 0; --i){
        for(auto x : res[i])
            que.emplace(x);
        if(!que.empty()){
            ans += que.top();
            que.pop();
        }
    }
    return ans;
}

void solve(){
    int n;
    cin >> n;
    vector<int> k(n), l(n), r(n);
    i64 sum = 0;
    vector<vector<pair<int,i64>>> v(2);
    for(int i = 0; i < n; ++i){
        cin >> k[i] >> l[i] >> r[i];
        if(k[i] == n){
            sum += l[i];
            continue;
        }
        sum += min(l[i], r[i]);
        if(l[i] > r[i])
            v[0].emplace_back(k[i] - 1, l[i] - r[i]);
        else if(l[i] < r[i])
            v[1].emplace_back(n - k[i] - 1, r[i] - l[i]);
    }
    cout << sum + solve(v[0]) + solve(v[1]) << endl;
}


signed main(){
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i)
        solve();
    return 0;
}


Measured memory_bytes: 19192
function main(input) {
    var AA = input.split('\n')[1].split(' ').map((n) => parseInt(n, 10));
    var BB = 0;
    while(AA.every((n)=>(n%2)===0)) {
        BB++;
        AA = AA.map((n)=>n/2);
    }
    console.log(BB);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7500
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << '\n'
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N;
    cin >> N;
    ll w = 0;
    P p;
    rep1(n, 3500) rep(h, 3500) {
        ll x = 4*h*n-N*n-N*h;
        ll y = N*h*n;
        if (x<=0) continue;
        if (y%x!=0) continue;
        w = y/x;
        p = P(n, h);
        break;
    }
    
    printf("%lld %lld %lld\n", p.fi, p.se, w);
    return 0;
}


Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
int a[4];

int main(){
    for(int i=0;i<4;i++){
        int c;
        cin>>c;
        if(c==1)a[0]++;
        if(c==9)a[1]++;
        if(c==7)a[2]++;
        if(c==4)a[3]++;
    }
    if(a[0]&&a[1]&&a[2]&&a[3])puts("YES");
    else puts("NO");
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i<n;i++){
            a[i] = sc.nextInt();
        }

        for (int i = 1; i<n; i++){
            print(a);
            int v = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > v){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = v;
        }
        print(a);
    }

    public static void print(int[] a){
        System.out.print(a[0]);
        for (int i=1;i<a.length;i++){
            System.out.print(" "+a[i]);
        }
        System.out.println();
    }
}

Measured memory_bytes: 33804
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var m = int.Parse(line[0]);
        var f = int.Parse(line[1]);
        var b = int.Parse(line[2]);
        if (m + f < b) { Console.WriteLine("NA"); goto end; }
        if (m > b) { Console.WriteLine(0); goto end; }
        Console.WriteLine(b - m);
        end:;
    }
}

Measured memory_bytes: 9228
#include <iostream>
using namespace std;
int main() {
    int m, n_min, n_max;
    while(cin>>m>>n_min>>n_max){
        if(m==0&&n_min==0&&n_max==0)break;

        int p[m+2];
        for(int i=1; i<=m; i++)cin>>p[i];

        int gap=-1,ans;
        for(int i=n_min; i<=n_max; i++){
            if(gap<=p[i]-p[i+1]){
                gap=p[i]-p[i+1];
                ans=i;
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3100
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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 A,B,C;

int main(){
    cin>>A>>B>>C;
    bool amari[B];
    rep(i,B){
        amari[i]=0;
    }
    for(int i=1;;i++){
        // out(i);
        if(amari[(A*i)%B]==0){
            amari[(A*i)%B]=1;
        }
        else break;
    }
    // rep(i,B){
    //     printf("%d: %d\n",i,amari[i]);
    // }
    repi(i,1,B){
        if(amari[i]==1){
            for(int j=0;j<B-i;j++){
                amari[j+i]=amari[j+i]+amari[j];
            }
        }
    }
    if(amari[C])out("YES");
    else out("NO");
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;
	
	int[] c, n;
	boolean[] used;
	void run() {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (;t>0;t--) {
			c = new int[9]; n = new int[9];
			for (int i=0;i<9;i++) n[i] = sc.nextInt();
			for (int i=0;i<9;i++) {
				char color = sc.next().charAt(0);
				c[i] = color == 'R' ? 0 : ( color == 'G' ? 1 : 2);
			}
			ok = new int[1<<9]; fill(ok, -1);
			System.out.println(solve(0));
		}
	}
	
	int[] ok;
	int solve(int S) {
		if (S == (1<<9)-1) return 1;
		if (ok[S] >= 0) return ok[S];
		
		int ret = 0;
		for (int i=0;i<9;i++) if (((S>>i)&1) == 0)
		for (int j=i+1;j<9;j++) if (((S>>j)&1) == 0) 
		for (int k=j+1;k<9;k++) if (((S>>k)&1) == 0)
			if (is_set(i, j, k)) {
				ret |= solve(S | (1<<i) | (1<<j) | (1<<k));
				if (ret == 1) return ok[S] = ret;
			}
		
		return ok[S] = ret;
	}
	
	boolean is_set(int i, int j, int k) {
		if (c[i] != c[j] || c[j] != c[k]) return false;
		if (n[i] == n[j] && n[j] == n[k]) return true;
		int[] a = {n[i], n[j], n[k]}; sort(a);
		return a[0] + 1 == a[1] && a[1] +1 == a[2];
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 20960
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N,M;
  cin>>N>>M;
  if(N==1&&M==1)cout<<1;
  else if(N==1||M==1)cout<<N+M-3;
  else{cout<<(N-2)*(M-2);}
}

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

int main(){

  int n;
  int d[200];

  while(cin >> n){
    for(int i=0;i<n;i++) cin >> d[i];
    sort(d,d+n);

    long long k = 0;
    for(int i=1;i<n;i++) d[i] += d[i-1];
    for(int i=0;i<n;i++) k += d[i];

    cout << k << endl;
  }

}

Measured memory_bytes: 1172
import sys,math,collections,itertools
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
color1 = -1
color2 = -1
color3 = -1
 
m = 10**9+7
patern = 1
 
for a in A:
    if color1 == a-1 and color2 == a-1 and color3 == a-1:
        patern = (patern * 3)%m
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 == a-1):
        patern = (patern * 2)%m
        color2 = a
 
    elif (color1 == a-1 and color2 == a-1 and color3 != a-1):
        patern = (patern * 2)%m
        color1 = a
    elif (color1 == a-1 and color2 != a-1 and color3 != a-1):
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 != a-1):
        color2 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 == a-1):
        color3 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 != a-1):
        patern = 0
        break
print(patern)


Measured memory_bytes: 21192
n,m=map(int,input().split())

l=[]
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  l.append([s,a])

v=[10**7 for x in range(2**n)]
v[0]=0
for s,a in l:
  for j in range(2**n):
    if v[j] != 10**7:
      v[j|s] = min(v[j|s], v[j]+a)

print(v[2**n-1] if v[2**n-1] != 10**7 else -1)


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

vector<int> minprime;

int num(int n)
{
    map<int, int> mp;
    while(n != 1)   
    {
        mp[minprime[n]]++;
        n /= minprime[n];
    }
    int ret = 1;
    for(auto &it: mp) {
        ret *= (it.second + 1);
    }
    return ret;
}

void solve() {
    int n;
    cin>>n;
    minprime.resize(n + 2, 0);
    for(int i = 2; i * i <= n; i++)
    {
        if(minprime[i] == 0)
        {
            for(int j = i * i; j <= n; j += i)
            {
                if(minprime[j] == 0)
                    minprime[j] = i;
            }
        }
    }               
    rep(i,2,n)
    {
        if(minprime[i] == 0)
            minprime[i] = i;
    }
    vector<int> pfs(n + 2);
    for(int i = 1; i <= n; i++) {
        pfs[i] = num(i);
    }
    int ans = 0;
    rep(i, 1, n - 1) {
        int req = n - i;
        ans += pfs[req];
    }
    cout<<ans<<endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int t = 1;
    //cin>>t;
    for(int test = 1; test <= t; test++) {
        //cout<<"Case #"<<test<<": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 18744
#define _CRT_SECURE_NO_WARNINGS

#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

vector<int> v;
int a[20];
int m;
int n, q;

void dp(int cnt, int value)
{
	if (cnt >= n) {
		v.push_back(value);
		return;
	}
	dp(cnt + 1, value + a[cnt]);
	dp(cnt + 1, value);
}

int main(){
	
	cin >> n;
	int n_1 = 1, n_2 = 1;
	if (n < 2) {
		cout << "1" << endl;
	}
	else {
		for (int i = 2; i < n; i++) {
			n_1 += n_2;
			swap(n_1, n_2);
		}
		cout << n_1 + n_2 << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    now=int(i)
    cnt=int(0)
    while now<k:
        cnt+=1
        now*=2
    add=int(1)

    for j in range(cnt):
        add/=2
    ans+=add

print(ans/n)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;


struct Dice
{
	int label[6];

	void create()
	{
		for (int i = 0; i < 6; i++)
		{
			cin >> label[i];
		}
	}

	void roll(string s)
	{
		int buf[6];
		for (int i = 0; i < 6; i++)
		{
			buf[i] = label[i];
		}

		if (s == "E")
		{
			label[0] = buf[3];
			label[2] = buf[0];
			label[3] = buf[5];
			label[5] = buf[2];
		}
		else if (s == "N")
		{
			label[0] = buf[1];
			label[1] = buf[5];
			label[4] = buf[0];
			label[5] = buf[4];
		}
		else if (s == "S")
		{
			label[0] = buf[4];
			label[1] = buf[0];
			label[4] = buf[5];
			label[5] = buf[1];
		}
		else if (s == "W")
		{
			label[0] = buf[2];
			label[2] = buf[5];
			label[3] = buf[0];
			label[5] = buf[3];
		}
	}

	bool operator ==(Dice d)
	{
		for (int i = 0; i < 6; i++)
		{
			if (label[i] != d.label[i])
			{
				return false;
			}
		}
		return true;
	}
};

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

	Dice* dice = new Dice[n];
	for (int i = 0; i < n; i++)
	{
		dice[i].create();
	}

	string output = "Yes";
	string ls[] = { "E", "N", "S", "W" };

	for (int i = 1; i < n; i++)
	{
		bool b = false;
		for (int j = 0; j < 100000; j++)
		{
			if (dice[0] == dice[i])
			{
				b = true;
				break;
			}
			dice[i].roll(ls[rand() % 4]);
		}

		if (b)
		{
			output = "No";
			break;
		}
	}

	cout << output << endl;
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(ll i = (a); i < (ll) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
#define MAXN 100005
ll dp[MAXN][3];
void solve(vector< vector<ll> > &a, int n)
{
    forn(i,MAXN)
    {
        forn(j,3)
        {
            dp[i][j]=(pow(10,9)+5)*(ll)(-1);
        }
    }
    dp[0][0]=a[0][0], dp[0][1]=a[0][1], dp[0][2]=a[0][2];
    forr(i,1,n)
    {
        forn(j,3)
        {
            forn(k,3)
            {
                if(j==k)
                {
                    continue;
                }
                else dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
            }
        }
 
    }
    cout << max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])) << "\n";
}
 
int main() {
    FIN;
    int n;
    cin >> n;
    vector< vector<ll> > arreglo(n);
    forn(i,n) arreglo[i].resize(3);
    forn(i,n)
    {
        forn(j,3) cin >> arreglo[i][j];
    }
    solve(arreglo, n);
    return 0;
}

Measured memory_bytes: 10968