akhauriyash/Code-Regression huggingface dataset:
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End


/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template


signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Cinii(N,L);
    int absMin = INF,total = 0,absMinSign = +1;
    rep(i,N){ absMin = min(absMin,abs(L+i)); absMinSign = ((L+i>=0)? 1:-1); }
    rep(i,N) total += (L+i);
    cout << total - absMin * absMinSign << nn;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int f(int x) {
  if(x%2==0)
    return x/2;
  return 3*x+1;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  int s;
  cin>>s;
  set<int> found;
  found.insert(s);
  repeat(i,2,1000000+1) {
    s=f(s);
    if(found.find(s)!=found.end()) {
      cout << i << endl;
      return 0;
    }
    found.insert(s);
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

#define lo long long
using namespace std;

lo n,p,a,tab[5];
int main()
{
    cin>>n>>p;
    p%=2;
    for (int i=0;i<n;i++)
    {
        cin>>a;
        tab[a%2]++;
    }

    if (tab[1]==0 && p==1)
    {
        cout<<0<<endl;
        return 0;
    }
    else
    {
        lo pkt=tab[0]+tab[1]-1;
        if (p==0 && tab[1]==0) pkt++;
        lo ans=1;
        for (int i=0;i<pkt;i++) ans*=2;
        cout<<ans<<endl;
        return 0;
    }
}


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

#define IOS cin.tie(0);ios::sync_with_stdio(false)

#define ll      long long
#define Fi      first
#define Se      second
#define Pb      push_back
#define vi      vector<int>
#define vp      vector<pair<int,int>>
#define vvi     vector<vector<int>>
#define vvp     vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define all(v) v.begin(),v.end()
#define output_s(s) printf("%s\n",(s).c_str())

#define rep(i,n)        for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m)      for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m)     for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m)    for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x)         for(auto &item:(x))

void CINT(){} //@shibh308's template
template <class Head,class... Tail> void CINT(Head&& head,Tail&&... tail){cin>>head; CINT(move(tail)...);}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

void OUT(){}
template<class Head,class...Tail> void OUT(Head&& head,Tail&&...tail){cout<<head<<(sizeof...(tail)?' ':'\n'); OUT(move(tail)...);}
#define COUT(...) OUT(__VA_ARGS__)

template<typename TypeInt>TypeInt GCD(TypeInt a,TypeInt b){return a%b==0?b:GCD(b,a%b);} //最大公約数
template<typename TypeInt>TypeInt LCM(TypeInt a,TypeInt b){return a*b/GCD(a,b);}//最小公倍数

void YES(bool f){printf(f?"YES\n":"NO\n");}
void Yes(bool f){printf(f?"Yes\n":"No\n");}
void Possible(bool f){printf(f?"Possible\n":"Impossible\n");}
void POSSIBLE(bool f){printf(f?"POSSIBLE\n":"IMPOSSIBLE\n");}

//void print(){}

//----------------------library------------------------//

//const int dx[4]={1,0,-1,0};
//const int dy[4]={0,1,0,-1};
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

const int NMAX = 200;
bool flag;

bool comp(int x,int y){
    return abs(0-x)<abs(0-y);
}

void f(int &n){
    if(n%2==0) n/=2;
    else n=n*3+1;
}

signed main(){
//    IOS;
    CIN(N);
    priority_queue<int> que;
    rep(i,N){
        int p;cin>>p;
        que.push(p);
    }
    int ans=que.top()/2;
    que.pop();
    while (!que.empty()){
        ans+=que.top();
        que.pop();
    }
    printf("%d\n",ans);
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication11 {
    class Program {
        static void Main(string[] args) {
            new Program().solve();
        }

        void solve() {
            while (true) {
                int num_budget = int.Parse(Console.ReadLine());
                if (num_budget == 0) {
                    return;
                }
                Budget[] input = new Budget[num_budget];
                for (int i = 0; i < num_budget; i++) {
                    input[i] = new Budget(Console.ReadLine());
                }
                int[] fee = new int[num_budget];
                for (int i = 0; i < num_budget; i++) {
                    fee[i] = classifyBudget(input[i]);
                }
                int sumfee = 0;
                for (int i = 0; i < num_budget; i++) {
                    sumfee += fee[i];
                }
                Console.WriteLine(sumfee);
            }
        }

        int classifyBudget(Budget b) {

            int[] upperSize = new int[]{60,80,100,120,140,160};
            int[] upperWeight = new int[]{2,5,10,15,20,25};
            int[] fee = new int[]{600,800,1000,1200,1400,1600};

            if ((b.getSize() > upperSize[4] || b.getWeight() > upperWeight[4])
                && (b.getSize() <= upperSize[5] && b.getWeight() <= upperWeight[5])) {
                return fee[5];
            } else if ((b.getSize() > upperSize[3] || b.getWeight() > upperWeight[3])
                && (b.getSize() <= upperSize[4] && b.getWeight() <= upperWeight[4])) {
                return fee[4];
            } else if ((b.getSize() > upperSize[2] || b.getWeight() > upperWeight[2])
                && (b.getSize() <= upperSize[3] && b.getWeight() <= upperWeight[3])) {
                return fee[3];
            } else if ((b.getSize() > upperSize[1] || b.getWeight() > upperWeight[1])
                && (b.getSize() <= upperSize[2] && b.getWeight() <= upperWeight[2])) {
                    return fee[2];
            } else if ((b.getSize() > upperSize[0] || b.getWeight() > upperWeight[0])
                && (b.getSize() <= upperSize[1] && b.getWeight() <= upperWeight[1])) {
                    return fee[1];
            } else if (b.getSize() <= upperSize[0] && b.getWeight() <= upperWeight[0]) {
                return fee[0];
            }
            return 0;
        }
    }

    class Budget {
        int depth;
        int width;
        int height;
        int weight;

        public Budget(string budList) {
            depth = int.Parse(budList.Split(' ')[0]);
            width = int.Parse(budList.Split(' ')[1]);
            height = int.Parse(budList.Split(' ')[2]);
            weight = int.Parse(budList.Split(' ')[3]);
        }

        public int getSize() {
            return depth+width+height;
        }

        public int getWeight() {
            return weight;
        }
    }
}

Measured memory_bytes: 10424
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

int d[20], v[105][105], ord[105], D[1LL<<17];
signed main(void)
{
  int n, m, k;
  cin >> n >> m >> k;
  REP(i, m) cin >> d[i], d[i]--;
  REP(i, n) REP(j, k) {
    cin >> v[i][j], v[i][j]--;
  }

  REP(i, n) ord[i] = INF;
  REP(i, m) ord[d[i]] = i;

  REP(i, 1LL<<m) D[i] = INF;
  D[(1LL<<m)-1] = 0;
  queue<int> que;
  que.push((1LL<<m)-1);
  while(que.size()) {
    int t = que.front(); que.pop();
    // cout << t << endl;
    // ???i??§????§?
    REP(i, k) {
      int nxt = 0;
      // j?????????1???????¬????????§???????bit????????????
      REP(j, m) {
        if(t & (1<<j)) {
          // ????§??????????????????¨?±?
          if(ord[v[d[j]][i]] == INF) continue;
          nxt |= (1LL << ord[v[d[j]][i]]);
        }
      }
      // cout << "i:" << i << " " << nxt << " " << D[nxt] << " " << D[t] << endl;
      if(D[nxt] > D[t] + 1) {
        D[nxt] = D[t] + 1;
        que.push(nxt);
        if(nxt == 0) {
          cout << D[0] << endl;
          return 0;
        }
      }
    }
  }

  assert(false);
  return 0;
}

Measured memory_bytes: 3572
#include <stdio.h>
int square(a,b){
  return (a*b);
}
int length(a,b){
  return (2*(a+b));
}
int main()
{
  int x,y;
  scanf("%d %d",&x,&y);
  int s,l;
  s = square(x,y);
  l = length(x,y);
  printf("%d %d\n",s,l);
  return 0;
}



Measured memory_bytes: 2116
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>
#include <deque>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


map<ll, ll> mp;
string s;
ll n, p, now;

ll powmod(ll a, ll b) {
	a %= p;
	ll res = 1;
	while (b > 0) {
		if (b % 2 == 1)res = res * a % p;
		a = a * a % p;
		b /= 2;
	}
	return res;
}
int main() {
	mp[0] = 1;
	cin >> n >> p;
	cin >> s;
	ll ans = 0;
	if (p == 2) {
		REP(i, n)if ((s[i] - '0') % 2 == 0)ans += i + 1;
		cout << ans << endl;
	}
	else if (p == 5) {
		REP(i, n)if ((s[i] - '0') % 5 == 0)ans += i + 1;
		cout << ans << endl;
	}
	else {
		REPR(i, n - 1) {
			now = (powmod(10, n - i - 1) * (s[i] - '0') + now) % p;
			mp[now]++;
		}

		for (auto& i : mp)
		{
			ans += i.second * (i.second - 1) / 2;
		}
		cout << ans << endl;
	}
}



Measured memory_bytes: 1028
N = gets.to_i
a = gets.split.map(&:to_i)
sum = 0
s = [0].concat(a.map { |x| sum += x })
h = Hash.new(0)
s.each do |i|
  h[i] += 1
end
ans = 0
h.each do |i, cnt|
  next if cnt < 2
  ans += (cnt * (cnt - 1)) / 2
end

p ans

Measured memory_bytes: 31492
#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int n, k;

bool check(vector<int>& w, int m)
{
	int cnt = 0;
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		sum += w[i];
		while (sum > m)
		{
			sum = w[i];
			++cnt;
			if (cnt == k)
			{
				return(false);
			}
		}
	}
	return(true);
}

void solve()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> k;
	vector<int> w(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> w[i];
	}
	int l = 0;
	int r = INT_MAX;
	while (l < r)
	{
		int mid = (l + r) / 2;		
		if (check(w, mid))
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << l << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1536
#include<cstdio>
#include<vector>
#include<algorithm>


using namespace std;
using vi=vector<int>;


int main(void)
{
	int n, m;

	while(scanf("%d%d", &n, &m)==2)
	{
		vi a(n+1);
		vi x(m), y(m);
		vi count(n+1);
		vi cover(n+1);

		for(int i=1;i<=n;i++)
		{
			scanf("%d", &a[i]);
			cover[max(0, a[i]-count[a[i]])]++;
			count[a[i]]++;
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(!cover[i]) ans++;
		}
		for(int i=0;i<m;i++)
		{
			scanf("%d%d", &x[i], &y[i]);
			int v=a[x[i]];
			a[x[i]]=y[i];
			count[v]--;
			if(v-count[v]>0)
			{
				cover[v-count[v]]--;
				if(cover[v-count[v]]==0) ans++;
			}
			if(y[i]-count[y[i]]>0)
			{
				if(cover[y[i]-count[y[i]]]==0) ans--;
				cover[y[i]-count[y[i]]]++;
			}
			count[y[i]]++;

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

	return 0;
}


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

using i64 = int64_t;

int main(){
    int n;
    cin >> n;
    vector<i64> v;
    int maxi = 0, idx = 0;
    for(int i=0;i<n;++i){
        i64 a;
        cin >> a;
        v.push_back(a);
        if(abs(a) > maxi){
            maxi = abs(a);
            idx = i;
        }
    }
    vector<pair<int, int>> ans;
    if(v[idx] > 0){
        ans.emplace_back(idx+1, n);
        ans.emplace_back(idx+1, n);
        for(int i=2;i<n;++i){
            ans.emplace_back(n, i);
            ans.emplace_back(n, n);
        }
    }else if(v[idx] < 0){
        ans.emplace_back(idx+1, 1);
        ans.emplace_back(idx+1, 1);
        for(int i=n-1;i>0;--i){
            ans.emplace_back(1, i);
            ans.emplace_back(1, 1);
        }
    }else{
        cout << 0 << endl;
        return 0;
    }

    cout << ans.size() << endl;
    for(auto e: ans){
        cout << e.first << " " << e.second << endl;
    }


    return 0;
}

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

#include <set>
using namespace std;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

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

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

typedef long long ll;

int main() {
    int N, K;
    set<int> snuke;
    cin >> N >> K;
    rep(i, K) {
        int d;
        cin >> d;
        rep(j, d) {
            int a;
            cin >> a;
            snuke.insert(a);
        }
    }
    cout << N - snuke.size() << endl;
    return 0;
}


Measured memory_bytes: 3608
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String args[]) {
		FastScanner scanner = new FastScanner();
		int n=scanner.nextInt();
		int[] w=new int[n];
		int sum=0;
		for(int i=0;i<n;i++){
			w[i]=scanner.nextInt();
			sum+=w[i];
		}
		//Arrays.sort(w);
		int min=10000000;
		for(int i=0;i<n;i++){
			int tmp=0;
			for(int j=0;j<i;j++){
				tmp+=w[j];
			}
			min=Math.min(min, Math.abs(tmp-(sum-tmp)));
		}
		System.out.println(min);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 22868
N,A,B,K = map(int,input().split())
MOD = 998244353

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# 組み合わせを全部メモ化
C = [0]*(N+1)
C[0] = C[N] = 1
for k in range(1,N//2+1):
    v = C[k-1]*(N-k+1)*modinv(k,MOD)
    v %= MOD
    C[k] = C[N-k] = v

Ans = 0
A,B = max(A,B),min(A,B)
for ai in range(N+1):
    bi = (K-A*ai)//B
    if 0<= bi <=N and A*ai + B*bi == K:
        Ans += C[ai] * C[bi]
        Ans %= MOD

print(Ans)

Measured memory_bytes: 10128
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0; i < (n); i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) (a).begin(), (a).end()
#define AALL(a, n) (a), a + n
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define MOD(x) ((x) % (1e9 + 7))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

const double EPS = 1e-10;
const double PI = acos(-1.0);

inline int toInt(string s) {
	int v;
	istringstream sin(s);
	sin >> v;
	return v;
}

int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", n / 2 - (n % 2 ? 0 : 1));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }



int main() {
	int n;
	scanf("%d", &n);
	map<int,int> cnt;
	while(n--) {
		int x;
		scanf("%d", &x);
		++cnt[x];
	}
	vector<int> v;
	for(pair<int,int> p : cnt) {
		if(p.second >= 2) {
			v.push_back(p.first);
		}
		if(p.second >= 4) {
			v.push_back(p.first);
		}
	}
	
	if((int) v.size() < 2) {
		puts("0");
		return 0;
	}
	long long x = v.back() * (long long) v.end()[-2];
	printf("%lld\n", x);
}


Measured memory_bytes: 8312
#include <iostream>
using namespace std;
 
int main() {
	int N;
    int H[100010];
    cin >> N;
   	for (int i = 0; i < N; i++) cin >> H[i];
	
  	int flg = 0;
  	string ans = "Yes";
   	for (int i = N-1; i>0; i--) {
    	if (H[i-1] - H[i] == 1) {
          H[i-1]--;
        } else if (H[i-1] - H[i] > 1) {
          ans = "No";
          break;
        }
    }  
	cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}

int main(){
    ll n,i,j,t,x,y,ma=0,mi=1e17;
    cin>>x>>y;
    int cnt=0;
    while(x){
        x/=y;
        cnt++;
    }
    cout<<cnt;
}
/*
7
140 1
120 2
100 3
120
100
-1
100
*/


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

int main() {
  string S;
  cin >> S;
  char a = S.at(5);
  char b = S.at(6);
  if (a == '1' || b == '5' || b == '6' || b == '7' || b == '8' || b == '9'
     || b == '0')
    cout << "TBD" << endl;
  else
    cout << "Heisei" << endl;
  
}


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

int main(){
    int n;
    double ans = 0, a;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a;
        ans += 1.0 / a;
    }
    ans = 1.0 / ans;
    cout << setprecision(16) << ans << endl;
   return 0;
}

Measured memory_bytes: 3780
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
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; }

void solve(long long N, long long K, std::vector<long long> h){
    vll dp(N, INF);
    dp[0] = 0;
    for(ll i = 0; i < N; i++){
        for(ll j = i+1; j < min(N, i+K+1); j++){
            ll tmp = dp[i] + abs(h[i] - h[j]);
            chmin(dp[j], tmp );
        }
    }
    cout<< dp[N-1]<<endl;
}

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


Measured memory_bytes: 1792
import numpy as np

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

X = []
X = np.vstack([input().split() for i in range(N)])

count = 0

for i in range(N - 1):
  for j in range(N - (i + 1)):
    r = 0
    for k in range(D):
      r += (int(X[i, k]) - int(X[i + (j + 1), k])) ** 2
  
    if np.sqrt(r).is_integer():
      count += 1
    
print(count)

Measured memory_bytes: 12468
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char s[100001];
int main()
{
    int a,b;
    scanf("%d%d\n",&a,&b);
    for(int i=1;i<=a+b+1;i++)s[i]=getchar();
    for(int i=1;i<=a+b+1;i++)
        if(((s[i]<48||s[i]>58)&&i!=a+1)||(i==a+1&&s[i]!='-'))
        {
            printf("No\n");
            return 0;
        }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 256
from numpy import cumsum
N = int(input())
A1 = [0] + [int(i) for i in input().split()]
A2 = [0] + [int(i) for i in input().split()]
cum_A1 = cumsum(A1)
cum_A2 = cumsum(A2)
ans = 0
for i in range(N):
    ans = max(ans, cum_A1[i + 1] + (cum_A2[-1] - cum_A2[i]))
print(ans)


Measured memory_bytes: 12432
<?php
fscanf(STDIN, "%d", $N);
$H = explode(" ", trim(fgets(STDIN)));
#var_dump($H);
$ans = 0;
$maximum = 0;
foreach($H as $value){
    if ($value >= $maximum){
        $maximum = $value;
        $ans += 1;
    }
}
echo $ans;

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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int x, y, z;
  cin >> x >> y >> z;

  int res = x / (y + z);
  cout << ((y+z) * res + z <= x ? res : res-1) << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <cstdlib> 
#include <math.h>
#define gap cout<<endl;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define INF 1<<30
#define present(c,x) ((c).find(x) != (c).end())

int main(){

	string s,t,u;
	int a,b;
	cin>>s>>t;
	cin>>a>>b;
	cin>>u;
	if(u==t) b--;
	else a--;
	cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for i in range(N):
    A = list(map(int, input().split()))
    if sum([a*b for a, b in zip(A, B)]) + C > 0:
        ans += 1
print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,b[200009],a,ans;
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a;
		b[a]++;
	}
	int m=n-k;
	sort(b,b+n+1);
	for(int i=0;i<=m;i++){
		ans=ans+b[i];
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1152
s = input()
t = input()

s = s[::-1]
t = t[::-1]

for i in range(len(s) - len(t) + 1):
    for j, v in enumerate(t):
        if s[j+i] == v or s[j+i] == "?":
            continue
        else:
            break
    else:
        l = len(t)
        s = s[0:i] + t + s[i+l:]
        break
else:
    print("UNRESTORABLE")
    exit()

s = s.replace("?", "a")

print(s[::-1])

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

int main(){
	string s;
	cin>>s;
	ll k;
	cin>>k;
	vector<int> v;
	for(int i=0;i<s.size();i++){
		int cnt=1;
		while(i+1<s.size()&&s[i]==s[i+1]){
			i++;
			cnt++;
		}
		v.push_back(cnt);
	}
	int n=v.size();
	if(n==1){
		cout<<(k*(ll)s.size())/2<<endl;
		return 0;
	}
	ll ans=0;
	for(int i=0;i<n;i++){
		if(i==0||i==n-1){
			ans+=(v[i]/2);
		}
		else{
			ans+=k*(v[i]/2);
		}
	}
	if(s[0]==s.back()){
		ans+=(k-1)*((v[0]+v[n-1])/2);
	}
	else{
		ans+=(k-1)*(v[0]/2)+(k-1)*(v[n-1]/2);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

using namespace std;
using ll = long long;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

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

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

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

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

    int X;
    cin >> X;

    ll sum = 0;
    int i = 1;
    while (X > sum) {
        sum += i;
        i++;
    }

    cout << i - 1 << endl;
    return 0;
}

Measured memory_bytes: 256
def C_CitySavers():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 0
    for x in range(N):
        if A[x] >= B[x]:
            ans += B[x]
        else:
            over = B[x] - A[x]
            if A[x+1] < over:
                over = A[x + 1]
            A[x+1] -= over
            ans += A[x] + over
    print(ans)
    
if __name__ == "__main__":
    C_CitySavers()

Measured memory_bytes: 18476
#include <iostream>
#include<vector>
#include<algorithm>
#define ll long long 
#define rep(n) for(int i=0;i<n;++i)
using namespace std;
int main(void){
    // Your code here!

int n, max1=-1,max2=-1;
cin>>n;
vector<int> vec(n+1), vec2(n);
rep(n){
    cin>>vec[i];
    if(vec[i]>max1){
        max2= max1;
        max1=vec[i];
    }else{
        if(vec[i]>max2){
            max2=vec[i];
        }
    }
}
rep(n){
    if(vec[i]!=max1){
        cout<<max1<<endl;
    }
    else
    cout<<max2<<endl;
}
}


Measured memory_bytes: 4404
import sys

n, m = map(int, input().split())
s = input()
to_a = [set() for _ in range(n)]
to_b = [set() for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	if s[a-1] == "A":
		if s[b-1] == "A":
			to_a[a-1].add(b-1)
			to_a[b-1].add(a-1)
		else:
			to_b[a-1].add(b-1)
			to_a[b-1].add(a-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			to_b[a-1].add(b-1)
			to_b[b-1].add(a-1)
		else:
			to_a[a-1].add(b-1)
			to_b[b-1].add(a-1)

not_valid = set([i for i in range(n) if len(to_a[i]) * len(to_b[i]) == 0])
cnt = 0
#print(not_valid)

while not_valid:
	node = not_valid.pop()
	#print(node)
	cnt += 1

	for next_node in to_a[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	for next_node in to_b[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	#print(not_valid)

if cnt == n:
	print("No")
else:
	print("Yes")

Measured memory_bytes: 122960
#include <bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define inf 0x3f3f3f3f
#define db double
using namespace std;
const int maxn=1e7+10;
int d[2][6], cnt1=0,cnt2=0;
ll a[maxn];
int main() {
	a[0]=0;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=a[i-1]+i;
	ll ans=0;
	for(int i=1;i<=n;i++){
		int t=n/i;
		ans+=(ll)i*a[t];
	}	
	cout<<ans<<endl;
}

Measured memory_bytes: 81772
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll L[100];


int main() {
    int N;
    cin >> N;
    L[0] = 2LL, L[1] = 1LL;
    for (int i = 2; i < N+1; i++) {
        L[i] = L[i - 1] + L[i - 2];
    }
    printf("%ld\n", L[N]);
}

Measured memory_bytes: 256
while True:
    h, w = [int(arg) for arg in input().split()]
    if h == 0 and w == 0:
        break
    for i in range(h):
        if i % 2 == 0:
            print('#.'*int(w/2) if w%2==0 else '#.'*int(w/2)+'#')
        else:
            print('.#'*int(w/2) if w%2==0 else '.#'*int(w/2)+'.')
    print()


Measured memory_bytes: 5624
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;

int main(void) {

    int X; cin>>X;

    int ans = 1;
    for (int i = 2; i*i <= X; ++i) {
        for (int j = i*i; j <= X; j*=i) {
            ans = max(ans, j);
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define sf scanf
#define pf printf
#define pb push_back
#define llu unsigned long long
#define U unsigned int
#define SIZE 1000002
#define pie 3.14159265358979323
#define minuss 1e-6
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int main()
{
    ll n;
    char s[100];
    cin>>n;
    cin>>s;
    if(n>=3200)
        cout<<s<<endl;
    else
        cout<<"red"<<endl;
}


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

using namespace std;

int main() {
	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int h,w;
	char x;
	cin>>h>>w;
	for(int i=0;i<w+2;i++)
	    cout<<"#";
	  cout<<"\n";
	for(int i=1;i<=h;i++)
	{   cout<<"#";
	    for(int j=1;j<=w;j++)
	        {   cin>>x;
	            cout<<x;
	        }
	    cout<<"#\n";
	}
	
	for(int i=0;i<w+2;i++)
	    cout<<"#";
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define endl            "\n"
#define forn(i,n)       for(int i=0; i<n; i++)
#define forit(it, m)    for(decltype(m)::iterator it = m.begin(); it!=m.end(); ++it)
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void zeus()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
set<int> nums;

void primeFactors(int n)
{
    // Print the number of 2s that divide n
    while (n % 2 == 0)
    {
        nums.insert(2);
        n = n / 2;
    }

    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n % i == 0)
        {
            nums.insert(i);
            n = n / i;
        }
    }

    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        nums.insert(n);
}

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

    primeFactors(n);

    int ans = 0;
    for (auto i = nums.begin(); i != nums.end(); i++) {

        int x = *i;
        double count = 1;
        while (n % (x * (*i)) == 0) {
            x *= (*i);
            count++;
        }
        //cout << *i << " " << count << endl;
        ans += (int)((pow(1 + 8 * count, 0.5) - 1) / 2);

    }




    cout << ans << endl;




}





Measured memory_bytes: 4064
using System;
using System.Linq;
using static System.Math;
using System.Collections.Generic;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var nk = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var h = Console.ReadLine().Split().Select(int.Parse).OrderByDescending(x => x).ToArray();

            var ans = h.Count(x => x >= nk[1]);

            Console.WriteLine(ans);


        }
    }
}


Measured memory_bytes: 21344
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main(){
    int n; cin >> n;
    string d[7]={"fri", "sat", "sun", "mon", "tue", "wed", "thu"};
    cout << d[(n-1)%7] << endl;
    return 0;
}


Measured memory_bytes: 3196
#include<iostream>
using namespace std;
int main()
{
	int n,q,t,cnt=0;
	int S[10000];
	cin>>n;
	for(int i=0; i<n; ++i){
	  cin>>S[i];
	}
	cin>>q;
	for(int i=0; i<q; ++i){
	  cin>>t; 
		for(int i=0; i<n; ++i){
			if(S[i]==t){
				cnt++;
				break;
			}
		}
	}
	cout<<cnt;
	cout<<'\n';
	return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
#define REP(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;

constexpr ll MOD = 1000000007;
constexpr int MAX = 10010;

string s;
int d;
ll dp[10010][2][101];

int main() {
	cin >> s >> d;
	dp[0][0][0] = 1;
	int n = s.size();
	REP(i, n) {
		int now = s[i] - '0';

		// from j = 0
		REP(j, d + 1) {
			REP(k, now) (dp[i + 1][1][(j + k) % d] += dp[i][0][j]) %= MOD;
			(dp[i + 1][0][(j + now) % d] += dp[i][0][j]) %= MOD;
		}

		// from j = 1
		REP(j, d + 1) 
			REP(k, 10) (dp[i + 1][1][(j + k) % d] += dp[i][1][j]) %= MOD;
	}
	cout << ((dp[n][0][0] + dp[n][1][0]) % MOD + MOD - 1) % MOD;
	return 0;
}

Measured memory_bytes: 16000
n, k = map(int, input().split())

h = []
for i in range(n):
    h.append(int(input()))

h.sort()

min = 1000000000
for i in range(n-k+1):
    d = h[i+k-1]-h[i]
    if min >= d:
        min = d

print(min)


Measured memory_bytes: 7384
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>

using namespace std;

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

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

template<typename T>
ostream& operator << (ostream& os, const vector<T>& v) {
    for (auto& x : v) {
        os << x << " ";
    }
    os << "\n";
    return os;
}

const int64_t MOD = 1e9 + 7;

bool bad_mask(int mask, int x, int y, int z) {
    return ((mask & (1 << x)) > 0) &&
           ((mask & (1 << (x + y))) > 0) &&
           ((mask & (1 << (x + y + z))) > 0);
}

int64_t mypow(int64_t x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x % MOD;
    int64_t y = mypow(x, p / 2);
    y *= y;
    y %= MOD;
    if (p % 2 == 0) return y;
    else return (y * x) % MOD;
}

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

#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int N, X, Y, Z;
    cin >> N >> X >> Y >> Z;

    vector<vector<int64_t>> dp(N + 1, vector<int64_t>(1 << (X + Y + Z), 0));
    dp[0][1] = 1;
    for (int n = 0; n < N; ++n) {
        for (int mask = 0; mask < (1 << (X + Y + Z)); ++mask) {
            for (int t = 1; t <= 10; ++t) {
                int new_mask = mask << t;
                new_mask |= 1;
                new_mask &= (1 << (X + Y + Z)) - 1;
                if (X < t || !bad_mask(mask, X - t, Y, Z)) {
                    dp[n + 1][new_mask] += dp[n][mask];
                    dp[n + 1][new_mask] %= MOD;
                }
            }
        }
    }
    // cout << dp << endl;

    // int hmask = 1 + (1 << 5) + (1 << 12) + (1 << (X + Y + Z));
    // cout << hmask << " " << bad_mask(hmask, X, Y, Z) << " " << dp[N][hmask] << endl;


    int64_t ans = mypow(10, N);
    for (int mask = 0; mask < (1 << (X + Y + Z)); ++mask) {
        ans += MOD - dp[N][mask];
        ans %= MOD;
    }
    cout << ans;
}


Measured memory_bytes: 46476
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<algorithm>
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
void over(){puts("-1"),std::exit(0);}
const int N=500007;
std::vector<int>e[N];
int n,m,ans,eu,ev,a[N],fa[N],dep[N],f[N];
void dfs(int u)
{
    dep[u]=dep[fa[u]]+1,f[u]=dep[u]&1? 1:-1;
    for(int v:e[u]) if(v^fa[u]) dep[v]? (eu=u,ev=v):(fa[v]=u,dfs(v),f[u]+=f[v]);
}
void work1()
{
    if(f[1]) over();
    for(int i=1;i<=n;++i) ans+=abs(f[i]);
    printf("%d",ans);
}
void work2()
{
    if(f[1]&1) over();
    int x=-f[1]/2;
    for(;eu;eu=fa[eu]) f[eu]+=x;
    for(;ev;ev=fa[ev]) f[ev]+=x;
    for(int i=1;i<=n;++i) ans+=abs(f[i]);
    printf("%d",ans+abs(x));
}
void work3()
{
    if(f[1]) over();
    int c=0,x;
    for(;ev^eu;ev=fa[ev]) a[++c]=f[ev],dep[ev]=0;
    std::sort(a+1,a+c+1),x=a[(c+1)/2];
    for(int i=1;i<=n;++i) if(dep[i]) ans+=abs(f[i]);
    for(int i=1;i<=c;++i) ans+=abs(a[i]-x);
    printf("%d",ans+abs(x));
}
int main()
{
    n=read(),m=read();
    for(int i=1,u,v;i<=m;++i) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs(1);
    m==n-1? work1():(abs(dep[eu]-dep[ev])&1? work3():work2());
}

Measured memory_bytes: 26496
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if i == 0:
                U[i][j] = 1 if s[i][j] != "#" else 0
                D[-i-1][j] = 1 if s[-i-1][j] != "#" else 0
            else:
                U[i][j] = 1 + U[i-1][j] if s[i][j] != "#" else 0
                D[-i-1][j] = 1 + D[-i][j] if s[-i-1][j] != "#" else 0
            if j == 0:
                L[i][j] = 1 if s[i][j] != "#" else 0
                R[i][-j-1] = 1 if s[i][-j-1] != "#" else 0
            else:
                L[i][j] = 1 + L[i][j-1] if s[i][j] != "#" else 0
                R[i][-j-1] = 1 + R[i][-j] if s[i][-j-1] != "#" else 0
    m_c = 0
    for i in range(h):
        for j in range(w):
            m_c = max(m_c, U[i][j] + D[i][j] + R[i][j] + L[i][j] - 3)
    print(m_c)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 308232
import sys
readline = sys.stdin.readline

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
  
  ans += pat
  ans %= DIV

print(ans)


Measured memory_bytes: 226012