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

using namespace std;

int n, a, b;

bool check_bit (int _a, int _bit) { return (_a >> _bit) & 1; }

int remove_bit (int _a, int _bit) {
    return (_a & ( (1 << _bit) - 1) ) | ( (_a >> (_bit + 1) ) << _bit);
}

int insert_bit (int _a, int _bit, bool val) {
    int tmp = (_a & ( (1 << _bit) - 1) ) | ( (_a >> (_bit) ) << (_bit + 1) );
    if (val) tmp |= (1 << _bit);
    return tmp;
}

vector<int> solve (int LOG, int be, int en) {
    if (LOG == 1) return vector<int>{ be, en };
    int diff = 0;
    while (diff < LOG) {
        if (check_bit(be, diff) != check_bit(en, diff) ) break ;
        ++diff;
    }
    bool diff_left = check_bit(be, diff);

    be = remove_bit(be, diff);
    en = remove_bit(en, diff);

    vector<int> left = solve(LOG - 1, be, be ^ 1),
                right = solve(LOG - 1, be ^ 1, en),
                ret;
    for (int _ : left) ret.push_back(insert_bit(_, diff, diff_left) );
    for (int _ : right) ret.push_back(insert_bit(_, diff, diff_left ^ 1) );

    return ret;
}

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

    cin >> n >> a >> b;

    if (!(__builtin_popcount(a ^ b) & 1) ) return cout << "NO\n", 0;
    cout << "YES\n";

    vector<int> ans = solve(n, a, b);

    for (auto _ : ans) cout << _ << ' '; cout << '\n';

    return 0;
}


Measured memory_bytes: 1756
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 2000005;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[SIZE], finv[SIZE], inv[SIZE];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

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);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

double len(int a, int b, int c, int d) {
	return (double)sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

int dp[3005][3005];
string LCS(string a, string b) {
	string res;
	for (int i = 0; i < a.length(); ++i) {
		for (int j = 0; j < b.length(); ++j) {
			if (a[i] == b[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; }
			else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); }
		}
	}

	int n = a.length(), m = b.length();
	while (n && m) {
		if (dp[n - 1][m] == dp[n][m]) { --n; }
		else if (dp[n][m - 1] == dp[n][m]) { --m; }
		else {
			res += a[n - 1];
			--n, --m;
		}
	}reverse(all(res));

	return res;
}

int main() {
	string a, b;
	cin >> a >> b;
	cout << LCS(a, b) << endl;
}

