akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>

using namespace std;

int N, K;
char D[10];
string str;

int main(){
	cin >> N >> K;
	for(int i = 0; i < K; i++){
		cin >> D[i];
	}
	
	int x;
	int ans;
	int flg = 0;
	while(1){
		str = to_string(N);
		for(int i = 0; i < K; i++){
			x = (int)str.find(D[i]);
			if(x != -1) flg++;
		}
		if(flg == 0) break;
		N++;
		flg = 0;
	}

	cout << N << endl;

	return 0;

}


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

using namespace std;
char a[50][50];
int c,d,b[55][55];
int main(){
    cin>>c>>d;
    for(int i=0;i<c;i++)
    cin>>a[i];
    for(int i=0;i<c;i++)
    for(int j=0;j<d;j++)
    if(a[i][j]=='#')
    b[i][j]++,b[i][j+1]++,b[i][j+2]++,
    b[i+1][j]++,b[i+1][j+1]++,b[i+1][j+2]++,
    b[i+2][j]++,b[i+2][j+1]++,b[i+2][j+2]++;
    for(int i=0;i<c;i++){
        for(int j=0;j<d;j++)
        if(a[i][j]=='#') cout<<'#';
        else cout<<b[i+1][j+1];
        cout<<endl;
    }

}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<string>
#include<iostream>

using namespace std;

int main()
{
	string key;
	int page;
	map< string,set<int> > dic;

	while(cin>>key>>page)	dic[key].insert(page);

	map< string,set<int> >::iterator it_dic;
	for(it_dic=dic.begin();it_dic!=dic.end();it_dic++){
		cout<<it_dic->first<<endl;
		set<int>::iterator it;
		for(it=it_dic->second.begin();it!=it_dic->second.end();it++){
			if(it!=it_dic->second.begin())	cout<<" ";
			cout<<*it;
		}
		cout<<endl;
	}

	return 0;
}

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

List = list(list(map(int, input().split())) for i in range(N))

# print(List)

List.sort(key = lambda x:x[1])

# print(List)

S = 0
for j in range(N):
    S += List[j][0]
    if(S > List[j][1]):
        print('No')
        break
else:
    print('Yes')



Measured memory_bytes: 53728
#include <bits/stdc++.h>
/* Uncomment only if you are not using GNU compiler->
*/
#include <map>
#include <algorithm> 
#include <vector> 
#include <string.h> 
#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <chrono> 
#include <thread> 
#include <iomanip>
#include <typeinfo>
/**/ 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define all(v)  v.begin(), v.end()

//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const long long MOD = 1000000007;
const long long inf = 1e18;
 
using namespace std;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

ll power(ll x, ll n)
{
    ll res=1;
    while(n>0){
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}

bool custom_sort(int &x, int &y)
{
    if(x<y)
        return 1;
    else
        return 0;
}

void always_ignore_function_name()
{
    int n;
    cin>>n;
    n%=1000;
    n=1000-n;
    n%=1000;
    cout<<n<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1, tt=1;
    // cin>>t;
    while(tt<=t)
    {
        // cout<<"Case #"<<tt<<": ";
        always_ignore_function_name();
        tt++;
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


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

using namespace std;

int main()
{
    int n, x = 1;
    deque<int> d;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if(i == 0) d.push_back(tmp);
        else if(x)
        {
            d.push_back(tmp);
            x = !x;
        }
        else
        {
            d.push_front(tmp);
            x = !x;
        }
    }
    if(n & 1)
    {
        cout << d[0];
        for(int i = 1; i < n; i++)
            cout << " " << d[i];
    }
    else
    {
        cout << d[n-1];
        for(int i = n-2; i >= 0; i--)
            cout << " " << d[i];
    }
    return 0;
}


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

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

using ll=long long;
const int Hmax=1010;
const int Wmax=1010;
ll H,W;
char g[Hmax][Wmax];
ll dp[Hmax][Wmax];
const ll INF=1LL<<60;
const ll MOD=1000000007;


int main(){
  cin >> H >> W;
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      cin >> g[i][j];
    }
  }
  dp[0][0]=1;
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      if(g[i][j]=='.'){
        dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
        dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
      }
    }
  }
   cout << dp[H-1][W-1] << endl;   
      
  
}

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

using namespace std;

struct UniTree {
    int n;
    int *par, *depth;

    UniTree(int n) {
        par = new int[n], depth = new int[n];

        for(int i = 0; i < n; i++) {
            par[i] = i;
            depth[i] = 0;
        }
    }

