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

using namespace std;

#define frei(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define fred(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define fri(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define frd(i,n) for (int i = (n) - 1; i >= 0; i--)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )

#define uint64 unsigned long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define pr pair

#define BIT(n) (1<<(n))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define sqr(x) ((x) * (x))

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<pii> vii;
typedef vector<int> vi;

#define PI 3.1415926535897932385
#define INF 1000111222
#define eps 1e-7
#define maxN 5005



int main(int argc, char const *argv[])
{
    /* code */
    int n, m;
    int mod = 1e9+7;
    cin >> n >> m;
    int a[n+1][m+1];
    char ch;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> ch;
            if(ch == '.') {
                a[i][j] = 0;
            } else {
                a[i][j] = -1;
            }
        }
    }
    a[1][1] = 1;
    for(int i = 2; i <= m; i++) {
        if(a[1][i] >= 0) {
            a[1][i] = a[1][i-1] > 0 ? 1 : 0;
        }
    }
    for(int i = 2; i <= n; i++) {
        if(a[i][1] >= 0) {
            a[i][1] = a[i-1][1]> 0 ? 1 : 0;
        }
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 2; j <= m; j++) {
            if(a[i][j] >= 0) {
                a[i][j] = ((a[i-1][j] > 0 ? a[i-1][j] : 0)%mod + (a[i][j-1] > 0 ? a[i][j-1] : 0)%mod)%mod;
                //cout << a[i][j] << endl;
            }
        }
    }
    cout << a[n][m] << endl;
    return 0;
}


Measured memory_bytes: 4096
def insert(array, index):
    value = array[index]
    for i in range(index - 1, -1, -1):
        if array[i] < value:
            array[i+1] = value
            break
        array[i + 1] = array[i]
    else:
        array[0] = value

def insertion_sort(array, log=False):
    for i in range(len(array)):
        insert(array, i)
        if log:
            print(*array)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    insertion_sort(A, True)

Measured memory_bytes: 8140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n,m;
  cin >> n >> m;
  long long sum = 0;
  for(int i = 0; i < m; i++){
    long long t = 0;
    cin >> t;
    sum += t;
  }
  long long ans = n - sum;
  if(ans >= 0){
    cout << ans;
  }else{
    cout << -1;
  }
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    string S;
    cin >> S;
    int ans = 1000000000;
    rep(i, S.size() - 2) {
        string str = "";
        rep(j, 3) str += S[i + j];
        int x = stoi(str);
        ans = min(abs(753 - x), ans);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
#include<math.h>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
	int N; cin >> N;
    vector<ll> A(N+1),B(N);
    rep(i,N+1) cin >> A[i];
    rep(i,N) cin >> B[i];
    ll ans = 0;
    rep(i,N){
        if(A[i] >= B[i]) ans += B[i];
        else{
            ans += A[i];
            ll d = B[i] - A[i];
            if(A[i+1] >= d){
                ans += d;
                A[i+1] -= d;
            }
            else{
                ans += A[i+1];
                A[i+1] = 0;
            }

        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

vi adj[200001];
int d[200001];

void dfs(int x, int p, int s)
{
    for (int y : adj[x])
    {
        if (y == p) continue;
        dfs(y, x, s + d[x]);
    }
    d[x] += s;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    while (q--)
    {
        int p, x;
        cin >> p >> x;
        d[p] += x;
    }
    dfs(1, -1, 0);
    for (int i = 1; i <= n; ++i)
        cout << d[i] << ' ';
}


Measured memory_bytes: 26624
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = 0; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
  ll n;
  cin >> n;
  vector<ll> vec(n + 1);
  for (int i = 0; i < n + 1; i++) {
    if (i == 0) {
      vec.at(i) = 2;
    } else if (i == 1) {
      vec.at(i) = 1;
    } else {
      vec.at(i) = vec.at(i - 1) + vec.at(i - 2);
    }
  }
  cout << vec.at(n) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 1000001;
const int MOD = 1000000007;
   
        signed main() {
           int n,d,a;
           cin>>n>>d>>a;
           pair<int,int> p[n];
           int x,h;
           for(int i=0;i<n;i++){
               cin>>x>>h;
               p[i]=make_pair(x,(h-1)/a +1);
           }
           sort(p,p+n);
           int ans[n]={},k=0,j=0;
           for(int i=0;i<n;i++){
               while(p[j].first<p[i].first-2*d){
                   k-=ans[j];
                   j++;
               }
               ans[i]=max(0ll,p[i].second-k);
               k+=ans[i];
           }
           int ans2=0;for(int i=0;i<n;i++)ans2+=ans[i];
           cout<<ans2;


           return 0;

        }


Measured memory_bytes: 4992
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int n,m,a[55]={},b[55]={},par[100005]={},ans=0;
int find(int x) {
  if(par[x]==x) {
    return x;
  }
  return par[x]=find(par[x]);
}
bool same(int x,int y) {
  return par[x]==par[y];
}
void unit(int x,int y) {
  x=find(x),y=find(y);
  if(x!=y) {
    par[x]=y;
  }
}
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    par[i]=i;
  }
  for(int i=0; i<m; i++) {
    cin >> a[i] >> b[i];
    a[i]--,b[i]--;
  }
  for(int i=0; i<m; i++) {
    set<int> s;
    for(int i=0; i<n; i++) {
      par[i]=i;
    }
    for(int j=0; j<m; j++) {
      if(i!=j) {
        unit(a[j],b[j]);
      }
    }
    for(int i=0; i<n; i++) {
      s.insert(find(i));
    }
    if(s.size()!=1) {
      ans++;
    }
  }
  cout << ans << endl;
}



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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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 (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

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

    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    map<ll, ll> mp;
    REP(i, N) mp[-A[i]]++;
    REP(i, M){
    	ll B, C;
    	cin >> B >> C;
    	mp[-C] += B;
    }

    ll res = 0;
    ll noko = N;
    for(auto x: mp){
    	ll toru = min(noko, x.second);
    	noko -= toru;
    	res += toru*x.first;
    }
    cout << -res << endl;
    return 0;
}

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

typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int h,a;
    cin >> h >> a;
    int k = h/a;
    if(k*a < h) ++k;
    cout << k << endl;
    return 0;
}

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

