akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return a*(ll)b%mod;}
void inc(int&a,int b){(a+=b)%=mod;}
int pow(int a,int b){
    int s=1;
    while(b){
        if(b&1)s=mul(s,a);
        a=mul(a,a);
        b>>=1;
    }
    return s;
}
vector<int>g[60];
int fac[210],rfac[210],k;
int C(int n,int k){return mul(fac[n],mul(rfac[k],rfac[n-k]));}
int dfn[60],low[60],stk[60],tp,M,ans;
set<int>s;
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int burnside(int n){
    int i,s=0;
    for(i=1;i<=n;i++)inc(s,pow(k,gcd(i,n)));
    return mul(s,pow(n,mod-2));
}
void dfs(int x){
    int t,n,m;
    dfn[x]=low[x]=++M;
    stk[++tp]=x;
    for(int y:g[x]){
        if(!dfn[y]){
            dfs(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                s.clear();
                do{
                    t=stk[tp--];
                    s.insert(t);
                }while(t!=y);
                s.insert(x);
                n=s.size();
                m=0;
                for(int x:s){
                    for(int y:g[x]){
                        if(s.count(y))m++;
                    }
                }
                m>>=1;
                if(m<n)ans=mul(ans,k);
                if(n==m)ans=mul(ans,burnside(m));
                if(n<m)ans=mul(ans,C(m+k-1,k-1));
            }
        }else
            low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    int n,m,i,x,y;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    fac[0]=1;
    for(i=1;i<=m+k;i++)fac[i]=mul(fac[i-1],i);
    rfac[m+k]=pow(fac[m+k],mod-2);
    for(i=m+k;i>0;i--)rfac[i-1]=mul(rfac[i],i);
    ans=1;
    for(i=1;i<=n;i++){
        if(!dfn[i])dfs(i);
    }
    printf("%d",ans);
}

Measured memory_bytes: 256
#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<ll> over;
vector<ll> under;
ll a[MAXN], b[MAXN];
int n;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	ll sunder = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > b[i]) {
			over.push_back(a[i] - b[i]);
		} else if (a[i] < b[i]) {
			under.push_back(b[i] - a[i]);
			sunder += b[i] - a[i];
		}
	}
	sort(over.begin(), over.end());
	reverse(over.begin(), over.end());
	if (sunder == 0) {
		cout << 0 << endl;
		return 0;
	}
	ll sover = 0;
	for (int i = 0; i < over.size(); i++) {
		sover += over[i];
		if (sover >= sunder) {
			cout << i + 1 + under.size() << endl;
			return 0;
		}
	}
	cout << "-1" << endl;
	return 0;
}


Measured memory_bytes: 5820
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
int N, x, y, ans[20010]={0};
Graph G(20010);
int bfs(int start){
    int i;
 // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[start] = 0;
    que.push(start); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない
            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
            if(nv>start) ans[dist[nv]]++;
        }
    }
}
int main(){
    int i;
    cin >> N >> x >> y;
    x--;y--;
    for(i=0;i<N-1;i++){
        G[i].push_back(i+1);
        G[i+1].push_back(i);
    }
    G[x].push_back(y);
    G[y].push_back(x);
    for(i=0;i<N-1;i++){
        bfs(i);
    }
    for(i=1;i<N;i++){
        cout << ans[i] <<endl;
    }
    
    return 0;
}

Measured memory_bytes: 768
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define NDEBUG
#define debug(...)
#define IFD(...)
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <cassert>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <sstream>
#include <iostream>
#include <iomanip>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = static_cast<int>(a); i <= static_cast<int>(b); ++i)
#define FORD(i, b, a) for (int i = static_cast<int>(b); i >= static_cast<int>(a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

struct dpdata
{
    int a, b, c;

    int size()
    {
        return a;
    }
};

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

    string s, t;
    cin >> s >> t;

    vector dp(s.size() + 1, vector<dpdata>(t.size() + 1, {0, -1, -1}));
    // dp[i][0], dp[0][j] = "";
    FOR(i, 1, s.size())
    {
        FOR(j, 1, t.size())
        {
            if (dp[i][j].size() < dp[i - 1][j].size())
            {
                dp[i][j] = dp[i - 1][j];
            }
            if (dp[i][j].size() < dp[i][j - 1].size())
            {
                dp[i][j] = dp[i][j - 1];
            }
            if (s[i - 1] == t[j - 1] and dp[i][j].size() < dp[i - 1][j - 1].size() + 1)
            {
                dp[i][j] = {dp[i - 1][j - 1].size() + 1, i - 1, j - 1};
            }
        }
    }

    string ans;
    {
        stringstream ss;
        auto [a, i, j] = dp[s.size()][t.size()];
        while (i != -1 and j != -1)
        {
            ss << s[i];
            auto [aa, ii, jj] = dp[i][j];
            a = aa;
            i = ii;
            j = jj;
        }
        ans = ss.str();
        reverse(ans.begin(), ans.end());
    }

    cout << ans << '\n';

    return 0;
}


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

int sum(int dp[][3][3], int i, int j)
{
    int ans;
    int k;
    ans = 0;
    
    for (k = 0; k < 3; k++){
        if (dp[i][j][k] != -1){
            ans += dp[i][j][k];
        }
    }
    return (ans);
}

