akhauriyash/Code-Regression huggingface dataset:
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
while(true){
   var nm=arr.shift().split(" ");
   if(nm.join(" ")=="0 0")break;
   var n=nm[0];
   var m=nm[1];
   var M=[];
   for(var i=0;i<m;i++)M.push(arr.shift()-0);
   var N=[];
   for(var i=0;i<n;i++)N.push(arr.shift()-0);
   var dp=[];
   for(var i=0;i<=n;i++){
      dp[i]=[];
      for(var j=0;j<=255;j++){
         dp[i][j]=-1;
      }
   }
   dp[0][128]=0;
   for(var i=1;i<=n;i++){
      for(var j=0;j<=255;j++){
         for(var k=0;k<m;k++){
            var jm=j+M[k];
            if(jm<0)jm=0;
            if(jm>255)jm=255;
            if(dp[i-1][j]!=-1){
               if(dp[i][jm]!=-1)dp[i][jm]=Math.min(dp[i][jm],dp[i-1][j]+Math.pow(N[i-1]-jm,2));
               else dp[i][jm]=dp[i-1][j]+Math.pow(N[i-1]-jm,2);
            }
         }
      }
   }
   var min=Infinity;
   dp[n].forEach(function(v){
      if(v!=-1)min=Math.min(min,v);
   });
   console.log(min);
}

Measured memory_bytes: 223020
#include<bits/stdc++.h>
#define lld         long long int
#define llf         long double
#define pb          push_back
#define mp          make_pair
#define IN          insert
#define loopN(n)    for(lld i=0;i<n;i++)
#define loop(p,n)   for(lld i=p;i<=n;i++)
#define rloop(p,n)  for(lld i=n;i>=p;i--)
#define loop2(p,n)  for(lld j=p;j<=n;j++)
#define all(v)      v.begin(),v.end()
#define F1          first
#define F2          second
#define INF         2e18
#define FILE        freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define PI          2*acos(0.0)
#define ISO         ios::sync_with_stdio(false);cin.tie(0)
#define mem(a,b)    memset(a,b,sizeof(a))
#define case(z)     cout<<"Case "<<z<<": ";
using namespace std;
const lld mod=1e9+7;

lld on(lld m,lld p){return m | (1<<p);}
bool ison(lld m,lld p){return (bool)(m & (1<<p));}
lld flip(lld m,lld p){return m ^ (1<<p);}
lld allon(lld p){return (1<<p)-1;}
//______________________________________________________________________________________

lld n;
lld dp[100005][3];
lld a[100005][3];

lld fun(lld p, lld k)
{
    if(p>=n)return 0;
    if(dp[p][k]!=-1)
    {
        return dp[p][k];
    }
    lld ans=-INF;
    if(p==0)
    {
        loopN(3)
        {
            ans=max(ans,a[p][i]+fun(p+1,i));
        }
        return ans;
    }
    else
    {
        loopN(3)
        {
            if(i!=k)
            {
                ans=max(ans,a[p][i]+fun(p+1,i));
            }

        }

    }
    return dp[p][k]=ans;



}


int main()
{
    ISO;

    //lld t;cin>>t;while(t--)
    mem(dp,-1);
    cin>>n;
    loopN(n)loop2(0,2)cin>>a[i][j];
    cout<<fun(0,0)<<endl;


    return 0;
}




Measured memory_bytes: 16104
#include <stdio.h>
int main()
{
	int h, min, s, i;
	scanf("%d", &s);
	h = s/3600;
	i= s%3600;
	min = i / 60;
	s= i % 60;
	printf("%d:%d:%d\n", h,min,s);
	return 0;
}


Measured memory_bytes: 2112
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
	int A, B;
	cin >> A; cin >> B;
	int ans=0;
	ans=(max(max(2*A-1, 2*B-1),A+B));
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

    int n;
    cin >> n;
    const int mx = 100100;
    long long sum = 0;
    vector<int> count(mx, 0);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        sum += x;
        count[x]++;
    }

    int q;
    cin >> q;
    while (q--) {
        int b, c;
        cin >> b >> c;
        sum -= (ll)count[b] * b;
        sum += (ll)count[b] * c;
        count[c] += count[b];
        count[b] = 0;
        cout << sum << "\n";
    }

    
    return 0;
}

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

int main() {
 int n,m;
 cin>>n>>m;
 vector<int> data(n);
    rep(i,m) {
        int a;
        cin >> a;
        data.at(a) = 1;
    }
    
    vector<long long> dp(n+2);
    int mod = 1000000007;
    dp.at(n) = 1;
    for(int i = n -1;i>=0;i--) {
     if(data.at(i) == 1) {
      dp.at(i) = 0;
     continue;
     }
        dp.at(i) = (dp.at(i+1) + dp.at(i+2)) % mod;
    }
    cout << dp.at(0);

}


