akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
static inline void Add(int *fwt,int i,int v,int len){while(i<len){fwt[i]+=v;i|=i+1;}}
static inline int Sum(int *fwt,int i){int v=0;while(i>=0){v+=fwt[i];i=(i&(i+1))-1;}return v;}
static inline int Diff(int *fwt,int x,int y,int len){if(x==-1){return Sum(fwt,y);}if(y==-1){y=len-1;}return Sum(fwt,y)-Sum(fwt,x-1);}
int main()
{
  int N=IN(),Q=IN(),after[500001],dat[500000],fenwick[500000],id[500000],left[500001],pos[500000],result[500000];
  rep(i,N){dat[i]=IN()-1;}
  rep(i,Q){left[i+1]=IN()-1;int r=IN()-1;after[i+1]=id[r];id[r]=i+1;}
  rep(r,N)
  {
    if(pos[dat[r]]){Add(fenwick,pos[dat[r]]-1,-1,N);}
    Add(fenwick,r,1,N);
    for(int i=id[r];i;i=after[i]){result[i-1]=Diff(fenwick,left[i],r,N);}
    pos[dat[r]]=r+1;
  }
  rep(i,Q){OUT(result[i]);}
}

Measured memory_bytes: 17196
n = int(input())

wa_min = n
for i in range(1,n+1):
	n1 = n - i
	n2 = i
	wa1 = 0
	wa2 = 0
	while n1 > 0:
		mod = n1 % 10
		wa1 += mod
		n1 = n1 // 10
	while n2 > 0:
		mod2 = n2 % 10
		wa2 += mod2
		n2 = n2 // 10
	if (wa1 + wa2) < wa_min:
		wa_min = (wa1 + wa2)
	if i == n-i:
		break
print(wa_min)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
#define m long long
#define d(s,i,n) for(m i=s;i<n;i++)
#define z else
main(){m n,a,g,b,o=1e9+7,x=90,l[x][x],r[x][x];cin>>n;d(0,i,x){l[i][0]=r[i][0]=1;d(1,j,x){if(i==j)r[i][j]=r[i][j-1]*2+l[i][j-1];z r[i][j]=r[i][j-1]+l[i][j-1];l[i][j]=r[i][j-1];}}d(0,i,n){cin>>a>>b;if(b>a)swap(a,b);m k=0;d(0,j,x)if(a>=r[0][j]&&b>=l[0][j])k=j;if(k==0)k=1,g=1;z if(k==1)if(b==1)g=a;z g=4;z{g=1;if(b>=r[0][k]&&a>=l[0][k]&&l[0][k]<r[0][k])g++;d(1,j,k+1)if(r[j][k]<=a&&l[j][k]<=b)g+=1+(a-r[j][k])/l[j][k];d(1,j,k+1)if(r[j][k]<=b)g+=1+(b-r[j][k])/l[j][k];}cout<<k<<" "<<g%o<<" ";}}

Measured memory_bytes: 4440
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    cout << (n - 1) / (k - 1) + bool((n - 1) % (k - 1)) << '\n';
    return 0;
    vector <int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

int main(void){
  ll x, k, d;
  cin >> x >> k >> d;

  x = abs(x);

  ll tmp = min(k,x/d);
  k = k - tmp;
  x = x - d * tmp;

  if(k%2==0){
    cout << x << endl;
  }
  else{
    cout << d - x << endl;
  }

  return 0;
}


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

const ll mod = 998244353;
int n, k;

ll Pow(ll b, ll e){
	ll ret=1;
	while(e){
		if(e&1) (ret*=b)%=mod;
		(b*=b)%=mod; e>>=1;
	}
	return ret;
}