int main(void)
{
	int n, k;
	int dp[100][3][3];
	int day, m;
	int i, j;
	int ans;
	
	scanf("%d%d", &n, &k);
	memset(dp, 0, sizeof(dp));
	
    for (i = 0; i < k; i++){
		scanf("%d%d", &day, &m);
        dp[day - 1][m % 3][0] = dp[day - 1][m % 3][1] = dp[day - 1][m % 3][2] = -1;
        dp[day - 1][(m + 1) % 3][0] = dp[day - 1][(m + 1) % 3][1] = dp[day - 1][(m + 1) % 3][2] = -1;
    }
    
	for (i = 0; i < 3; i++){
		for (j = 0; j < 3; j++){
            if (dp[1][i][j] != -1 && dp[0][j][0] != -1 && dp[0][j][1] != -1 && dp[0][j][2] != -1){
                dp[1][i][j] = 1;
            }
		}
	}
	
	for (i = 2; i < n; i++){
		for (j = 0; j < 3; j++){
            if (dp[i][j][j] != -1){
			    dp[i][j][j] = (sum(dp, i - 1, j) - (dp[i - 1][j][j] != -1 ? dp[i - 1][j][j] : 0)) % 100000;
            }
            if (dp[i][j][(j + 1) % 3] != -1){
			    dp[i][j][(j + 1) % 3] = sum(dp, i - 1, (j + 1) % 3) % 100000;
            }
            if (dp[i][j][(j + 2) % 3] != -1){
                dp[i][j][(j + 2) % 3] = sum(dp, i - 1, (j + 2) % 3) % 100000;
            }
		}
	}
	
	ans = (sum(dp, n - 1, 0) + sum(dp, n - 1, 1) + sum(dp, n - 1, 2)) % 10000;
	printf("%d\n", ans);
	
	return (0);
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <iostream>
#define MN 301000
#define mod 1000000007

int f[MN][2][4]; //?? 0? 00 01
char s[MN];
int cnt[MN];

void rw(int &a, int b) {a = (a + b) % mod;}

int main()
{
	scanf("%s", s);
	int len = strlen(s);
	cnt[len] = 1;
	for(int i = len - 1; i >= 0; i--) 
	{
		cnt[i] = cnt[i + 1];
		if(s[i] == '?') cnt[i] = 2 * cnt[i] % mod;
	}
	f[0][0][0] = 1;
	int ans = 0;
	for(int i = 0; i < len; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			for(int k = 0; k < 4; k++)
			{
				if(s[i] == '0' || s[i] == '?')
				{
					if(k == 0 || k == 2 || k == 3) rw(f[i + 1][j][1], f[i][j][k]);
					if(k == 1) rw(f[i + 1][j][2], f[i][j][k]);
				}
				if(s[i] == '1' || s[i] == '?')
				{
					if(k == 0 || k == 3)
					{
						if(j == 1) rw(ans, 1ll * f[i][j][k] * cnt[i + 1] % mod);
						else rw(f[i + 1][j + 1][0], f[i][j][k]);
					}
					if(k == 1) rw(f[i + 1][j][3], f[i][j][k]);
					if(k == 2) rw(f[i + 1][j][1], f[i][j][k]);
				}
			}
		}
	}
	rw(ans, f[len][1][0]);
	rw(ans, f[len][1][3]);
	printf("%d\n", ans);
}

//如果知道 S，可以从左往右贪心，有1就留，否则凑足3个合并(最左边为0)，然后DP一下方案数 

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

