akhauriyash/Code-Regression huggingface dataset:
S = gets.chomp

months = %w(01 02 03 04 05 06 07 08 09 10 11 12)
years = months + (13..99).to_a.map(&:to_s) + ["00"]

if months.include?(S[0,2])
  if months.include?(S[2,4])
    puts "AMBIGUOUS"
  elsif years.include?(S[2,4])
    puts "MMYY"
  else
    puts "NA"
  end
elsif years.include?(S[0,2])
  if months.include?(S[2,4])
    puts "YYMM"
  else
    puts "NA"
  end
else
	puts "NA"
end


Measured memory_bytes: 1788
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = mutableListOf<Long>()
    (1..n).forEach { aList.add(readLine()!!.toLong()) }
    val aList2 = aList.sorted()
    val max = aList2[n-1]
    val max2 = aList2[n-2]
    for(i in 0 until n){
        if(aList[i]==max){
            println(max2)
        }else{
            println(max)
        }
    }
}


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

#define ll long long
#define ull unsigned long long 
#define endl "\n"
#define pii pair<int, int>
#define all(a) a.begin(),a.end()

template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

int main(){
    ll x, y;
    cin >> x >> y;
    ll ans = INT_MAX;

    if(x<=y){
        ans = min(ans, y-x);
    }
    if(-x <= y){
        ans = min(ans, 1+y-(-x));
    }
    if(x<=-y){
        ans = min(ans, 1-y-x);
    }
    if(-x <= -y){
        ans = min(ans, 2-y+x);
    }
    cout << ans;
}


Measured memory_bytes: 3612
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let input: Vec<i32> = s.split_whitespace().map(|x| x.parse::<i32>().unwrap()).collect();

    let A = input[0];let B = input[1];
    let xs = [A+B,A-B,A*B];
    let ans = xs.iter().max().unwrap();
    println!("{}",ans);
}


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