ll fa[500'001];
ll Inv(ll x){ return Pow(x, mod-2); }
inline ll Comb(ll n, ll r){
	if(r<0 || r>n) return 0;
	return fa[n]*Inv(fa[r])%mod*Inv(fa[n-r])%mod;
}
inline ll Way(ll w, ll h){ return Comb(w+h, w); }

ll F(ll r, ll b){
	if(r<b) return 0;
	if(r == b) return F(r, b-1);
	if(r >= b+n){
		return Comb(r+b, r);
	}
	return (Comb(r+b, b) + mod-Comb(r+b, b-r+n-1)) % mod;
}

int main()
{
	fa[0]=1;
	for(ll i=1; i<=500'000; ++i) fa[i]=fa[i-1]*i%mod;
	
	cin >> n >> k;
	ll ans = 0;
	
	for(ll r=n; r<=k; ++r) (ans += F(r, k-r)) %= mod;
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4096
n = int(input())

s = []
for i in input():
  if i == '.':
    s.append(0)
  else:
    s.append(1)

black_num = sum(s)
change_num = n - black_num
ans = change_num

for i in s:
  if i == 0:
    change_num -= 1
  else:
    change_num += 1
  ans = min(ans,change_num)
    
print(ans)

Measured memory_bytes: 5096
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ldouble = long double;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s) cout << fixed << setprecision(10) << s << endl;


int main()
{
	ll a[2];
	for (ll i = 0; i < 2; i++)
	{
		int x;
		cin >> x;

		if (x == 2)
		{
			a[i] = 0;
		}
		else if ((x < 8 && x % 2 == 1) || (x >= 8 && x % 2 == 0))
		{
			a[i] = 1;
		}
		else
		{
			a[i] = 2;
		}

	}

	
	if (a[0] == a[1])
	{
		println("Yes");
	}
	else
	{
		println("No");
	}
}

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = rbegin(s); i != rend(s); ++i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.ne(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<class A, int N, class T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

int n, q;
string s;
void solve() {
    cin >> n >> s >> q;

    rep(i, q) {
        int k;
        cin >> k;

        ll ans = 0;
        ll d = 0, m = 0, dm = 0;
        rep(i, k) {
            if (s[i] == 'D') ++d;
            else if (s[i] == 'M') {
                ++m;
                dm += d;
            }
            else if (s[i] == 'C') ans += dm;
        }

        loop(i, k, n) {
            if (s[i - k] == 'D') {
                --d;
                dm -= m;
            }
            else if (s[i - k] == 'M') --m;

            if (s[i] == 'D') ++d;
            else if (s[i] == 'M') {
                ++m;
                dm += d;
            }
            else if (s[i] == 'C') ans += dm;
        }

        cout << ans << endn;
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 1948
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <time.h>
#include <tuple>
#define all(c) ((c).begin(),(c).end())
#define rall(c) ((c).rbegin(),(c).rend())
//#define sort(v,n) sort(v,v+n)
#define ll long long
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//
int n;
char c[52];
int main() {
	for (int i = 0; i < 26; i++) {
		c[i] = char('A' + i);
	}
	for (int i = 0; i < 26; i++) {
		c[i + 26] = char('a' + i);
	}
	while (cin >> n, n) {
		queue<int> q;
		for (int i = 0; i < n; i++) {
			int a; cin >> a;
			q.push(a);
		}
		string ans = "";
		string s; cin >> s;
		for (int i = 0; i < s.length(); i++) {
			int a = q.front();
			q.pop();
			char b = s[i];
			int num = -1;
			for (int i = 0; i < 52; i++) {
				if (c[i] == b) {
					num = i;
					break;
				}
			}
			if (num - a < 0) {
				ans += c[52 + num - a];
			}
			else {
				ans += c[num - a];
			}
			q.push(a);
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

int main(void) {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> vec;
    for(int i=0; i<N-1; i++) {
        if(S.substr(i,2) == "AC") {
            vec.push_back(i);
        }
    }
    for(int j=0; j<Q; j++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        cout << upper_bound(vec.begin(), vec.end(), r-1) - lower_bound(vec.begin(), vec.end(), l) << endl;;
    }
    return 0;
}


Measured memory_bytes: 1276
#include <stdio.h>

int main(){
  int j;
  int N;
  int flag=1;
  int a;
  int count=0;

  scanf("%d",&N);
  int A[N];

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

  while(flag==1){
    flag=0;
    for(j=N-1;j>=0;j--){
      if(A[j] < A[j-1]){
	a=A[j];
	A[j]=A[j-1];
	A[j-1]=a;
	count++;
	flag=1;
      }

    }

  }

  for(j=0;j<N;j++){
    if(j==N-1){
      printf("%d\n",A[j]);
      printf("%d\n",count);
    }
    else printf("%d ",A[j]);
  }


  return 0;
}



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

int main()
{
	LL n, x, t;
	cin >> n >> x >> t;
	LL ans;
	if(n % x == 0)
		ans = n / x;
	else
		ans = n / x + 1;
	cout << ans * t << endl;
	return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
ll sz(string &s){ return (ll)s.size(); }
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }

int main(){
    ll n;
    cin >> n;
    ll l[n] = {};
    rep(i,0,n){
        cin >> l[i];
    }

    sort(l,l+n);

    ll ans = 0;
    rep(i,0,n){
        rep(j,i+1,n){
            ll ok = j,ng = n;
            while(abs(ok-ng) > 1){
                ll mid = (ok+ng)/2;
                if(l[mid] < l[i]+l[j]) ok = mid;
                else ng = mid;
            }
            ans += ok-j;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>

using namespace std;
int main()
{
	int x;
	cin >> x;
	int i = 0;
	while(i*(i+1)<2*x)
	{
		i++;
	}
	cout << i << endl;

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int M = N;
  int keta=0;
  int ans;
  while(M!=0){
    M /= 10;
    keta++;
  }
  switch (keta) {
    case 1:
    cout << N << '\n';
    break;
    case 2:
    cout << 9 << '\n';
    break;
    case 3:
    ans=N-90;
    cout << ans << '\n';
    break;
    case 4:
    cout << 909 << '\n';
    break;
    case 5:
    ans = N-9090;
    cout << ans << '\n';
    break;
    case 6:
    cout << 90909 << '\n';
    break;  
  } 
}

Measured memory_bytes: 256
#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

dp = [[0]*13 for i in range(n+1)]

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])


Measured memory_bytes: 64876
#include<bits/stdc++.h>
#include<vector>
#include<deque>
#include<list>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
struct pos{
	int x,y,cost;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int n,x;
	cin>>n>>x;

	int t=0;
	rep(i,n){
		int l;
		cin>>l;
		t+=l;
		if(t>x){
			cout<<i+1<<endl;
			return 0;
		}
	}
	cout<<n+1<<endl;

	return 0;
}


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

int main(){
char c;
cin >> c;
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
    cout << "vowel" << endl;
}
else {
    cout << "consonant" << endl;
}
}

Measured memory_bytes: 256
from bisect import bisect_left
INFTY = 10**5+10
P = [1 for _ in range(INFTY)]
P[0]=0
P[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
X = int(input())
ind = bisect_left(Q,X)
print(Q[ind])

Measured memory_bytes: 44784
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int mask[1001],cost[1001];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i= 0 ;i<m;i++){
        cin>>cost[i];
        int b;
        cin>>b;
        while(b--){
            int c;
            cin>>c;
            c--;
            mask[i] = mask[i]|(1<<c);
        }
    }
    vector<int> dp(1 << n, INF), e(1 << n);
    dp[0]=0;
    for(int i=0;i<m;i++){
        copy(dp.begin(),dp.end(),e.begin());
        for(int j=0;j<(1<<n);j++){
            int mas = j|mask[i];
            e[mas] = min(dp[j]+cost[i],e[mas]);
        }
        copy(e.begin(),e.end(),dp.begin());
    }
    if(dp[(1<<n)-1]==INF){
        cout<<-1<<endl;
    }else{
        cout<<dp[(1<<n)-1]<<endl;
    }
    
    return 0;
}

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


def main():
    N = int(input())
    s = [input() for _ in range(N)]
    M = int(input())
    t = [input() for _ in range(M)]
    y = 0
    for ss in set(s):
        yy = s.count(ss) - t.count(ss)
        if y < yy:
            y = yy
    print(y)


main()


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

int main()
{
    string S;
    cin >> S;
    vector<int> children(S.size());
    int i = 0;
    int rPoint, gatheringPoint, lPoint;
    rPoint = 0;
    while(i < S.size()){
        while(S[i] == 'R'){
            i++;
        }
        gatheringPoint = i;//RLのLの位置
        int rChildren = gatheringPoint - rPoint;
        children.at(gatheringPoint - 1) += (rChildren - rChildren / 2);
        children.at(gatheringPoint) += rChildren / 2;
        while(i < S.size() && S[i] == 'L'){
            i++;
        }
        lPoint = i - 1;
        int lChildren = lPoint - gatheringPoint + 1;
        children.at(gatheringPoint) += (lChildren - lChildren / 2);
        children.at(gatheringPoint - 1) += lChildren / 2;

        rPoint = i;
    }
    bool isFirst = true;
    for (int count : children){
        if(isFirst)
        {
            isFirst = false;
        }else{
            cout << " ";
        }
        cout << count;
    }
    return 0;
}

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

int main(){
	int x[10];
	for(int i = 0; i < 10; i++){
		cin >> x[i];
	}
	sort(x,x + 10);
	cout << x[9] << endl << x[8] << endl << x[7] << endl;
	return 0;
}

Measured memory_bytes: 1176
using System;
using System.Text.RegularExpressions;

namespace ConsoleApp3
{
	class Program
	{
		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			var s = Console.ReadLine().ToCharArray();

			int count = 0;
			char pre = '0';
			for (int i = 0; i < s.Length; i++)
			{
				if (s[i] != pre)
				{
					count++;
					pre = s[i];
				}
			}
			Console.WriteLine(count);
		}
	}
}


Measured memory_bytes: 11488
s = input()

def day_dream(s):
    while not s == "":
        if s[-7:] == "dreamer":
            s = s[:-7]
        elif s[-6:] == "eraser":
            s = s[:-6]
        elif s[-5:] == "dream" or s[-5:] == "erase":
            s = s[:-5]
        else:
            return "NO"
    return "YES"

print(day_dream(s))


Measured memory_bytes: 3316
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC094
{
    class C
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] X = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] sortedX = X.OrderBy(x => x).ToArray();

            int res = 0;
            int B1 = sortedX[N / 2 - 1];
            int B2 = sortedX[N / 2];
            for (int i = 0; i < N; i++)
            {
                if (X[i] <= B1) res = B2;
                else res = B1;
                Console.WriteLine(res);
            }
        }
    }
}


Measured memory_bytes: 41104
l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, i*j%2019)
        if a == 0:
            print(0)
            exit()

print(a)


Measured memory_bytes: 3060
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int q=sc.nextInt();
        int[] ans=new int[q];
        for(int n=0;n<q;n++){
            String X=sc.next();
            String Y=sc.next();
            int[][] A=new int[X.length()+1][Y.length()+1];
            for(int i=1;i<X.length()+1;i++){
                for(int j=1;j<Y.length()+1;j++){
                    if((X.substring(i-1,i)).equals(Y.substring(j-1,j))){
                        A[i][j]=A[i-1][j-1]+1;
                    }else{
                        if(A[i-1][j]<A[i][j-1]){
                            A[i][j]=A[i][j-1];
                        }else{
                            A[i][j]=A[i-1][j];
                        }
                    }
                }
            }
            ans[n]=A[X.length()][Y.length()];
        }
        for(int num:ans){
            System.out.println(num);
        }
    }
}


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