int main(){
  int n, l;
  cin >> n >> l;
  vector<string> s(n);
  for(int i = 0; i < n; i++) cin >> s[i];
  sort(s.begin(), s.end());
  for(int i = 0; i < n; i++){
    cout << s[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
 
using namespace std;
 
signed main()
{
    fast;
    int n;
    cin>>n;

    vector<int> a(n);

    for ( int i = 0 ; i < a.size() ; i++ )
    {
        cin>>a[i];
    }

    int count = 1;

    int x = a[0];

    for ( int i = 1 ; i < a.size() ; i++ )
    {
        if ( x > a[i] )
        {
            count++;
        }
        x = min(x,a[i]);
    }

    cout<<count<<endl;
    
    return 0;
}

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

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

#define FOR(i, b, e) for(int i=(b);i<(e);i++)
#define REP(i, n) FOR(i,0,n)

#define ALL(v) (v).begin(),(v).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000007;
const int INF = 1e9;

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

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

double a, b, x;

int main() {
    cin >> a >> b >> x;
    printf("%.10lf\n",
        atan(
            (a * a * b <= 2 * x)
                ? 2 / a * (b - x / a / a)
                : a * b * b / 2 / x
        ) * 180.0 / PI
    );
    return 0;
}


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

using namespace std;
typedef long long ll;

int main(){
    string s[3];
    for (int i = 0; i < 3; i++)
    {
        cin >> s[i];
    }

    cout << 'A' << char(s[1][0]) << 'C' << endl;
    
    
}

Measured memory_bytes: 256
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
ll n,m;
int main() {
	read(n);read(m);
	ll tmp=m/n,ans=0;
	while(tmp) {
		tmp>>=1;
		ans++;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 256
mod = 1000000007
eps = 10**-9
 
 
def main():
    import sys
    input = sys.stdin.buffer.readline
    
    #by tamatoさん
    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)
 
        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
 
        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)
 
        # return smallest i(l <= i < r) s.t. check(A[i]) == True
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1
 
    def check(val):
        return val >= v

    n,q = map(int,input().split())
    morty = list(map(int,input().split()))
    stree = SegmentTree(morty,segfunc=max,ident=-2000000000)

    for _ in range(q):
        t,x,v = map(int,input().split())
        if t == 1:
            stree.update(x, v)
        elif t==2:
            print(stree.query(x,v+1))
        else:
            print(stree.binsearch(x,n+1, check))
if __name__ == '__main__':
    main()


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

// ABC071B - Not Found
int main(){
  string s;
  cin >> s;

  char bucket[26] = {0};
  std::for_each(s.begin(), s.end(), [&bucket](char c){
    ++bucket[c - 'a'];
  });
  for (int i = 0; i < 26; ++i) {
    if (bucket[i] == 0) {
      cout << char('a' + i) << endl;
      return 0;
    }
  }

  cout << "None" << endl;
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,y,k,s,g,m,f=0;
  cin>>n>>y;
  for(int i=0;10000*i<=y;i++){
    for(int j=0;10000*i+5000*j<=y;j++){
      k=n-i-j;
      if(10000*i+5000*j+1000*k==y){s=k;g=j;m=i;f=1;break;}
    }
  }
  if(f){cout<<m<<' '<<g<<' '<<s;}
  else{cout<<-1<<' '<<-1<<' '<<-1;}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define print(v) cout<<v<<endl;
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

ll F(ll x){
    if(x<=0)return 1;
    if(x==1)return 2;
    if(x==2)return 3;
    if(x==3)return 5;
    if(x==4)return 8;
    if(x==5)return 13;
    if(x==6)return 21;
    if(x==7)return 34;
    if(x==8)return 55;
}


int main(){
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    vector<ll> X(M,0);
    for(ll i=0;i<M;i++)cin>>X[i];
    sort(X.begin(), X.end());
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for(ll i=0;i<M-1;i++){
        pq.emplace(X[i+1]-X[i]);
    }
    ll ans=0;
    for(ll i=0;i<M-N;i++){
        ans+=pq.top();
        pq.pop();
    }
    print(ans)
    return 0;
}

Measured memory_bytes: 2296
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;++i)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;

int main(){
    int n;cin>>n;
    char s;bool flag=false;
    fol(i,n){
        cin>>s;
        if(s=='Y') flag=true;
    }
    if(flag)cout << "Four"<<endl;
    else cout << "Three" <<endl;
    return 0;
}


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

#define pb push_back
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pii pair<int,int>

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;

int main(){
    ll a;
    cin >> a;
    for (ll i = -1000 ; i <= 1000 ; i++) {
        for (ll j = -1000 ; j <= 1000 ; j++) {
            ll p1 = pow(i,5);
            ll p2 = pow(j,5);
            if (p1 - p2 == a) {
                cout << i <<' '<<j << '\n';
                exit(0);
            }
        }
    }
}

Measured memory_bytes: 4100
from collections import Counter
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  c = Counter(A)
  B = [k for k,v in c.items() if v>=2]
  C = [k for k,v in c.items() if v>=4]
  B.extend(C)
  B.sort(reverse=True)
  if len(B)<2:
    return 0
  ans = B[0]*B[1]
  return ans
print(solve())

Measured memory_bytes: 22020
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
	int i;
	int n;
	while(scanf("%d",&n),n){
		int y;
		scanf("%d",&y);
		double mx=0;
		int my;
		for(i=0;i<n;++i){
			int p,q,r;
			scanf("%d%d%d",&p,&q,&r);
			if((r==1?y*q/100.+1:pow(q/100.+1,y))>mx){
				mx=r==1?y*q/100.+1:pow(q/100.+1,y);
				my=p;
			}
		}
		printf("%d\n",my);
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int red = 0;
  int blue = 0;
  for(int i=0; i<S.size(); i++){
    if(S.at(i) == '0'){
      red++;
    }
    else{
      blue++;
    }
  }
  cout << min(red,blue)*2 << endl;
}

Measured memory_bytes: 512
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] P = new int[M];
		int[] Y = new int[M];
		HashMap<Integer,TreeMap<Integer,Integer>> localGovernment = new  HashMap<>();
		String[] ans = new String[M];
		
		for (int i = 0; i < M; i++) {
			P[i] = sc.nextInt();
			Y[i] = sc.nextInt();
			localGovernment.computeIfAbsent(P[i], key -> new TreeMap<>()).put(Y[i], i);
		}
		
		localGovernment.forEach((k,v) -> {
			int i = 1; 
			for(Entry<Integer,Integer> tree : v.entrySet()) {
				ans[tree.getValue()] = String.format("%06d%06d", k, i++);
			}
		});
		
		Arrays.stream(ans).forEach(System.out::println);

		sc.close();
	}


}


