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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

inline int addmod(lli x,lli y)
{
    return (x%mod + y%mod)%mod;
}
inline int submod(lli x,lli y)
{
    return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(lli x,lli y)
{
    return (x%mod * y%mod)%mod;
}


inline int nextSubMask(int i, int mask)
{
    return (i-1)&mask;   /// returns next  submask
}

template<typename T>
void we_r_done(T mssg)
{
    cout<<mssg;
    exit(0);
}


int main()
{
    ///freopen("output.txt","w",stdout);
    //freopen("input.txt","r",stdin);
    FastIO;

    string s;
    while(cin>>s){
        int n = s.size();
        lli dp[2][3] , tpow = 1;
        Fill(dp,0);
        int curr = 1;
        for(int i=0; i<n; i++){

            for(int j=0; j<3; j++) dp[curr][j] = dp[curr^1][j];

            if(s[i] == 'A') dp[curr][0] += tpow;
            if(s[i] == 'B') dp[curr][1] += dp[curr^1][0];
            if(s[i] == 'C') dp[curr][2] += dp[curr^1][1];

            if(s[i] == '?'){
                dp[curr][0] = (3*dp[curr^1][0] + tpow);
                dp[curr][1] = (3*dp[curr^1][1] + dp[curr^1][0]);
                dp[curr][2] = (3*dp[curr^1][2] + dp[curr^1][1]);
                tpow = mulmod(3,tpow);
            }
            for(int j=0; j<3; j++) dp[curr][j] %= mod;
            curr ^= 1;
        }
        cout<<dp[curr^1][2]<<endl;
    }

    return 0;
}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,mod,div,i;
    string s;
    vector<char>v;
    cin>>n;
    while(n>0)
    {
        n--;
        mod=n%26;
        //div=n/26;
        n/=26;
        /*if(mod==0)
        {
            mod=26;
            n--;
        }*/
        char j='a'+mod;
        v.push_back(j);
        //cout<<mod<<endl;
    }
    reverse(v.begin(),v.end());
    for(i=0; i<v.size(); i++)
        cout<<v[i];
    v.clear();
    return 0;
}


Measured memory_bytes: 3608
# frozen_string_literal: true

_n = gets.to_i
s = gets.chomp
count = 0
('0'..'9').each do |i|
  t = s.index(i)
  next if t.nil?

  ('0'..'9').each do |j|
    u = s.index(j, t + 1)
    next if u.nil?

    ('0'..'9').each do |k|
      v = s.index(k, u + 1)
      next if v.nil?

      count += 1
    end
  end
end
puts count


Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define inf 1000000000000
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

vector<vi> edges;
vi _,a,comp,vis,best,rest;
ll cur=0;

void dfs(ll v){
  vis[v] = 1;
  comp[v] = cur;
  rep(i,0,edges[v].size()){
    if (!vis[edges[v][i]]) { dfs(edges[v][i]); }
  }
}

int main(){
  ll N,M,x,y,res=0; cin >> N >> M; edges.assign(N,_); a.assign(N,0); vis.assign(N,0); comp.assign(N,-1);
  rep(i,0,N) cin >> a[i];
  rep(i,0,M) { cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); }

  rep(i,0,N){
    if (!vis[i]){ dfs(i); cur++; }
  }

  if (2*(cur-1) > N) { cout << "Impossible" << endl; exit(0); }

  best.assign(cur,inf);
  rep(i,0,N) {
    if (best[comp[i]] > a[i]) {
      if (best[comp[i]] != inf) rest.push_back(best[comp[i]]);
      best[comp[i]] = a[i];
    } else { rest.push_back(a[i]); }
  }
  if (cur == 1) {cout << 0 << endl; exit(0);}
  rep(i,0,best.size()) res += best[i];
  sort(rest.begin(), rest.end());
  rep(i,0,cur-2) res += rest[i];
  cout << res << endl;

}


Measured memory_bytes: 9724
#include <stdio.h>

int main()
{
    int n,flg =0,ko,gyo,cnt=0,kaz;
    scanf("%d",&n);
    char U[101][101];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) U[i][j]='0';
    }
    for(int i=0;i<n;i++){
        kaz =0;flg =0;cnt=0;
        scanf("%d %d",&gyo,&ko);
        for(int j=0;j<ko;j++){
            scanf("%d",&kaz);
            U[i][kaz-1] = '1';
            //printf("i=%c ?",U[i][kaz]);
        }
        //printf("3=%d ?",U[i][3]);
        //U[i][n] = '\0';
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        {
            if(j == 0) printf("%c",U[i][j]);
            else printf(" %c",U[i][j]);
        }
        printf("\n");
    }
}


Measured memory_bytes: 2120
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

//

int32_t main() {
  FAST_IO;
  int n;
  cin >> n;
  if (n % 2) {
    cout << 0;
    rtn 0;
  }
  int p = 10;
  int ans = 0;
  while (p <= n) {
    ans += n / p;
    p *=  5;
  }
  cout << ans << '\n';
  rtn 0;
}


