akhauriyash/Code-Regression huggingface dataset:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

void add(int & x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int sum(int x, int y) {
  add(x, y);
  return x;
}

int mult(int x, int y) {
  return (ll) x * y % mod;
}

int power(int x, ll p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
    p >>= 1;
  }
  return res;
}

int inv(int x) {
  return power(x, mod - 2);
}

const int maxn = 6100;

int c[maxn][maxn];

void precalc() {
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j - 1];
      add(c[i][j], c[i - 1][j]);
    }
  }
}

int n, m;

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  return true;
}

void solve() {
  int res = 0;
  for (int diff = n - 1; diff <= n; diff++) {
    int cur = 0;
    int step = 2 * (diff + 1);
    vector<int> v(step);
    for (int i = 0; i <= 2 * m; i++) {
      add(v[i % step], c[2 * m][i]);
    }
    int val = 0;
    for (int i = m; i <= m + diff; i++) {
      add(val, v[i % step]);
    }
    for (int i = m + step / 2; i <= m + step / 2 + diff; i++) {
      add(val, mod - v[i % step]);
    }
    /*vector<int> dp(2 * diff + 1);
    dp[2] = 1;
    for (int i = 0; i < 2 * m; i++) {
      vector<int> ndp(2 * diff + 1);
      for (int j = 0; j < 2 * diff + 1; j++) {
        if (j) {
          add(ndp[j - 1], dp[j]);
        }
        if (j < 2 * diff) {
          add(ndp[j + 1], dp[j]);
        }
      }
      dp = ndp;
    }
    int sum = 0;
    for (int i = 0; i < 2 * diff + 1; i++) {
      add(sum, dp[i]);
    }*/
    for (int it = 0; it <= diff; it++) {
      add(cur, val);
      add(val, v[((m - it - 1) % step + step) % step]);
      add(val, mod - v[((m + diff - it) % step + step) % step]);
      add(val, mod - v[((m - it - 1 + step / 2) % step + step) % step]);
      add(val, v[((m + diff - it + step / 2) % step + step) % step]);
      if (!it) {
        //assert(sum == val);
      }
    }
    if ((diff - n) & 1) {
      add(res, mod - cur);
    } else {
      add(res, cur);
    }
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}



Measured memory_bytes: 144000
import sys
input = sys.stdin.readline

N = int(input())
d = list(map(int, input().split()))
d.sort()
if len(d)%2 == 0:
    print(d[int((N-1)/2 + 1)] - d[int((N-1)/2)])
elif len(d)%2 == 1:
    print(0)

Measured memory_bytes: 14016
N = int(input())
lst = list(map(int,input().split()))

for i in range(len(lst)):
	if i == len(lst)-1:
		break
	if lst[i+1] > lst[i]:
		lst[i+1] -= 1
	if lst[i+1] < lst[i]:
		print('No')
		exit()
print('Yes')

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

int main() {
    string N;
    cin >> N;
    rep(i, 3) {
        if (N[i] == '7') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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


int main(){
  int N,M,res_N,res_M;
  cin >> N >> M;
  if(N==0|N==1){
    res_N=0;
  }else{
    res_N=N*(N-1)/2;
  }
  
  if(M==0|M==1){
    res_M=0;
  }else{
    res_M=M*(M-1)/2;
  } 
  
  
  cout << res_N+res_M << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
   "fmt" 
)

func main() {
    var H,N,c int   
    fmt.Scan(&H)
    fmt.Scan(&N)
          
    for N >0 {
        var x int
        fmt.Scan(&x)
        c+=x
        N-=1
    }
    if c >= H{
        fmt.Print("Yes")
    }else {
        fmt.Print("No")
    }
}

Measured memory_bytes: 5504
#include <stdio.h>

int a,b,ans,n,m ;

int main(void){
    
    scanf ("%d%d",&a,&b) ;
    
    n = b-a ;
    m = (1+n)*n/2 ;
    ans = m-b ;
    
    printf ("%d",ans) ;

    return 0 ;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 
//using namespace boost::multiprecision; 
using namespace std;
#define ll long long int
#define ld long long double
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define nl '\n'
#define mp make_pair
#define debug1(x) cout <<#x<<" "<<x<<'\n';
#define debug2(x,y) cout <<#x<<" "<<x <<" "<<#y<<" "<<y <<'\n';
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<'\n';
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define inf 1e18
const int mod = (int)1e9+7;
pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};
pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};

void solve() {
	ll k,x;
	cin >> k >> x;
	if(500*k>=x){
		cout << "Yes\n";
	}
	else{
		cout << "No\n";
	}
}

signed main() {
	boost;
	solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    ll n,k;
    cin>>n>>k;
    ll sum=0;
    if(k==0) {
        cout<<n*n<<endl;
        return 0;
    } 
    for(ll b=k+1;b<=n;++b){
        sum+=n/b*(b-k);
        sum+=max(0ll,n%b-k+1);
    }
    cout<<sum<<endl;
    return 0;
}

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

int c[9]={0};

int main(void){
	int n, ans = 0;
	cin >> n;
	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		if(1<=a&&a<400) c[0]=1;
		else if(400<=a&&a<800) c[1]=1;
		else if(800<=a&&a<1200) c[2]=1;
		else if(1200<=a&&a<1600) c[3]=1;
		else if(1600<=a&&a<2000) c[4]=1;
		else if(2000<=a&&a<2400) c[5]=1;
		else if(2400<=a&&a<2800) c[6]=1;
		else if(2800<=a&&a<3200) c[7]=1;
		else if(3200<=a&&a<=4800) c[8]++;
	}
	for(int i=0; i<8; i++) ans += c[i];
	if(ans==0) cout << 1 << " " << c[8] << endl;
	else cout << ans << " " << ans+c[8] << endl;
}


Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  val N = sc.nextLong

  val z = {
    val buf = new StringBuilder
    @scala.annotation.tailrec
    def loop(n: Long): Unit = {
      buf.append(((n - 1) % 26 + 'a').toChar)
      if (n != 0) loop((n - 1) / 26)
    }
    loop(N)

    buf.reverse.toString.tail
  }
  println(z)
}


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