Measured memory_bytes: 186460
import java.util.*;
import java.io.*;
import java.lang.Math.*;

class Main{

    static double[][] dp = new double[3001][1502];
    static double[] mData = new double[3001];    
    static int N;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in).useLocale(Locale.US);

        N = sc.nextInt();
        for(int i = 0; i < N; i++){
            mData[i+1] = sc.nextDouble();
        }
        
        int Npola = N/2 + 1;

        dp[1][0] = 1;
        dp[1][1] = mData[1];
        for(int i = 2; i < Npola; i++){
            dp[1][i] = 0;
        }

        for(int i = 2; i <= N; i++){
            dp[i][0] = 1;            
            for(int j = 1; j < 1502; j++){
                dp[i][j] = ( mData[i]*dp[i-1][j-1] + (1-mData[i])*dp[i-1][j] ); 
                //System.out.println( dp[i][j] );
            }
        }
    /*
        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= N; j++){
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    */
        System.out.println( dp[N][N/2 + 1] );
        sc.close();
    }
}

















Measured memory_bytes: 87828
n,a,b,c = map(int,input().split())
L = [int(input()) for i in range(n)]
MP = []
for i in range(4**n):
    i_bit = bin(i)[2:].zfill(2*n)
    co_a = 0
    co_b = 0
    co_c = 0
    p_a = 0
    p_b = 0
    p_c = 0
    for j in range(n):
        if i_bit[-1-2*j:-3-2*j:-1] == '00':
            co_a += L[j]
            p_a += 1
        elif i_bit[-1-2*j:-3-2*j:-1] == '01':
            co_b += L[j]
            p_b += 1
        elif i_bit[-1-2*j:-3-2*j:-1] == '10':
            co_c += L[j]
            p_c += 1
        else:
            continue
    if co_a*co_b*co_c!=0 and p_a<=a and p_b<=b and p_c<=c:
        MP += [10*(p_a+p_b+p_c-3)+abs(a-co_a)+abs(b-co_b)+abs(c-co_c)]