Measured memory_bytes: 256
#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define loop(i, a, n) for(int i = (a); i < (n); i++)
#ifdef _DEBUG
#define dd(x) cout << #x << " : " << x << endl
#else
#define dd(x)
#endif
using namespace std;
using ll = int64_t;

// 引用元：https://qiita.com/DaikiSuyama/items/444e409423bd1b4b83d7
class UnionFind{
public:
    vector<ll> parent;
    vector<ll> siz;
    map<ll,vector<ll>> group;
    ll n;

    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);
    }

    void unite(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        if(rx==ry) return;
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;
    }

    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    ll size(ll x){
        return siz[root(x)];
    }

    void grouping(){
        rep(i,n)root(i);
        rep(i,n)group[parent[i]].push_back(i);
    }

    void clear(){
        rep(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

int main(){
    int n, m; cin >> n >> m;
    UnionFind uf = UnionFind(n);
    rep(i, m) {
        int a, b; cin >> a >> b;
        uf.unite(--a, --b);
        uf.unite(b, a);
    }

    int ans = 0;
    set<int> st;
    rep(i, n) {
        st.insert(uf.root(i));
    }

    cout << st.size() - 1 << endl;

    return 0;
}


Measured memory_bytes: 8408
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> t(N);
	vector<Int> a(N);
	for (Int i = 0; i < N; i++) {
		cin >> t[i] >> a[i];
	}

	Int temp;
	Int b, c;
	for (Int i = 0; i < N-1; i++) {
			temp = max((t[i] + (t[i + 1] - 1)) / t[i + 1], (a[i] + (a[i + 1] - 1)) / a[i + 1]);
			//b = (t[i] + (t[i + 1] - 1)) / t[i + 1];
			//c = (a[i] + (a[i + 1] - 1)) / a[i + 1];
			//temp = max(b, c);

			t[i + 1] *= temp;
			a[i + 1] *= temp;
	}

	cout << t[N - 1]+ a[N - 1] << "\n";

}

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

int main() {
    ll S; cin >> S;
    ll x1 = 1;
    ll y1 = 1e9;
    ll x2 = (S + (y1 - 1)) / y1;
    ll y2 = (y1 - 1) - (S + (y1 - 1)) % y1;
    cout << "0 0 ";
    cout << x1 << " " << y1 << " ";
    cout << x2 << " " << y2 << endl;
    // cout << abs(x1 * y2 - x2 * y1) << endl;
    return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const ll max_co = 3234600000;
vl ans;
int mod =1000000007;
int main(){
   int n,k;
   string s;
   cin>>n>>k>>s;
   int count = 0;
   rep(i,n-1){
       if(s[i]=='R'&&s[i+1]=='R')count++;
   }
   for(int i=n-1;1<=i;i--){
       if(s[i]=='L'&&s[i-1]=='L')count++;
   }

   cout<<min(2*k+count,n-1)<<endl;

}


Measured memory_bytes: 512
#include <set>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#define MAXN 10010
#define LL long long
#define INF 0x7fffffff
using namespace std;

int main(){
	int num[100005];
	int t[100005];
	memset(t,0,sizeof(t));
	int n;
	cin>>n;
	for (int i=0;i<n;i++) {
		int k;
		cin>>k;
		num[i]=k+1;
		t[k+1]++;
		t[k]++;
		t[k+2]++;
	}
	int ans=0;
	for (int i=0;i<100005;i++){
		ans=max(ans,t[i]);
	}
	cout<<ans<<endl;
	return 0;
}

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

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

    vector<long long int> a(n+2);// a[0] = a[n+1] = 0
    long long int sum = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        sum += abs(a[i] - a[i-1]);
    }
    sum += abs(a[n+1] - 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;
    }
    return 0;
}

Measured memory_bytes: 2048
import math

D,G=map(int,input().split())


score=[None]*D
for i in range(D):
    score[i]=list(map(int,input().split()))


import itertools
bitlist=list(itertools.product((0,1),repeat=D))

def xx(a):
    XX=[0 for i in range(D)]
    for i in range(len(a)):
        if a[i]==1:
            XX[i]=score[i][0]
    return XX


def scoresolve(X):
    ANS=0
    for i in range(len(X)):
            ANS+=X[i]*(i+1)*100
            if X[i]==score[i][0]:
                ANS+=score[i][1]

    return ANS





ANS=100000
for bit in bitlist:
    ii=xx(bit)
    if scoresolve(ii)>=G:
        ANS=min(ANS,sum(ii))
    else:
        j=D-ii[::-1].index(0)-1
        if G-scoresolve(ii)<=(j+1)*100*score[j][0]:
            ANS=min(ANS,sum(ii)+math.ceil((G-scoresolve(ii))/(j+1)/100))

print(ANS)
            
            

        
        
    


Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<numeric>
#include<set>
#include<math.h>
using namespace std;

int A, B, K;

int gcd(int m, int n){
    int m1 = m;
    int n1 = n;
    int tmp = 0;

    while(n1 != 0){
        tmp = m1 % n1;
        m1 = n1;
        n1 = tmp;
    }

    return m1;
}

