akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;

int main(){
    int k;
    cin>>k;
    queue<string>q;
    for(int i=1; i<=9; ++i)q.push(to_string(i));
    while(1){
        if(k<=q.size()){
            rep(i,k-1)q.pop();
            cout<<q.front()<<endl;
            return 0;
        }
        k-=q.size();
        vector<string>sq;
        while(!q.empty()){
            string s=q.front();
            q.pop();
            int n=s.size();
            rep(i,10){
                if(abs((s[n-1]-'0')-i)<=1)sq.push_back(s+char(i+'0'));
            }
        }
        rep(i,sq.size())q.push(sq[i]);
    }
}


Measured memory_bytes: 11512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

int dp[100005][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	repn(i, 1, n + 1){
		int a, b, c;
		cin >> a >> b >> c;
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a;
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b;
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c;
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 1408
import sys
H,W = map(int,input().split())

if H%3 == 0 or W%3 == 0:
  print(0)
  sys.exit()

ans = float("inf")  
if W < H:
  W,H = H,W
  
for i in range(1,W): #W>=Hの前提で考える。
  a = H*i
  if H%2 == 0:
    b = (W-i)*(H//2)
    ans = min(ans,abs(a-b))
  else:
    b = (W-i)*(H//2)
    c = (W-i)*(H//2+1)
    dif = max(abs(a-b),abs(a-c),abs(b-c))
    ans = min(ans,dif)

for i in range(1,H): #W>=Hの前提で考える。
  a = W*i
  if W%2 == 0:
    b = (H-i)*(W//2)
    ans = min(ans,abs(a-b))
  else:
    b = (H-i)*(W//2)
    c = (H-i)*(W//2+1)
    dif = max(abs(a-b),abs(a-c),abs(b-c))
    ans = min(ans,dif)    

#横分割
ans = min(ans,H)
print(ans)      

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#define rep(i, n)for(int i=0; i<n; i++)
using ll = long long int;
using namespace std;

int main(){
    string s;
    int m;
    while(true){
        cin >> s;
        if(s=="-") break;
        cin >> m;
        rep(i, m){
            int h;
            cin >> h;
            string s1 = s.substr(0, h);
            s.erase(0, h);
            s += s1;
        }
        cout << s << endl;
    }
     
    return 0;
}


Measured memory_bytes: 3208
//aea ctmr
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
//v.erase(unique(v.begin(),v.end()),v.end());
#define f(i,a,b) for( ll i = a; i < b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define PI 3.14159265358979323846
 
typedef long double ld;
typedef long long ll;
const ll N = 100500;
const ll mod = 1e9 + 7;
using namespace std;
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << endl;}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);}
#else
#define trace(...)
#endif

vector <ll> xd;
ll fact[N];

ll bpow(ll a, ll b){
    if(b == 0) return 1LL;

    ll a1 = bpow(a, b / 2);
    ll a2 = (a1 * a1) % mod;
    if(b % 2 == 0) return a2;
    else return (a2 * a) % mod;
}

ll comb(ll a, ll b){
    if(a < b) return 0LL;
    ll dev = fact[a];
    ll aba = (fact[b] * fact[a - b]) % mod;

    dev *= bpow(aba, mod - 2);
    dev %= mod;

    return dev;
}

int main(){
    fastio;
    ll n, k;
    cin >> n >> k;

    fact[0] = 1LL;
    for(ll i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % mod;

    for(ll i = 0; i < n; i++){
        ll a;
        cin >> a;
        xd.push_back(a);
    }

    sort(xd.begin(), xd.end());
    ll ans = 0;
    for(ll i = 0; i < n; i++){
        ll uwu = (xd[i] * comb(n - i - 1, k - 1));
        ans -= uwu;
        ans %= mod;
    }
    for(ll i = 0; i < n; i++){
        ll uwu = (xd[i] * comb(i, k - 1));
        ans += uwu;
        ans %= mod;
    }

    if(ans < 0) ans += mod;

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


Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define REP(i,n)    for(int i = 0; i < (int)n; i++)
#define MAX_N   100000
typedef long long ll;

void solve(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    int ans = (a[2] / a[0]) * a[1];
    
    cout << ans << endl;
}

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

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

int *factorial_table;

void factorial_init(int max, int m) {
  factorial_table = new int[(max + 1) * 3];
  factorial_table[0] = 0;
  factorial_table[1] = 1;
  factorial_table[2] = 1;
  factorial_table[3] = 1;
  factorial_table[4] = 1;
  factorial_table[5] = 1;
  for (int i = 2; i <= max; i++) {
    int inv = m - (int)((long)factorial_table[3 * (m % i)] * (m / i) % m);
    int *p = factorial_table + 3 * i;
    p[0] = inv;
    p[1] = (int)((long)p[-2] * i % m);
    p[2] = (int)((long)p[-1] * inv % m);
  }
}

int combination(int n, int k, int m) {
  return (int)((long)factorial_table[3 * n + 1] * factorial_table[3 * k + 2] % m *
               factorial_table[3 * (n - k) + 2] % m);
}

int calc(int n, int k, int i, int m) {
  if (n - k < i - 1) {
    return 0;
  }
  int blue = combination(k - 1, i - 1, m);
  int red = combination(n - k + 1, i, m);
  return (int)((long)blue * red % m);
}

int main() {
  int m = 1000000007;
  int n, k;
  cin >> n >> k;

  factorial_init(n, m);

  for (int i = 1; i <= k; i++) {
    int answer = calc(n, k, i, m);
    cout << answer << endl;
  }
}

Measured memory_bytes: 3612
import copy
N = int(input())
R = []
for i in range(N):
    a,b = map(int,input().split())
    R.append([a,b])
B = []
for i in range(N):
    c,d = map(int,input().split())
    B.append([c,d])
######
INF = 10**10
R.sort(key=lambda x:-x[1])
B.sort(key=lambda x:x[0])
ans = 0
for r in range(N):
    for b in range(N):
        if R[r][0]<B[b][0] and R[r][1]<B[b][1]:
            ans+=1
            B[b][0]=-INF
            B[b][1]=-INF
            break
print(ans)

Measured memory_bytes: 3444
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int x;
    int id;
}node;

int compare_ascending(const void* a, const void* b){
    if(((node*)a)->x - ((node*)b)->x == 0){
        return ((node*)a)->id - ((node*)b)->id;
    }else{
        return ((node*)a)->x - ((node*)b)->x;
    }
}

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    node a[n+1];
    a[0].x = 0;
    a[0].id = 0;
    for(int i=1; i<=n; i++){
        int buf;
        scanf("%d", &buf);
        a[i].x = buf + a[i-1].x;
        a[i].x = a[i].x % k;
        a[i].id = i;
    }
    for(int i=0; i<=n; i++){
        a[i].x -= (i%k);
        if(a[i].x < 0){
            a[i].x += k;
        }
    }
    /*for(int i=0; i<=n; i++){
        printf("%d ", a[i].x);
    }
    printf("\n");
    for(int i=0; i<=n; i++){
        printf("%d ", a[i].id);
    }
    printf("\n");*/
    qsort(a, n+1, sizeof(node), compare_ascending);
    /*for(int i=0; i<=n; i++){
        printf("%d ", a[i].x);
    }
    printf("\n");
    for(int i=0; i<=n; i++){
        printf("%d ", a[i].id);
    }
    printf("\n");*/
    long long int ans = 0;
    int target = 0;
    for(int i=1; i<=n; i++){
        if(a[target].x == a[i].x){
            while(target < i && (a[i].id - a[target].id) >= k){
                target++;
            }
            ans += i - target;
            //printf("%d %d\n", i, target);
        }else{
            target = i;
        }
    }
    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 3324
#include <bits/stdc++.h>
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)
#define REPr(i, n) for(int i = (n)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;
///////////////////////////////////////////////
// for template
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

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


///////////////////////////////////////////////
/// 🍈( '-' 🍈 |AC|
int main() {
    ll L,R; cin >> L >> R;
    if (R - L >= 2020){
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1e16;

    for (ll i = L; i <= R; i++) {
        for (ll j = i + 1; j <= R; j++) {
            chmin(ans,(i * j) % 2019);        
        }
    }
    cout << ans << endl;
}

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

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

    int ans;
    for(int i = 0; i < (1<<3); i++) {
        int ret = s[0] - '0';
        for(int k = 0; k < 3; k++) {
            if((i>>k)&1) ret += (s[k+1] - '0');
            else ret -= (s[k+1] - '0');
        }
        if(ret == 7) {
            ans = i;
            break;
        }
    }

    int c = 0;
    for(; c < 3; c++) {
        cout << s[c];
        if((ans>>c)&1) cout << "+";
        else cout << "-";
    }
    cout << s[c] << "=7" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(b==0)
    return a;
    else
        return gcd(b,a%b);
}

int main(){
int t;cin>>t;
if(t<30)
    cout<<"No\n";
else
    cout<<"Yes\n";
return 0;}

Measured memory_bytes: 3560
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    // 整数の入力
	int size = Integer.parseInt(sc.nextLine());
    int[] cell = new int[size];
    for(int i = 0; i < size; i++){
      cell[i] = Integer.parseInt(sc.next());
    }
    //System.out.println(cell[size-1]);
    
    //計算
    int maxmove = 0;
    int nowmove = 0;
    for(int i = 0; i < size-1; i++){
      if(cell[i] >= cell[i+1])
      {
        //進行可能
        nowmove++;
        //System.out.println("ikeru");
      }
      else
      {
        //進行不可
        if(maxmove < nowmove){
          maxmove = nowmove;
        }
        nowmove = 0;
        //System.out.println("muri");
      }
      
    }
    
    if(maxmove < nowmove){
          maxmove = nowmove;
    }
    
    System.out.println(maxmove);
    
  }
}

Measured memory_bytes: 48824
#include<bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
const int MAXN = 100010;
int n, l, timer=0;
vector<int> grf[MAXN];
vector<vector<int>> up;
int tin[MAXN],tout[MAXN];

bool isancestor(int u,int v){
    return tin[u]<=tin[v] and tout[u]>=tout[v];
}

int lca(int u,int v){
    if( isancestor(u,v)) return u;
    if( isancestor(v,u)) return v;
    for(int i=l; i>=0; i--){
        if( !isancestor(up[u][i],v)){
            u = up[u][i];
        }
    }
    return up[u][0];
}

void dfs(int node, int p){
    tin[node] = ++timer;
    up[node][0] = p;

    // initialise its ancestors
    for(int i=1; i<=l; i++){
        up[node][i] = up[ up[node][i-1] ][i-1];
    }
    // go only in subtree
    for(auto nbr : grf[node]){
        if( nbr!= p){
            dfs(nbr,node);
        }
    }
    tout[node] = ++timer;
}

void init(int root){
    l = (int) ceil(log2(n));
    up.assign(n+1,vector<int>(l+1));
    dfs(root,root);
}

int main() {
    // freopen("./input.txt","r",stdin);
    // freopen("./output.txt","w",stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n;
    int x,ch; 
    for(int i=0; i<n; i++){
        cin>>ch;
        while(ch--){
            cin>>x;
            grf[i].push_back(x);
        }
    }
    init(0);
    int q; cin>>q;
    while(q--){
        int u,v; cin>>u>>v;
        cout<< lca(u,v) <<"\n";
    }
}


Measured memory_bytes: 24020
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;

bool same(string s, string t){
    if(t.length() - s.length() != 1) return false;

    for(int i=0;i<s.length();i++){
        if(s[i] != t[i]) return false;
    }
    if(isalpha(t[t.length() - 1])) return true;
    else return false;
}

int main(){
    fast;
    string s,t;
    cin >> s;
    cin >> t;
    bool ans = same(s,t);
    if(ans) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>

using namespace std;

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0)
      break;
    int A[n];
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      int a;
      cin >> a;
      sum += a;
      A[i] = a;
    }
    double avg = sum / n;
    int count = 0;
    for (int i = 0; i < n; ++i) {
      if (A[i] <= avg)
        ++count;
    }
    cout << count << endl;
  }
  return 0;
}



Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_A = 1000005;

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

    bool pairwise = true;
    for (int i = 2; i < MAX_A; i++) {
        int cnt = 0;
        for (int j = i; j < MAX_A; j+=i) cnt += C[j];
        if (cnt > 1) {
            pairwise = false;
            break;
        }
    }
    if (pairwise) {
        cout << "pairwise coprime" << endl;
        return 0;
    }

    int g = 0;
    for (int i= 0; i < N; i++) g = __gcd(g, A[i]);
    if (g == 1) {
        cout << "setwise coprime" << endl;
        return 0;
    }

    cout << "not coprime" << endl;
    return 0;
}

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