int main() {
  int N;
  cin >> N;
  int count=0;
  for(int i=1;i<10;i++){
    for(int j=i;j<10;j++){
      if(i*j==N) count++;
      }
    }
  if(count >= 1) {
    cout << "Yes" << endl;
  }else{
  cout << "No" << endl;
  }


  

}

Measured memory_bytes: 256
my $N=<stdin>;
my $A_in=<stdin>;
chomp $N;
chomp $A_in;
my @A=split(/ /,$A_in);
my $count=0;
my $flag=0;
while($flag==0){
    foreach my $x(@A){
        if($x%2!=0){
            $flag=1;
            last;
        }else{
            $x=$x/2;
        }
    }
    if($flag==0){
        $count++;
    }
}
print "$count\n";



Measured memory_bytes: 640
#include <iostream>
#include <unordered_map>

using namespace std;

typedef unsigned long long ull;

ull N,V;
ull p[4][1001];

ull solve() {
  ull ans = 0;
  unordered_map<ull, ull> c;
  for (int i=0; i<2; ++i) {
    for (int j=0; j<N; ++j) {
      for (int k=0; k<N; ++k) {
        ull tmp = p[i*2][j]+p[i*2+1][k];
        if (i==1 && V > tmp) {
          ans += c[V-tmp];
        } else {
          ++c[tmp];
        }
      }
    }
  }
  return ans;
}