int main(){
    cin >> A >> B >> K;
    
    int cnt = 1;
    int ans = gcd(A, B);

    while(cnt < K){
        ans--;
        if(A % ans == 0 && B % ans == 0) cnt++;
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))

b=[0]*n
oddsum=0
evensum=0
for i in range(n):
    if i%2==0:
        oddsum+=a[i]
    else:
        evensum+=a[i]

b[0]=oddsum-evensum

for i in range(1,n):
    c=b[i-1]-a[i-1]
    b[i]=-c
    b[i]+=a[i-1]

L=[str(a) for a in b]
ans=" ".join(L)
print(ans)

Measured memory_bytes: 26072
#include<stdio.h>
int main()
{
	int n,p,d1,d2,i,m,a;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		m=0;
		for(i=0;i<n;i++){
			scanf("%d%d%d",&p,&d1,&d2);
			if(d1+d2>m){
				a=p;
				m=d1+d2;
			}
		}
		printf("%d %d\n",a,m);
	}
	return 0;
}

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

using namespace std;

int main() {
    int64_t n, m;
    cin >> n >> m;

    int64_t total = 0;
    int64_t add1 = min(n, m / 2);
    total += add1;
    n -= add1;
    m -= 2 * add1;
    int64_t add2 = m / 4;
    total += add2;
    m -= 4 * add2;

    cout << total << endl;
}


Measured memory_bytes: 256
a,b = map(int,input().split())
s=list(input())
ans="Yes"
for i in range(a):
    if(s[i]=="-"):
        ans="No"
for i in range(b):
    i+=a+1
    if(s[i]=="-"):
        ans="No"
if(s[a]!="-"):
    ans="No"
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int n,count=1; cin>>n;
 char s[n]; for(int i=0;i<n;i++)cin>>s[i];
  
  for(int i=0;i<n-1;i++){
  
  if (s[i] != s[i+1]) {count++;}
    
  }
  
  cout<<count;
}
 

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

using namespace std;

string p;
string q;

vector <string> v;

int rez[5];

string f;

int n,k;

int st[12];

void init()
{
    st[k] = 0;
}

int succesor()
{
    if(st[k] < n && k <= n)
    {
        st[k]++;
        return 1;
    }

    return 0;
}

int valid()
{
    for(int i = 0; i < k; i++)
        if(st[i] == st[k])
        return 0;

    return 1;
}

int sol()
{
    return k == n;
}

void tipar()
{
    for(int i = 1; i <= k; i++)
        f.push_back(char(st[i]));

    v.push_back(f);
    if(q == f)
        rez[1] = v.size();
    if(p == f)
        rez[2] = v.size();

    f.clear();
}

void bt()
{
    k = 1;

    init();
    while(k)
    {
        int as = 1;
        int ev = 0;

        while(as&&!ev)
        {
            as = succesor();
            if(as)
                ev = valid();
        }
        if(as)
            if(sol())
                tipar();
        else
        {
            k++;
            init();
        }
        else
        k--;
    }
}
int main()
{
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        p.push_back(char(x));
    }

    for(int i = 0 ; i < n; i++)
    {
        int x;
        cin >> x;
        q.push_back(char(x));
    }

    bt();

   cout << abs(rez[1] - rez[2]);

    return 0;
}


Measured memory_bytes: 2424
import java.util.Scanner;

//Patisserie
public class Main{

	static double[][][] dp;
	static int[] r;
	static int n;
	static double[][] cach;
	