int main(void) {
    long long num;
    cin >> num;
    string result = "";
    while (num) {
        long long k = num /26;
        long long z = num % 26;
        if  (z == 0) {
            result = (char)('z') + result;
            k--;
        } else {
            // Coming from storing back
            result = (char) ( 'a' + z - 1) + result;
        }
        num = k;
    }
    cout << result << "\n";
    return 0;
}



Measured memory_bytes: 3136
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code,
  unused_macros
)]
//use proconio::fastout;
use proconio::input;
use proconio::marker::*;
//use std::collections::HashSet;
use std::cmp::*;
use std::collections::*;
macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}
fn main() {
  input! {
     H:usize,
     W:usize,
     C:(Usize1, Usize1),
     D:(Usize1, Usize1),
     S:[Chars;H]
  }
  let C: (usize, usize) = (C.0 + 2, C.1 + 2);
  let D: (usize, usize) = (D.0 + 2, D.1 + 2);
  let S: Vec<Vec<char>> = S;
  let mut kabe = vec![vec![true; W + 10]; H + 10];
  for x in 0..H {
    for y in 0..W {
      if S[x][y] == '.' {
        kabe[x + 2][y + 2] = false;
      }
    }
  }
  let kabe: Vec<Vec<bool>> = kabe;
  // Cを基準に幅優先探索。
  // (n=ワープ回数, 位置)
  let mut h = BinaryHeap::new();
  //訪問済み
  let mut v = vec![vec![false; W + 10]; H + 10];
  // ワープ回数
  let mut d = vec![vec![std::u64::MAX; W + 10]; H + 10];
  v[C.0][C.1] = true;
  d[C.0][C.1] = 0;
  h.push((Reverse(0), C.0, C.1));

  let mut mv = |h: &mut BinaryHeap<(Reverse<u64>, usize, usize)>, c: u64, x: usize, y: usize| {
    if !kabe[x][y] {
      if kabe[x][y] == false {
        if d[x][y] > c {
          d[x][y] = c;
          h.push((Reverse(c), x, y));
        }
      }
    }
  };
  while let Some((Reverse(c), x, y)) = h.pop() {
    mv(&mut h, c, x - 1, y);
    mv(&mut h, c, x + 1, y);
    mv(&mut h, c, x, y - 1);
    mv(&mut h, c, x, y + 1);
    let c = c + 1;
    mv(&mut h, c, x - 2, y - 2);
    mv(&mut h, c, x - 2, y - 1);
    mv(&mut h, c, x - 2, y);
    mv(&mut h, c, x - 2, y + 1);
    mv(&mut h, c, x - 2, y + 2);
    mv(&mut h, c, x - 1, y - 2);
    mv(&mut h, c, x - 1, y - 1);
    mv(&mut h, c, x - 1, y + 1);
    mv(&mut h, c, x - 1, y + 2);
    mv(&mut h, c, x, y - 2);
    mv(&mut h, c, x, y + 2);
    mv(&mut h, c, x + 1, y - 2);
    mv(&mut h, c, x + 1, y - 1);
    mv(&mut h, c, x + 1, y + 1);
    mv(&mut h, c, x + 1, y + 2);
    mv(&mut h, c, x + 2, y - 2);
    mv(&mut h, c, x + 2, y - 1);
    mv(&mut h, c, x + 2, y);
    mv(&mut h, c, x + 2, y + 1);
    mv(&mut h, c, x + 2, y + 2);
  }
  let ans = d[D.0][D.1];
  if ans < std::u64::MAX {
    println!("{}", ans);
  } else {
    println!("-1");
  }
}