int main(){
  string s;
  cin>>s;
  string pat[4]={"dream","dreamer","eraser","erase"};
  int pos=s.length();
  while(pos>0){
    bool ok=0;
    rep(d,4){
      if(pos>=(int)pat[d].length()&&s.substr(pos-pat[d].length(),pat[d].length())==pat[d]){
	ok=1;
	pos-=pat[d].length();
      }
    }
    if(!ok)break;
  }
  cout<<(pos==0?"YES":"NO")<<endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>



#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))

using namespace std;
string s1,s2,s3;
int a,b,c;
char now;
int main(){
  cin >> s1 >> s2 >> s3;
  now = 'a';
  a = 0;
  while(1){
    if(a>s1.size()){
      cout << "A" << endl;
      return 0;
    }
    if(b>s2.size()){
      cout << "B" << endl;
      return 0;
    }
    if(c>s3.size()){
      cout << "C" << endl;
      return 0;
    }
    if(now=='a'){
      now = s1[a];
      a++;
    }
    else if(now=='b'){
      now = s2[b];
      b++;
    }
    else if(now=='c'){
      now = s3[c];
      c++;
    }
    //cout << a << " " << b << " " << c << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
#define NMAX 100005
#define LAST 1000000000002
map<ll,int> tab;

int main()
{   
    ll n;
    cin>>n;
    int ans = 0;
    for (int i = 2; i < 1000000; ++i)
    {   int k = 0;
        while(n%i==0){
            n/=i;
            k++;
        }
        for(int j=1 ; j<=k ; j++){
            k-=j;
            if(k<0){
                break;
            }
            ans++;
        }
    }
    if(n>1)ans++;
    cout<<ans;
   return 0;
}


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

int ar[1005];
int main(){
    int n,k,sum=0;
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>ar[i];
    }
    sort(ar+1,ar+n+1);
    for(int i=1;i<=k;++i){
        sum+=ar[i];
    }
    cout<<sum<<endl;
   return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <typeinfo>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int main(){

    string str;
    vector<int> v(26,0);

    while(getline(cin, str)){
        transform(str.begin(), str.end(), str.begin(), ::tolower);
        for(int i=0; i<str.length(); i++){
            if('a'<=str[i] && str[i]<='z'){
                v[str[i]-'a'] += 1;
            }
        }
    }
    //
    // getline(cin, str);





    for(int i=0; i<26; i++){
        cout << char(i+97) << " " << ":" << " " << v[i] << endl;
    }




    return 0;
}



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

using namespace std;

const long MAX = 510000;
const long MOD = 1000000007;

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

// テーブルを作る前処理
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(){
    int N, K;
    cin >> N >> K;

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

    sort(A, A+N);

    COMinit();

    long ans = 0;
    for(int i=N-1; i>=0; i--){
        ans = ans + A[i]*COM(i, K-1) - A[i]*COM(N-i-1, K-1);
        ans = ans % MOD;
    }

    printf("%ld\n", ans);

    return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A, B, C, X, Y; cin >> A >> B >> C >> X >> Y;
    int ulim = max(X, Y)*2;
    int ans = INF;
    for(int i = 0; i <= ulim; i+=2){
        int remA = X - i/2;
        int remB = Y - i/2;
        ans = min(ans, i*C + max(0, remA)*A + max(0, remB)*B);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
ll longinf=1ll<<60;
int inf=1<<29;
int dh[]={1,-1,0,0};
int dw[]={0,0,1,-1};
//mleしなければぜんぶllでかく。

int main(){
      cin.tie(0);
      ios::sync_with_stdio(false);
      double t,x;
      cin>>t>>x;
      cout<<setprecision(10)<<t/x<<endl;
      return 0;
}

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

using namespace std;

int main(){
    string S;
    while(cin >> S){
        const int n = S.size();
        int res = n;
        for(int i=0;i+1<n;i++){
            if(S[i] == S[i+1]) continue;
            res = min(res, max(i+1, n-(i+1)));
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define inf 2123333333

struct node { int t,next; }a[4010];

pii h[2010];

int ans=inf;
int head[2010],mn[2010],size[2010],sum[2010],n,tt,tot;
char s[2010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void add(int x,int y) { a[++tot].t=y;a[tot].next=head[x];head[x]=tot; }

inline void pre_dfs(int x,int y)
{
	size[x]=(s[x]=='1');
	sum[x]=0;
	for (int i=head[x];i;i=a[i].next)
	{
		int t=a[i].t;
		if (t==y) continue;
		pre_dfs(t,x);
		size[x]+=size[t];
		sum[x]+=sum[t]+size[t];
	}
}

inline void dfs(int x,int y)
{
	int son=0;
	for (int i=head[x];i;i=a[i].next)
	{
		int t=a[i].t;
		if (t==y) continue;
		dfs(t,x);son++;
	}
	if (!son) { mn[x]=0;return; }
	if (son==1)
	{
		int t=0;
		for (int i=head[x];i;i=a[i].next) if (a[i].t!=y) { t=a[i].t;break; }
		mn[x]=mn[t]+size[t];
		return;
	}
	tt=0;
	for (int i=head[x];i;i=a[i].next) if (a[i].t!=y) h[++tt]=pii(sum[a[i].t]+size[a[i].t],a[i].t);
	sort(h+1,h+tt+1);
	int s=0;
	for (int i=1;i<tt;i++) s+=h[i].first;
	if (s>=h[tt].first)
	{
		if ((s+h[tt].first)&1) mn[x]=1;
		else mn[x]=0;
		return;
	}
	int hh=mn[h[tt].second]+size[h[tt].second];
	if (s>=hh)
	{
		if ((s+hh)&1) mn[x]=1;
		else mn[x]=0;
		return;
	}
	mn[x]=hh-s;
}

inline void gao(int rt)
{
	pre_dfs(rt,0);
	if (sum[rt]&1) return;
	dfs(rt,0);
	if (mn[rt]==0) ans=min(ans,sum[rt]/2);
}

int main()
{
	n=rd();tot=0;
	scanf("%s",s+1);
	for (int i=1;i<n;i++) { int x=rd(),y=rd();add(x,y);add(y,x); }
	for (int i=1;i<=n;i++) gao(i);
	if (ans==inf) puts("-1");
	else printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<int>A(N+2);
    int sum = 0;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        sum+=abs(A[i]-A[i-1]);
    }
    sum+=abs(A[N]);
    for(int i = 1; i <= N; i++) {
        cout << sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]) << endl;
    }
}


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

int main()
{
    ll N;
    cin >> N;
    vector<ll> B(pow(10,5),0);
    vector<ll> a(N);

    for(int i = 0; i < N; i++)
    {
        cin >> a.at(i);
        if(a.at(i) != 0)B.at(a.at(i)-1)++;
        if(a.at(i) != pow(10,5)-1)B.at(a.at(i)+1)++;
        B.at(a.at(i))++;
    }

    ll xmax = 0;

    for(int i = 0; i < B.size(); i++)
    {
        xmax = max(xmax,B.at(i));
    }

    cout << xmax << endl;
}

Measured memory_bytes: 1792
N = int(input())
A = [int(i) for i in input().split()]

m = 1000
s = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        m += s*A[i]
        s = 0
    else:
        s += m//A[i]
        m %= A[i]

print(m+s*A[-1])


Measured memory_bytes: 61896
#!python3

from time import perf_counter
tick = perf_counter() + 1.90

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from random import randrange
from bisect import bisect

def resolve():
    it = map(int, sys.stdin.read().split())
    D = next(it)
    C = [next(it) for i in range(26)]
    S = [[next(it) for i in range(26)] for i in range(D)]
    L = [[-1] for i in range(26)]
    T = [0] * D

    def update(di, qi):
        T1, L1 = T[:], L[:]

        score = 0
        t0 = T[di]
        score += S[di][qi]-S[di][t0]
        T1[di] = qi

        L1[t0] = li = L[t0][:]
        ii = li.index(di)
        la = D if len(li)-1 == ii else li[ii+1]
        score -= C[t0] * (di-li[ii-1])*(la-di)
        li.pop(ii)

        L1[qi] = li = L[qi][:]
        ii = bisect(li, di)
        li.insert(ii, di)
        la = D if len(li)-1 == ii else li[ii+1]
        score += C[qi] * (di-li[ii-1])*(la-di)

        return score, T1, L1

    score = 0
    x = (1+D)*D//2
    for i in range(D):
        score += S[i][0]
        L[0].append(i)

    for i in range(1, 26):
        score -= C[i] * x

    while perf_counter() < tick:
        diff, T1, L1 = update(randrange(0, D), randrange(0, 26))
        if diff > 0:
            score += diff
            T, L = T1, L1

    print(*(i+1 for i in T), sep="\n")

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 94692
n = int(input())
li = []

for i in range(n):
    a, b = list(map(int, input().split()))
    li.append([a,b])
li = li[::-1]
ans = 0
for ind, (a, b) in enumerate(li):
    ans += -a%b
    if not ind == n-1:
        li[ind+1][0] += ans
print(ans)

Measured memory_bytes: 23908
#include<iostream>
#include<queue>
using namespace std;
int n, d[100], M[100][100];
queue<int>q;
void bfs(int u){
	q.push(u);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int i=0; i<n; i++){
			if(M[v][i]==1 && d[i]==-1){
				d[i]=d[v]+1;
				q.push(i);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++)
			M[i][j]=0;
	}
	for(int i=0; i<n; i++)
		d[i]=-1;
	d[0]=0;
	for(int i=0; i<n; i++){
		int id,k;
		cin>>id>>k;
		for(int j=0; j<k; j++){
			int child;
			cin>>child;
			M[id-1][child-1]=1;
		}
	}
	bfs(0);
	for(int i=0; i<n; i++)
		cout<<i+1<<" "<<d[i]<<endl;
	return 0;
}


Measured memory_bytes: 3116
import java.lang.Math.abs

fun main(args:Array<String>):Unit {
    while (true) {
        val (n, m) = readLine()!!.trim().split(' ').map(String::toInt)
        if (n == 0 && m == 0) return
        val stones = Array(n){
            val a = readLine()!!.trim().split(' ').map(String::toInt).toIntArray()
            (1 .. a[0]).map{
                Stone(a[it * 2 - 1], a[it * 2])
            }.toTypedArray()
        }
        val dangers = stones.map{
            Array(it.size){Array(m + 1){Int.MAX_VALUE}}
        }.toTypedArray()
        for (i in 0 until dangers[0].size){
            dangers[0][i][m] = 0
        }
        if (m > 0) for (i in 0 until dangers[1].size){
            dangers[1][i][m - 1] = 0
        }
        for (line in 1 until n){
            for (from in 0 until dangers[line - 1].size){
                for (to in 0 until dangers[line].size){
                    for (d in 0 .. m){
                        if (dangers[line][to][d] - stones[line - 1][from].jumpTo(stones[line][to]) > dangers[line - 1][from][d]){
                            dangers[line][to][d] = dangers[line - 1][from][d] + stones[line - 1][from].jumpTo(stones[line][to])
                        }
                    }
                }
            }
            if (line > 1){
                for (from in 0 until dangers[line - 2].size){
                    for (to in 0 until dangers[line].size){
                        for (d in 1 .. m){
                            if (dangers[line][to][d - 1] - stones[line - 2][from].jumpTo(stones[line][to]) > dangers[line - 2][from][d]){
                                dangers[line][to][d - 1] = dangers[line - 2][from][d] + stones[line - 2][from].jumpTo(stones[line][to])
                            }
                        }
                    }
                }
            }
        }
        val l = dangers.takeLast(2)
        println(
                minOf(l.first().map{
                    it.drop(1).min() ?: Int.MAX_VALUE
                }.min() ?: Int.MAX_VALUE, l.last().map{it.min() ?: Int.MAX_VALUE}.min() ?: Int.MAX_VALUE)
        )
    }
}
data class Stone(val x:Int, val danger:Int){
    fun jumpTo(stone:Stone):Int {
        return abs(x - stone.x) * (danger + stone.danger)
    }
}


Measured memory_bytes: 62380
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (register int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 6e2 + 5 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T = int> T read()
{
	T f = 1, a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	return a * f ;
}

ll n, a[maxn], sum, flag[maxn], ans = 1;

ll f[2][maxn][maxn];

signed main()
{
	scanf("%lld", &n);
	rep(i, 1, n << 1) scanf("%lld", &a[i]);
	rep(i, 1, n)
	{
		if(a[i * 2 - 1] == -1 && a[i * 2] == -1) (ans *= ++ sum) %= mod;
		else if(a[i * 2 - 1] == -1) flag[a[i * 2]] = 1;
		else if(a[i * 2] == -1) flag[a[i * 2 - 1]] = 1;
		else flag[a[i * 2]] = flag[a[i * 2 - 1]] = 2;
	}
	f[1][0][0] = 1;
	per(i, n << 1, 1)
	{
		int now = i & 1;
		clr(f[now]);
		rep(j, 0, n) rep(k, 0, n)
		{
			if(flag[i] == 2)
			{
				f[now][j][k] = f[!now][j][k];
				continue;
			}
			if(flag[i] == 1)
			{
				if(k) (f[now][j][k] += f[!now][j][k - 1]) %= mod;
				(f[now][j][k] += f[!now][j + 1][k]) %= mod;
				continue;
			}
			if(j) (f[now][j][k] += f[!now][j - 1][k]) %= mod;
			(f[now][j][k] += f[!now][j + 1][k] % mod) %= mod;
			(f[now][j][k] += f[!now][j][k + 1] * (k + 1) % mod) %= mod;
		}
	}
	printf("%lld\n", ans * f[1][0][0] % mod);
	return 0;
}

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

typedef long long ll;
# define  pii pair<ll,ll> 
# define pb push_back
# define f first 
# define s second 


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

	vector<int> v1(n,0),v2(n,0);

	double no=0;

	int cn=0;

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

		no= sqrt(pow(v1[i],2) + pow(v2[i],2));

		if(no<=d) cn++;



	}

	cout<<cn<<endl;



   
	return 0;
}


Measured memory_bytes: 4804
#include<iostream>
#define MAX 1000001
using namespace std;
const int infty = 1<<25;
int main()
{
  int allnum = 0;
  int oddnum = 0;
  static int KAll[MAX];
  static int KOdd[MAX];
  static int Answer1[MAX];
  static int Answer2[MAX];
  Answer1[0]=0;
  Answer2[0]=0;

  int n = 1;
  while( true ){
    int t = n*(n+1)*(n+2) / 6;
    if( t >= MAX ) break;
    KAll[allnum++]=t;
    if( t % 2 == 1 ){
      KOdd[oddnum++]=t;
    }
    ++n;
  }
  
  for(int i = 1; i < MAX; ++i){
    Answer2[i] = Answer1[i] = infty;
    for(int j = 0; j < allnum && i - KAll[j] >= 0; ++j){
      Answer1[i] = min(Answer1[i], 1+Answer1[i-KAll[j]]);
    }
    for(int j = 0; j < oddnum && i - KOdd[j] >= 0; ++j){
      Answer2[i] = min(Answer2[i], 1+Answer2[i-KOdd[j]]);
    }
  }
  
  while(true){
    int N;
    scanf("%d", &N);
    if( N == 0 ) break;
    printf("%d %d\n", Answer1[N], Answer2[N]);
  }
  return 0;
}

Measured memory_bytes: 8552
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 50100
using namespace std;
int x[MAXN],y[MAXN];
struct edge{
	int from,to;double quan;
}e[MAXN*2];
int n,m;int fa[MAXN];

int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}

double getdis(int f,int s){
	return sqrt((x[f]-x[s])*(x[f]-x[s])+(y[f]-y[s])*(y[f]-y[s]));
}

bool cmp(edge x,edge y){
	return x.quan>y.quan;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];//scanf("%f%f",&x[i],&y[i]);
	double ans=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int xx,yy;scanf("%d%d",&xx,&yy);
		double dis=getdis(xx,yy);
		e[i].from=xx,e[i].to=yy,e[i].quan=dis;
		ans+=dis;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int xx=find(e[i].from),yy=find(e[i].to);
		if(fa[xx]!=fa[yy]){
			fa[xx]=yy;
			ans-=e[i].quan;
		}
	}
	printf("%0.3f",ans);
	return 0;
}

Measured memory_bytes: 3776
#!/usr/bin/perl
use POSIX qw(floor);

my ($n) = map { $_ - 0 } split(/\s+/,<STDIN>);
my @a  = map { $_ - 0 } split(/\s+/,<STDIN>);

my $c = 0;
for(my $i=0;$i<$n;$i++){
  $c++ if( ( $i % 2 == 0 ) and ($a[$i] % 2) == 1 );
}

print "$c\n";


Measured memory_bytes: 6640
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#define PI 3.14159265358979323846
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
int r;
cin >> r;
double l;
l = 2 *r * PI;
    cout << fixed << setprecision(20);
    cout << l << endl;

return 0;

}