    int root(int x) {
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void link(int x, int y) {
        x = root(x);
        y = root(y);

        if(par[x] == par[y]) return;
        if(depth[x] < depth[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if(depth[x] == depth[y]) depth[x]++;
        }
    }
};

int main() {
    int n, k, l;
    cin >> n >> k >> l;

    UniTree road(n), train(n);
    for(int i = 0; i < k; i++) {
        int p, q;
        cin >> p >> q;
        road.link(p - 1, q - 1);
    }
    for(int i = 0; i < l; i++) {
        int r, s;
        cin >> r >> s;
        train.link(r - 1, s - 1);
    }

    map<pair<int, int>, int> m;
    for(int i = 0; i < n; i++) {
        pair<int, int> tmp(road.root(i), train.root(i));
        int tp = m[tmp];
        m[tmp] = tp + 1;
    }

    for(int i = 0; i < n; i++) {
        if(i != 0) cout << " ";
        pair<int, int> tmp(road.root(i), train.root(i));
        cout << m[tmp];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 15104
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

VI g[55];
int m[55];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, x, d;
  cin >> n >> x >> d;
  cin >> m[0];
  FOR(i, 1, n) {
    int p;
    cin >> m[i] >> p;
    g[p-1].PB(i);
  }

  // 頂点iの部分木を取ったときのコストXと価値Yを求める
  VI X(n), Y(n);
  function<void(int)> dfs = [&](int v) {
    X[v] = m[v], Y[v] = 1;
    for(int i: g[v]) {
      dfs(i);
      X[v] += X[i];
      Y[v] += Y[i];
    }
  };
  dfs(0);

  VI idx(n);
  REP(i, n) idx[i] = i;
  // Y[x]/X[x] >= Y[y]/X[y] ⇔ Y[x]*X[y] >= Y[y]*X[x] でソート
  sort(ALL(idx), [&](int x, int y){return Y[x]*X[y]>Y[y]*X[x];});

  // dp[i] = (価値がiのときの最小の重さ)
  VI dp(50*50*50+5, INF);
  // i番目のアイテムについて重さと価値がそれぞれ(X[i],Y[i])(2X[i],Y[i])…(2^kX[i],2^kY[i])が一つずつ存在すると考える
  dp[0] = 0;
  REP(i, n) {
    int num = idx[i]?min(50LL,d):50;
    for(int k=1; num; k<<=1) {
      int mul = min(k, num);
      for(int j=50*50*50; j>=0; --j) {
        if(j+mul*Y[idx[i]] <= 50*50*50) {
          chmin(dp[j+mul*Y[idx[i]]], dp[j] + mul*X[idx[i]]);
        }
      }
      num -= mul;
    }
  }
  // cout << dp << endl;

  int ans = 0;
  REP(i, 50*50*50+1) {
    // iグラム使ったとして残りをgreedyに決める
    if(dp[i]>x) continue;
    int ret=i, w = x-dp[i];
    REP(j, n) {
      // cnt個取る
      int cnt = idx[j]?max(0LL, d-50):INF;
      chmin(cnt, w/X[idx[j]]);
      ret += cnt*Y[idx[j]];
      w -= cnt*X[idx[j]];
    }
    // cout << i << " " << ret << endl;
    chmax(ans, ret);
  }
  cout << ans << endl;

  return 0;
}


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

long long m_min(long long t[], long long K)
{
	long long m = INT_MAX;
	for(long long i=0; i<K; i++)
		if(t[i] < m)
			m = t[i];
	return m;
}

int main()
{
	long long N, K;
	long long temp;
	cin>>N>>K;
	long long arr[N];
	long long dp[N];
	dp[0] = 0;

	for(long long i=0; i<N; i++)
		cin>>arr[i];

	for(long long i=1; i<N; i++)
	{
		if(i<K)
			temp = i+1;
		else
			temp = K+1;
		long long t[temp-1];
		for(long long j=1; j<temp; j++)
		{
			t[j-1] = dp[i-j]+abs(arr[i]-arr[i-j]);
		}
		dp[i] = m_min(t, temp-1);
	}
	cout<<dp[N-1];
}

Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll mod = 1000000007;
const double pi = 3.14159265358979;

int main() {
    str S;
    cin >> S;
    bool ans = false;
    rep(i, S.size() - 1) {
        if(S[i] == 'A') {
            if (S[i + 1] == 'C') {
                ans = true;
            }
        }
    }
    if(ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n;
    double xmx,xmn,ymx,ymn,r1,r2,l1,l2,u1,u2,d1,d2;
    xmn = ymn = r1 = l1 = u1 = d1 = 1e9;
    xmx = ymx = r2 = l2 = u2 = d2 = -1e9;
    cin >> n;
    for (int i = 0;i < n;++i) {
        double x,y;
        char d;
        cin >> x >> y >> d;
        if (d == 'R') {
            r1 = min(r1,x);
            r2 = max(r2,x);
            ymn = min(ymn,y);
            ymx = max(ymx,y);
        } else if (d == 'L') {
            l1 = min(l1,x);
            l2 = max(l2,x);
            ymn = min(ymn,y);
            ymx = max(ymx,y);
        } else if (d == 'U') {
            u1 = min(u1,y);
            u2 = max(u2,y);
            xmn = min(xmn,x);
            xmx = max(xmx,x);
        } else {
            d1 = min(d1,y);
            d2 = max(d2,y);
            xmn = min(xmn,x);
            xmx = max(xmx,x);
        }
    }
    double ans = 1e17;
    for (double j = 0;j < 400000001;j++) {
        double i = 0.5*j;
        ans = min(ans,(max({xmx,r2+i,l2-i})-min({xmn,r1+i,l1-i}))*(max({ymx,u2+i,d2-i})-min({ymn,u1+i,d1-i})));
    }
    cout << fixed << setprecision(12) <<ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<string>
 
const int MAX_N=1<<17;
 
using namespace std;
 
int n,bit[MAX_N+1];
 
int sum(int i){
  int s=0;
  while(i>0){
    s+=bit[i];
    i-=i&-i;
  }
  return s;
}
 
void add(int i,int x){
  while(i<=n){
    bit[i]+=x;
    i+=i&-i;
  }
}
 
int main(void){
 
  int q,com,a,b;
 
  cin >> n >> q;
  n++;
  while(q--){
    cin >> com >> a >> b;
    if(com)cout << sum(b+1)-sum(a) << endl;
    else add(a+1,b);
  }
 
  return 0;
}


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

int main(){
  long n;
  cin >> n;
  long ans = 0, nn = n;
  for(long i=2;i<=sqrt(nn);i++){
    if(n%i!=0) continue;
    long tmp = 0;
    while(n%i==0){
      tmp++;
      n /= i;
    }
    long num = 1;
    while(1){
      if((num*(num+1))/2 <= tmp) num++;
      else break;
    }
    ans += num-1;
  }
  if(n!=1)ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long int
#define endl "\n"
using namespace std;
void solve()
{
	//Enter your code here Tanmay:)
	//int n;
	string s;
	cin>>s;
	int a=0,b=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='A')
			a++;
		else
			b++;
	}
	if(a==0||b==0)
		cout<<"No";
	else
		cout<<"Yes";
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}
/*
int eulortotent(int n)
     {
    //Enter your code here Tanmay:)
    int total=n;
        for(int p=2;p*p<=n;p++)
        {
            if (n%p==0)
        {
            total /= p;
            total *= (p-1);
            while ( n % p == 0 ) 
                n /= p;
        }
    }

    if(n>1)
    {
        total/=n;
        total*=(n-1);
    }

  return total;
}
*/

Measured memory_bytes: 256
n=int(input())
a=[]
for i in range(n):
  a_=list(map(int,input().split()))
  a.append(a_)
  
dp=[[0]*3 for i in range(n)]
dp[0]=a[0]
for i in range(1,n):
  for k in range(3):
    
    for j in range(3):
      
      if k!=j:
        dp[i][k]=max(dp[i][k], dp[i-1][j] + a[i][k])
#print(dp)        
print(max(dp[n-1]))

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

#define int long long
#define double long double

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

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

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

const int INF = 1e16;
const int MOD = 1e9+7;

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


signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N, K; cin >> N >> K;
    int n = N/K;
    cout << min(N-n*K, K-(N-n*K)) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

struct CountUnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;
    vector<int> cnt;

    CountUnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        cnt.assign(sz, 1);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else    return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)  return;
        if(rank[x] < rank[y]){
            par[x] = y;
            cnt[y] += cnt[x];
        }
        else{
            par[y] = x;
            cnt[x] += cnt[y];
            if(rank[x] == rank[y])  ++rank[x];
        }
    }

    int get_cnt(int x){
        return cnt[find(x)];
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i];
        --a[i], --b[i];
    }
    CountUnionFind uf(n);
    vector<ll> ans(m);
    ans[m - 1] = (ll)n * (n - 1) / 2;
    for(int i = m - 1; i > 0; --i){
        if(uf.same(a[i], b[i])){
            ans[i - 1] = ans[i];
            continue;
        }
        ans[i - 1] = ans[i] - (ll)uf.get_cnt(a[i]) * uf.get_cnt(b[i]);
        uf.unite(a[i], b[i]);
    }
    for(int i = 0; i < m; ++i)  cout << ans[i] << "\n";
}

Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int N = sc.nextInt();
            int D = sc.nextInt();
            int X = sc.nextInt();
            int sum = 0;
            for (int i = 0; i < N; i++) {
                sum += (D - 1) / sc.nextInt() + 1;
            }
            System.out.println(sum + X);
        }
    }
}


