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

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
  std::vector<long long> answers;
  long long ans = (N * (N - 1)) / 2;
  auto uf = UnionFind(N+1);

  for (int i = M-1; i >= 0; i--) {
    answers.push_back(ans);
    auto ac = uf.size(A[i]);
    auto bc = uf.size(B[i]);
    if (!uf.findSet(A[i], B[i]))
    {
      ans -= ac * bc;
      uf.unionSet(A[i], B[i]);
    }
  }
  for (int i = M-1; i >= 0; i--) {
    printf("%lld\n", answers[i]);
  }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 4212
//Heaplax
#include<bits/stdc++.h>
#define N 105
#define LL long long
#define LOG(x) cerr<<#x<<" = "<<x<<endl
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
    while(ch=getchar(),ch<33);
    if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
    while(ch=getchar(),ch>33)x=x*10+ch-48;
    if(fs)x=-x;
}
using namespace std;
int n,m,x,y,f[2][N][N][N],sx[N][N],sy[N][N];
char s[N][N];
void check(int& a,int b)
{
	a=a<b?b:a;
}
int slx(int x,int a,int b)
{
	if(a>b)return 0;
	return sy[x][b]-sy[x][a-1];
}
int sly(int y,int a,int b)
{
	if(a>b)return 0;
	return sx[b][y]-sx[a-1][y];
}
int main()
{
	re(n),re(m);
	for(int i=1;i<=n;++i)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			sx[i][j]=sx[i-1][j]+(s[i][j]=='o'),
			sy[i][j]=sy[i][j-1]+(s[i][j]=='o');
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(s[i][j]=='E')
				x=i,y=j;
	int ans=0;
	for(int i=0;i<x;++i)
	{
		bool b=i&1;
		for(int j=0;j<=n-x;++j)
			for(int k=0;k<y;++k)
				for(int l=0;l<=m-y;++l)
				{
					int& e=f[b][j][k][l];
					ans=max(ans,e);
					check(f[b^1][j][k][l],e+(j<x-i-1?slx(x-i-1,max(y-k,l+1),min(y+l,m-k)):0));
					check(f[b][j+1][k][l],e+(x+j+1<=n-i?slx(x+j+1,max(y-k,l+1),min(y+l,m-k)):0));
					check(f[b][j][k+1][l],e+(l<y-k-1?sly(y-k-1,max(x-i,j+1),min(x+j,n-i)):0));
					check(f[b][j][k][l+1],e+(y+l+1<=m-k?sly(y+l+1,max(x-i,j+1),min(x+j,n-i)):0));
					e=0;
				}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 9216
#include <iostream>
#include <vector>
#include <string>
#include <complex>

int intp(int a, int b)
{
    int ans = 1;
    for (auto count = 0; count < b; ++count)
    {
        ans *= a;
    }

    return ans;
}

int FillRow(std::vector<std::vector<bool>> &dest, int row)
{
    int ans = 0;
    for (int i = 0; i < dest[row].size(); ++i)
    {
        if (dest[row][i])
        {
            dest[row][i] = false;
            ++ans;
        }
    }
    return ans;
}

int FillColumn(std::vector<std::vector<bool>>& dest, int column)
{
    int ans = 0;
    for (int i = 0; i < dest.size(); ++i)
    {
        if (dest[i][column])
        {
            dest[i][column] = false;
            ++ans;
        }
    }
    return ans;
}

int main()
{
    int w, h, k;
    std::cin >> h >> w >> k;
    constexpr bool WHITE = false, BLACK = true;
    std::vector<std::vector<bool>> field(h, std::vector<bool>(w, WHITE));

    int blackCount = 0;
    for (auto y = 0; y < h; ++y)
    {
        std::string s;
        std::cin >> s;
        for (auto x = 0; x < w; ++x)
        {
            if (s[x] == '#')
            {
                field[y][x] = BLACK;
                ++blackCount;
            }
            else
            {
                field[y][x] = WHITE;
            }
        }
    }

    int reqDelta = blackCount - k;
    if (reqDelta < 0)
    {
        std::cout << 0;
        return 0;
    }

    int ansCnt = 0;
    for (int y = 0; y < intp(2, h); ++y)
    {
        auto workR = field;
        int deltaR = 0;
        for (int yi = 0; yi < h; ++yi)
        {
            if (y & intp(2, yi))
            {
                deltaR += FillRow(workR, yi);
            }
        }

        for (int x = 0; x < intp(2, w); ++x)
        {
            auto workC = workR;
            int deltaC = 0;
            for (int xi = 0; xi < w; ++xi)
            {
                if (x & intp(2, xi))
                {
                    deltaC += FillColumn(workC, xi);
                }
            }
            if (deltaR + deltaC == reqDelta)
            {
                ++ansCnt;
            }
        }
    }

    std::cout << ansCnt;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
using ll = long long;

ll combination(ll n, ll k) {
    ll r = 1;
    for (ll d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

int main(){
	// input
	// A <= x <= B
	int N, A, B;
	cin >> N >> A >> B;

	vector<ll> v(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
	}

	// sort
	sort(v.begin(), v.end(), greater<ll>());

	// calculate max average
	long double average = 0;
	for (int i; i < A; ++i) {
		average += v[i];
	}
	average /= A;
	cout << fixed << average << endl;

	// calculate combination
	ll n = v[A - 1];
	int min_i = 0;
	int max_i = N-1;
	
	while(v[min_i] != n){
		min_i++;
	}
	while(v[max_i] != n){
		max_i--;
	}
	int w = max_i - min_i + 1;
	
	ll comb = 0;
	for (int k = A - min_i; k <= B - min_i; ++k) {
		if (v[min_i + k - 1] != n) {
			break;
		}
		comb += combination(w, k);
		if (min_i != 0) {
			break;
		}
	}


	cout << comb << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll k;
  cin >> k;
  if(k<=1){
    cout << 2 << endl;
    cout << 0 << " " << k+1 << endl;
  }
  else if(k<=50){
    cout << k << endl;
    for(ll i=1;i<=k;i++){
      cout << i << " ";
    }
    cout << endl;
  }
  else{
    cout << 50 << endl;
    for(ll i=1;i<=50;i++){
      if(50-i+1<=k%50){
        cout << (k+50-1)/50+i-1 << " ";
      }
      else{
        cout << k/50+i-1 << " ";
      }
    }
    cout << endl;
  }
}

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

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

    int n; cin >> n;
    vector<int> a(n);
    vector<int> sorta(n);
    int maxa = 0,cnt=0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sorta[i] = a[i];
        maxa = max(maxa,a[i]);
    }
    for(int i=0;i<n;i++){
        if(maxa == a[i]){
            cnt++;
        }
    }
    sort(sorta.rbegin(),sorta.rend());
    bool flag = true; int seconda;
    for(int i=0;i<n;i++){
        if(sorta[i]!=maxa){
            seconda = sorta[i];
            flag = false;
            break;
        }else{
            continue;
        }
    }

    if(flag){
        for(int i=0;i<n;i++){
            cout << maxa << endl;
        }
    }else{
        for(int i=0;i<n;i++){
            if(a[i] == maxa){
                if(cnt>1){
                    cout << maxa << endl;
                }else{
                cout << seconda << endl;
                }
            }else{
                cout << maxa << endl;
                }
        }
    }
}

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

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

    int sum = 0;
    int l = 0;
    int r = 0;

    for (int i = 0; i < N; i++) {
        cin >> l >> r;
        sum = sum + (r - l + 1);
    }
    //cout <<  << endl;
    // if (cnt == 3){
    //     cout << "Three" << endl;
    // }
    // if (cnt == 4){
    //     cout << "Four" << endl;
    // }
    cout << sum << endl;

    return 0;

}





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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

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

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

char f[30][30];
ll d[30][30];

int main(int argc, char **argv)
{
	ll H, W; cin >> H >> W;
	REP(h, H) REP(w, W) cin >> f[h][w];

	ll res{0};
	REP(h, H)
	{
		REP(w, W)
		{
			if (f[h][w] == '#') continue;
			REP(i, 30)REP(j, 30) d[i][j] = -1;
			queue<pair<ll, ll>> que;
			que.push(pair<ll, ll>(h, w));
			d[h][w] = 0;

			while (!que.empty())
			{
				auto now = que.front(); que.pop();
				ll h = now.first;
				ll w = now.second;

				REP(i, 4)
				{
					ll nh = h + dy[i];
					ll nw = w + dx[i];

					if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
					if (f[nh][nw] == '#') continue;
					if (d[nh][nw] != -1) continue;

					d[nh][nw] = d[h][w] + 1;
					que.push(pair<ll, ll>(nh, nw));
					res = max(res, d[nh][nw]);
				}
			}
		}
	}

	std::cout << res << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr lint mod = 1e9 + 7;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }
inline lint powm(lint a, lint n, lint p = mod) { return !n ? 1 : powm(a * a % p, n >> 1, p) * (n & 1 ? a : 1) % p; }

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  lint n, k; cin >> n >> k;
  if (n > k) return cout << 0 << '\n', 0;
  lint res = 1;
  for (int i = 0; i < n; ++i) (res *= k - i) %= mod;
  cout << emod(res) << '\n';
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int a,p;
  cin >> a >> p;
  int ans = (3*a+p)/2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3608
#include <iostream>

using namespace std;

int main(){
    int A;
    //高橋くんの年齢
    int B;
    //観覧車の料金
    cin >> A >> B;
    if (A >= 13){
        cout << B << endl;
    } else if (A >= 6 && A <= 12){
        cout << B / 2 << endl;
    } else if (0 <= 5){
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vvvi> vvvvi;

ii frac(ll a, ll b) {
    ll gc = __gcd(a, b);
    a /= gc, b /= gc;
    if (a == 0 || b > a) return {0, 1};
    return {a, b};
}

class Comp {
    public:
    bool operator()(ii a, ii b) {
        ll ca = a.F * (b.S / __gcd(a.S, b.S)), cb = b.F * (a.S / __gcd(a.S, b.S));
        if (ca < cb) return true;
        else return false; 
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    priority_queue<ii, vii, Comp> pq;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        pq.push(frac(k, 1));
    }
    for (int i = 0; i < m; ++i) {
        ii v = pq.top();
        pq.pop();
        pq.push(frac(v.F, v.S*2));
    }
    ll ans = 0;
    while (!pq.empty()) {
        ii v = pq.top();
        pq.pop();
        ans += v.F / v.S;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; cin >> n;
	int tmp = -1;
	for(int i = 0; i * (i + 1) <= 2 * n; i++) {
		if(i * (i + 1) == 2 * n) {
			tmp = i;
		}
	}
	if(tmp == -1) {
		cout << "No" << endl;
		return 0;
	}
	
	int tail = 1;
	std::vector<std::vector<int>> vec(tmp + 1, std::vector<int>(tmp, 0));
	for(int i = 0; i < tmp + 1; i++) {
		for(int j = 0; j < i; j++) vec[i][j] = vec[j][i - 1];
		for(int j = i; j < tmp; j++) vec[i][j] = tail++;
	}
	
	cout << "Yes" << endl;
	cout << tmp + 1 << endl;
	for(int i = 0; i < tmp + 1; i++) {
		cout << vec[i].size() << " ";
		for(auto v : vec[i]) cout << v << " ";
		cout << endl;
	}
	return 0;
}


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

using namespace std;

typedef long long ll;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll sw = x;
        int r = 0;
        for (int j = 0; j < n; j++)
        {
            if (j != i && a[j] <= sw)
            {
                sw -= a[j];
                r++;
            }
        }
        ans = max(ans, (ll)(r + (sw == a[i])));
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint dp[2001][2001];
int main() {
    int h, w;
    cin >> h >> w;

    vector<string> a(h);
    rep(i,h){
        cin >> a[i];
    }

    dp[1][1] = 1;
    rep(i,h)rep(j,w){
        if ( i != 0 || j != 0 ) {
            if (a[i][j] == '#') {
                dp[i+1][j+1] = 0;
            } else {
                dp[i+1][j+1] = dp[i][j+1] + dp [i+1][j];
            }
        }
    }
    cout << dp[h][w].x << endl;
}


Measured memory_bytes: 33024
#include <stdio.h>
int main(void)
{
	int i;
	char s[20];
	scanf("%s",s);
	for(i=0; i<19; i++){
		if(i==5 || i==13){
			printf(" ");
		}else{
			printf("%c",s[i]);
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main()
{
	int a,b;
	char o;
	for(int i=1;;i++)
	{
		scanf("%d %c %d",&a,&o,&b);
		if(o=='?')
		{
			break;
		}
		if(o=='+')
		{
			printf("%d\n",a+b);
		}
		else if(o=='-')
		{
			printf("%d\n",a-b);
		}
		else if(o=='*')
		{
			printf("%d\n",a*b);
		}
		else
		{
			printf("%d\n",a/b);
		}
	}
return 0;}

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

int main(){
  long int N, M;

  cin >> N >> M;
  if(N == 1){
    if(M == 1){
      cout << "1" << endl;
      return 0;
    }

    if(M == 2){
      cout << "0" << endl;
      return 0;
    }

    if(M > 2){
      cout << M - 2 << endl;
      return 0;
    }
  }

  if(N == 2){
    cout << "0" << endl;
    return 0;
  }

  if(N > 2){
    if(M == 1){
      cout << N - 2 << endl;
      return 0;
    }

    if(M == 2){
      cout << "0" << endl;
      return 0;
    }

    if(M > 2){
      cout << (N - 2) * (M - 2) << endl;
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int const MAX = 100005;
long long x[MAX];
long long y[MAX];

long long dp[MAX][30]; //iから1<<j-1回移動するとdp[i][j]に着く
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	long long l;
	cin >> l;
	bool flag = 0;
	for (int i = 1; i <= n; i++) {
		y[i] = upper_bound(x + 1, x + n + 1, x[i] + l) - x - 1 ;
		dp[i][0] = i;
		dp[i][1] = y[i];
		if (y[i] < n) {
			flag = 1;
		}
	}
	int cnt = 2;
	while(flag){
		flag = 0;
		int t = 1 << (cnt - 1);
		for (int i = 1; i <= n; i++) {
			dp[i][cnt] = dp[dp[i][cnt - 1]][cnt - 1];
			if (dp[i][cnt] < n) {
				flag = 1;
			}
		}
		cnt++;
	}
	cnt--;
	int q;
	cin >> q;
	for (int aaa = 0; aaa < q; aaa++) {
		int from, to;
		cin >> from >> to;
		if (from > to) {
			swap(from, to);
		}
		int ans = 0;
		int now = from;
		while (now < to) {
			int t = lower_bound(dp[now], dp[now] + cnt, to) - dp[now];
			if (t > 2) {
				t--;
			}
			now = dp[now][t];
			ans += (1 << (t - 1));
		}
		cout << ans << endl;
	}
}

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

//C問題解答例
int main() {
	int N, M; cin >> N >> M;

	vector<vector<int>> vec(M);

	rep(i, M) {
        // 電球iはk個のスイッチに繋がっている
		int k; cin >> k;
        // vector::resize 要素数の変更(vec[M][k]にする)
        // kの値によって要素数がきまる -> 動的な確保が要る
		vec[i].resize(k);
        // 電球iに繋がっているスイッチの番号(1~N)を入力
		rep(j, k) {
			cin >> vec[i][j];
			--vec[i][j]; //0~N-1に調整
		}
	}

    // 電球iは，対応するk個の番号が振られたスイッチのうち，
    // onになっている個数を2で割った余り == p[i] のとき点灯
	vector<int> p(M);
	rep(i, M) cin >> p[i];

	int ans = 0;

    // すべてのスイッチのON/OFFの組みあわせを1つ固定する
    /*
        例えばN=2のとき(入力例1)
        1<<2 == 100 = 4
        000で固定, 001で固定, 010で固定, 011で固定
        固定したすべての組み合わせについて，電球が点灯するかチェックする
    */
	for (int i = 0; i < (1 << N); ++i) {
        // bool ok
        // 固定したスイッチの組み合わせにおいて全電球が点灯するならtrue
        // ひとつでも点灯しない電球があるならfalse
		bool ok = true;
        // 各電球について
		for (int j = 0; j < M; ++j) {
			int sum = 0;
            // 電球jに接続している各スイッチ(番号id)がONであるかどうか調べる
			for (int id : vec[j]) {
                // a & b == aとbのビット単位のANDをとる
                // iのidビット目が立っている <=> スイッチiがON
				if ((i >> id) & 1) {
					sum++;
				}
			}
            // 電球jに接続しているON状態のスイッチが規則に従っていないなら
            // その電球は点灯しない
			if (sum % 2 != p[j]) {
				ok = false;
                break; // 全電球点灯することがなくなったのでbreakできる
			}
		}
        // 全電球点灯するならカウントアップ
		if (ok) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
   int N, W;
   cin >> N >> W;
   vector<int> weight(N), value(N);
   vector<ll> gain(W+1);
   
   for (int i=0; i<N; i++) {
       cin >> weight[i] >> value[i];
   }
   
   for (int i=0; i<N; i++) {
        for (int w=W-weight[i]; w>=0; w--) {
            gain[w+weight[i]] = max(gain[w+weight[i]], gain[w]+(ll)value[i]);
        }    
   }
   
   cout << gain[W] << endl;
   return 0;
}

Measured memory_bytes: 1024
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

S = list(input())
N = len(S)

# dp[i][j] ... S[:i]でj(mod13)をつくる組み合わせの数
dp = [[0] * 13 for _ in range(N + 1)]

dp[0][0] = 1
for i in range(1, N + 1):
    if S[i - 1] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
    else:
        x = ord(S[i - 1]) - ord('0')
        for j in range(13):
            dp[i][(j * 10 + x) % 13] += dp[i - 1][j]
    for j in range(13):
        dp[i][j] %= 1000000007
print(dp[-1][5])


Measured memory_bytes: 66736
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int h[N], f[N], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    f[2] = abs(h[1] - h[2]);
    for (int i = 3; i <= n; i++)
        f[i] = min(abs(h[i] - h[i - 1]) + f[i - 1],
                   abs(h[i] - h[i - 2]) + f[i - 2]);
    printf("%d\n", f[n]);
    return 0;
}

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

int main(void){
  int n, i, cnt, ans;
  scanf("%d", &n);
  char s[n];
  scanf("%s", s);
  cnt=0;
  ans=0;
  for(i=0; i<n; i++){
    if(s[i]=='I')
      cnt++;
    else
      cnt--;
    if(ans<cnt)
      ans=cnt;
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
// 前後で数え上げ
ll N, N2;
void check(string S, map < pair < string, string >, ll >& mp){
    string s1, s2;
    rep(bit,1<<N){
        s1.clear(), s2.clear();
        rep(i,N){
            if(bit & 1<<i)
                s1 += S[i];
            else
                s2 += S[i];
        }
        mp[{s1, s2}]++;
    }
    
}
int main() {
    init();
    cin >> N;
    N2 = 2 * N;
    string S;
    cin >> S;
    string s1 = S.substr(0, N), s2 = S.substr(N, N);
    reverse(all(s2));

    // ペアがいなければ0
    map<char, ll> mp;
    rep(i, N2) mp[S[i]]++;
    bool isok = true;
    repa(p, mp) if (p.second & 1) isok = false;
    if(!isok){
        cout << 0 << endl;
        return 0;
    }

    map<pair<string, string>, ll> mp1, mp2;

    check(s1, mp1), check(s2, mp2);
    ll ans = 0;
    repa(p, mp1){
        ans += p.second * mp2[p.first];
    }
    cout << ans << endl;
}


Measured memory_bytes: 108160
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

list<pair<int, int> > L;

void Write(){

    int l, s; cin >> l >> s;
    for(auto itr = L.begin();;itr++){
        if(itr->first != -1) continue;

        if(itr->second <= s){
            itr->first = l;
            s -= itr->second;
            if(s == 0) return;
        }else{
            itr->second -= s;
            itr = L.insert(itr, {l, s});
            return;
        }
    }

}

void Read(){
    int p; cin >> p;
    p++;
    for(auto itr : L){
        p -= itr.second;
        if(p <= 0){
            cout << itr.first << endl;
            break;
        }
    }



}

void Delete(){

    int l; cin >> l;
    for(auto &itr : L){
        if(itr.first == l){
            itr.first = -1;
        }
    }

}


signed main(){

    while(1){
        int n; cin >> n;
        if(!n) break;
        L.clear();
        L.push_back({-1, 10000000000});

        for(int i = 0; i < n; i++){
            char op; cin >> op;
            if(op == 'W') Write();
            else if(op == 'R') Read();
            else Delete();
                
            //for(auto x : L) cerr << "(" << x.first << ", " << x.second << ") ";
            //cerr << endl;


        }
        cout << endl;
    }
    return 0;
}




Measured memory_bytes: 3276
package main

import "fmt"

func main() {
	var n string
	fmt.Scan(&n)

	switch n {
	case "RRR":
		fmt.Println(3)
	case "RRS", "SRR":
		fmt.Println(2)
	case "SSS":
		fmt.Println(0)
	default:
		fmt.Println(1)
	}
}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	if (n == 3) {
		cout << "2 3 25" << endl;
		return 0;
	}
	int a = n % 3 ? n - 2 : n - 4;
	if (a > 15000)
		a = n % 2 ? 15000 - 1 : 15000;
	for (int i = 1; i <= a; i++)
		cout << i * 2 << ' ';
	for (int i = 0; i < n - a; i++)
		cout << i * 6 + 3 << ' ';
	cout << endl;
	return 0;
}


Measured memory_bytes: 384
def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        S.append(list(map(int,input().split())))

    S.sort()
    #print(S)

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

        ans[i] %= mod
        acc[i] = (acc[i-1]+ans[i])%mod


    print(ans[N-1])


main()


Measured memory_bytes: 24532
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

#define X 0
#define Y 1
#define M 1000000007

int N;
string s1, s2;

long long ans = 1;

long long num(int prev, int cur)
{
    int ret;

    if(prev == X && cur == X)
    {
        ret = 2;
    }
    else if(prev == X && cur == Y)
    {
        ret = 2;
    }
    else if(prev == Y && cur == X)
    {
        ret = 1;
    }
    else if(prev == Y && cur == Y)
    {
        ret = 3;
    }
    else if(prev == -1 && cur == X)
    {
        ret = 3;
    }
    else if(prev == -1 && cur == Y)
    {
        ret = 6;
    }
    return ret;
}

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

    int prev = -1, cur = -1;

    for (int i = 0; i < N;i++)
    {
        if(s1[i] == s2[i])
        {
            cur = X;
        }
        else
        {
            cur = Y;
            i++;
        }
        ans = (ans * num(prev, cur)) % M;
        prev = cur;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>

#define rep(i,p) for(int i=1;i<=p;i++)
#define ll long long

using namespace std;

int main(){

 string S;
 ll int N;

 cin >> N;
 cin >> S;
	 bool b1 = false;

 if (N%2!=0){
 }

 else{
	  b1 = true;
	 for(int i=0;i<N/2;i++){
		 if(S[i]!=S[i+N/2]){
			 b1 = false;
		 }
		 else{}
	 }
 }
	 if(b1){
		 cout << "Yes";
	 }
             
 


else{

	 cout << "No";
}


	return 0;

}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include<vector>
#include<climits>
#include<set>
#include<string>
#include<map>
#define ll long long
#define fr(j,p) for (int i=j; i<p ;i++)
#define fastScan ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define inp(x,n) fr(0,n) cin>>x[i];
#define out(x,n) fr(0,n) cout<<x[i]<<" ";
#define test int t; cin>>t; while(t--)
#define YESF if(flag==0)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define yesf if(flag==0)cout<<"Yes"<<endl; else cout<<"No"<<endl; 
const long long md=1e9+7;
using namespace std;
int main()
{
  fastScan
  //test
  {
    ll n, k;

    cin>>k>>n;


    ll arr[n];
    for(int i=0; i<n ; i++)
    {
      cin>>arr[i];

    }


    sort(arr,arr+n);

    ll ans = k;

    for(int i=0; i<n ; i++)
    {
      ll temp = arr[(i+n-1)%n]- arr[i];

      if(temp < 0)
        temp+=k;

      ans = min(ans , temp);
    }


    cout<<ans<<endl;






   
    

   
      
  } 
     return 0;
  
}

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

int main() {
  string s;
  cin >> s;
  
  vector<string> t;
  for (int i=0; i<(int)s.size(); i++){
    if (s.at(i) == '1') t.push_back("1");
    if (s.at(i) == '0') t.push_back("0");
    if (s.at(i) == 'B' && t.empty() == false) t.pop_back();
  }
  
  for (int i=0; i<(int)t.size(); i++){
    cout << t.at(i);
  }
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int,int> PI;
int main(){
    int n;
    scanf("%d",&n);
    PI num[n];
    for(int i=0;i<n;i++){
        scanf("%d",&(num[i].first));
        num[i].second=i;
    }
    sort(num,num+n);
    int ans[n];
    for(int i=0;i<n;i++){
        if(i<n/2)ans[num[i].second]=num[n/2].first;
        else ans[num[i].second]=num[n/2-1].first;
    }
    for(int i=0;i<n;i++)printf("%d\n",ans[i]);
}


Measured memory_bytes: 4480
import numpy as np

N = int(input())
C, S, F = [], [], []
for _ in range(N - 1):
    c, s, f = map(int, input().split())
    C.append(c)
    S.append(s)
    F.append(f)
# cumsum_C = np.array(C)[::-1].cumsum()
# print(f'{cumsum_C=}')

for i in range(N):
    x = 0
    for j in range(i, N - 1):
        if S[j] > x:
            x = S[j]
        else:
            # S[j] + a * F[j] > x
            a = ((x - S[j]) + (F[j] - 1)) // F[j]
            x = S[j] + F[j] * a
        x += C[j]
        # print(f'{x=}')
    print(x)
# T = [0] * (N - 1)
# T[-1] = C[-1] + S[-1]
# for i in range(N - 2, -1, -1):
#     if C[i] + S[i] > S[i + 1]:
#         T[i] = C[i] + S[i]
#     else:
#         T[i] = C[i] + S[i] + C[i + 1]
# 後ろから考えていき、その駅の始発に乗れない場合はプラスで待ち時間を加える
# 後ろからのCのcumsumがいる
# 12 24 6 -> 12 + 24 > 16 -> 12 + 24 + 0 + 52 + 99
# 52 16 4 -> 52 + 16 > 2 -> 52 + 16 + 99
# 99 2 2 -> 101

# やっぱりDPっぽくする必要ありそう？


Measured memory_bytes: 27212
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--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 (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int row[2020][2020];
int line[2020][2020];

signed main() {
  INIT;
  VAR(int,h,w);
  VEC(string,s,h);

  // r
  REP(hi,h){
    REP(wi,w){
      if (s[hi][wi] == '#') {
        row[hi][wi] = 0;
        continue;
      }
      if(wi>0) row[hi][wi] = row[hi][wi-1] + 1;
      else row[hi][wi] = 1;
    }

    RREP(wi,w){
      if (row[hi][wi] == 0) continue;
      if(wi+1<w) row[hi][wi] = max(row[hi][wi+1], row[hi][wi]);
    }
  }


    // l
  REP(wi,w){
    REP(hi,h){
      if (s[hi][wi] == '#') {
        line[hi][wi] = 0;
        continue;
      }
      if(hi>0) line[hi][wi] = line[hi-1][wi] + 1;
      else line[hi][wi] = 1;
    }
    RREP(hi,h){
      if (line[hi][wi] == 0) continue;
      if(hi+1<h) line[hi][wi] = max(line[hi+1][wi], line[hi][wi]);
    }
  }

  int ans = 0;
  REP(hi,h){
    REP(wi,w){
      if (s[hi][wi] == '#') continue;
      int tmp = row[hi][wi]+line[hi][wi]-1;
      ans = max(ans, tmp);
    }
  }
  OUT(ans)BR;

  /*
  REP(hi,h){
    REP(wi,w)
    debug(row[hi][wi]);
  }
  
  REP(hi,h){
    REP(wi,w)
      debug(line[hi][wi]);
    
  }
  */
  
  return 0;
}


Measured memory_bytes: 67968
/*
    BY - Darkworld1 ( Tanu kumar )
    college - AIT
    Problem - contest ( div 3 )
*/
#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll  long long
#define PB push_back
#define ld long double
#define ff first
#define ss second
# define st(v) (v).begin(),(v).end()
#define rep(i,a,n) for( int i = a ; i < n ; i++ )
#define prep( i, a , n ) for ( int i = a ; i>= n ; i--)
#define   pr pair<int,int>
const int N = 13 , M=N,inf=(int)1e9;
const int mod=1e9+7;
int fastAbs(int n) { return (n ^ (n >> 31)) - (n >> 31); }
ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
ll ans ;
map< pair<int,int> , int > mp;
const int dx[4] = {1,0,0,-1};
const int dy[4] = {0,-1,1,0};
void solve(){

      ll n , m ;
      cin >> n >> m ;
      ll ans = 1 ;
      for ( ll i = m/n ; i >0  ; i--){
                if( m % i == 0 && (m/i>=n) ){
                        /*ll q = (m/i)/n;
                        ll r =  (m/i)%n;
                        ans = __gcd(q*i , (q*i+(r>0?1:0)*i));*/
                        cout << i;
                        return ;
                }
      }
      cout << ans ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q=1;
    //cin >> q;
    while(q--)
        solve();
}
/*
    ---------------- lemmas-----------------------------------
   1)
   2)
   3)

*/


Measured memory_bytes: 256
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, a, b = map(int, input().split())
    s = input()
    for ch in s:
        ans = 'Yes'
        if ch == 'c':
            ans = 'No'
        elif ch == 'a':
            if a > 0:
                a -=1
            elif b > 0:
                b -= 1
            else:
                ans = 'No'
        else:
            if b > 0:
                b -= 1
            else:
                ans = 'No'
        print(ans)


if __name__ == '__main__':
    main()

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

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int> V(n);
	for(int i=0;i<n;i++) cin>>V[i];
	vector<bool> dp(k+5,false);
	for(int i=1;i<=k;i++)
	{
		for(int j=0;V[j]<=i&&j<n;j++)
		{
			if(dp[i-V[j]]==false) {dp[i]=true;break;}
			dp[i]=false;
		}
	}
	if(dp[k]) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n;
    string s;
    vector<int> v;

    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (i == 0) v.push_back(s[i] == 'E');
        else v.push_back((s[i] == 'E') + v[i - 1]);
    }

    int c = 100000000;
    for (int i = 0; i < n; i++) {
        int l = i == 0 ? 0 : i - v[i - 1];
        int r = i == n - 1 ? 0 : v[n - 1] - v[i];
        c = min(c, l + r);
    }

    cout << c << endl;
}

Measured memory_bytes: 2812
n=gets.to_i
v=gets.chomp.split.map(&:to_i)
v1=[]
v2=[]

h1 = Hash.new(0)
h2 = Hash.new(0)
v.each_with_index do |w, i|
    if i%2==0
        v1 << w
        h1[w] += 1
    else
        v2 << w
        h2[w] += 1
    end
end

hh1 = h1.to_a.sort {|a,b| a[1] <=> b[1]}.reverse
hh2 = h2.to_a.sort {|a,b| a[1] <=> b[1]}.reverse

#p hh1
#p hh2

# 最頻値の数が同じ
if hh1[0][1] == hh2[0][1]
    # 最頻値の値も同じ
    if hh1[0][0] == hh2[0][0]
        if hh1[0][1] == n/2
            puts n/2
        else 
            puts n - hh1[0][1] - [hh1[1][1], hh2[1][1]].max
        end
    else
        if hh1[0][1] == n/2
            puts 0
        else
            puts n - 2 * hh1[0][1]
        end
    end
else
    puts n - hh1[0][1] - hh2[0][1]
end


Measured memory_bytes: 22076
import sys
import math
input = lambda: sys.stdin.readline().rstrip()


def factorize(n):
    b = 2
    fct = set()
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct |= set([b])
        b = b + 1
    if n > 1:
        fct |= set([n])
    return fct


def solve():
    A, B = map(int, input().split())
    ap = factorize(A)
    bp = factorize(B)
    ans = 1 + len(ap & bp)
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38384
#include <iostream>
#include <cstdio> 
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

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

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    int n, k;cin >> n >> k;
    vector<int> l(n);
    for(int i=0;i<n;i++) cin >> l[i];
    sort(l.begin(), l.end());
    reverse(l.begin(), l.end());

    int ans = 0;
    for(int i=0;i<k;i++){
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N; cin >> N;
  vector<int> H(N);
  rep(i, N) cin >> H[i];
  
  int ans = 0;
  int k = 0;
  
  rep(i, N-1) {
    if(H[i] >= H[i+1]) {
      k++;
    } else {
      ans = max(ans, k);
      k = 0;
    }
  }
  ans = max(ans, k);
  
  cout << ans << endl;
  
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
signed main(){
  long long ans, a,b,c,h=20190430;
  char r;
  cin>>a>>r>>b>>r>>c;
  ans=c+b*100+a*10000;
  if(h>=ans)
    cout<<"Heisei"<<'\n';
  else
    cout<<"TBD"<<endl;

  return(0);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; typedef long double ld;
const int INF32 = 1e9+10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  array<int,3> PY[100010];
  for (int i = 0; i < M; i++) {
    int p, y; cin >> p >> y;
    PY[i][0] = p; PY[i][1] = y; PY[i][2] = i;
  }
  sort(PY, PY+M);
  string ans[100010];
  int preP; int num = 1;
  for (int i = 0; i < M; i++) {
    string s = "";
    int p = PY[i][0];
    if (to_string(p).length() < 6) {
      for (int j = 0; j < 6-to_string(p).length(); j++) {
        s += "0";
      }
    }
    s += to_string(p);
    if (preP == p) {
      num++;
    } else {
      num = 1;
    }
    if (to_string(num).length() < 6) {
      for (int j = 0; j < 6-to_string(num).length(); j++) {
        s += "0";
      }
    }
    s += to_string(num);
    ans[PY[i][2]] = s;
    preP = p;
  }
  for (int i = 0; i < M; i++) {
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 9728
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
N = len(S)+1
A = [0]*N
B = [0]*N

tmp = 0
for i in range(N-1):
    if S[i] == "<":
        tmp += 1
        A[i+1] = tmp
    else:
        tmp = 0

tmp = 0
for i in range(N-1):
    if S[N-i-2] == ">":
        tmp += 1
        B[i+1] = tmp
    else:
        tmp = 0

B = B[::-1]

C = [0]*N
for i in range(N):
    C[i] = max(A[i], B[i])

print(sum(C))


Measured memory_bytes: 33444
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

ll N, A[100000 + 10];

const ll MOD = 1000000007;

vector<ll> memo[100000 + 10];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> A[i];

	for (int i = 0; i <= N; i++)memo[i].resize(3, 0);
	ll ans = 1;
	for (int i = 0; i < N; i++) {
		if (count(memo[i].begin(), memo[i].end(), A[i]) == 0) {
			cout << 0 << endl;
			return 0;
		}
		ans *= count(memo[i].begin(), memo[i].end(), A[i]);
		ans %= MOD;
		memo[i + 1] = memo[i];
		int idx = find(memo[i + 1].begin(), memo[i + 1].end(), A[i]) - memo[i + 1].begin();
		memo[i + 1][idx]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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 (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int mod=1e9+7;
vector<int> Zalgo(string s){
  int m=s.size();
  vector<int> res(m);
  res[0]=m;
  int i=1,j=0;
  while(i<m){
    while(i+j<m&&s[j]==s[j+i]){
      j++;
    }
    res[i]=j;
    if(j==0){
      i++;
      continue;
    }
    int k=1;
    while(i+k<m&&k+res[k]<j){
      res[i+k]=res[k];
      k++;
    }
    i+=k,j-=k;
  }
  return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    string s;cin >> s;
    int ans=0;
    for(int i=0;i<n;i++){
        string t=s.substr(i);
        auto lcp=Zalgo(t);
        for(int j=0;j<t.size();j++){
            chmax(ans,min(lcp[j],j));
        }
    }
    cout << ans << endl;
}

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

const int MAX_N = 1e5, A = 1e9 + 7;
int n, k;
int a[MAX_N];

int po(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) ans = static_cast<long>(ans) * x % A;
        x = static_cast<long>(x) * x % A;
        y >>= 1;
    }
    return ans;
}

int fac[MAX_N + 1], inv[MAX_N + 1];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);

    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = static_cast<long>(fac[i - 1]) * i % A;
    }
    inv[n] = po(fac[n], A - 2);
    for (int i = n - 1; i >= 0; i--) {
        inv[i] = static_cast<long>(inv[i + 1]) * (i + 1) % A;
    }
    
    int ans = 0;
    for (int i = 0; i < n - k + 1; i++) {
        ans = (-(static_cast<long>(fac[n - i - 1]) * inv[k - 1] % A
            * inv[n - k - i] % A) * a[i] + A + ans) % A;
    }
    for (int i = k - 1; i < n; i++) {
        ans = (ans + static_cast<long>(fac[i]) * inv[k - 1] % A
            * inv[i - k + 1] % A * a[i]) % A;
    }

    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1280
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
#define ll long long

int main(){
	int N;
	cin>>N;
	ll ans=0;
	for(ll i=1;i<=N-1;i++){
		ll tmp=0;
		for(ll j=0;j<1000;j++)tmp+=i;
		ans+=tmp/1000;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int main()
{
	IO;
	string s;
	cin>>s;
	if(s[1]=='B'){
		cout<<"ARC"<<endl;
	}else{
		s[1]='B';
		cout<<s<<endl;
	}
 	return 0;
}







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

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
#define ll long long
using namespace std;


const int inf = (int)1e9 + 7;
const int N = (int)3e5 + 7;

int n,a,b;
vector <int> v;
int cnt,cnt1;

 main () {
    cin >> n >> a >> b;

    if (n + 1 < a + b || n < a || n < b) {
        cout << "-1";
        return 0;
    }
    else {
        for (int i = n - a + 1; i <= n; i ++)
            v.pb(i);

        int o = b - 1;
        if (o == 0 && a != n) {
            cout << -1 << endl;
            return 0;
        }
        if (o > 0) {
            int k = int((n - a) / o) * o + 1;

            if (((n - a + o - 1) / o) > a) {
                cout << "-1";
                return 0;
            }
            for (int j = 1; j <= ((n - a + o - 1) / o); j ++) {
                for (int i = min(n - a,(o * j)); i >= o * (j - 1) + 1; i --) {
                    v.pb(i);
                    if (i == k)
                        break;
                }
            }
        }
//
//        for (int i = a; i < v.size(); i ++) {
//            if (v[i] > v[i - 1])
//                cnt ++;
//        }
//        for (int i = 1; i < v.size(); i ++) {
//            if (v[i] < v[i - 1])
//                cnt1 ++;
//        }
//        if (cnt + 1 > a || cnt1 + 1 != b) {
//            cout << -1;
//            return 0;
//        }
        for (int i = 0; i < v.size(); i ++)
            cout << v[i] << " ";
    }
}

Measured memory_bytes: 3440
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#include <atcoder/all>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll T;
    cin >> T;
    REP(i, 0, T) {
        ll N, M, A, B;
        cin >> N >> M >> A >> B;
        cout << floor_sum(N, M, A, B) << endl;
    }
}


Measured memory_bytes: 3584
#include <iostream>
#include<vector>
#include <string>
#include<algorithm>
using namespace std;
typedef long long  ll;

int main() {
	int n;
	vector<ll> A;
	ll ans = 0;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		A.emplace_back(x);
	}
	sort(A.begin(), A.end());
	for (int i = 1; i < n ; i++) {
			ans += A[n-1 - i / 2];
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 5368