int main() {
  cin>>N>>V;
  for (int i=0; i<4; ++i) {
    for (int j=0; j<N; ++j) {
      cin>>p[i][j];
    }
  }
  cout<<solve()<<endl;
  return 0;
}


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

ll func(ll n){
  ll cnt=1;
  ll c = 26,cc = 26;
  while(c < n){
    cc *= 26;
    c += cc;
    cnt++;
  }
  
  return cnt;
}

int main(){
  ll n;
  cin >> n;
  int keta = func(n);
  vector<int> v(keta);
  
  for(int i=0;i<keta;i++){
    n--;
    v.at(i) = n%26;
    n -= v.at(i);
    n /= 26;
    v.at(i)++;
  }
  
  for(int i= keta-1;i>=0;i--){
    if(v.at(i) == 1) cout << 'a';
    else if(v.at(i) == 2) cout << 'b';
    else if(v.at(i) == 3) cout << 'c';
    else if(v.at(i) == 4) cout << 'd';
    else if(v.at(i) == 5) cout << 'e';
    else if(v.at(i) == 6) cout << 'f';
    else if(v.at(i) == 7) cout << 'g';
    else if(v.at(i) == 8) cout << 'h';
    else if(v.at(i) == 9) cout << 'i';
    else if(v.at(i) == 10) cout << 'j';
    else if(v.at(i) == 11) cout << 'k';
    else if(v.at(i) == 12) cout << 'l';
    else if(v.at(i) == 13) cout << 'm';
    else if(v.at(i) == 14) cout << 'n';
    else if(v.at(i) == 15) cout << 'o';
    else if(v.at(i) == 16) cout << 'p';
    else if(v.at(i) == 17) cout << 'q';
    else if(v.at(i) == 18) cout << 'r';
    else if(v.at(i) == 19) cout << 's';
    else if(v.at(i) == 20) cout << 't';
    else if(v.at(i) == 21) cout << 'u';
    else if(v.at(i) == 22) cout << 'v';
    else if(v.at(i) == 23) cout << 'w';
    else if(v.at(i) == 24) cout << 'x';
    else if(v.at(i) == 25) cout << 'y';
    else if(v.at(i) == 26) cout << 'z';
  }
  cout << endl;
     
  return 0;
}


Measured memory_bytes: 3588
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#include<bitset>
#include<cstdlib>
#include<set>
#include<unordered_map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define low(x) (x&(-x))
#define IL inline
#define reg register
#define LL long long
#define N 500010
#define MOD 998244353
#define MO 1000000007
#define INF 0x3f3f3f3f
using namespace std;

int T,n,m,i,j,k,x,y,z,Ans,sum,cnt;
int a[N],b[N],f[N];
char c[N];

struct Data{
	int x,y;
}d[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL bool cmp(const Data a,const Data b){return a.x<b.x;}

IL LL Mi(LL x,LL y){
	LL p=x,t=1,Res=1;
	for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
	return Res;
}

IL int read(){
	int p=0,f=1;	char	c=getchar();
	while (c<48||c>57)	{if (c=='-')	f=-1;	c=getchar();}
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p*f;
}

IL int Find(int x){return (x==f[x])?x:f[x]=Find(f[x]);}

int main(){
	#ifdef __Marvolo
	freopen("zht.in","r",stdin);
	freopen("zht.out","w",stdout);
	#endif
	n=read();	m=read();
	for (i=1;i<=n;i++)	f[i]=i;
	for (i=1;i<=m;i++){
		x=read();	y=read();
		x=Find(x);	y=Find(y);
		if (x==y)	continue;
		f[x]=y;
	}
	for (i=1;i<=n;i++){
		x=Find(i);	b[x]++;
	}
	for (i=1;i<=n;i++)	Ans=Max(Ans,b[i]);
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 10584
num = gets.split.map(&:to_i)
dice = num.first
std_point = num.last

prob = 0.0
(1..dice).each do |i|
  point = i
  tmp_prob = 1.0 / dice.to_f

  while point < std_point do
    point = point * 2
    tmp_prob = tmp_prob * 0.5
  end
  prob += tmp_prob
end

puts prob

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int, int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
map<int, vector<int> >adj;
std::vector<bool> visited;
vector<int> components;
void dfs(int v) {
	if (visited[v]) return;
	components.push_back(v);
	visited[v] = true;
	for (int u : adj[v]) {
		if (!visited[u]) {
			dfs(u);
		}
	}
}

void solve() {
	int  n, m;
	cin >> n >> m;
	visited.assign(n, false);
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int max_ = 0;

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			dfs(i);
			int c = (int)components.size();
			components.clear();
			max_ = max(c,max_);
		}
	}
	cout << max_;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}

