akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#include<queue>
#include<stack>
#include<cctype>
#include<deque>
#include<time.h>
#include<bitset>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
#include<random>
#include<numeric>
//by Skeef79

typedef long long ll;
typedef long double ld;

typedef unsigned long long ull;

#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:16777216")
#define pb push_back
#define en '\n'
#define for0(i,n) for(int i = 0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pii pair<int,int>
#define pll pair<ll,ll>
#define what_is(x) cout<<#x<<" is "<<x<<en;

using namespace std;

const int INF = 2000000000;
const ll LINF = 2000000000000000000;

template<typename T> void print(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}

template<typename T> void print(deque<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}

template<typename T> void print(vector<vector<T>>& a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}

template <typename T> void input(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cin >> a[i];
}

template<typename T> void input(deque<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cin >> a[i];
}

template<typename T> void input(vector<vector<T>>& a)
{
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < a[i].size(); j++)
			cin >> a[i][j];

}

void solve()
{
	ll n;
	cin >> n;
	ll sum = 0;
	map<ll, ll>mp;
	for (int i = 0; i < n; i++)
	{
		ll x;
		cin >> x;
		mp[x]++;
		sum += x;
	
	}
	int m;
	cin >> m;
	while (m--)
	{
		ll b, c;
		cin >> b >> c;
		ll cnt = mp[b];
		cout << sum - cnt * b + cnt * c << en;
		sum -= cnt * b;
		sum += cnt * c;
		mp[b] = 0;
		mp[c] += cnt;
	}
}

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

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	//freopen("luigi.in", "r", stdin);
	//freopen("luigi.out", "w", stdout);

	int tst = 1;
	//cin >> tst;

	while (tst--)
		solve();
}


Measured memory_bytes: 9552
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,fix[20050],ans;
vector<ll>v[205],g[2005];
void solve(ll x){
    for(int i=1; i<=n; i++){
        g[i].clear();
        fix[i] = 0;
    }
    fix[x] = 1;
    g[1].pb(x);
    ll las = -1;
    for(int i=1; i<=n; i++){
        if((int)g[i].size() == 0)break;
        las = i;
        for(int j=0; j<g[i].size(); j++){
            ll to = g[i][j];
            for(int l=0; l<v[to].size(); l++){
                if(!fix[v[to][l]]){
                    fix[v[to][l]] = i + 1;
                    g[i + 1].pb(v[to][l]);
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<v[i].size(); j++){
            if(abs(fix[i] - fix[v[i][j]]) != 1)return;
        }
    }
    ans = max(ans , las);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        for(int j=0; j<s.size(); j++)
            if(s[j] == '1')
                v[i].pb(j + 1);
    }
    ans = -1;
    for(int i=1; i<=n; i++){
        solve(i);
    }
    
    
    cout << ans << endl;
    
    return 0;
}


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

using namespace std;

void rwFile() {
    freopen("INP.inp", "r", stdin);
    freopen("OUT.out", "w", stdout);
}

void solve() {
    int n; cin >> n;
    int arr[3][n];
    cin >> arr[0][0] >> arr[1][0] >> arr[2][0];
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;
        arr[0][i] = max(arr[1][i - 1], arr[2][i - 1]) + a;
        arr[1][i] = max(arr[0][i - 1], arr[2][i - 1]) + b;
        arr[2][i] = max(arr[0][i - 1], arr[1][i - 1]) + c;
    }
    int res = max(arr[0][n - 1], arr[1][n - 1]);
    res = max(res, arr[2][n - 1]);
    cout << res;
}