print(min(MP))

Measured memory_bytes: 5012
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int X = scan.nextInt();
        if (X % 7 == 0) {
            System.out.println("thu");
        } else if (X % 7 == 1) {
            System.out.println("fri");
        } else if (X % 7 == 2) {
            System.out.println("sat");
        } else if (X % 7 == 3) {
            System.out.println("sun");
        } else if (X % 7 == 4) {
            System.out.println("mon");
        } else if (X % 7 == 5) {
            System.out.println("tue");
        } else if (X % 7 == 6) {
            System.out.println("wed");

        }
    }
}



Measured memory_bytes: 26332
import java.util.Scanner;

public class Main {

	public static void main (String[] args)  {

		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		System.out.println(s.charAt(0)==s.charAt(1) && s.charAt(1)==s.charAt(2) ? "No" : "Yes");


	}




}


Measured memory_bytes: 21844
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main() {
    ll x;
    cin >> x;

    ll cur = 100;
    int ans = 0;
    while(cur < x) {
        ans++;
        cur += cur / 100;
    }

    cout << ans << endl;
    return 0;
}


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

int main() {
  int k,cnt;
  string s;
  cin >> s;
  k = s.size();
  cnt=0;
  for(int i=0;i<k;i++){
    if(s.at(i) == 'o'){
      cnt++;
    }
  }
  
  if((15-k) + cnt >= 8){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
int main(void) {
	char str[81];
	int count = 0,length,i,j=0,k=0;

	while (scanf("%s",str) != EOF)
	{
		length = strlen(str);
		for (i = length - 1; i >= 0; i--) {
			if (isdigit(str[i])) {
				j = 0;
				k = 0;
				while (1) {
					if (isdigit(str[i - j])) {
						count += (str[i - j]-'0') * (pow(10, j));
						k++;
					}
					else {
						i -= k;
						break;
					}
					j++;
				}
			}
		}
	}
	printf("%d\n",count);

	return 0;
}

Measured memory_bytes: 580
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();//14
	int d = sc.nextInt();//3
    int result = 0;
    
    if(n == 1 || n == 2){
      System.out.println(1);
    }else{
    for(int i = 0;i < n;i++){
      if((2*d+1)*i >= n){
        result = i;
        break;
      }
    }
    System.out.println(result);
    }
  }
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
#define all(v) v.begin(),v.end()
#define all(v) v.begin(),v.end()
#define endl "\n"
#define clr(n, r) memset(n,r,sizeof(n))
typedef bitset<13> MASK;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<vector<int>> vvi;

//set iterator can be increamnted and decreamnted
void fast() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}

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