Measured memory_bytes: 25684
def f(n):
    if n & 1:
        return 3 * n + 1
    else:
        return n//2

p = int(input())
t = {p}
m = 1
while True:
    m += 1
    p = f(p)
    if p in t:
        break
    t.add(p)
print(m)

Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<ios>
#include<string>
#include<map>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>

using namespace std;


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

	cout << s[0] << s.size()-2 << s[s.size() - 1] << endl;

	return 0;
}

Measured memory_bytes: 256
Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r+1):
    if is_sosu[i]:
        for j in range(i*i, max_r+1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if is_sosu[i] and is_sosu[(i+1)//2]:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i]-1])


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

int main() {
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	vector<ll> p(a), q(b), r(c);
	rep(i, a) cin >> p[i];
	rep(i, b) cin >> q[i];
	rep(i, c) cin >> r[i];
	sort(p.rbegin(), p.rend());
	sort(q.rbegin(), q.rend());
	sort(r.rbegin(), r.rend());
	vector<ll> res;
	rep(i, x) res.emplace_back(p[i]);
	rep(i, y) res.emplace_back(q[i]);
	rep(i, c) res.emplace_back(r[i]);
	sort(res.rbegin(), res.rend());
	ll ans = 0;
	rep(i, x + y) ans += res[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8688
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m, b[102] = {}, c[102] = {};
    string s[102] = {};
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (s[i][j] == '#') b[i] = c[j] = 1;
    for (int i = 0; i < n; i++) if (b[i]) {
        for (int j = 0; j < m; j++) if (c[j]) cout << s[i][j];
        cout << '\n';
    }
}


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

int main() {
  int N, K;
  cin >> N >> K;
  int screen = 1, tmp = 1;
  rep(i, N){
    screen *= 2;
    if(screen > K){
      break;
    }
    tmp += 1;
  }
  rep(i,N-tmp){
    screen += K;
  }
  cout << screen << endl;
}


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

int main(void){
  string s,t; cin>>s>>t;
  if( s.length() < t.length()){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  // S'文字列に既にtが含まれていない場合
  for( int i=(s.length()-t.length()); i>=0; --i){
    bool is_restorable = true;
    for( int j=0; j<t.length(); ++j){
      if( s[i+j] != '?' && s[i+j] != t[j]){
        is_restorable = false;
        break;
      }
    }
    if( is_restorable ){
      for( int j=0; j<t.length(); ++j){
        s[i+j] = t[j];
      }
      replace(s.begin(), s.end(), '?', 'a');
      cout << s << endl;
      return 0;
    }
  }
  cout << "UNRESTORABLE" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void selectionSort(int[],int);

int main(){
  int N,i;
  int A[100];

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  selectionSort(A,N);
  return 0;
}

void selectionSort(int A[],int N){
  int i,min,j,a,count=0;

  for(i=0;i<N-1;i++){
    min = i;
    for(j=i;j<N;j++){
      if(A[j]<A[min])min = j;
    }
    a = A[i];
    A[i] = A[min];
    A[min] = a;
    
    if(i!=min)count++;
  }

  for(i=0;i<N;i++){
    if(i>0)printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
  printf("%d\n",count);
}



Measured memory_bytes: 2140
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
void update(int& x, int y) { if(x < y) x = y; }

int main(){
  int T;
  cin >> T;
  while(T --){
    int L; cin >> L;
    vector<int> A(L);
    REP(i, L) cin >> A[i];
    int dp[100][400] = {}; // 0からiまでのEa鎖で、i - 1が+kのとき、iが取れる増加値の最大
    REP(i, L)REP(j, 400) dp[i][j] = -INF;
    dp[0][0] = A[0]; // L = 1の例外
    dp[1][A[0]] = A[1]; //初期値
    // (現在のEa鎖のindex, 一つ前の基の値, 現在の基の値) = (i, j, k)
    // (i, j, k) -> (i + 1, k, A[i + 1]) (伝播しない)
    //           -> (i + 1, k - 1, j + A[i + 1]) (伝播した)
    for(int i = 1; i + 1 < L; i++){
      for(int j = 0; j <= 4 * i; j++){
        if(dp[i][j] >= 0) update(dp[i + 1][dp[i][j]], A[i + 1]);
        if(dp[i][j] >= 1) update(dp[i + 1][dp[i][j] - 1], j + A[i + 1]);
      }
    }
    int ans = 0;
    for(int i = 0; i < 4 * L; i++) update(ans, dp[L - 1][i]);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1356
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1000000;
// clang-format on
int N;

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

  ll power = 1;
  for (ll i = 1; i <= N; i++) {
    power = (power * i) % (ll)MOD;
  }
  cout << power << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;
int main(int argc, char const *argv[]) {
  vll a(5, 0);
  ll x, y;
  re(i, 3){
    std::cin >> x >> y;
    a[x]++, a[y]++;
  }
  ll r = 0, l = 100000;
  rep(i, 1, 5){
    r = max(r, a[i]);
    l = min(l, a[i]);
  }
  if(r==2&&l==1) std::cout << "YES" << '\n';
  else std::cout << "NO" << '\n';
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
class Program
{       
    public void Slove()
    {
        var inputs = Console.ReadLine().Split();
        int n = int.Parse(inputs[0]);
        long shiftCost = long.Parse(inputs[1]);
        long[] costs = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long minSum = costs.Sum();
        foreach(int i in Enumerable.Range(1, n))
        {
            long temp = costs[n - 1];
            foreach(int j in Enumerable.Range(1, n - 1).Reverse())
            {
                costs[j] = Math.Min(costs[j], costs[j - 1]);
            }
            costs[0] = Math.Min(costs[0], temp);
            minSum = Math.Min(minSum, costs.Sum() + shiftCost * i);
        }
        System.Console.WriteLine(minSum);
    }
    
    static void Main(string[] args)
    {
        new Program().Slove();
    }
}


Measured memory_bytes: 42960
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n;
  cin >> n;
  vi x(n);
  REP(i, n) { cin >> x[i]; }
  int ans = 100 * 100 * 100 + 1;
  FOR(i, 1, 101) {
    int tmp = 0;
    REP(j, n) { tmp += (i - x[j]) * (i - x[j]); }
    ans = min(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}


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


int main()
{
  string s, t;
  cin >> s >> t;
  vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
  rep(i, s.size())
    rep(j, t.size())
      if (s[i] == t[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 i = s.size(), j = t.size();
  string ans;
  while (dp[i][j] > 0)
  {
    if (dp[i][j] == dp[i-1][j])
      i--;
    else if (dp[i][j] == dp[i][j-1])
      j--;
    else
    {
      ans += s[i-1];
      i--;
      j--;
    }
  }
  for (int k = ans.size() - 1; k >= 0; k--)
    printf("%c", ans[k]);
  puts("");
  return 0;
}

Measured memory_bytes: 35584
//cf gay
#include<bits/stdc++.h>
using namespace std;
#define g(a,b,c) for(int a=b;a<c;a++)
#define ff(a,b,c) for(int a=c;a>b;a--)
#define ffk(a,b,c) for(int a=b;a<=c;a++)
#define fff(a,b,c) for(int a=c;a>=b;a--)
int main (){
	string s;
	int dem=0,dem2=0,dem3=0;
	for(int i=1;i<=4;i++){
		cin>>s[i];
	}
	for(int i=1;i<=4;i++){
	  for(int j=i+1;j<=4;j++){
	  	if(s[i]==s[j]){
	  		dem++;
		  }
	  }
	}
	if(dem==2){
		cout<<"Yes";
	}
	else {
		cout<<"No";
	}
/*	if(dem==4){
		cout<<"Yes";
	}
	else {
		cout<<"No";
	}*/
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	
	public static int count(int[] sorted, int[] intSet) {
		
		int result = 0;
		int low = 0;
		int high = sorted.length;
		
		for(int i = 0; i < intSet.length; i++) {

			result = result + binary(sorted, intSet[i], low, high);
			
		}
		return result;
	}

	public static int binary(int[] ls, int num, int low, int high) {
		
		if(high >= low) {
			int mid = low + (high - low) / 2;

			if(ls[mid] == num) {
				return 1;
			}
			else if (ls[mid] > num) { 
				return binary(ls, num, low, mid - 1);
			}
			else { 
				return binary(ls, num, mid+1, high);
			}
		}
		else 
			return 0;
	}
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int numSorted = in.nextInt();
		int[] sorted = new int[numSorted];
		
		for(int i = 0; i < numSorted; i++) {

			sorted[i] = in.nextInt();

		}
		
		int setNum = in.nextInt(); 
		int[] intSet = new int[setNum];

		for(int j = 0; j < setNum; j++) {

			intSet[j] = in.nextInt();

		}

		int result = count(sorted, intSet);

		System.out.println(result);


		in.close();
		
	}

}



Measured memory_bytes: 69184
// 069-c
// 4で割れるもの(a)、4では割れないが2で割れるもの(b)、どちらでも割れないもの(c)を記録する
// b==0 && c-1≦a または　b>0 && c<=a なら可能


#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define ALL(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main(){
  ll N,A[100007],a=0,b=0,c=0;cin >> N;
  rep(i,N){
    cin >> A[i];
    if(A[i]%4==0){
      a++;
    }
    else if(A[i]%2==0){
      b++;
    }
    else{
      c++;
    }
  }
  if((b==0 && c-1<=a) || (b>0 && c<=a)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 1024
//Author: Fuadul Hasan(fuadul202@gmail.com)
//BSMRSTU,Gopalganj
#include<bits/stdc++.h>
using namespace std;int tc = 1;
#define happy ios::sync_with_stdio(false);
#define coding  cin.tie(0);
#define mp make_pair
#define ll long long
#define Pi atan(1)*4
#define pb  push_back
#define vpr vector<pr> 
#define pr pair<int, int> 
#define vi std::vector<int>
#define vll std::vector<ll>
#define YES printf("YES\n");
#define NO printf("NO\n");
#define Yes printf("Yes\n");
#define No printf("No\n");
#define all(n) n.begin(),n.end()
#define point(x) setprecision(x)
#define Test printf("Case %d: ",tc++);
#define Unique(c) (c).resize(unique(all(c))-(c).begin())

const int M = 1e9 + 7;
const ll  Inf = (ll)2e18 + 5;
const int N   = 2e5 + 5;
ll dp1[N],dp2[N],dp3[N];
int solve() 
{
	//happy coding

	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		dp1[i] = max(dp2[i-1]+a,dp3[i-1]+a);
		dp2[i] = max(dp1[i-1]+b,dp3[i-1]+b);
		dp3[i] = max(dp1[i-1]+c,dp2[i-1]+c);
	}
	int x = max(dp1[n],max(dp2[n],dp3[n]));
	cout<<x<<endl;
	return 0;
}
int main(){
	int test = 1;
	//scanf("%d", &test);
	while (test--)solve();return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
vector<int> h(n);
for(int i = 0; i < n; i++){
    cin >> h[i];
}
// we have the heights as a vector now.
// initially it is at standing at stone 1. h0.
vector<int> dp(n);
dp[0] = 0;
dp[1] = abs(h[1] - h[0]);
for(int i = 2; i < n; i++){
   dp[i] = min(dp[i-1]+ abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
}
cout << dp[n-1] << endl;
    return 0;

}













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

int main() {
  int N;
  cin >>N;
  int A[N];
  int count=0;
  for(int i=0;i<N;i++){
  int A_buff;
  int count_buff=0;
  int flag_continue=1;
    cin>>A_buff;
    if(A_buff%2==0){
      while(flag_continue){
        if(A_buff%2==0){
          count_buff++;
        }else{
        break;
        }
        A_buff/=2;
        flag_continue=A_buff;
      }
      if(count==0){
      count=count_buff;
      }else if(count>count_buff){
      count=count_buff;
      }
    }else{
      count=0;
      break;
    }
  }  
  cout<<count<<endl;
}



Measured memory_bytes: 256
input1 = list(map(str,input().split()))
input2 = list(map(int,input().split()))
input3 = input()

if input1.index(input3) == 0:
    print(input2[0] - 1, input2[1])
    
elif input1.index(input3) == 1:
    print(input2[0], input2[1] - 1)
    
else:
    print(input2[0],input2[1])

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String T = sc.next();
        
        if(T.substring(0, S.length()).equals(S)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35652
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//40min
int main(void){
  int n;
  int p[51];
  int t[51];
  int tmp;
  int i = 0, j = 0;

  scanf("%d", &n);

  for(int cnt = 1; cnt <= n; cnt++){
    scanf("%d", &p[cnt]);  
  }

  for(int cnt = 1; cnt <= n; cnt++){
    t[cnt] = p[cnt];
  }
  /*
  //昇順作る
  for(int a = 1; a <= n; a++){
    for(int b = a; b <= n; b++){
      if(t[a] > t[b]){
	tmp = t[a];
	t[a] = t[b];
	t[b] = tmp;
      }
    }
  }
  */
  for(int cnt = 1; cnt <= n; cnt++){
    //    printf("cnt = %d  p[cnt]=%d\n", cnt, p[cnt]);
    if(cnt != p[cnt]){
      if(i == 0){
	i = cnt;
      }else if(j == 0){
	j = cnt;
      }else{
       break;
      }
    }
  }

  if(i != 0 && j != 0){
    tmp = p[i];
    p[i] = p[j];
    p[j] = tmp;
  }
  
  // 昇順と同じこと確認する
  for(int cnt = 1; cnt <= n; cnt++){
    //    printf("cnt = %d  p[cnt]=%d\n", cnt, p[cnt]);
    if(cnt != p[cnt]){
      printf("NO\n");
      return 0;
    }
  }

  printf("YES\n");
  
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n,m;
    cin>>n>>m;
    ll x[n],y[m];
    for(int i=0;i<n;i++)cin>>x[i];
    for(int i=0;i<m;i++)cin>>y[i];
    ll xans=0,yans=0;
    for(ll i=0;i<n;i++){
        xans+=(2*i-n+1)*x[i];
        xans=(xans%MOD+MOD)%MOD;
    }
    for(ll i=0;i<m;i++){
        yans+=(2*i-m+1)*y[i];
        yans=(yans%MOD+MOD)%MOD;
    }
    cout<<(xans*yans)%MOD<<endl;
}


Measured memory_bytes: 1792
// template {{{

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

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

int cv[256];
int cv2[256];

int h, w;
int g[10][10];
int sx, sy, sdir;
int cnt;
string res;

bool dfs(int x, int y, int d)
{
	g[x][y] = 0;
	cnt--;
	if (cnt == 0) return true;
	rep(dir, 4){
		if (abs(dir - d) == 2) continue;
		for (int i = 1;; i++){
			int nx = x + dx[dir] * i;
			int ny = y + dy[dir] * i;
			if (nx < 0 || nx >= h || ny < 0 || ny >= w) break;
			if (g[nx][ny]){
				res += cv2[dir];
				if (dfs(nx, ny, dir)) return true;
				res.pb();
				break;
			}
		}
	}
	g[x][y] = 1;
	cnt++;
	return false;
}

int main()
{
	rep(i, 4) cv["ULDR"[i]] = i;
	rep(i, 4) cv2[i] = "ULDR"[i];

	cin >> h >> w;
	rep(i, h) rep(j, w){
		char c;
		cin >> c;
		if (c == 'o'){
			g[i][j] = 1;
			cnt++;
		}
		else if (c != '.'){
			sx = i;
			sy = j;
			sdir = cv[c];
			cnt++;
		}
	}
	
	if (dfs(sx, sy, sdir)) cout << res << endl;
	else assert(false);
}

Measured memory_bytes: 3224
#include<iostream>
using namespace std;
int main() {
	int n;
	int a[100005], b[100005], k = 0;
	long long int ans = 0;
	cin >> n;
	for (int i = 0; i < n + 1; i++) {
		cin >> a[i];
	}
	for (int j = 0; j < n; j++) {
		cin >> b[j];
	}
	//a[n + 1] = a[n + 2] = b[n] = b[n + 1] = 0;
	long long int hoge = 0;
	for (int j = 0; j < n; j++) {
		if (a[j] >= b[j]) {
			ans += b[j];
			//a[j] -= b[j];
			//b[j] -= b[j];
			continue;
		}
		else {
			ans += a[j];
			//b[j] -= a[j];
			//a[j] -= a[j];
		}
		hoge = b[j] - a[j];
		if (hoge > a[j + 1]) {
			ans += a[j + 1];
			//b[j] -= a[j + 1];
			a[j + 1] -= a[j + 1];
		}
		else {
			ans += hoge;
			a[j + 1] -= hoge;
			//b[j] -= hoge;
		}
		//cout << ans << endl;
	}

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

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

template<typename F> long long discrete_binary_search(long long ok, long long ng, F is_ok) {
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
}

int N, M, V, P;
int A[110000];
signed main() {
    cin >> N >> M >> V >> P;
    rep(i, N) { cin >> A[i]; }
    sort(A, A + N);
    int k = discrete_binary_search(N - P, -1, [&](int x) {
        int wari = 0;
        int ub = A[x] + M;
        rep(i, N - P + 1) {
            if (i == x) { continue; }
            if (A[i] > ub) { return false; }
            wari += min(ub - A[i], M);
        }
        return wari >= (V - P) * M;
    });
    cout << N - k << endl;
}


Measured memory_bytes: 1024
# -*- coding: utf-8

n, x = map(int, input().split())
a = list(map(int, input().split()))

count = max(0, a[0] - x)
a[0] = min(a[0], x)

for i in range(len(a) - 1):
    if a[i] + a[i + 1] > x:
        tmp_num = max(0, a[i] + a[i + 1] - x)
        count += tmp_num
        a[i + 1] -= tmp_num
print(count)

Measured memory_bytes: 14132
#include <stdio.h>

int main(){
    int dp[32];
    int i,n;

    while(1){
    scanf("%d",&n);
    if(n == 0){
        break;
    }
    
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for(i = 3; i <= n ; i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    }
    printf("%d\n",(dp[n]-1)/3650+1);
    }
    return 0;

}


Measured memory_bytes: 2036
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintStream out = new PrintStream(System.out);

        int N, T[], M, P[], X[], sum;

        sum = 0;
        N = sc.nextInt();
        T = new int[N];
        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();

            sum += T[i];
        }

        M = sc.nextInt();
        P = new int[M];
        X = new int[M];
        for (int i = 0; i < M; i++) {
            P[i] = sc.nextInt();
            X[i] = sc.nextInt();
        }
        
        for (int i = 0; i < M; i++) {
            out.println(sum - T[P[i]-1] + X[i]);
        }
        sc.close();
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, divisor, modinv, bitSearch, bitList, dfs, bfs//
//dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color, D; vll path;
//***********//
int main() {
	cin >> N;
	ll T, A;
	cin >> T >> A;
	vl H(N);
	A *=1000;
	T *= 1000;
	ll P = INF;
	for (i = 0; i < N; i++) {
		cin >> H[i];
		if (abs(A - (T - H[i] * 6)) < P) {
			ans = i + 1;
			P = abs(A - (T - H[i] * 6));
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define LL       long long
#define DS       pair<LL, LL>
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int a[N];

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int n, mx = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        mx = max(mx, a[i]);
    }
    sort(a, a + n);
    LL ans = 1e18;
    for (int i = 0; i <= mx; i++) {
        LL cost = 0;
        for (int j = 0; j < n; j++) {
            LL tmp = (a[j] - i);
            tmp *= tmp;
            cost += tmp;
        }
        ans = min(ans, cost);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/python
# coding: utf-8

from sys import stdin

# M * 1900 ms  正解確率 0.5
# (N - M) * 100 ms  正解確率 1.0
# 問: すべて正解するまで繰り返すときの実行時間の期待値

# 成功確率 0.5 ** M のベルヌーイ試行
# 成功するまでの試行回数 X は幾何分布に従う。
# P(X = n) = (1 - p) ** (n - 1) * p
# 期待値 E(X) = 1 / p

N, M = map(int, stdin.readline().split())

p = 0.5 ** M
time = M * 1900 + (N - M) * 100
print(int(time / p))


Measured memory_bytes: 2568
import java.util.Scanner;

//Al dente
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), T = sc.nextInt(), E = sc.nextInt();
		int[] a = new int[n+1];
		for(int i=1;i<=n;i++)a[i]=sc.nextInt();
		int res = -1;
		for(int i=1;i<=n&&res==-1;i++){
			int k = (T-E-1)/a[i]+1;
			if(T-E<=a[i]*k&&a[i]*k<=T+E)res=i;
		}
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
from bisect import bisect_left as bisect


def inpl():
    return list(map(int, input().split()))


n = int(input())
S = inpl()
q = int(input())
T = inpl()

S.sort()
S.append(10**11)

# print(S, bisect(S, T[0]))
print(sum(1 for t in T if S[bisect(S, t)] == t))



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

using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s, t;
        cin >> s >> t;
        int dp[1001][1001] = {};
        for (int j = 0; j < s.length(); ++j) {
            for (int k = 0; k < t.length(); ++k) {
                if (s[j] == t[k]) {
                    dp[j + 1][k + 1] = max(dp[j + 1][k + 1], dp[j][k] + 1);
                }
                dp[j+1][k+1] = max(dp[j+1][k+1], dp[j+1][k]);
                dp[j+1][k+1] = max(dp[j+1][k+1], dp[j][k+1]);
            }
        }
        cout << dp[s.length()][t.length()] << endl;

    }
    return 0;
}


Measured memory_bytes: 7132
#include <iostream>
#include <cstring>

using namespace std;

const long long int mod = (int)1e9 + 7;
string S;
long long int dp[(int)1e5 + 10][4] = {};

void add(long long int &a, long long int b) {
    a += b;
    if (a >= mod) a -= mod;
}

int main() {
    cin >> S;
    dp[0][0] = 1;
    for (int i = 0; i < S.size(); ++i) {
        for (int j = 0; j <= 3; ++j) {
            if (S[i] == '?') add(dp[i + 1][j], (dp[i][j] * 3) % mod);
            else add(dp[i + 1][j], dp[i][j]);
        }
        if (S[i] == 'A' || S[i] == '?') add(dp[i + 1][1], dp[i][0]);
        if (S[i] == 'B' || S[i] == '?') add(dp[i + 1][2], dp[i][1]);
        if (S[i] == 'C' || S[i] == '?') add(dp[i + 1][3], dp[i][2]);
    }

    cout << dp[S.size()][3] << endl;

    return 0;
}




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

int main()
{
    string s1,s2;
    cin>>s1>>s2;
    
    int n1=s1.length(),n2=s2.length();
    
    int dp[n1+1][n2+1];
    
    for(int i=0;i<n1+1;i++)
    {
        for(int j=0;j<n2+1;j++)
        {
            dp[i][j]=0;
        }
    }
    //cout<<n1<<" "<<n2<<endl;
    
    for(int i=0;i<=n1;i++)
    {
        for(int j=0;j<=n2;j++)
        {
            if(i==0 || j==0)
            dp[i][j]=0;
            else if(s1[i-1]==s2[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    
    
    
    
    string s="";
    int a=n1,b=n2;
    
    while(a>0 && b>0)
    {
        if(s1[a-1]==s2[b-1])
        {
           // if(s1[a]==s2[b])
            s+=s2[b-1];
            
            a--;
            b--;
        }
        else if(dp[a-1][b]>dp[a][b-1])
        a--;
        else
        b--;
    }
    reverse(s.begin(),s.end());
    cout<<s;
    return 0;
}


Measured memory_bytes: 35456