int main()
{
    //rwFile();
    solve();
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

int main()
{
	int i, j, k, l;
	int a, b;
	cin >> a >> b;
	if (b%a == 0)
	{
		cout << a + b;
	}
	else
	{
		cout << b-a;
	}

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

const int MAX_N = 1e2 + 10;
int64_t N;
int64_t x[MAX_N], y[MAX_N], h[MAX_N];

int64_t check(int cx, int cy) {
    int64_t H = 0;
    for (int i = 1; i <= N; i++) {
        if (0 < h[i]) {
            H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
            break;
        }
    }
    //if (H == 0) { return H; }

    for (int i = 1; i <= N; i++) {
        int64_t tmp = std::max((int64_t)0, H - abs(x[i] - cx) - abs(y[i] - cy));
        if (tmp != h[i]) {
            return -1;
        }
    }
    return H;
}

int main(int argc, char **argv) {
    std::cin >> N;
    
    for (int i = 1; i <= N; i++) {
        std::cin >> x[i] >> y[i] >> h[i];
    }

    for (int cx = 0; cx <= 100; cx++) {
        for (int cy = 0; cy <= 100; cy++) {
            int64_t H = check(cx, cy);
            if (H != -1) {
                std::cout << cx << " " << cy << " " << H << std::endl;
            }
        }
    }

    return 0;

}


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

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

int main(){
  string s;
  int q;
  const int max_q = 2*1e5;
  vector<int> t(max_q+1, 0);
  vector<int> f(max_q+1);
  vector<string> c(max_q+1);
  

  cin >> s >> q;
  for(int i = 0; i < q; i++) {
    cin >> t[i];
    if(t[i] == 2) cin >> f[i] >> c[i];
  }

  bool flag = 0;
  int count = 0;
  for(int i = 0; i < q; i++){
    if(t[i] == 1){
      // reverse(s.begin(), s.end());
      flag = 1 - flag;
      count ++;
    }
    if(t[i] == 2 && f[i] == 1){
      if(flag == 0) s.insert(0, c[i]);
      else s.insert(s.size(), c[i]);
    }
    if(t[i] == 2 && f[i] == 2){
      if(flag == 0) s.insert(s.size(), c[i]);
      else s.insert(0, c[i]);
    }
  }
  if(count%2 == 1) reverse(s.begin(), s.end());
  cout << s << endl;

  return 0;
}

Measured memory_bytes: 13440
MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)


Measured memory_bytes: 170800
from math import sqrt
n,d=map(int,input().split())
X=[[int(i)for i in input().split()]for _ in range(n)]
c=0
for i in range(n-1):
    for j in range(i+1,n):
        a=0
        for k in range(d):
            a+=(X[i][k]-X[j][k])**2
        if sqrt(a)==int(sqrt(a)):
            c+=1
print(c)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

int main()
{
    string hoge;
    cin>>hoge;
    int a[4];
    rep(i, 4)
    {
        a[i]=(int)(hoge[i]-'0');
    }
    rep(i, 2 * 2 * 2)
    {
        int temp = a[0];
        rep(j, 3)
        {
            if (((i & (1 << j)) > 0))
            {
                temp += a[j + 1];
            }
            else
            {
                temp -= a[j + 1];
            }
        }
        if (temp == 7)
        {
            cout << a[0];
            rep(j, 3)
            {
                if (((i & (1 << j)) > 0))
                {
                    cout << '+';
                }
                else
                {
                    cout << '-';
                }
                cout << a[j + 1];
            }
            cout << "=7" << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void)
{
	int i,j,k,l,m,o,x;
	int c = 0;
	cin>>l>>m>>o>>x;
	for(i=0;i<l+1;i++)
	{
		for(j=0;j<m+1;j++)
		{
			for(k=0;k<o+1;k++)
			{
				if(500*i+100*j+50*k==x)
				c++;
			}
		}
				
    }
	 
	 cout<<c;
	
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define mod 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=550;
//↑templete
int main() {
	int N;
	cin>>N;
	int A[SIZE]={};
	vint B;
	for(int i=0;i<N-1;i++){
		int b;
		cin>>b;
		B.pb(b);
	}
	A[0]=B[0];

	ll ans=0;
	for(int i=1;i<N;i++){
		if(i==N-1){
			A[i]=B[i-1]-A[i];
			continue;
		}
		A[i]=min(B[i-1]-A[i],B[i]);
	}
	for(int i=0;i<N;i++)
		ans+=A[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 40) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.length();
    vector<string> ss;
    string t = "";
    for(int i = 0; i < n; i++) {
        bool f = false;
        if(s[i] == 'A') {
            t.push_back('0');
        } else if(s[i] == 'B') {
            if(i < n - 1 && s[i + 1] == 'C') {
                t.push_back('1');
                i++;
            } else {
                f = true;
            }
        } else {
            f = true;
        }
        if(f) {
            if(t != "") {
                ss.push_back(t);
            }
            t = "";
        }
    }
    if(t != "") {
        ss.push_back(t);
    }
    ll ans = 0;
    for(int i = 0; i < ss.size(); i++) {
        ll c = 0;
        for(int j = 0; j < ss[i].size(); j++) {
            if(ss[i][j] == '0') {
                c++;
            } else {
                ans += c;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3216
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
  int l, r;
  bool operator < (const node &a) const {
    return r == a.r? l > a.l :r < a.r;
  }
}a[120000];
bool bkt[120000];
int main() {
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= m; i ++ ) {
    cin >> a[i].l >> a[i].r;
  }
  sort(a+1, a+m+1);
  int now = 0;
  int maxn = 0;
  for(int i = 1; i <= m; i ++ ) {
    // cout<<a[i].l<<" "<<a[i].r<<endl;
    // cout<<maxn<<" "<<now<<endl;
    if(maxn > a[i].l) continue;
    else maxn = a[i].r, now ++;
  }
  printf("%d\n", now);
}


Measured memory_bytes: 1024
'use strict'

function Main(input) {
    const tmp = input.trim().split('\n')[0].split(' ');
    const K = Number(tmp[0]);
    const S = Number(tmp[1]);
    // console.log(K, S);

    let result = 0;
    for (let x = 0; x <= K; x++) {
        for (let y = 0; y <= K; y++) {
            const z = S - x - y;
            if (z >= 0 && z <= K) {
                result++;
            }
        }
    }
    console.log(result);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

using namespace std;

const int MAXN = 1e5;

int v[MAXN + 1];

int main() {
    //ifstream cin(".in");
    //ofstream cout(".out");
    int n, pos = 0, l;
    cin >> n >> l;
    for (int i = 1; i <= n; ++i) {
      cin >> v[i];
      if (i > 1 && v[i] + v[i - 1] >= l)
        pos = i - 1;
    }
    if (pos) {
        cout << "Possible\n";
      for (int i = 1; i < pos; ++i)
        cout << i << "\n";
      for (int i = n - 1; i > pos; --i)
        cout << i << "\n";
      cout << pos;
    } else
      cout << "Impossible";
    return 0;
}


Measured memory_bytes: 1152
#include<stdio.h>

int main(){
 
  int n;
  int m;
  int a;
  int sum=0;
  
  scanf("%d %d",&n,&m);
  
  for(int i=0;i<m;i++){
    scanf("%d",&a);
    sum+=a;
  }
  
  if(sum<=n){
    printf("%d",n-sum);
  } else printf("-1");
  
  return 0;
}

Measured memory_bytes: 1728
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }

        long[] dp = new long[n * n];
        for (int i=0; i<n; i++) {
            dp[i * n + i] = a[i]; 
        }
        calculate(dp, a, n);
        System.out.println(dp[n - 1]);

    }
    private static void calculate(long[] dp, long[] a, int n) {
        for (int i = n - 2; i > -1; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i * n + j] = Math.max(a[i] - dp[(i + 1) * n + j], a[j] - dp[i * n + (j - 1)]);
            }
        }

    }
}

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

int main()
{
  int n,i,x;

  i = 1;
  cin >> n;

  while (++i <= n)
  {
      x = i;
    if(x % 3 == 0)
    {
      cout << " " << i;
      continue;
    }

    while(x)
    {
      if(x % 10 == 3)
      {
	      cout << " " << i;
	      break;
      }
      x /= 10;
    }
  }

  cout << endl;
  return 0;

}



Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main() {
  string s;
  cin >> s;

  regex re("(dream|dreamer|erase|eraser)+");

  if (regex_match(s, re))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 39808
a, b = map(int, input().split())
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

i = 1
j = 1
table_a = []
while i * i <= a:
    if a%i == 0:
        table_a.append(i)
        table_a.append(a//i)
    i += 1
table_a = list(set(table_a))

table_b = []
while j * j <= b:
    if b%j == 0:
        table_b.append(j)
        table_b.append(b//j)
    j += 1
table_b = list(set(table_b))

table = set(table_a) & set(table_b)
nums = list(table)

cnt = 0
for i in range(len(nums)):
    if is_prime(nums[i]):
        cnt += 1
print(cnt+1)

Measured memory_bytes: 5192
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll N;
  string S;
  cin >> N >> S;

  if(N%2>0){
    cout << "No" << "\n";
    return 0;
  }
  
  bool ans = true;
  REP3(i,N/2,N){
    if (S[i] != S[i-S.length()/2]){
      ans = false;
      break;
    }
  }
  cout << ((ans) ? "Yes" : "No") << "\n";
  return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  int N, M; cin >> N >> M;
  vector<int> X(M);
  rep(i, M) {
    cin >> X[i];
  }
  if (N >= M) {
    cout << 0 << endl;
    return 0;
  }
  sort(X.begin(), X.end());
  vector<int> dists;
  rep(i, M - 1) {
    dists.push_back(X[i + 1] - X[i]);
  }
  sort(dists.begin(), dists.end());
  ll unvisited_dist = 0;
  REP(i, dists.size() - N + 1, dists.size()) {
    unvisited_dist += dists[i];
  }
  cout << X[M - 1] - X[0] - unvisited_dist << endl;
}


Measured memory_bytes: 1276
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,a,b) for(ll i=(a)-1;i>=(b);i--)

int main() {
    ll N;
    cin >> N;
    vector<ll> Ais(N);
    rep(i,0,N) {
        cin >> Ais[i];
    }
    bool found_one = false;
    rep(i,0,N) {
        if (Ais[i] == 1) {
            found_one = true;
        }
    }
    if (!found_one) {
        cout << -1 << endl;
        return 0;
    }
//    ll conti_cnt = 1;
//    rep(i,1,N) {
//        if (Ais[N-1-i] == Ais[N-1] - i) {
//            conti_cnt++;
//        }
//    }
    ll broken = 0;
    ll expect = 1;
    rep(i,0,N) {
        if (Ais[i] == expect) {
            expect++;
        } else {
            broken++;
        }
    }
    cout << broken << endl;
}



Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 2e5 + 7;

int a[N], p[N];
map <int, int> c, cp;

void solve() {
    int n, k;
    cin >> n >> k;
    loop1(i, n) {
        cin >> a[i];
        p[i] = (p[i - 1] + a[i]) % k;
    }
    int ans = 0;
    loop(i, n + 1) {
        ans += c[p[i] - i] + cp[p[i] - i];
        ++c[p[i] - i]; ++cp[p[i] - i - k];
        if (i >= k - 1) {
            int pos = p[i - (k - 1)] - (i - (k - 1));
            --c[pos]; --cp[pos - k];
        }
    }
    cout << ans;

}

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


Measured memory_bytes: 44140
MOD = 10**9 + 7
h, w = [int(item) for item in input().split()]
field = []
for i in range(h):
    field.append(input().rstrip() + "#")
field.append("#" * (w+1))
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1

for i in range(h):
    for j in range(w):
        if field[i][j+1] == ".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= MOD
        if field[i+1][j] == ".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
print(dp[-1][-1])

Measured memory_bytes: 44616
// Problem : B - An Odd Problem
// Contest : AtCoder - AIsing Programming Contest 2020
// URL : https://atcoder.jp/contests/aising2020/tasks/aising2020_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)


#include<bits/stdc++.h>
using namespace std;
#define int         long long int
#define vi           vector<int>
#define pii          pair<int,int>
#define vpp          vector<pii>
#define mii          map<int,int>
#define pb           push_back
#define rep(i,a,bb)  for(int i=a;i<bb;i++)
#define ff           first
#define ss           second
#define fast         ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test         int T;cin>>T;while(T--)
#define __sort(v)    sort(v.begin(),v.end())
#define __rsort(v)   sort(v.rbegin(),v.rend())
#define setbits(x)   __builtin_popcount(x)
#define zrobits(x)   __builtin_ctzint(x)
#define endl '\n'
#define debug(x)  cerr<<"[ "<<#x<<" : "<<x<<" ]"<<endl
#define debugp(x) cerr<<"[ "<<#x<<".ff : "<<x.first<<", "<<#x<<".ss : "<<x.second<<" ]"<<endl
#define debugs(x) cerr<<"[ "; for(auto i:x) cerr<<i<<" "; cerr<<" ]"<<endl;
#define debugm(x) cerr<<"----------"<<endl; for(auto i:x) cerr<<i.ff<<":"<<i.ss<<endl; cerr<<"----------"; 
#define PI 3.14159265359
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dxk[]={0,0,1,-1,1,1,-1,-1};
int dyk[]={1,-1,0,0,1,-1,1,-1};
const int inf = 1e+18;
const int mod = 1e+9 + 7;

void solve()
{
	int n;
	cin>>n;
	int ans = 0;
	rep(i, 1, n+1){
		int x;
		cin>>x;
		if(x%2&&i%2)
		 ++ans;
	}
	cout<<ans;
}

int32_t main()
{
  fast;
  //test
  solve();
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include<vector>
#define Inf 1000000007
using namespace std;
int  fun(vector<vector<int>>&v,int dp[100000][3],int n)
{

    for(int k=0;k<3;k++)
    dp[0][k]=v[0][k];
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {    
            for(int k=0;k<3;k++)
            {
                if(j==k)
                continue;
                dp[i][j]=max(dp[i][j],dp[i-1][k]+v[i][j]);
            }
        }
    }
    return max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}
 
int main()
{
    int n;
    cin>>n;
    vector<vector<int>>v;
    v.resize(n);
    for(int i=0;i<n;i++)
    v[i].resize(3);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>v[i][j];
        }
    }
    int dp[100000][3];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            dp[i][j]=0;
        }
    }
    cout<<fun(v,dp,n)<<endl;
    return 0;
}