int main() {
    fast();
    //    freopen("input.txt","r",stdin);
    //    freopen("out.txt","w",stdout);
    ll n, x, m;
    cin >> n >> x >> m;
    ll total = 0;
    ll arr[2 * m + 1];
    clr(arr, 0);
    arr[0] = x;
    int i = 1, s;
    bool b = 0;
    map<ll, int> freq;
    for (i = 1; i < m; ++i) {

        arr[i] = binpow(arr[i - 1], 2, m);
        if (freq[arr[i]]) {
            s = freq[arr[i]];
            break;
        }
        freq[arr[i]] = i;
    }
    if (n <= i) {
        ll t = 0;
        for (int j = 0; j < n; ++j) {
            t += arr[j];
        }
        cout << t;
    } else {

        ll t = 0;
        for (int j = 0; j < i; ++j) {
            t += arr[j];
        }
        ll now = 0;
        for (int j = s; j < i; ++j) {
            now += arr[j];
        }
        n -= i;

        if(i-s>0) {
            ll r = n / (i - s);
            t += (r) * now;


            for (int k = s; k < s + n % (i - s); ++k) {
                t += arr[k];
            }
        }
        cout << t;
    }

}

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

int a[101];
int main(){
  int n,m,x;
  int right=0,left=0;
  cin>>n>>m>>x;
  for(int i=0;i<m;i++){
    int temp; cin>>temp;
    a[temp]=1;
  }
  for(int i=x;i<n;i++){
    if(a[i]==1) right++;
  }
  for(int i=0;i<x;i++){
    if(a[i]==1) left++;
  }
  cout<<min(right,left)<<"\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N,L;
string S[100];
main(){
  cin>>N>>L;
  for(int i=0;i<N;++i)cin>>S[i];
  sort(S,S+N);
  for(int i=0;i<N;++i)cout<<S[i];
  cout<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }


i64 N;
vector<i64> A;

int main() {
  cin >> N;
  A.resize(N);
  rep(i,0,N) {
    cin >> A[i];
  }
  vector<vector<i64>> res(N + 1, vector<i64>(2, -1e18));
  res[0][0] = 0;
  res[1][0] = A[0];
  res[2][1] = A[1];
  rep(i,2,N) {
    res[i + 1][0] = std::max(res[i + 1][0], res[i - 1][0] + A[i]);
    res[i + 1][1] = std::max(res[i + 1][1], res[i - 1][1] + A[i]);
    res[i + 1][1] = std::max(res[i + 1][1], res[i - 2][0] + A[i]);
  }
  if(N % 2 == 0) {
    cout << std::max(res[N][1], res[N - 1][0]) << endl;
    return 0;
  }
  std::vector<i64> dp(N, -1e18);
  dp[0] = std::max(A[0], 0ll);
  for(i64 i = 2; i < N; i += 2) {
    dp[i] = std::max(dp[i - 2] + A[i], std::max(res[i][1], res[i - 1][0]));
  }
  std::cout << dp[N - 1] << std::endl;
}


Measured memory_bytes: 17260
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

char C[3000010];

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


	fread(C, 1, 3000010, stdin);
	char* ci = C, c;
	int N = 0;
	while ((c = *ci++) >= '0') N = N * 10 + c - '0';

	int D[10];
	int d = 1;
	for (int i = 9; i >= 0; i--) {
		D[i] = d;
		d *= 10;
	}
	ll p[20][20] = {};
	rep(i, N) {
		ll kari = 0;
		while ((c = *ci++) >= '0') kari = kari * 10 + c - '0';
		d = 0;
		if (*(ci - 1) == '.') {
			while ((c = *ci++) >= '0') {
				kari = kari * 10 + c - '0';
				d++;
			}
		}
		kari *= D[d];

		int a = __builtin_ctzll(kari);
		if (a > 18) a = 18;
		int b = 0;
		while (kari % 5 == 0) {
			b++;
			kari /= 5;
		}
		p[a][b]++;
	}
	ll kotae = 0;
	rep(a, 19) rep(b, 19) if (p[a][b]) {
		ll P = p[a][b];
		for (int x = 18 - a; x <= 18; x++) {
			for (int y = 18 - b; y <= 18; y++) {
				kotae += P * p[x][y];
			}
		}
	}
	for (int a = 9; a <= 18; a++) {
		for (int b = 9; b <= 18; b++) {
			kotae -= p[a][b];
		}
	}

	printf("%lld\n", kotae / 2);

	Would you please return 0;
}

Measured memory_bytes: 4188
#include <stdio.h>
#include <stdlib.h>
typedef struct data *node;
struct data
{
  int key;
  node par;
  node left;
  node right;
};