Measured memory_bytes: 3760
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 +9;

typedef vector<lli> Vec;
typedef vector<vector<lli>> Mat;
Vec operator +(const Vec &a, const Vec &b){
    Vec res(a.size());
    for(int i=0; i<(int)a.size(); i++){
        res[i] = (a[i] + b[i]) %mod;
    }
    return res;
}
Vec operator *(const Mat &a, const Vec &b){
    Vec res(b.size(), 0);
    for(int i=0; i<(int)b.size(); i++){
        for(int j=0; j<(int)a[i].size(); j++){
            res[i] += a[i][j]*b[j] %mod;
        }
        res[i] %= mod;
    }
    return res;
}
Mat operator *(const Mat &a, const Mat &b){
    int p=a.size(), q=b.size(), r=b[0].size();
    Mat res(p, Vec(r, 0));
    for(int i=0; i<p; i++){
        for(int j=0; j<r; j++){
            for(int k=0; k<q; k++){
                res[i][j] += a[i][k]*b[k][j] %mod;
            }
            res[i][j] %= mod;
        }
    }
    return res;
}

Mat modpow(Mat a, lli p){
    Mat res(a.size(), Vec(a.size(), 0));
    for(int i=0; i<(int)a.size(); i++){
        res[i][i] = 1;
    }
    for(int i=63; i>=0; i--){
        res = res*res;
        if((1LL<<i & p) != 0){
            res = res*a;
        }
    }
    return res;
}