Measured memory_bytes: 9852
// ABC096C - Half and Half

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

int main() {
	long long int A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;

	long long int minT = X * A + Y * B;
//	cout << minT << endl;

	for (long long int i = 0; i <= max(X, Y); i++) {
//		if (2 * i * C + max(X - i, (long long)0) * A + max(Y - i, (long long)0) * B < minT) {
//			cout << 2 * i * C + max(X - i, (long long)0) * A + max(Y - i, (long long)0) * B << endl;
//		}
		minT = min(minT, 2 * i * C + max(X - i, (long long)0) * A + max(Y - i, (long long)0) * B);
	}

	cout << minT << endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll unsigned long long
using namespace std;
ll N,Cnt[2],P,x,Ans,t,C[105][105];
int main()
{
	ll i,j,t=0;
	
	scanf("%lld%lld",&N,&P);
	for(i=1;i<=N;i++)scanf("%lld",&x),Cnt[x&1]++;
	
	Ans=1LL<<Cnt[0];
	
	for(i=0;i<=Cnt[1];i++)C[i][0]=1;
	for(i=1;i<=Cnt[1];i++)
	for(j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
	
	if(P&1)
	{
		for(i=1;i<=Cnt[1];i+=2)
		t+=C[Cnt[1]][i];
	}
	else
	{
		for(i=0;i<=Cnt[1];i+=2)
		t+=C[Cnt[1]][i];
	}
	
	printf("%lld",Ans*t);
}

Measured memory_bytes: 256
/*___________Bismillahir Rahmanir Rahim__________*/
//Think positive, be positive and never use negative words
#include<bits/stdc++.h>
#define ll               long long int
#define uni(a)           a.erase(unique(a.begin(),a.end()),a.end())
#define vsum(a)          accumulate(a.begin(),a.end(),0)
#define vmax(a)          *max_element(a.begin(),a.end())
#define vmin(a)          *min_element(a.begin(),a.end())
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define yes              cout<<"YES"<<endl
#define no               cout<<"NO"<<endl
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n;
    cin>>n;
    if(n>29) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
/*_________________Alhamdulillah_________________*/

Measured memory_bytes: 3632
global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E48)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
   

Measured memory_bytes: 11636
using System;
using static System.Console;
using static System.Math;

public class Hello{
    public static void Main(){
        string[] input = ReadLine().Split(' ');
        int kazu = int.Parse(input[0]);
        int min = int.Parse(input[1]);
        int max = int.Parse(input[2]);
        int count = 0;
        
        for(int i=1;i<=kazu;i++){
            int check = 0;
            int suuji = i;
            for(int j=0;j<5;j++){
                check += suuji%10;
                suuji /= 10;
                if(suuji == 0){
                    break;
                }
            }
            if(min <= check && check <= max){
                count += i;
            }
        }
        WriteLine(count);
    }
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++) cin >> a[i];

    bool f = true;
    int cnt = 0;
    while(f)
    {
        f = false;
        for(int i = n - 1;i > 0;i--){
            if(a[i - 1] > a[i]){
                cnt++;
                int t = a[i];
                a[i] = a[i - 1];
                a[i - 1] = t;
                f = true; 
            }
        }
    }

    for(int i = 0;i < n - 1;i++){
        cout << a[i] << " ";
    }
    cout << a[n - 1] << endl;
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3124
package main 
import "fmt"

func main() {
  var s string
  fmt.Scan(&s)
  if (s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]){
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}


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


vector<int> a(12);
vector<vector<long long>> Q(51, vector<long long>(4));
int n, m, q;
long long ans = 0;
void dfs (int v, int start) {
    if (v > n) {
        long long total = 0;
        for (int i = 0; i < q; i++) {
            int fi = Q[i][0];
            int si = Q[i][1];
            if (a[si] - a[fi] == Q[i][2]) {
                total += Q[i][3];
            }
        }
        ans = max (ans, total);
        return;
    }
    for (int i = start; i <= m; i++) {
        a[v] = i;
        dfs (v + 1, i);
    }
}
void solve () {
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < 4; j++) {
            long long x; cin >> x;
            Q[i][j] = x;
        }
    }
    dfs(1,1);
    cout << ans;
}

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


