akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<char>> A(H + 2, vector<char>(W + 2, '#'));
    // 黒マスの座標を保存する
    vector<P> M;
    rep(1, i, H + 1)
    {
        rep(1, j, W + 1)
        {
            cin >> A[i][j];
            if (A[i][j] == '#')
            {
                M.push_back(P(i, j));
            }
        }
    }
    // bfsのためのデータ
    vector<vector<int>> dist(H + 2, vector<int>(W + 2, -1));
    queue<P> que;
    vector<int> dx, dy;
    dx = {1, 0, -1, 0};
    dy = {0, 1, 0, -1};

    // 黒のマスをすべてqueueに追加
    for (auto m : M)
    {
        dist[m.first][m.second] = 0;
        que.push(m);
    }
    // マスが#の点からbfsする
    while (que.size())
    {
        P v = que.front();
        que.pop();
        rep(0, i, 4)
        {
            int nx = v.first + dx[i];
            int ny = v.second + dy[i];
            // 黒マスか探索済みなら
            if ((A[nx][ny] == '#') || (dist[nx][ny] != -1))
            {
                continue;
            }
            dist[nx][ny] = dist[v.first][v.second] + 1;
            que.push(P(nx, ny));
        }
    }
    int ans = 0;
    rep(0, i, H + 2)
    {
        rep(0, j, W + 2)
        {
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 21224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M;
    ll K;
    cin >> N >> M >> K;
    ll A[N], B[M];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }
    int ans = 0;
    ll c[M + 1]{};
    for (int i = 0; i < M; i++) {
        c[i + 1] = c[i] + B[i];
    }
    ll t = 0;
    for (int i = 0; i <= N; i++) {
        if (i != 0) {
            t += A[i - 1];
        }
        if (t > K) break;
        int l = -1;
        int r = M + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (t + c[m] <= K) {
                l = m;
            } else {
                r = m;
            }
        }
        ans = max(ans, i + l);
    }
    cout << ans << "\n";
    return 0;
}

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

#include <iostream>
#include <fstream>

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

typedef long long ll;
#define tr(container, it) \
        for (auto it = container.begin(); it != container.end(); it++)
#define scontains(c, x) ((c).find(x) != (c).end())   //O(log n)
#define contains(c, x) (find((c).begin(),(c).end(),x) != (c).end()) //O(n)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mll map<ll,ll>
#define intv(x, a, b)((x)>=a && (x)<=b)
#define  rep(i, _begin, _end) for (__typeof(_end) end = _end, begin = _begin,  i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define  _for(i, end) for (__typeof(end) i = 0, _len = (end); i < (_len); i += 1)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define F first
#define S second
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define readint ({int t;cin >> t;t;})
const double PI = 2 * acos(.0);
const int INF = 0x3f3f3f3f;
const ll LLINF = 1000000000000000005LL;;
const ll MOD = (ll) (1e9) + 7;
void _mod(ll &x){x = mod(x, MOD);}
//const ll MOD = (ll) 998244353 ;
const double EPS = 1e-10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *) array, (T *) (array + N), val);
}


#define int ll
int N, A[101010];
ll S1[101010], S2[101010];
class DRainFlowsIntoDams {
public:

void solve(std::istream& cin, std::ostream& cout) {
    Fill(S1,0), Fill(S2,0);
    cin >> N;
    _for(i,N)cin >> A[i];
    int sum = 0;
    for (int i = 0; i < N; i+=2) {
        S1[i+2] = S1[i] + A[i], sum += A[i];
    }
    for (int i = 1; i < N; i+=2) {
        S2[i+2] = S2[i] + A[i], sum += A[i];
    }
    _for(j,N) {
        int i = j +1;
    if(i&1){
        cout <<  sum - (S1[i-1] + S2[N] - S2[i])*2 << " ";
    }
    else {
        cout << sum - (S1[N+1] - S1[i] + S2[i-1])*2 << " ";
    }

}


}
};


