akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e5 + 5);
const ll MOD = (ll)(1e9 + 7);

string l;
ll dp[2][MAX_N];

ll ans;

int main(void) {
  // Here your code !
  cin >> l;

  dp[0][0] = 1LL;

  for (int i = 0; i < l.size(); ++i) {
    // a + b == 0
    {
      if (l[i] == '0') {
        dp[0][i + 1] += dp[0][i]; dp[0][i + 1] %= MOD;
        dp[1][i + 1] += dp[1][i]; dp[1][i + 1] %= MOD;
      }
      else {
        dp[1][i + 1] += (dp[0][i] + dp[1][i]); dp[1][i + 1] %= MOD;
      }
    }

    // a + b == 1
    {
      if (l[i] == '0') {
        dp[1][i + 1] += 2 * dp[1][i]; dp[1][i + 1] %= MOD;
      }
      else {
        dp[0][i + 1] += 2 * dp[0][i]; dp[0][i + 1] %= MOD;
        dp[1][i + 1] += 2 * dp[1][i]; dp[1][i + 1] %= MOD;
      }
    }
  }

  ans = dp[0][l.size()] + dp[1][l.size()];

  ans %= MOD;

  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
#define pii pair<ll,ll>
#define x1 dlfjl
#define x2 dkfj
#define MOD 1000000007
#define y1 dskgj
#define y2 dskfj
#define SQ 320
//#define N 1000005
typedef int ll;
using namespace std;
ll n,i,j,k,x,y,z,q,r,timer,mx,m;

ll a[100500], dp[100500];
map<ll,ll> f;
int main() {
    //freopen("input.txt","r",stdin);
    cin >> n;
    for (i = 0; i < n; i++)
    {
        scanf("%d",&x);
        f[x]++;
    }
    cin >> m;
    for (i = 0; i < m; i++)
    {
        scanf("%d",&x);
        f[x]--;
        if (f[x] < 0)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 9600
s = gets.chomp.split('')
s.each.with_index(1) do |d, i|
  if i.odd?
    unless ['R', 'U', 'D'].include?(d)
      puts 'No'
      exit
    end
  else
    unless ['L', 'U', 'D'].include?(d)
      puts 'No'
      exit
    end
  end
end
puts 'Yes'


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

#pragma region Macro
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v) sort(v.begin(), v.end())
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define vvi vector<vector<int>>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#pragma endregion

void solve(){
	#define int ll
	// ここに処理を記述
	// コンパイル時はエイリアス「gpp」--> c++17でコンパイル
	int N;
	cin >> N;
	if(N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8){
		cout << "pon" << endl;
	}
	else if(N % 10 == 3){
		cout << "bon" << endl;
	}
	else{
		cout << "hon" << endl;
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	
	solve();
	return 0;
}

Measured memory_bytes: 3652
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]            #  おいしさポイントの高い方からK個の寿司を選択
    pick_type = set([t for t, d in pick]) # 選択済の種類

    cnt = Counter()             #  各種類の寿司が何個ずつあるか覚えておく
    for t, d in pick:
        cnt[t] += 1

    rem = dict()                #  未選択の種類の寿司のうち、一番おいしさポイントが高い物
    for t, d in sushi:
        if t not in pick_type:
            rem[t] = max(rem.get(t, 0), d)
    res = sorted([[k, v] for k, v in rem.items()], key=lambda x: x[1]) # おいしさで昇順にソート(一番おいしい物が末尾)

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2] #  現在の選択でのスコア、ここから種類を1つずつ増加させていきスコアを計算する
    while len(pick_type) < K and pick and res:
        t, d = res.pop()
        pick_type.add(t)
        tt, dd = pick.pop()
        while cnt[tt] == 1 and pick:
            tt, dd = pick.pop()
        if cnt[tt] > 1:
            cnt[tt] -= 1
            manzoku = manzoku - dd + d
            ans.append(manzoku+ len(pick_type)**2)
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 85336
#include <stdio.h>

int main() {
	int i,j,k;
	int x, n, cnt;
	while (1) {
		scanf("%d %d", &n, &x);
		if (n == 0 && x == 0) {
			break;
		}
		cnt = 0;
		for (i = 1; i < n - 1; ++i) {
			for (j = i + 1; j < n;++j) {
				for (k = j + 1; k < n + 1 ;++k) {
//					printf("%d %d %d\n", i, j, k);
					if ((i + j + k) == x) {
						++cnt;
					}
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Measured memory_bytes: 600
import sys
input=sys.stdin.readline

def Eratosthenes():
    num=[True for i in range(100001)]
    num[0]=False
    num[1]=False
    for i in range(2,100001):
        if num[i]:
            for j in range(2*i,100001,i):
                num[j]=False
    return num

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    p_list=Eratosthenes()
    dp=[0 for _ in range(100001)]
    for i in range(3,100000):
        if p_list[i] and p_list[(i+1)//2]:
            dp[i+1]=dp[i]+1
        else:
            dp[i+1] = dp[i]
    for l,r in Queries:
        print(dp[r+1]-dp[l])


Measured memory_bytes: 64988
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
//  cout.precision(15); cout << fixed;

typedef pair<ll, ll> P;

int main() {
  // 1 2
  int n, l; cin >> n >> l;
  int total = 0;
  bool zero = l<=0 and l+n>0;
  for (int i=l; i<l+n; i++) {
    total += i;
  }
  
  if (zero) {
    cout << total << endl;
    return 0;
  }
  
  if (l<0) {
    cout << total - (l+n-1) << endl;
    return 0;
  }
  
  cout << total - l << endl;
  return 0;
}


Measured memory_bytes: 3592
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Yulian
 */

#include <iostream>
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <algorithm>
#include <map>


#include <iostream>

#include <fstream>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <algorithm>
#include <map>



int getTheAnswer() {
    return 42;
}

template< class InputIt>
void incAll(const InputIt &first, const InputIt &last){
  for(auto it = first; it != last; ++it){
    ++*it;
  }
}

template <class InputIt>
void printAll(const InputIt &first, const InputIt &last, std::ostream& out){
  for(InputIt it = first; it != last; ++it){
    out << *it << " ";
  }
}

// only for positive integers
int gcd(int a, int b){
  int tmp;
  if(a < b){
    tmp = a;
    a = b;
    b = tmp;
  }
  while(b != 0){
    tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

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


using namespace std;

class TaskD {
public:
  void solve(std::istream &in, std::ostream &out) {
    ios::sync_with_stdio(false);
    int n, tmp;
    in >> n;
    map<int, int> a;
    auto it = a.begin();
    for (int i = 0; i < n; ++i) {
      in >> tmp;
      it = a.find(tmp);
      if (it == a.end()) {
        // tmp has not been seen before
        a.insert({tmp, 1});
      } else {
        // tmp is a dup
        it->second++;
      }
    }
    int res = 0;
    // count number of even counts:
    for (auto it = a.begin(); it != a.end(); ++it) {
      res += (it->second + 1) % 2;
    }
    // if number of even numbers is even,  erverything will work out
    // otherwise 1 number must be deleted
    if(res % 2){
      res = a.size() - 1;
    }else{
      res = a.size();
    }

    out << res << endl;
  }
};


int main() {
	TaskD solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using ld = long double;

template <typename T>
int sz(T &x) {
  return (int)(x.size());
}

const int inf = 1'000'000'007;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());

  vector<int> has(n);
  for (int i = 0; i < n; ++i) {
    has[a[i]]++;
  }
  int ok = a[n - 1] == a[n - 2];
  ok &= a[0] >= (a[n - 1] + 1) / 2;

  for (int i = 0; i <= a[n - 1]; ++i) {
    int dist = max(i, a[n - 1] - i);
    ok &= has[dist] > 0;
    has[dist]--;
  }

  if (a[n - 1] % 2 == 0) {
    ok &= has[a[n - 1] / 2] == 0;
  } else {
    ok &= has[(a[n - 1] + 1) / 2] == 0;
  }

  if (ok) {
    cout << "Possible\n";
  } else {
    cout << "Impossible\n";
  }
}

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

  int t;
  t = 1;
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3636
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

using i64 = long long;

#define REP(i, n) for (int i = 0, i##_len = n; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)

const int is = 1 << 17;
char ib[is], *ip = ib + is, it;
inline char getc() {
	if (ip == ib + is) { fread_unlocked(ib, 1, is, stdin); ip = ib; }
	return *ip++;
}
inline i64 read() {
	i64 r = 0;
	if (ip + 16 > ib + is) while ((it = getc()) & 16) r = r * 10 + it - '0';
	else while ((it = *ip++) & 16) r = r * 10 + it - '0';
	return r;
}

const int os = 1 << 17;
char ob[os], *op = ob, ot;
inline void putc(const char c) {
	*op++ = c;
	if (op == ob + os) { fwrite_unlocked(ob, 1, os, stdout); op = ob; }
}
// x shoud be greater than or equal to zero
inline void write(i64 x) {
	char d[20];
	int i = 0;
	while (true) {
		d[i] = x % 10 + 48;
		x /= 10;
		++i;
		if (x <= 0) break;
	}
	while (i--) {
		putc(d[i]);
	}
}

signed main() {
  i64 N = read();
  i64 M = read();
  vector<i64> A(N);
  REP(i, N) A[i] = read();
  sort(A.begin(), A.end());
  vector<i64> S(N + 1);
  REP(i, N) S[i + 1] = S[i] + A[i];
  i64 h_ng = 0;
  i64 h_ok = A[N - 1] * 2 + 1;
  i64 h = h_ok;
  i64 ans = 0;
  while (h_ok > h_ng + 1) {
    h = h_ng + h_ok >> 1;
    i64 s = 0;
    i64 q = 0;
    i64 gt = 0;
    RREP(i, N) {
      while (gt < N && !(A[i] + A[gt] > h)) gt++;
      q += N - gt;
      s += S[N] - S[gt] + A[i] * (N - gt);
    }
    if (q <= M) {
      h_ok = h;
      ans = s + (M - q) * h;
    } else {
      h_ng = h;
    }
  }
  write(ans);
  fwrite_unlocked(ob, 1, op - ob, stdout);
}


Measured memory_bytes: 2048
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> { fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering { self.0.partial_cmp(&other.0).unwrap() }}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;


fn main() {
    input!{n:usize, a:[i64;3*n]};
    let mut a = a;
    a.sort();
    a.reverse();
    println!("{}", a.iter().enumerate().filter(|&(i,_x)| i%2!=0).map(|(_,x)| *x).collect::<Vec<i64>>()[0..n].iter().sum::<i64>());
}


Measured memory_bytes: 10492
def readinput():
    n,k=map(int,input().split())
    return n,k

def main(n,k):
    ans=k
    for i in range(1,n):
        ans=ans*(k-1)
        if ans >2**31-1:
            return 2**31-1
    return ans

if __name__=='__main__':
    n,k=readinput()
    ans=main(n,k)
    print(ans)


Measured memory_bytes: 9156
n = int(input())
a = [int(input()) for _ in range(n)]

sortA = sorted(a, reverse=True)
maxA = sortA[0]
semiMaxA = sortA[1]

for i in range(n):
  if a[i] == maxA:
    print(semiMaxA)
  else:
    print(maxA)

Measured memory_bytes: 14108
"use strict";

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance"); }

function _iterableToArrayLimit(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

!function () {
  function splitNum(line) {
    return (Array.isArray(line) ? line : line.split(/\s+/)).map(function (n) {
      return parseInt(n);
    });
  }

  function sortByKey(arr, keys) {
    if (!Array.isArray(keys)) keys = [keys];
    return arr.sort(function (a, b) {
      var _iteratorNormalCompletion = true;
      var _didIteratorError = false;
      var _iteratorError = undefined;

      try {
        for (var _iterator = keys[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
          var k = _step.value;

          if ("string" == typeof k) {
            var d = a[k] - b[k];
            if (0 !== d) return d;
          } else {
            var _d = a[k[0]] - b[k[0]];

            var sig = "desc" === k[1] ? -1 : "asc" === k[1] ? 1 : Number(k[1]);
            if (0 !== _d) return _d * sig;
          }
        }
      } catch (err) {
        _didIteratorError = true;
        _iteratorError = err;
      } finally {
        try {
          if (!_iteratorNormalCompletion && _iterator.return != null) {
            _iterator.return();
          }
        } finally {
          if (_didIteratorError) {
            throw _iteratorError;
          }
        }
      }

      return 0;
    });
  }

  !function (input) {
    var lines = input.split("\n");

    var _splitNum = splitNum(lines[0]),
        _splitNum2 = _slicedToArray(_splitNum, 2),
        N = _splitNum2[0],
        M = _splitNum2[1];

    var A = splitNum(lines[1]).slice(0, N);
    var bcs = lines.slice(2, M + 2).map(function (line) {
      var _splitNum3 = splitNum(line),
          _splitNum4 = _slicedToArray(_splitNum3, 2),
          B = _splitNum4[0],
          C = _splitNum4[1];

      return {
        B: B,
        C: C
      };
    });
    A.sort(function (a, b) {
      return a - b;
    });
    sortByKey(bcs, [["C", -1]]);
    var sum = 0;
    var index = 0,
        bci = 0;

    for (; index < N; index++) {
      var q = bcs[bci];
      if (null == q) break;
      if (!(q.B <= 0)) {
        if (A[index] < q.C) {
          sum += q.C;
          q.B--;
        } else break;
      } else {
        bci++;
        index--;
      }
    }

    for (; index < N; index++) {
      sum += A[index];
    }

    console.log(sum);
  }(require("fs").readFileSync("/dev/stdin", "utf8"));
}();


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

int prime[3520],s;
int flg[32770];

int isPrime(int x){
  int i;
  for(i=0;i<s && prime[i]<=sqrt(x);i++){
    if(x % prime[i] == 0) return 0;
  }
  return 1;
}

void mkPrime(void){
  int i;

  flg[0]=flg[1]=0;
  flg[2]=s=1;
  prime[0]=2;
  for(i=3;i<=32768;i++){
    if(isPrime(i)){
      prime[s++] = i;
      flg[i] = 1;
    }
    else{
      flg[i] = 0;
    }
  }
}

int main(void){
  int i,x,rst;

  mkPrime();
  while(1){
    scanf("%d",&x);
    if(!x) break;

    rst = 0;
    for(i=2;i<=x/2;i++){
      if(flg[i] && flg[x-i]) rst++;
    }
    printf("%d\n",rst);
  }

  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define f first
#define s second
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define fast 
#define f first
#define s second


int main(){
string s;
cin >> s;
if(s[3] == s[2] && s[4] == s[5])
cout << "Yes";
else
cout << "No";

}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int cat, unknown, number_x;
  scanf("%d %d %d", &cat, &unknown, &number_x);
  if(number_x - cat <= unknown && number_x - cat >= 0) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 128
N = int(input())
inputs = [list(map(int, input().split())) for _ in range(N)]

dicts = {}
for i in range(N):
    dicts[i] = sum(inputs[i])

ans = 0
count = 0
for key, value in sorted(dicts.items(), key=lambda x: -x[1]):
    if count % 2 == 0:
        ans += inputs[key][0]
    else:
        ans -= inputs[key][1]
    count += 1

print(ans)


Measured memory_bytes: 53240
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  int N, C; cin >> N >> C;
  int D[C][C]; rep(i, C) rep(j, C) cin >> D[i][j];
  vector<vector<int>> m(3, vector<int>(C, 0)); 
  rep(i, N) rep(j, N) {
    int c; cin >> c; c--;
    m[(i+j)%3][c]++;
  }

  ll result = LLINF;
  rep(c0, C) rep(c1, C) rep(c2, C) {
    if (c0==c1||c1==c2||c2==c0) continue;
    ll tmp = 0;
    rep(i, C) tmp += D[i][c0] * m[0][i];
    rep(i, C) tmp += D[i][c1] * m[1][i];
    rep(i, C) tmp += D[i][c2] * m[2][i];
    result = min(result, tmp);
  }

  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include <map>
#include <queue>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define R register
inline int read(){
	R int x; R char c; for (;(c=getchar())<'0'||c>'9';);
	for (x=c^'0'; (c=getchar())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));
	return x;
}
#define MN 1000005
#define pr std::pair<int,int>
#define mp(x,y) std::make_pair(x,y)
#define pb(x,y) push_back(mp(x,y))
#define fir first
#define sec second
struct Edge{
	Edge *nxt;int to;
	Edge(int v,Edge *nt){to=v;nxt=nt;}
}*hd[MN];
inline void ins(int u,int v){hd[u] = new Edge(v,hd[u]);}
inline void insw(int u,int v){ins(u,v); ins(v,u);}
int n,m,vn,endd,dis[MN];bool val[MN],vis[MN];
std::vector<pr> col[MN],num[MN];
std::priority_queue<pr,std::vector<pr>,std::greater<pr> > pq;
void dij(int u){
	dis[u]=0;pq.push(mp(0,u));
	while(!pq.empty()){
		u=pq.top().sec;pq.pop();
		if (vis[u]) continue;vis[u]=1;
		for (Edge *p=hd[u]; p!=NULL; p=p->nxt)
			if (!vis[p->to]&&dis[p->to]>dis[u]+val[p->to]){
				dis[p->to]=dis[u]+val[p->to];
				pq.push(mp(dis[p->to],p->to));
			}
	}
	dis[endd]==0x3f3f3f3f?dis[endd]=-1:0;
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	n=read(),m=read();
	for (R int i=1,x,y,c; i<=m; ++i){
		x=read(),y=read(),c=read();
		if (x>y) x^=y,y^=x,x^=y;
		col[x].pb(c,y);col[y].pb(c,x);
	}
	for (R int i=1,tmp; i<=n; ++i){
		std::sort(col[i].begin(),col[i].end());
		tmp=++vn;val[vn]=1;if (i==n) endd=tmp;
		for (R int j=0; j<col[i].size(); ++j){
			if (!j||col[i][j].fir!=col[i][j-1].fir)
				num[i].pb(col[i][j].fir,++vn),insw(vn,tmp);
			if (col[i][j].sec<i)
				insw(vn,std::lower_bound(num[col[i][j].sec].begin(),num[col[i][j].sec].end(),mp(col[i][j].fir,0))->sec);;
		}
	}dij(1);printf("%d\n",dis[endd]);
}

Measured memory_bytes: 107252
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

//区間A[a,b]と区間B[c,d]の関係
int intervalState(int a, int b, int c, int d){
	if(a < c && b < c) return 0;            //A < B
	else if(a > d && b > d) return 1;       //A > B
	else if(a <= c && d <= b) return 2;     //A -> B
	else if(c < a && b < d) return 3;       //B -> A
	else if(a <= c && b < d) return 4;      //A <= B
	else if(c < a && d <= b) return 5;      //A >= B
	return -1;
}

//Give input directly to vector<pair<int, int>> in
vector<pair<int, int>> JoinInterval(vector<pair<int,int>> in){
	vector<pair<int, int>> v;
	rep(i,in.size()) in[i].second *= -1;
	sort(all(in));
	rep(i,in.size()) in[i].second *= -1;

	rep(i,in.size()){
		if(v.empty()) v.emplace_back(in[i]);
		else{
			pair<int, int> &u = v.back();
			int tmp = intervalState(in[i].first,in[i].second,u.first,u.second);
			switch (tmp){
				case 0:
				case 1:
					v.emplace_back(in[i]);
					break;
				case 2:
					u.first = in[i].first;
					u.second = in[i].second;
					break;
				case 3:
					break;
				case 4:
				case 5:
					u.first = min(u.first, in[i].first);
					u.second = max(u.second, in[i].second);
					break;
				case -1:
					assert(0);
			}
		}
	}
	sort(all(v));
	return v;
}

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

	vector<pair<int, int>> tmp[30];
	rep(i,n){
		int s, t, C;
		cin >> s >> t >> C;
		C--;
		s*=2;
		s--;
		t*=2;
		tmp[C].emplace_back(s, t);
	}

	vector<pair<int, int>> v[30];
	rep(i,c){
		v[i] = JoinInterval(tmp[i]);
		//for(auto i : v[i]){ cout << i.first << ' ' << i.second << endl; }
	}

	vector<int> imos(200005,0);
	rep(i,c){
		for(auto j : v[i]){
			imos[j.first]++;
			imos[j.second + 1]--;
		}
	}
	rep(i,200001){
		imos[i + 1]+=imos[i];
	}
	cout << *max_element(all(imos)) << endl;
}


Measured memory_bytes: 3328
N = int(input())
S = input()

W_cnt_array = [0] * N
E_cnt_array = [0] * N

W_cnt = 0
E_cnt = 0
for i in range(N):
    if S[i] == 'W':
        W_cnt += 1
    elif S[i] == 'E':
        E_cnt += 1
    W_cnt_array[i] = W_cnt
    E_cnt_array[i] = E_cnt

prev_dir = S[0]
num = min(max(E_cnt_array), max(W_cnt_array))
for i in range(1, N):
    if prev_dir == 'E' and S[i] == 'W':
        num = min(num, W_cnt_array[i - 1] + E_cnt_array[-1] - E_cnt_array[i])
    prev_dir = S[i]
print(num)


Measured memory_bytes: 17568
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

lst = list(make_divisors(N))
#print(lst)
#print(len(lst))
cnt = 0
#print(lst)

lst2 = []

for i in lst:
    if len(set(prime_factorize(i))) == 1:
        lst2.append(i)
#print(lst2)

for i in range(len(lst2)):
    if N > 1:
        if N%lst2[i] == 0:
            N = N//lst2[i]
            cnt+=1
            #print(N)
            #print(lst2[i])
            #print(N)
#print()
print(cnt)

Measured memory_bytes: 9508
#include <iostream>
using namespace std;
int main(void){
    int n,ans=0,i,a;
    cin>>n;
    for(i=1;i<10;i++){
        if(n%i==0){
            a=n/i;
            if(a>=1 && a<=9)ans=1;
        }
    }
    if(ans==1)cout<<"Yes";
    else cout<<"No";
}


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

int main() {
  int n, min, max;
  long long sum = 0;
  cin >> n;
  int a[n];
  int i;
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  min = 1000000;
  max = -1000000;

  for (i = 0; i < n; i++) {
    if (min > a[i]) {
      min = a[i];
    }
    if (max < a[i]) {
      max = a[i];
    }
    sum += a[i];
  }

  cout << min << " " << max << " " << sum << endl;
  return 0;
}



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

// 入力
int n, W;
int w[100], v[100];

int dp[101][10001];


int rec_dp(int i, int j) {
  if (dp[i][j] != -1) {

    return dp[i][j];
  }

  int res;
  if (i == n) {
 
    res = 0;
  } else if (j < w[i]) {

    res = rec_dp(i + 1, j);
  } else {
   
    int r[3]={rec_dp(i + 1, j),
              rec_dp(i + 1, j - w[i]) + v[i],
	      rec_dp(i,j-w[i])+v[i]};
    sort(r,r+3);
    res=r[2];
    
  }

  return dp[i][j] = res;
}

int main() {
  memset(dp, -1, sizeof(dp)); // メモ化テーブルを-1で初期化　以下のforループと等価


  cin>>n>>W;
  for(int i=0;i<n;i++){
    cin>>v[i]>>w[i];
  }
  cout << rec_dp(0, W) << endl;
}

Measured memory_bytes: 5756
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string str;
int n,k,sz;
int main()
{
	cin >> n >> k;
	cin >> str;
	for(int i = 1;i < n;i ++)
		if(str[i] == str[i - 1])
			sz ++;
	cout << min(int(str.size() - 1),(sz + 2 * k)) << endl;
	return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    vector<pair<int, int>> v;
    for (int i = 1; i <= 150; ++i) {
        for (int j = i + 1; j <= 150; ++j) {
            assert(i < j);
            v.emplace_back(i, j);
        }
    }
    sort(begin(v), end(v),
         [](const pair<int, int>& a, const pair<int, int>& b) {
             int ah = a.first;
             int aw = a.second;
             int bh = b.first;
             int bw = b.second;
             auto aa = ah * ah + aw * aw;
             auto bb = bh * bh + bw * bw;
             if (aa < bb) {
                 return true;
             }
             else if (aa == bb) {
                 return ah < bh;
             }
             return false;
         });
    while (true) {
        int h, w;
        cin >> h >> w;
        if (h == 0 && w == 0) {
            return 0;
        }

        auto it = find(begin(v), end(v), make_pair(h, w));
        ++it;
        cout << it->first << ' ' << it->second << endl;
    }
}

Measured memory_bytes: 3228
#include<bits/stdc++.h>
#include<cstdlib>
#include<cmath>
using namespace std;
int main(){
 string S; string T; cin>>S>>T;
  int K=0;
  for(int i=0; i<S.size(); i++){
    if(S.at(i)!=T.at(i))
      K++;
    else continue;
  }
  cout<<K<<endl;
}

Measured memory_bytes: 3916
(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))
(defun f(n m plst)
  (let* ((wacounters (make-array n :initial-element 0))
         (collectp (make-array n :initial-element nil)))
    (labels ((rec(plst)
               (if (null plst)
                 wacounters
                 (let* ((index (1- (parse-integer (car (car plst)))))
                        (acwa (cadr (car plst))))
                   (if (string= acwa "AC")
                     (progn
                       (setf (aref collectp index) t)
                       (rec (cdr plst)))
                     (if (not (aref collectp index))
                       (progn
                         (incf (aref wacounters index))
                         (rec (cdr plst)))
                       (rec (cdr plst))))))))
      (rec plst)
      (let ((wan 0)
            (collectn 0))
        (dotimes (i n)
          (when (aref collectp i)
            (incf collectn)
            (setf wan (+ wan (aref wacounters i)))))
        (format t "~A ~A~%" collectn wan))
      ;(format t "~A ~A~%" (length (remove-if (lambda(a) (null a)) collectp)) (reduce #'+ wacounters))
      )))
(defun g()
  (let* ((line0 (mapcar #'parse-integer (splitat #\space (read-line nil nil))))
         (plst nil))
    (dotimes (i (cadr line0))
      (setf plst (cons (splitat #\space (read-line nil nil)) plst)))
    (f (car line0) (cadr line0) (nreverse plst))))
(g)


Measured memory_bytes: 69992
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);

constexpr int MAX = 100000;

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;
int indeg[MAX];
vector<int> stand;

void bfs(int s) {
	queue<int> q;
	q.push(s);
	V[s] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		out.emplace_back(u);
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			indeg[v]--;
			if (indeg[v] == 0 && !V[v]) {
				V[v] = true;
				q.push(v);
			}
		}
	}
}
void tsort() {
	for (int i = 0; i < N; i++) {
		indeg[i] = 0;
	}

	for (int u = 0; u < N; u++) {
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			indeg[v]++;
		}
	}

	for (int u = 0; u < N; u++) {
		if (indeg[u] == 0 && !V[u])bfs(u);
	}
	for (list<int>::iterator it = out.begin(); it != out.end(); it++) {
		stand.emplace_back(*it);
		cout << *it + 1 << endl;
	}
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		bool b = false;
		for (int j = 0; j < G[stand[i]].size(); j++) {
			if (G[stand[i]][j] == stand[i + 1])b = true;
		}
		if (!b) {
			ans = 1;
		}
	}
	cout << ans << endl;
}

int main() {
	int s, t, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		V[i] = false;
	}
	for (int i = 0; i < M; i++) {
		cin >> s >> t;
		s--, t--;
		G[s].emplace_back(t);
	}
	tsort();
}

Measured memory_bytes: 6184
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val h = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    var ans = true
    for (i in n-1 downTo 1) {
        if (h[i-1] <= h[i]) continue
        if (h[i-1] - 1 == h[i]) {
            h[i-1] -= 1
        } else {
            ans = false
        }
    }
    println (if (ans) "Yes" else "No")
}


Measured memory_bytes: 59780
import heapq
s = input()
k = int(input())

que = []
heapq.heapify(que)
subs = set([])
for char in range(97, 97+26):
    char = chr(char)
    for i, ss in enumerate(s):
        if ss == char:
            heapq.heappush(que, (ss, i))
    while len(que) > 0:
        sub, i = heapq.heappop(que)
        if not sub in subs:
            subs.add(sub)
            k -= 1
            # print(sub)
            if k == 0:
                print(sub)
                exit()
        
        i_end = i+len(sub)+1
        if i_end > len(s):
            continue
        else:
            heapq.heappush(que, (s[i:i+len(sub)+1], i))


Measured memory_bytes: 3828
#include <cstdio>
using namespace std;
const int mod = 1000000007;
int N,K,A[2000],cnt1,cnt2,ans;
int fpow(int b,int e) {
    if (e == 0) return 1;
    int tmp = fpow(b,e>>1); tmp = 1LL*tmp*tmp%mod;
    if (e&1) return 1LL*tmp*b%mod; else return tmp;
}
int main() {
    scanf("%d%d",&N,&K); for (int i = 0;i < N;i++) scanf("%d",&A[i]);
    for (int i = 0;i < N;i++) {
        cnt1 = cnt2 = 0;
        for (int j = 0;j < N;j++) if (A[j] > A[i]) cnt1++;
        for (int j = 0;j < i;j++) if (A[j] > A[i]) cnt2++;
        ans = (ans+((cnt2<<1)+(1LL*cnt1*(K-1))%mod)%mod*K%mod*fpow(2,mod-2)%mod)%mod;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 128
#include <algorithm>
#include <iomanip>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
// Powered by caide (code generator, tester, and library code inliner)
const int INF = 1e9 + 5;

class Solution {
public:
    void solve(std::istream& in, std::ostream& out) {
        int n;
        in >> n;
        vector<int> height(n);
        for (auto &x : height)
            in >> x;
    	
		
        vector<int> dp(n, INF);
        dp[0] = 0;
    	for(int i=0; i<n; i++) {
    		for(int j:{i+1, i+2}) {
    			if(j<n) {
                    dp[j] = min(dp[j], abs(height[i] - height[j]) + dp[i]);
    			}
    		}
    	}

        out << dp[n - 1] << endl;

    	//base case -- as per given problem
    	// if(n==2) {
     //        dp[1] = abs(height[1] - height[0]);
     //        out << dp[1] << std::endl;
     //        return;
    	// }
    	// //initializing dp[2] here
     //    dp[1] = abs(height[1] - height[0]);
    	// for(int i=2;i<n;i++) {
     //        dp[i] = min(abs(height[i - 1] - height[i])+ dp[i-1], abs(height[i - 2] - height[i]) +dp[i-2]);
    	// }
     //    out << dp[n - 1] << endl;
     //    
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}


#include <fstream>
#include <iostream>


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


    istream& in = cin;


    ostream& out = cout;

    solve(in, out);
    return 0;
}




Measured memory_bytes: 1024
#include<stdio.h>
int main(void)
{
	int a,b,c,x,y,z,t,h,m,s,i;
	for(i=0; i<3; i++)
	{
		scanf("%d %d %d %d %d %d", &a, &b, &c, &x, &y, &z);
		t=(x*3600+y*60+z)-(a*3600+b*60+c);
		h=t/3600;
		t-=h*3600;
		m=t/60;
		s=t%60;
		printf("%d %d %d\n", h, m, s);
	}
	
	return 0;
}


Measured memory_bytes: 2052
#include <bits/stdc++.h>
#include<string>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define vi vector<int>
#define pb push_back
#define ld long double
#define mp make_pair
#define pii pair<int,int>

int main() {
        fio;
        ll s;
        cin>>s;
        int max=1000000000;
        int x3=(max-s%max)%max;
        int y3=(s+x3)/max;
        cout<<0<<" "<<0<<" "<<max<<" "<<1<<" "<<x3<<" "<<y3<<endl;
        

 }



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

int main(){
	int n,v[112345];
	scanf("%d",&n);
	for(int i = 0;i < n;++i)
		scanf("%d",&v[i]);
	sort(v,v+n);
	int meio = n/2 -1;

	printf("%d\n",v[meio+1]-v[meio]);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, n;
  int ans = 0;
  
  cin >> n >> a >> b;
  
  for(int i = 1; i <= n; i++){
    int temp, sum = 0, num = i;
    while(num){
      temp = num % 10;
      sum = sum + temp;
      num = num / 10;
    }
    
    if(sum >= a && sum <= b)
      ans += i;
  }
  
  cout << ans << endl;
  
  return 0;
}

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

int main(){
	ll n; cin>>n;
	ll x[n]={};
	rep(i,n) cin>>x[i];
	ll ans=(1<<30),k=0;
	for(int p=0; p<=101; p++){
		ll k=0;
		for(int i=0; i<n; i++){
			k+=(x[i]-p)*(x[i]-p);
		}
		ans=min(k,ans);
	}
	cout<<ans<<endl;
}
		
	

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

using namespace std;

int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(20);

    int n;
    cin >> n;
    string s = to_string(n);

    int sum = 0;
    for(int i = 0; i < s.size(); i++)
        sum += s[i]-'0';
    
    if(n%sum==0) cout << "Yes\n";
    else cout << "No\n";

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string S; cin>>S;
    if(S=="ABC") cout<<"ARC";
    else cout<<"ABC";
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];



void solve() {
  int x,y;
  cin >> x >> y;
  cout << max({x+y, x-y, x*y})<< endl;

}


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

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <functional>
#include <tuple>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {}
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {}
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

template <class T>
inline T scan() {
  T res;
  std::cin >> res;
  return res;
}

using lint = long long;
constexpr int inf = (1 << 30) - 1;
constexpr lint linf = (1ll << 60) - 1;

int N;
int A[5000], cnt[5000];
std::vector<int> graph[5000];
lint dp[5000][5000][2];

void dfs(int v, int p) {
  cnt[v] = 1;
  chmin(dp[v][0][0], A[v]);
  if (A[v] > 0) {
    chmin(dp[v][0][1], A[v]);
  }
  for (int x: graph[v]) {
    if (x == p) {
      continue;
    }
    dfs(x, v);
    for (int i: revrange(0, cnt[v])) {
      lint a = dp[v][i][0], b = dp[v][i][1];
      dp[v][i][0] = dp[v][i][1] = linf;
      for (int j: range(0, cnt[x])) {
        chmin(dp[v][i + j][0], a + dp[x][j][0]);
        chmin(dp[v][i + j][0], a + dp[x][j][1]);
        chmin(dp[v][i + j][1], b + dp[x][j][1]);
        if (dp[x][j][1] < linf) {
          chmin(dp[v][i + j + 1][0], a);
          chmin(dp[v][i + j + 1][1], b);
        }
        if (dp[x][j][0] < 0) {
          chmin(dp[v][i + j + 1][0], a);
          chmin(dp[v][i + j + 1][1], b);
        }
      }
    }
    cnt[v] += cnt[x];
  }
}

int main() {
  std::cin >> N;
  for (int i: range(0, N)) {
    std::cin >> A[i];
  }
  for (int i: range(0, N - 1)) {
    int u, v;
    std::cin >> u >> v;
    --u; --v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  for (int i: range(0, N)) {
    for (int j: range(0, N)) {
      dp[i][j][0] = dp[i][j][1] = linf;
    }
  }
  dfs(0, -1);
  int ans = inf;
  for (int j: range(0, N)) {
    if (dp[0][j][0] < 0) {
      chmin(ans, j);
    }
    if (dp[0][j][1] < linf) {
      chmin(ans, j);
    }
  }
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 391680
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  ll l, r;
  cin >> l >> r;
  ll ans = 2e10;
  for(ll i = l; i <= r; i++){
    for(ll j = i+1; j <= r; j++){
      ans = min(ans, (i*j)%2019);
      if(ans == 0){
        cout << 0 << endl;
        return 0;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

void solve() {
  int a, b, c, d;
  scan(a, b, c, d);
  while (true) {
    c -= b;
    if (c <= 0) {
      print("Yes");
      return;
    }
    a -= d;
    if (a <= 0) {
      print("No");
      return;
    }
  }
}

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


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

int main()
{
	int R;
	cin >> R;
	if (R < 1200)
	{
		cout << "ABC" << endl;
	}
	else if (R < 2800)
	{
		cout << "ARC" << endl;
	}
	else
	{
		cout << "AGC" << endl;
	}
	return 0;
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,m,a;

  while(true){
    cin >> n >> m >> a;
    if(n == 0 && m == 0 && a == 0) break;
    vector<map<int,int>> line(1001);
    rep(i,m){
      int h,p,q;
      cin >> h >> p >> q;
      line[h][p] = q;
      line[h][q] = p;
    }
    int c = a;
    for(int i = 1000; i >= 0; i--){
      //if(i < 5) cout << i << '*' << c << endl;;
      if(line[i][c] != 0){
        c = line[i][c];
      }
    }
    cout << c << endl;
  }
  return 0;
}



Measured memory_bytes: 3224
import java.util.*;
import java.math.BigDecimal;

public class Main {
	public static void main(String[] args) {  
  		Scanner sc = new Scanner(System.in);
      	int D = sc.nextInt();
      	
      	switch(D) {
          case 25:
            System.out.println("Christmas");
            break;
          case 24:
            System.out.println("Christmas Eve");
            break;
          case 23:
            System.out.println("Christmas Eve Eve");
            break;
          case 22:
            System.out.println("Christmas Eve Eve Eve");
            break;
        }
    }
}

Measured memory_bytes: 21716
# -*- coding: utf-8 -*-
list_n = [True for i in range(123456*2+1)]
list_n[0] = False
list_n[1] = False
ans = []
count = 0
for i, n in enumerate(list_n):
    if n:
        prime = i
        count += 1
        k = prime * 2
        l = 3
        while k < 123456*2+1:

            list_n[k] = False
            k = prime * l
            l += 1
    ans.append(count)
a = 1

while True:
    try:
        N = int(input())
        if N == 0:
            break
        count = ans[2*N] - ans[N]
        print(count)
    except:
        break




Measured memory_bytes: 10048
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
if n % 10 == 3:
    print("bon")
elif n % 10 in (0,1,6,8):
    print("pon")
else:
    print("hon")


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

int main(void){
	int n, p=0, q=0, r=0;
	cin >> n;
	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		if(a%4==0) p++;
		else if(a%2==0) q++;
		else r++;
	}
	if(q==0 && p>=r-1 || q!= 0&& p>=r) cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

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

Measured memory_bytes: 256