Measured memory_bytes: 44704
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
using namespace std;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int>L(M), R(M), p(Q), q(Q);
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i];
    }
    for (int i = 0; i < Q; i++) {
        cin >> p[i] >> q[i];
    }

    vector<vector<int>>memo(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>>sum(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        memo[L[i]][R[i]]++;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            memo[i][j] += memo[i - 1][j];
            memo[i][j] += memo[i][j - 1];
            memo[i][j] -= memo[i - 1][j - 1];
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << memo[q[i]][q[i]] - memo[p[i]-1][q[i]] - memo[q[i]][p[i]-1] + memo[p[i]-1][p[i]-1] << endl;
    }
    

    return 0;
}

Measured memory_bytes: 5248
#include <iostream>

using namespace std;

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
  int l= b/n;
  l=l*n;
    if(a<=l){
        cout<<"OK"<<endl;
    }
    else{
        cout<<"NG"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
int main()
{
  int n;
  std::cin >> n;
  n /= 2;

  std::vector<int> e(n);
  std::vector<int> o(n);

  for (int i = 0; i < n; i++) {
    std::cin >> e[i];
    std::cin >> o[i];
  }

  std::sort(std::begin(e), std::end(e));
  std::sort(std::begin(o), std::end(o));

  int es = 0;
  std::vector<std::pair<int, int>> emode;
  for (int i = 1; i <= n; i++) {
    if (i == n || e[i - 1] != e[i]) {
      emode.push_back(std::make_pair(i - es, e[i - 1]));
      es = i;
    }
  }

  es = 0;
  std::vector<std::pair<int, int>> omode;
  for (int i = 1; i <= n; i++) {
    if (i == n || o[i - 1] != o[i]) {
      omode.push_back(std::make_pair(i - es, o[i - 1]));
      es = i;
    }
  }

  std::sort(std::begin(emode), std::end(emode), std::greater<std::pair<int, int>>());
  std::sort(std::begin(omode), std::end(omode), std::greater<std::pair<int, int>>());

  int ans = 0;

  if (emode[0].second != omode[0].second) {
    ans = (n - emode[0].first) + (n - omode[0].first);
  }
  else {
    if (emode.size() == 1 && omode.size() == 1) {
        ans = n;
    }
    else if (emode.size() == 1) {
      ans = (n - emode[0].first) + (n - omode[1].first);
    }
    else if (omode.size() == 1) {
      ans = (n - omode[0].first) + (n - emode[1].first);
    }
    else {
        ans = std::min((n - emode[0].first) + (n - omode[1].first),
                       (n - emode[1].first) + (n - omode[0].first));
    }
  }

  std::cout << ans << std::endl;

  return 0;
}

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

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define se cout << "test ok" << endl;
#define sp << " " <<
#define enl "\n"
using namespace std;
using ll=long long;
using ld=long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using vlll = vector<vector<vector<ll>>>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
ll mod = ll(1e9)+7;
ll inf = ll(1e18);
void bl(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void bl2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(a>b){a=b; return true;} return false; }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

#include <iostream>
#include <vector>
#include <map>
using namespace std;

namespace dbg {
    using ll = long long;

    class Debug {
    public:
        Debug(){}
        template<typename T>
        void vd(vector<T> vec);
        template<typename T>
        void vd2(vector<vector<T>> vec);
        template<typename T>
        void ad(T *arr, ll n);
        template<typename T, size_t N>
        void ad2(T (&arr)[N], ll n);
        template<typename T>
        void md(T mp);
    };

    template<typename T>
    void Debug::vd(vector<T> vec) {
        for (auto vv : vec) cout << vv << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::vd2(vector<vector<T>> vec) {
        for (auto vv : vec) {
            for (auto vvv : vv) cout << vvv << " ";
            cout << endl;
        }
    }

    template<typename T>
    void Debug::ad(T *arr, ll n) {
        for (int i = 0; i <= n; i++) cout << arr[i] << " ";
        cout << endl;
    }

    template<typename T, size_t N>
    void Debug::ad2(T (&arr)[N], ll n) {
        for (int i = 0; i <= N; i++) for (int j = 0; j <= n; j++) cout << arr[i][j] << " ";
        cout << endl;
    }

    template<typename T>
    void Debug::md(T mp) {
        cout << "key : value" << endl;
        for (auto const &m : mp) cout << m.first << " : " << m.second << endl;
        cout << endl;
    }

}

#endif //INCLUDE_DEBUG_HPP

dbg::Debug debug;

class DDigitSumReplace {
public:
	void solve(std::istream& in, std::ostream& out) {
		ll m;
		in >> m;
		vl d(m), c(m);
		for(int i=0; i<m; i++){
			in >> d[i] >> c[i];
		}

		ll sum = 0, cnt=0;
		for(int i=0; i<m; i++){
			sum += d[i]*c[i];
			cnt += c[i];
		}

		out << cnt-1 + (sum-1)/9 << enl;
	}
};


int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	DDigitSumReplace solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;

#define EPS (1.0e-6)
#define equals(a, b) (fabs((a)-(b)) < EPS)
#define N_MAX 100

struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  Point operator +(Point p) { return Point(x + p.x, y + p.y); }
  Point operator -(Point p) { return Point(x - p.x, y - p.y); }
  Point operator *(double a) { return Point(x * a, y * a); }
  Point operator /(double a) { return Point(x / a, y / a); }
  bool operator < (const Point &p) const {
    return x != p.x ? p.x - x > EPS : p.y - y > EPS;
  }
  bool operator == (const Point &p) const {
    return equals(x, p.x) && equals(y, p.y);
  }
  bool operator != (const Point &p) const {
    return !(*this == p);
  }
};
typedef Point Vector;

struct Segment {
  Point p1, p2;
  Segment(Point p1, Point p2) {
    this->p1 = p1;
    this->p2 = p2;
  }
};
typedef Segment Line;

double norm(Vector a) { return pow(a.x, 2.0) + pow(a.y, 2.0); }
double abs(Vector a) { return sqrt(norm(a)); }
double cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }
bool isParallel(Vector a, Vector b) {
  return equals(cross(a, b), 0.0);
}
bool isParallel(Line s1, Line s2) {
  return isParallel(s1.p2 - s1.p1, s2.p2 - s2.p1);
}
Point getCrossPoint(Line s1, Line s2) {
  Vector a = s1.p2 - s1.p1;
  Vector b = s2.p2 - s2.p1;
  double d1 = cross(b, a);
  double d2 = cross(b, s2.p1 - s1.p1);
  return s1.p1 + a*d2/d1;
}
Vector getOrthogonal(Vector a) { return Vector(-a.y, a.x); }