int main(){
    for(int dataset=1; ; dataset++){
        lli w,h,n;
        cin >> w >> h >> n;
        if(w == 0) break;

        map<lli, vector<lli>> obs;
        obs[h-1] = vector<lli>();
        for(int i=0; i<n; i++){
            lli x,y;
            cin >> x >> y;
            x--; y--;
            obs[y].push_back(x);
        }
        
        Mat ch(w, Vec(w, 0));
        for(int i=0; i<w; i++){
            for(int j=-1; j<=1; j++){
                if(i+j<0 or i+j>=w) continue;
                ch[i][i+j] = 1;
            }
        }
        Vec curr(w, 0);
        curr[0] = 1;
        lli curridx = 0;
        for(auto p: obs){
            if(curridx < p.first){
                curr = modpow(ch, p.first-curridx)*curr;
            }
            for(lli obsx: p.second){
                curr[obsx] = 0;
            }
            curridx = p.first;
        }
        cout << "Case " << dataset << ": " << curr.back() << endl;
    }
    return 0;
}



Measured memory_bytes: 3284
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  set<int> A;
  while (n--) {
    int t;
    cin >> t;
    A.insert(t);
  }
  int m;
  cin >> m;
  set<int> B;
  while (m--) {
    int t;
    cin >> t;
    if (A.find(t) != A.end()) {
      B.insert(t);
    }
  }
  for (auto x : B)
    cout << x << endl;
  return 0;
}


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