Measured memory_bytes: 4536
# coding: utf-8
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 奇数番目の最頻値と偶数番目の最頻値が同じ時に注意
N = ir()
V = lr()
odd = V[::2]
even = V[1::2]
cnt_odd = Counter(odd)
cnt_even = Counter(even)
cnt_odd_most = cnt_odd.most_common()
cnt_even_most = cnt_even.most_common()
if cnt_odd_most[0][0] == cnt_even_most[0][0]:
    answer = N
    if len(cnt_odd_most) > 1:
        temp = N - cnt_odd_most[1][1] - cnt_even_most[0][1]
        answer = min(answer, temp)
    if len(cnt_even_most) > 1:
        temp = N - cnt_odd_most[0][1] - cnt_even_most[1][1]
        answer = min(answer, temp)
    if answer == N:
        answer = N // 2
else:
    answer = N - cnt_odd_most[0][1] - cnt_even_most[0][1]

print(answer)


Measured memory_bytes: 21944
N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = 1e+18
for i in range(1<<N):
  if bin(i).count('1') != K:
    continue
  cost = 0
  cur_height = 0
  for j in range(N):
    if i & (1<<j):
      cost += max(0, cur_height-a[j]+1)
      cur_height = max(a[j], cur_height+1)
    else:
      cur_height = max(a[j], cur_height)
  ans = min(ans, cost)
print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		long n = sc.nextInt();
		lab: {
			for (int i = 1; i < 1000; i++) {
				long m = (long) Math.pow(i, 5);
				if (n < m) {
					for (int j = 0; j < 1000; j++) {
						if ((m - Math.pow(j, 5)) == n) {
							System.out.println(i + " " + j);
							break lab;
						}
					}
				} else {
					for (int j = 0; j > -1000; j--) {
						if ((m - Math.pow(j, 5)) == n) {
							System.out.println(i + " " + j);
							break lab;
						}
					}
				}
			}
		}
	}

	static class FastScanner {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public FastScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					return reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}

			return tokenizer.nextToken("\n");
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}
}

Measured memory_bytes: 36776
#include<bits/stdc++.h>
using namespace std;
#define fr(i,n)  for(int i = 0;i<n;++i)
#define fri(i,a,b) for(int i= a;i<=b;++i)
#define fro(i,a,b) for(int i= a;i>=b;--i)
#define debug(P) cout<<#P<<" = "<<P<<endl;
#define fi first
#define se second
#define pb(x)  push_back(x)
#define  mp(x,y) make_pair(x,y)
#define endl  "\n"
#define  ii  pair<int,int>
#define  int  long long
#define  maxm(a,b,c)  max(a,max(b,c))
int mod = 1e9+7;
int dp[410][410];
int pref[410],a[410];
signed main(){
	 int n;
	 cin>>n;
	 for(int i = 1;i<=n;++i){
	 	  cin>>a[i];
	 }
	 for(int i = 1;i<=n;++i){
	 	pref[i] = pref[i-1]+a[i];
	 }
	 for(int i = 1;i<=n;++i){
	 	  dp[i][i] = 0;
	 }
	for(int l = 2;l<=n;++l){
		  for(int i = 1;i<=(n-l+1);++i){
		  	  int j = i+l-1;
		  	  dp[i][j] = 1e15;
		  	  for(int k = i;k<=j-1;++k){
		  	  	int sum = pref[k]-pref[i-1];
		  	  	sum += pref[j]-pref[k];
		  	  	   dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum);
				}
		  }
	}
	cout<<dp[1][n];
}

Measured memory_bytes: 1536
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

int H,W,K;

bool inside(int a, int b){
	return 0<=a&&a<H&&0<=b&&b<W;
}