int main(){
  int n;
  cin>>n;
  vector<int> a,b(n);
  for(int i=0; i<n; i++) cin>>b[i];
  for(int i=n-1; i>=0; i--){
    if(b[i]==i+1) {
      a.push_back(b[i]);
      b.erase(b.begin()+i);
      i = b.size();
    }
  }
  if(b.size() != 0) {
    cout<<-1;
    return 0;
  }
  reverse(a.begin(),a.end());
  for(int i=0; i<a.size(); i++) cout<<a[i]<<endl;
}

Measured memory_bytes: 256
N=int(input())
d=list(map(int,input().split()))
list_A=[]
list_B=[]
for num3 in d:
    list_B.append(int(num3*num3))
k=sum(list_B)
for num in d:
    for num2 in d:
        list_A.append(int(num*num2))
print((sum(list_A)-k)//2)

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

int main() {
  int N;
  cin>>N;
  string s[N];
  for(int i=0;i<N;i++) cin>>s[i];
  int M;
  cin>>M;
  string t[M];
  for(int i=0;i<M;i++) cin>>t[i];
  int ans=0;
  for(int i=0;i<N;i++){
    int sum=0;
    for(int k=0;k<N;k++)
      if(s[i]==s[k]) sum++;
      for(int j=0;j<M;j++)
        if(s[i]==t[j]) sum--;
  ans=max(ans,sum);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int N,R,I;

    while ((N<1||100<N)||(R<0||4111<R))
    {
        scanf("%d %d\n",&N,&R);
    }

    if (N<10)
    {
        I=R+100*(10-N);
    }else
    {
        I=R;
    }

    printf("%d\n",I);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>

using namespace std;

int main(){
	double T,X;
	cin>>T>>X;
	cout<<T/X<<endl;
}

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

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
#define PB push_back
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int N, M;
VVI s;
VI p, k;

int solve(int si, vector<bool> &glowing_light) {
  // スイッチsiまでを決めている
  if (si == N + 1) {
    for (vector<bool>::iterator it = glowing_light.begin(); it != glowing_light.end(); ++it) {
      if (!*it)
        return 0;
    }
    return 1;
  }
  int res = 0;
  // スイッチiをオフにする = そのままにする
  res += solve(si + 1, glowing_light);
  // スイッチiをオンにする
  REP(i, M) {
    REP(j, k[i]) {
      if (s[i][j] == si)
        glowing_light[i] = !glowing_light[i];
    }
  }
  res += solve(si + 1, glowing_light);
  return res;
}
int main() {
  cin >> N >> M;

  REP(i, M){
    int _k;
    cin >> _k;
    k.PB(_k);
    VI v(k[i], 0);
    s.PB(v);
    REP(j, k[i]) {
      int _s;
      cin >> _s;
      s[i][j] = _s;
    }
  }
  REP(i, M) {
    int _p;
    cin >> _p;
    p.PB(_p);
  }
  vector<bool> glowing_light(M, false);
  REP(i, M)
    glowing_light[i] = p[i] == 0;
  cout << solve(1, glowing_light) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000000000000002
#define N 400003
#define endl "\n"
using namespace std;
ll arr[200][100000];
int main()
{

    ll s[1000][2]={0};ll n,w;cin>>n>>w;
    for(ll i=0;i<n;i++)
    {
        cin>>s[i][0]>>s[i][1];
    }
    for(ll i=0;i<=n;i++)
    {
        for(ll j=0;j<=w;j++)
        {
            if(i==0||j==0)
            {
                arr[i][j]=0;
            }
            else{
            if(s[i-1][0]<=j)
            {
                arr[i][j]=max(arr[i-1][j],s[i-1][1]+arr[i-1][j-s[i-1][0]]);
            }
            else

            {
                arr[i][j]=arr[i-1][j];
            }
            }
        }
    }
    cout<<arr[n][w]<<endl;;

    return 0;
}


Measured memory_bytes: 80128
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long power(long long a, long long b,long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a %m;
        a = a * a %m;
        b >>= 1;
    }
    return res;
}

vector<vector<int> >adj;
int vis[100005][2];
int ans[2];
int tot=0;
void dfs(int ver,int x)
{
    ans[x]++;
    vis[ver][x]=1;

    for(auto i:adj[ver])
    {
        if(vis[i][(x+1)%2]==0)
            dfs(i,(x+1)%2);
    }   
}


signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n,m;
    cin>>n>>m;
    adj.resize(n+1);
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1,0);
    tot+=ans[0]*ans[1]-m;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i][0]+vis[i][1]==2)
            res++;
    }    
    tot-=res*res;
    tot+=(res*(res-1))/2;
    cout<<tot;
    
} 
    