int N;
Point P[N_MAX];

void make(int k, vector<Point> &V) {
  vector<Line> L;
  for(int j = 0; j < N; ++j) {
    if(j == k) continue;
    if(abs(P[k] - P[j]) <= 2.0) {
      Point m = (P[k]+P[j])/2.0;
      L.push_back(Line(P[k], P[j]));
      L.push_back(Line(m, m+getOrthogonal(P[k]-P[j])));
    }
  }
  for(int i = 0; i < L.size(); ++i) {
    for(int j = i+1; j < L.size(); ++j) {
      if(!isParallel(L[i], L[j]))
	V.push_back(getCrossPoint(L[i], L[j]));
    }
  }
}

void solve() {
  vector<Point> V;
  for(int i = 0; i < N; ++i) {
    make(i, V);
  }
  V.erase(unique(V.begin(), V.end()), V.end());
  int ans = 1;
  for(int i = 0; i < V.size(); ++i) {
    int cnt = 0;
    for(int j = 0; j < N; ++j) {
      if(abs(V[i] - P[j]) <= 1.0) cnt++;
    }
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}


main() {
  while((cin >> N) && N) {
    for(int i = 0; i < N; ++i) {
      scanf("%lf,%lf", &P[i].x, &P[i].y);
    }
    solve();
  }
}

Measured memory_bytes: 1484
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll w[100+5];
ll v[100+5];
ll dp[100+5][100000+5];

ll ans(int n, int wt){
    if(n<0) return 0;
if(dp[n][wt]!=-1) return dp[n][wt];
if(w[n]>wt) return dp[n][wt] = ans(n-1,wt);
else{
    return dp[n][wt] = max(ans(n-1,wt-w[n])+v[n], ans(n-1,wt));
}
}
int main(){
    int n, W;
    cin >> n >> W;
    for(int i=0; i<n; i++) cin >> w[i] >> v[i];
    for(int i=0; i<=n; i++){
        for(int j=0; j<=W; j++){
            dp[i][j] = -1;
        }
    }
    cout << ans(n-1,W);
return 0;
}


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int x, k;
  cin >> k >> x;
  vector<int> ans;
  for (int i = x - k + 1; i < x + k; i++) ans.push_back(i);
  cout << ans[0];
  for (int i = 1; i < ans.size(); i++) cout << " " << ans[i];
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int fa[51],siz[51];
ll sv[51],lim[51];
ll f[125010],_f[125010],N=125000;
struct fucker{ll a,b,c;}shit[51];
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi(),X=gi(),d=gi();
	for(int i=1;i<=n;++i)siz[i]=1,sv[i]=gi(),fa[i]=i==1?0:gi(),lim[i]=i==1?1e9:d;
	for(int i=n;i;--i)sv[fa[i]]+=sv[i],siz[fa[i]]+=siz[i];
	memset(f,63,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;++i){
		ll up=std::min(50ll,lim[i]);
		memcpy(_f,f,sizeof f);
		for(int _=0;_<siz[i];++_){
			static int que[125010],hd,tl;hd=tl=0;
			que[tl++]=_;
			for(int j=_+siz[i];j<=N;j+=siz[i]){
				while((hd^tl)&&j-que[hd]>siz[i]*up)++hd;
				if(hd^tl)cnk(f[j],_f[que[hd]]+(j-que[hd])/siz[i]*sv[i]);
				while((hd^tl)&&_f[que[tl-1]]+(j-que[tl-1])/siz[i]*sv[i]>_f[j])--tl;
				que[tl++]=j;
			}
		}
	}
	for(int i=1;i<=n;++i)shit[i]={sv[i],siz[i],std::max(0ll,lim[i]-50)};
	std::sort(shit+1,shit+n+1,[](fucker a,fucker b){return a.a*b.b<a.b*b.a;});
	ll ans=0;
	for(int i=0;i<=N;++i){
		ll rest=X-f[i],sum=i;if(rest<0)continue;
		for(int j=1;j<=n;++j){
			ll cnt=rest/shit[j].a;cnk(cnt,shit[j].c);
			sum+=cnt*shit[j].b;rest-=cnt*shit[j].a;
		}
		cxk(ans,sum);
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 2688
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> pint;
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

int main(){
	int n;
	cin>>n;
	rep(i,n){
		int a=0,b=0;
		bool f=true;
		rep(j,10){
			int k;
			cin>>k;
			if(a<k)a=k;
			else if(b<k)b=k;
			else f=false;
		}
		cout<<(f?"YES":"NO")<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long int li;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
typedef tuple<ll, ll, ll, ll>T;
#define PI 3.14159265359
#define MOD 998244353
const int MAX = 510000;
//この設定だとn<10^7が限界。maxの０を一個増やせば100msかかるが一桁増やせる。
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;
}
template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}
int main() {
    // 前処理
    COMinit();
  ll N,M,K;
  cin>>N>>M>>K;
  ll ans=0;
  for(int i=0;i<=K;i++){
    ll memo;
    memo=COM(N-1,i);
    memo=(M*memo)%MOD;
    memo=(memo*mod_pow(M-1,N-i-1ll,(ll)(MOD)))%MOD;
    ans=(ans+memo)%MOD;
  }
  cout<<ans;
}

Measured memory_bytes: 15588
//
// Created by yamunaku on 2019/08/10.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int main(){
    int n,m,p;
    cin >> n >> m >> p;
    vector<int> a(m),b(m),c(m);
    for(int i=0;i<m;i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--,b[i]--;
        c[i]=p-c[i];
    }
    vector<ll> dist(n, IINF);
    vector<vector<int>> par(n);
    dist[0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dist[a[j]]+c[j]<dist[b[j]]){
                dist[b[j]]=dist[a[j]]+c[j];
                par[b[j]]=vector<int>(1,a[j]);
            }else if(dist[a[j]]+c[j]==dist[b[j]]){
                par[b[j]].push_back(a[j]);
            }
        }
    }
    vector<int> use(n,0);
    use[n-1]=1;
    queue<int> q;
    q.push(n-1);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto nx:par[now]){
            if(use[nx]) continue;
            use[nx]=1;
            q.push(nx);
        }
    }
    for(int i=0;i<m;i++){
        if(dist[a[i]]+c[i]<dist[b[i]]&&use[a[i]]>0&&use[b[i]]>0){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << (-dist[n-1]<0?0:-dist[n-1]) << endl;
    return 0;
}


Measured memory_bytes: 47616
N,D = map(int,input().split())
A=[]
for i in range(N):
    b = list(map(int,input().split()))
    A.append(b)
counter = 0
for i in range(N):
    for j in range((i+1),N):
        n = 0
        for k in range(D):
            n += (A[i][k]-A[j][k])**2
        n = n**0.5
        if n.is_integer() ==True:
            counter += 1

print(counter)


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

int main() {
  int n;
  cin >> n;
  std::set<int> st;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    st.insert(x);
  }
  cout << st.size() << endl;
}


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