#undef int
int main() {


	DRainFlowsIntoDams solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(0); ios::sync_with_stdio(0); out<<fixed<<setprecision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> P;
static const int INF=1<<24;


int main(){
	int n;
	P m[110][110];
	int vi[110][110];
	while(cin>>n,n){
		rep(i,110){
			rep(j,110){
				m[i][j].F=0;
				m[i][j].S=0;
				vi[i][j]=0;
			}
		}
		rep(i,n){
			rep(j,n){
				cin>>m[i][j].F>>m[i][j].S;
			}
		}
		int x,y;
		int res=0;
		rep(i,n){
			rep(j,n){
				x=j;
				y=i;
				rep(k,n*n){
					P tmp=m[y][x];
					x=tmp.F;
					y=tmp.S;
				}
				if(vi[y][x]==0){
					res++;
					rep(k,n*n+10){
						if(vi[y][x]==1){
							break;
						}
						vi[y][x]=1;
						P tmp=m[y][x];
						x=tmp.F;
						y=tmp.S;
					}
				}
			}
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1300
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  VL as(3 * n);
  FOR(a,as) {
    cin >> a;
  }
  VL head(n+1);
  ll head_sum = accumulate(as.begin(), as.begin() + n, 0ll);
  priority_queue<ll, VL, greater<ll>> head_que(as.begin(), as.begin() + n);
  REP(k,0,n+1) {
    head[k] = head_sum;
    ll x = as[n+k];
    head_sum += x;
    head_que.push(x);
    head_sum -= head_que.top();
    head_que.pop();
  }
  VL tail(n+1);
  ll tail_sum = accumulate(as.rbegin(), as.rbegin() + n, 0ll);
  priority_queue<ll> tail_que(as.rbegin(), as.rbegin() + n);
  for(int k=n; k>=0; k--) {
    tail[k] = tail_sum;
    ll x = as[n+k-1];
    tail_sum += x;
    tail_que.push(x);
    tail_sum -= tail_que.top();
    tail_que.pop();
  }
  ll ans = LLONG_MIN;
  REP(i,0,n+1) {
    ans = max(ans, head[i] - tail[i]);
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 6520
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cerr<<#x<<"="<<x<<endl;



int main( ){
  int n,m,pos,num;

  scanf("%d %d",&n,&m);

   vector<int>s(n+1,-1);

  bool ex=0;

  for(int i=0;i<m;i++){

    scanf("%d %d",&pos,&num);
    pos--;

    if((s[pos]>-1&&s[pos]!=num)||(pos+num<1&&n>1)){
        return cout<<-1<<endl,0;
    }
    s[pos]=num;
  }

    cout<<(s[0]==-1?(n>1?1:0):s[0]);
    for(int i=1;i<n;i++)cout<<max(s[i],0);
    cout<<endl;

}

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

int main() {
  int N, X, Y;
  cin >> N >> X >> Y;
  
  vector<int> cnt(N);
  for (int i = 1; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) {
      int d1 = j - i;
      int d2 = abs(i - X) + abs(j - Y) + 1;
      cnt.at(min(d1, d2))++;
    }
  }

  for (int i = 1; i < N; i++) cout << cnt.at(i) << "\n";
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int H;
int W;
int A;
int B;
char res1[1002];
char res2[1002];
int main(){
  int i;
  rd(H);
  rd(W);
  rd(A);
  rd(B);
  for(i=(0);i<(W);i++){
    res1[i] = res2[i] = '0';
  }
  for(i=(0);i<(A);i++){
    res1[i]++;
  }
  for(i=(A);i<(W);i++){
    res2[i]++;
  }
  for(i=(0);i<(B);i++){
    wt_L(res1);
    wt_L('\n');
  }
  for(i=(B);i<(H);i++){
    wt_L(res2);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20190921-1

// --- original code ---
// int H, W, A, B;
// char res1[1002], res2[1002];
// {
//   rd(H,W,A,B);
//   rep(i,W) res1[i] = res2[i] = '0';
//   rep(i,A) res1[i]++;
//   rep(i,A,W) res2[i]++;
//   rep(i,B) wt(res1);
//   rep(i,B,H) wt(res2);
// }


Measured memory_bytes: 1280
N = int(input())
dp = [N] * 110000
dp[0] = 0

for i in range(N):
    j = 0
    while i + 9 ** j <= N:
        dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)
        j += 1
    k = 0
    while i + 6 ** k <= N:
        dp[i + 6 ** k] = min(dp[i + 6 ** k], dp[i] + 1)
        k += 1

print(dp[N])

Measured memory_bytes: 9928
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    cin >> n;
    vector<int> v(n), v2(n);
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        v[k-1] = i;
    }
    int q = 0;
    for (int i = n-1; i >= 0; --i) {
        q += v[i];
        v2[i] = q;
    }
    int p = 0;
    for (int i = 0; i < n; ++i) {
        p += v[i];
        if(i) printf(" ");
        printf("%d", p);
    }
    printf("\n");
    for (int i = 0; i < n; ++i) {
        if(i) printf(" ");
        printf("%d", v2[i]);
    }
    printf("\n");
    return 0;
}


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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define P  pair<int,int>
using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;
string grid[(int)(1e6)+1];
int h,w,k;
int sx, sy, gx, gy;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<vector<int>> dist;
void bfs(){
    queue<P> q;
    q.push({sx,sy});
    dist[sx][sy]=0;
    while(!q.empty()){
        auto from = q.front();q.pop();
        int fx=from.first,fy=from.second;
        rep(d,4){
            reps(m,k+1,1){
                int tx=fx+dx[d]*m;
                int ty=fy+dy[d]*m;
                if(tx<0||tx>=h||ty<0||ty>=w)continue;
                if(grid[tx][ty]=='@')break;
                if(dist[tx][ty] !=-1 && dist[tx][ty]<=dist[fx][fy])break;
                if(dist[tx][ty] !=-1) continue;
                dist[tx][ty] = dist[fx][fy]+1;
                q.push({tx,ty});
            }
        }
    }
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

cin>>h>>w>>k;
dist=vector<vector<int>>(h,vector<int>(w,-1));
cin>>sx>>sy>>gx>>gy;
sx--,sy--,gx--,gy--;
rep(i,h){
    cin>>grid[i];
}

bfs();
cout<<dist[gx][gy]<<endl;

return 0;
}

Measured memory_bytes: 42240
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vdo=vector<double>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vvdo=vector<vector<double>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using pqin=priority_queue<int>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
int main()
{
    string s;
    cin>>s;
    bool can=false;
    rep(i,3){
        if(s[i]=='7'){
            can=true;
            break;
        }
    }
    if(can)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3628
n, m, k = map(int, input().split())
*parent, = range(n+m)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
for i in range(k):
    a, b, c = map(int, input().split())
    b -= 1; c -= 1
    if a == 1:
        pb = root(m+b); pc = root(m+c)
        if pb < m and pc < m and pb != pc:
            print(i+1)
            break
        unite(pb, pc)
    else:
        pb = root(m+b)
        if pb < m and pb != c:
            print(i+1)
            break
        unite(c, pb)
else:
    print(0)

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 4e5 + 5;


int n;
ll k, a[maxn];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  //cout << fixed << setprecision(6);
  cin>>n>>k;
  for (int i=0; i<n; i++) {
    cin>>a[i];
  }
  vector<int> ans;
  bool whatever = false;
  for (int b=62; b>=0; b--) {
    int num_zeros = 0;
    for (int i=0; i<n; i++) {
      if (((a[i] >> b)&1) == 0) {
	num_zeros++;
      }
    }
    int d = (k >> b)&1;
    
    if (num_zeros > n/2 && (d==1 || whatever)) {
      ans.push_back(1);
    } else {
      ans.push_back(0);
      if (d==1) {
	whatever=true;
      }
    }
  }

  ll X = 0;
  ll base = 1;
  int sz = (int)ans.size();
  for (int i=sz-1; i>=0; i--) {
    X += base*ans[i];
    base *= 2;
  }

  ll res = 0;
  for (int i=0; i<n; i++) {
    res += a[i]^X;
  }

  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define nl cout<<'\n';
int main()
{
    int n,cnt=0;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
       cin>>a[i];
       b[i]=a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
       if(a[i]!=b[i])
         cnt++;
    }
    if(cnt>2)
      cout<<"NO";
    else
      cout<<"YES";
    nl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Misterious Gems
 *  URL:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2000
 *
 * @author Igari Kazuya
 *
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n;
		while(true){
			int[][] map = new int[21][21];
			for(int i=0;i<21;i++){
				for(int j=0;j<21;j++){
					map[i][j] = 0;
				}
			}

			n = sc.nextInt();
			if(n == 0){
				break;
			}

			for(int i=0;i<n;i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				map[y][x] = 1;
			}

			n = sc.nextInt();

			int x=10;
			int y=10;
			int xx,yy;
			for(int i=0;i<n;i++){
				switch(sc.next().charAt(0)){
				case 'N':
					yy = 1;
					xx = 0;
					break;
				case 'E':
					xx = 1;
					yy = 0;
					break;
				case 'S':
					yy = -1;
					xx = 0;
					break;
				case 'W':
					xx = -1;
					yy = 0;
					break;
				default:
					xx = 0;
					yy = 0;
				}

				int next = sc.nextInt();
				for(int j=0;j<next;j++){
					x += xx;
					y += yy;

					map[y][x] = 0;
				}
			}

			int flag = 0;
			for(int i=0;i<21;i++){
				for(int j=0;j<21;j++){
					flag += map[i][j];
				}
			}

			if(flag == 0){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}

	}

}

Measured memory_bytes: 12000
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int n, a;
    cin >> n;
    vector<int>an(n * 3);
    rep(i, n * 3)cin >> an[i];
    sort(all(an));
    ll sum1=0, sum2=0,sum3=0;
    for (int i = n; i < 2 * n; i++)sum1 += an[i];
    for (int i = 1; i < 3 * n; i += 3)sum2 += an[i];
    for (int i = n; i < 3 * n; i += 2)sum3 += an[i];
    cout << max(sum3,max(sum1, sum2)) << endl;
}

Measured memory_bytes: 1408
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define mod 998244353
#define inf (1LL<<61)
#define int long long
typedef long long ll;
#define ld long double
#define N 301 



int32_t main()
{
    IOS;
    int x;
    cin >> x;
    cout << x * x * x << endl;
}


Measured memory_bytes: 3108
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAX_LEN (3000)
// #define MAX_LEN (12)
#define SIZE_BUF (30)

using namespace std;

int dpss[MAX_LEN + 1][MAX_LEN + 1];
int from_iss[MAX_LEN + 1][MAX_LEN + 1], from_jss[MAX_LEN + 1][MAX_LEN + 1];

// self study
// time taken 55 min
// 2 WA
int main() {
  // read inputs
  char ss[MAX_LEN + 1], ts[MAX_LEN + 1], buf[SIZE_BUF];
  scanf("%s", ss);
  fgets(buf, SIZE_BUF, stdin);
  scanf("%s", ts);
  //   printf("%s\n", ss);
  //   printf("%s\n", ts);

  // get length of each string
  const int N = strlen(ss), M = strlen(ts);
  //   printf("N = %d, M = %d\n", N, M);

  // solve dp
  // initialize
  dpss[0][0] = 0;
  for (int i = 0; i < N; i++) {
    dpss[i + 1][0] = 0;
  }
  for (int j = 0; j < M; j++) {
    dpss[0][j + 1] = 0;
  }
  // update
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (ss[i] == ts[j]) {
        dpss[i + 1][j + 1] = dpss[i][j] + 1;
        from_iss[i + 1][j + 1] = i;
        from_jss[i + 1][j + 1] = j;
      } else {
        if (dpss[i + 1][j] >= dpss[i][j + 1]) {
          dpss[i + 1][j + 1] = dpss[i + 1][j];
          from_iss[i + 1][j + 1] = i + 1;
          from_jss[i + 1][j + 1] = j;
        } else {
          dpss[i + 1][j + 1] = dpss[i][j + 1];
          from_iss[i + 1][j + 1] = i;
          from_jss[i + 1][j + 1] = j + 1;
        }
      }
    }
  }

  // retrieve the LCS
  char cs[MAX_LEN + 1];
  cs[dpss[N][M]] = '\0';
  int i = N - 1, j = M - 1, k = dpss[N][M] - 1;
  while (k >= 0) {
    if (from_iss[i + 1][j + 1] == i && from_jss[i + 1][j + 1] == j) {
      cs[k--] = ss[i];
      i--;
      j--;
    } else if (from_iss[i + 1][j + 1] == i) {
      i--;
    } else {
      j--;
    }
  }

  //   printf("%d\n", dpss[N][M]);
  printf("%s\n", cs);
}

Measured memory_bytes: 105728
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n, i;
long long sum;
int main()
{
	scanf("%d", &n);
	while(sum < n)
	{
		i++;
		sum += i;
	}
	printf("%d\n", i);
}

Measured memory_bytes: 128
from math import factorial
n, blue = map(int, input().split())

red = n - blue

mod = 10**9+7

def cmb(n, r):
    result = factorial(n) // (factorial(n-r)*factorial(r)) 
    return result


for i in range(1, blue+1, 1):
    if red + 1 < i:
        print(0) 
    else:
        ans = cmb(red+1, i) * cmb(blue-1, i-1)
        #print(i)
        print(ans % mod)


Measured memory_bytes: 3444
import sys
from heapq import *
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8, i8, i8[:]), cache=True)
def main(H, W, AB):
    A, B = AB[::2], AB[1::2]
    dp = np.zeros(W + 10, np.int64)
    dp[0] = -1
    INF = 1 << 60
    q = [0] * W
    rm_q = [0] * 0
    # dp に入っている値が有効なデータ点全体を BIT で管理する
    bit_raw = np.ones(W + 10, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    for h in range(H):
        a, b = A[h], B[h]
        # a-1, b+1 の値を計算
        for x in [a - 1, b + 1]:
            if x in (0, W + 1):
                continue
            if dp[x] != -1:
                continue
            k = get_sum(bit, x)
            if k >= 1:
                x0 = find_kth_element(bit, k)
                dp[x] = dp[x0] + (x - x0)
                add(bit, x, 1)
                heappush(q, dp[x])
        # [a,b] 内の値を無効化する
        k = get_sum(bit, a - 1) + 1
        while True:
            x = find_kth_element(bit, k)
            if x > b:
                break
            heappush(rm_q, dp[x])
            dp[x] = -1
            add(bit, x, -1)
        # 有効な dp の値の最小値を求める
        while rm_q and rm_q[0] == q[0]:
            heappop(rm_q)
            heappop(q)
        if not q:
            print(-1)
        else:
            print(1 + h + q[0])

H, W = map(int, readline().split())
AB = np.array(read().split(), np.int64)

main(H, W, AB)

Measured memory_bytes: 134968
S = input()
Q = int(input())
muki = 1
one = ''
two = ''

for i in range(Q):
    I = input().split()
    if I[0] == '1':
        muki *= -1
    elif I[0] == '2':
        F = int(I[1])
        C = I[2]
        if F==1:
            if muki == 1:
                t = [one, C ]
                one = ''.join(t)
            else:
                t = [two, C ]
                two = ''.join(t)
        elif F==2:
            if muki == 1:
                t = [two, C ]
                two = ''.join(t)
            else:
                t = [one, C ]
                one = ''.join(t)
if muki == 1:
    ANS = [one[::-1],S,two]
    print(''.join(ANS))
else:
    ANS = [two[::-1],S[::-1],one]
    print(''.join(ANS))
            

Measured memory_bytes: 4644
#include<iostream>

using namespace std;


int main(){

	int x=1,y=1,box;

	for(int i =1 ;(x+y)!=0;i++){
		cin >> x >> y;

		if(x > y){
			box = x;
			x = y;
			y = box;
		}
		if((x+y) != 0){
			cout << x << " " << y <<"\n";
		}
	}
	return 0;
}


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

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int test_cases = 1;
        Solver s = new Solver();
        for (int i = 1; i <= test_cases; i++) {
            s.solve(i, in, out);
        }
        out.close();
    }
}