node root,NIL;
void insert(int k)
{
  node y=NIL;
  node x=root;
  node z;

  z=(node)malloc(sizeof(struct data));
  z->key=k;
  z->left=NIL;
  z->right=NIL;


  while(x!=NIL)
  {
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->par=y;
  if(y==NIL)root=z;
  else
  {
    if(z->key<y->key)y->left=z;
    else y->right=z;
  }
}
void InOrder(node u)
{
  if(u==NIL) return;//,
  InOrder(u->left);
  printf(" %d",u->key);
  InOrder(u->right);
}
void Preorder(node u)
{
  if(u==NIL)return;
  printf(" %d",u->key);
  Preorder(u->left);
  Preorder(u->right);
}
node find(node x,int k)
{
  while(x!=NIL&&k!=x->key)
  {
    if(k<x->key)x=x->left;
    else x=x->right;
  }
  return x;
}
int main()
{
  int n,i,x;
  char str[10];
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s",str);
    if(str[0]=='f')
    {
      scanf("%d",&x);
      node t=find(root,x);
      if(t!=NIL)printf("yes\n");
      else printf("no\n");
    }
    if(str[0]=='i')
    {
      scanf("%d",&x);
      insert(x);
    }
    else if(str[0]=='p')
    {

      InOrder(root);
      printf("\n");
      Preorder(root);
      printf("\n");

    }
  }
  return 0;
}



Measured memory_bytes: 20472
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;


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


void solve(){
	long double a,b;
	cin >> a >> b;
	long double ans = floor(a*b);
	cout << fixed  << setprecision(0) << ans << endl;
}

int main(){
	fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output1.txt","w",stdout);
	#endif

	// int t;cin >> t;while(t--)
		solve();
}


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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll N;
    cin >> N;

    ll count=0;
    REP(i,N){
       ll n;
       cin >> n;
       if( n != (i+1) ){
            count++;
       }
    }

    cout << ((count <= 2) ? "YES":"NO") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int H, W;
	cin >> H >> W;

	auto func = [](ll h, ll w, ll s1)
	{
		auto midH = h / 2;
		auto midW = w / 2;

		auto s2 = midH * w;
		auto s3 = (h - midH) * w;
		auto maxS = max(s1, max(s2, s3));
		auto minS = min(s1, min(s2, s3));
		auto result = maxS - minS;

		s2 = h * midW;
		s3 = h * (w - midW);
		maxS = max(s1, max(s2, s3));
		minS = min(s1, min(s2, s3));
		result = min(result, maxS - minS);
		return result;
	};

	auto ans = LLONG_MAX;
	for (auto i = 1; i < H; ++i)
	{
		auto s1 = (ll)i * W;
		auto temp = func(H - i, W, s1);
		ans = min(ans, temp);
	}
	for (auto i = 1; i < W; ++i)
	{
		auto s1 = (ll)i * H;
		auto temp = func(H, W - i, s1);
		ans = min(ans, temp);
	}

	cout << ans << endl;

	return 0;
}

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

vector<vector<bool>> make_fill_vec(int n) {
  if (n == 1)
    return {{true}, {false}};
  vector<vector<bool>> re;
  for (vector<bool> b:make_fill_vec(n-1)) {
    vector<bool> t = {true};
    vector<bool> f = {false};
    t.insert(t.end(),b.begin(), b.end());
    f.insert(f.end(),b.begin(), b.end());
    re.push_back(t);
    re.push_back(f);
  }
  return re;
}

int main() {
  int d,g;
  cin >> d >> g;
  vector<int> qnum(d);
  vector<int> bonus(d);
  for(int i=0;i<d;i++){
    cin >> qnum.at(i) >> bonus.at(i);
  }
  
  
  int minc = g;
  for(auto a:make_fill_vec(d)){
    vector<int> ansnum(d,0);
    for(int i=0;i<d;i++){
      if (a.at(i))
        ansnum.at(i) = qnum.at(i);
    }
    int total = 0;
    int count = 0;
    for(int i=0;i<d;i++){
      if(a.at(i)){
        total += qnum.at(i)*(i+1)*100 + bonus.at(i);
        count += qnum.at(i);
        if(total>=g)
          break;
      }
    }
    if(total>=g){
      minc = min(minc,count);
      continue;
    }
    
    for(;;){
      for(int i=d-1; i>=0; i--){
        if(!a.at(i)) {
          total += (i+1)*100;
          count++;
          ansnum.at(i)++;
          if(ansnum.at(i)==qnum.at(i)){
            total += bonus.at(i);
            a.at(i) = true;
          }
          break;
        }
      }
      if(total>=g)
        break;
    }
    minc = min(minc, count) ;
    
  }
  cout << minc << endl;
  
  return 0;
}
         
  
      