int main(){
  int a,b;
  cin>>a>>b;
  
  int ans=1;
  
 if(b==1){
 	cout<<0;
 }else if(a>=b){
 	cout<<1;
 }else{
   int i;
   a-=1;
 	for(i=0;ans<b;i++){
    	ans+=a;
    }
   
   cout<<i;
 }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<string,ll>;
using Map = map<char,ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

ll gcd(ll a,ll b) {
    while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
    }
    return a;
}
ll lcm(ll a, ll b){
    return a/gcd(a,b)*b;
}
ll F(ll x,ll C,ll D){
    return x-x/C-x/D+x/(lcm(C,D));
}

int main(){
    ll A;
    cin >> A;
    ll B;
    cin >> B;
    ll C;
    cin >> C;
    ll D;
    cin >> D;
    cout<<F(B,C,D)-F(A-1,C,D)<<endl;
return 0;
}


Measured memory_bytes: 256
import collections

n,p=map(int,input().split())
s=input()
arr=[int(s[i]) for i in range(len(s))]
if p==2 or p==5:
  ans=0
  for i in range(n):
    if arr[i]%p==0:
      ans+=i+1
  print(ans)
else:
  dic=collections.defaultdict(int)
  match=[]
  pows=[1]
  for _ in range(n):
    pows.append((pows[-1]*10)%p)
  tmp=0
  for i in range(n-1,-1,-1):
    tmp+=arr[i]*pows[n-1-i]
    tmp%=p
    match.append(tmp)
    dic[tmp]+=1
  match=match[::-1]
  ans=0
  rem=0
  rev=pow(10,p-2,p)
  for i in range(n-1,-1,-1):
    ans+=dic[rem]
    rem+=arr[i]*pows[n-1-i]
    rem%=p
    dic[match[i]]-=1
  print(ans)

Measured memory_bytes: 22852
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

#define rep(i, n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    int a,b;
    cin>>a>>b;
    if(a>=10||b>=10){
        cout<<-1<<endl;
    }else{
        cout<<a*b<<endl;
    }



    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

int main(void)
{
  int i;
   int k;
    int l;
    {
    char ch[1001];
    {   
    while(scanf("%s", ch)!= EOF)
      {
        for(i=0;ch[i]!='\0'; i++)
	  {
            l=0;
            if(ch[i]=='@')
	      {
                l=ch[i+1]-'0';
                i++;
                for(k=1; l>k; k++)
		  {
                    printf("%c",ch[i+1]);
                }
            }
            else
	      {
                printf("%c",ch[i]);
            }
        }
        printf("\n",ch);
    }   
    return (0);
    }
    }
}



Measured memory_bytes: 1920
#include <stdio.h>
#include <stdlib.h>
int main(void) {
  long long int x, k, d;
  long long int q, r;
  scanf("%lld%lld%lld", &x, &k, &d);
  x = llabs(x);
  d = llabs(d);
  q = x/d;
  r = x%d;
  if (k <= q) {
    printf("%lld", x - d*k);
    return 0;
  }
  if ((k-q)%2==0) {
    printf("%lld", r);
    return 0;
  }
  if ((k-q)%2!=0) {
    printf("%lld", d-r);
    return 0;
  }
}

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

using namespace std;

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

int mod=1e9+7;
const int N=2e5+100;