Measured memory_bytes: 17448
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int c,lim,sho;
string res[65],str;
bool check(string s)
{
    if(!s.size())return 1;
    cout<<"? "<<s<<endl;
    int t;
    cin>>t;
    if(t==sho)return 1;
    return 0;
}
string merge(int l,int r)
{
    if(l==r)return res[l];
    int mid=(l+r)>>1;
    string t1=merge(l,mid),t2=merge(mid+1,r),ans="";
    int j=0;sho=c-t1.size()-1;
    for(int i=0;i<t1.size();i++)
    {
        while(j<t2.size())
        {
            if(!check(ans+t2[j]+t1.substr(i)))break;
            ans.pb(t2[j]);
            j++;
            sho--;
        }
        ans.pb(t1[i]);
    }
    while(j<t2.size())ans.pb(t2[j]),j++;
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    int cnt=0,t;
    for(int i='A';i<='Z';i++)
    {
        str.clear();
        for(int j=1;j<=128;j++)str.pb(i);
        cout<<"? "<<str<<endl;
        cin>>t;
        t=128-t;
        if(t)
        {
            c+=t;
            cnt++;
            for(int j=1;j<=t;j++)res[cnt].pb(i);
        }
    }
    for(int i='a';i<='z';i++)
    {
        str.clear();
        for(int j=1;j<=128;j++)str.pb(i);
        cout<<"? "<<str<<endl;
        cin>>t;
        t=128-t;
        if(t)
        {
            c+=t;
            cnt++;
            for(int j=1;j<=t;j++)res[cnt].pb(i);
        }
    }
    for(int i='0';i<='9';i++)
    {
        str.clear();
        for(int j=1;j<=128;j++)str.pb(i);
        cout<<"? "<<str<<endl;
        cin>>t;
        t=128-t;
        if(t)
        {
            c+=t;
            cnt++;
            for(int j=1;j<=t;j++)res[cnt].pb(i);
        }
    }
    string s=merge(1,cnt);
    cout<<"! "<<s<<endl;
    return 0;
}