Measured memory_bytes: 37120
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define RREP(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;

template<typename T> class Edge{
    public:
        int to;
        T cost;

        Edge(){}
        Edge(int t, T c){
            this->to = t;
            this->cost = c;
        }
        bool operator<(Edge e){return this->cost < e.cost;}
        bool operator>(Edge e){return this->cost > e.cost;}
};

template<typename T> class Graph_list{
    public:
        vector<vector<Edge<T>>> list;

        Graph_list(int n);
        void add(int f, int t, T c);
        void add(int f, int t);
        int size();
        vector<Edge<T>> operator[](int i){
            return list[i];
        }
};

template<typename T> Graph_list<T>::Graph_list(int n){
    list = vector<vector<Edge<T>>>(n + 1, vector<Edge<T>>());
}

template<typename T> void Graph_list<T>::add(int f, int t, T c){
    list[f].push_back(Edge<T>(t, c));
}
template<typename T> void Graph_list<T>::add(int f, int t){
    list[f].push_back(Edge<T>(t, 1));
}
template<typename T> int Graph_list<T>::size(){
    return (int)list.size();
}

template<typename T>
vector<T> bfs_graph(Graph_list<T>& g, int s){
    const auto INF = numeric_limits<T>::max();
    vector<T> dist(g.size(), INF);
    
    queue<T> que;
    que.push(s);
    dist[s] = 0;
    while(que.size()){
        int p = que.front(); que.pop();
        for (auto e : g[p]){
            if (dist[e.to] == INF){
                dist[e.to] = dist[p] + e.cost;
                que.push(e.to);
            }
        }
    }
    return dist;
}


int main(){
    int n;
    cin >> n;
    Graph_list<ll> G(n);
    REP(i,0,n - 1){
        int a, b, c;
        cin >> a >> b >> c;
        G.add(a, b, c);
        G.add(b, a, c);
    }

    int q, k;
    cin >> q >> k;
    vector<ll> d = bfs_graph<ll>(G, k);
    REP(i,0,q){
        int x, y;
        cin >> x >> y;
        cout << d[x] + d[y] << endl;
    }
    
    
    return 0;
}

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

int main() {
  int n,a,b,ans = 0;
  cin >> n >> a >> b;
  for(int i = 1;i <= n;i++){
    int t = i/10000 + (i%10000)/1000 + (i%1000)/100 + (i%100)/10 + i%10;
    if((t >= a) && (t <= b)){
      ans += i;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
  
using namespace std;
const int inf = 1e9 + 7;
 
 
signed main() {
	/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
 
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
 
    int n;
    cin >> n;
    int a[n];
    map<int, int> b;
    int res = 0;
    for(int i = 0;i < n;i++) {
    	cin >> a[i];
    	res += b[a[i]];
    	b[a[i]]++;
    }

    for(int i = 0;i < n;i++) {
    	cout << res - b[a[i]] + 1 << '\n';
    }

}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	int n, x; cin >> n >> x;
	vector<int>a(n);
	rep(i, n)cin >> a[i];
	SORT(a);
	int ans = n, sum = 0;
	rep(i, n) x -= a[i];
	cout << ans + x / a[0] << "\n";

	return 0;
}

Measured memory_bytes: 256
//Daniel Grzegorzewski
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

const int N = 3006;

int n, a[N];
PII dp[N][N][2];

signed main() {
  init_ios();
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    dp[i][i][0] = {a[i], 0};
    dp[i][i][1] = {0, a[i]};
  }
  for (int len = 2; len <= n; ++len)
    for (int i = 1; i+len-1 <= n; ++i) {
      int j = i+len-1;
      PII tmp1 = {a[i]+dp[i+1][j][1].ST, dp[i+1][j][1].ND};
      PII tmp2 = {a[j]+dp[i][j-1][1].ST, dp[i][j-1][1].ND};
      if (tmp1.ST-tmp1.ND > tmp2.ST-tmp2.ND)
        dp[i][j][0] = tmp1;
      else
        dp[i][j][0] = tmp2;
      tmp1 = {dp[i+1][j][0].ST, a[i]+dp[i+1][j][0].ND};
      tmp2 = {dp[i][j-1][0].ST, a[j]+dp[i][j-1][0].ND};
      if (tmp1.ST-tmp1.ND < tmp2.ST-tmp2.ND)
        dp[i][j][1] = tmp1;
      else
        dp[i][j][1] = tmp2;
      
    }
  cout<<dp[1][n][0].ST-dp[1][n][0].ND<<"\n";
}

Measured memory_bytes: 280832
program main
  implicit none
  integer :: a, b
  real :: k
  read *, a, b
  if (a == b) then
    print '(i0)', 0
  else if (mod(a+b, 2) == 0) then
    print '(i0)', (a+b)/2
  else
    print '(a)', 'IMPOSSIBLE'
  end if

end program


Measured memory_bytes: 768
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
c, d = 0, 0
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] > A[j]:
      d += 1
    elif A[i] < A[j]:
      c += 1
kip = ((K * (K + 1)) // 2) % mod
pip = ((K * (K - 1)) // 2) % mod
S = (d * kip) % mod + (c * pip) % mod
S %= mod
print(S)

Measured memory_bytes: 3188
MOD = 10**9 + 7

def modcomb(n, k, mod):
    def fact(n, k, mod):
        ans = 1
        while n>k:
            ans = (ans * n) % mod
            n -= 1
        return ans

    def inv(k, mod):
        ans = 1
        while k>1:
            ans = (ans * k) % mod
            k -= 1
        return pow(ans, mod-2, mod)

    return (fact(n,n-k,mod) * inv(k, mod))%mod

def resolve():
    N,a,b = list(map(int, input().split()))
    ans = pow(2,N,MOD) - 1 - modcomb(N, a, MOD) - modcomb(N, b, MOD)
    print(ans % MOD)

resolve()

Measured memory_bytes: 39152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr long double EPS = 1e-15;
const long double PI = acos(-1);
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;
//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

void solve() {
    string s[3] = {"Sunny","Cloudy","Rainy"};
    string ss;
    cin >> ss;
    for (int i = 0; i < 3; i++) {
        if (ss == s[i]) {
            cout << s[(i+1)%3] << endl;
            return;
        }
    }
}

int main(int argc, char *argv[]){
    // /* Regular */
    // int case_num = 1;
    // if (argc > 1 && stoi(argv[1])) cin >> case_num;
    // REP(case_no, case_num) {
    //   cerr << endl << "case " << case_no + 1 << endl;
    //   solve();
    // }
    /* AOJ */
    solve();
    return 0;
}

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

int A,B,C,K;
int main(){
	cin>>A>>B>>C;
	cin>>K;
	
	for(int i = 0; i<K; i++){
		if(A>=B){
			B = B*2;
			continue;
		}
		if(B>=C){
			C = C*2;
			continue;
		}
	}
	
	if((A<B)&&(B<C)){
		cout<<"Yes"<<endl;
	} else {
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

typedef long long ll;

const ll inf = 1LL << 60;

ll dp[110][100100];

int main(){
  ll N,W; cin >> N >> W;
  vector<ll> w(N); vector<ll> v(N);
  
  ll max_v = 0;

  for(ll i = 0; i < N; i++){
    cin >> w[i] >> v[i];  max_v += v[i];}
  
  for(ll i = 0; i < 110; i++){
    for(ll j = 0; j < 100100; j++){
      dp[i][j] = inf;}}
  
  dp[0][0] = 0;
                                     
  for(ll i = 0; i < N; i++){
    for(ll sum_v = 0; sum_v <= 100100; sum_v++){
      if( sum_v >= v[i]){
        dp[i+1][sum_v] = min( dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i]);}
        dp[i+1][sum_v] = min( dp[i+1][sum_v], dp[i][sum_v]);}}
  
  ll res = 0;
  for(ll sum_v = max_v; sum_v >= 0; sum_v--){
    if( dp[N][sum_v] <= W){ cout << sum_v << endl; return 0;} }
  
   }


Measured memory_bytes: 86272
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
using namespace std;
using ll = long long;

int main(){
  int n;
  cin >> n;
  string str;
  cin >> str;
  int i=0;
  int j=n-1;
  int cnt=0;
  while(1){
    while(str[i]!='W'&&i < str.size()) i++;
    while(str[j]!='R'&&j > 0) j--;
    if(j<=i) break;
    swap(str[i],str[j]);
    cnt++;
  }
  cout << cnt;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)

using namespace std;

ll go(int index, int capacity, vector <ll> &wt, vector <ll> &val, vector <vector <ll>> &dp) {
	if(index == wt.size() || capacity <= 0) return 0;

	if(dp[index][capacity] != -1) return dp[index][capacity];
	
	//check before including the current index
	ll p1 = 0;
	if(capacity >= wt[index]) {
		p1 = val[index] + go(index + 1, capacity - wt[index], wt, val, dp);
	}
	ll p2 = go(index + 1, capacity, wt, val, dp);

	return dp[index][capacity] = max(p1, p2);

}

void solve() {
	int n, cpcty;
	cin >> n >> cpcty;

	vector <ll > wt(n), val(n);

	rep(i, 0, n) cin >> wt[i] >> val[i];
	vector <vector <ll >> dp(n + 1, vector <ll> (cpcty + 1, -1));
	cout << go(0, cpcty, wt, val, dp);

}

int main() {
	int t = 1;
	//cin >> t;
	while(t--)
		solve();

	return 0;
}


Measured memory_bytes: 80256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cctype>
#include <map>
#include <vector>
#include <queue>

#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
	int n, q;
	string s;
	cin >> n >> q >> s;
	vector<ll> num(s.size()+1,0);
	rep(i, 0, s.size()) {
		num[i+1] = num[i];
		if (s[i] == 'A'&&s[i + 1] == 'C')num[i+1]++;
	}
	rep(i, 0, q) {
		int l, r;
		cin >> l >> r;
		cout << num[r-1]-num[l-1] << endl;
	}
	return 0;
}

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int n,A,B,C;
vector<int> l;

int solve(int cnt,int a,int b,int c){
    if(cnt==n){
        if(a==0 || b==0 || c==0){
            return INF;
        }else{
            return abs(A-a)+abs(B-b)+abs(C-c) - 30;
        }
    }

    int ans0 = solve(cnt+1, a, b, c);
    int ans1 = solve(cnt+1, a+l[cnt],b, c) + 10;
    int ans2 = solve(cnt+1, a, b+l[cnt], c) + 10;
    int ans3 = solve(cnt+1, a, b, c+l[cnt]) + 10;

    return min(min(ans0,ans1),min(ans2,ans3));
}


int main(){
    bool flag=false;
    ll ans=0,sum=0;

    cin >>n>>A>>B>>C;
    rep(i,n){
        int li;
        cin>>li;
        l.pb(li);
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout<<solve(0,0,0,0)<<endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
n, m  = map(int,input().split())
l = [0] * m
r = [0] * m
for i in range(m):
    l[i],r[i] = map(int,input().split())
value = min(r) - max(l) + 1
if value >= 0:
    print(value)
else:
    print('0')

Measured memory_bytes: 10868
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
  #define pb push_back
#define f first
#define s second
  #define MAXN 100005
using namespace std;

int main()
{
	int arr[4];
	for(int i=0; i<4; i++) {
		cin>>arr[i];
	}
	sort(arr,arr+4);
	//cout<<arr[1]<<endl;
	if(arr[0]==1&&arr[1]==4&&arr[2]==7&&arr[3]==9) {
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}


	return 0;
}


Measured memory_bytes: 256
A, B, K = map(int, input().split())

ans = []
i = A if (A >= B) else B
while(1):
  if (A % i == 0 and B % i == 0):
    ans.append(i)
  i -=1
  if (len(ans) == K):
    break

ans = sorted(ans, reverse=True)
print(ans[K - 1])


Measured memory_bytes: 38256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let mut a: Vec<usize> = (0..n)
        .map(|_| iterator.next().unwrap().parse().unwrap())
        .collect();
    a.sort();

    let mut sum = 0;
    let mut t = 0;
    for i in 0..(n - 1) {
        sum += a[i];
        if sum * 2 < a[i + 1] {
            t = i + 1;
        }
    }
    return format!("{}", n - t);
}


Measured memory_bytes: 6396
#include<stdio.h>
main(){
  int x1,y1,y2,y3;
  int con;
  int x,y;
  scanf("%d",&x1);
  scanf("%d",&y1);                                                        
  scanf("%d",&y2);                                                        
  scanf("%d",&y3);                                             
  scanf("%d",&con);

  x=x1*con;
  if(con < y2){
    y=y1;
  }else{
    y= y1 + (con-y2)*y3;
  }
  if(x>y){
    printf("%d\n",y);
  }else if(x<y){
    printf("%d\n",x);
  }else{
    printf("%d\n",x);
  }
}

Measured memory_bytes: 2716
import sys
import math
n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
f = list(map(int, sys.stdin.readline().strip().split()))

a = sorted(a)  # 昇順ソート
f = sorted(f, reverse=True)  # 降順ソート


def team_result(a, f):
    eat = []
    for i, j in zip(a, f):
        eat.append(i * j)
    return(max(eat))


r = team_result(a, f)
l = -1  # l = 0 はあり得るので
while(l + 1 < r):
    mid = (l + r) // 2

    train_cost = 0
    for i, j in zip(a, f):
        train_cost += max(0, math.ceil(i - mid / j))

    if train_cost <= k:
        r = mid
    else:
        l = mid

print(r)

Measured memory_bytes: 118784
import bisect
s=list(input())
t=list(input())
N=len(s)
sd={x:[] for x in sorted(set(s))}
if not set(t) <= set(sd.keys()):
    print(-1)
    exit()

for i,c in enumerate(s):
    sd[c].append(i)
index=-1
ans=0
for c in t:
    i=bisect.bisect_left(sd[c],index+1)

    if i==len(sd[c]):
        ans+=1
        i=bisect.bisect_left(sd[c],0)
    index=sd[c][i]
print(ans*N+index+1)


Measured memory_bytes: 61296
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n;
ll a[100005];
ll dp[100005];
ll ans(ll index){
    if(index == (n-1)){
        return 0;
    }
    if(dp[index] != -1){
        return dp[index];
    }
    ll left = abs(a[index] - a[index+1]) + ans(index + 1);
    ll right = INT_MAX;
    if(index + 2 < n){
       right = abs(a[index] - a[index+2]) + ans(index + 2);
    }
    return dp[index] = min(left,right);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<ans(0)<<"\n";
    
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];
  int ans = INT_MAX, tmp;
  for (int i = 0; i < N - K + 1; i++) {
    tmp = A[i + K - 1] - A[i] + min(abs(A[i + K - 1]), abs(A[i]));
    if (ans > tmp) ans = tmp;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 640
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;

int n;

int main()
{
	ll n;
	cin >> n;
	cout << n+n*n+n*n*n << endl;
	return 0;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define DBGDO(X) ({ if(1) cerr << "DBGDO: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s; cin >> s;
	ll n = sz(s);
	
	vvl dp(n,vl(27,n+1));
	
	FORD(i,0,n) {
		ll k = s[i]-'a';
		dp[i][k] = i+1;
		FOR(j,k+1,27) {
			if (dp[i][j-1] >= n) continue;
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
		FOR(j,0,k) {
			if (dp[i][26] >= n) continue;
			dp[i][j] = dp[dp[i][26]][j];
		}
	}
	
	vvl step(20, vl(n,n+1));
	FOR(i,0,n) step[0][i] = dp[i][26];
	FOR(k,1,20) FOR(i,0,n) {
		if (step[k-1][i] >= n) continue;
		step[k][i] = step[k-1][step[k-1][i]];
	}
	
	ll q; cin >> q;
	while (q--) {
		ll a, b; cin >> a >> b;
		a--;
		FORD(k,0,20) {
			if (step[k][a] > b) continue;
			a = step[k][a];
			if (a == b) break;
		}
		cout << (a == b ? "Yes\n" : "No\n");
	}
}



Measured memory_bytes: 203932
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define sz(v) (ll)v.size()
#define inf 100000000000000
#define vll vector<ll>
#define pll pair<ll,ll>nnnn
using namespace std;
const int N=200004;

void solve()
{
	ll n,i;
	double x,sum=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		x=1/x;
		sum+=x;
	}
	printf("%.12lf",1/sum);

}
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
 
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int p = k / 500 * 1000;
        int q = (k % 500) / 5 * 5;
        System.out.println(p + q);
    }
}


Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <queue>


using namespace std;

typedef long long ll;

vector<bool> visited;
vector<vector<pair<int, int>>> graph;
vector<ll> costs;

void dfs(int k) {
	if (visited[k]) return;
	visited[k] = true;
	for (auto &e : graph[k]) {
		if (!visited[e.first]) {
			costs[e.first] = costs[k] + e.second;
			dfs(e.first);
		}
	}
}

int main() {
	int N, Q, K;
	cin >> N;
	graph.resize(N + 1, vector<pair<int, int>>());
	visited.resize(N + 1, false);
	costs.resize(N + 1, 0);
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}

	cin >> Q >> K;

	dfs(K);

	vector<long long> ans(Q);
	for (int i = 0; i < Q; i++) {
		int x, y;
		cin >> x >> y;
		ans[i] = costs[x] + costs[y];
	}

	for (int i = 0; i < Q; i++)
		cout << ans[i] << endl;

	return 0;
}

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

int cost(int i, int n, int h[], int dp[])
{
	if(dp[i]!=-1)
	return dp[i];
	if(i==n-1)
	return 0;
	if(i==n-2)
	{
		dp[i]=abs(h[i]-h[i+1]);
		return dp[i];
	}
	int ans=0;
	ans=min(abs(h[i]-h[i+1]) + cost(i+1, n, h,dp), abs(h[i]-h[i+2])+cost(i+2,n,h,dp));
	dp[i]=ans;
	return dp[i];
}

int main() {
	int n;
	cin>>n;
	int h[n], dp[n];
	for(int i=0; i<n; ++i)
	{
		cin>>h[i];
		dp[i]=-1;
	}
	dp[n-1]=0;
	cout<<cost(0,n,h,dp);
	return 0;
}

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

int main()
{
    int count=0;
    string w, str;
    cin >> w;
    while(cin>>str, str!="END_OF_TEXT"){
        string w1, str1;
        for(int i=0; i<w.size(); ++i) w1 += toupper(w[i]);
        for(int i=0; i<str.size(); ++i) str1 += toupper(str[i]);
        if(str1==w1)count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 3180
N,X,Y = map(int,input().split())
length = [0]*(N+1)
for i in range(1,N+1):
  for j in range(i,N+1):
    ans = min(abs(j-i),abs(X-i)+1+abs(Y-j),abs(X-j)+1+abs(Y-i))
    length[ans] += 1
for i in range(1,N):
  print(length[i])

Measured memory_bytes: 3444
#include<stdio.h>
int main()
{
int a,b,c,sw,i,temp;
  scanf("%d %d %d",&a,&b,&c);
  sw=0;
  temp=a;
  for(i=0;i<b;i++)
  {
  if(temp%b==c) {sw++;
             }
  temp=temp+a;
  }

 if(sw>0) printf("YES");
 else printf("NO");

return 0;
}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int mod = 998244353;

int n, k, s, t, a[100], m, num;
ll bs[100], comb[100][100], f[100], ans, rbs[100];
vector<int> tr;

inline int addMod(int a, int b) {
	return (a += b) >= mod ? a - mod : a;
}

inline ll quickpow(ll base, ll pw) {
	ll ret = 1;
	while (pw) {
		if (pw & 1) ret = ret * base % mod;
		base = base * base % mod, pw >>= 1;
	}
	return ret;
}

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

inline int popc(ll w) {
	w = (w & 0x5555555555555555) + ((w & 0xaaaaaaaaaaaaaaaa) >> 1);
	w = (w & 0x3333333333333333) + ((w & 0xcccccccccccccccc) >> 2);
	w = (w & 0x0f0f0f0f0f0f0f0f) + ((w & 0xf0f0f0f0f0f0f0f0) >> 4);
	w = (w & 0x00ff00ff00ff00ff) + ((w & 0xff00ff00ff00ff00) >> 8);
	w = (w & 0x0000ffff0000ffff) + ((w & 0xffff0000ffff0000) >> 16);
	w = (w & 0x00000000ffffffff) + ((w & 0xffffffff00000000) >> 32);
	return w;
}

void dfs(ll now, int step, int val) {
	if (!now) return;
	if (step == num) {
		ans += val * f[popc(now)];
		return;
	}
	dfs(now, step + 1, val);
	dfs(now & bs[step], step + 1, -val);
	dfs(now & rbs[step], step + 1, -val);
	return;
}

int main() {
	read(n), read(k), read(s), read(t);
	if ((s & t) != s) {
		cout << "0\n";
		return 0;
	}
	for (R int j = 0; j <= 18; ++j) {
		if ((s & (1 << j)) || (~t & (1 << j))) continue;
		tr.push_back(j), ++num;
	}
	for (R int i = 1; i <= n; ++i) {
		read(a[i]);
		if ((a[i] & s) != s || (a[i] & t) != a[i])
			continue;
		for (R int j = 0; j < num; ++j)
			if (a[i] & (1 << tr[j]))
				bs[j] |= 1ll << m;
		++m;
	}
	for (R int i = 0; i < num; ++i)
		rbs[i] = ((1ll << m) - 1) ^ bs[i];
	for (R int i = 0; i <= m; ++i) {
		comb[i][0] = 1;
		for (R int j = 1; j <= i; ++j) {
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			if (j <= k) f[i] += comb[i][j];
		}
	}
	dfs((1ll << m) - 1, 0, 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9) + 7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
const double PI = acos(-1);

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n)
{
	vector<pair<ll, ll>> p;
	for (ll i = 2; i * i <= n; i++)
	{
		if ((n % i) != 0)
			continue;
		pair<ll, ll> a = make_pair(i, 0);
		while ((n % i) == 0)
		{
			n /= i;
			a.second += 1;
		}
		p.push_back(a);
	}

	if (n != 1)
		p.push_back(make_pair(n, 1));
	return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a)
{
	ll b = MOD, u = 1, v = 0;
	while (b)
	{
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0)
	{
		u += MOD;
	}
	return u;
}
// 順列
ll permutation(const ll n, const ll m)
{
	ll result = 1;
	for (ll i = n; i > n - m; i--)
	{
		result = (result * i) % MOD;
	}
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x)
{
	if (x == 0)
		return 1;
	ll res = repeat_square(n, x / 2);
	res = res * res % MOD;
	if ((x % 2) == 1)
		res = res * n % MOD;
	return res;
}
// 組み合わせ nCm
ll combination(ll n, ll m)
{
	ll p = permutation(n, m);
	ll div = 1;
	for (ll i = 2; i <= m; i++)
	{
		div = (div * i) % MOD;
	}
	return (p * modinv(div)) % MOD;
}

int main() {
	int N;
	cin >> N;
	vector<int> p(N, 0);
	rep(i, N) cin >> p[i];

	int ans = 0;
	int temp;
	if (p[0] == 1) {
		temp = p[0];
		p[0] = p[1];
		p[1] = temp;
		ans++;
	}

	if (p[N-1] == N) {
		temp = p[N-1];
		p[N-1] = p[N-2];
		p[N-2] = temp;
		ans++;
	}

	rep (i, 1, N-1) {
		if (i+1 != p[i]) continue;

		if (p[i+1] != i+1) {
			temp = p[i];
			p[i] = p[i+1];
			p[i+1] = temp;
			ans++;
			
		} else if (p[i-1] != i+1) {
			temp = p[i];
			p[i] = p[i-1];
			p[i-1] = temp;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
import math

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

ans = 0.0
for n in range(1, N + 1):
  i = 0
  if n < K:
    i = math.ceil(math.log2(K / n))
  ans += (0.5 ** i) / N

print("{:.15f}".format(ans))

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

int main(){
  int N;
  cin >> N;
  bool ans = false;
  for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= 9; j++){
      if(i*j == N) ans = true;
    }
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, A: int):
    print(YES if N % 500 <= A else NO)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    solve(N, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
s =input()
t =input()

ss = sorted(s)
tt = sorted(t)

sl = len(ss)
tl = len(tt)

ttr = list(reversed(tt))

if sl >= tl:
    for i in range(tl):
        if ss[i] < ttr[i]:
            print("Yes")
            exit()
        elif ss[i] > ttr[i]:
            print("No")
            exit()
    print("No")
    exit()
    
elif sl < tl:
    for i in range(sl):
        if ss[i] < ttr[i]:
            print("Yes")
            exit()
        elif ss[i] > ttr [i]:
            print("No")
            exit()
    print("Yes")
    exit()

Measured memory_bytes: 3064
#B問題
R,G,B,N=map(int,input().split())
count=0
nr=int(N/R)
for i in range(nr+1):
    N1=N-i*R
    ng=int(N1/G)
    for j in range(ng+1):
        N2=N1-j*G
        if N2%B==0:
            count+=1
print(count)

Measured memory_bytes: 2940
#include <stdio.h>
 
int main (void)
{
int n,m;
int   s=0,i;
scanf("%d",&n);
m = n;
i = 0;
do
{
s += m%10;
m=m/10;
i ++;
}while(i<10);
 
if(n%s == 0)
printf("Yes");
else
printf("No");
 
return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int n;
    cin >> n;
    if(bitset<32>(n).count() == 1){
        cout << "No" << endl;
        return 0;
    }

    vector<pair<int, int> > ans;
    ans.push_back(make_pair(1+n, 2+n));
    for(int a=2; a<n; a+=2){
        int b = a + 1;
        ans.push_back(make_pair(1, a));
        ans.push_back(make_pair(1, b));
        ans.push_back(make_pair(a, b+n));
        ans.push_back(make_pair(b, a+n));
    }
    if(n % 2 == 0){
        int a = 2;
        while((n & a) == 0)
            a <<= 1;
        int b = n ^ a ^ 1;
        ans.push_back(make_pair(a, n));
        ans.push_back(make_pair(b, n+n));
    }

    cout << "Yes" << endl;
    for(const auto& p : ans)
        cout << p.first << ' ' << p.second << endl;

    return 0;
}


Measured memory_bytes: 3952
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
#define ck(a,b) (0<=(a)&&(a)<(b))

using namespace std;
//O(n^2*m)
int main(){
	int n;
	while(cin>>n,n){
		int maxs=0;
		string s[51];
		REP(i,0,n) {
			string tmps;
			cin>>tmps;
			s[i]+=tmps[0];
			REP(j,1,(int)tmps.size()){
				char c=tmps[j-1];
				if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
					s[i]+=tmps[j];
				}
			}
			maxs=max(maxs,(int)s[i].size());
		}

		REP(k,0,maxs+1){
			bool flag=false;
			REP(i,0,n) REP(j,i+1,n){
				string s1,s2;
				if((int)s[i].size()<=k) s1=s[i];
				else s1=s[i].substr(0,k);
				if((int)s[j].size()<=k) s2=s[j];
				else s2=s[j].substr(0,k);
				if(s1==s2) flag=true;
			}
			if(!flag){
				p(k);
				break;
			}
			if(flag&&k==maxs)	p(-1);
		}
	}
	return 0;
}

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

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

	int ans = 2*n;
	if(n%2 == 0) ans = n;
	cout << ans << endl;
	return 0;

}




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

int main(){
  int n,m;
  cin>>n>>m;
  int a[m];
  rep(i,m) cin>>a[i];
  int sum=0;
  rep(i,m) sum=sum+a[i];
  if(n-sum<0) cout<<-1<<endl;
  if(n-sum>=0) cout<<n-sum<<endl;
}

Measured memory_bytes: 3648
#!/usr/local/bin/ruby
a=0
sum=0
while line=gets
   d=line.to_i
   for i in 0..(600-2*d)/d
      a=a+d
      sum+=a*a
   end
   ans=sum*d
   puts "#{ans}"
   a,ans,sum=0,0,0
end

Measured memory_bytes: 6092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll a[N], b[N], c[N];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		c[i] = k + 3 * n - 1 - i;
		if (2 * i < n) {
			a[i] = k + n / 2 + i;
			b[i] = k + 2 * n - 1 - 2 * i;
		} else {
			int p = (2 * i - n) / 2;
			a[i] = k + p;
			b[i] = k + 2 * n - 2 - 2 * p;
		}
		if (a[i] + b[i] > c[i])
			return cout << "-1", 0;
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << " " << b[i] << " " << c[i] << "\n";
	}
	return 0;
}

Measured memory_bytes: 4608
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static readonly Dictionary<char, string> dic1 = new Dictionary<char, string>()
        {
            {'A',"00000" }, {'B',"00001" }, {'C',"00010" }, {'D',"00011" },
            {'E',"00100" }, {'F',"00101" }, {'G',"00110" }, {'H',"00111" },
            {'I',"01000" }, {'J',"01001" }, {'K',"01010" }, {'L',"01011" },
            {'M',"01100" }, {'N',"01101" }, {'O',"01110" }, {'P',"01111" },
            {'Q',"10000" }, {'R',"10001" }, {'S',"10010" }, {'T',"10011" },
            {'U',"10100" }, {'V',"10101" }, {'W',"10110" }, {'X',"10111" },
            {'Y',"11000" }, {'Z',"11001" }, {' ',"11010" }, {'.',"11011" },
            {',',"11100" }, {'-',"11101" }, {'\'',"11110" }, {'?',"11111" }
        };

        static readonly Dictionary<string, char> dic2 = new Dictionary<string, char>()
        {
            {"101"      ,' ' }, {"000000"   ,'\'' },
            {"000011"   ,',' }, {"10010001" ,'-' },
            {"010001"   ,'.' }, {"000001"   ,'?' },
            {"100101"   ,'A' }, {"10011010" ,'B' },
            {"0101"     ,'C' }, {"0001"     ,'D' },
            {"110"      ,'E' }, {"01001"    ,'F' },
            {"10011011" ,'G' }, {"010000"   ,'H' },
            {"0111"     ,'I' }, {"10011000" ,'J' },
            {"0110"     ,'K' }, {"00100"    ,'L' },
            {"10011001" ,'M' }, {"10011110" ,'N' },
            {"00101"    ,'O' }, {"111"      ,'P' },
            {"10011111" ,'Q' }, {"1000"     ,'R' },
            {"00110"    ,'S' }, {"00111"    ,'T' },
            {"10011100" ,'U' }, {"10011101" ,'V' },
            {"000010"   ,'W' }, {"10010010" ,'X' },
            {"10010011" ,'Y' }, {"10010000" ,'Z' }
        };

        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            string input;

            while ((input = Console.ReadLine()) != null)
            {
                string nums = "";

                for (int i = 0; i < input.Length; i++)
                {
                    nums += dic1[input[i]];
                }

                bool flg = true;
                string res = "";

                while (flg)
                {
                    flg = false;

                    for (int i = 3; i <= 8; i++)
                    {
                        if (nums.Length < i) break;

                        string sub = nums.Substring(0, i);

                        if (dic2.ContainsKey(sub))
                        {
                            res += dic2[sub];
                            nums = nums.Substring(i);
                            flg = true;
                            break;
                        }
                    }
                }
                sb.AppendLine(res);
            }
            Console.Write(sb);
        }
    }
}

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

int main(){
  string s,t;
  int slen,tlen;
  cin>>s>>t;
  slen=s.size();
  tlen=t.size();
  for(int i=0;i<=slen-tlen;i++)
    if(s.substr(i,tlen)==t)cout<<i<<endl;
  return 0;
}

Measured memory_bytes: 1196
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/atcoder-stl
from libcpp cimport bool
cdef extern from "<atcoder/dsu>" namespace "atcoder" nogil:
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
from cython.parallel cimport prange
from libc.stdio cimport getchar, putchar
cdef inline int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int i
cdef dsu *d = new dsu(read())
for i in prange(read(), nogil=1):
    if read():
        if d.same(read(), read()): putchar(49)
        else: putchar(48)
        putchar(10)
    else: d.merge(read(), read())
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Measured memory_bytes: 10656
N=int(input())
li=[]
import collections

for i in range(N):
    S=input()
    li.append(S)

li.sort()

c=collections.Counter(li)
cl=c.values()
m=max(cl)
keys=[k for k,v in c.items() if v==m]
keys.sort()

for j in range(len(keys)):
    print(keys[j])
    


Measured memory_bytes: 35584
n=int(input())
a=list(map(int,input().split()))
x=0
t=0
while x==0:
    for i in range(n):
        if a[i]%2==0:
            a[i]/=2
        else:
            print(t)
            x=1
            exit()
    t+=1
print(t)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  ll n, m, x, ans = INF;
  cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll>> a(n,vector<ll>(m));
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }

  for (int bit = 0; bit < (1 << n); bit++){
    ll cost = 0;
    vector<ll> rec(m,0);
    rep(i,n){
      if(bit & (1<<i)){
        cost += c[i];
        rep(j, m) rec[j] += a[i][j];
      }
      bool f = true;
      rep(i,m){
        if (rec[i] < x) f = false;
      }
      if (f) chmin(ans, cost);
    }
  }
  if (ans == INF) puts("-1");
  else cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>

int main(void)
{
  int a,b,c,ans;
  
  scanf("%d %d %d",&a,&b,&c);
  
  if(a < b)
    if(b < c)
      ans = (a + b + 10*c);
    else
      ans = (a + 10*b + c);
  else
    if(a < c)
      ans = (a + b + 10*c);
    else
      ans = (10*a + b + c);
  
  printf("%d\n",ans);
  
  return(0);
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int n = Integer.parseInt(line);
        int[] num = new int[n];
        for(int i = 0; i< n; i++) {
            String line1 = sc.nextLine();
            num[i] = Integer.parseInt(line1);
        }
        int min = num[0];
        int max = num[1] - num[0];
        for(int i = 1; i < n; i++) {
            if(num[i] - min > max) {
                max = num[i] - min;
            }
            if(num[i] < min) {
                min = num[i];
            }
            
        }
        System.out.println(max);
            
    }
 }
 