	static double get(int left, int s, int right){
		if(dp[left][s][right]!=0)return dp[left][s][right];
		int c = 0;
		for(int i=0;i<n;i++)if((s&(1<<i))>0)c++;
		if(c==1){
			return dp[left][s][right] = 2*r[left];
		}
		if(c==2){
			if(r[left]==r[right])return dp[left][s][right] = 4*r[left];
			else return dp[left][s][right] = r[left]+r[right]+cach[left][right];
		}
		double min = Integer.MAX_VALUE;
		for(int i=0;i<n;i++){
			if((s&(1<<i))==0 || i==left || i==right)continue;
			for(int j=0;j<n;j++){
				if((s&(1<<j))==0 || j==right || j==left)continue;
				if(c>3 && i==j)continue;
				double x = r[left]+r[right]-r[i]-r[j]+get(i, s-(1<<left)-(1<<right),j) + cach[left][i] + cach[right][j];
				min = Math.min(min, x);
			}
		}
		return dp[left][s][right] = min;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String[] s = sc.nextLine().split(" ");
			n = s.length-1;
			int len = Integer.parseInt(s[0]);
			r = new int[n];
			for(int i=0;i<n;i++)r[i]=Integer.parseInt(s[i+1]);
			cach = new double[n][n];
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(i==j)cach[i][j]=2*r[i];
					else{
						if(r[i]==r[j])cach[i][j]=2*r[i];
						else cach[i][j] = Math.sqrt(Math.pow(r[i]+r[j], 2)-Math.pow(r[i]-r[j], 2));
					}
				}
			}
			dp = new double[n][1<<n][n];
			double min = Integer.MAX_VALUE;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(n>1 && i==j)continue;
					min = Math.min(min, get(i, (1<<n)-1, j));
					if(min<=len)break;
				}
				if(min<=len)break;
			}
			System.out.println(min<=len?"OK":"NA");
		}
	}
}

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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> s(h);
  for (int i = 0; i < h; i++) cin >> s.at(i);
  int id = 0, lastrow;
  vector<vector<int>> a(h, vector<int>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (s.at(i).at(j) == '#') {
        id++;
        lastrow = i;
        a.at(i).at(j) = id;
        for (int k = j - 1; k >= 0 && a.at(i).at(k) == 0; k--) {
          a.at(i).at(k) = id;
        }
      }
    }
    if (a.at(i).at(0) != 0 && a.at(i).at(w - 1) == 0) {
      for (int k = w - 1; a.at(i).at(k) == 0; k--) {
        a.at(i).at(k) = id;
      }
    }
    for (int l = i - 1; l >= 0 && a.at(l).at(0) == 0; l--) {
      for (int j = 0; j < w; j++) {
        a.at(l).at(j) = a.at(i).at(j);
      }
    }
  }
  for (int i = lastrow + 1; i < h; i++) {
    for (int j = 0; j < w; j++) {
      a.at(i).at(j) = a.at(lastrow).at(j);
    }
  }
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << a.at(i).at(j);
      if (j == w - 1) {
        cout << "\n";
      } else {
        cout << " ";
      }
    }
  }
}