Measured memory_bytes: 3772
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <list>
#include <queue>
using namespace std;

#define int long long
#define INF 1e18

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

    int ans = 1;
    for(int i = 1; i < n; i++) {
        bool flag = true;
        for(int j = 0; j < i; j++) {
            if(h[i] < h[j]) flag = false;
        }
        if(flag) ans++;
    }

    cout << ans << endl;
}


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

#define boost                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long int
// #define int ll
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>
#define vii vector<pii>
#define pb push_back
#define B begin()
#define E end()
#define sz(A) (ll)(A).size()
#define F first
#define S second
#define loop(z, v) for (auto &z : v)
#define sp << ' ' <<
#define sps << ' '
#define nl "\n"
// #define nl endl
#define fat 1000000007
// #define fat 998244353
#define PI_2 1.57079632679489661923

ll power(ll base, ll exp, ll mod) // O(logn) time
{
    ll ans=1LL; 
    while(exp){
        if(exp&1LL) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exp>>=1LL;
    }
    return ans%mod;
}

int main() { 
    ll tt = 1, n, q, m, l, r, c, i, j, k, w;
    boost;
    
    // cin >> tt;
    ll ans = 1;

    for(int _ = 1; _ <= tt; _++){
        cin >> n;

        vi dp(n + 1, 1);
        dp[0] = dp[1] = dp[2] = 0;

        ll sum = 0;
        for(i = 3; i <= n; i++){
            dp[i] = (dp[i] + sum - dp[i - 1] - dp[i - 2] + 2*fat)%fat;
            sum = (sum + dp[i] + fat)%fat;
        }

        cout << dp[n] << nl;
    }
}


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

using namespace std;
// #define int long long
mt19937 rnd(time(0));
typedef long long ll;
typedef long double ld;

// #define _GLIBCXX_DEBUG
#define f first
#define s second
#define pb push_back
#define pii pair<int, int> 
#define vi vector<int>
#define int ll