Measured memory_bytes: 384
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int height[n+1];
	for(int i=0; i<n; i++)
	{
		cin>>height[i];
	}
	vector<int> dp(n+2, 1e9);
	dp[0]=0;
	for(int i=0; i<=n; i++)
	{
		for(int j : {i+1,i+2})
		{
			if(j<n)
			{
				dp[j] = min(dp[j] , dp[i] + abs(height[i] - height[j]));
			}
		}
	}
	cout<<dp[n-1];
	
}


Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(50) << setiosflags(ios::fixed);
  ll a, b;
  cin >> a >> b;
  cout << static_cast<bitset<32>>(a & b) << endl;
  cout << static_cast<bitset<32>>(a | b) << endl;
  cout << static_cast<bitset<32>>(a ^ b) << endl;
  return 0;
}



Measured memory_bytes: 3228
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
int N, K, d[1001], A[1001], num[1001], ans;
int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1;i<=K;i++)
	{
		scanf("%d", &d[i]);
		for(int j=1;j<=d[i];j++)
		{
			scanf("%d", &A[j]);
			num[A[j]]++;
		}
	}
	for(int i=1;i<=N;i++)
	    if(num[i]==0)
	        ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3836
MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * com.calc_COM(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * com.calc_COM(n-i, k-1)
    ans %= MOD
    print(ans)


Measured memory_bytes: 23008
a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i
k = gets.to_i

if b - a > k then
  puts ":("
elsif c - a > k then
  puts ":("
elsif d - a > k then
  puts ":("
elsif e - a > k then
  puts ":("
elsif c - b > k then
  puts ":("
elsif d - b > k then
  puts ":("
elsif e - b > k then
  puts ":("
elsif d - c > k then
  puts ":("
elsif e - c > k then
  puts ":("
elsif e - d > k then
  puts ":("
else
  puts "Yay!"
end


Measured memory_bytes: 1788
import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**5 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)


Measured memory_bytes: 14396
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>

#ifdef _MSC_VER
#include <Windows.h>
#else
#include <unistd.h>
#endif

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD=(double)1e9+7;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

#define INF 1LL << 50




int main(){
    string s;cin>>s;
    int res=100000;
    REP(i,26){
        char c='a'+i;
        int cnt=0;
        string s2=s;
        string s3=s;
        while(1){
            bool flag=true;
            REP(j,SZ(s2))if(s2[j]!=c)flag=false;
            if(flag)break;
            s2="";
            REP(j,SZ(s3)){
                if(j==SZ(s3)-1){
                    s2+="";
                }else if(s3[j]==c||s3[j+1]==c){
                    s2+=c;
                }else{
                    s2+=s3[j];
                }
            }
            //cout<<s2<<endl;
            cnt++;
            s3=s2;
        }
        //cout<<cnt<<endl;
        res=min(res,cnt);
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;

template<typename T>auto& operator<<(ostream &s, const vector<T> &v) {
   s << v.size() << " [";
   for (auto e:v) {
      s << e << "\t";
   }
   s << "]";
   return s;
}
#define rep(i, m) for(ll i=0;i<(m);i++)
#define rep1(i, m) for(ll i=1;i<=(m);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define INFI 1000000007
char S[2][60];
int main() {
   int N; cin >> N;
   cin >> S[0];
   cin >> S[1];
   // l = 0; S[0][0] = 3
   ll cnt = 1LL;
   int pat = -1;
   rep(i, N) {
      if (S[0][i] == S[1][i]) {
         switch(pat) {
            case 1:
               cnt *= 1; break;
            case 0: cnt *= 2; break;
            case -1: cnt = 3; break;
         }
         pat = 0;
      } else {
         switch(pat) {
            case 1: cnt *= 3; break;
            case 0: cnt *= 2; break;
            case -1: cnt = 6; break;
         }
         pat = 1;
         i++;
      }
      cnt %= INFI;
   }
   cout << cnt << endl;
}

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

int n, a[500005], l[500005], r[500005], inf = 1e9 + 1, s;
void merge( int x, int y ){
	if( x == y ) return;
	int c1 = (x + y) / 2;
	int c2 = ((x + y) / 2) + 1;
	
	merge( x, c1 );
	merge( c2 , y);
	
	for( int i = 0 ; i <= c1 - x ; i++ ) l[i] = a[i + x];
	for( int i = 0 ; i <= y - c2 ; i++ ) r[i] = a[i + c2];
	
	l[c1 - x + 1] = inf;
	r[y - c2 + 1] = inf;
	
	int k = x, l1 = 0, r1 = 0;
	
	for( int i = 0 ; i < y - x + 1 ; i++ ){
		a[k] = min( l[l1], r[r1]);
		k++;
		if( l[l1] > r[r1] ) r1++;
		else l1++;	
	}
	s += y - x + 1;	
	
}


int main(){
	
	cin >> n;
	for( int i = 0 ; i < n ; i++ ){
		cin >> a[i];
	}
	
	merge(0, n - 1);
	for( int i = 0 ; i < n ; i++ ){
		if( i != 0 ) cout << ' ';
		cout << a[i];
	}
	cout << "\n" << s << "\n";
	
}


Measured memory_bytes: 6924
#define N 40
#include <stdio.h>
struct poker {
    char suit;
    int value;
};

void showArray(struct poker a[], int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%c%d", a[i].suit, a[i].value);
    }
    printf("\n");
}

void bubbleSort(struct poker a[], int n) {
    int flag = 1;
    while (flag) {
        flag = 0;
        int i = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j].value > a[j + 1].value) {
                struct poker tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                flag = 1;
            }
        }
        i++;
    }
}