Measured memory_bytes: 1280
//むずすぎ　理解追いついてない
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(){
  int ans = 0,N,M;
  cin >> N >> M;
  int p;
  vector<int> k(M);
  vector<int> a(N);
  for(int i=0;i<M;i++){
    cin >> k[i];
    for(int j=0;j<k[i];j++){
      int s;
      cin >> s;
      a[--s] |= 1 << i;
    }
  }
  for(int i=0;i<M;i++){
    int x;
    cin >> x;
    p |= x << i;
  }
  for(int s=0; s<(1<<N); s++){
    int t = 0;//状態
    for(int i=0;i<N;i++){
      if(s>>i&1){//iビット目が立っているか
        t ^= a[i];
      }
    }
    if(t == p){
      ans++;
    }
  }


  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static final int INF = Integer.MAX_VALUE / 2 - 1;
	public static final int M_MAX = 6;
	public static final int N_MAX = 100;
	public static final int MAX = M_MAX + N_MAX + 2;
	
	public static int node_num(int n, int m, String in){
		//System.out.println(in);
		
		// 0 ~ m - 1 >= cakes
		// m => home
		// m + 1 to n + m + 1 => Landmark
		// n + m + 2 => goal
		
		if("H".equals(in)){
			return m;
		}else if("D".equals(in)){
			return n + m + 1;
		}else{
			return Integer.parseInt(in.substring(1)) + (in.charAt(0) == 'L' ? m : -1);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[][] adj = new int[MAX][MAX];
		int[][] cal_array  = new int[MAX][1 << M_MAX];
		int[] cal_in = new int[M_MAX];
		
		while(true){
			final int m = sc.nextInt();
			final int n = sc.nextInt();
			final int k = sc.nextInt();
			final int d = sc.nextInt();
			
			if(n == 0 && m == 0 && k == 0 && d == 0){
				break;
			}
			
			Arrays.fill(cal_in, 0);
	
			for(int i = 0; i < m; i++){
				cal_in[i] = sc.nextInt();
			}
			
			final int max    = n + m + 2; 
			final int home   = m;
			final int arrive = n + m + 1;
			
			for(int i = 0; i < max; i++){
				for(int j = 0; j < max; j++){
					adj[i][j] = INF;
				}
			}
			
			for(int i = 0; i < d; i++){
				final int from = node_num(n, m, sc.next());
				final int to   = node_num(n, m, sc.next());
				
				final int dist = sc.nextInt();
				
				///System.out.println(from + " "+ to);
				
				adj[from][to] = adj[to][from] = Math.min(adj[from][to], dist * k);
			}
			
			for(int i = 0; i < max; i++){
				Arrays.fill(cal_array[i], INF);
			}
			cal_array[home][0] = 0;
			
			final int bit_max = 1 << m;
			while(true){
				boolean updated = false;
				
				//System.out.println("test");
				
				for(int node = 0; node < max; node++){
					for(int bit = 0; bit < bit_max; bit++){
						if(cal_array[node][bit] >= INF){
							continue;
						}
						
						//System.out.println(node + " " + Integer.toBinaryString(bit));
						
						for(int next = 0; next < max; next++){
							if(node == next){
								continue;
							}else if(adj[node][next] >= INF){
								continue;
							}
							
							//System.out.println(node + " " + next);
							
							int next_cost = 0;
							int next_bit  = 0;
							
							if(next < m){
								if((bit & (1 << next)) != 0){
									continue;
								}
								
								next_cost = cal_array[node][bit] + adj[node][next] - cal_in[next];
								next_bit  = bit | (1 << next);
							}else{
								next_cost = cal_array[node][bit] + adj[node][next];
								next_bit = bit;
							}
							
							//System.out.println(next + " " + node);
							
							if(cal_array[next][next_bit] > next_cost){
								cal_array[next][next_bit] = next_cost;
								updated = true;
							}
						}
					}
				}
				
				if(!updated){
					break;
				}
			}
			
			int min = Integer.MAX_VALUE;
			for(int i = 0; i < bit_max; i++){
				min = Math.min(min, cal_array[arrive][i]);
			}
			
			System.out.println(min);
		}
		
		sc.close();
	}
}

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



int main() {
    ll N, K;
    cin >> N >> K;
    ll ans = 0;
    while(N > 0){
        ans++;
        N /= K;
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	int H, W, i, j;
	while(1){
		cin >> H >> W;
		if(H == 0 and W == 0){
			break;
		}else{
			for(j = 0; j < W; j ++){
				cout << "#";
			}
			cout << endl;
			for(i = 2; i < H; i++){
				cout << "#";
				for(j = 2; j < W; j ++){
					cout << ".";
				}
				cout << "#" << endl;
			}
			for(j = 0; j < W; j ++){
				cout << "#";
			}
			cout << endl;
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3096
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <regex>
#include <stdexcept>
#include <unordered_set>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <cassert>
#include <time.h>
#include <numeric>
#include <complex>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define fill(x, y) memset(x, y, sizeof(x))
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define itn int
#define re return
#define prev PREV
#define next NEXT

#define sz(x) ((int)x.size())

const int inf = 2e9;
const ld st = 0.000001;
const ld pi = acos((ld)-1);
const int maxn = 2*1000005;

#define FILENAME ""

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    vector <ll> a;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        a.pb(x);
    }
    vector <ll> dp(sz(a) + 1, inf);
    dp[0] = 0;
    dp[1] = abs(a[1] - a[0]);
    for (int i = 2; i < n; i++) {
        for (int j = i - 1; j >= max((i - k), (ll)0); j--) {
            dp[i] = min(dp[i], dp[j] + abs(a[i] - a[j]));
        }
    }
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 1908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,(e))
#define irp(i,s,e) for(int i=(s);i>(e);--i)
#define irpz(i,s) irp(i,(s),-1)
template<class T> T in(){T x;cin>>x;return x;}
// long long a = in<long long>();
template<class T> vector<T> inarr(int s,int e, T init=0){
	vector<T> v;T x;
	rp(i,0,s)v.push_back(init);
	rp(i,s,e){x=in<T>();v.push_back(x);}
	return v;
}
// vi P = inarr<int>(1,N+1,INT_MAX);
// vi P = inarr<int>(0,N);

// #define NMAX 1000000000
int H,N;
string S, T;
using PLL = pair<ll,ll>;
using VP = vector<PLL>;
VP AB;

ll solve(){
	ll ans=0;

	// rp(i,0,AB.size()){
	// 	cout<<i<<" ";
	// 	cout<<AB[i].first<<" "<<AB[i].second<<"\n";
	// }

	ll INF = LLONG_MAX>>2;
	vvl dp(N+1, vl(H+1, INF));
	dp[0][0] = 0;
	rp(i,1,N+1){
		ll mp,hp;tie(hp,mp)=AB[i-1];
		rp(j,0,H+1){
			if(j==0) dp[i][j] = 0;
			if(j-hp>=0) dp[i][j] = min(dp[i-1][j], dp[i][j-hp] + mp);
			else dp[i][j] = min(dp[i-1][j], mp);

		}
	}

	ans = dp[N][H];
	return ans;
}

int main(){
	cin>>H;
	cin>>N;
	rp(i,0,N){
		int a,b;
		cin>>a>>b;
		AB.emplace_back(a,b);
	}
	cout<< solve() <<endl;
}


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

const int MAX_N =510000;

int par[MAX_N];
int depth[MAX_N];

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

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

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

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


int main(){
    int N, M;
    cin >> N >> M;
    init(N+1);
    int num=N;
    for(int i=0; i<M; i++){
        int X, Y ,Z; cin >> X >> Y >> Z;
        if(!same(X,Y)){
            unite(X,Y); num--;
        }
    }
    cout << num << endl;
}

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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX (int)(1e12)

long long power(unsigned __int128 x, unsigned __int128 n){
	unsigned __int128 ans = 1;
	while(n){
		if((double)ans*x > MAX) return -1;
		if(n&1) ans *= x;
		n >>= 1;
		x *= x;
		if(ans > MAX) return -1;
	}
	return (long long)ans;
}


signed main(){
	int N, P, ans = 1;
	
	cin>>N>>P;
	
	if(N==1){
		cout<<P<<endl;
		return 0;
	}
	
	for(int i = 2; i*i <= P; i++){
		int t = power(i,N);
		if(t < 0 || t > P)break;
		if(P%t==0)ans = i;
		
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <stdio.h>
//#define ULLONG_MAX implementation-defined
using namespace std;

int main(void)
{
	int x, t;
	cin >> x >> t;
	if(x - t > 0)
		cout << x - t << endl;
	else
		cout << 0 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long A,B,C,K;
    cin >> A >> B >> C >> K;
    long long D = K - (A+B);
    if(K < A) cout << K << endl;
    else if(D < 0) cout << A << endl;
    else cout << A - D << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9 + 7;
const int MAX = 510000;

int main(){
    string s; cin >> s;
    string ans = "ABC" + s;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  string s;
  int cnt=0;
  cin>>s;
  int len=s.length();
  for(int i=1;i<len;i++){
    if(s[i]!=s[i-1])	cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 512
while 1:
 n=int(input())
 if n==0:break;
 a=[list(map(int,input().split()))for _ in[0]*n]
 for r in a:
  for s in r:print(f"{s:5}",end='')
  print(f"{sum(r):5}")
 for c in zip(*a):print(f"{sum(c):5}",end='')
 print(f"{sum([sum(r)for r in a]):5}")


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)

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

struct edge {
	int to,cost;
	edge(int t,ll c):to(t),cost(c) {}
};

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

ll mypow(ll x,ll n,ll m) {
	if(n==0) return 1;
	if(n%2==0) return mypow(x*x%m,n/2,m);
	else return x*mypow(x,n-1,m)%m;
}

//-----------------------------------------------------------------------------

int n,a,b;

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

	cin>>n>>a>>b;
	cout<<min(a*n,b)<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define CR cerr<<endl;
#define MOD 1000000007
#define INF 9223372036854775807
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));
signed main(){
	string S; cin >> S;
	bool is_Yes = false;
	if(S[0] == S[1] and S[1] == S[2]) is_Yes = false;
	else if(S[0]==S[1] and S[2] == S[3]) is_Yes = true;
	else if(S[0]==S[2] and S[1] == S[3]) is_Yes = true;
	else if(S[0] == S[3] and S[1] == S[2]) is_Yes = true;

	if(is_Yes) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long int f(int n){
    long long int res = 1;
    int x = n;
    for(;n> x-2; n--) res *= n;
    return res;
}

int main(void){
    long long int N, M;
    long long int ans = 0;
    cin >> N >> M;
    ans = f(N)/2;
    ans += f(M)/2;
    cout << ans << endl;
    return 0;
}

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

using ll = long long;

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define pb push_back
#define mp make_pair
#define fill(x, y) memset(x, y, sizeof(x))
#define even(x) x % 2 == 0
#define odd(x) x % 2 != 0
#define all(x) x.begin(), x.end()
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

// these functions return the position of result of Binary Search.
#define LB(s, t, x) (int) (lower_bound(s, t, x) - s)
#define UB(s, t, x) (int) (upper_bound(s, t, x) - s)

ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts>
auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); }
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }
// auto dp = make_v<int>(4, h, w);
// fill_v(dp, 0);

const ll INF_LL = (1ll << 60);
const int INF_INT = (int)1e9;
const ll MOD_CONST = (ll)(1e9 + 7);

template <class T>
bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T>
bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

inline tuple<ll, ll> rotate45(tuple<ll, ll> p) { ll x = get<0>(p), y = get<1>(p); return tuple<ll, ll>(x + y, x - y); }

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

	int N, MA, MB; cin >> N >> MA >> MB;
	auto dp = make_v<int>(41,405,405); fill_v(dp, INT32_MAX);
	dp[0][0][0] = 0;
	
	REP(i, N) {
		// 薬品i
		int a, b, c; cin >> a >> b >> c;
		REP(j, 401) {
			REP(k, 401) {
				if (dp[i][j][k] == INT32_MAX) continue;
				// 薬品iを加えない
				chmin(dp[i + 1][j][k], dp[i][j][k]);
				// 加える
				if (j + a >= 404) continue;
				if (k + b >= 404) continue;
				chmin(dp[i + 1][j + a][k + b], c + dp[i][j][k]);
			}
		}
	}

	int ans = INT32_MAX;
	REP(ca, 401) {
		REP(cb, 401) {
			if (cb == 0 and ca == 0) continue;
			if (cb == INT32_MAX or ca == INT32_MAX) continue;
			if (ca * MB == cb * MA)
				chmin(ans, dp[N][ca][cb]);
		}
	}
	cout << ((ans == INT32_MAX) ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 27776
#include<iostream>
#define D(x) cout<<"D:"<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int k;
		cin>>k;
		if(!(k%2) && k%3 && k%5)
		{
			puts("DENIED");
			return 0;
		}
	}
	puts("APPROVED");
	return 0;
}


Measured memory_bytes: 256
import Data.Char
import Control.Monad

main = do
  ns <- map digitToInt <$> getLine
  putStrLn $ solve ns operators

operators :: [(Int -> Int -> Int, Char)]
operators = [((+), '+'), ((-), '-')]

solve :: [Int] -> [(Int -> Int -> Int, Char)] -> String
solve [a, b, c, d] operators = (++"=7") . head $ do
  (op1, op1c) <- operators
  (op2, op2c) <- operators
  (op3, op3c) <- operators
  guard $ a `op1` b `op2` c `op3` d == 7
  return [intToDigit a, op1c, intToDigit b, op2c, intToDigit c, op3c, intToDigit d]

Measured memory_bytes: 508
#include<bits/stdc++.h>
#define mod 998244353
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long
using namespace std;

int n,m;
int Pow(int b,LL k){ int r=1;for(;k;k>>=1,b=1ll*b*b%mod) if(k&1) r=1ll*r*b%mod;return r; }

int main(){
	scanf("%d%d",&n,&m);
	int Cn=1,Cm=1,ans=0,fc=1;
	rep(i,0,min(n,m)){
		ans = (ans + 1ll * Cn * Cm % mod * (i&1 ? -1ll : 1ll) * fc % mod * Pow(m+1,n-i) % mod * Pow(n+1,m-i)) % mod;
		Cn = 1ll * Cn * (n-i) % mod * Pow(i+1 , mod-2) % mod;
		Cm = 1ll * Cm * (m-i) % mod * Pow(i+1 , mod-2) % mod;	
		fc = 1ll * fc * (i+1) % mod;
	}
	printf("%d\n",(ans+mod)%mod);
}

Measured memory_bytes: 3816
#include<stdio.h>
int a[8][8], row[8], col[8], c[17], d[17];
int QP(int ,int ,int);
 
int main(){
    int k, i, j, x, y;
    scanf("%d", &k);
    for(i = 1; i <= k; i++){
        scanf("%d %d", &x, &y);
        a[x][y] = 1;
        row[x] = col[y] = c[x+y] = d[y - x + 7] = 1;
    }
    QP(0, 0, 8);
    for(i = 0; i < 8; i++){
        for(j = 0; j < 8; j++){
            if(a[i][j])
                printf("Q");
            else
                printf(".");
        }
        printf("\n");
    }
}
int QP(int i, int j, int s){
    int i1 = i + (j==7), j1 = (j + 1) % 8;
    if(s == 0)
        return 1;
    if(i > 7)
        return 0;
    if(a[i][j] == 1){
        if(QP(i1, j1, s-1))
            return 1;
        return 0;
    }
    if(row[i] == 0 && col[j] == 0 && c[i + j] == 0 && d[j - i + 7] == 0){
        a[i][j] = 1;
        row[i] = col[j] = c[i + j] = d[j - i + 7] = 1;
        if(QP(i1, j1, s-1))
            return 1;
        row[i] = col[j] = c[i + j] = d[j - i + 7] = 0;
        a[i][j] = 0;
    }
    if(QP(i1, j1, s))
        return 1;
    return 0;
}



Measured memory_bytes: 2108
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

k = int(input())

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)

print(ans)

Measured memory_bytes: 69580
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<stack>
#include <cstring>
#include <climits>
using namespace std;
#define rep(i,n) for(int (i)=0;(i) < (n); (i)++)
#define rrep(f,i,n) for(int (i)=0;(i) < (f); (i)++)
#define FIND(v, k) find((v).begin(), (v).end(), k)
#define mset(a,x) memset(a,x,sizeof(a))

#define MAX 101
#define MAX_V 15

string b[500];
int main()
{
	long long m, n;
	cin >> m >> n;
	if (abs(m - n) > 1) {
		cout << 0 << endl;
	}
	else {
		long long result = 1;
		if (m == n) {
			for (int j = 0; j < 2; j++) {
				for (int i = 2; i <= m; i++) {
					result *= i;
					result %= 1000000007;
				}
			}
			result *= 2;
			result %= 1000000007;
			cout << result << endl;
		}
		else {
			for (int i = 2; i <= n; i++) {
				result *= i;
				result %= 1000000007;
			}
			for (int i = 2; i <= m; i++) {
				result *= i;
				result %= 1000000007;
			}
			cout << result << endl;

		}
	}
	return 0;
}



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

int main(){
  int H, W;
  cin >> H >> W;
  string b;
  for(int j = 0; j < W + 2; j++){
    b += '#';
  }
  cout << b << endl;
  for(int i = 0; i < H; i++){
    string a;
    cin >> a;
    cout << '#' + a + '#' << endl;
  }
  cout << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    
    
	 long long n,i,j,k,sum=0,count=0,ans=0,x,y,l,r,m;
     cin>>n;
     long long a[n],b[n],c[n];
     for(i=0;i<n;i++)
     {
         cin>>a[i];
         b[i]=a[i]+i;
         c[i]=-a[i]+i;
     }
     
     map<long long ,long long>m1,m2;
     m1[b[0]]++;
     m2[c[0]]++;
     for(i=1;i<n;i++)
     {
         m2[c[i]]++;
         ans+=m1[c[i]];
         m1[b[i]]++;
     }
    cout<<ans;
    
}

Measured memory_bytes: 42524
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)
#define SUMV(v)		(accumulate(v.begin(),v.end(),0.0))