Measured memory_bytes: 3644
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>

using namespace std;

#define ll long long

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

	long dd[9];
	dd[0] = 1;
	dd[1] = 1;
	for (int i = 2; i <= n; i++)
		dd[i] = dd[i - 1] * i;
	bool use[8];
	for (int i = 0; i < n; i++)
		use[i] = false;
	//	p
	for (int i = 0; i < n; i++)
	{
		int num = 0;
		for (int j = 0; j < p[i] - 1; j++)
			if (!use[j])
				num++;
		a += dd[n - i - 1] * num;
		use[p[i] - 1] = true;
	}
	for (int i = 0; i < n; i++)
		use[i] = false;
	for (int i = 0; i < n; i++)
	{
		int num = 0;
		for (int j = 0; j < q[i] - 1; j++)
			if (!use[j])
				num++;
		b += dd[n - i - 1] * num;
		use[q[i] - 1] = true;
	}

	a -= b;
	if (a < 0)
		a *= -1;

	printf("%ld", a);
	return 0;
}


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

struct P
{
    int x,y;

    bool operator<(const P &a)const{

        if(y!=a.y) return y>a.y;
        return x>a.x;
    }

};

vector<int> v;

//bitset<4001000> b;
int i,n,d,m,k,a,b,c;

long long o[211111][3][3];
long long l[211111];
long long j[211111];
int e;