Measured memory_bytes: 170620
import java.util.*
import kotlin.collections.ArrayDeque
import kotlin.collections.HashMap

fun main(args: Array<String>){

//    var (H, W) = readLine()!!.split(" ").map{it.toInt()}
    var S = readLine()!!.toCharArray()
    var T = readLine()!!.toCharArray()
    var ans = "Yes"
    var transMapS = HashMap<Char,Char>()
    var transMapT = HashMap<Char,Char>()

    for(i in S.indices){
        if(transMapS.containsKey(S[i])){
            if(transMapS.get(S[i]) != T[i]){
                ans = "No"
                break
            }
        } else {
            transMapS.set(S[i],T[i])
        }

    }

    for(i in T.indices){
        if(transMapT.containsKey(T[i])){
            if(transMapT.get(T[i]) != S[i]){
                ans = "No"
                break
            }
        } else {
            transMapT.set(T[i],S[i])
        }

    }
    println(ans)




}

Measured memory_bytes: 41832
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
        int a, b, c;

        cin >> a;
        cin >> b;
        cin >> c;

        int res = b / a;
        if (res > c)
                res = c;

        cout << res << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		double m = scan.nextDouble();

		double[] a = new double[n];

		int i;
		double sum = 0;
		for(i = 0; i < n; i++) {
			a[i] = scan.nextDouble();
			sum += a[i];
		}
		double temp = sum * (1 / (4 * m));
		int cnt = 0;
		for(i = 0; i < n; i++) {
			if(a[i] >= temp)
				cnt++;
		}

		if(cnt >= m) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 22740