void mainmain(){
	cin>>H>>W>>K;
	vvint vv;
	initvv(vv,H,W);
	pii start;
	rep(i,H){
		rep(j,W){
			char t;
			cin>>t;
			vv[i][j] = t == '#';
			if(t=='S') start = pii(i, j);
		}
	}
	int ans = min(min(start.F, start.S), min(H-1-start.F, W-1-start.S));
	queue<pii> q;
	q.push(start);
	set<pii> se;
	rep(i,K){
		int qs = q.size();
		rep(_, qs){
			pii top = q.front();
			q.pop();
			int dd[] = {0,1,0,-1,0};
			rep(j,4){
				pii nn = top;
				nn.F += dd[j];
				nn.S += dd[j+1];
				if(!inside(nn.F, nn.S)) continue;
				if(se.find(nn) != se.end()) continue;
				if(vv[nn.F][nn.S]) continue;
				se.insert(nn);
				q.push(nn);
				int tmp = min(min(nn.F, nn.S), min(H-1-nn.F, W-1-nn.S));
				mins(ans, tmp);
			}
		}
	}
	cout << (ans+K-1)/K + 1 << endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 32256
s = list(input())

n = len(s)
ans = n

num_0 = 0
for i in range(0, n, 2):
  if s[i] == "1":
    num_0 += 1
if n % 2 == 1:
  for i in range(1, n - 1, 2):
    if s[i] == "0":
      num_0 += 1
else:
  for i in range(1, n, 2):
    if s[i] == "0":
      num_0 += 1

num_1 = 0
for i in range(0, n, 2):
  if s[i] == "0":
    num_1 += 1
if n % 2 == 1:
  for i in range(1, n - 1, 2):
    if s[i] == "1":
      num_1 += 1
else:
  for i in range(1, n, 2):
    if s[i] == "1":
      num_1 += 1

print(min(ans, num_0, num_1))

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

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

  string w;
  cin >> w;
  map<char, int> dic;
  for (auto i : w) {
    dic[i]++;
  }

  for (char i = 'a'; i <= 'z'; i++) {
    if (dic[i]%2 == 1) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
}

Measured memory_bytes: 256
object Main extends App {
  val nums = io.StdIn.readLine().split(" ").map(_.toInt)
  val m = nums(0)
  val f = nums(1)
  val b = nums(2)

  b match {
    case x if x <= m => println(0);
    case x if x > m + f => println("NA")
    case x  => println(x - m)
  }
}


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

using namespace std ;

long long a [ 200001 ] , c , d , e , f , g , h , k , l , m , n ;

int main ()
{
    int mn = 1e9 , b ;
    cin >> n ;
    for ( int i = 0 ; i < n ; ++ i ){
        cin >> c ;
        a [ i ] = c - i - 1 ;
    }
    sort ( a , a + n ) ;
    for ( int i = 0 ; i < n / 2 ; ++ i ){
        m += a [ n - i - 1 ] - a [ i ] ;
    }
    cout << m ;
    return 0 ;
}
    

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

int main() {
    cout.tie(0)->sync_with_stdio(0);
    int N; cin >> N;
    vector<int> heights(N);
    for (int i = 0; i < N; ++i) cin >> heights[i];
    int res = 0, j = 1;
    for (int i = 0; i+1 < N; ++i) {
        j = i+1;
        while(j < N && heights[j] <= heights[j-1]) ++j;
        res = max(res, j - i - 1);
    }
    cout << res << '\n';
}


Measured memory_bytes: 3788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
vector<ll> p;
ll a[200005],vis[200005];
int main(){
    ll n,k,t=0;
    cin>>n>>k;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    ll now=1;
    while(vis[now]<2){
        if(t==k){
            cout<<now<<endl;
            return 0;
        }
        vis[now]++;
        if(vis[now]==2) p.push_back(now);
        now=a[now];
        t++;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==1) k--;
    }
    k%=p.size();
    cout<<p[k]<<endl;
}

Measured memory_bytes: 7416
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int r,g;
	cin >> r >> g;
	cout << 2 *g -r << endl;
	return 0;
}


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

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  if (A==B){
    cout << C << endl;
  } 
  else if(B==C){
    cout << A << endl;
  }
  else{
    cout << B << endl;
  }
}


Measured memory_bytes: 256
module Main where

import Control.Applicative
import Numeric

main :: IO ()
main = do
  { [n] <- getInts
  ; call n
  }

call :: Int -> IO ()
call n = check_num n 1 1 

check_num :: Int -> Int -> Int -> IO ()
check_num n i x = if x `mod` 3 == 0
  then putStr (' ':show i) >> end_check_num n (succ i) x
  else include3 n i x
  
include3 :: Int -> Int -> Int -> IO ()
include3 n i x = if x `mod` 10 == 3
  then putStr (' ':show i) >> end_check_num n (succ i) x
  else if not (x' == 0) then include3 n i x'
       else end_check_num n (succ i) x'
  where
    x' = x `div` 10

end_check_num :: Int -> Int -> Int -> IO ()
end_check_num n i x = if i <= n then check_num n i i
  else putStrLn ""

--

getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""

done :: IO ()
done = return ()



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

using namespace std;

const int INF = 100000000;

int N, A, B, C;
vector<int> l;

int dfs(int cnt, int a, int b, int c);

int main(){
    cin >> N >> A >> B >> C;
    for(int i = 0; i < N; ++i){
        int temp;
        cin >> temp;
        l.push_back(temp);
    }
    cout << dfs(0, 0, 0, 0) << endl;
}

int dfs(int cnt, int a, int b, int c){
    if(cnt == N){
        if(min({a, b, c}) <= 0)     return INF;
        // 0個から1個にするとき、各変数で余分に10ptずつ消費しているので、その分を減算
        return abs(a - A) + abs(b - B) + abs(c - C) - 30;
    }
    int temp1, temp2, temp3, temp4;
    temp1 = dfs(cnt + 1, a, b, c);
    temp2 = dfs(cnt + 1, a + l[cnt], b, c) + 10;
    temp3 = dfs(cnt + 1, a, b + l[cnt], c) + 10;
    temp4 = dfs(cnt + 1, a, b, c + l[cnt]) + 10;
    return min({temp1, temp2, temp3, temp4});
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100005];
map<int, int> cnt;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;   
    for(int i=1;i<=n;i++){
        cin >> a[i];
        cnt[a[i]]++;
    }

    long long ans = 0;
    vector<int> v;
    for(auto its:cnt){
        if(its.second >= 2){
            v.emplace_back(its.first);
        }
        if(its.second >= 4){
            ans = max(ans, its.first*1ll*its.first);
        }
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    if(v.size() >= 2){
        ans = max(ans, v[0]*1ll*v[1]);
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 5376
import java.util.*;

class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String str=sc.next();
char[] c=new char[str.length()];
for(int i=0;i<str.length();i++){
c[i]=str.charAt(i);
}
for(int i=str.length()-1;i>=0;i--){
System.out.print(c[i]);
}
System.out.print("\n");
}
}

Measured memory_bytes: 17112
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long L, R, Min=2019, i, j;
  cin >> L >> R;
  R = min(R, L + 2019);
  for(i=L;i<=R;i++){
    for(j=i+1;j<=R;j++){
      long long i_=i%2019, j_=j%2019;
        Min = min(Min, (i_*j_)%2019);
    }
  }
  cout << Min << endl;
  return 0;
}

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

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