int main(){
    int N,K;
    cin >> N >> K;
    ll A[N+1];
    A[0]=0;
    for(int i=1;i<=N;i++){
        ll temp;
        cin >> temp;
        A[i]=A[i-1]+temp;
    }
    
    ll answer=0;
    int p=40;
    while(p>=0){
        ll x = answer+pow(2,p);
        ll ans=0;
        for(int i=0;i<N;i++){
            for(int j=i+1;j<=N;j++){
                ll y = A[j]-A[i];
                if((x&y)==x) ans++;
            }
        }
        if(ans>=K) answer=x;
        p--;
    }
    cout << answer << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
#define FOR(i, m, n) for(int i = m;i < n;i++)
int MAX_N = 100000;
#define REP(i, n) for(int i = 0;i < n;i++)
int MAX_W = 100000;

int main(){
  int N;cin >> N;
  vector<int>d(N);REP(i,N)cin >> d[i];
  VSORT(d);
  int tem = 0;
  int count = 0;
  REP(i,N){
    if(i != 0 &&tem == d[i]){
      continue;
    }
    tem = d[i];
    count++;
  }
  cout << count << endl;
}


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

int main(){
    int a, b, c, counter=0;
    cin >> a >> b >> c;
    if(a != b) counter++;
    if(a != c) counter++;
    if(b != c) counter++;
    if(counter == 0) counter++;
    cout << counter << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 205, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

int a[MX][MX*2];

int main() {
  int h, w;
  scanf("%d%d",&h,&w);
  rep(i,h)rep(j,w) scanf("%d",&a[i][j]);
  vvi dp(h+1,vi(h+1,a[0][0]));

  rrep(s,h+w-2) {
    vvi p(h+1,vi(h+1));
    swap(dp,p);
    int mh = min(h,s);
    rep(i,mh)rep(j,mh) {
      for (int ni = i; ni <= i+1; ++ni) {
        for (int nj = j; nj <= j+1; ++nj) {
          int c = a[ni][s-ni];
          if (ni != nj) c += a[nj][s-nj];
          maxs(dp[ni][nj],p[i][j]+c);
        }
      }
    }
  }
  cout<<dp[h-1][h-1]<<endl;
  return 0;
}































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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {
    
    // source code
  int n;
  cin >> n;
  int h[n];
  int temp = 0;
  int now = 0;
  map<int,int> mtemp;
  rep(i,n)
  {
    cin >> h[i];
    if(temp < h[i] || mtemp.empty())
    {
      mtemp.insert(make_pair(i, 0));
      now = i;
    }
    else
    {
      mtemp.at(now)++;
    }
    temp = h[i];
  }
  int max = 0;
  int place = 0;
  for (auto v : mtemp)
  {
    if(max < v.second)
    {
      max = v.second;
    }
  }
  
  cout << max << endl;
}



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

using namespace std;

int main(void){
  int n, p, m = 300000, num = 0;
  cin >> n;

  for (int i = 0; i < n; i++){
    cin >> p;
    if (p < m){
      num++;
    }
    m = min(m, p);
  }


  cout << num << endl;


  return 0;
}


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

using namespace std;

vector<pair<int, int> > G[110000];
map<int, int> mp;
int N;
vector<int> visited;
void dfs(int from, int current, int distance){
  int S = G[current].size();
  for(int i=0;i<S;i++){
    if(G[current][i].first == from)continue;
    if((distance+G[current][i].second)%2==0)mp[G[current][i].first]=0;
    else mp[G[current][i].first]=1;
    dfs(current, G[current][i].first, distance+G[current][i].second);
  }
  return;
}

int main(){
  cin >> N;
  for(int i=0;i<N-1;i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--;v--;
    if(u>v)swap(u, v);
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  }

  visited.resize(N, 0);
  int rootID=0;
  int maxnodes=0;
  for(int i=0;i<N;i++){
    if(G[i].size()>maxnodes){
      maxnodes=G[i].size();
      rootID=i;
    }
  }
  mp[rootID]=0;
  dfs(-1, rootID, 0);
  for(int i=0;i<N;i++){
    cout << mp[i] << endl;
  }
  
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;
const int INF = 1 << 30;
const long long LINF = 1LL << 60;
const long long MOD = 1000000000 + 7;
const double PI = acos(-1);

int main() {
	int N; cin >> N;
	long long num = 1000000000000000000;
	vector<long long> A(N);
	rep(i, N)cin >> A[i];

	rep(i, N) {
		if (A[i] == 0) {
			cout << 0;
			return 0;
		}
	}
	long long preNum = A[0];
	long long ans = A[0];
	rep(i, N - 1) {
		ans *= A[i + 1];
		if (preNum > ans || ans>num) {
			cout << -1;
			return 0;
		}
		preNum = ans;
	}
	cout << ans;
}



Measured memory_bytes: 4048
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            var tmp = Console.ReadLine().Split(' ');
            var s = tmp[0];
            var t = tmp[1];
            var result = string.Empty;

            for (int i = 0; i < n; i++)
            {
                result += s[i].ToString() + t[i].ToString();
            }

            Console.WriteLine(result);
        }

        static List<long> ReadLine()
        {
            var line = Console.ReadLine();
            var array = line.Split(' ');

            return array.Select(x => long.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define KOZYUN(a) sort(all(a),greater<int>())
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    INT(n);
    string s; cin >> s;
    int ans = 0;
    rep(i,n-2){
        if(s.substr(i,3) == "ABC")  ans++;
    }
    ANS;

    return 0;
}

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

using namespace std;

int main(){

    double a, b, c, n, r, minEdge;

    while(cin >> a >> b >> c, a || b || c){

        minEdge = min(min(hypot(a, b), hypot(a, c)), hypot(b, c));

        cin >> n;

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

            cin >> r;

            if(minEdge < 2 * r){
                cout << "OK" << endl;
            } else {
                cout << "NA" << endl;
            }

        }

    }

}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int main(){
  long long N,M,a;
  cin>>N>>M;

  if (N*2 >= M) {
    a = M/2; //cが足りない
  }  else {
    a = N+(M-N*2)/4; //cが余った
  }

  cout<<a;
  
  return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! dvec {
    ($t:expr ; $len:expr) => {
        vec![$t; $len]
    };

    ($t:expr ; $len:expr, $($rest:expr),*) => {
        vec![dvec!($t; $($rest),*); $len]
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

const MOD: i64 = 1e9 as i64 + 7;

fn main() {
    input! {
        n: usize, k: i64,
        a: [i32; n]
    };

    let mut total = 0;
    for i in 0..n {
        let mut w_count = 0i64;
        for j in i+1..n {
            if a[i] > a[j] {
                w_count += 1;
            }
        }
        let mut p_count = 0i64;
        for j in 0..i {
            if a[i] > a[j] {
                p_count += 1;
            }
        }
        let initial = w_count;
        let diff = w_count + p_count;
        let last = initial + diff * (k - 1) % MOD;

        total += (initial + last) % MOD * k % MOD * 500000004 % MOD;
        total %= MOD;
    }
    println!("{}", total);
}


Measured memory_bytes: 4352
#include "iostream"
#include "string"
#include "vector"
#include "algorithm"
#include "functional"
#include "cmath"
#include "set"
#include "cstdio"

#define NDEF -200
#define NA -100
#define N_MAX 10000

std::vector<unsigned int> required_match{2, 5, 5, 4, 5, 6, 3, 7, 6};

std::vector<int> max_digit(N_MAX + 1, NDEF);


// setting max_digit[0]
void init_max_digit() {
    max_digit[0] = 0L;
    return;
}

// get max_digit by DP
int get_max_digit(int num_match, std::set<unsigned int> required_match_part) {
    if(max_digit[num_match] != NDEF) {
        return max_digit[num_match];
    } else {
        int maybe_max = NA;
        for (unsigned int required_num:required_match_part) {
            int remain_match = num_match - required_num;
            int remain_digit = (remain_match >= 0) ?
                    get_max_digit(remain_match, required_match_part) : NA;
            if (remain_digit >= 0) {
                maybe_max = std::max(maybe_max, remain_digit + 1);
            }
        }
        max_digit[num_match] = maybe_max;
        return maybe_max;
    }
}

int main(){
    init_max_digit();

    std::cin.tie(0);
    std::ios_base::sync_with_stdio(false);

    // get values from input
    int n, m;
    std::vector<int> a;

    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a_i;
        std::cin >> a_i;
        a.push_back(a_i);
    }

    // main procedure
    std::vector<int> digits_allowed = a; // sorted as desc
    std::sort(digits_allowed.begin(), digits_allowed.end(), std::greater<int>());

    std::set<unsigned int> required_match_part;
    for (int digit:digits_allowed) {
        required_match_part.insert(required_match[digit - 1]);
    }

    std::string ans;
    int remain_digit_num = get_max_digit(n, required_match_part);
    int remain_match_num = n;

    while (remain_match_num > 0) {
        int is_find = false;
        for (int digit:digits_allowed) {
            int match_num_tmp = remain_match_num - required_match[digit - 1];
            if (match_num_tmp < 0) {
                continue;
            }

            int digit_num_tmp = get_max_digit(match_num_tmp,
                    required_match_part);
            if (digit_num_tmp == remain_digit_num - 1){
                ans += std::to_string(digit);
                remain_match_num = match_num_tmp;
                remain_digit_num--;
                is_find = true;
                break;
            }
        }
        if (!is_find) {
            break;
        }
    }

    // output
    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 2432
#include<iostream>
using namespace std;
int main(){
    int H,W,i,x;
    i=0;
    x=0;
    string a="";
    while(1){
    cin>>H>>W;
    if(H==0&&W==0) break;
    while(x<W){
        a+="#";
        x+=1;
    }
    while(i<H){
        cout<<a<<endl;
        i+=1;
    }
    cout<<endl;
    x=0;
    i=0;
    a="";
    }
}


Measured memory_bytes: 3156
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

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

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

var pfs map[int]int

// PfsMap : 素因数分解し、マップを作成
func PfsMap(n int) bool {
	for n%2 == 0 {
		pfs[2] = pfs[2] + 1
		// if pfs[2] == 2 {
		// 	return false
		// }
		n = n / 2
		for n%2 == 0 {
			n = n / 2
		}
	}

	for i := 3; i*i <= n; i = i + 2 {
		for n%i == 0 {
			pfs[i] = pfs[i] + 1
			// if pfs[i] == 2 {
			// 	return false
			// }
			n = n / i
			for n%i == 0 {
				n = n / i
			}
		}
	}

	if n > 2 {
		pfs[n] = pfs[n] + 1
	}
	return true
}

// GCD : greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N := getInt()
	a := getInts(N)
	sc := a[0]
	pfs = make(map[int]int)
	PfsMap(a[0])
	for i := 1; i < N; i++ {
		PfsMap(a[i])
		sc = GCD(sc, a[i])
	}
	// out(sc, pfs, a)
	flg := true
	for _, e := range pfs {
		if e != 1 {
			flg = false
			break
		}
	}
	if flg == true {
		out("pairwise coprime")
		return
	}
	if sc == 1 {
		out("setwise coprime")
		return
	}
	out("not coprime")

}


Measured memory_bytes: 19080
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1<<30;
const ll  longinf = 1LL<<60;
const int mod=1000000007;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
int main(){
  int n;
  cin>>n;
  int a[n],sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  if(sum%10!=0){
    cout<<sum<<endl;
    return 0;
    }
  sort(a,a+n);
  rep(i,n){
    if(a[i]%10!=0){
      cout<<sum-a[i]<<endl;
      return 0;
      }
    }
  cout<<"0"<<endl;
  return 0;
  }

  




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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n, h, w;
string s;
Vi dir = {1, 0, -1, 0, 1};

int main() {
    while (true) {
        cin >> w >> h;
        if (w == 0 && h == 0) {
            break;
        }

        V<VVi> wall(h, VVi(w, Vi(4, 0)));
        REP(i, 2*h-1) {
            int H = i/2;
            if (i%2 == 0) {
                REP(j, w-1) {
                    int x; cin >> x;
                    if (x == 1) {
                        wall[H][j][0] = 1;
                        wall[H][j+1][2] = 1;
                    }
                }
            } else {
                REP(j, w) {
                    int x; cin >> x;
                    if (x == 1) {
                        wall[H][j][3] = 1;
                        wall[H+1][j][1] = 1;
                    }
                }
            }
        }

        VVi dis(h, Vi(w, -1));
        queue<Pii> q;
        q.push({0, 0});
        dis[0][0] = 1;
        while (!q.empty()) {
            int y = q.front().first, x = q.front().second;
            q.pop();
            REP(i, 4) {
                int Y = y + dir[i+1], X = x + dir[i];
                if (Y < 0 || X < 0 || Y >= h || X >= w) continue;
                if (wall[y][x][i] == 1) continue;
                if (dis[Y][X] != -1) continue;
                dis[Y][X] = dis[y][x] + 1;
                q.push({Y, X});
            }
            if (dis[h-1][w-1] != -1) {
                std::cout << dis[h-1][w-1] << '\n';
                break;
            }
        }
        if (q.empty()) {
            std::cout << 0 << '\n';
        }
    }

    return 0;
}



Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
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; }
const ll INF = 1LL << 60;
int main(){
    string s = "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";
    vector<int> v = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << v[k-1] << endl;

    return 0;
}

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

//============================================================================
typedef struct{
    char suit;
    int  value;
    int  order;
}TCard;
//============================================================================
int BubbleSort(TCard *ary, int n)
{
    int i,j,k,l, cnt; TCard chg;

    for (k=cnt=0, l=n; k<n-1; k++, l--)
    for (i=0,j=1; j<l; i++, j++){
        if (ary[j].value<ary[i].value)
            chg=ary[i], ary[i]=ary[j], ary[j]=chg, cnt++;
	}
    return cnt;
}
//============================================================================
int SelectionSort(TCard *ary, int n)
{
    int i,j,minj,cnt; TCard chg;

    for (i=cnt=0; i<n; i++){
        for (j=minj=i; j<n; j++){
            if (ary[j].value<ary[minj].value)
                minj=j;
        }
        if (i!=minj)
            chg=ary[i], ary[i]=ary[minj], ary[minj]=chg, cnt++;
    }
    return cnt;
}
//============================================================================
void selectionsort()
{
    int i,cnt, n; TCard *ary;

    scanf("%d", &n);
    ary=malloc(n*sizeof(TCard));
    for (i=0; i<n; i++)
        scanf("%d", &ary[i].value);
    cnt=SelectionSort(ary, n);
    for (i=0; i<n; i++){
        if (i) printf(" ");
        printf("%d", ary[i].value);
    }
    printf("\n%d\n", cnt);
    free(ary);
}
//============================================================================
void prnval(TCard *ary, int n)
{
    int i,nstb;

    for (i=nstb=0; i<n; i++){
        if (i) printf(" ");
        printf("%c%d", ary[i].suit, ary[i].value);
        if (i<n-1)
        if (ary[i].value==ary[i+1].value && ary[i+1].order<ary[i].order)
                nstb++;
    }
    printf("\n%s\n", (nstb)?"Not stable":"Stable");
}
//============================================================================
void cardsort()
{
    int i,cnt,nstb,n; TCard *bary, *sary; char sub[10];

    scanf("%d", &n);
    bary=malloc(n*sizeof(TCard));
    sary=malloc(n*sizeof(TCard));
    for (i=0; i<n; i++){
        scanf("%s", sub);
        //scanf("%c%d", &bary[i].suit, &bary[i].value);
        bary[i].suit=*sub;
        bary[i].value=sub[1]-'0';
        bary[i].order=i;
    }
    memcpy(sary, bary, sizeof(TCard)*n);
    cnt=BubbleSort(bary, n);
    prnval(bary, n);
    cnt=SelectionSort(sary, n);
    prnval(sary, n);
    free(sary);
    free(bary);
}
//============================================================================
int main(void)
{
    //selectionsort();
    cardsort();
    return 0;
}
//============================================================================

Measured memory_bytes: 612
#include <cstdio>
#include <set>

using namespace std;

const int N = 200'009;

int a[N];
bool w[N];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    w[i] = false;
  }
  int len = 0, last = -1;
  for (int i = 0; i < n; ++i) {
    if (a[i] > last) {
      ++len;
      if (len == k) {
        w[i] = true;
        --len;
      }
    } else {
      len = 1;
    }
    last = a[i];
  }
  set<int> s;
  for (int i = 0; i < k; ++i) {
    s.insert(a[i]);
  }
  int ans = 0;
  if (!w[k - 1]) {
    ++ans;
  }
  for (int i = k; i < n; ++i) {
    s.erase(a[i - k]);
    bool ok = false;
    if (a[i - k] > *s.begin()) {
      ok = true;
    }
    if (a[i] < *s.rbegin()) {
      ok = true;
    }
    s.insert(a[i]);
    if (!w[i] && ok) {
      ++ans;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (w[i]) {
      ++ans;
      break;
    }
  }
  printf("%d\n", ans);
}


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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

//↓0-originか1-originでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   //0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) //1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;

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

const ld PI = acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
//const int mod = 998244353;

/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(10);

    int n,m; cin >> n >> m;
    vec<string> a(n); rep(i,n) cin >> a[i];
    vec<string> b(m); rep(i,m) cin >> b[i];

    for(int i = 0; i <= n - m; ++i) {
        for(int j = 0; j <= n - m; ++j) {
            bool can = 1;
            for(int k = 0; k < m; ++k) {
                for(int l = 0; l < m; ++l) {
                    if(b[k][l] != a[k+i][l+j]) {
                        can = 0;
                        break;
                    }
                }
                if(!can) break;
            }
            if(can) {
                cout << "Yes" <<'\n';
                return 0;
            }
        }
    }
    cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def primeFactorization(n, primes):
    ans = []
    temp = n
    for p in primes:
        while temp%p == 0:
            ans.append(p)
            temp //= p
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()

    primes = sieve(N)
    cnt = collections.Counter()
    
    for i in range(2, N + 1):
        pf = primeFactorization(i, primes)
        for k, v in pf.items():
            cnt[k] += v

    ans = 1
    for i in cnt.values():
        ans *= (i + 1)
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10316
#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++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

// 解説は条件付き期待値
// （ゲームの回数の期待値）= 
// Σ(ゲーム中AかBが出る回数がM回である確率(A Bは正規化する)) * (ゲーム中AかBが出る回数がM回である時に、Cが出る回数も含めた総合回数の期待値)
// https://www.creativ.xyz/best-of-2n-1-1080/

const int MAX = 2000005;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod/i) % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}


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

    int N;
    ll A, B, C;
    cin >> N >> A >> B >> C;

    COMinit();
    ll a = A * modpow(A+B, mod-2) % mod;
    ll b = B * modpow(A+B, mod-2) % mod;
    ll c = 100 * modpow(100-C, mod-2) % mod;

    ll ans = 0;
    repr(m, N, 2*N){
        ll add = c * m % mod;
        add *= COM(m-1, N-1) * modpow(a, N) % mod * modpow(b, m-N) % mod;
        chmod(add);
        ans += add;
        chmod(ans);
    }
    repr(m, N, 2*N){
        ll add = c * m % mod;
        add *= COM(m-1, N-1) * modpow(a, m-N) % mod * modpow(b, N) % mod;
        chmod(add);
        ans += add;
        chmod(ans);
    }
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 47104
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MODADD(ADD_X,ADD_Y)  (ADD_X+ADD_Y)%MOD;
#define MODSUB(SUB_X,SUB_Y)  (SUB_X-SUB_Y)+MOD)%MOD;
#define MODMUL(MUL_X,MUL_Y)  (MUL_X*MUL_Y)%MOD;
#define LCM(LCM_X,LCM_Y) (LCM_X*LCM_Y)/__gcd(LCM_X,LCM_Y);
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
int dx[]= {1,0,-1,0,1,-1,1,-1};
int dy[]= {0,1,0,-1,1,-1,-1,1};

