akhauriyash/Code-Regression huggingface dataset:
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 10;
const int M = 1100;

int n, m, k;
string s[N];
int mx[M];
vector<vector<int>> row;

int get(int mask, int i) {
  return (mask >> i) & 1;
}

void build(int mask) {
  row.clear();
  for(int i = 0 ; i < n ; i++) {
    vector<int> val(m, 0);
    int j = i;
    while(j < n && get(mask, i) == get(mask, j)){
      for(int c = 0 ; c < m ; c++) {
        val[c] += s[j][c] == '1';
      }
      j++;
    }
    row.push_back(val);
    i = j - 1;
  }
}

int solve() {
  int ans = sz(row) - 1;
  vector<int> cur(n, 0);
  for(int j = 0 ; j < m ; j++) {
    bool can = true;
    for(int i = 0 ; i < sz(row) ; i++) {
      if(row[i][j] > k) return n * m;
      can &= (cur[i] + row[i][j]) <= k;
    }
    if(can) {
      for(int i = 0 ; i < sz(row) ; i++) {
        cur[i] += row[i][j];
      }
    } else {
      ans++;
      for(int i = 0 ; i < sz(row) ; i++) {
        cur[i] = row[i][j];
      }
    }
  }
  return ans;
}

void print() {
  cout << sz(row) << endl;
  for(int i = 0 ; i < sz(row) ; i++) {
    for(int j = 0 ; j < m ; j++)
      cout << row[i][j] << " ";
    cout << endl;
  }
}