Measured memory_bytes: 12532
import sys
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from random import randint
d=int(input().rstrip())
c=[int(i)for i in input().split()]
s=[[int(i)for i in input().split()]for _ in range(d)]
last=[0]*26
for i in range(d):
    print(randint(1,26))

Measured memory_bytes: 9868
#include<bits/stdc++.h>
    using namespace std;
    #define inp(k)           ll k;cin>>k;
    #define in2(n,k)       ll n, k; cin>>n;cin>>k;
    #define in3(n,k,r)       ll n, k,r; cin>>n;cin>>k;cin>>r;
    #define ll long long
    #define dl double
    #define ch char
    #define f(i,a,b) for(ll i=a;i<b;i++)
    #define rf(i,a,b) for(ll i=a-1;i>=b;i--)
    #define Godspeed                ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #define vpl vector< pair<ll,ll> >
    #define vpi vector< pair<int,int> >
    #define vi vector<int>
    #define vl vector<ll>
    #define vdl vector<dl>
    #define vch vector<char>
    #define pll pair<ll,ll>
    #define pb push_back
    #define mp make_pair
    #define fr first
    #define se second
    #define PI 3.14159265
    vl v[100005];
    bool visited[100005]={0};
    ll cnt=0;
    ll dist[100005]={0};
    ll in_degree[100005];
    void dfs(ll u)
    {
        assert(!visited[u]);
        visited[u]=1;
        f(i,0,v[u].size())
        {
            ll f=v[u][i];
            dist[f]=max(dist[f],dist[u]+1);
            --in_degree[f];
            if(in_degree[f]==0)dfs(f);
        }
    }
    void solve()
    {
        in2(n,m);
        f(i,0,m)
        {
            in2(x,y);
            v[x].pb(y);
            ++in_degree[y];
        }
        f(i,1,n+1)
        {
            if(!visited[i] && in_degree[i]==0)
                dfs(i);
        }
        cout<<*max_element(dist,dist+n+1);

    }

    int32_t main(void)
    {
        Godspeed;
        int q;
        q=1;
        //cin>>q;
        while (q--)
        {
            solve();cout<<endl;
        }
        return 0;
    }


Measured memory_bytes: 15408
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int maxn = 1e5 + 3;
long long n,maxWeight;
long long dp[105][maxn], price[105], weight[105];