int main()
{
    int n;cin>>n;
   string s;cin>>s;
   int a=0,b=0,c=0;
   for(int i=0;i<s.size();i++){
     if(s[i]=='R') a++;
     if(s[i]=='G') b++;
     if(s[i]=='B') c++;
   }
   ll kk=0;
   for(int i=0;i<=n/2;i++){
     for(int j=0;j+2*i<n;j++){
         if(s[j]!=s[j+i]&&s[j]!=s[j+i*2]&&s[j+i]!=s[j+2*i])
            kk++;
     }
   }
  //cout<<kk<<endl;
   ll ans=1ll*a*b*c;
   cout<<ans-kk;
   return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
int main(){
  int n;
  string a,b;
  cin>>n>>a>>b;

  int cnt1[256]={0};
  rep(i,n)cnt1[(char)a[i]]++;
  int cnt2[256]={0};
  rep(i,n)cnt2[(char)b[i]]++;

  vector<int>A,B;
  rep(i,256)if(cnt1[i])A.push_back(cnt1[i]);
  rep(i,256)if(cnt2[i])B.push_back(cnt2[i]);

  n=max(A.size(),B.size());
  while(A.size()!=n)A.push_back(0);
  while(B.size()!=n)B.push_back(0);
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  ////////////////////////////
  /*rep(i,n){
    rep(j,n){
      if(B[i]==A[j]){
	A.erase(A.begin()+j);
	B.erase(B.begin()+i);
	i--;j--;
	break;
      }
    }
  }*/
  int out=0;
  rep(i,A.size()){
    if(B[i]>A[i]){
      out+=B[i]-A[i];
    }
  }
  cout<<out<<endl;
  /*
  rep(i,A.size())cout<<A[i]<<endl;
  cout<<endl;
  rep(i,B.size())cout<<B[i]<<endl;
  */
}

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

int main() {
    int N;
    std::cin >> N;
    std::vector<int> an;
    for (int i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        an.push_back(a);
    }

    int index = 1;
    int counter = 0;

    while (true) {
        int next = an[index - 1];
        if (next == -1) {
            counter = -1;
            break;
        }

        ++counter;
        an[index - 1] = -1;

        if (next == 2) {
            break;
        }

        index = next;
    }

    std::cout << counter << std::endl;
    return 0;
}


Measured memory_bytes: 1140
#include<bits/stdc++.h>
using namespace std;
int main(){
    while(1){
     int a,b;
     string op;
     cin>>a>>op>>b;
     if(op=="?") break;
     int ans;
     if(op=="+") ans=a+b;
     if(op=="-") ans=a-b;
     if(op=="*") ans=a*b;
     if(op=="/") ans=a/b;
     cout<<ans<<endl;
    }
    return 0;
}


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

int main()
{
    int n;
    cin>>n;
    int a[n+5],b[n+5],c[n+5];

    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];
    int dp[3][n+5];
    dp[0][1]=a[1];
    dp[1][1]=b[1];
    dp[2][1]=c[1];
    for(int i=2;i<=n;i++){
        dp[0][i]=a[i]+max(dp[1][i-1],dp[2][i-1]);
        dp[1][i]=b[i]+max(dp[2][i-1],dp[0][i-1]);
        dp[2][i]=c[i]+max(dp[0][i-1],dp[1][i-1]);
    }
    cout << max(dp[0][n],max(dp[1][n],dp[2][n]));
    return 0;
}


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

int main(){
    
    int N;
    int A,B;
    
    cin >> N;
    cin >> A >> B;
    
    int P;
    int a = 0;
    int b = 0;
    int c = 0;
    for(int i = 0; i < N ; i++){
        cin >> P;
        if(P<=A)a++;
        else if(A+1 <= P && P <= B)b++;
        else c++;
    }
    
    cout << min(a,min(b,c))<<endl;
    
    
    
}
    
    



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] S = sc.next().toCharArray();
		sc.close();
		boolean ok = true;
		int N = S.length;
		// Sは回文であるか
		for(int i = 0; i < N; i++) {
			ok &= S[i] == S[N - i - 1];
		}
		// Sの1文字目から(N - 1)/2文字目まで(両端含む)からなる文字は回文であるか
		for(int i = 0; i < (N - 1) / 2; i++) {
			ok &= S[i] == S[(N - 1) / 2 - i - 1];
		}
		// Sの(N + 3)/2文字目からN文字目まで(両端含む)からなる文字は回文であるか
		// ※Sが回分であることが条件のため、Sの(N + 3)/2文字目移行の文字と1文字目～からが回分であればOK
		for(int i = (N + 3) / 2 - 1; i < N; i++) {
			ok &= S[i] == S[N - i - 1];
		}
		System.out.println(ok ? "Yes" : "No");
	}
}

Measured memory_bytes: 23764
#include<cstdio>

using namespace std;