n = int(input())
a = list(map(int, input().split()))
N = [0] * (n+1)
for i in range(1, n+1):
    N[i] += N[i-1] + a[i-1]

Max = N[-1]
ans = float("INF")
for i in range(1, n):
    if abs(N[i] - (Max-N[i])) < ans:
        ans =  abs(N[i] - (Max-N[i]))
print(ans)

Measured memory_bytes: 24832
#include <cstdio>

const long long mod = 1000000007L;

int main() {
  int n;
  scanf("%d", &n);
  long long p10 = 1, p9 = 1, p8 = 1;
  for (int i = 0; i < n; ++i) {
    p10 = (p10 * 10) % mod;
    p9 = (p9 * 9) % mod;
    p8 = (p8 * 8) % mod;
  }
  long long res = ((p10 - p9 - p9 + p8) % mod + mod) % mod;
  printf("%lld\n", res);
  return 0;
}


Measured memory_bytes: 1732
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])


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

const int MN = 1e5 + 5;
int H[MN];
int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &H[i]);
	H[N + 1] = 1e9 + 100;
	bool can = true;
	for (int i = N; i >= 1; i--)
	{
		if (H[i] > H[i + 1]) H[i]--;
		if (H[i] > H[i + 1])
		{
			can = false;
			break;
		}
	}
	can ? puts("Yes") : puts("No");
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int a[3] = {0};
    cin >> a[0] >> a[1] >> a[2];
    
    sort(a, a+3);
    
    if(a[0] == 5 && a[1] == 5 && a[2] == 7)
    	cout << "YES";
    else
    	cout << "NO";

	return 0;
}

Measured memory_bytes: 256