//int dx[10]={2,2,-2,-2,1,1,-1,-1},dy[10]={1,-1,1,-1,2,-2,2,-2};

int dx[10]={0,1,0,-1,1,1,-1,-1},dy[10]={1,0,-1,0,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};
long long mod=1000000009,mod2=1000000009,mod3=2017;
long long x,z,y;
double pi=3.14159265;
P u[1];
//stack<int> s;
//set<int> se;
//priority_queue<int> q;
//queue<int> q;
string r,r1;
//char r[1];
//2147483647
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p;
/*
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<long long, int, custom_hash> safe_map;
*/
//list<int> l;


//deque<int> de;
//srand((int)time(NULL));




bool as(P a,P b)
{
    return a.x<b.x;
}

long long f(int n,int c,int d)
{
    if(d>=3) return 98765421987654321;
    if(n==a)
    {
        if((l[n]+c)%2+d>2) return 987654321987654321;
        return 0;
    }
    if(o[n][c][d]>=0) return o[n][c][d];
    int p;
    long long x=987654321987654321;
    if(n==0) p=0;
    else p=(c+l[n])%2;
    if(l[n+1]==0)
    {
        x=j[a]-j[n];
        for(int h=1;h<=2;h++)
            x=min(x,f(n+1,h,d+(p+h+l[n+1])%2)+h);
    }
    else
    {
        x=j[a]-j[n];
        for(int h=0;h<2;h++)
            x=min(x,f(n+1,h,d+(p+h+l[n+1])%2)+h);
    }
    return o[n][c][d]=x;
}