using namespace std;

typedef long long ll;

int a, b, c, k;

int x;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c >> k;
    while(b <= a)
    {
        b *= 2;
        x++;
    }
    while(c <= b)
    {
        c *= 2;
        x++;
    }
    if(x <= k)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <math.h>
#include <queue>

using namespace std;

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

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll mod_pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return mod_pow(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}


ll dp[310][310][310];

int main() {

    int N, M;
    cin >> N >> M;

    for(int i = 0; i < 310; i++){
        for(int j = 0; j < 310; j++){
            for(int k = 0; k < 310; k++){
                dp[i][j][k] = 0;
            }
        }
    }

    dp[0][N-1][1] = 1;

    for(int n = 0; n <= M-1; n++){
        for(int x = 0; x <= N-1; x++){
            for(int y = 1; y <= N; y++){
                dp[n+1][x][y] = add(dp[n+1][x][y], mul(N - x - y, dp[n][x][y]));
                dp[n+1][x][N-x] = add(dp[n+1][x][N-x], mul(y, dp[n][x][y]));
                dp[n+1][x-1][y] = add(dp[n+1][x-1][y], mul(x, dp[n][x][y]));
            }
        }
    }

    cout << dp[M][0][N] << endl;

    return 0;
}

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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

string s;

signed main()
{
    cin >> s;

    if (s[2] == s[3] && s[4] == s[5])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def euclid(a, b):
    if a > b:
        large = a
        small = b
    else:
        large = b
        small = a

    while small != 0:
        r = large % small
        large = small
        small = r

    return large


def solve(inputs):
    [A, B, C, D] = string_to_int(inputs[0])
    cd_gcd = euclid(C, D)
    cd_lcm = (C*D) // cd_gcd

    a_c = (A-1) // C
    a_d = (A-1) // D
    a_cd = (A-1) // cd_lcm

    b_c = B // C
    b_d = B // D
    b_cd = B // cd_lcm

    under_a = int((A-1) - a_c - a_d + a_cd)
    under_b = int(B - b_c - b_d + b_cd)

    return under_b - under_a


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 3064
n,m,x = map(int,input().split())
s = [list(map(int,input().split())) for i in range(n)]
s.insert(0,[0]*(m+1))

dp_list = ([0]*m)*(n+1)

ans = 10**7

def dp(i,cost,rikai):
    global ans
    frag = True
    tmp = [j for j in rikai]
    for j in range(m):
        if tmp[j] < x:
            frag = False
    if frag == True:#理解度を上回った
        ans = min(ans,cost)
        pass
    if i == n:#すべての本を買ったとき
        if frag == True:
            ans = min(ans,cost)
    else:
        dp(i+1,cost,tmp)#次の本を買わない
        for j in range(m):
            tmp[j] += s[i+1][j+1]
        dp(i+1,cost+s[i+1][0],tmp)#次の本をかう
            

dp(0,0,[0]*m)

if ans == 10**7:
    print(-1)
else:
    print(ans)



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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
const ll MOD = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);

int main(void)
{
    vector<ll> a(5);
    rep(i,5) cin>>a[i];
    ll ans=INF;
    vector<ll> p={0,1,2,3,4};
    do{
        ll tmp=0;
        rep(i,5){
            while(tmp%10!=0) tmp++;
            tmp+=a[p[i]];
        }
        ans=min(ans,tmp);
    }while(next_permutation(p.begin(),p.end()));
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) ((x).begin()), ((x).end())

#define READ(x) (cin >> (x))
#define WRITE_N(x) (cout << (x) << endl)
#define WRITE(x) (cout << (x))
#define WRITE_YESNO(x) (WRITE_N((x) ? "Yes" : "No"))

