akhauriyash/Code-Regression huggingface dataset:
// 累積和を使った方法
#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1000000007;

int main()
{
  int N, K;
  cin >> N >> K;
  vector<int64_t> sums(N + 1);
  sums.at(0) = 0;
  for (int i = 1; i < sums.size(); i++)
  {
    sums.at(i) = (sums.at(i - 1) + i) % MOD;
  }

  int64_t ans = 0;
  for (int i = K - 1; i < N + 1; i++)
  {
    int64_t sum_max = sums.at(N) - sums.at(max(N - i - 1, 0));
    int64_t sum_min = sums.at(i);
    ans += sum_max - sum_min + 1;
    ans %= MOD;
  }
  // オーバーフローして負数になる場合はMODを足す
  if (ans < 0)
  {
    ans += MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 4780
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[10][10];
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (s[i][j]=='#'){
		if (i!=1||j!=1){
			int cnt=0;
			if (s[i-1][j]=='#') cnt++;
			if (s[i][j-1]=='#') cnt++;		
			if (cnt>1) return puts("Impossible"),0;
		}
		if (i!=n||j!=m){
			int cnt=0;
			if (s[i+1][j]=='#') cnt++;
			if (s[i][j+1]=='#') cnt++;		
			if (cnt>1) return puts("Impossible"),0;
		}
	}
	if (s[1][1]!='#'||s[n][m]!='#') return puts("Impossible"),0;
	puts("Possible");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

using namespace std;
using P = pair<int, int>;
using T = tuple<int, int, int>;

long long MOD = 1000000007;
long long dp[100005][4];

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

int main() {

	int N;
	cin >> N;

	int ans = N * N*N;

	cout << ans << endl;
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<long long> a(n);
  for (auto&& e : a) {
    cin >> e;
  }
  auto dfs = [&](auto&& self, int i, int ci, int j, int cj) -> long long {
    if (j - i == 1) {
      return ci * a[i] + cj * a[j];
    }
    long long res = 1e18;
    for (int k = i + 1; k < j; ++k) {
      auto cur = self(self, i, ci, k, ci + cj);
      cur -= (ci + cj) * a[k];
      cur += self(self, k, ci + cj, j, cj);
      res = min(res, cur);
    }
    return res;
  };
  cout << dfs(dfs, 0, 1, n - 1, 1) << '\n';
}


Measured memory_bytes: 256
H, W, K = map(int, input().split())

S = []
no_ichigo = -1
ichigo_count = 1
for i in range(H):
    count = 0
    tmp = input()
    tmp_s = []
    # print(tmp)
    for s in tmp:
        # print(s)
        if s == ".":
            tmp_s.append(ichigo_count)
        elif count >0:
            ichigo_count += 1
            tmp_s.append(ichigo_count) 
        else:
            tmp_s.append(ichigo_count)
            #ichigo_count += 1
            count += 1
    if no_ichigo<0 and count == 0:
        tmp_s = [0 for i in range(W)]
        no_ichigo -= 1
        ichigo_count -= 1
    elif no_ichigo>=0 and count == 0:
        tmp_s = S[-1]
        ichigo_count -= 1
    elif no_ichigo<0:
        no_ichigo *= -1 
        no_ichigo -= 1
    ichigo_count += 1
    # print(tmp_s)
    S.append(tmp_s)
    
if no_ichigo > 0:
    for i in range(no_ichigo):
        S[i] = S[no_ichigo]

for s in S:
    print(" ".join(map(str,s)))


Measured memory_bytes: 7156
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

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

const ll mod = 1e9 + 7;
const ll inf = 1e18;

map<int, bool> disable;

ll selected_sports(vector<ll> A){
    for(auto a : A){
        if(!disable[a]){
            return a;
        }
    }
    return -1;
}


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

    // input
    ll N, M;
    cin >> N >> M;

    vector<vector<ll> > A(N);
    FOR(i, 0, N){
        FOR(j, 0, M){
            ll a;
            cin >> a;
            A[i].push_back(a);
        }
    }

    FOR(i, 1, M+1){
        disable[i] = false;
    }

    ll min_Q = inf;

    FOR(_, 0, M){
        map<int, int> mp;
        FOR(i, 0, N){
            ll id = selected_sports(A[i]);
            mp[id]++;
        }
        ll max_id = -1;
        ll max_count = -1;
        for(auto p : mp){
            ll id = p.first;
            ll count = p.second;
            if(count > max_count){
                max_count = count;
                max_id = id;
            }
        }
        ll Q = max_count;
        min_Q = min(min_Q, Q);

        // 最人気のsportsを消す
        disable[max_id] = true;
    }

    p(min_Q);
    
    return 0;
}

Measured memory_bytes: 1536
N = int(input())
 
def abc114_c(s):
  if(int(s) > N):
    return 0
  if(all(s.count(c) > 0 for c in "753")):
    ans = 1
  else:
    ans = 0
  for c in "753":
    ans += abc114_c(s+c)
  return ans
print(abc114_c("0"))

Measured memory_bytes: 3060
# from sys import exit
# A, B, C = [int(n) for n in input().split()]
while(True):
    N = int(input())
    if N == 0:
        break
    S = str(input())
    L = len(S)
    F = {"M":0, "S":0, "L":0}
    hands = [{"M":0, "S":0, "L":0} for _ in range(N)]

    cur = 0
    while(cur != L):
        if S[cur] == "M":
            hands[cur%N]["M"] += 1
        elif S[cur] == "S":
            F["M"] += hands[cur%N]["M"]
            hands[cur%N]["M"] = 0
            F["S"] += hands[cur%N]["S"] + 1
            hands[cur%N]["S"] = 0
            F["L"] += hands[cur%N]["L"]
            hands[cur%N]["L"] = 0
        else:
            hands[cur%N]["M"] += F["M"]
            F["M"] = 0
            hands[cur%N]["S"] += F["S"]
            F["S"] = 0
            hands[cur%N]["L"] += F["L"] + 1
            F["L"] = 0
        cur += 1

    ans = [sum(d.values()) for d in hands]
    ans = sorted(ans)
    for e in ans:
        print(e, end=" ")
    print(sum(F.values()))



Measured memory_bytes: 5624
#include<cstdio>
#include<algorithm>

using namespace std;

const int MA=25000001;

long long a[MA],b[MA],c[MA];
int M,N;

int main(){
	scanf("%d",&M);
	scanf("%d",&N);
	
	long long m0,md;
	scanf("%lld%lld",&m0,&md);
	a[0]=m0;
	for(int i=1;i<M;i++){
		a[i]=(a[i-1]*58+md)%(N+1);
	}
	
	long long n0,nd;
	scanf("%lld%lld",&n0,&nd);
	b[0]=n0;
	for(int i=1;i<N;i++){
		b[i]=(b[i-1]*58+nd)%(M+1);
	}
	
	sort(b,b+N);
	reverse(b,b+N);
	
	for(int i=0;i<M;i++){
		c[0]++;
		c[a[i]]--;
	}
	for(int i=1;i<N;i++){
		c[i]+=c[i-1];
	}
	
	long long csum=0,bsum=0;
	for(int i=0;i<N;i++){
		csum+=c[i];
		bsum+=b[i];
		bsum=min(bsum,csum);
	}
	printf("%lld\n",bsum);
	return 0;
}

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

int main(){
    int n; cin >> n;
    ll a[n] = {0}; rep(i, n) cin >> a[i];

    if(n == 1) {
        cout << a[0] << endl;
        return 0;
    }

    ll ans = lcm(a[0], a[1]);
    loop(i, 2, n){
        ans = lcm(ans, a[i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3644
a, b = map(int, input().split())
c = []
for i in range(b):
    d = int(input())
    c.append([d, list(map(int, input().split()))])
e = 0
for i in range(1, a+1):
    for j in c:
        if i in j[1]:
            break
    else:
        e += 1
print(e)

Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
int n;
string s,t,ans;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>s>>t;
    for (int i=0;i<n;i++){
        ans.push_back(s[i]);
        ans.push_back(t[i]);
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    int higher = a+b;
    if(2*a-1>higher)higher =a+a-1;
    if(b+b-1>higher)higher = b+b-1;
    printf("%d\n", higher);
    return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        long K;
        K = sc.nextLong();

        final Solver solver = new Solver();
        solver.solve(K);
    }
}

class Solver {
    public void solve(long K) {
        int[] a = {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};
        System.out.println(a[(int) (K - 1)]);
    }
}



Measured memory_bytes: 22228
#include <cstdio>
#include <algorithm>

using namespace std;

int player_score[200];
int score[3][200];
int main(){
	int n,f,h,i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d",&score[0][i],&score[1][i],&score[2][i]);
	}
	for(i=0;i<n;i++) player_score[i]=0;
	for(h=0;h<3;h++){
		for(i=0;i<n;i++){
			f=0;
			for(j=0;j<n;j++){
				if(i!=j && score[h][i]==score[h][j]) f=1;
			}
			if(f==0) player_score[i]+=score[h][i];
		}
	}
	for(i=0;i<n;i++) printf("%d\n",player_score[i]);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
typedef long long ll;
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	while(n < 1000)
	{
		int tmp = n;
		if(tmp / 100 == (tmp % 100) / 10 && tmp / 100 == tmp % 10)
		{
			cout << tmp << endl;
			return 0;
		}
		n++;
	}	
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000)

def dfs(A, i):
    A.append(i)
    if len(str(i)) == 10:
        return A
    x = int(list(str(i))[-1])-1 if int(list(str(i))[-1]) > 0 else 0
    y = int(list(str(i))[-1])+2 if int(list(str(i))[-1]) < 9 else 10
    for v in range(x, y):
        i = i * 10 + v
        dfs(A, i)
        i = int(str(i)[:len(str(i))-1])

K = int(input())
B = []
for i in range(1, 10):
    A = []
    dfs(A,i)
    B = B + A
B.sort()
print(B[K-1])

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

int main(){
	int n;
	int a[100];
	bool dp[105][105] = {};
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++){
		dp[i][i] = true;
	}
	for(int i = 2;i <= n;i++){
		for(int j = 0;j < n - i + 1;j++){
			for(int k = j + 1;k <= j + i - 1;k++){
				if(dp[j][k] && dp[k][j + i]) dp[j][j + i] = true;
			}
			if(a[j] != a[j + i - 1]) continue;
			int num = a[j];
			int l = j,r = j + i - 1;
			while(l < r && a[l] == num) l++;
			while(l < r && a[r] == num) r--;
			if(l == r && a[l] == num) dp[j][j + i] = true;
			if(dp[l][r + 1]) dp[j][j + i] = true;
			for(int k = j + 1;k <= j + i - 2;k++){
				if(a[k] == num && dp[j + 1][k] && dp[k + 1][j + i - 1]) dp[j][j + i] = true;
			}
		}
	}
	/*for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++) cout << dp[i][j] << " ";
		cout << endl;
	}*/
	if(dp[0][n]) cout << "yes" << endl;
	else cout << "no" << endl;
	return 0;
}

Measured memory_bytes: 3108
#![allow(warnings)]
fn read<T: std::str::FromStr>() -> T {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  read::<String>().split_whitespace()
    .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
  (0..n).map(|_| read_vec()).collect()
}

fn main() {
  let n: u8 = read();
  let s: String = read();

  let mut chars = Vec::new();
  for ch in s.chars() {
    let ascii_code: u8 = ch as u8 + n;
    if ascii_code <= 90 {
      chars.push(ascii_code as char);
    } else {
      let ascii_code = ascii_code - 26;
      chars.push(ascii_code as char);
    }
  }

  let ans: String = chars.into_iter().collect();
  println!("{}", ans);

}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define MOD 1000000007 
#define INF 1000000000000000000
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing

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


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
    int i,N,total=0;
    int sum1=0;
    int sum2=0;
    int diff=0;
    int temp=0;
    int a[100];

    scanf("%d", &N);
    for(i=0;i<N;i++){
        scanf("%d", &a[i]);
        total+=a[i];
    }

    sum1=a[0];
    sum2=total-sum1;
    diff=abs(sum1-sum2);
    for(i=1;i<N-1;i++){
        sum1+=a[i];
        sum2=total-sum1;
        temp=abs(sum1-sum2);
        if(diff>temp){
            diff=temp;
        }
        else{
            printf("%d\n", diff);
            return 0;
        }
    }
    printf("%d\n", diff);

    return 0;
}

Measured memory_bytes: 128
Scanf.scanf "%d %d %d" (fun h w k ->
    let c = Array.init h (fun _ -> Scanf.scanf " %s" (fun c -> c)) in

    let count mask =
        let rec loop_y y acc =
            let rec loop_x x acc =
                if x = w then acc else
                    let m = (1 lsl (y + w)) lor (1 lsl x) in
                    let acc = if m land mask > 0 then acc else
                        if c.(y).[x] = '.' then acc else acc + 1
                    in
                    loop_x (x + 1) acc
            in
            if y = h then acc else loop_y (y + 1) (loop_x 0 acc)
        in
        loop_y 0 0
    in

    let rec loop i acc =
        if i < 0 then acc else
            let acc = if count i = k then acc + 1 else acc in
            loop (i - 1) acc
    in
    loop ((1 lsl (h + w))-1) 0 |> Printf.printf "%d\n"
)

Measured memory_bytes: 5832
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <iomanip>
#include <climits>

using namespace std;
 
int main()
{
    char X,Y;
    cin >> X >> Y;
   
    int n=X-Y;
    
    if(n>0)
		cout<<'>'<<endl;
	if(n<0)
		cout<<'<'<<endl;
	if(n==0)
		cout<<'='<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>

using namespace std;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  n--;

  string w;
  char head_char;
  char tail_char;

  map<string, int> m;
  cin >> w;
  m.insert(pair<string, int>(w, 1));

  head_char = w.front();
  tail_char = w.back();

  while(n--) {
    cin >> w;
    head_char = w.front();

    if (head_char != tail_char) {
      cout << "No" << endl;
      return 0;
    }

    tail_char = w.back();

    if ((int)m.count(w) == 0) {
      m.insert(pair<string, int>(w, 1));
    } else {
      cout << "No" << endl;
      return 0;
    }

  }

  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

module ModOp = struct
  let prime = 1_000_000_007
  let (-) a b = (a + prime - b) mod prime
  let (+) a b = (a + b) mod prime
  let ( * ) a b = (a * b) mod prime

  let rec pow x n =
    if n = 0 then 1
    else if n mod 2 = 0 then pow (x*x) (n/2)
    else x * pow (x*x) (n/2)
end

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  if String.length line = 0 then []
  else
    (match sep with
     | None -> List.map String.of_char @@ String.to_list line
     | Some sep -> String.split_on_char sep line)
    |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let (x,n) = scan "%d %d" Tuple2.make
let p = scan_list ~sep:' ' Int.of_string

let () =
  ListL.map (0++101) ~f:(fun v ->
      if List.exists ((=) v) p then (Int.max_num, v)
      else (abs (x - v), v))
  |> List.sort Tuple2.compare
  |> List.first
  |> Tuple2.second
  |> Printf.printf "%d\n"


Measured memory_bytes: 5568
#include <bits/stdc++.h>
#define MAXN 1010
#define pii pair<int, int>
#define pb push_back
typedef long long ll;

using namespace std;

int n, m, dp[MAXN][MAXN], mod = 1e9 + 7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char a;
            cin >> a;
            if(i == 0 and j == 0){
                if(a == '#') dp[1][1] = 0;
                else dp[1][1] = 1;
                continue;
            }
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % mod;
            if(a == '#') dp[i + 1][j + 1] = 0;
        }
    }
    cout << dp[n][m];
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll k, a, b;
    cin >> k >> a >> b;
    reps(i, a, b + 1) {
        if (i % k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
using namespace std;
const double EPS = 1e-9;

int n , m;
int book[100];
double simulate(double width){
	int height = 0;
	double remain = 0;
	for(int i = 0 ; i < n ; i++){
		if( remain - book[i] < -EPS){
			height++;
			remain = width; 
		}
		remain -= book[i];
		if( remain < -EPS) return false;
	}
	return height <= m;
}

int main(){
	while(cin >> m >> n && (m||n) ){
		for(int i = 0 ; i < n ; i++) cin >> book[i];
		int ans = 1e9;
		
		double l = 0 , r = 1500000;
		for(int i = 0 ; i < 128 ; i++){
			double mid = (l+r) / 2; //切り上げ(いろいろな都合で)
			if( simulate(mid) ){ //midで入れるのに成功したらrをmにする
				r = mid;
			}else{
				l = mid;		//midで入れるのに失敗したら
			}
		}
		printf("%.lf\n",l);
		/*
		for(int i = 0 ; i < n ; i++){
			int sum = 0;
			for(int j = i ; j < n ; j++){
				sum += book[j];
				if( simulate(sum) ) ans = min( ans , sum );
			}
		}
		cout << ans << endl;
		*/
	}
}

Measured memory_bytes: 0
<?php
$n = trim(fgets(STDIN));
$a = explode(" ", trim(fgets(STDIN)));
$b = explode(" ", trim(fgets(STDIN)));
$c = explode(" ", trim(fgets(STDIN)));

$sum = array_sum($b);

for($i=0; $i<count($a)-1; $i++){
    if($a[$i]+1 == $a[$i+1]){
        $sum += $c[$a[$i]-1];
    }
}
echo $sum;
?>

Measured memory_bytes: 4604
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl
#define INF 1000000;
#include <map>
#include <math.h>
 
using ll = long long;
using namespace std;

ll n, k;
const ll mod = 1000000007;


int main(){
    int r;
    cin >> r;
    out(r*r);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

int f(int x) { return x % __builtin_popcount(x); }

int dp[200009];

ll modpow(ll n, ll k, ll m) {
    ll res = 1;
    while(k) {
        if(k & 1) res = res * n % m;
        n = n * n % m;
        k >>= 1;
    }
    return res;
}

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

    FOR(i, 1, 200009) dp[i] = dp[f(i)] + 1;

    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = count(ALL(s), '1');

    int a = 0, b = 0;
    rep(i, n) if(s[i] == '1') {
        a = (a + modpow(2, n - 1 - i, cnt + 1)) % (cnt + 1);
        if(cnt > 1) b = (b + modpow(2, n - 1 - i, cnt - 1)) % (cnt - 1);
    }

    rep(i, n) {
        if(s[i] == '0') {
            cout << dp[(a + modpow(2, n - 1 - i, cnt + 1)) % (cnt + 1)] + 1
                 << endl;
        } else {
            if(cnt <= 1) {
                cout << 0 << endl;
            } else {
                cout << dp[(b + cnt - 1 - modpow(2, n - 1 - i, cnt - 1)) %
                           (cnt - 1)] +
                            1
                     << endl;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 4548
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void solve() {
    int n, m, q; cin >> n >> m >> q;
    vector<vector<char>> s(n, vector<char>(m));
    rep(i, n) {
        rep(j, m) {
            cin >> s[i][j];
        }
    }
    vector<vector<int>> cnt_edgea(n + 1, vector<int>(m + 1, 0)), cnt_edgeb(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> cnt_vertex(n + 1, vector<int>(m + 1, 0));
    rep(i, n) {
        rep(j, m) {
            cnt_vertex[i + 1][j + 1] = cnt_vertex[i + 1][j] + cnt_vertex[i][j + 1] - cnt_vertex[i][j];
            cnt_edgea[i + 1][j + 1] = cnt_edgea[i + 1][j] + cnt_edgea[i][j + 1] - cnt_edgea[i][j];
            cnt_edgeb[i + 1][j + 1] = cnt_edgeb[i + 1][j] + cnt_edgeb[i][j + 1] - cnt_edgeb[i][j];
            if(s[i][j] == '1') {
                cnt_vertex[i + 1][j + 1] ++;
                if(i + 1 < n && s[i + 1][j] == '1') {
                    cnt_edgeb[i + 1][j + 1] ++;
                }
                if(j + 1 < m && s[i][j + 1] == '1') {
                    cnt_edgea[i + 1][j + 1] ++;
                }
            }
        }
    }
    while(q--) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        --x1; --y1;
        int vs = cnt_vertex[x2][y2] - cnt_vertex[x2][y1] - cnt_vertex[x1][y2] + cnt_vertex[x1][y1];
        int es = cnt_edgea[x2][y2 - 1] - cnt_edgea[x2][y1] - cnt_edgea[x1][y2 - 1] + cnt_edgea[x1][y1] + cnt_edgeb[x2 - 1][y2] - cnt_edgeb[x2 - 1][y1] - cnt_edgeb[x1][y2] + cnt_edgeb[x1][y1];
        //cerr << vs << " " << es << endl;
        cout << vs - es << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 54272
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
const ll MOD (1e9+7);
const ll INF (2e9);
const int MAX_N (200001);

int par_road[MAX_N];
int rank_road[MAX_N];
int par_train[MAX_N];
int rank_train[MAX_N];



struct PARENT{
    int num;//num 番目の都市は（問題上では1番目～n番目だが、0番目～n-1番目と表記することにする）
    int road;//道に関するUnion-Find木でroad番目の都市を親に持ち
    int train;//線路に関するUnion-Find木でtrain番目の都市を親に持つ
};

bool cmp(const PARENT a,const PARENT b){//sort用関数　roadで昇順ソート、roadが等しかったらtrainで昇順
    if(a.road==b.road){
        return a.train<b.train;
    }else{
        return a.road<b.road;
    }
}

void init(int n,int *par,int *rank){//Unioo-Find木を生成
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
}

int find(int x,int *par){//根探し
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x],par);
    }
}

void unite(int x, int y,int *par,int *rank){//連結
    x=find(x,par);
    y=find(y,par);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]){
            rank[x]++;
        }
    }
}

bool same(int x,int y,int *par){//根が等しいか判定
    return find(x,par)==find(y,par);
}

int main(void) {
    int n,k,l;
    cin>>n>>k>>l;

    init(n,par_road,rank_road);//道についてのUnion-Find木を生成
    init(n,par_train,rank_train);//線路についてのUnion-Find木を生成
    int p,q,r,s;
    for(int i=0;i<k;i++){//道の情報によって連結していく
        cin>>p>>q;
        unite(p-1,q-1,par_road,rank_road);//0~n-1番目の道　としたので　p-1 q-1
    }
    for(int i=0;i<l;i++){//線路の情報によって連結していく
        cin>>r>>s;
        unite(r-1,s-1,par_train,rank_train);
    }

    PARENT *parent=new PARENT[n];
    for(int i=0;i<n;i++){//num番目の都市は　road番目の都市を道根に持ち、train番目の都市を線路根に持つ
        parent[i].num=i;
        parent[i].road=find(i,par_road);
        parent[i].train=find(i,par_train);
    }




    sort(parent,parent+n,cmp);


    int *answer=new int[n];
    int memo_start=0,count=1;
    int i;

    for(i=1;i<n;i++){
        if(parent[i].road==parent[i-1].road && parent[i].train==parent[i-1].train){
            count++;
        }else{
            for(memo_start;memo_start<i;memo_start++){//memo_startは現在の位置を指して終わる
                answer[(parent[memo_start]).num]=count;
            }
            count=1;
        }
    }

 
    for(memo_start;memo_start<i;memo_start++){
        answer[parent[memo_start].num]=count;
    }

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

    return 0;
}

Measured memory_bytes: 6912
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, K;
i64 A[101010];
i64 poss[101010];
i64 acc[101010];

int main()
{
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; ++i) {
		scanf("%lld", A + i);
	}
	poss[0] = acc[0] = 0;
	for (int i = 1; i <= N; ++i) {
		acc[i] = acc[i - 1] + A[i - 1];
		poss[i] = poss[i - 1] + max(0LL, A[i - 1]);
	}

	i64 ret = -(1LL << 62LL);
	for (int l = 0; l <= N - K; ++l) {
		ret = max(ret, poss[l] + (poss[N] - poss[l + K]) + max(0LL, acc[l + K] - acc[l]));
	}
	printf("%lld\n", ret);
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
 
using namespace std;
#define int long long

const int N = 1e5 + 5, oo = (int)2e9;
int c[N], cnt[N], M[N];
 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

    int n, m, a, b, k=0;
    cin >> n >> m;
    int sum = 0, mi = 0, res = oo;
    for (int i = 0; i <= m; i++) {
        cnt[i] = 0;
        M[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        if (i != 0) {
            a = c[i] + 1;
            a -= (a > m ? m : 0);
            cnt[a]--;
            b = c[i];
            b += (c[i] < c[i - 1] ? m : 0);
            M[a] += b - c[i - 1] - 1;
            a = c[i - 1] + 2;
            a -= (a > m ? m : 0);
            cnt[a]++;
            if (c[i] < c[i-1]) {
                mi += m - c[i-1];
                sum += m - c[i-1] + c[i];
                if (c[i-1] != m) {
                    k++;
                }
            }
            else sum += c[i] - c[i - 1];
        }
    }
    res = sum - mi;
    for (int i = 2; i <= m; i++) {
        mi -= M[i];
        k += cnt[i];
        mi += k;
        if (sum - mi < res) res = sum - mi;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i!=n;i++)

using namespace std;
int main(void){
    int n;string s,t;
    cin >> n >> s >> t;
    string ans="";
    REP(i,n){
        ans.push_back(s[i]);
        ans.push_back(t[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
using namespace std;

int main(){

	int N,E,limit,tmp,minimum;
	scanf("%d %d",&N,&E);

	limit = pow(2,N);

	int cost[N][N];

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++)cost[i][k] = BIG_NUM;
	}

	int from,to,value;

	for(int i = 0; i < E; i++){
		scanf("%d %d %d",&from,&to,&value);
		cost[from][to] = value;
	}

	int*** dp = new int**[N+1];
	for(int i = 0; i <= N; i++){
		dp[i] = new int*[N];
		for(int k = 0; k < N; k++){
			dp[i][k] = new int[limit];
		}
	}

	minimum = BIG_NUM;
	for(int start = 0; start <= 0; start++){

		for(int i = 0; i <= N; i++){
			for(int k = 0; k < N; k++){
				for(int p = 0; p < limit; p++)dp[i][k][p] = BIG_NUM;
			}
		}

		tmp = pow(2,start);

		dp[0][start][tmp] = 0;

		for(int i = 1; i <= N; i++){
			for(int k = 0; k < N; k++){
				for(int p = 0; p < limit; p++){
					if(dp[i-1][k][p] != BIG_NUM){
						for(int a = 0; a < N; a++){
							if(p & (1 << a)){
								if(i == N && a == start){
									if(cost[k][start] != BIG_NUM)dp[i][start][limit-1] = min(dp[i][start][limit-1],dp[i-1][k][p]+cost[k][start]);
								}
							}else{
								if(cost[k][a] != BIG_NUM){
									tmp = p + pow(2,a);
									dp[i][a][tmp] = min(dp[i][a][tmp],dp[i-1][k][p]+cost[k][a]);
								}
							}
						}
					}
				}
			}
		}

		minimum = min(minimum,dp[N][start][limit-1]);
	}

	if(minimum == BIG_NUM){
		printf("-1\n");
	}else{
		printf("%d\n",minimum);
	}

}

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

const int INF = 1e9;

int main() {
  int n, m;
  cin>>n>>m;
  map<int, int> x;
  for (int i=0; i<n; i++) {
    int k;
    cin>>k;
    for (int j=0; j<k; j++) {
      int a;
      cin>>a;
      ++x[a];
    }
  }
  int cnt = 0;
  for (auto y: x) {
    if (y.second == n) {
      ++cnt;
    }
  }
  cout<<cnt<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
long long N;
  cin >> N;
long long a[N];
  for(int i = 0;i < N;i++){
  cin >> a[i];
  }

int cnt = 0;
int now = 0;  
bool b = true;
  
  while(b){
  for(int i = 0;i < N;i++){
   if((now == 0) && (a[i] % 2 == 0)){
   a[i] /= 2;
   now = 1; 
   cnt++;
   break;
   }    
    
    if((i == N - 1) && (now == 0)){
   b = false;
   }   
  }    
    now = 0;
  }
  
  cout << cnt << endl;
  return 0;
  
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll x;
	ll sum = 0LL;
	cin >> n >> x;
	ll a[n];
	for(int i = 0; i<n; i++){
		cin >> a[i];
	}
	sort(a,a+n);
	int ans = 0;
	for(int i = 0; i+1<n; i++){
		sum += a[i];
		if(sum<=x){
			ans++;
		}
	}
	sum += a[n-1];
	if(sum==x){
		ans++;
	}
	cout << ans << endl;

}

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

int main() {
    ll a,b,c,count=0;
    ll na,nb,nc;
    cin >> a >> b >> c;

    if (a%2==1 or b%2==1 or c%2==1) {
        cout << 0 << endl;
    }
    else if (a==b and b==c) cout << -1 << endl;
    else {
        while (true) {
            if (a%2==1 or b%2==1 or c%2==1) {
                cout << count << endl;
                break;
            }
            else {
                na=(b+c)/2;nb=(a+c)/2;nc=(a+b)/2;
                a=na;b=nb;c=nc;
                ++count;
                if (count > 9999999) {
                    cout << "-1" << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;

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

    if (N % 2 == 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    N /= 10;
    while (N > 0) {
        ans += N;
        N /= 5;
    }

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

Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			int N=in.nextInt();//人数(1<=i<=N)
			int T=in.nextInt();//10円玉ストレージの初期保存枚数
			int H=in.nextInt();//100円玉ストレージの初期保存枚数
			int L=in.nextInt();//10円玉ストレージの保存可能枚数(上限を超えたらbreak)
			int a[]=new int[N];//iの持つ10円の数
			int b[]=new int[N];//iの持つ100円の数
			for(int i=0;i<N;i++)
			{
				a[i]=in.nextInt();
				b[i]=in.nextInt();
			}
			int turn=0;
			int input=0;
			for(;;)
			{
				if(a[turn]==0&&b[turn]==0)
					break;
				if(a[turn]>0)
				{
					a[turn]--;
					input+=10;
					T++;
					if(T>L)
						break;
				}
				else if(b[turn]>0)
				{
					b[turn]--;
					input+=100;
					H++;
				}
				if(input>=90)
				{
					input-=90;
					while(input!=0)
					{
						a[turn]++;
						input-=10;
						T--;
					}
				}
				if(T<0)
					break;
				turn=(turn+1)%N;
			}
			System.out.println(++turn);
		}
	}
	
	static public void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}
}

Measured memory_bytes: 20212
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

fn main() {
    input! {
        n: usize,
        m: usize,
        ms: [(Usize1, Usize1); m],
    }

    let mut gs = vec![vec![]; n];
    for e in ms {
        gs[e.0].push(e.1);
        gs[e.1].push(e.0);
    }

    let mut rs = vec![std::usize::MAX; n];
    rs[0] = 0;
    let mut vd = std::collections::VecDeque::new();
    vd.push_back(0);

    while let Some(to) = vd.pop_front() {
        for &g in &gs[to] {
            if rs[g] != std::usize::MAX {
                continue;
            }
            rs[g] = to;
            vd.push_back(g);
        }
    }

    for i in 0..n {
        if i == 0 {
            echo!("Yes");
        } else {
            echo!(rs[i] + 1);
        }
    }
}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int main() {
    int n,m,a[10]={},v[10]={},poz,c,ok=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=11;
    }
    while(m--){
        cin>>poz>>c;
        if(c==0 && poz==1 && n>1) ok=0;
        if(a[poz]!=11 && a[poz]!=c) ok=0;
        a[poz]=c; 
    }
    if(ok==0) cout<<-1;
    else{
        if(n==1 && a[1]==11) a[1]=0;
        else if(a[1]==11) a[1]=1;
        cout<<a[1];
        for(int i=2;i<=n;i++){
            if(a[i]==11) a[i]=0;
            cout<<a[i];
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <cctype>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	string s, t, r;
	cin >> s >> t >> r;
	char a = toupper(s[0]); char b = toupper(t[0]); char c = toupper(r[0]);
	cout << a<< b << c << endl;
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()

const int MAX = 1e5+10;
const int MOD = 1e9+7;

string L;
ll dp[MAX][2];

int solve() {
    dp[0][0] = 2;
    dp[0][1] = 1;
    FOR (i, 1, L.size()) {
        if (L[i] == '0') {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = (dp[i-1][1] * 3) % MOD;
        } else {
            dp[i][0] = dp[i-1][0] * 2 % MOD;
            dp[i][1] = (dp[i-1][1] * 3 + dp[i-1][0]) % MOD;
        }
    }
    return (dp[L.size()-1][0]  + dp[L.size()-1][1]) % MOD;
}

int main() {
    cin >> L;
    cout << solve() << endl;
}

Measured memory_bytes: 2048
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 50 + 10;
int dp[N][N][N * N];

void add(int& x, int y) {
  x += y;
  x %= MOD;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  if (m % 2) {
    puts("0");
    return 0;
  }
  m /= 2;
  dp[0][0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      for (int k = 0; k <= m; ++k) {
        if (k + j <= m) add(dp[i + 1][j][k + j], dp[i][j][k]);
        if (k + j <= m) add(dp[i + 1][j][k + j], (int64)dp[i][j][k] * 2 * j % MOD);
        if (k + j + 1 <= m) add(dp[i + 1][j + 1][k + j + 1], dp[i][j][k]);
        if (j > 0 && k + j - 1 <= m) {
          add(dp[i + 1][j - 1][k + j - 1], (int64)dp[i][j][k] * j * j % MOD);
        }
      }
    }
  }
  printf("%d\n", dp[n][0][m]);
  return 0;
}


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef tuple<int,int,int,int> Tiiii;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){

    int n,m,l,q;
    cin>>n>>m>>l;
    Vi a(m),b(m),c(m);
    vector<vector<Pii>> connect(n);
    REP(i,0,m){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
    }
    cin>>q;
    Vi s(q),t(q);
    vin(s,t);
    REP(i,0,q){s[i]--;t[i]--;}

     vector<vector<int>> dist(n,Vi(n,INF));
     REP(i,0,n) dist[i][i]=0;
     REP(i,0,m){
         dist[a[i]][b[i]]=c[i];
         dist[b[i]][a[i]]=c[i];
     }
     
     REP(i,0,n){
         REP(j,0,n){
             REP(k,0,n){
                 chmin(dist[j][k],dist[j][i]+dist[i][k]);
             }
         }
     }

    // REP(i,0,n){
    //     REP(j,0,n) cout<<dist[i][j]<<" ";
    //     cout<<endl;
    // }

    VVi dist2(n,Vi(n,INF));
    REP(i,0,n) dist2[i][i]=0;
    REP(i,0,n){
        REP(j,0,n){
            if(dist[i][j]<=l){
                dist2[i][j]=1;
                dist2[j][i]=1;
            }
        }
    }
     REP(i,0,n){
         REP(j,0,n){
             REP(k,0,n){
                 chmin(dist2[j][k],dist2[j][i]+dist2[i][k]);
             }
         }
     }

    REP(i,0,q){
        if(dist2[s[i]][t[i]]!=INF)cout<<dist2[s[i]][t[i]]-1<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}


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

class weighted_unionfind {
  vector<int> par, weight;
  
public:
  weighted_unionfind(int n) {
    for (int i = 0; i < n; i++) {
      par.push_back(i);
      weight.push_back(0);
    }
  }
  
  int find(int n) {
    if (par.at(n) == n) return n;
    int r = find(par.at(n));
    weight.at(n) += weight.at(par.at(n));
    return par.at(n) = r;
  }
  
  void merge(int m, int n, int d) {
    d += diff(m) - diff(n);
    m = find(m), n = find(n);
    par.at(n) = m;
    weight.at(n) = d;
  }
  
  int diff(int n) {
    find(n);
    return weight.at(n);
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  weighted_unionfind t(n);
  for (int i = 0; i < m; i++) {
    int l, r, d;
    cin >> l >> r >> d;
    l--; r--;
    if (t.find(l) != t.find(r)) {
      t.merge(l, r, d);
    } else {
      if (t.diff(r) - t.diff(l) != d) {
        puts("No");
        return 0;
      }
    }
  }
  puts("Yes");
}


Measured memory_bytes: 1396
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = scan.nextInt();
		}
		Sort sort = new Sort();
		arr = sort.insertion(arr);
	}
}

class Sort{
	public int[] insertion(int[] A){
		showArray(A);
		for(int i=1; i<A.length; i++){
			int v = A[i];
			int j = i-1;
			while(j >= 0 && A[j] > v){
				A[j+1] = A[j];
				j--;
			}
			A[j+1] = v;
			showArray(A);
		}
		return A;
	}
	public void showArray(int[] A){
		for(int i=0; i<A.length; i++){
			System.out.print(A[i]);
			if(i != A.length-1)System.out.print(" ");
		}
		System.out.println("");
	}
}

Measured memory_bytes: 34724
#include <stdio.h>

int main(){
	
int n;
scanf ("%d", &n);

int check = 0;

for (int i = 1; i < 10; i++){
	for (int j = 1; j < 10; j++){
		
		if (n == i * j){
			check = 1;
			break;
		}
}
	}
	if (check == 1){
		puts ("Yes");
	}
	else if (check == 0) {
		puts ("No");
	}
	return 0;
}

Measured memory_bytes: 2064
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        Integer a = Integer.parseInt(sc.next());
        Integer b = Integer.parseInt(sc.next());
        Integer.parseInt(sc.next()); // 未使用となる変数c

        // 主処理
        int result = a * b / 2;

        // 出力
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 23764
#include <stdio.h>
const int INF=(1<<30);
int main(){
    int n,s,a[100010],back=0,ans=INF;
    long long int now=0;
    scanf("%d%d",&n,&s);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        now+=a[i];
        while(now>=s){
            if(i-back+1<ans)ans=i-back+1;
            now-=a[back];
            back++;
            if(back>i)break;
        }
    }
    if(ans==INF)printf("0\n");
    else printf("%d\n",ans);
}

Measured memory_bytes: 3140
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
int main()
{
    int n;
    scanf("%d",&n);
    ll ans = 1;
    for(int i = 1; i <= n; ++i)
        ans = (ans%mod)*i % mod;
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;
#define mp make_pair
#define pb push_back
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n;
int a[100005];
LL ans = 0;

int main() {
    scanf("%d", &n);
    forn(i, n) scanf("%d", a + i);
    forn(i, n - 1) if (a[i] % 2 == 1 && a[i + 1]) {
        --a[i];
        --a[i + 1];
        ++ans;
    }
    forn(i, n) ans += a[i] / 2;
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;

const int MOD = 1000000007;
const int INF = 1001001001;

#define rep(i, n)  for(int i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()

int main() {
    int n, m;
    cin >> n;
    map<string, int> card;
    rep(i, n) {
        string s;
        cin >> s;
        card[s] += 1;
    }
    cin >> m;
    rep(i, m) {
        string s;
        cin >> s;
        card[s] -= 1;
    }

    int ans = 0;

    for(auto itr = card.begin(); itr != card.end(); itr++) {
        ans = max(ans, itr->second);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256