#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int ll;

//int dp[MAX];

int main(){
	int a,b;cin>>a>>b;

	int w=1,e=3;
	REPS(i,3,1001){
		if((w-a)==(e-b)&&e>b){
			cout << (w-a) << endl;
			break;
		}
		w=e;
		e+=i;
	}

	return 0;
}

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

signed main(){
  int n;
  cin>>n;
  vector<int> p(n);
  for(auto& i:p)cin>>i;
  int lw=p[0],r=1;
  for(int i=1;i<n;++i){
    if(p[i]<=lw)++r;
    lw=min(lw,p[i]);
  }
  cout<<r;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define ll long long
using namespace std;
int n;
ll a,b;
ll x[maxn];
int main()
{

    scanf("%d%lld%lld",&n,&a,&b);

    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i]);
        ll ans=0;
        for(int i=2;i<=n;i++)
        {
            if((x[i]-x[i-1])*a>b)
                ans+=b;
            else
                ans+=(x[i]-x[i-1])*a;
        }
        printf("%lld\n",ans);
        return 0;
}


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

int main() {
    int n;
    cin>>n;
    int w[n]={0};
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    int a[n]={0};
    int x=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j<=i){
                a[i]+=w[j];
            }else{
                a[i]-=w[j];
            }
        }
        if(a[i]>0){
            x=i;
            break;
        }
    }
    if(a[x-1]+a[x]>=0){
        cout<<-1*a[x-1]<<endl;
    }else{
        cout<<a[x]<<endl;
    }
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import collections
N = int(input())
A = list(map(int,input().split()))
Min = min(A)
Max = max(A)
d = {i:0 for i in range(Min,Max+1)}
for ii in A:
    d[ii] += 1