#define PRECISE_COUT std::cout << std::setprecision(15) << std::fixed

bool xor_logic(bool x, bool y) { return (x && y) || (!x && !y); }

using coord = pair<ll, ll>;

template <typename T1, typename T2>
bool pair_second_lt(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
  return p1.second > p2.second;
}

ll solve(vector<ll> &h, vector<ll> &w) {
  set<coord> c;
  unordered_map<ll, ll> h_map, w_map;
  for (size_t i = 0; i < h.size(); i++) {
    c.emplace(coord{h[i], w[i]});

    h_map[h[i]]++;
    w_map[w[i]]++;
  }

  vector<ll> h_max_keys, w_max_keys;
  ll h_max = 0, w_max = 0;
  for (auto &&p : h_map) {
    if (p.second > h_max) {
      h_max = p.second;
      h_max_keys = {p.first};
    } else if (p.second == h_max) {
      h_max_keys.push_back(p.first);
    }
  }
  for (auto &&p : w_map) {
    if (p.second > w_max) {
      w_max = p.second;
      w_max_keys = {p.first};
    } else if (p.second == w_max) {
      w_max_keys.push_back(p.first);
    }
  }

  bool is_all_coord_has_target = true;
  for (auto &&h_k : h_max_keys) {
    for (auto &&w_k : w_max_keys) {
      if (c.count(coord{h_k, w_k}) == 0) {
        is_all_coord_has_target = false;
        break;
      }
    }
  }

  return h_max + w_max - (is_all_coord_has_target ? 1 : 0);
}

int main() {
  // get values from input
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H, W, M;
  cin >> H >> W >> M;

  std::vector<ll> h(M, 0), w(M, 0);
  for (size_t i = 0; i < M; i++) {
    cin >> h[i] >> w[i];
  }

  // main procedure
  ll ans = solve(h, w);

  // output
  cout << ans << endl;

  return 0;
}

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

int main() {
  long N,K,A;
  cin >> N >> K ;
  A=0;
  for (long i=K; i<=N+1; i++){
    A+=((i*(N*2-i+1)-(i-1)*i)/2+1)%1000000007;
   // cout << A << endl;
  }
  cout << A%(1000000007)<< endl;
}


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

#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define ffor(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(i, n) ffor(i,0,n)
#define All(obj) (obj).begin(),(obj).end()
#define INF ((ll)1e9+7)
#define c(a) cout<<a<<"\n";
using namespace std;
const int N = 100005;



int main() {
	speed;
	cout << fixed << setprecision(6);
	/*start*/
	int n;
	cin >> n;
	vector<int>h(n);
	rep(i, n) {
		cin >> h[i];
	}
	vector<int> conte(n,0);
	int index = 0;
	rep(i, n - 1) {
		if (h[i] >= h[i + 1])conte[index]++;
		else index++;
	}
	sort(All(conte));
	int ans = conte.back();
	c(ans);
	ed;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000, boost::int128_type>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }
template<class T> inline bool isSosuu(const T& n) { if (n == T(1)) { return false; } for (T i = 2; i*i <= n; ++i) { if (n % i == 0) { return false; } } return true; }
template<class T> vector<vector<T>> split (const vector<T>& S, T delim) { vector<vector<T>> ret{}; vector<T> buff{}; for (auto c : S) { if (c == delim) { if (!buff.empty()) ret.push_back(buff); buff.clear(); } else { buff.push_back(c); } } if (!buff.empty()) ret.push_back(buff); return ret; }
template<class T> inline void printYesNo(const T& t) { cout << (t ? "Yes" : "No") << CRLF; }
template<class T = int64_t> T modpow(T N, T P, T M) { T ret{1}; N %= M; while (P) { if (P & 0x01) { ret *= N; ret %= M; } P >>= 1; N *= N; N %= M; } return ret; }

/** code for assert debug begin */
int gErr = 0;
#define ASSERT(p) if(!(p)){ gErr = 1; }else{ ; }
/** code for assert debug end */

struct Tmp
{
public:
  int N;
  Tmp(int N)
  : N(N)
  {}
};

void solve(void)
{
  int N; cin >> N;
  vector<ll> A(N);
  for (auto& a : A) { cin >> a; }
  std::sort(A.begin(), A.end());
  vector<ll> B(N);
  B[0] = 0;
  for (int i = 1; i < N; ++i) {
    B[i] = B[i-1] + A[i-1];
  }

  int res = 0;
  for (int i = 1; i < N; ++i) {
    if (A[i] > B[i]*2) {
      chmax(res, i);
    }
  }
  auto ans = N-res;
  cout << ans << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);
#define endl "\n"
#define MAXN 100123
#define ll long long
#define INF INT_MAX
#define FORE(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,n) FORE(i,0,n)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define ps(v) push_back(v)
#define ms(v,x) memset(v,x,sizeof(v)) 