int main(){
	int sq[18];
	for(int i=1;i<18;i++)	sq[i]=i*i;

	int memo[301][18];
	for(int i=0;i<18;i++)	memo[0][i]=1;
	for(int i=1;i<=300;i++){
		for(int j=1;j<18;j++){
			memo[i][j]=(j>0?memo[i][j-1]:0);
			for(int k=1;k*sq[j]<=i;k++){
				int rem=i-k*sq[j];
				memo[i][j]+=memo[rem][j-1];
			}
		}
	}

	for(int p;scanf("%d",&p),p;)	printf("%d\n",memo[p][17]);

	return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

vvint G;
vint lis, A, ans;


void dfs(int u, int prev) {
	int pos = lower_bound(begin(lis), end(lis), A[u]) - begin(lis);
	int base;
	bool f = pos == lis.size();
	if (f) { lis.push_back(A[u]); }
	else   { base = lis[pos]; lis[pos] = A[u]; }
	ans[u] = lis.size();
	for (auto &v : G[u]) {
		if (v != prev) dfs(v, u);
	}
	//戻す
	if (f) { lis.pop_back(); }
	else { lis[pos] = base; }
}

void Main() {
	int N; cin >> N;
	G = vvint(N);
	A = vint(N);
	ans = vint(N, -1);
	cin >> A;	
	for (int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0, -1);
	for (int i = 0; i < N; i++) {
		cout << ans[i] << el;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 30000
from heapq import heappush, heappop

n = int(input())
A = list(map(int, input().split()))

f_inf = float('inf')
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    for l in range(i+1):
        r = i-l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*A[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])
print(ans)


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

int main() {
  int N,M;//Nは都市数Mは道路数
  cin>>N>>M;
  vector<int> vec(M*2);
    rep(i,M*2){
    cin>>vec.at(i);
  }//代入
  
  vector<int> city(N);//それぞれの都市の道路数
  rep(j,N){
    rep(i,M*2){
    if(vec.at(i)==j+1){
      city.at(j)+=1;
    }
  }
  }
  rep(i,N){
  cout<<city.at(i)<<endl;
  }
}

Measured memory_bytes: 256
function main(input) {
	const args = input.split(' ');
  	const a = parseInt(args[0],10);
    const b = parseInt(args[1],10);
  	const seki = a*b;
  	if (seki%2===0){
    	console.log('Even');
    }
  	else{
    	console.log('Odd');
    }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
                     
#define int             long long
#define ld              long double
#define mp              make_pair
#define ff              first
#define ss              second
#define pb              push_back
#define fo(i,n)         for(i=0;i<n;i++)
#define fo1(i,n)        for(i=1;i<=n;i++)
#define FO(i,a,b)       for(i=a;i<=b;i++)
#define FOR(i,a,b)      for(i=a;i>=b;i--)
#define all(c)          c.begin(),c.end()
#define rall(c)         c.rbegin(),c.rend()
#define si              set<int>
#define vi              vector<int>
#define mii             map<int,int>
#define pii             pair<int,int>
#define vpii            vector<pii>
#define vvi             vector<vi>
#define usi             unordered_set<int>
#define umii            unordered_map<int,int>
#define pqmx            priority_queue<int>
#define pqmn            priority_queue<int,vi,greater<int> >
#define sp(x)           cout<<setprecision(x)<<fixed;
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define in(a,n)         vi a(n);fo(i,n)cin>>a[i];
#define in1(a,n)        vi a(n+1);fo1(i,n)cin>>a[i];
#define w(t)            int t;cin>>t;while(t--)
#define sz(v)           (int)v.size()
#define gcd             __gcd
#define lcm(x,y)        x*(y/gcd(x,y))
#define endl            '\n'
#define PI              3.14159265358979323846
const int inf =         1e18;
const int mod =         1e9+7;
void __p(int x) {cout<<x;}
void __p(int32_t x){cout<<x;}
void __p(float x){cout<<x;}
void __p(double x){cout<<x;}
void __p(ld x) {cout<<x;}
void __p(char x){cout <<'\''<<x<<'\'';}
void __p(const char *x){cout <<'\"' <<x<<'\"';}
void __p(const string &x) {cout<<'\"'<<x<<'\"';}
void __p(bool x) {cout<<(x?"true":"false");}
void _p() {cout << "]\n";}
template<typename T,typename V>     void __p(const pair<T,V> &x) {cout<<'{';__p(x.first);cout<<',';__p(x.second);cout<<'}';}
template<typename T>                void __p(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __p(i); cout << "}";}
template <typename T,typename... V> void _p(T t, V... v) {__p(t);if(sizeof...(v))cout<<", ";_p(v...);}
int po(int x,int p) {int ans=1;x%=mod;while(p>0){if(p&1)ans=(ans*x)%mod;p=p>>1;x=(x*x)%mod;}return ans;}
int inv(int x){return po(x,mod-2)%mod;}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_p(x)
#else 
#define dbg(x...)
#endif
//=================================================================================




int n,m,k,x,y,z,a,b,c,d,i,j,l,r,f,q;








void sol()
{   
    cin>>n;
    in(a,n);
    i=0;
    int value=1000;
    while(i+1<n)
    {   int c=0;
        while(i+1<n && a[i+1]<=a[i])i++;
        c=value/a[i];
        int buy=a[i];
        while(i+1<n && a[i+1]>a[i])i++;
        int sell=a[i];
        value+=c*(sell-buy);       
    }

    cout<<value<<endl;
    
}





int32_t main()
{   
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    //sp(10);
    // w(t)
    sol();
    return 0;
}

Measured memory_bytes: 3660
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;
const int inf = 1000000000; //10^9
const ll MX = 1e18;         //1(1倍)e(指数)18(10^18)
const ll MOD = 1e9 + 7;
//加算代入演算子は+=
//int 2^31 10^9まで
//intは10桁、long longは18桁、doubleは308桁、long double は4932桁
//10^10くらいまででdoubleは誤差が発生しちゃう。なるべく整数にすること
//doubleからlong longにキャストするときは、+0.5で切り捨ての誤差を調整
//__int128()で128bit対応の整数（多倍長整数）

int main() {
    int h, w;
    char a[101][101];
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
 
    for (int i = 0; i < h+2; i++) {
        if (i == 0 || i == h+1) { //一行目と最終行に'#'
            for (int j = 0; j < w+2; j++) {
                cout << "#";
            }
        } else {
            for (int j = 0; j < w+2; j++) {
                if (j == 0 || j == w+1) {//一列目と最終列は"#"
                    cout << "#";
                } else {
                    cout << a[i-1][j-1]; //一行目と一列目を#判定に使ったからその分減らす
                }
            }
        }
        cout << endl;
    }
    return 0;
}

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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using Vll = V<ll>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Msi = M<string, int>;

const ll MOD = 1e9+7;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()


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

    Msi map;
    REP(i, n) {
        string s;
        cin >> s;
        sort(ALL(s));
        if (map.find(s) != map.end()) {
            map[s]++;
        } else {
            map[s] = 1;
        }
    }

    ll cnt = 0;
    FOR(i, map) {
        ll val = i->second;
        cnt += val * (val-1) / 2;
    }

    std::cout << cnt << '\n';

    return 0;
}


Measured memory_bytes: 11136