long long solve(int indx, long long remPrice)
{
    if(indx >= n)
    {
        if(remPrice == 0)
            return 0;
        return 1e17;
    }
    if(dp[indx][remPrice] != -1)
        return dp[indx][remPrice];
    long long ans = 1e17;
    if(remPrice - price[indx] >= 0)
        ans = min(ans, weight[indx] + solve(indx + 1,remPrice - price[indx]));
    ans = min(ans, solve(indx + 1, remPrice));
    return dp[indx][remPrice] = ans;
}
int main()
{
    IO;
    cin >> n >> maxWeight;
    for(int i = 0; i < n; i++)
        cin >> weight[i] >> price[i];
    memset(dp, -1, sizeof dp);
    for(int currPrice = 1e5; currPrice >= 0; currPrice--)
    {
        long long ans = solve(0,currPrice);
        if(maxWeight >= ans)
        {
            cout << currPrice;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 82304
N,A,B,C = map(int,input().split())
l = [int(input()) for i in range(N)]
INF = 100000000
def rec(i,a,b,c):
    if(i==N):
        return(abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else INF)
    ret0 = rec(i+1,a,b,c)
    ret1 = rec(i+1,a+l[i],b,c)+10
    ret2 = rec(i+1,a,b+l[i],c)+10
    ret3 = rec(i+1,a,b,c+l[i])+10
    return min(ret0,ret1,ret2,ret3)
print(rec(0,0,0,0))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e9;

// auto mod int
// depends on Template

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// combination mod prime
// depends on Template, Modint
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

//input
ll n;
vector<ll>a;

int main(){
    cin >> n;
    a.resize(n+1);
    combination c(1e6);
    rep(i,n+1)cin>>a[i];
    cout << n << endl;//k=1
    

    //k>=2
    vector<int>cnt(n+1);
    rep(i,n+1){
        cnt[a[i]]++;
    }
    int twi;//二回出現する数字
    rep(i,n+1){
        if(cnt[i]==2)twi=i;
    }
    int A=0,B=0;
    rep(i,n+1){
        if(a[i]!=twi)A++;
        else break;
    }
    for(int i=n;i>=0;i--){
        if(a[i]!=twi)B++;
        else break;
    }
    cout << c(n+1,2)-A-B << endl;//k=2
    for(int i=3;i<=n+1;i++){
        if(A+B<i-1)cout<<c(n+1,i) << endl;
        else cout << c(n+1,i)-c(A+B,i-1) << endl;
    }
    return 0;
}


Measured memory_bytes: 20012
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = str.length();
        char[] s = new char[n];
        for (int i = 0; i < n; i++) {
            s[i] = str.charAt(i);
        }
        
        long curACount = 0;
        long AJumpedCount = 0;
        
        for (int i = 0; i < n; i++) {
            boolean meetsA = s[i] == 'A';
            boolean canJump = i + 1 < n && s[i] == 'B' && s[i + 1] == 'C';
            
            if (meetsA) {
                curACount++;
            } else if (canJump) {
                AJumpedCount += curACount;
                i++;
            } else {
                curACount = 0;
            }
        }
        
        System.out.println(AJumpedCount);
    }
}


Measured memory_bytes: 26636
#include<iostream>
#include<vector>
#include <string>
#include <numeric>
#include<algorithm>
#include <cmath>
// #include <iterator>

using namespace std;

unsigned long numOfAttack(unsigned long power)
{
  if (power <= 1) {
    return 1;
  } else {
    return 1 + numOfAttack(power / 2) *2;
  }
}

int main()
{
  unsigned long h;
  cin >> h;

  cout << numOfAttack(h) << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int main(){
  
  int n;
  string s;
  cin>>n;
  cin>>s;
  int b[n],w[n];
  REP(i,n){
    if(i==0){
      if(s[i]=='#'){
        b[i] = 1;
      }else{
        b[i] = 0;
      }
    }else{
      if(s[i]=='#'){
        b[i] = b[i-1] + 1;
      }else{
        b[i] = b[i-1];
      }
    }
  }
  for(int i=n-1;i>=0;i--){
    if(i==n-1){
      if(s[i]=='.'){
        w[i] = 1;
      }else{
        w[i] = 0;
      }
    }else{
      if(s[i]=='.'){
        w[i] = w[i+1] + 1;
      }else{
        w[i] = w[i+1];
      }
    }
  }
  int ans=n;
  int temp;
  REP(i,n){
    if(i<n-1){
      temp = b[i] + w[i+1];
    }else{
      temp = b[i];
    }
    ans = min(ans, temp);
  }
  ans = min(ans, w[0]);
  
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    ll A[100010];
    cin >> N;
    rep(i,0,N) cin >> A[i];
    sort(A, A+N);
    ll cnt_plus = 0;
    rep(i,0,N){
        if(A[i] >= 0) cnt_plus++;
    }
    if(cnt_plus == N){
        if(N == 2){
            print(A[1] - A[0]);
            cout << A[1] << " " << A[0] << endl;
        }else{
            vector<lpair> ans;
            ll v = A[0];
            ans.push_back(make_pair(v, A[1]));
            v -= A[1];
            rep(i,2,N-1){
                ans.push_back(make_pair(v, A[i]));
                v -= A[i];
            }
            ans.push_back(make_pair(A[N-1], v));
            v = A[N-1] - v;
            print(v);
            rep(i,0,ans.size()){
                cout << ans[i].first << " " << ans[i].second << endl;
            }
        }

    }else if(cnt_plus == 0){
        sort(A, A+N, greater<ll>());
        if(N == 2){
            print(A[0] - A[1]);
            cout << A[0] << " " << A[1] << endl;
        }else{
            vector<lpair> ans;
            ll v = A[0];
            ans.push_back(make_pair(v, A[1]));
            v -= A[1];
            rep(i,2,N){
                ans.push_back(make_pair(v, A[i]));
                v -= A[i];
            }
            print(v);
            rep(i,0,ans.size()){
                cout << ans[i].first << " " << ans[i].second << endl;
            }

        }

    }else{
        vector<ll> plus, minus;
        rep(i,0,N){
            if(A[i] >= 0){
                plus.push_back(A[i]);
            }else{
                minus.push_back(A[i]);
            }
        }
        ll v = minus[0];
        vector<lpair> ans;
        rep(i,0,plus.size()-1){
            ans.push_back(make_pair(v, plus[i]));
            v -= plus[i];
        }
        ans.push_back(make_pair(plus[plus.size()-1], v));
        v = plus[plus.size()-1] - v;
        rep(i,1,minus.size()){
            ans.push_back(make_pair(v, minus[i]));
            v -= minus[i];
        }
        print(v);
        rep(i,0,ans.size()){
            cout << ans[i].first << " " << ans[i].second << endl;
        }



    }


    
}

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

int main() {
    int a,b,c,d;cin>>a>>b>>c>>d;
    while(a>0&&c>0)
    {
        c-=b;
        if(c<=0)
        {
            cout<<"Yes";
            return 0;
        }
        a-=d;
    }
    cout<<"No";
	return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x-I .)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int dy[2] = {1,0}, dx[2] = {0,1};
    int H, W;
    cin >> H >> W;
    vector<vector<char>> nap(1010, vector<char>(1010));
    vector<vector<ll>> ans(1010, vector<ll>(1010, 0));
    vector<vector<bool>> al(1010, vector<bool>(1010, false));
    REP(i,H)REP(j,W){cin >> nap[i][j];}
    queue<P> Q;
    Q.emplace(1,1);
    ans[1][1] = 1;
    while(!Q.empty()){
        int y = Q.front().first, x = Q.front().second;
        Q.pop();
        if(al[y][x])continue;
        al[y][x] = true;
        rep(i,2){
            int ny = dy[i] + y, nx = dx[i] + x;
            if(nap[ny][nx] == '.'){
                ans[ny][nx] += ans[y][x];
                ans[ny][nx] %= MOD;
                Q.emplace(ny, nx);
            }
        }
    }
    cout << ans[H][W] << endl;
    return 0;
}


Measured memory_bytes: 12856
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
from itertools import accumulate
accumulated1 = [0] + list(accumulate(A))
accumulated2 = [0] + list(accumulate(B)) + [10**10]
def check(x,now):
    if accumulated1[now] + accumulated2[x] <= K:
        return True
    else:
        return False


#[l,r)
def bisect(l,r,now):
    if r - l == 1: return  l
    mid = (r+l)//2
    if check(mid,now):
        return bisect(mid,r,now)
    else:
        return bisect(l,mid,now)


ans = 0
for i in range(N+1):
    if accumulated1[i] > K: pass
    else:
        ans = max(ans,bisect(0,M+1,i) + i)
print(ans)


Measured memory_bytes: 138692
using System;

namespace ABC_109_A_Csharp_ver
{
    class Program
    {
        static void Main(string[] args)
        {
            var word = Console.ReadLine().Split(' ');
            int A = int.Parse(word[0]);
            int B = int.Parse(word[1]);
            if (A % 2 != 0 && B % 2 != 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
            Console.ReadKey();
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vb = vector<bool>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)

int main() {

	ll q, h, s, d;
	cin >> q >> h >> s >> d;
	ll n;
	cin >> n;
	ll tl = d;
	tl = min(tl, 2 * s);
	tl = min(tl, 4 * h);
	tl = min(tl, 8 * q);

	ll ol = s;
	ol = min(ol, 2 * h);
	ol = min(ol, 4 * q);
	ll m = (n / 2) * tl + (n % 2) * ol;
	cout << m <<  endl;
}

Measured memory_bytes: 256
from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")



Measured memory_bytes: 97840
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <stack>

#define rep(i, n) for(int i=0;i<n;i++)
#define IOS() ios_base::sync_with_stdio(false)
#define ll long long
#define ull unsigned long long
#define INT_MINI -987654321
#define INT_MAXI 987654321
#define ABS(X) ((X) < 0 ? -(X) : (X))


using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

long double a, b, c;


void input() {

    cin >> a >> b >> c;
}

void process() {

    long double aa, bb, cc;
    long double eps = 1.0E-14;
    aa = sqrtl(a);
    bb = sqrtl(b);
    cc = sqrtl(c);

    /*
    printf("%.33Lf\n", sqrt(a) + sqrt(b) + eps);
    printf("%.33Lf\n", aa + bb + eps);
    printf("%.33Lf\n", cc);
    printf("%.33Lf\n", sqrt(c));
     */

    if(aa + bb + eps < cc) {
    //if(sqrt(a) + sqrt(b) + eps < sqrt(c)){
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    input();
    process();

    return 0;
}

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

//
ll dp[450][450];
ll ar[450];
ll pre[450];
//

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

	ll n; cin >> n;
	for (ll i = 0; i < n; i++)
		cin >> ar[i];
	for (ll i = 0; i < n; i++)
		pre[i + 1] = pre[i] + ar[i];

	for (ll len = 2; len <= n; len++)
	{
		ll st = 0;
		ll ed = len - 1;
		while (ed < n)
		{
			// cout << st << "," << ed << ": ";
			dp[st][ed] = 1e17;
			for (ll i = st; i < ed; i++)
			{
				// st to i
				// i + 1 to ed
				ll ans1 = dp[st][i];
				ll ans2 = dp[i + 1][ed];
				ll mix = pre[ed + 1] - pre[st];
				// cout << "[" << ans1 << "," << ans2 << "," << mix << "] ";
				dp[st][ed] = min(dp[st][ed], ans1 + ans2 + mix);
			}
			// cout << dp[st][ed] << "\n";
			st++; ed++;
		}
		// cout << "\n";
	}

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

Measured memory_bytes: 4904
S = input()
N = len(S)
W = ['p']*N
g, p = 0, 0
d = 0

last = None
w = 0
for i in range(N):
    p += 1
    if p <= g:
        if S[i] == 'g':
            w+=1
    else:
        W[i] = 'g'
        p -= 1
        g += 1
        if S[i] == 'p':
            w-=1
print(w)



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

void chmax(int& a, int b){
    a = max(a, b);
}

int main(){
    int N;
    cin >> N;
    vector<vector<int>> A;
    for(int i=0; i<N; i++){
        vector<int> v(4);
        for(int j=0; j<4; j++) cin >> v[j];
        A.push_back(v);
    }
    sort(A.begin(), A.end(), [](auto a, auto b){ return a[0]+a[3] > b[0]+b[3]; }); 
    static int dp[2001][4001][2];
    for(int i=0; i<=N; i++) for(int j=0; j<=4000; j++) for(int k=0; k<2; k++) dp[i][j][k] = -1e9;
    dp[0][4000][0] = 0;
    for(int i=0; i<N; i++){
        int r = A[i][0], a = A[i][1], w = A[i][2], t = A[i][3];
        for(int j=4000; j>0; j--) for(int k=0; k<2; k++){
            chmax(dp[i+1][j][0], dp[i][j][k]);
            int j2 = min(j-r, t);
            int v2 = dp[i][j][k] + (k ? w : a);
            if(j2 > 0) chmax(dp[i][j2][1], v2);
        }
    }
    int ans = 0;
    for(int j=1; j<=2000; j++) for(int k=0; k<2; k++) chmax(ans, dp[N][j][k]);
    cout << ans << endl;
}



Measured memory_bytes: 65824
package main

import (
	"fmt"
)

func main() {
	var N, M, C int
	_, _ = fmt.Scan(&N, &M, &C)
	B := make([]int, M)
	for m := 0; m < M; m++ {
		_, _ = fmt.Scan(&B[m])
	}
	cnt := 0
	for n := 0; n < N; n++ {
		sum := 0
		for m := 0; m < M; m++ {
			var a int
			_, _ = fmt.Scan(&a)
			sum += a * B[m]
		}
		if sum + C > 0 {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 512
// RMQ and RUQ
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INIVAL 2147483647

int *a, s, t, v, n, w, minval;

void find_min(int k, int l, int r)
{
  if (l>=n || r<=s || t<=l) return;
  if (s<=l && r<=t) {
    if (a[k]<minval)  minval = a[k];
  } else {
    if (a[((k+1)<<1)-1]>=0)  find_min(((k+1)<<1)-1, l, (l+r)>>1);
    if (a[(k+1)<<1]>=0)      find_min((k+1)<<1, (l+r)>>1, r);
    else if (a[k] < minval)  minval = a[k];
  }
}

void update_min(int k)
{
  if (k<=0) return;
  int sib = k%2 ? k+1 : k-1;
  int pp = (k-1)>>1;
  int pval = a[pp];
  a[pp] = a[k];
  if (a[pp]>a[sib])  a[pp] = a[sib];
  if (pval!=a[pp])   update_min(pp);
}

void update(int k, int l, int r)
{
  if (r<=s || t<=l) return;
  int pp, sib;
  pp = (k-1)>>1;
  int k1 = (k<<1) + 1;
  int k2 = k1 + 1;
  if (a[k] < 0) {
    if (a[pp]==v) return;
    sib = k%2 ? k+1 : k-1;
    a[k] = a[sib] = a[pp];
    if (k < w)  a[k1] = a[k2] = a[(sib<<1)+1] = a[(sib<<1)+2] = -1;
  }
  
  if (s<=l && r<=t) {
    a[k] = v;
    if (k<w)  a[k1] = a[k2] = -1;
    update_min(k);
  } else if (l<r-1) {
    update(k1, l, (l+r)>>1);
    update(k2, (l+r)>>1, r);
  }
}

int main()
{
  int i;
  char *p, buf[64] = {0};
  buf[62] = '\n';
  fgets(buf, 64, stdin);
  for (n=0,p=buf; *p>' '; n=n*10+*(p++)-'0');
  w = n>1 ? pow(2,(int)ceil(log2(n)))-1 : 0;

  a = (int*)malloc(sizeof(int)*(w+n));
  for (i=0; i<w+n; i++)  a[i] = INIVAL;
  
  while (fgets(buf, 64, stdin)) {
    for (s=0,p=buf+2; *p>' '; s=s*10+*(p++)-'0');
    for (t=0,p++; *p>' '; t=t*10+*(p++)-'0');
    t++;
    if (*buf=='0') { // update(s, t, x)
      for (v=0,p++; *p>' '; v=v*10+*(p++)-'0');
      update(0, 0, w+1);
    } else { // find(s, t)
      minval = INIVAL;
      find_min(0, 0, w+1);
      if (minval<10) {
	putc_unlocked('0'+minval, stdout);
	putc_unlocked('\n', stdout);
      } else {
	for (i=62; minval>0; buf[--i]='0'+minval%10,minval/=10);
	fputs(buf+i, stdout);
      }
    }
  }
  return 0;
}



Measured memory_bytes: 2808
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  // ll n;
  // cin >> n;
  // ll n, m;
  // cin >> n >> m;
  ll n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  char arr[n];
  fi(0, n) {
    cin >> arr[i];
  }

  if(c == d) {
    cout << "No\n";
    return 0;
  }
  else {
    fi(b + 1, d - 1) {
      if(arr[i - 1] == '#' && arr[i] == '#') {
        cout << "No\n";
        return 0;
      }
    }
    fi(a + 1, c - 1) {
      if(arr[i - 1] == '#' && arr[i] == '#') {
        cout << "No\n";
        return 0;
      }
    }
    if(c > d && ((arr[b] == '#' || arr[b - 2] == '#') && (arr[d] == '#' || arr[d - 2] == '#'))) {
      int ok = 0;
      fi(b - 1, d - 2) {
        if(arr[i] == '.' && arr[i + 1] == '.' && arr[i + 2] == '.') {
          ok = 1;
          break;
        }
      }
      if(!ok) {
        cout << "No\n";
        return 0;
      }
    }
  }
  
  cout << "Yes\n";
  // cout << ans << endl;
  return 0;
}



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

using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
constexpr int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p){os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N;
    cin >> N;
    N--;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    const int INF = 10000 * 10001 + 1;

    vector<vector<vector<int>>> dp(2, vector<vector<int>>(N + 2, vector<int>(2, INF)));
    dp[0][0][0] = 0;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= N + 1; j++) {
            for(int k = 0; k < 2; k++) {
                for(int l = 0; l < 2; l++) {
                    if (l == 1 && j + l > N + 1) continue;
                    dp[(i + 1) % 2][j + l][l] = min(dp[(i + 1) % 2][j + l][l], dp[i % 2][j][k] + (k != l ? A[i] : 0));
                }
            }
        }
        for(int j = 0; j <= N + 1; j++) {
            for(int k = 0; k < 2; k++) {
                dp[i % 2][j][k] = INF;
            }
        }
    }

    cout << min(dp[N % 2][(N + 1) / 2][0], dp[N % 2][(N + 1) / 2][1]) << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

namespace A
{
    public class Program

    {
        public static void Main(string[] args)
        {
            int day = ReadInt();
            switch (day)
            {
                case 25:
                    Console.WriteLine("Christmas");
                    break;
                case 24:
                    Console.WriteLine("Christmas Eve");
                    break;
                case 23:
                    Console.WriteLine("Christmas Eve Eve");
                    break;
                case 22:
                    Console.WriteLine("Christmas Eve Eve Eve");
                    break;
            }
        }

        static string ReadSt() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static long ReadLong() { return long.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static string[] ReadStAr(char sep = ' ') { return Console.ReadLine().Split(sep); }
        static int[] ReadIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
        static long[] ReadLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
        static double[] ReadDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }

    }

}


Measured memory_bytes: 11092
#include<iostream>
#include<cstdio>
#include<cstring>

#define EXIT puts("No"),exit(0)

using namespace std;

int n,x[100001][3],rnk[100001],sumv[100001],pos[100001],sta[100001],rev[2][2];

inline int get(int x){return (x+2)/3;}

inline int lowbit(int x){return x&-x;}

inline void update(int k,int x){for(int i=k;i>0;i-=lowbit(i))sumv[i]+=x;}

inline int query(int k){int s=0;for(int i=k;i<=n;i+=lowbit(i))s+=sumv[i];return s;}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){scanf("%d",&x[i][0]),pos[rnk[i]=get(x[i][0])]=i,(rev[0][i&1]+=(x[i][0]+1)%3)&=1;if((rnk[i]&1)!=(i&1))EXIT;}
	for(int k=1;k<=2;++k)for(int i=1;i<=n;++i){scanf("%d",&x[i][k]);if(get(x[i][k])!=rnk[i]||abs(x[i][k-1]-x[i][k])!=1)EXIT;}
	for(int i=1;i<=n;i+=2){int t=pos[i]+(query(pos[i])<<1);(rev[1][0]+=abs(t-i)>>1)&=1;update(pos[i],1);}
	memset(sumv,0,sizeof(sumv));
	for(int i=2;i<=n;i+=2){int t=pos[i]+(query(pos[i])<<1);(rev[1][1]+=abs(t-i)>>1)&=1;update(pos[i],1);}
	puts(rev[0][0]==rev[1][0]&&rev[0][1]==rev[1][1]?"Yes":"No");
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	cin >> s;
	if(s.find("AC") != string::npos) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 768
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}

int main(){
  int m,d;
  cin>>m>>d;
  int ans=0;
  for(int i=1;i<=m;i++){
for(int j=22;j<=d;j++){
  int d1=j/10;
  int d2=j-d1*10;
  if(d1<2||d2<2)continue;
  if(d1*d2==i)ans++;
}
 }
 cout<<ans<<endl;
}




Measured memory_bytes: 256
import scala.io.{StdIn => in}

object Main extends App {
  val Array(h, w, d) = in.readLine.split(" ").map(_.toInt)
  case class Point(x:Int, y:Int) {
    def manhattan(that: Point): Int = {
      (that.x - this.x).abs + (that.y - this.y).abs
    }
  }
  val table = Array.ofDim[Point](h*w+1)
  val grid = Iterator.continually(in.readLine)
    .take(h)
    .map(_.split(" ").map(_.toInt))
    .toArray
  
  for{
    i <- 0 until h
    j <- 0 until w
  } table(grid(i)(j)) = new Point(y = i, x = j)

  val acc = Array.ofDim[Int](h*w+1)
  for(i <- 1 to h*w-d) {
    acc(i+d) = acc(i) + (table(i+d) manhattan table(i))
  }

  val out = new java.io.PrintWriter(System.out)
  val q = in.readInt
  Iterator.continually(in.readLine)
    .take(q)
    .map(_.split(" ")map(_.toInt))
    .foreach (e => {
      val l = e(0)
      var r = e(1)
      out.println(acc(r) - acc(l))
    })
  out.flush
}

Measured memory_bytes: 54764
#include <stdio.h>


int main(){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a>=b&&b>=c){printf("%d",a-c);}
	else if(a>=c&&c>=b){printf("%d",a-b);}
	else if(b>=c&&c>=a){printf("%d",b-a);}
	else if(b>=a&&a>=c){printf("%d",b-c);}
	else if(c>=b&&b>=a){printf("%d",c-a);}
	else if(c>=a&&a>=b){printf("%d",c-b);}
	else 
	
	return 0;
}


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

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

int p[200],q[50],dp1[1000000],dp2[1000000],n;

int main(){
	rep(i,200)p[i]=(i+1)*(i+2)*(i+3)/6;
	rep(i,50)q[i]=(4*i+1)*(4*i+2)*(4*i+3)/6;
	for(int i=1;i<1e6;i++){
		dp1[i]=dp2[i]=INF;
		rep(j,200)if(p[j]<=i)dp1[i]=min(dp1[i],dp1[i-p[j]]+1);
		rep(j,50)if(q[j]<=i)dp2[i]=min(dp2[i],dp2[i-q[j]]+1);
	}
	while(cin>>n&&n){
		cout<<dp1[n]<<" "<<dp2[n]<<endl;
	}
}

Measured memory_bytes: 8516
import java.util.*;

class Main {
	Scanner sc = new Scanner(System.in);
	public void run() {
		while(sc.hasNext()){
			boolean[] odd=new boolean[101];
			while(true){
				int f=sc.nextInt(),t=sc.nextInt();
				if(f==0 && t==0) break;
				odd[f]=!odd[f];
				odd[t]=!odd[t];
			}
			boolean ok=true;
			ok&=odd[1]&&odd[2];
			for(int i=3;i<=100;i++){
				ok&=!odd[i];
			}
			ln(ok?"OK":"NG");
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

Measured memory_bytes: 12000
fun main(args: Array<String>){
    val N = readLine()!!.toLong()
    var ans = 0L


    fun dfs(s:Long){
        if(s> N){return }
        if(s.toString().contains("7") && s.toString().contains("5") && s.toString().contains("3")){
            ans++
        }
        dfs(s*10+3)
        dfs(s*10+5)
        dfs(s*10+7)
    }
    dfs(0)
    println(ans)
}


Measured memory_bytes: 43776