int main()
{
  cin >> n >> m >> k;
  for(int i = 0 ; i < n ; i++)
    cin >> s[i];
  int best = n * m;
  for(int mask = 0 ; mask < (1 << n) ; mask++) {
    build(mask);
    // print();
    best = min(best, solve());
  }
  cout << best << endl;
  return 0;
}


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

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BDoNotDuplicate {
public:
    static constexpr int kStressIterations = 0;

    static void generateTest(std::ostream& test) {
    }

    void solve(std::istream& cin, std::ostream& cout) {
        int N, K;
        cin >> N >> K;

        vector<int> A(N);
        map<int, vector<int>> idx;
        REP(i, N) {
            cin >> A[i];
            idx[A[i]].push_back(i);
        }

        vector<int> next(N);
        for (auto kv: idx) {
            auto& b = kv.second;
            int m = b.size();
            b.push_back(kv.second[0] + N);
            REP(i, m) {
                next[b[i]] = b[i + 1] - b[i] + 1;
            }
        }

        int L = 60;
        vector<vector<int>> dnext(L + 1, vector<int>(N));
        dnext[0] = next;
        REP(l, L) {
            REP(i, N) {
                dnext[l + 1][i] = min(INF, dnext[l][i] + dnext[l][(i + dnext[l][i]) % N]);
            }
        }

        int k = N * K;
        int cur = 0;
        REV(l, 60, 0) {
            if (cur + dnext[l][cur % N] <= k) {
                cur += dnext[l][cur % N];
            }
        }
        if (cur == k) {
            cout << "" << endl;
            return;
        }

        vector<int> ans;
        set<int> s;
        FOR(i, cur % N, N - 1) {
            if (s.count(A[i])) {
                while (true) {
                    int v = ans.back();
                    ans.pop_back();
                    s.erase(v);
                    if (v == A[i]) break;
                }
            } else {
                ans.push_back(A[i]);
                s.insert(A[i]);
            }
        }

        REP(i, ans.size()) cout << ans[i] << " ";


    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BDoNotDuplicate solver;
    solver.solve(in, out);
    return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    int n = s.size();
    string t = s.substr(0, (n - 1) / 2);
    string u = t;
    reverse(t.begin(), t.end());
    if (t != u) {
        cout << "No" << endl;
        return 0;
    }
    t = s.substr((n + 3) / 2 - 1);
    u = t;
    reverse(t.begin(), t.end());
    if (t != u) {
        cout << "No" << endl;
        return 0;
    }
    u = s;
    reverse(s.begin(), s.end());
    if (u != s) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    
    return 0;
}



Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k,n = LI()
    a = LI()
    r = a[0] - a[-1] + k
    for i in range(n-1):
        r = max(r, a[i+1] - a[i])

    return k - r


print(main())





Measured memory_bytes: 28144
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n,tot;
const int N=1005;
LL a[N][N],zhi[N<<1],vis[10010];

long long GCD(long long x, long long y) 
{
    while (y ^= x ^= y ^= x %= y) void();
    return x;
}

long long LCM(long long x, long long y) 
{
    if (!x || !y) return x + y;
    return x / GCD(x, y) * y;
}/*
LL GCD(LL a,LL b){return b?GCD(b,a%b):a;}
LL LCM(LL a,LL b){return a&b?a/GCD(a,b)*b:a+b;}*/
void YYCH()
{
	vis[1]=1;
	for(int i=2;i<=10000;++i)
	{
		if(!vis[i])zhi[++tot]=i;
		for(int j=1;j<=tot&&i*zhi[j]<=10000;++j)
		{
			vis[i*zhi[j]]=1;
			if(!(i%zhi[j]))break;
		}
	}
}
int main()
{
	cin>>n;if(n==2)return printf("4 7\n23 10\n")==233;
	YYCH();
	 for (int i = 1; i <= n; ++i)
        for (int j = (i + 1 & 1) + 1; j <= n; j += 2)
            a[i][j] = zhi[(i + j) / 2] * zhi[n + (i - j) / 2 + (n + 1) / 2];
    for (int i = 1; i <= n; ++i)
        for (int j = (i & 1) + 1; j <= n; j += 2)
            a[i][j] = LCM(LCM(a[i - 1][j], a[i][j - 1]),
                          LCM(a[i][j + 1], a[i + 1][j])) +
                      1;
    for (int i = 1; i <= n; ++i, puts(""))
        for (int j = 1; j <= n; ++j) printf("%lld ", a[i][j]);
	/*
    for(int i=1;i<=n;++i)
    	for(int j=((i+1)&1)+1;j<=n;j+=2)
    		a[i][j]=zhi[(i+j)/2]*zhi[n+(i-j)/2+(n+1)/2];
    for(int i=1;i<=n;++i)
    	for(int j=(i&1)+1;j<=n;j+=2)
			a[i][j]=LCM(LCM(a[i-1][j],a[i][j-1]),LCM(a[i+1][j],a[i][j+1]))+1;
    for(int i=1;i<=n;++i,puts(""))
    	for(int j=1;j<=n;++j)printf("%lld ",a[i][j]);
	*/
    return 0;
}

Measured memory_bytes: 7168
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,v;
  int A[N+1];
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
  
 

  for(i=1;i<=n;i++){
    
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
     
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
   
    }
    trace(A,n);  
  }
  return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
	char c = getchar();
	bool f = false;
	for (x = 0; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = true;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	if (f) {
		x = -x;
	}
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
	read(x), read(y...);
}
const int N=2e5+10,P=1e9+7;
int n;
int ST[N],F[N][2];
struct Data {
  int x,v;
  Data () {}
  Data (int x,int v) :x(x),v(v) {}
}A[N];
bool cmp(Data A,Data B) {
  return A.v<B.v;
}
struct Sec {
  int l,r;
  Sec () {}
  Sec (int l,int r) :l(l),r(r) {}
}G[N];
bool cmp1(Sec A,Sec B) {
  return A.r==B.r?A.l<B.l:A.r<B.r;
}
//#define rua
int main() {
//	ios::sync_with_stdio(false);
#ifdef rua
	freopen("GG.in","r",stdin);
#endif
  read(n);
  for(int i=1;i<=n;++i) read(A[i].x,A[i].v);
  sort(A+1,A+n+1,cmp);
  int top=0;
  for(int i=1;i<=n;++i) {
    if(!top||A[i].x>A[ST[top]].x) ST[++top]=i;
    int l=1,r=top;
    while(l!=r) {
      int mid=l+r>>1;
      if(A[ST[mid]].x>=A[i].x) r=mid;
      else l=mid+1;
    }
    G[i].l=ST[l];
  }
  top=0;
  for(int i=n;i;--i) {
    if(!top||A[i].x<A[ST[top]].x) ST[++top]=i;
    int l=1,r=top;
    while(l!=r) {
      int mid=l+r>>1;
      if(A[ST[mid]].x<=A[i].x) r=mid;
      else l=mid+1;
    }
    G[i].r=ST[l];
  }
  sort(G+1,G+n+1,cmp1);
  int res=0; top=0;
  for(int i=1;i<=n;++i) {
    if(G[i].l==1) F[i][1]=(F[i-1][0]+F[i-1][1]+1)%P;
    else {
      while(top<i&&G[top+1].r<G[i].l-1) ++top;
      F[i][1]=(F[i-1][1]-F[top][1]+P)%P;
      F[i][0]=(F[i-1][0]-F[top][0]+P+1)%P;
    }
    if(G[i].r==n) res=(res+F[i][1])%P;
    F[i][1]=(F[i-1][1]+F[i][1])%P;
    F[i][0]=(F[i-1][0]+F[i][0])%P;
  }
  printf("%d\n",res);
	return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1000000000000000000;
const long double PI=3.14159265358979;
const ll MAX=100010;

int main() {
  ll N,M;
  string s,t;
  cin>>N>>M>>s>>t;
  ll g=__gcd(N,M);
  ll ans=N*M/__gcd(N,M);
  N/=g;
  M/=g;
  ll c=1;
  for(int i=0;i<g;i++){
  //  cout<<N*i<<" "<<M*i<<endl;
    if(s[i*N]!=t[i*M]){
      c=0;
      break;
    }
  }
  if(c){
    cout<<ans;
  }
  else{
    cout<<-1;
  }
  
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

string s;
ll ans;

void f(int n, ll sum){
	if(n == s.size()){
		ans += sum;
		return;
	}
	ll now = 0LL;
	for(int i = n; i <s.size(); i++){
		now *= 10LL;
		now += s[i]-'0';
		f(i+1, sum + now);
	}
}

int main(){
	cin>>s;
	f(0,0LL);
	cout<<ans<<endl;
}

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

typedef pair<int,int> pii;

int c[1000001];

int main(){
	int n, q, a, v;
	scanf("%d%d", &n, &q);
	priority_queue<pii> pq;
	pq.push(pii(0, -1));

	for(int i = 0; i < q; ++i){
		scanf("%d%d", &a, &v);
		c[a] += v;
		pq.push(pii(c[a], -a));

		while(1){
			int x = -pq.top().second;
			int y = pq.top().first;
			if(c[x] == y){
				printf("%d %d\n", x, y);
				break;
			}
			pq.pop();
		}
	}
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000
#define LLINF 1e18

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_abc_a() {
	ll n, m;
	ll x, y;
	ll a, b, d;
	ll c;
	//char c;
	ll h, w;
	ll k;
	string s, t;
	//ll s, t;
	ll l_ans = 0;
	string s_ans = "NG";

	cin >> a >> b >> c;
	map<ll, ll> mp;
	++mp[a];
	++mp[b];
	++mp[c];

	cout << mp.size() << "\n";

	return;
}


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

	solve_abc_a();

	return 0;
}


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

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

    string left = s.substr(0,n);
    string right = s.substr(n);
    reverse(right.begin(), right.end());

    map<pair<string, string>, long long int> map1, map2;
    for(int bit=0; bit<(1<<n); bit++){
        string a = "", b = "";
        for(int i=0; i<n; i++){
            if(bit >> i & 1) a += left[i];
            else b += left[i];
        }

        if(map1.find({a,b}) == map1.end()) map1[{a,b}] = 1;
        else map1[{a,b}] += 1;
    }
    for(int bit=0; bit<(1<<n); bit++){
        string a = "", b = "";
        for(int i=0; i<n; i++){
            if(bit >> i & 1) a += right[i];
            else b += right[i];
        }

        if(map2.find({a,b}) == map2.end()) map2[{a,b}] = 1;
        else map2[{a,b}] += 1;
    }

    long long int ans = 0;
    for(auto m : map1){
        auto key = m.first;
        if(map2.find(key) != map2.end()) ans += m.second * map2[key];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 60988
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def p(M, N, mod):
    if N == 0:
        return 1
    if N % 2 == 0:
        half = p(M, N // 2, mod)
        return half * half % mod
    else:
        return M * p(M, N - 1, mod) % mod


if __name__ == "__main__":
    M, N = map(int, input().split())
    mod = 1_000_000_007
    ans = p(M, N, mod)
    print(ans)


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;




int main() {
    while(1){
        int n;
        cin >> n;
        if (n == 0)break;

        vector<int> w(n);
        REP(i,n) cin >> w[i];

        vector<vector<int>> dp(n,vector<int>(n,0));

        for(int width=2; width<=n; width++){//もらうDP
            FOR(left,0,n-width+1){
                int right = left+width-1;
                if(width%2==0 && dp[left+1][right-1]==width-2){//内側の区間が適切に処理でき、
                    if(abs(w[left] - w[right])<=1){//端の差が1以下なら
                        dp[left][right] = width;
                    }
                }

                for(int mid=left; mid<right; mid++){
                    dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid+1][right]);
                }
                
            }
        }

        cout << dp[0][n-1] << endl;
    }
    return 0;
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define MSGF(x, n) MSG(fixed << setprecision(n) << x)
#define END(x) cout << x << endl; return(0);
#define IPT(v, n) REP(i, 0, n){ cin >> v[i]; }
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<ull> vul;
typedef vector<vector<ull>> vvul;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
const static ll INF = 1LL << 30;

ll a, b, c, d, k, l, m, n, h, w, q, x, y;
string s, t;

ll ans = 0;
ll sum = 0;
ll cnt = 0;
ll cur = 0;
ll tmp = 0;
ll mini = INF;
ll maxi = 0;

double ave = 0.0;

ll mod_pow(ll base, ll power) {
    if (power == 0) return 1;
    if (power == 1) return base % MOD;
    if (power % 2 == 0) return ((mod_pow(base % MOD, (power / 2)) % MOD) * (mod_pow(base, (power / 2)) % MOD)) % MOD;
    return (base % MOD * (mod_pow(base % MOD, power - 1) % MOD)) % MOD;
}

ll mod_fact(ll number) {
    ll ret = 1;
    ll count = 1;
    while (count <= number) {
        ret *= (count % MOD);
        ret %= MOD;
        count++;
    }
    return ret % MOD;
}

ll gcd(ll a, ll b) {
    if (a < b) {
        return gcd(b, a);
    }
    ll c = a % b;
    while (c != 0) {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    cin >> d;
    vl c(26);
    vvl s(d, vl(26));
    vl t(d);
    vl last(26);

    REP(i, 0, 26) {
        cin >> c[i];
        last[i] = 0;
    }

    REP(i, 0, d) {
        REP(j, 0, 26) {
            cin >> s[i][j];
        }
    }

    REP(i_d, 0, d) {
        ll max_score = -LLONG_MAX;
        ll max_type = -1;
        REP(i_type, 0, 26) {
            ll tmp_score = s[i_d][i_type];
            REP(i_type_all, 0, 26) {
                if (i_type == i_type_all) continue;
                tmp_score -= c[i_type_all] * (i_d + 1 - last[i_type_all]);
            }
            if (tmp_score >= max_score) {
                max_score = tmp_score;
                max_type = i_type;
            }
        }
        last[max_type] = i_d + 1;
        MSG(max_type + 1)
    }
}


Measured memory_bytes: 3732
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

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

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&... args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

bool isPalindrome(string S) {
  bool ok = true;

  for (int i = 0; i < S.size(); i++)
    ok &= S[i] == S[S.size() - i - 1];

  return ok;
}

int main() {
  string S;
  int N;

  cin >> S;
  N = S.size();

  bool ans = true;

  ans &= isPalindrome(S);
  ans &= isPalindrome(S.substr(0, S.size() / 2));
  ans &= isPalindrome(S.substr(S.size() - S.size() / 2, S.size() / 2));

  if (ans)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

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

using namespace std;

int main() {
	int n,c=0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];

	for (int i = 0; i < n; i += 2) {
		if (a[i] % 2 != 0) {
			c++;
		}
	}
	cout << c;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
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; }
const ll MOD = 1e9+7;

int main(){
    int N;
    cin >> N;
    double sum = 0;
    REP(i,N){
        int a;
        cin >> a;
        sum += 1 / (double)a;
    }

    double ans = 1 / sum;

    printf("%.20lf\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
typedef pair<int,int> P;

int gcd(ll a, ll b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
int lcm(ll a, ll b){
  return a / gcd(a,b) * b;
}

struct edge{int to,id;};
vector<edge> g[55];
vector<int> es;

bool dfs(int now,int goal,int p = -1){
  if(now == goal) return true;
  for(auto e:g[now]){
    if(e.to == p) continue;
    if(dfs(e.to,goal,now)){
      es.push_back(e.id);
      return true;
    }
  }
  return false;
}

int main(){
  int n; cin >> n;
  rep(i,n-1){
    int a,b; cin >> a >> b;
    a--,b--;
    g[a].push_back({b,i});
    g[b].push_back({a,i});
  }
  int m; cin >> m;
  vector<ll> eset(m);
  rep(i,m){
    int u,v; cin >> u >> v;
    u--,v--;
    es = vector<int>();
    dfs(u,v);
    for(int e:es){
      eset[i] |= 1LL << e;
    }
  }
  
  ll ans = 0;
  rep(i,1 << m){
    ll mask = 0;
    rep(j,m){
      if(i & (1 << j)){
        mask |= eset[j];
      }
    }
    int white_e = __builtin_popcountll(mask);
    ll pattern = 1LL << (n - 1 - white_e);
    if(__builtin_popcountll(i)%2 == 0) ans += pattern;
    else ans -= pattern;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);
#define N 100010
vector<ll> e[N];
ll n,m,a[N],b[N];

namespace uf{
  ll p[N];
  void init(){
      for(int i=0;i<N;i++)p[i]=i;
  }
  ll par(ll x){return p[x]=(x==p[x]?x:par(p[x]));}
  void unite(ll x,ll y){
      x=par(x),y=par(y);
      if(x!=y){
	  p[x]=y;
      }
  }
  bool same(ll x,ll y){return par(x)==par(y);}
};

ll f[N],g[N];
P dat[N]; bool vis[N];
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
      cin>>a[i]>>b[i];
      dat[i-1]=make_pair(a[i]-b[i],i);
  }
  sort(dat,dat+n);
  
  for(int i=0;i<m;i++){
      ll x,y;cin>>x>>y;
      e[x].push_back(y);
      e[y].push_back(x);
  }
  
  for(int i=1;i<=n;i++)vis[i]=0,g[i]=b[i];
  uf::init();
  for(int i=0;i<n;i++){
      int y=dat[i].second; vis[y]=1;
      f[y]=1e17; //cout<<"#"<<y<<endl;
      vector<ll> vist;
      for(auto x:e[y])if(vis[x]==1&&uf::same(x,y)==0){
	  x=uf::par(x); vist.push_back(x);
	  g[y]+=g[x];
	  uf::unite(x,y);
      }
      if(g[y]==b[y]){f[y]=max(a[y],b[y]); continue;}
      for(auto x:vist){
	  chmin(f[y],max(a[y],b[y]+f[x])+g[y]-g[x]-b[y]);
      }
  }
  cout<<f[dat[n-1].second]<<endl;
  //for(int i=1;i<=n;i++)cout<<f[i]<<" "<<g[i]<<endl;
    return 0;
}



Measured memory_bytes: 13056
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] b=new long[n];
        long sum=0;
        long flag=0;
        long temp=Long.MAX_VALUE;
        for(int i=0;i<n;++i){
          b[i]= sc.nextInt();
          flag+=b[i]<0?1:0;
          b[i]*=b[i]<0?-1:1;
          sum+=b[i];
          temp=temp<b[i]?temp:b[i];
        }
        if(flag%2==0){
          System.out.println(sum);
        }else{
          System.out.println(sum-2*temp);
        }
    }
}


Measured memory_bytes: 48888
#include<bits/stdc++.h>
using namespace std;
 
int main(){
string s;
string c;
 
cin>>c;
 
for(int i=0;i<c.size();i++){
if(c[i]=='1'){
s+="1";
}else if(c[i]=='0'){
s+="0";
}else if(c[i]=='B'){
if(!s.empty())
s.erase(s.end()-1);
}
}
 
cout<<s<<endl;
 
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   string s,t,u;
   cin>>s>>t;
   int a,b;
   cin>>a>>b;
   cin>>u;
   if(s==u)
   {
       cout<<a-1<<" "<<b<<endl;
   }
   else
    cout<<a<<" "<<b-1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
const int N=201;
const int MAXN=1e5+10;
const int mod=1e9+7;
typedef long long ll;
template<class T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;}
int n,X;
int dp[N][MAXN];
int S[N];
int main()
{
	init(n),init(X);
	for(int i=1;i<=n;++i) init(S[i]);
	sort(S+1,S+1+n);reverse(S+1,S+1+n);
	dp[0][X]=1;
	for(int i=1;i<=n;++i) {
		for(int j=X;~j;--j){
			Inc(dp[i][j%S[i]],dp[i-1][j]);
			Inc(dp[i][j],(ll)(n-i)*dp[i-1][j]%mod);
		}
	}int ans=0;
	for(int i=0;i<=X;++i) Inc(ans,(ll)i*dp[n][i]%mod);
	cout<<ans<<endl;
}


Measured memory_bytes: 78336
N = int(input())

As = list(map(int, input().split()))

dic = {}
for A in As:
    if A in dic.keys():
        dic[A] += 1
    else:
        dic[A] = 1

total = 0
for A in dic.keys():
    a = dic[A]
    if a > 1:
        temp = a*(a-1)/2
        total += temp

for i in range(N):
    Ai = As[i]
    if dic[Ai] == 2:
        print(int(total-1))
    elif dic[Ai] > 2:
        a = dic[Ai]
        diff = (a*(a-1) - (a-1)*(a-2))/2
        print(int(total - diff)) 
    else:
        print(int(total))

Measured memory_bytes: 26140
n = input()
n = n.split()
k = int(n[1])
n = int(n[0])
c = [0]
for f in range(n-1):
  c.append(0)
for b in range(k):
  d = int(input())
  a = input()
  a = a.split()
  for e in range(d):
    c[int(a[e])-1] = 1
h = 0
for g in range(n):
  if c[g] == 0:
    h = h + 1
print(h)

Measured memory_bytes: 9152
open Str

let read_list f =
  split (regexp " +") (read_line ()) |> List.map f

let print_array a = Array.to_list a |> List.map string_of_int |> String.concat " " |> print_endline

let insertion_sort a n =
  let rec iloop i =
    if i = n then ()
    else
      let v = a.(i) in
      let rec jloop j =
        if j < 0 || a.(j) <= v then a.(j+1) <- v
        else
          begin
            a.(j+1) <- a.(j);
            jloop (j-1)
          end
      in jloop (i-1); print_array a; iloop (i+1)
  in print_array a; iloop 1
  
let () =
  let n = read_int () in
  let ar = Array.of_list (read_list int_of_string) in
  insertion_sort ar n

Measured memory_bytes: 2876
def insertionSort(A,input_num):
    for i in range(input_num):
        v = A[i]
        j = i - 1
        while(j >= 0 and A[j] > v):
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = v
        print(*A)
        
input_num = int(input())
A = list(map(int, input().split()))

insertionSort(A,input_num)


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

int main()
{
    int n,m;
    cin >> n >> m;
    vector<ll> xa(n),ya(n);
    for(ll i = 0;i < n;i++) cin >> xa[i] >> ya[i];
    vector<ll> xb(m),yb(m);
    for(ll i = 0;i < m;i++) cin >> xb[i] >> yb[i];
    for(ll i = 0;i < n;i++){
        ll min = 1000000000;
        ll min_n = 0;
        for(ll j = 0;j < m;j++){
            ll tmp = abs(xa[i] - xb[j]) + abs(ya[i] - yb[j]);
            if(tmp < min){
                min = tmp;
                min_n = j + 1;
            }
        }
        cout << min_n << endl;
    }
}


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

using namespace std;

template< typename T >
struct RadixHeap
{
  using uint = unsigned;

  vector< pair< uint, T > > v[33];
  uint size, last;

  RadixHeap() : size(0), last(0) {}

  bool empty() const { return size == 0; }

  inline int getbit(int a)
  {
    return a ? 32 - __builtin_clz(a) : 0;
  }

  void push(uint key, const T &value)
  {
    ++size;
    v[getbit(key ^ last)].emplace_back(key, value);
  }

  pair< uint, T > pop()
  {
    if(v[0].empty()) {
      int idx = 1;
      while(v[idx].empty()) ++idx;
      last = min_element(begin(v[idx]), end(v[idx]))->first;
      for(auto &p : v[idx]) v[getbit(p.first ^ last)].emplace_back(p);
      v[idx].clear();
    }
    --size;
    auto ret = v[0].back();
    v[0].pop_back();
    return ret;
  }
};

template< typename T >
struct edge
{
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s)
{
  const auto INF = numeric_limits< T >::max();
  vector< T > dist;
  dist.assign(g.size(), INF);

  using Pi = pair< T, int >;
  RadixHeap< int > que;
  dist[s] = 0;
  que.push(dist[s], s);
  while(!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      auto next_cost = cost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      que.push(dist[e.to], e.to);
    }
  }
  return dist;
}

int main()
{
  int V, E, S;
  scanf("%d %d %d", &V, &E, &S);
  WeightedGraph< unsigned > g(V);
  for(int i = 0; i < E; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    g[x].emplace_back(y, z);
  }
  auto cost = dijkstra(g, S);
  for(int i = 0; i < V; i++) {
    if(cost[i] == numeric_limits< unsigned >::max()) puts("INF");
    else printf("%d\n", cost[i]);
  }
}



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

#define mp make_pair
#define mt make_tuple
#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 forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef double ld;

int main()

{ 
ios_base::sync_with_stdio(false);

cin.tie(NULL);
ll a[3];
forn(i,3)
cin>>a[i];
sort(a,a+3);
if(a[0]==5&&a[1]==5&&a[2]==7)
cout<<"YES";
else cout<<"NO";

return 0;

}


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

const int mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define ll long long
#define vi vector < int >
#define si set <int>
#define mii map <int, int>
#define vll vector < ll >
#define pii pair < int , int >
#define ff first
#define tc \
    int ttt; cin >> ttt;\
    while(ttt --)
#define ss second
#define f(i,a,b) for(int i=a;i<b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)
#define nl '\n'
#define all(x) x.begin() , x.end()
#define mne min_element
#define mxe max_element
#define pr(x) cout << fixed << setprecision(10) << x
ll gcd(ll x, ll y) {return y == 0 ? x : gcd(y, x % y);}
int logg(ll x , ll y) {if (x == 0) return -1; return logg(x / y, y) + 1;}
ll poww(ll a, ll b, ll m) {
	if (b == 0) return 1;
	ll ans = 1;
	ans = poww(a, b >> 1, m);
	ans = (ans * ans) % m;
	if (b & 1) ans = (ans * a) % m;
	return ans;
}
// Start of code
int n;
int stones[100005];
int dp[3001][3001][2];
int X;
int Y;

int solve(int i, int j, int choice) {

	if (i > j) return 0;

	if (dp[i][j][choice] != -1) return dp[i][j][choice];

	if (choice) {
		dp[i][j][choice] = max(stones[i] + solve(i + 1, j, 0), stones[j] + solve(i, j - 1, 0));
	}
	else dp[i][j][choice] = min(solve(i + 1, j, 1), solve(i, j - 1, 1));

	return dp[i][j][choice];
}

int32_t main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast;
	cin >> n;
	memset(dp , -1, sizeof dp);
	int sum = 0;
	f(i, 0, n) cin >> stones[i], sum += stones[i];
	X = solve(0, n - 1, 1);
	cout << X - (sum - X) << nl;
}

Measured memory_bytes: 144596
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#include <bitset>
#include<math.h>
#include<queue>
using namespace std;
#define MAX 300000
#define INF 3000
typedef long long ll;
typedef pair<int,int> P;

int c[10][10],dis[1000][1000];
int N,M,ans;
bool flag=true;;
int perm[10];



int main(){
  int data1,data2;
  cin>>N>>M;
  for(int i=0;i<M;i++){
    cin>>data1>>data2;
    c[data1-1][data2-1]++;
    c[data2-1][data1-1]++;
  }
  for(int i=0;i<N;i++){
    perm[i]=i;
  }
  do{
    flag=true;
    for(int i=0;i<N-1;i++){
      if(c[perm[i]][perm[i+1]]==0){
        flag=false;
        break;
      }
    }
    if(flag) ans++;
  }while(next_permutation(perm+1,perm+N));
  cout<<ans<<endl;
  
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    map<int, int> m;
    auto prime_factorize = [&](int k) -> void {
        for (int i = 2; i*i <= k; i++)
        {
            if (k%i != 0) continue;
            int num = 0;
            while (k%i == 0) {
                num++;
                k /= i;
            }
            m[i] += num;
        }
        if (k != 1) m[k] += 1;        
    };
    for (int i = 1; i <= n; i++)
    {
        prime_factorize(i);
    }

    auto rec = [&](auto &&rec, auto p, int k) -> int {
        if (p == m.end()) {
            if (k == 1) return 1;
            else return 0;
        }

        int res = 0;
        for (int i = 0; i <= p->second; i++)
        {
            if (k%(i+1) == 0) {
                res += rec(rec, ++p, k/(i+1));
                p--;
            }
        }
        return res;
    };
    cout << rec(rec, m.begin(), 75) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <iomanip>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
//typedef long long unsigned int ll;
typedef long long ll;
typedef pair<ll, ll> edge;
typedef tuple<ll, ll, ll> tp;

int main() {
  ll n;
  cin >> n;
  vector<edge> T[n+1];
  for(int i=0;i<n-1;i++){
    ll u,v,w;
    cin >> u >> v >> w;
    //cout << u << v << w <<endl;
    T[u].push_back(edge(v,w));
    T[v].push_back(edge(u,w));
  }
  //cout << T[1][0].first << endl;
  
  int cl[n+1];
  fill(cl,cl+n+1,-1);
  cl[1] = 0;
  queue<tp> q;
  for(int i=0; i<T[1].size(); i++){
    q.push(tp(1, T[1][i].first, T[1][i].second));
  }
  while(!q.empty()){
    tp tmp = q.front(); q.pop();
    ll bf = get<0>(tmp);
    ll af = get<1>(tmp);
    ll we = get<2>(tmp);
    //cout << bf << af << we << endl;

    if(cl[af] != -1) continue;
    else if (we%2 == 0) cl[af] = cl[bf];
    else if (we%2 == 1) cl[af] = 1 - cl[bf];
    //cout << af << cl[af] << endl;
    for(int i=0; i<T[af].size(); i++){
      q.push(tp(af, T[af][i].first, T[af][i].second));
    }
  //cout << 'b' << endl;
  }
  //cout << 'a' << endl;
  for(int i=1;i<=n;i++) cout << cl[i] << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int x;
  cin>>x;
  int ans = 1;
  FOR(b,2,x+1){
    int cur = b*b;
    while(cur <= x){
      CHMAX(ans, cur);
      cur *= b;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val a, b, c, x = sc.nextInt

  var count = 0
  for(d <- 0 to a; e <- 0 to b; f <- 0 to c){
    if(x == 500 * d + 100 * e + 50 * f) count += 1
  }
  println(count)
}

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

int main(){
    int h,w;

    cin >> h >> w;

    vector<string> a(h);

    for(int i=0; i<h ; i++){
        cin >> a.at(i);
    }

    for(int i=0; i<w+2; i++){
        cout << '#';
    }
    cout << endl;

    for(int i=0; i<h; i++){
        cout << '#';
        cout << a.at(i);
        cout << '#' << endl;
    }

    for(int i=0; i<w+2; i++){
        cout << '#';
    }
    cout << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision

#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL  MOD=1E9+7;

struct Problem{
    int n;
    string s;
    vector<int> c;
    Problem(LL n):n(n),c(0){};

    void solve(){
        cin >> s;
        int tmp=0;
        for(int i=0; i<n; ++i){
            if(s[i]=='0'){
                c.push_back(tmp);
                tmp=0;
            }else{
                tmp++;
            }
        }
        c.push_back(tmp);
        DBG(c)
        vector<vector<int>> dp ((int)c.size(),vector<int>(4));
        for(int i=1; i<(int)c.size(); ++i){
            if(c[i]>0 and c[i-1]>0){
                dp[i][0]=*max_element(dp[i-1].begin(),dp[i-1].end());
                dp[i][1]=dp[i-1][0]+c[i-1];
                if(c[i-1]>1)dp[i][1]=max({dp[i][1],dp[i-1][1]+c[i-1]-1,dp[i-1][3]+1});
                dp[i][2]=dp[i-1][0]+c[i];
                if(c[i-1]>1)dp[i][2]=max({dp[i][2],dp[i-1][1]+c[i],dp[i-1][3]+c[i]});
                dp[i][3]=dp[i][2]-1;
            }else{
                dp[i][0]=*max_element(dp[i-1].begin(),dp[i-1].end());
            }
        }
        DBG(dp)
        cout << *max_element(dp.back().begin(),dp.back().end())<<"\n";
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    long long n=0;
    cin >> n;
    Problem p(n);
    p.solve();
    return 0;
}



Measured memory_bytes: 30100
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
C_array = na()
C_array.sort()
ans = 0
mod = 10 ** 9 + 7
dp = [C_array[0], 0]
arr2 = [0, 1]
j = 1
for i in range(N):
    j = j * 2 % mod
    arr2.append(j)

# print(dp)
cold = C_array[0]
cusum = 0
for i, c in enumerate(C_array[1:]):
    new00 = (dp[0] + cold * arr2[i + 1] + cusum *
             arr2[i] + c * arr2[i + 1]) % mod
    new01 = (dp[1] + cusum * arr2[i] + c * arr2[i + 1]) % mod
    # print(new00,new01)
    new0 = (new00 + new01) % mod
    new1 = (dp[0] + dp[1]) % mod
    dp = [new0, new1]
    # print(dp)
    cusum = (cold + cusum) % mod
    cold = c
ans = (dp[0] + dp[1]) * arr2[N + 1] % mod
print(ans)


Measured memory_bytes: 110168
#include <bits/stdc++.h>
using namespace std;
int main(){

  int n,m,c;
  cin >> n >> m >> c;
  int b[m],a[n][m];
  for(int i=0; i<m; i++) cin >> b[i];
  for(int i=0; i<n; i++){
  	for(int j=0; j<m; j++){
    	cin >> a[i][j];
    }
  }
	int sum=0;
  int count =0;
  for(int i=0; i<n; i++){
    
  	for(int j=0; j<m; j++){
    	sum +=a[i][j]*b[j];
    }
    if((sum+c) > 0) count++;
    sum=0;
  }
  
  
  cout << count << endl;
}

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES puts("YES\n")
#define Yes puts("Yes\n")
#define NO  puts("NO\n")
#define No  puts("No\n")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }



signed main() {

	int A, B;
	cin >> A >> B;
	cout << max({ A + B, A - B, A * B }) << endl;



	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

string S;
vector<set<int>> posLists;

int main()
{
    posLists.assign(26, set<int>{500001});
    int N; cin >> N >> S;
    for (int i = 0; i < N; ++i)
    {
        posLists[S[i] - 'a'].insert(i);
    }
    int Q; cin >> Q;
    // Type1はO(log(N))，Type2はO(#alphabet*logN)より，総計算量はO(Q*#alphabet*logN)~O(10e6)でギリギリ？
    while (Q--)
    {
        int type; cin >> type;
        if (type == 1)
        {
            // 文字の位置を更新:O(logN)
            int iq; char cq; cin >> iq >> cq; --iq;
            posLists[S[iq] - 'a'].erase(iq);  // O(logN)
            posLists[cq - 'a'].insert(iq);  // O(logN)
            S[iq] = cq;
        }
        else
        {
            int lq, rq; cin >> lq >> rq; --lq;
            int ret = 0;
            // 各文字について[L, R]の範囲に存在するかどうか調べる:O(#alphabet*logN)
            for (int i = 0; i < 26; ++i)
            {
                // L以上R以下の要素を持つかどうか探索する:O(logN)
                const auto lb = *posLists[i].lower_bound(lq);
                const auto rb = *posLists[i].lower_bound(rq);
                if (lb < rb) ++ret;
            }
            cout << ret << endl;
        }
    }
}


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

int main(){
    long long n,k; cin >> n >> k;
    long long ans = min(n%k,abs(k-n%k));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String  S = sc.next();
   // char[] s = S.toCharArray();
    //ArrayList<Character> aa = new ArrayList<>();

	if(S.charAt(0)==S.charAt(1)){
		System.out.println("Bad");
    }else if(S.charAt(1)==S.charAt(2)){
		System.out.println("Bad");
    }else if(S.charAt(2)==S.charAt(3)){
		System.out.println("Bad");
    }else{
		System.out.println("Good");
	}
	}
}

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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

int main() {
    int n;
    cin >> n;
    if (n < 1200) {
        puts("ABC");
    } else {
        puts("ARC");
    }

    return 0;
}

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

using namespace std;

typedef long long ll;

ll n, k, a, ans = 0;
vector<ll> d(40);
vector< vector<ll> > m(40, vector<ll>(2, -1));

ll solve(ll i, bool f) {
    if (m.at(i).at(f) >= 0) return m.at(i).at(f);
    if (i == 0) return m.at(i).at(f) = max(((k & 1) | f) * (n - d.at(0)), d.at(0));
    if ((k & (1LL << i)) || f) return m.at(i).at(f) = max(solve(i - 1, f) + ((n - d.at(i)) << i), solve(i - 1, true) + (d.at(i) << i));
    return m.at(i).at(f) = solve(i - 1, f) + (d.at(i) << i);
}

int main() {
    scanf("%lld%lld", &n, &k);
    for (ll i = 0; i < n; ++i) {
        scanf("%lld", &a);
        for (ll j = 0; j < 40; ++j) if (a & (1LL << j)) ++d.at(j);
    }
    printf("%lld\n", solve(39, false));
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>

using namespace std;
typedef long long int ll;

ll n,a[300010],r=0;

int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        r+=a[i]%2;
    }
    cout<<(r%2 ? "NO":"YES")<<endl;
    
    
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(void)
{
    int a,n,c;
    scanf("%d",&a);
    for(n = 1;n < 10;n++)
    {
        if(a/n < 10)
        {
            if(a%n == 0)
            {
                c = 1;
                break;
            }
            else
            {
                c = 0;   
            }
            
        }
        else
        {
            c = 0;
        }
        
    }

    if(c == 0)
    {
        printf("No\n");
    }
    else if(c == 1)
    {
        printf("Yes\n");
    }
    return 0;
    
}

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

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



int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int s = c / b;
  int t = c % b;
  int u = a / d;
  int v = a % d;

  if (s < u){
    cout << "Yes" << endl;
  }
  if (s == u) {
    if (t == 0) {
      cout << "Yes" << endl;
    }
    if (t != 0 && v == 0) {
      cout << "No" << endl;
    }
    if (t != 0 && v != 0) {
      cout << "Yes" << endl;
    }
  }
  if (s > u) {
    if (s - u == 1) {
      if (t != 0) {
        cout << "No" << endl;
      }
      if (t == 0 && v != 0) {
        cout << "Yes" << endl;
      }
      if (t == 0 && v == 0) {
        cout << "No" << endl;
      }
    }
    else {
      cout << "No" << endl;
    }
  }

}

Measured memory_bytes: 3636