int main()
{
    memset(o,-1,sizeof(o));
    scanf("%d",&a);
    for(int t=1;t<=a;j[t]=l[t]+j[t-1],t++)
        scanf("%lld",&l[t]);
    j[a+1]=j[a];
    x=987654321987654321;
    for(int t=0;t<=a;t++)
    {
        if(t==0||l[t]%2==0)
        x=min(x,f(t,0,0)+j[t]);
        else x=min(x,f(t,1,0)+j[t]);
        //printf("%lld  %lld\n",x,j[t]);
    }
    printf("%lld",x);
}


Measured memory_bytes: 37120
n, m = map(int, input().split())
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab, key = lambda x:x[0])
ans = 0
nokori = m
i = 0
while nokori > 0:
    ans += ab[i][0] * min(ab[i][1], nokori)
    nokori -= ab[i][1]
    i += 1
print(ans)

Measured memory_bytes: 18932
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
typedef long double ld;
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; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int main(){
  int W,H,N;  cin>>W>>H>>N;
  bool d[W+1][H+1];
  memset(d, 1, sizeof(d));
  rep(st,0,N){
    int x,y,z;  cin>>x>>y>>z;
    --x;  --y;
    switch(z){
      case 1 : rep(i,0,x+1){
        rep(j,0,H+1){
          d[i][j] = false;
        }
      }
      break;
      case 2 : rep(i,x+1,W+1){
        rep(j,0,H+1){
          d[i][j] = false;
        }
      }
      break;
      case 3 : rep(i,0,W+1){
        rep(j,0,y+1){
          d[i][j] = false;
        }
      }
      break;
      case 4 : rep(i,0,W+1){
        rep(j,y+1,H+1){
          d[i][j] = false;
        }
      }
      break;
    }
  }
  int cnt = 0;
  rep(i,0,W)rep(j,0,H){
    if(d[i][j]) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
def get_digit(n):
    return int(str(n)[-1])

dig_to_pronounce = {
    2: 'hon',
    4: 'hon',
    5: 'hon',
    7: 'hon',
    9: 'hon',
    0: 'pon',
    1: 'pon',
    6: 'pon',
    8: 'pon',
    3: 'bon',
}

def main():
    N = int(input())
    print(dig_to_pronounce[get_digit(N)])


if __name__ == '__main__':
    main()


Measured memory_bytes: 9052
#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N = 1e6 + 10;
using namespace std;
string a,b;
int main() {
  ios::sync_with_stdio(false);
   cin>>a>>b;
   int a1=a[0]-'0';
   int b1=b[0]-'0';
   string c=a;
   string d=b;

   for(int i=1;i<=b1-1;i++)
       a+=c;
   for(int i=1;i<=a1-1;i++)
       b+=d;
   vector<string> A;
   A.push_back(a);
   A.push_back(b);
   sort(A.begin(),A.end());
   cout<<A[0];

    return 0;
}

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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=500003;
int main()
{
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int x;
		cin>>x;
		n-=x;
	}
	if(n<0) n=-1;
	cout<<n;
	return 0;
}

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

typedef long long int ll;
typedef vector<int> vi;            typedef vector<ll> vl;
typedef vector<vi> vvi;         typedef vector<vl> vvl;
typedef pair<int, int>     pii;    typedef pair<ll, ll> pll;
typedef vector<pii> vii;         typedef vector<pll> vll;
typedef map<int,int> mii;
typedef vector<char> vc;
typedef vector<bool> vb;
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define rforne(i,n) for(int i=n;i>=1;i--)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
const ll INFL = 1e18;
const int INFI = 1e9;
#ifdef KARAN
    #include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}
ll modpow(ll a, ll b, ll m = MOD){a %= m; ll res = 1; 
    while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}
void graph(vvi &adj, int m) {int x, y; x--; y--; forn(i, m){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}}

typedef vector<double> vd;
void solve(){
    int n; cin>>n;
    vd p(n);
    forn(i, n) cin>>p[i];
    vector<vd> dp(n+1, vd(n+1, 0));
    dp[0][0] = 1;
    forn(i, n)
        forn(j, n)
            dp[i+1][j+1] += dp[i][j]*p[i],
            dp[i+1][j] += dp[i][j]*(1-p[i]);
    int cntr = n/2+1;
    double ans = 0;
    for(int i = cntr; i<=n; i++)
        ans += dp[n][i];
    cout<<setprecision(12);
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef KARAN
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int t=1;
    while(t--)
        solve();
}

Measured memory_bytes: 70784
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), cout, ", ") << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, ostream &os = cout, string sep = " ")
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

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

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), os, ", ") << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, K);
    queue<ll> q;
    REP1(i, 9)
    {
        q.push(i);
    }
    REP(i, K - 1)
    {
        ll x = q.front();
        q.pop();
        ll a = x % 10;
        for (ll b = max(a - 1, 0LL); b <= min(a + 1, 9LL); ++b)
        {
            q.push(10 * x + b);
        }
    }
    OUT(q.front());
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto x:v)cerr<<x<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define EPS 1e-9
typedef long long ll;