using namespace std;

int n,soma,v,m;

int main(){_
    cin >> n >> m;
    FOR(i,m){
        cin >> v;
        soma+=v;
    }

    cout <<(soma<=n ? n-soma:-1) << endl;
    return 0;
}

Measured memory_bytes: 3640
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    A,B,N=mi()

    x = min(B-1,N)
    f = (A*x)//B - A*(x//B)
    
    print(f)

if __name__ == "__main__":
    main()

Measured memory_bytes: 61840
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int r; cin>>r;
    OUT(r*r);
}


Measured memory_bytes: 256
//C - Iroha's Obsession: 
//Assunto: 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    vector<bool> dislike(10, false);
    vector<int> use;
    int n, k, x, sz;
    string ans, aux, primeiro;
    bool igual, flag;
    
    cin >> n >> k;
    while(k--) {
        cin >> x;
        dislike[x] = true;
    }
    loop(i, 0, 10) if(!dislike[i]) use.pb(i);
    
    aux = to_string(n);
    sz = aux.size();
        //cout << ans << '\n';
    flag = false; igual = true; ans = "";
    loop(i, 0, sz) {
        if(igual) {
            loop(j, 0, use.size()) {
                if(use[j] >= (aux[i] - '0')) {
                    ans += use[j] + '0';
                    if(use[j] > (aux[i] - '0')) igual = false;
                    break;
                } else if(j == use.size()-1) flag = true;
            }
        } 
        else ans += use[0] + '0';
    }
    
    if(flag) {
        ans = "";
        if(use[0] != 0) ans += use[0] + '0';
        else ans += use[1] + '0';
        while(sz--) ans += use[0] + '0';
    }
    cout << ans << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int a[5];
    cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
    int b[5];
    for(int i=0;i<5;i++){
        if(a[i]%10!=0){
            b[i]=a[i]+10-a[i]%10;
        }
        else b[i]=a[i];
    }
    int sum=b[0]+b[1]+b[2]+b[3]+b[4];
    int ans=sum;
    for(int i=0;i<5;i++){
        //cout<<ans<<endl;
        if(a[i]%10!=0) ans=min(ans,sum-(10-a[i]%10));
        
    }

    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

class UnionFind {
    vector<int> parent;

public:
    UnionFind(int n)
    {
        parent = vector<int>(n, -1);
    }
    int getparent(int n)
    {
        // cout << n << endl;
        if(parent[n] == -1) return n;
        else return parent[n] = getparent(parent[n]);
    }
    void connect(int x, int y)
    {
        x = getparent(x);
        y = getparent(y);
        if(x == y) return;
        if(x > y) swap(x, y);
        parent[y] = x;
        // cout << x << " " << y << " " << parent[y] << endl;
    }
};

map<pair<int, int>, int> cnt;