void solve(){
    int a, b;
    cin >> a >> b;
    string A = "", B = "";
    for (int i = 0; i < b; ++i)
        A.pb(a + '0');
    for (int i = 0; i < a; ++i)
        B.pb(b + '0');
    cout << min(A, B) << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t = 1;
    while(t--){
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 1e18
#define REPL(i,a,b) for(int i=a;i<a;++i)
#define REPLE(i,a,b) for(int i=a;i<=a;++i)
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;

#define M_PI 3.14159265358979323846

char a[1020][1020];
const int oo = 1e9+10;
const int mod = 1e9+7;
ll memo[1020][1020];

ll gcd(ll a, ll b){return a==0 ? b : gcd(b%a, a);}

int add(int a, int b){
	return ((a+b) < mod ? a+b : a+b - mod);
}

int h,w;
ll dp(int i, int j){
	if(i == h-1 && j == w-1)return 1;
	if(memo[i][j] != -1)return memo[i][j];
	ll ans = 0;
	if(i+1 < h && a[i+1][j] != '#'){
		ans = dp(i+1,j);
	}
	if(j+1 < w &&  a[i][j+1] != '#'){
		ans = add(ans, dp(i,j+1));
	}
	return memo[i][j] = ans;
}

void solve(){
	cin>>h>>w;
	for(int i = 0 ; i < h; ++i){
		for(int j = 0 ; j < w ; ++j){
			cin >> a[i][j];
		}
	}	
	memset(memo, -1, sizeof memo);
	cout << dp(0,0) << '\n';
}
int main(){   
    ios::sync_with_stdio(0);cin.tie(0);
	int t=1;
	while(t--){
		solve();
	}
}  









Measured memory_bytes: 12820
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rpd(i,a,b) for(register int i=a;i>=b;--i)
#define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
typedef long long ll;
const int N=500+5;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct data{int x1,y1,x0,y0;}a[N*N];
int n,m,cnt;int b[N][N];
int main(){
	n=read();m=read();
	rep(i,1,n)rep(j,1,m)b[i][j]=read();
	rep(i,1,n){
		rep(j,1,m-1)
		if(b[i][j]%2==1){
			b[i][j]-=1;b[i][j+1]+=1;
			a[++cnt].x1=i;a[cnt].y1=j;
			a[cnt].x0=i;a[cnt].y0=j+1;
		}
		if(i==n)break;
		if(b[i][m]%2==1){
			b[i][m]-=1;b[i+1][m]+=1;
			a[++cnt].x1=i;a[cnt].y1=m;
			a[cnt].x0=i+1;a[cnt].y0=m;
		}
	}
	printf("%d\n",cnt);
	rep(i,1,cnt)printf("%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x0,a[i].y0);
	return 0;
}

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

typedef long long ll;

ll N, M;
vector<vector<ll>> Out, In;

vector<bool> Seen;
vector<ll> T;

vector<bool> RSeen;
set<ll> SCC;

list<ll> Loop;
set<ll> Set;

void dfs(ll v) {
  if (Seen[v]) return;
  Seen[v] = true;
  for (ll w : Out[v]) {
    dfs(w);
  }
  T.push_back(v);
}
void rdfs(ll v) {
  if (RSeen[v]) return;
  RSeen[v] = true;
  SCC.insert(v);
  for (ll w : In[v]) {
    rdfs(w);
  }
}

void find_loop() {
  vector<bool> lseen;
  deque<ll> loop;
  lseen.resize(N);
  ll v = *SCC.begin();
  while (!lseen[v]) {
    loop.push_back(v);
    lseen[v] = true;
    for (ll w : Out[v]) {
      if (SCC.count(w)) {
        v = w;
        break;
      }
    }
  }
  while (loop.front() != v) {
    loop.pop_front();
  }
  for (ll v : loop) {
    // cout << "@ " << v << endl;
    Loop.push_back(v);
  }
}
void find() {
  find_loop();
  for (ll v : Loop) {
    Set.insert(v);
  }
  for (auto it = Loop.begin(); it != Loop.end(); ++it) {
    ll v = *it;
    for (ll w : Out[v]) {
      if (Set.count(w)) {
        // cout << "@ " << v << " -> " << w << endl;
        for (auto it2 = next(it); true;) {
          if (it2 == Loop.end()) {
            for (auto it3 = Loop.begin(); *it3 != w;) {
              // cout << "@@ remove " << *it3 << endl;
              Set.erase(*it3);
              it3 = Loop.erase(it3);
            }
            break;
          }
          if (*it2 == w) break;
          // cout << "@ remove " << *it2 << endl;
          Set.erase(*it2);
          it2 = Loop.erase(it2);
        }
      }
    }
  }
}

void solve() {
  Seen.resize(N);
  for (ll v = 0; v < N; ++v) {
    dfs(v);
  }
  reverse(T.begin(), T.end());

  RSeen.resize(N);
  for (ll v : T) {
    SCC.clear();
    rdfs(v);
    if (SCC.size() > 1) {
      find();
      cout << Loop.size() << endl;
      for (ll v : Loop) {
        cout << v + 1 << endl;
      }
      return;
    }
  }
  cout << -1 << endl;
}

int main() {
  cin >> N >> M;
  Out.resize(N);
  In.resize(N);
  for (ll i = 0; i < M; ++i) {
    ll a, b;
    cin >> a >> b;
    --a;
    --b;
    Out[a].push_back(b);
    In[b].push_back(a);
  }
  solve();
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <queue>
using namespace std;

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

	for (int i = 0; i < S.size() - 1; i++) {
		if (S.at(i) == S.at(i + 1)) {
			cout << "Bad" << endl;
			return 0;
		}
	}

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

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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define intMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod = 1e9+7;

ll a,b;
int gcd(int x, int y){
	if(y == 0)return x;
	else return gcd(y, x%y);
}
int main(){
	cin >> a >> b;
	ll ans = (a * b) / gcd(a,b);
	cout << ans << endl;
}


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

int main(void){
    int n, k;
    cin >> n >> k;
    vector<long long> h(n+10);
    for(int i=1;i<=n;++i) cin >> h[i];
    vector<long long> dp(n+10, 10000000000);
    dp[0] = 0;
    dp[1] = 0;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=i+k;++j){
            if(j > n) break;
            dp[j] = min(dp[j], abs(h[j]-h[i])+dp[i]);
        }
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int x,n,p;
    map<int,int>mp;
    cin>>x>>n;
    while(cin>>p)
        mp[p]++;
    for(int i=0;;i++){
        if(mp[x-i]==0){
            cout<<x-i<<endl;
            return 0;
        }
        if(mp[x+i]==0){
            cout<<x+i<<endl;
            return 0;
        }
    }
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

const double eps = 0.1;

void Main() {
    ll a;
    double b;
    cin >> a >> b;
	
  	int c = b*100 + eps;
  
    ll x = a * c;
    cout << x/100 << endl;
	return;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353;

int N,ans,cnt;
string x;
struct p{int n,s;};
vector<p> v;

int pw(int n,int k){
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}

int f(int a){//長さaのループがX以下に何種類存在するか
  int res=0;
  for(int i=0;i<a;i++) if(x[i]=='1') res+=pw(2,a-i-1),res%=MOD;//桁DPっぽいところ
  //最初a文字がXと完全に一致しているやつがx以下かどうかの判定
  string s,A=x.substr(0,a);
  while(s.size()<N)s+=A;
  for(int i=0;i<s.size();i++) if((i/a)&1) s[i]=(s[i]^'1')+'0';
  //sがx以下かどうか判定する
  for(int i=a;i<N;i++){
    if(x[i]^s[i]) {res+=(s[i]=='0');break;}
    res+=(i==N-1);
  }
  return res;
}

int INT(string x){//xを数字に変換する
  int res=0;
  for(char p:x)res*=2,res+=(p=='1'),res%=MOD;
  return res;
}

signed main(){
  cin>>N>>x;
  for(int i=1;i<N;i++) if(N%i==0&&(N/i)&1) v.push_back({i,f(i)});
  for(int i=0;i<v.size();i++){
    for(int j=i+1;j<v.size();j++) if(v[j].n%v[i].n==0) v[j].s-=v[i].s;
    ans+=v[i].s*2*v[i].n;ans%=MOD;
    cnt+=v[i].s;cnt%=MOD;
  }
  int nomal=(INT(x)+1-cnt)%MOD;//2*Nでループするやつの個数
  ans+=nomal*N*2%MOD;ans%=MOD;if(ans<0)ans+=MOD;
  cout<<ans<<endl;
}


Measured memory_bytes: 1052
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ll long long

int main() {
	//入力
	int n;
	cin >> n;
	vector<int> v(n), c(n);
	rep(i, n) cin >> v[i];
	rep(i, n) cin >> c[i];
	int ans = 0;
	rep(i, n) {
		if ((double)v[i] / c[i] > 1.0) {
			ans += v[i] - c[i];
		}
	}
	std::cout << ans << endl;
}

Measured memory_bytes: 3596
import math

while True:
    r, n = map(int, input().split())
    if r == 0 and n == 0:
        break
    sun_place = [-10000000000000000000 for _ in range(r)]
    for i in range(r):
        sun_place[i] = 0 - r + math.sqrt(r * r - i * i)

    ans = 10000000000000000
    bilding1 = [0 for i in range(len(sun_place))]
    bilding2 = [0 for i in range(len(sun_place))]
    for i in range(n):
        x1, x2, h = map(int, input().split())
        if x1 < -r:
            x1 = -r
        if r <= x2:
            x2 = r
        for j in range(x1, x2):
            if j < 0:
                j += 1
                bilding1[abs(j)] = max(h, bilding1[abs(j)])
            else:
                bilding2[abs(j)] = max(h, bilding2[abs(j)])

    for i in range(len(sun_place)):
        ans = min(ans, bilding1[i] - sun_place[i])
        ans = min(ans, bilding2[i] - sun_place[i])
    print(ans)
    # print(bilding1, bilding2)
    # print(sun_place)


Measured memory_bytes: 5700
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main(){
    int N;
  string S;
  cin >> N >> S;
  int ans = 0;
  for(int i = 0; i < N-2;i++){
  if(S.substr(i,3) == "ABC"){
      ans += 1;
  }}
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
	double N,M;
	double G;
	M=0;
    cin>>N;
    for(int i=1;i<=N;i++)
{
	if(i%2==1)
	M+=1;
	else
	continue;
}   
    G=M/N;
    cout<<fixed<<setprecision(10)<<G<<endl;
    
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1e9 + 7
#define INF 1e9
#define SENTINEL 2e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T>
inline bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
template <class T>
T GCD(T a, T b) {if (b == 0) return a; else return GCD(b, a % b);}
template <class T>
inline T LCM(T a, T b) { return (a * b) / GCD(a, b);}

int main(){
    int n, m;
    cin >> n >> m;
    if (n >= m){
        cout << 0 << endl;
        return 0;
    }
    vector<int> x(m);
    rep(i, m) cin >> x[i];
    sort(x.begin(), x.end());
    vector<int> dis(m - 1);
    rep(i,m - 1) dis[i] = x[i + 1] - x[i];
    sort(dis.begin(), dis.end());
    int sum = 0;
    rep(i, m - n) sum += dis[i];
    cout << sum << endl;
}

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

typedef long long ll;

int main() {        
	string s;
	cin >> s;
	int x = (int)s.size();
	for (int i = 0;  i < pow(2,x - 1); ++i) {
		string ans = "";
		ans += s[0];
		int sum = s[0] - '0';
		for (int j = 0, p = 0; j < x - 1; ++j,p++) {
			if ((i >> j) & 1) {
			//	if (j == 0) {
				//	sum += (s[p] - '0') + (s[p + 1] - '0');
			//	}else {
					sum = (sum + (s[p + 1] - '0'));
			//	}
				//if (i == 0) {
				//	ans += ;
					ans += "+";
					ans += s[p+ 1];
			//	} 
			}else {
			//if (j == 0) {
				//	sum += (s[p] - '0') - (s[p + 1] - '0');
				//}else {
					sum = (sum - s[p + 1] + '0');
				//}
				//ans += s[p];
				ans += "-";
				ans += s[p + 1]; 
			//	cout << sum << " ";
			}
		//	cout << sum << " ";
		}
	//	cout << sum << " " << ans << endl;
		//cout << ans << endl;
		if (sum == 7) {
			cout << ans << "=7";
			return 0;
		}
	}
}




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

struct p{char c;int a;};
int costb[3000][3000],costw[3000][3000],dp[3000][3000];

template<typename T>
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n_,T d):n(n_),bit(n_+1,d){}

  //bit[i]は長さはiの最後のbit分で、スタートはそれ以外のbit 合計でちょうどiまでの情報
  //最後のbitが表す物をk,それ以外のbitが表す物をlとするとbit[i]=(l,l+k]でl+k=i

  T sum(int i){
    T s=bit[0];
    for(int x=i;x>0;x-=(x&-x))//x&-x:(xの最後のbit) 上の言葉でxをl+kからlにしてる
      s+=bit[x];
    return s;
  }

  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))//k,l+kは自明に増える lは増えない(lとkの間に0が出来ない)
      bit[x]+=a;
  }

  void check(){
    for(int i=0;i<=10;i++)cout<<bit[i]<<" ";cout<<endl;
  }

  int lower_bound(int w){//w以上となる最小の場所を返す 単調性を仮定してる(bit[i]>=0)
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){//xに2のべき乗を大きい方から足せるなら足すだけ
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;//xはw未満を満たす最大の場所なので1大きい値を返す
  }

  T sum0(int i){
    return sum(i+1);
  }

  void add0(int i,T a){
    add(i+1,a);
  }

  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  T query0(int l,int r){
    return sum(r)-sum(l);
  }
};

signed main(){
  int N;cin>>N;
  vector<p> v(2*N);
  for(int i=0;i<2*N;i++){
    char c;int a;cin>>c>>a;
    v[i]={c,a};
  }
  BIT<int> b(3000,0),w(3000,0);
  for(int i=2*N-1;i>=0;i--){
    if(v[i].c=='B'){
      int res=b.sum(v[i].a);
      for(int j=0;j<=N;j++){
        int tmp=w.sum(j);
        costb[j][v[i].a]=res+tmp;
      }
      b.add(v[i].a,1);
    }
    else{
      int res=w.sum(v[i].a);
      for(int j=0;j<=N;j++){
        int tmp=b.sum(j);
        costw[v[i].a][j]=res+tmp;
      }
      w.add(v[i].a,1);
    }
  }
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      if(!i&&!j)continue;
      if(!i)dp[i][j]=dp[i][j-1]+costb[i][j];
      if(!j)dp[i][j]=dp[i-1][j]+costw[i][j];
      if(i&&j)dp[i][j]=min(dp[i][j-1]+costb[i][j],dp[i-1][j]+costw[i][j]);
    }
  }
  cout<<dp[N][N]<<endl;
}