void selectionSort(struct poker a[], int n) {
    for (int i = 0; i < n; i++) {
        int minj = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j].value < a[minj].value) {
                minj = j;
            }
        }
        if (minj != i) {
            struct poker tmp = a[minj];
            a[minj] = a[i];
            a[i] = tmp;
        }
    }
}

int isStable(struct poker a[], struct poker b[], int n) {
    for (int i = 0; i < n; i++) {
        if (a[i].suit != b[i].suit) {
            return 0;
        }
    }
    return 1;
}

int main() {
    struct poker p1[N], p2[N];
    int n = 0;
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            getchar();
        }
        scanf("%C%d", &p1[i].suit, &p1[i].value);
        p2[i] = p1[i];
    }
    bubbleSort(p1, n);
    selectionSort(p2, n);
    showArray(p1, n);
    printf("Stable\n");
    showArray(p2, n);
    if (isStable(p1, p2, n)) {
        printf("Stable\n");
    }
    else {
        printf("Not stable\n");
    }
    return 0;
}


Measured memory_bytes: 2104
#ABC156 - Virtual
sel='A'
#A
if sel=='A':
    N,R=map(int,input().split())
    if N>=10:
        print(R)
    else:
        print(R+100*(10-N))
#B
if sel=='B':
    N,K=map(int,input().split())
    cnt=0
    while N>0:
        N//=K
        cnt+=1
    print(cnt)

#C
if sel=='C':
    def ceilT(a,b): #ceil(a/b)
        return (a+b-1)//b

    N=int(input())
    X=[int(i) for i in input().split()]
    p=ceilT(sum(X),N)
    ans=sum((x-p)**2 for x in X)
    p-=1
    ans=min(ans,sum((x-p)**2 for x in X))
    print(ans)






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

int main()
{
    ll MOD = 1e9 + 7;
    int n;
    ll k;
    cin >> n >> k;
    ll arr[n];
    for (int i=0; i<n; ++i) {
        cin >> arr[i];
    }
    
    // dp[i][j] is the # of ways to distribute j candies amongst i children.  
    // dp[i][j] += dp[i-1][j-k] for every k ith child can eat.
    ll dp[n+1][k+1]; 
    ll prefix_sum[k+2] = {0}; 
    
    fill(*dp, *dp + (n+1)*(k+1), 0);
    for (int i=0; i<=n; ++i)
        dp[i][0] = 1;
    
    for (int child=1; child<=n; ++child) {
        for (ll i=1; i<=k+1; ++i)
            prefix_sum[i] = (prefix_sum[i-1] + dp[child-1][i-1]) % MOD;

        for (ll c_dist=1; c_dist<=k; ++c_dist) 
            dp[child][c_dist] = (prefix_sum[c_dist+1] - prefix_sum[c_dist-min(arr[child-1], c_dist)] + MOD) % MOD;
            
    }
    
    cout << dp[n][k];
    return 0;
}


Measured memory_bytes: 79872
N,M,X = map(int,input().split())
A = list(map(int,input().split()))
A.append(X)
A.sort()
flag = False
for i in range(N+1):
  if (A[i] == X):
    flag = True
    break
if flag:
  print(min(len(A[i+1:]),len(A[:i])))

Measured memory_bytes: 3064