int main()
{
    int n, k, l;
    cin >> n >> k >> l;
    UnionFind forroad(n);
    UnionFind fortrain(n);
    for(int i = 0; i < k; i++){
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        forroad.connect(p, q);
    }
    for(int i = 0; i < l; i++){
        int r, s;
        cin >> r >> s;
        r--;
        s--;
        fortrain.connect(r, s);
    }
    for(int i = 0; i < n; i++){
        int tmp1 = forroad.getparent(i);
        int tmp2 = fortrain.getparent(i);
        if(cnt.find(make_pair(tmp1, tmp2)) != cnt.end()) cnt[make_pair(tmp1, tmp2)]++;
        else cnt[make_pair(tmp1, tmp2)] = 1;
    }
    for(int i = 0; i < n; i++){
        cout << cnt[make_pair(forroad.getparent(i), fortrain.getparent(i))];
        if(i != n - 1) cout << " ";
        else cout << endl;
    }
    return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<string, int>;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    vector<vector<bool>> dp(n+1, vector<bool>(k+1));
    int ans = 0;
    dp[0][0] = true;
    for(int i = 0; i < n; i++)
    {
        bool flag = false;
        for(int x = 0; x <= k; x++)
        {
            if(dp[i][x])
            {
                dp[i+1][x] = true;
                if(x + a[i] < k)
                {
                    dp[i+1][x+a[i]] = true;
                }
                else
                {
                    flag = true;
                }
            }
        }
        if(flag) ans = 0;
        else ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3584
#include<cstdio>
#include<cstdlib>
#include<cstring>

using namespace std;

struct Node {
    int key;
    Node *prev, *next;
};

Node *nil;

void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

Node* listSearch(int key) {
    Node *cur = nil->next;
    while (cur != nil && cur->key != key) {
        cur = cur->next;
    }
    return cur;
}

void deleteNode(Node *t) {
    if ( t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

void printList() {
    Node *cur = nil->next;
    int isf =0;
    while(1) {
        if (cur == nil) break;
        if ( isf++ > 0) printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    int key, n, i;
    int size = 0;
    char com[20];
    int np = 0, nd = 0;
    scanf("%d", &n);
    init();
    for (i = 0; i < n; i++) {
        scanf("%s%d", com, &key);
        if (com[0] == 'i') { insert(key); np++; size++; }
        else if (com[0] == 'd') {
            if (strlen(com) > 6) {
                if (com[6] == 'F') deleteFirst();
                else if (com[6] == 'L') deleteLast();
            } else {
                deleteKey(key); nd++;
            }
            size--;
        }
    }

    printList();
}


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

vector<ll> v(200005),w(200005);

int ft(ll l, ll r, ll &m, vector<ll> &vctr){
  ll x = w[m-1] - w[l-1];
  ll y = w[r-1] - w[m-1];

  ll d = abs(x-y);
  
  while((x<y) && (m<r-1)){
    ++m;
    x += v[m-2];
    y -= v[m-2];
    
    if(d >= abs(x-y)){
      d = abs(x-y);
      continue;
    }else{
      x -= v[m-2];
      y += v[m-2];
      --m;
      break;
    }
  }
  
  vctr[0] = max(x,y);
  vctr[1] = min(x,y);
  return 0;
}


int main(){
  ll n;
  cin >> n;
  
  for(ll i=0; i<n; i++) cin >> v[i];
  w[0] = 0;
  w[1] = v[0];
  for(ll i=1; i<n; i++) w[i+1] = w[i] + v[i];
  
  vector<ll> tmp1(2);
  vector<ll> tmp2(2);
  
  ll left = 1;
  ll right = n+1;
  
  ll m_l = left + 1;
  ll sep = m_l + 1;
  ll m_r = sep + 1;
  
  ll tr = 1000000000000;
  
  for(sep = 3; sep <= n-1; sep++){
    ft(left, sep, m_l, tmp1);
    ft(sep, right, m_r, tmp2);
    
    tr = min(tr,max(tmp1[0],tmp2[0]) - min(tmp1[1],tmp2[1]));
    
  }
  
  cout << tr << endl;
}

Measured memory_bytes: 3328
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
	int f;char c;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
	static char q[64];int cnt=0;
	if(!x)pc('0');if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
const int maxn=3005;
int mod;
int mo(const int x){
	return x>=mod?x-mod:x;
}
int s[maxn][maxn],c[maxn][maxn],_0[maxn*maxn],_1[maxn];
int main(){
	int n;
	read(n),read(mod);
	s[0][0]=c[0][0]=1;
	for(int i=1;i<=n+1;++i){
		s[i][0]=0;c[i][0]=1;
		for(int j=1;j<=i;++j){
			s[i][j]=mo(s[i-1][j-1]+1ll*j*s[i-1][j]%mod);
			c[i][j]=mo(mod-c[i-1][j-1]+c[i-1][j]);
		}
	}
	int tmp=n*n;_0[0]=1;
	for(int i=1;i<=tmp;++i)
		_0[i]=mo(_0[i-1]<<1);
	_1[0]=2;
	for(int i=1;i<=n;++i)
		_1[i]=1ll*_1[i-1]*_1[i-1]%mod;
	int ans=0;
	for(int i=0;i<=n;++i){
		tmp=0;
		for(int j=0;j<=i;++j){
			tmp=mo(tmp+1ll*_0[(n-i)*j]*_1[n-i]%mod*s[i+1][j+1]%mod);
		}
		ans=mo(ans+1ll*c[n][i]*tmp%mod);
	}
	write(ans),pc('\n');
	return 0;
}


Measured memory_bytes: 93896
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

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

const int MAX = 55;
int H,W;
char tront[MAX][MAX];

bool check(int x, int y){
  return x>=0 && x<W && y>=0 && y<H && tront[x][y] == '#';
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> H >> W;
  rep(y,H)rep(x,W)cin >> tront[x][y];
  rep(y,H)rep(x,W){
    if(tront[x][y] == '#')continue;
    int count = 0;
    rep(i,8){
      int cx = x+dx[i], cy = y+dy[i];
      if(check(cx,cy)) ++count;
    }
    tront[x][y] = '0'+count;
  }
  rep(y,H){
    rep(x,W)cout << tront[x][y];
    cout << endl;
  }
  return 0;
}


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

using namespace std;

int main()
{
    string s;
    cin >> s;

    const char *c = s.c_str();

    int from, to;
    for (int i = 0; i < s.length(); ++i)
    {
        if (c[i] == 'A')
        {
            from = i;
            break;
        }
    }

    for (int i = s.length() - 1; i >= 0; --i)
    {
        if (c[i] == 'Z')
        {
            to = i;
            break;
        }
    }

    cout << (to - from + 1) << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, N, a, b) for(int i = a; i < N; i += b)
typedef long long ll;

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

	vector<ll> A(N);
	ll sum = 0;
	rep(i, N){
		cin >> A.at(i);
		sum += A.at(i);
	}
	ll ans = sum;
	ll tmp = 0;
	rep(i, N){
		tmp += A.at(i);
		ans = min(ans, abs(sum - tmp * 2));
	}
	cout << ans << endl;
}



Measured memory_bytes: 1792
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

namespace n91 {

	using i8 = std::int_least8_t;
	using i32 = std::int_least32_t;
	using i64 = std::int_least64_t;
	using u8 = std::uint_least8_t;
	using u32 = std::uint_least32_t;
	using u64 = std::uint_least64_t;
	using isize = std::ptrdiff_t;
	using usize = std::size_t;

	class rep {
		const usize f, l;

	public:
		class itr {
			friend rep;
			usize i;
			constexpr itr(const usize x) noexcept : i(x) {}

		public:
			void operator++() noexcept { ++i; }
			constexpr usize operator*() const noexcept { return i; }
			constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
		};
		constexpr rep(const usize first, const usize last) noexcept
			: f(first), l(last) {}
		constexpr itr begin() const noexcept { return itr(f); }
		constexpr itr end() const noexcept { return itr(l); }
	};
	class revrep {
		const usize f, l;

	public:
		class itr {
			friend revrep;
			usize i;
			constexpr itr(usize x) noexcept : i(x) {}

		public:
			void operator++() noexcept { --i; }
			constexpr usize operator*() const noexcept { return i; }
			constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
		};
		constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
		constexpr itr begin() const noexcept { return itr(l); }
		constexpr itr end() const noexcept { return itr(f); }
	};
	template <class T> using vec_alias = std::vector<T>;
	template <class T> auto md_vec(const usize n, const T &value) {
		return std::vector<T>(n, value);
	}
	template <class... Args> auto md_vec(const usize n, Args... args) {
		return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
	}
	template <class T> constexpr T difference(const T &a, const T &b) {
		return a < b ? b - a : a - b;
	}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>
#include <numeric>
#include<string>

namespace n91 {

	void main_() {
		usize n, q;
		std::string s;
		std::cin >> n >> q >> s;
		std::vector<usize> cnt(n + 1);
		for (const auto i : rep(1, n)) {
			if (s[i - 1] == 'A'&&s[i] == 'C') {
				++cnt[i];
			}
		}
		for (const auto i : rep(0, n)) {
			cnt[i + 1] += cnt[i];
		}
		while (q--) {
			usize l, r;
			std::cin >> l >> r;
			--l;
			--r;
			usize ans = cnt[r] - cnt[l];
			std::cout << ans << std::endl;
		}
	}

} // namespace n91

int main() {
	n91::main_();
	return 0;
}


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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> broken(n + 1);
    rep(i, m) {
        int a;
        cin >> a;
        broken[a] = 1;
    }
    vector<int> dp(n + 2);
    const int mod = 1000000007;
    dp[n] = 1;
    for(int i = n - 1; i >= 0; i--) {
        if(broken[i]) {
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod;
    }
    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 3924
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 1000001;
const int MOD = 1000000007;
   
        signed main() {
          int n,h,w,a,b,ans=0;
          cin>>n>>h>>w;
          for(int i=0;i<n;i++){
              cin>>a>>b;
              if(h<=a&&w<=b)ans++;
          }
          cout<<ans;
           return 0;

        }


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

class Dice_c{

private:
  int me[4];
  int topbot[2]; // top,bottom

public:
  void Input();
  void Roll(char c);
  void Output();

};


int main(){

  Dice_c dice;
  char com;

  dice.Input();
 
  while(1){
    scanf("%c",&com);

    if(com=='\n')
      break;

    dice.Roll(com);

  }
  
  dice.Output();

  return 0;
}


///////////////////////////////////////




void Dice_c::Input(){

  cin >> me[1] >> topbot[1] >> me[2] >> me[0] >> topbot[0] >> me[3];
  getchar();

}

void Dice_c::Roll(char c){

  int tmp;

  if(c == 'W'){
    tmp = me[0];
    me[0]=me[1] , me[1]=me[2] , me[2]=me[3] , me[3]=tmp;
  }
  else if(c == 'E'){
    tmp = me[3];
    me[3]=me[2] , me[2]=me[1] , me[1]=me[0] , me[0]=tmp;
  }
  else if(c == 'N'){
    tmp = topbot[1];
    topbot[1]=me[3] , me[3]=topbot[0] , topbot[0]=me[1] , me[1]=tmp;
  }
  else{
    tmp = topbot[0];
    topbot[0]=me[3] , me[3]=topbot[1] , topbot[1]=me[1] , me[1]=tmp;
  }

  
  /*
  cout << "  " << topbot[0] << endl;
  for(int i=0; i<4; i++)
    cout << me[i] << ' ';
  cout << endl << "  " << topbot[1] << endl;
  */

}


void Dice_c::Output(){

  cout << me[1] << endl;

}

Measured memory_bytes: 1188