int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int cnt=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int temp=i;
        int cur=0;
        while(temp>0){
            temp/=10;
            cur++;
        }
        if(cur%2)
            cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 3648
A,B,N=list(map(int,input().split()))
l=set()
for i in range(A,A+N):
    if i > B:
        break
    l.add(i)
for i in reversed(range(B-N+1,B+1)):
    if i < A:
        break
    l.add(i)
l=list(l)
l.sort()
for i in l:
    print(i)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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 S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll N;
ll A[100];
ll dp[100];

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

  rep( i, N )
    std::cin >> A[i];

  dp[0] = 1000;

  rep( i, N ) {
    if( i-1 >= 0 )
      chmax( dp[i], dp[i-1] );

    rep( j, i ) {
      ll cnt = dp[j]/A[j];
      chmax( dp[i], dp[j]%A[j]+cnt*A[i] );
    }
  }

  std::cout << dp[N-1] << std::endl;

  return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int MOD = 1000000007;
int MUL(int x, int y) { return (long long)x * y % MOD; }
int ADD(int x, int y) { return (x + y) % MOD; }
int main()
{
    string S;
    cin >> S;
    vector<int> la(S.size()), lq(S.size()), rc(S.size()), rq(S.size());
    for (int i = 1; i < S.size(); i++) {
        la[i] = la[i-1] + (S[i-1] == 'A');
        lq[i] = lq[i-1] + (S[i-1] == '?');
    }
    for (int i = S.size()-2; i >= 0; i--) {
        rc[i] = rc[i+1] + (S[i+1] == 'C');
        rq[i] = rq[i+1] + (S[i+1] == '?');
    }
    int q = count(S.begin(), S.end(), '?');
    vector<int> pow3(q+1);
    pow3[0] = 1;
    for (int i = 1; i < q+1; i++) pow3[i] = MUL(pow3[i-1], 3);
    
    int answer = 0;
    for (int i = 1; i < S.size() - 1; i++) {
        if (!(S[i] == 'B' || S[i] == '?')) continue;
        answer = ADD(answer, MUL(MUL(la[i], rc[i]), pow3[lq[i]+rq[i]]));
        answer = ADD(answer, MUL(MUL(lq[i], rc[i]), pow3[lq[i]+rq[i]-1]));
        answer = ADD(answer, MUL(MUL(la[i], rq[i]), pow3[lq[i]+rq[i]-1]));
        answer = ADD(answer, MUL(MUL(lq[i], rq[i]), pow3[lq[i]+rq[i]-2]));
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
double pi = acos(-1.0);
const double EPS=1e-9;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define t() ll t;cin>>t;while(t--) 

int main()
{ 
    fastio;
    ll i,n,j;
    cin>>n;
    vector<ll>a(n+1),dp(n+1);
    for(i=1;i<=n;i++) cin>>a[i];
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for(i=3;i<=n;i++) dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    cout<<dp[n];
    
    
       
}

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

using namespace std;

#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define INF (int)1e9
typedef long long int int64;

void print() {
    cout << endl;
}

void print(const char* s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(char s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(string s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int64 s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int s, bool endline = true) {
    cout << s;
    if (endline) print();
}

template <typename T, typename T2>
void print(pair<T, T2>& p, bool endline = true) {
    cout << "(";
    print(p.first, false);
    cout << ", ";
    print(p.second, false);
    cout << ")";

    if (endline) print();
}

template <typename T>
void print(T& t, bool endline = true) {
    cout << "[";
    for (auto it = t.begin(); it != t.end(); ++it) {
        if (it != t.begin()) cout << ", ";
        print(*it, false);
    }
    cout << "]";

    if(endline) print();
}

template <typename T>
vector<T> operator+(const vector<T> &a, const vector<T> &b)
{
    vector<T> ret;
    ret.reserve( a.size() + b.size() );                // preallocate memory
    ret.insert( ret.end(), a.begin(), a.end() );        // add A;
    ret.insert( ret.end(), b.begin(), b.end() );        // add B;

    return ret;
}

template <typename T>
vector<T> &operator+=(vector<T> &a, const vector<T> &b)
{
    a.reserve( a.size() + b.size() );                // preallocate memory without erase original data
    a.insert( a.end(), b.begin(), b.end() );         // add B;
    return a;
}

bool c(const pair<int,int> &a, const pair<int,int> &b) 
{ 
    return (a.first + a.second > b.first + b.second); 
}

int main() {
    // g++ -Wall -Wextra -O2 -std=c++17 helloworld.cpp
    int n, m;

    cin >> n >> m;

    vector<vector<char>> grid (n, vector<char> (m));
    
    int count = 0;
    queue<pair<int, int>> children;

    for(int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for(int j = 0; j < m; ++j) {
            grid[i][j] = s[j];

            if (s[j] == '.') {
                count++;
            } else {
                children.push({i, j});
            }
        }
    }

    int ret = -1;
    const int d[4][2] {{0,1}, {1,0}, {0,-1}, {-1,0}};

    while(children.size() != 0) {
        int size = children.size();

        for(int i = 0; i < size; ++i) {
            auto c = children.front();
            children.pop();

            for(auto& p : d) {
                int x = c.first + p[0];
                int y = c.second + p[1];

                if(x >= 0 and x < n and y >= 0 and y < m) {
                    if(grid[x][y] == '.') {
                        grid[x][y] = '#';
                        children.push({x, y});
                    }
                }
            }
        }

        ret++;
    }

    print(ret);


    return 0;
}

Measured memory_bytes: 9488
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < M; i++){
    int L, R, D;
    cin >> L >> R >> D;
    L--;
    R--;
    E[L].push_back(make_pair(D, R));
    E[R].push_back(make_pair(-D, L));
  }
  vector<int> d(N);
  vector<int> comp(N, -1);
  bool ok = true;
  for (int i = 0; i < N; i++){
    if (comp[i] == -1){
      comp[i] = i;
      d[i] = 0;
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (auto P : E[v]){
          int dist = P.first;
          int w = P.second;
          if (comp[w] != -1){
            if (d[w] != d[v] + dist){
              ok = false;
            }
          } else {
            comp[w] = i;
            d[w] = d[v] + dist;
            Q.push(w);
          }
        }
      }
    }
  }
  if (ok){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int main(void) {
    int N;
    int64_t sum = 0;
    cin >> N;

    if(N >= 9){
        sum += 9;
        if(N > 99) {
            if( N >= 999){
                sum += 900;
                if(N > 9999) {
                    if(N >= 99999) {
                        sum += 90000;
                    } else {
                        sum += N - 9999;
                    }
                }
            } else {
                sum += N-99;
            }
        }
    } else {
        sum = N;
    }
    
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  string s, t;
  cin >> s >> t;
  int ans = t.size();
  for (int i = 0; i < s.size() - t.size() + 1; i++) {
    int cnt = 0;
    for (int j = 0; j < t.size(); j++) {
      if (t[j] != s[i + j]) cnt++;
    }
    ans = min(ans, cnt);
  }
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>

#define INC(i, a, b) for(int i = a; i < b; ++i)
#define DEC(i, a, b) for(int i = a; i > b; --i)
#define REP(i, n)    for(uint i = 0; i < n; ++i)

typedef unsigned int uint;
typedef unsigned long ul;
typedef long long  ll;
typedef unsigned long long ull;

using namespace std;

void TFprint(bool b, std::string T, std::string F){
    if(b){
        cout << T << endl;
    }else{
        cout << F << endl;
    }
}

int main(){
    int A, B, X;
    cin >> A >> B >> X;
    TFprint((A <= X && B >= X - A), "YES", "NO");
    return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
p = list(map(int,input().split()))
m=0
s=[0]
for i in range(n):
    s.append((p[i])*(p[i]+1)/2/p[i])
    s[i+1] += s[i]

for i in range(n-k+1):
    a=s[k+i]-s[i]
    if(m<a):m=a
print(m)


Measured memory_bytes: 25060
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int mod = 1000000007;

ll s[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  unordered_map<int,int>mp;
  int n,K;
  cin>>n>>K;
  mp[0] = 1;
  ll sum = 0,ret = 0;
  for(int i=1;i<=n;i++){
    if(i>=K){
      mp[s[i-K]%K-(i-K)]--;
    }
    int x;
    cin>>x;
    sum+=x;
    s[i] = sum;
    int tt = sum%K-i;
    //bug2(i,tt)
    ret+=mp[tt];
    tt = sum%K - i + K;
    ret+=mp[tt];
    //if(i==5)bug2(tt,mp[tt]);
    mp[sum%K-i]++;
  }
  if(K==1)ret=0;
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 18420
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  ll N;
  cin >> N;
  vec<ll> P(N), Q(N);
  REP(i, N) cin >> P[i];
  REP(i, N) cin >> Q[i];

  vec<ll> p(N);
  iota(ALL(p), 1);

  ll a = 0, b = 0;
  for (ll i = 1; next_permutation(ALL(p)); i++) {
    if (p == P) {
      a = i;
    }
    if (p == Q) {
      b = i;
    }
  }

  cout << abs(a - b) << endl;
  return 0;
}


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

using namespace std;

const int N = 1e4 + 10;
const int M = 110;

bool vis[N];

int n, s, a[M];

int main(){
	while(~scanf("%d", &n)){
		s = 0;
		for(int i=1; i<=n; i++){
			scanf("%d", a+i);
			s += a[i];
		}
		if(s % 10){
			printf("%d\n", s);
			continue;
		}
		memset(vis, 0, sizeof(vis));
		vis[0] = 1;
		for(int i=1; i<=n; i++){
			for(int j=s; j>=a[i]; j--){
				vis[j] = vis[j] || vis[j-a[i]];
			}
		}
		int ans = 0;
		for(int i=s; i>=0; i--){
			if(vis[i] && i%10){
				ans = i;
				break;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
#define INF 100000000

int n;
vector<P>es[25];
int vi[25] = {0};
int ne[25] = {0};
vector<int>res;
int ans = 0;

void dfs(int now, int cost){
	for(int i = 0; i < es[now].size(); i++){
		int t = es[now][i].first;
		int c = es[now][i].second;
		if(ne[t] == 1) continue;
		ans += c * 2;
		dfs(t, cost + c);
	}
	res.push_back(cost);
	return;
}

int main(){
	while(true){
	cin >> n;
	if(n == 0) return 0;
	memset(vi, 0, sizeof(vi));
	memset(ne, 0, sizeof(ne));
	for(int i = 0; i < n - 1; i++){
		int a,b,t;
		cin >> a >> b >> t;
		es[a].push_back(P(b, t));
	}
	queue<int>que;
	que.push(1);
	vi[1] = 1;
	//vector<int>v;
	while(!que.empty()){
		int now = que.front();
		que.pop();
		bool foo = false;
		for(int u = 0; u < es[now].size(); u++){
			if(!vi[es[now][u].first]){
				foo = true;
				vi[es[now][u].first] = 1;
				que.push(es[now][u].first);
			}
		}
		if(!foo) ne[now] = 1;
	}
	for(int i = 1; i <= n; i++){
		//if(ne[i]) cout << i << endl;
	}
	memset(vi, 0, sizeof(vi));
	vi[1] = 1;
	ans = 0;
	dfs(1, 0);
	sort(res.begin(),res.end());
	cout << ans - res[res.size()-1] << endl;
	res.clear();
	for(int i = 0; i < 25; i++){
		es[i].clear();
	}
}
	return 0;
}



Measured memory_bytes: 3020
N = int(input())
t, a = map(int, input().split())
for _ in range(N-1):
    T, A = map(int, input().split())
    kt, ka = t//T, a//A
    if t % T != 0:  kt += 1
    if a % A != 0:  ka += 1
    k = max(kt, ka)
    t, a = k*T, k*A
print(t+a)

Measured memory_bytes: 3064