using namespace std;

int main() {
  long long n, cap, w, v, i, j, m = 0;
  cin >> n >> cap;
  vector<long long> presack(cap+1,-1);
  presack[0] = 0;
  for (i = 0; i<n; i++) {
    cin >> w >> v;
    for (j = cap; j>0; j--) {
      if (j+w<=cap && presack[j]!=-1) {
        presack[j+w] = max(presack[j+w],presack[j]+v);
        m = max(m,presack[j+w]);
      }
    }
    presack[w] = max(presack[w],v);
    m = max(m,presack[w]);
  }
  cout << m << endl;
  return 0;
}


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

int main()
{
	int n;
	while(cin >> n){
		int x = (n+1) / 1.08;
		if(int(x * 1.08) == n){
			cout << x << endl;
		}
		else
			cout << ":(" << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	Scanner sc;
	final static int UNDEF = 999999999;
	void run(){
		sc = new Scanner( System.in );
		while( true ){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if( n == 0 && m == 0 ){ return; }
			int[] taro = new int[ n ];
			int tsum = 0;
			int[] hana = new int[ m ];
			int hsum = 0;
			for( int i = 0; i < n; i++ ){
				taro[ i ] = sc.nextInt();
				tsum += taro[ i ];
			}
			for( int i = 0; i < m; i++ ){
				hana[ i ] = sc.nextInt();
				hsum += hana[ i ];
			}
			int tt = UNDEF;
			int ht = UNDEF;
			for( int i = 0; i < n; i++ ){
				int ctsum = tsum - taro[ i ];
				for( int j = 0; j < m; j++ ){
					int chsum = hsum - hana[ j ];
					if( ctsum + hana[ j ] == chsum + taro[ i ] ){
						if( ctsum + hana[ j ] < tt + ht ){
							tt = taro[ i ];
							ht = hana[ j ];
						}
					}
				}
			}
			if( tt != UNDEF ){
				System.out.println( tt + " " + ht);
			}else{
				System.out.println( -1 );
			}
		}
	}
	public static void main( String[] args ){
		new Main().run();
	}
}

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

const int MAX_SIZE=1<<22,MOD=1e9+7;
int N;
long long int DP[22][MAX_SIZE],A[22][22];

long long int solve(int pos,int bit){
	if(pos==0) return 1;
	if(DP[pos][bit]!=-1){
		return DP[pos][bit];
	}
	long long int ret=0;
	for(int i=0;i<N;i++){
		if(A[pos][i]&&(!(bit&1<<i))) ret=((ret%MOD+solve(pos-1,bit|(1<<(i)))%MOD)+MOD)%MOD;
	}
	return DP[pos][bit]=ret;
}

void reset(){
	for(int i=1;i<22;i++){
		for(int j=0;j<MAX_SIZE;j++){
//			if(i==0) DP[i][j]=0;
			DP[i][j]=-1;
		}
	}
}

int main(){
	cin>>N;
	reset();
	for(int i=1;i<=N;i++){
		for(int j=0;j<N;j++){
			cin>>A[i][j];
		}
	}
	cout<<solve(N,0)<<"\n";
	return 0;
}

Measured memory_bytes: 688512
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;
using Pos = std::pair<int, int>;
//cout<<fixed<<std:cout<<fixed<<setprecision(2)<<Max<<endl;
constexpr int mod = 1e9 + 7;

int main() {
    int N;
    cin>>N;
    vector<long long> A(N);
    for(auto& a:A)
        cin>>a;

    sort(begin(A),end(A));

    vector<long long> sum(N,0);
    sum[0]=A[0];
    for(int i=1;i<N;++i){
        sum[i]+=sum[i-1]+A[i];
    }

    int ans=0;
    for(int i=0;i<N;++i){
        long long s=sum[i];
        int index=i;
        while(1){
            auto itr=upper_bound(begin(A)+index,end(A),2*s);
            if(itr==end(A)){
                ans=N-i;
                break;
            }
            else{
                if(itr==begin(A)+index+1)break;
                index=itr-begin(A)-1;
                s=sum[itr-begin(A)-1];
            }
        }
        if(ans>0)break;
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
using namespace std;
int input(){
  int x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}
int gcd(int x, int y){
	if(x<y){
    return gcd(y,x);
  }
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}



int main() {
  int A=input();
  int B=input();
  cout<<(A-1)*(B-1)<<endl;
  
  

  



  
  
  

  


}


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

#define ran 202202

int n;
vector<int> e[ran];

int sz[ran], inv[ran], cn[ran];
int f[ran], g[ran];

struct modular_arithmetic{
	int mod;

	modular_arithmetic(){
		mod = 1000000007;
	}
	//No specific settings.
	int add(int x,int y){return (x+=y)<mod?x:x-mod;}
	int sub(int x,int y){return (x-=y)>=0?x:x+mod;}
	int mul(int x,int y){return (int)((long long int)x*y%mod);}
	int pw(int base, int p) {
		int res = 1, mu = base%mod;
		for(;p>0;p/=2) {
			if (p&1) res = mul(res, mu);
			mu = mul(mu, mu);
		}
		return res;
	}
	int rev(int x) {return pw(x, mod-2);}
};
modular_arithmetic ma;

void dfs_sz(int cur, int par) {
	sz[cur] = 1;
	for(int i=0;i<(int)e[cur].size();i++) {
		int nxt = e[cur][i];
		if(nxt==par) continue;
		
		dfs_sz(nxt, cur);
		sz[cur] += sz[nxt];
	}
}

int c(int n, int m) {
	if(m==n) return 1;
	
	int res = 1;
	for(int i=0;i<m;i++)
		res = ma.mul(res, ma.mul(n-i, inv[i+1]));
	return res;
}

void dfs_down(int cur, int par) {
	f[cur] = 1;
	int sum = 0;
	for(int i=0;i<(int)e[cur].size();i++) {
		int nxt = e[cur][i];
		if(nxt==par) continue;
		
		dfs_down(nxt, cur);
		sum += sz[nxt];
		f[cur] = ma.mul(f[cur], ma.mul(f[nxt], c(sum, sz[nxt])));
	}
}

void dfs_up(int cur, int par) {
	for(int i=0;i<(int)e[cur].size();i++) {
		int nxt = e[cur][i];
		if(nxt==par) continue;
		
		g[nxt] = ma.mul(g[cur], ma.rev(ma.mul(f[nxt], cn[sz[nxt]])));
		//printf("- %d %d %d\n", nxt, g[nxt], sz[nxt]);
		g[nxt] = ma.mul(g[nxt], ma.mul(f[nxt], cn[sz[nxt]-1]));
		dfs_up(nxt, cur);
	}
}

int cmp(int x, int y) {
	return sz[x] > sz[y];
}

int main() {
	scanf("%d", &n);
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs_sz(1, -1);
	
	for(int i=1;i<=n;i++)
		sort(e[i].begin(), e[i].end(), cmp);
	inv[1]=1;
	for(int i=2; i<=n; i++)
		inv[i] = 1LL*inv[ma.mod%i]*(ma.mod-ma.mod/i)%ma.mod;
	
	memset(f, 0, sizeof f);
	dfs_down(1, -1);
	
	cn[0] = 1;
	for(int i=1;i<=n-1;i++)
		cn[i] = ma.mul(cn[i-1], ma.mul(n-i, inv[i]));
	g[1] = f[1];
	dfs_up(1, -1);
	
	for(int i=1;i<=n;i++)
		printf("%d\n", g[i]);
	
	return 0;
}

Measured memory_bytes: 17908
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = 0
for i in range(n):
    ans += b[a[i]-1]
    if i > 0 and a[i] == a[i-1]+1:
        ans += c[a[i]-2]
print(ans)


Measured memory_bytes: 3064