signed main(){
  int n,m,s,t;
  cin >> n >> m >> s >> t;
  s--;
  t--;
  vector<vector<pair<ll,ll>>> sunuke(n),yen(n);
  int u,v,a,b;
  FOR(i,0,m){
    cin >> u >> v >> a >> b;
    u--;
    v--;
    yen[u].pb(make_pair(v,a));
    yen[v].pb(make_pair(u,a));
    sunuke[u].pb(make_pair(v,b));
    sunuke[v].pb(make_pair(u,b));
  }
  ll dminy[n],dmins[n];
  FOR(i,0,n){
    dminy[i] = -1;
    dmins[i] = -1;
  }
  int counter = 0;
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pque,pque2;
  pque.push(make_pair(0,s));
  while(pque.size() && counter < n){
    pair<ll,ll> p = pque.top();
    pque.pop();
    if(dminy[p.second] == -1){
      dminy[p.second] = p.first;
      counter++;
      for(auto x:yen[p.second]){
        if(dminy[x.first] == -1)pque.push(make_pair(dminy[p.second]+x.second,x.first));
      }
    }
  }
  counter = 0;
  pque2.push(make_pair(0,t));
  while(pque2.size() && counter < n){
    pair<ll,ll> p = pque2.top();
    pque2.pop();
    if(dmins[p.second] == -1){
      dmins[p.second] = p.first;
      counter++;
      for(auto x:sunuke[p.second]){
        if(dmins[x.first] == -1)pque2.push(make_pair(dmins[p.second]+x.second,x.first));
      }
    }
  }
  ll ans[n];
  ll MAX = 0;
  REP(i,0,n){
    MAX = max(MAX,(ll)1e15-dminy[i]-dmins[i]);
    ans[i] = MAX;
  }
  FOR(i,0,n){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 20216
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}


fn main() {
  let n = read::<i32>();
  let k = read::<i32>();
  let mut h = vec![];
  let mut answers = vec![];

  for _ in 0..n {
    let h_i = read::<i32>();
    h.push(h_i)
  }

  h.sort();

  let mut s_index = 0;
  for i in (k - 1)..n {
    answers.push(h[i as usize] - h[s_index]);
    s_index += 1;
  }


  // println!("{:?}", h);
  // println!("{:?}", answers);
  println!("{:?}", answers.iter().min().unwrap());

}



Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

int main(){

    int a, b;
    cin >> a >> b;
    cout << a * (a <= b) + (a-1)*(a > b) << endl;

    return 0;
}

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

int main()
{
string s ;
cin >> s ;
ll k ;
cin >> k ;
ll te=1;
bool ok=1;
rep(i,s.size()-1){
  if(s[i]!=s[i+1])ok=0;
}
if(ok){
  cout << k*s.size()/2 << endl;
  return 0;
}

rep(i,s.size()-1){
  if(s[i]==s[i+1])te++;
  else {ans+=te/2;te=1;}
}
ans+=te/2;
ll su=0;
te=1;
string ss=s+s ;
rep(i,ss.size()-1){
  if(ss[i]==ss[i+1])te++;
  else {su+=te/2;te=1;}
}
su+=te/2;
su=su-ans;


cout << ans+su*(k-1) << endl;
return 0;
}

Measured memory_bytes: 256
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for c in range(2,N):
    cc=L[c]
    for b in range(1,c):
        bb=L[b]
        if cc>=bb+L[b-1]: continue
        l=-1
        u=b-1
        while u-l>1:
            a=(l+u+1)//2
            aa=L[a]
            if aa+bb>cc: u=a
            else: l=a
        ans+=(b-u)
print(ans)

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

int main() 
{
	char a[110], b[110];
	
	scanf("%s%s", a, b);
	sort(a, a + strlen(a));
	sort(b, b + strlen(b), greater<char>());
	if (strcmp(a, b) < 0) puts("Yes");
	else puts("No");
}


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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1LL<<60;
const int MINF = 1e9;
const int MOD = 1e9+7;

using vi = vector<int>;
using vii = vector<vi>;

template<typename T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

template<typename T>
T GCD(T a,T b){ return b ? GCD(b,a%b) : a ;}
template<typename T>
T LCM(T a,T b){ return a*b / GCD(a,b) ;}

template<typename T>//文字列の置換/Boost:replace_all()
T replace_str(T str, string target, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(target, pos), pos != string::npos) {
        str.replace(pos, target.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main(){
    ll n,w;cin >> n >> w;
    vector<ll> value(n);
    vector<ll> weight(n);
    rep(i,n)cin >> weight[i] >> value[i];
    vector<vector<ll>> dp(n+1,vector<ll>(1e5+1,INF));

    //dp[0].assign(1e3+100,0);//ダメ
    //dpは重さを持っているのでdp[0][0]のみ0
    // 重さ0にもかかわらず、価値を持ってしまうため
    dp[0][0] = 0;
    for(int i=0;i<n;i++){
        for(int sum_v=0;sum_v<=1e5;sum_v++){
            if(sum_v - value[i] >= 0){
                chmin(dp[i+1][sum_v],dp[i][sum_v-value[i]] + weight[i]);
            }
            chmin(dp[i+1][sum_v],dp[i][sum_v]);
        }
    }
    ll ans = 0;
    for(int i=0;i<=1e5;i++){
        if(dp[n][i]<=w)ans = i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 80256