class Solver {
    void solve(int test_number, InputReader in, PrintWriter out) throws IOException {
        long n = in.nextInt();
        for (int i = 3500; i >= 0; i--) {
            for (int j = 1; j <= 3500; j++) {
                long a = n * i * j;
                long b = 4 * i * j - i * n - n * j;
                if (b > 0 && a % b == 0) {
                    out.println(i + " " + j + " " + a / b);
                    return;
                }
            }
        }
    }
}


class InputReader {
    BufferedReader br;
    StringTokenizer st;

    public InputReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException  e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

Measured memory_bytes: 23508
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    s = getS()
    k = getN()

    ss = set()
    for i in range(len(s)):
        for j in range(1, k+1):
            if i + j <= len(s):
                ss.add(s[i:i+j])

    ss = list(ss)
    ss.sort()
    # ss.sort(key=lambda x:len(x))
    # print(ss)
    print(ss[k-1])


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()







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

class segtree:
    x_unit=0 # 単位元
    x_func=lambda self,a:a[0]+a[1]  # 関数
    def __init__(self,n,seq):
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の合計を取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

n,q=map(int,input().split())
*a,=map(int,input().split())
seg=segtree(n,a) 
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        old=seg.fold(x,x+1)
        seg.update(x, old+y)
    else:
        print(seg.fold(x, y))

Measured memory_bytes: 147388
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define ALL(v) v.begin(), v.end()
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);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string bans(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int n;cin>>n;
  bool ans;
  int sum=0;
  int in=n;
  while(n>0){
    sum+=n%10;
    n/=10;
  }
  ans=(in%sum==0);
  cout << bans(ans) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
int main() {
  int n, ans = 0;
  cin >> n;
  int curmin = 1e9;
  vector<int> P(n);
  rep(i, n) cin >> P[i];
  rep(i,n){
    curmin = min(curmin, P[i]);
    if(curmin == P[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    vector<int> A;
    for (int i=0; i<N; i++) {
        int temp;
        cin >> temp;
        A.push_back(temp);
    }

    double gyaku = 0;
    for (int i=0; i<N; i++) {
        gyaku += 1.0/A[i];
    }

    double result = 1.0/gyaku;
    cout << setprecision(10) << fixed << result;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void pre(){}
long long int sum(long long int n){
    return (n*(n+1))/2;
}
void solve(){
    long long int n;cin>>n;
    long long int ans = sum(n)-3*(sum(n/3))-5*(sum(n/5))+15*(sum(n/15));
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}


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

int main(){
   int a,d[1100000];
  cin >> a;
   d[0] = a;
  for(int j =0;j<1000000;j++){
  for(int i=1;i<1000000 ;i++){
    d[i] =0;
    if(d[i-1]%2 == 0){
      d[i] = d[i-1]/2;
    }
    if(d[i-1]%2 == 1){
      d[i] = 3*d[i-1]+1;
    }
    
    if((j!=i)&&(d[j] == d[i])){
      cout << i+1 << endl;
      
      return 0;
  }
    
  }
  }
}


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

int main()
{
    string s,t;
    cin>>s;
    cin>>t;
    int x=s.size();
    int ans=0;
    for(int i=0;i<x;i++)
    {
        if(s[i]!=t[i])
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3924
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<ll,ll> P;

ll s2ll(string s){
  ll res;
  stringstream ss;
  ss<<s;
  ss>>res;
  return res;
}

string s;
int p=0;

P change(string s){
  ll fi,se;
  if(s.find('x') == string::npos){
    return P(0, s2ll(s) );
  }
  
  string tmp="";
  for(int i=0;i<(int)s.size();i++){
    if(s[i]=='x')break;
    tmp+=s[i];
  }
  if(tmp=="")se=1;
  else se=s2ll(tmp);

  if(s.find('^')==string::npos){
    fi=1;
  }else{
    tmp="";
    for(int i=0;i<(int)s.size();i++){
      if(s[i]=='^')tmp="";
      else tmp+=s[i];
    }
    fi=s2ll(tmp);
  }
  
  return P(fi,se);
}

map< ll, ll > T;

void change(){
  
  int p=0,len=s.size();
  
  while(p<len){
    string tmp="";
    tmp+=s[p];
    p++;
    while(p<len&&s[p]!='+'&&s[p]!='-'){
      tmp+=s[p];
      p++;
    }
    if(tmp[0]=='+'){
      string tm=tmp.substr(1);
      P p=change(tm);
      T[ p.first ]+= p.second;      
    }else if(tmp[0]=='-'){
      string tm=tmp.substr(1);
      P p=change(tm);
      T[ p.first ]-= p.second;      
    }else{
      P p=change(tmp);
      T[ p.first ]+= p.second;
    }
  }
}

ll calc(ll x){
  ll res=0;
  ll B=1;
  
  for(int i=0;i<=5;i++){
    res+=B*T[i];
    B*=x;
  }
  return res;
}

int main(){
  int N;
  //  cin>>N;
  
  cin>>s;
  change();

  vec v;
  for(ll i=-3000;i<=3000;i++){
    if( calc(i) == 0 )v.push_back(i);
  }

  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  
  for(int i=0;i<v.size();i++){
    cout<<"(x";
    v[i]*=-1;
    if(v[i]>0)cout<<"+";
    cout<<v[i]<<")";
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3216
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for i in range(A+1):
  for s in range(B+1):
    for o in range(C+1):
      if X == 500*i + 100*s + 50*o:
        count+=1
print(count)

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    sort(all(a));
    ll ans = 0;
    if(n%2){
        ll tm = 0;
        ll tp = 0;
        for(i = 0;i < (n-1)/2;++i){
            tm += 2*a.at(i);
        }
        for(i = (n-1)/2;i < n;++i){
            tp += 2*a.at(i);
        }
        tp -= a.at((n-1)/2);
        tp -= a.at((n+1)/2);
        ans = tp - tm;
        tp = 0; tm = 0;
        for(i = 0;i < (n+1)/2;++i){
            tm += 2*a.at(i);
        }
        for(i = (n+1)/2;i < n;++i){
            tp += 2*a.at(i);
        }
        tm -= a.at((n-1)/2);
        tm -= a.at((n-3)/2);
        ll tmp = tp - tm;
        ans = max(ans, tmp);
    }else{
        ll minus = 0;
        for(i = 0;i < n/2;++i){
            minus += 2*a.at(i);
        }
        minus -= a.at(n/2-1);
        ll plus = 0;
        for(i = n/2;i < n;++i){
            plus += 2*a.at(i);
        }
        plus -= a.at(n/2);
        ans = plus - minus;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4028
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

long long inf=1000000007;

int main(){
	long long n;
	cin>>n;
	vector<pair<long long,long long>> hoge(n);
	
	for(int i=0;i<n;i++) cin>>hoge.at(i).second>>hoge.at(i).first;
	sort(hoge.begin(),hoge.end());
	string ans="Yes";
	long long now=0;
	
	for(auto a:hoge){
		now+=a.second;
		if(now>a.first){
			ans="No";
			break;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 3328
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node {
  int key;
  Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k) {
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while ( x != NIL ) {
    y = x;
    if ( z ->key < x->key ) {
      x = x->left;
    } else {
      x = x->right;
    }
  }

  z->parent = y;
  if ( y == NIL ) {
    root = z;
  } else {
    if ( z->key < y->key ) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node *u) {
  if ( u == NIL ) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node *u) {
  if ( u == NIL ) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

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

  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    cin >> com;
    if ( com == "insert" ) {
      scanf("%d", &x);
      insert(x);
    } else if ( com == "print" ) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  string s;
  cin>>s;
  puts(s[0]=='9'||s[1]=='9' ? "Yes" : "No");
  return 0;
}


Measured memory_bytes: 764
import numpy as np

n = int(input().strip())
A = list(map(int,input().strip().split(' ')))
sorted_A = sorted(A)
ai=sorted_A[-1]
print(ai)
del sorted_A[-1]
tmplist=np.array([min(i,ai-i) for i in sorted_A])
maxidx = np.argmax(tmplist)

print(sorted_A[int(maxidx)])


Measured memory_bytes: 31184
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        c: chars
    }
    println!("{}", (c[0] as u8 + 1) as char);
}


Measured memory_bytes: 4352
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

#define MAXN (1 << 20)

vector<int> a[MAXN];
int n;
vector<pair<int, int> > edges;
map<pair<int, int>, int> colors;
int deg;
int v[MAXN];

void dfs(int cur, int prevc) {
	//cerr << cur << " " << prevc << endl;
	v[cur] = 1;
	int color = 0;
	for (int i = 0; i < a[cur].size(); i++) {
		int nnext = a[cur][i];
		if (!v[nnext]) {
			if (color == prevc) {
				color++;
			}
			pair<int, int> e = make_pair(cur, nnext);
			if (e.first > e.second) {
				swap(e.first, e.second);
			}
			colors[e] = color;
			dfs(nnext, color);
			color++;
		}
	}
}


int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		if (v1 > v2) {
			swap(v1, v2);
		}
		v1--;
		v2--;
		a[v1].push_back(v2);
		a[v2].push_back(v1);
		edges.push_back(make_pair(v1, v2));
	}
	deg = 0;
	for (int i = 0; i < n; i++) {
		deg = max(deg, (int)a[i].size());
	}
	dfs(0, -1);
	cout << deg << endl;
	for (int i = 0; i < edges.size(); i++) {
		cout << colors[edges[i]] + 1 << endl;
	}
	return 0;
}


Measured memory_bytes: 37156
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<map>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,x;
map<int,int> mp;
int main()
{
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>x;
		mp[x]++;
	}
	cin>>m;
	for (i=1;i<=m;i++)
	{
		cin>>x;
		if (mp[x]<1)
		{
			cout<<"NO";
			return 0;
		}
		else mp[x]--;
	}
	cout<<"YES";
	return 0;
}

Measured memory_bytes: 9600
import sys
import numpy as np
input = sys.stdin.readline

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

def main():
    N = int(input())

    dic = {}
    for i in range(1, N+1):
        insu = factorization(i)
        for p, count in insu:
            if p in dic:
                dic[p] += count
            else:
                dic[p] = count
    dic = np.array(sorted(dic.values()))
    
    def cc(num):# num-1以上の要素の個数
        return np.count_nonzero(dic >= num-1)
    
    print(cc(75) + cc(25) * (cc(3) - 1) + cc(15) * (cc(5) - 1) + cc(5) * (cc(5) - 1) * (cc(3) - 2) // 2)


if __name__ == "__main__":
    main()

Measured memory_bytes: 12508
#include <iostream>
#include <utility>
#include <stdint.h>
#include <vector>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;

const int MAX = 1000001;

long long fac[MAX], finv[MAX], inv[MAX];

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
  uint64_t N, M, K;
  cin >> N >> M >> K;

  COMinit();
  
  uint64_t ans = 0;
  for (uint64_t k=0; k<=K; ++k) {
    uint64_t X = M;
    X *= mpow(M-1,N-1-k) % MOD;
    X %= MOD;
    //cerr << "X:" << X << endl;
    //cerr << N-k << "C" << k << "=" << COM(N-k,k) << endl;
    ans += ((COM(N-1,k)%MOD) * X)%MOD;
    ans %= MOD;
  }

  cout << ans%MOD << endl;

  return 0;
}


Measured memory_bytes: 27044
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		long a = 1, b = 1;
		for (int i = 0; i < n; i++) {
			long x = sc.nextInt();
			long y = sc.nextInt();
			long k = 1;
			k = Math.max(k, a / x);
			k = Math.max(k, b / y);
			while (x * k < a || y * k < b) {
				k++;
			}
			a = x * k;
			b = y * k;
		}
		System.out.println((a + b));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


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

int main(){
    int n,k;
    cin >> n >> k;
    vector<ll> x(n);
    ll ans = mod*mod;
    for(int i = 0; i < n; i++) cin >> x[i];
    if(n == 1){
        cout << abs(x[0]) << endl;
        return 0;
    }
    for(int i = 0; i <= n-k; i++){
        ll can = min(abs(x[i]),abs(x[k-1+i]))+abs(x[k+i-1]-x[i]);
        if(ans > can) ans = can;
    }    
    cout << ans << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

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

  int n, q;
  string s;
  vector<pair<string, string>> ops;

  cin >> n >> q >> s;
  ops.resize(q);

  for (int i = 0; i < q; i++) {
    cin >> ops[i].first >> ops[i].second;
  }

  auto get = [&] (int pos) {
    for (int i = 0; i < q; i++) {
      if (ops[i].first[0] == s[pos]) {
        if (ops[i].second == "L") {
          pos--;
        } else {
          pos++;
        }
        if (pos < 0) {
          return -1;
        }
        if (pos >= n) {
          return +1;
        }
      }
    }
    return 0;
  };

  int alpha = 0, beta = 0, l = 0, r = n - 1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (get(m) == -1) {
      alpha = m + 1;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  l = 0;
  r = n - 1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (get(m) == +1) {
      beta = n - m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  cout << n - alpha - beta << "\n";
}


Measured memory_bytes: 16016
x, k, d = map(int, input().split())

# if x >= 0:
if abs(x) >= k * d:
    print(abs(x) - k * d)
else:
    q, mod = divmod(x, d)
    k -= q
    if k % 2 == 0:
        print(mod)
    else:
        print(abs(mod - d))
# else:
#     if abs(x) >= k * d:
#         print(abs(x) - k * d)
#     else:
#         q, mod = divmod(abs(x), d)
#         k -= q
#         if k % 2 == 0:
#             print(mod)
#         else:
#             print(abs(mod - d))


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

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

killed = 0

for i in range(n):
    if b[i] <= a[i]:
        killed += b[i]
        continue
    else:
        b[i] -=	a[i]
        killed += a[i] + min(a[i+1], b[i])
        a[i+1] = max(0, a[i+1]-b[i])

print(killed)


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

W = list(map(int,input().split()))
min = 9999999999
tmp1= 0
tmp2= 0
for t in range(N-1):
    tmp1 = 0
    tmp2 = 0
    for i in range(len(W[:(t+1)])):
        tmp1 +=W[i]
    
    for i in range(len(W[(t+1):])):
        tmp2 +=W[i+len(W[:(t+1)])]

    if min > abs(tmp1-tmp2):
        min = abs(tmp1-tmp2)
    if tmp1-tmp2 == 0:
        min=0

print(min)  

Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define LL long long
#define mk make_pair
#define pb push_back
#define pii pair<int, int>
#define ArrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], (i==r)?'\n':' ')
const int maxn = 2e5+7;
const LL mod = 998244353;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const double EPS = 1e-8;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;

int n;

int main()
{
    scanf("%d", &n);
    printf("%d\n", (n+1)/2);
}

Measured memory_bytes: 888