s = [0] * (Max-Min+1)
n = len(s)
s[0] = d[Min]
for k in range(1,n):
    s[k] = s[k-1] + d[Min+k]
ss = 0
if n <= 3:
    ss = s[n-1]
    print(ss)
else:
    mmax = s[2]
    for i in range(3,n):
        mmm = s[i] - s[i-3]
        mmax = max(mmm,mmax)
    print(mmax)







Measured memory_bytes: 21532
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
using namespace std;


int main() {

	long long N;
	cin >> N;

	vector<long long> X(N, 0);
	vector<long long> D(N, 0);
	for (long long i = 0; i < N; i++) {
		cin >> X[i];
		D[i] = X[i];
	}

	sort(D.begin(), D.end());

	long long v1 = D[N / 2 - 1];
	long long v2 = D[N / 2];

	for (long long i = 0; i < N; i++) {
		if (X[i] <= v1) {
			cout << v2 << endl;
		}
		else {
			cout << v1 << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 6392
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 100;
queue<int> Q;
vector<int> G[maxn];
int f[maxn], col[maxn], in[maxn];
void dfs(int x, int fa){
    f[x] = fa;
    for(auto to : G[x]){
        if(to == fa) continue;
        dfs(to, x);
    }
}
int n, x, y;
int main()
{
    cin>>n;
    for(int i = 0; i < n-1; i++){
        cin>>x>>y;
        in[x]++; in[y]++;
        G[x].pb(y); G[y].pb(x);
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        if(in[i] == 1) Q.push(i);
    }
    int label = 0;
    f[1] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        if(col[f[x]]) label = 1;
        else{
            col[f[x]] = 1;
            in[f[f[x]]]--;
            if(in[f[f[x]]] == 0) label = 1;
            if(in[f[f[x]]] == 1 && f[f[x]] != 1) Q.push(f[f[x]]);
        }
    }
    cout<<(label ? "First" : "Second")<<endl;
    return 0;
}


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

ll pow(ll a,ll b){

    ll r =1;

    while(b){
        if(b%2!=0) r=(r*a);
        a=(a*a);
        b/=2;
    }

    return r;
}

const int sz = 5e5+20;
ll fact[sz], inv[sz];
void pre(){
	fact[0] = 1;
	inv[0] = pow(fact[0], mod-2);
	for(int i=1;i<sz;i++){
		fact[i] = (fact[i-1]*i)%mod;
	}
}

int allmask;
int dp[1<<21];
int n;
vector<vector<int>> v(22);

int count(int a,int j){
    
    if(a==allmask) return 1;
    if(j>=n) return 0;

    if(dp[a]!=-1) return dp[a];
    
    int ways = 0;
    for(int i=0;i<v[j].size();i++){
        if(!(a&(1<<v[j][i]))) ways+=(count(a|(1<<v[j][i]),j+1));
        ways%=mod;
    }

    return dp[a]=ways;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int a;
            cin>>a;
            if(a) v[i].push_back(j);
        }
    }

    memset(dp,-1,sizeof(dp));
    allmask = (1<<n)-1;

    cout<<count(0,0);
}

Measured memory_bytes: 11796