/*
解説AC
dpって発想が出なかったのダメだな
なんか貪欲にいける気がしていた
sortの時に小さい方から置きながらのdpは典型なのでダメだね
ただcostの取り方は軽く考察いる気もするし難しい
*/


Measured memory_bytes: 73984
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)
typedef long long ll;

// sum(0), add(0,x) してはいけない
template<typename T>
class BIT{
public:
    vector<T> bit;
    int size;
    BIT(int size):
        bit(vector<T>(size+1,0)),size(size){}
    
    T sum(int i){
        if(!i) return 0;
        return bit[i]+sum(i-(i&(-i)));
    }

    void add(int i,T x){
        if(i>size)return;
        bit[i]+=x;
        add(i+(i&(-i)),x); 
    }   
};

int main(){
    int N; ll K; cin >> N >> K;
    vector<ll> a(N);
    REP(i,N) cin >> a[i];
    REP(i,N) a[i] -= K;
    REP(i,N-1) a[i+1] += a[i];
    ll ans = 0;
    REP(i,N) if(a[i]>=0) ans ++;
    vector<ll> b(a);
    sort(all(b));
    b.erase(unique(all(b)),b.end());
    REP(i,N) a[i] = lower_bound(all(b),a[i]) - b.begin() + 1;
    BIT<ll> bit(N+10);
    REP(i,N) {
        ans += bit.sum(a[i]);
        bit.add(a[i],1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn],n,k;
bool check(ll mid){//比它小的数大于等于k-1
    ll ans=0,x;
    for(int i=1;i<n;i++){
        if(a[i]<0){
            if(mid>0) x=mid/a[i];
            else x=mid/a[i]+(mid%a[i]!=0);
            ans+=n-(lower_bound(a+i+1,a+1+n,x)-(a+1));
        }
        else if(a[i]>0){
            if(mid<0) x=mid/a[i]-(mid%a[i]!=0);
            else x=mid/a[i];
            // ll x=floor(double(mid)/a[i]);
            ans+=upper_bound(a+i+1,a+1+n,x)-(a+i+1);
        }
        else{
            if(mid>=0) ans+=(n-i);
        }
    }
    return ans>=k;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    ll l=-1e18-3,r=1e18+3;
    while(l+1<r){
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
    return 0;
}

Measured memory_bytes: 1792
// https://atcoder.jp/contests/abc070/tasks/abc070_d

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define MAX 100001
const long long INF = 1e18;

vector<pair<int, int> > graph[MAX];
long long dist[MAX];

struct option
{
	bool operator() (const pair<int, long long> &a, pair<int, long long> &b) const {
		return a.second > b.second;
	}
};

void Dijkstra(int s)
{
	priority_queue<pair<int, long long>, vector<pair<int, long long> >, option> pq;
	pq.push(make_pair(s, 0));

	dist[s] = 0;

	while(!pq.empty())
	{
		pair<int, long long> top = pq.top();
		pq.pop();

		int u = top.first;
		long long w = top.second;

		for(int i = 0; i < graph[u].size(); i++)
		{
			pair<int, int> v = graph[u][i];

			if(w + v.second < dist[v.first])
			{
				dist[v.first] = w + v.second;
				pq.push(pair<int, long long>(v.first, dist[v.first]));
			}
		}
	}
}

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

	for(int i = 0; i < N-1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		graph[v].push_back(pair<int, int>(u, w));
		graph[u].push_back(pair<int, int>(v, w));
	}

	int Q, K;
	cin >> Q >> K;

	for(int i = 1; i <= N; i++)
	{
		dist[i] = INF;
	}

	Dijkstra(K);

	for(int i = 0; i < Q; i++)
	{
		int x, y;
		cin >> x >> y;

		long long first = dist[x];

		long long second = dist[y];

		// cout << "first is " << first << " and second is " << second << endl;
		long long ans = first + second;
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 10484
#!/usr/bin/env ruby
input = gets.chomp.split(" ").map(&:to_s).first

if [2,4,5,7,9].include?(input[-1].to_i)
  puts 'hon'
elsif [0,1,6,8].include?(input[-1].to_i)
  puts 'pon'
else
  puts 'bon'
end



Measured memory_bytes: 14300
#include<stdio.h>
#include<string.h>
int main(){
   char S[4];
   scanf("%s",S);

   if(strcmp(S, "ARC")==0){
      printf("%s","ABC");

      }else if(strcmp(S, "ABC")==0){
      printf("%s","ARC");
   }
   return 0;
}


Measured memory_bytes: 1712
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int n;
    string s;
    int k;
    cin >> n;
    cin >> s;
    cin >> k;
    char moji = s[k-1];
    for(int i=0;i<n;i++){
        if(s[i]!=moji) s[i]='*';
    }
  cout << s << endl;
}


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

#define Omar45 ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb push_back
#define endl '\n'
#define mod 1000000007
#define maxN 100005
const int inf=0x3f3f3f3f;

int arr[maxN], dp[maxN];

int main() {
	Omar45
    int n; cin >> n;
    for (int i=0; i<n; i++) cin >> arr[i];
    for (int i=0; i<=n; i++) dp[i] = mod;
    //memset(dp, mod, sizeof(dp));
    dp[0] = 0;
    for (int i=0; i<n; i++){
        if (i+1<n) dp[i+1]= min(dp[i+1], dp[i]+abs(arr[i]-arr[i+1]));
        if (i+2<n) dp[i+2]= min(dp[i+2], dp[i]+abs(arr[i]-arr[i+2]));
    }
    cout << dp[n-1] << endl;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;


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

	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			if (i * j == N)
			{
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

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

Measured memory_bytes: 256
n=gets.to_i
a=gets.split.map(&:to_i)

s=0;i=0;j=0
nn=0
while(nn<n)
  while((i<n-1)&&(a[i]<=a[i+1]));i+=1;end
  while((j<n-1)&&(a[j]>=a[j+1]));j+=1;end
  i=j=nn= i>j ? i+1 : j+1
  s+=1
end

p s


Measured memory_bytes: 8580
def main():
    r,g,b,n = map(int,input().split())
    c = 0
    for i in range(n//r+1):
        m = n - r * i
        for j in range(m//g+1):
            l = m - g * j
            if l % b == 0:
                c += 1
            
    print(c)

main()

Measured memory_bytes: 9176
n=int(input())
lst=[list(map(int,input().split())) for _ in range(n)]
# print(lst)
cnt=0
ans="No"
for i in range(n):
    a,b=lst[i]
    # print(a,b)
    if a==b:
        cnt+=1
    else:
        cnt=0
    if cnt==3:
        # print(a,b,cnt)
        ans="Yes"
        break

print(ans)

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



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

    int n;cin>>n;
    int k;cin>>k;
    int price=0;
    int* fruit = new int[n];
    for (int j = 0; j < n; j++)
    {
        cin>>fruit[j];
    }
    
    sort(fruit,fruit+n);
    for (int i = 0; i < k; i++)
    {
        price+=fruit[i];
    }

    cout<<price;
    


}


Measured memory_bytes: 3656
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();
		long x =  Long.parseLong(W.split(" ")[0]);
		long a =  Long.parseLong(W.split(" ")[1]);
		
		if(x < a)
			System.out.println(0);
		else
			System.out.println(10);
			
	}
}


Measured memory_bytes: 22996
def count_diff(a, b):
    cnt = 0
    for c_a, c_b in zip(a, b):
        if c_a != c_b:
            cnt += 1
    return cnt

S = input()
T = input()

if len(S) == len(T):
    ans = count_diff(S, T)
    print(ans)
    exit()

ans = float('inf')
for i in range(len(S)-len(T)):
    word = S[i:i+len(T)]
    tmp = count_diff(word, T)
    ans = min(ans, tmp)

print(ans)


Measured memory_bytes: 67420
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
int n;
int ans = 0;

void check(int x) {
    bool f3 = false, f5 = false, f7 = false;
    while (x != 0) {
        if (x > n)
            break;

        int a = x % 10;
        if (a == 3)
            f3 = true;
        else if (a == 5)
            f5 = true;
        else if (a == 7)
            f7 = true;
        x /= 10;
    }

    if (f3 && f5 && f7)
        ans++;
}

void dfs(int x) {
    check(x);
    if (x <= 100000000) {
        dfs(10 * x + 3);
        dfs(10 * x + 5);
        dfs(10 * x + 7);
    }
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

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

int judge_operator(int a,char op,int b);

int main(){
    int a,b,output_value;
    char op;
    char finish_op;
    finish_op = '?';
    while(1){
        scanf("%d %c %d",&a,&op,&b);
            if(op == finish_op){
            break;
            }
        printf("%d\n",judge_operator(a,op,b));
    }
}

int judge_operator(int a,char op,int b){
    int calculation_result;
    switch(op){
        case '+':
            calculation_result = a + b;
            break;
        case '-':
            calculation_result = a - b;
            break;
        case '*':
            calculation_result = a * b;
            break;
        case '/':
            calculation_result = a / b;
            break;
        
    }
    return calculation_result; 
}


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

int main(){

    int n;
    long R[200000];
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>R[i];
    }
    long max = -2000000000;
    long min = R[0];

    for(int i=1;i<n;i++){
        if(R[i]-min>max)    max = R[i] - min;
        if(R[i]<min)    min = R[i];
    }
    cout<<max<<endl;
}


Measured memory_bytes: 4652
use proconio::{input, fastout};
use std::collections::HashMap;


#[fastout]
fn main() {
    input! {
        n: usize,
        aaa: [i64; n],
    }

    let mut pls = HashMap::new();
    let mut mns = HashMap::new();
    for (i, a) in aaa.iter().enumerate() {
        *pls.entry(i as i64 + a).or_insert(0u64) += 1;
        *mns.entry(i as i64 - a).or_insert(0u64) += 1;
    }
    let mut ans = 0u64;
    for (p, c) in &pls {
        ans += c * mns.get(p).unwrap_or(&0);
    }
    println!("{}", ans);
}


Measured memory_bytes: 16108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int x[10][10];

int calc(string s)
{
    int r = 0;
    rep(i,s.size()) r = x[r][s[i]-'0'];
    return r;
}

int main()
{
    rep(i,10)rep(j,10) cin >> x[i][j];

    int ans = 0;
    rep(i,10000)
    {
        string t = to_string(i);
        reverse(all(t));
        while(t.size()<4) t+='0';
        reverse(all(t));

        int e = calc(t);
        t += '0'+e;

        int a = 0;
        rep(j,5)
        {
            char c = t[j];
            rep(k,10)if(k!=c-'0')
            {
                t[j]=k+'0';
                if(calc(t)==0) a=1;
            }
            t[j]=c;
        }
        rep(j,4)if(t[j]!=t[j+1])
        {
            swap(t[j],t[j+1]);
            if(calc(t)==0) a=1;
            swap(t[j],t[j+1]);
        }

        ans += a;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3244