akhauriyash/Code-Regression huggingface dataset:
#include<queue>
#include<cstdio>
#include<cstring>
#define inf 2e8
#define maxn 500010
#define min(x,y) (x)<(y)?(x):(y)
using namespace std;
int to[maxn*2],nxt[maxn*2],mn[maxn*4];
int a[maxn],b[maxn],d[maxn];
int first[maxn];
int n,k,cnt;
priority_queue<int>q;
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=first[x];
    first[x]=cnt;
    d[y]++;
}
void change(int x,int l,int r,int p,int v)
{
    if(l==r)
    {
        mn[x]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        change(x<<1,l,mid,p,v);
    else
        change(x<<1|1,mid+1,r,p,v);
    mn[x]=min(mn[x<<1],mn[x<<1|1]);
}
int query(int x,int l,int r,int s,int t)
{
    if(s<=l&&r<=t)
        return mn[x];
    int mid=(l+r)>>1,ans=inf;
    if(s<=mid)
        ans=min(ans,query(x<<1,l,mid,s,t));
    if(t>mid)
        ans=min(ans,query(x<<1|1,mid+1,r,s,t));
    return ans;
}
int main()
{
    int x;
    scanf("%d%d",&n,&k);
    memset(mn,15,sizeof(mn));
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),a[b[i]]=i;
    for(int i=n;i;i--)
    {
        x=query(1,1,n,a[i]-k+1,a[i]);
        if(x<=n)
            add(a[x],a[i]);
        x=query(1,1,n,a[i],a[i]+k-1);
        if(x<=n)
            add(a[x],a[i]);
        change(1,1,n,a[i],i);
    }
    for(int i=1;i<=n;i++)
        if(!d[i])
            q.push(i);
    for(int i=n;i;i--)
    {
        b[i]=x=q.top();
        q.pop();
        for(int j=first[x];j;j=nxt[j])
            if((--d[to[j]])==0)
                q.push(to[j]);
    }
    for(int i=1;i<=n;i++)
        a[b[i]]=i;
    for(int i=1;i<=n;i++)
        printf("%d\n",a[i]);
    return 0;
}

Measured memory_bytes: 27008
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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;
}

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

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

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------


int main(){
ll n;
cin>>n;
ll a,b;

if(n==2){
    cin>>a>>b;
    cout<<a+b<<endl;
}else{
    cout<<"Hello World"<<endl;
}
}









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

def solve(a):
  ans=100
  cnt=1
  while cnt*cnt<=a:
    if a%cnt == 0:
      x=str(a//cnt)
      y=str(cnt)
      ans=min(ans,max(len(x),len(y)))
    cnt+=1
  return ans

print(solve(N))

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

int T, A, B, C, D;

signed main(){
  
  cin>>T;
  
  while(T--){
    
    cin>>A>>B>>C>>D;
    
    if( A < B ){
      cout<<"No"<<endl;
    }else{
    
      if( B > D ){
	cout<<"No"<<endl;
      }
    
      if( B == D ){
      
	if( A % B <= C ) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
      
      }
    
      if( B < D ){
      
	A %= B;
      
	int b = __gcd( B, D );
      
	int L = 0, R = B / b + 5;
      
	while( L < R ){
	
	  int M = ( L + R ) / 2;
	
	  if( A + b * M < B ) L = M + 1;
	  else R = M;
	
	}
      
	if( A + b * ( L - 1 ) <= C ) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
      
      }
    
    }
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
       Scanner sc = new Scanner(System.in);   
       //取得
      int N = sc.nextInt();
      int m = sc.nextInt();
      int[] M = new int[30];
      for(int i=0;i<N;i++){
        int K = sc.nextInt();
        int[] A = new int[K];
        for(int j=0;j<K;j++){
          A[j] = sc.nextInt();
          M[A[j]-1]++;
        }
      }
      int count=0;
      for(int i=0;i<30;i++){
        if(M[i]==N){
          count++;
        }
      }
      System.out.println(count);
    }
}

Measured memory_bytes: 38412
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i = n;i >= 0;--i)
#define FOR(i,m,n) for(int i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;


int main(void)
{
    int n;
    cin >> n;
    long long  cnt = 0;
    vector<int> L(n);

    REP(i, n){
        cin >> L[i];
    }
    sort(all(L));
    
    FOR(i,0,n-1){
        FOR(j,i+1,n){
            int a_max_idx = lower_bound(all(L),L[i]+L[j]) - L.begin() - 1;
            if(a_max_idx < 0){
                continue;
            }

            int a_min_idx = upper_bound(all(L),L[j]-L[i]) - L.begin();
            if(a_min_idx == n){
                continue;
            }

            cnt += a_max_idx - a_min_idx + 1;
            if(a_min_idx <= i && i <= a_max_idx){
                cnt--;
            }
            if(a_min_idx <= j && j <= a_max_idx){
                cnt--;
            }
        }
    }

    cout << cnt /3 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <strstream>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
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;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int query(string ans)
{
    char x;
    cout<<"? "<<ans<<endl;
    cin>>x;
    if(x=='Y')
    {
        return 1;
    }else
    {
        return 0;
    }
}
void solve()
{
    string temp="9";
    string ans="1";
    while(!query(temp))
    {
        temp+="9";
        ans+="0";
    }
    cout<<"! "<<ans<<endl;
}
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    string ans="1";
    string res;
    while(1)
    {
        cout<<"? "<<ans<<endl;
         cin>>res;
        if(res[0]=='Y')
        {
            ans+="0";
        }else
        {
            break;
        }
        if(ans.length()>11)
        {
            solve();
            return 0;
        }
    }
    int len=ans.length();
    string temp;
    rep(i,0,len-1)
    {
        int mid;
        int l=0;
        int r=9;
        while(l<=r)
        {
            mid=(l+r)>>1;
            ans[i]='0'+mid;
            if(query(ans))
            {
                r=mid-1;
            }else
            {
                l=mid+1;
                temp=ans;
            }
        }
        ans=temp;
    }
    temp.pop_back();
    int num=temp.length();
    stringstream ss;
    ss.clear();
    ss<<temp;
    ll fans;
    ss>>fans;
    fans++;
    cout<<"! "<<fans<<endl;

    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

Measured memory_bytes: 668
#include<bits/stdc++.h>
using namespace std;
long long dp[12][10];
int main()
{
	int k;
	scanf("%d",&k);
	for(int i=1;i<=9;i++){
		dp[1][i]=1;
	}
	dp[1][0]=1;
	long long sum=9;
	if(k<=9){
		printf("%d\n",k);
		return 0;
	}
	int x,y;
	for(int i=2;i<=20;i++){
		dp[i][0]=dp[i-1][0]+dp[i-1][1];
		for(int j=1;j<=9;j++){
			if(j!=9){
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
			}else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			sum+=dp[i][j];
			if(sum>=k){
				x=i;
				y=j;
				break;
			}
		}
		if(sum>=k){
			break;
		}
	}
	long long ans=y*pow(10,x-1);
	long long zz=(sum-dp[x][y]);
	for(int i=x-1;i>=1;i--){
		for(int j=-1;j<=1;j++){
			if((y+j)<0||(y+j)>9){
				continue;
			}
			zz+=dp[i][y+j];
			if(zz>=k){
				zz-=dp[i][y+j];
				y=y+j;
				ans+=y*pow(10,i-1);
				break;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
int a;
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>s;
	if (a>=3200) cout<<s;
	else cout<<"red";
	return 0;
}

Measured memory_bytes: 256
//解説あり
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()

using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int N;
ll ans = 1;
int A[100005];

int main(void) {
    
    scanf("%d", &N);
    rep(i, 0, N) scanf("%d", &A[i]);
    
    sort(A, A+N);
    
    int t, i;
    
    if (N%2 == 1) {
      if (A[0] != 0) {
        puts("0");
        return 0;
      }
      i = 1;
      t = 2;
    } else {
      i = 0;
      t = 1;
    }
    
    for (; i < N; i += 2) {
      if (A[i] != t || A[i+1] != t) {
        puts("0");
        return 0;
      }
      ans *= 2;
      ans %= MOD;
      t += 2;
    }
    
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
struct edge{int to,cost;};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=MOD;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    int memo=modpow(a,b/2);
    return memo*memo%MOD;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int inv(int x){
    x=modpow(x,MOD-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
double dist(double ax,double ay,double bx,double by){
    return sqrt((bx-ax)*(bx-ax)+(ay-by)*(ay-by));
}
int n,m;
string A="AC",W="WA";
bool b[100010];
int cnt[100010];
signed main(){
    cin>>n>>m;
    rep(i,m){
       int p;
       string s;
       cin>>p>>s;
       if(b[p])continue;
       if(s==A)b[p]=true;
       else cnt[p]++;
    }
    int ans=0,pe=0;
    for(int i=1;i<=n;i++){
        if(b[i]){
            ans++;
            pe+=cnt[i];
        }
    }
    cout<<ans<<" "<<pe<<endl;
    return 0;
}

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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int N, M, L;
vector<double> P, T, V;

double t[101][51]; // ??°???i???j????????????????????´???????????§?????????

double dp[101][51][51]; // ??°???i????????????j?????§???k??????????¢????

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> M >> L;
  P.resize(N); T.resize(N); V.resize(N);
  rep(i, N) cin >> P[i] >> T[i] >> V[i], P[i] /= 100;

  rep(i, N) rep(j, M+1) {
    if(V[i]) t[i][j] = L/V[i] + j*T[i];
    else t[i][j] = 1e9;
  }

  rep(i, N) dp[i][0][0] = 1;
  rep(i, N) rep(j, M) rep(k, j+1) {
    dp[i][j+1][k+1] += dp[i][j][k] * P[i];
    dp[i][j+1][k] += dp[i][j][k] * (1 - P[i]);
  }

  rep(i, N) {
    double ans = 0;
    rep(j, M+1) {
      double p = dp[i][M][j];
      rep(k, N) if(i != k) {
	double q = 0;
	rep(l, M+1) if(t[i][j] < t[k][l]) {
	  q += dp[k][M][l];
	}
	p *= q;
      }
      ans += p;
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 5280
#include<bits/stdc++.h>
//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<string>
//#include<queue>
//#include<cmath>
//#include<algorithm>
#define debug1 cout<<"?"<<endl;
#define debug2 cout<<"?"<<i<<endl;
#define PII pair<int,int>
typedef long long ll;
const int maxn=1e5+9;
const double pi=acos(-1);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double ep=1e-7;
using namespace std;
int main()
{
	int h,a,sum=0,n,i;
	scanf("%d%d",&h,&n);
	for(i=1;i<=n;i++)scanf("%d",&a),sum+=a;
	if(sum>=h)puts("Yes");
	else puts("No");
}

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

int main(){

    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n+2];

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

    int total = 0;
    for(int i=0; i<n+1; i++){
        total += abs(a[i+1] - a[i]);
    }

    for(int i=1; i<=n; i++){
        int temp = total - abs(a[i] - a[i-1]) - abs(a[i+1] - a[i]) + abs(a[i+1] - a[i-1]);
        cout << temp << "\n";
    }
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = (int)1e9 + 7;

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

    int a, b, c;
    cin >> a >> b >> c;
    cout << (a == b ? c : (a == c ? b : a)) << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int A;
  	int B;
  	cin >> A;
    cin >> B;
  	int ans;
  	if(A < B){
    ans = 2*B-1;
    }
  else if(A > B){
    ans = 2*A-1;
  }
  else{
    ans = A + B;
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll = long long int
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define REP3(i,x,n) for(int i=x; i>(n); i--)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

//文字列から数値に変換
int getChar(char ch){
    if(ch == 'A')return 1;
    else if(ch == 'C') return 2;
    else if(ch == 'G') return 3;
    else if(ch == 'T') return 4;
    else return 0;
}

//文字列カラス内へ変換してkeyを変換する
long long getKey(char str[]){
    long long sum =0,p = 1,i;
    for(i = 0; i < strlen(str);i++){
        sum += p*(getChar(str[i]));
        p*=5;
    }
    return sum;
}

int h1(int key){return key%M;}
int h2(int key){return 1 + (key%(M-1));}

int find(char str[]){
    long long key, i, h;
    key = getKey(str);
    for(int i = 0;;i++){
        h = (h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0)return 1;
        else if(strlen(H[h])==0)return 0;
    }
    return 0;
}
int insert(char str[]){
    long long key,i,h;
    key = getKey(str);
    for(i =0;;i++){
        h = (h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0)return 1;
        else if(strlen(H[h])==0){
            strcpy(H[h],str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int i,n,h;
    char str[L],com[9];
    for(i = 0; i < M;i++) H[i][0]='\0';
    scanf("%d",&n);
    for(i = 0;i < n;i++){
        scanf("%s %s",com,str);
        if(com[0]=='i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        }
    }
    return 0;
}




Measured memory_bytes: 17480
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void){
    char line[11],line1[30];
    int i=0,sum=0;
    scanf("%s",line);
    while(line[i]){
        if(isupper(line[i]))
                line[i]=tolower(line[i]);
        i++;
    }
    for(;i=0,scanf("%s",line1),strcmp(line1,"END_OF_TEXT");){
        while(line1[i]){
            if(isupper(line1[i]))
                    line1[i]=tolower(line1[i]);
            i++;
        }
        if(!strcmp(line1,line))
                sum++;
    }
    printf("%d\n",sum);
    return 0;
}

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

using namespace std;

struct Pair{
    int a;
    int b;
    Pair(int a, int b){
        this->a = a;
        this->b = b;
    }
};


int main(){
    int n;
    cin >> n;
    vector<long long> v;
    long long tmp;
    vector<Pair> vp;
    long long min = 1000001,max = -1000001;
    int index_min, index_max;
    for(int i =0;i<n;i++){
        cin >> tmp;
        v.push_back(tmp);
        if(min > tmp){
            min = tmp;
            index_min = i;
        }
        if(max < tmp){
            max = tmp;
            index_max = i;
        }
    }
    if(max < -min){
        for(int i=0;i<n;i++){
            v[i] += v[index_min];
            vp.push_back(Pair(index_min,i));
        }
        for(int i=n-1;i>0;i--){
            while(v[i-1] > v[i]){
                v[i-1] += v[i];
                vp.push_back(Pair(i,i-1));
                // cout << i << endl;
            }
        }
    } else {
        for(int i=0;i<n;i++){
            v[i] += v[index_max];
            vp.push_back(Pair(index_max,i));
        }
        for(int i=0;i<n-1;i++){
            while(v[i] > v[i+1]){
                v[i+1] += v[i];
                vp.push_back(Pair(i,i+1));
            }
        }
    }
    cout << vp.size() << endl;
    for(auto it = vp.begin();it!=vp.end();it++)
        cout << it->a+1 << " " << it->b+1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define MOD 1000000007

int main()
{
  ll a, bi;
  ld bd;
  cin >> a >> bd;
  bi = round(bd * 100);

  cout << a * bi / 100 << endl;
  return 0;
}


Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <vector>
#include <random>

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

using namespace std;

struct Myrand {
  uint64_t val;
  Myrand() : val(859238598) {}
  uint64_t operator()() {
    return val = val*val + 737598437;
  }
} my_rand;

typedef int Data;

const int INF = 1e8;

struct RBST {
  Data value;
  RBST *left;
  RBST *right;
  int cnt;
  Data minv;
  RBST(Data v)
    : value(v), left(nullptr), right(nullptr),
    cnt(1), minv(v) {}
};

int count(RBST *t) { return !t ? 0 : t->cnt; }
Data minv(RBST *t) { return !t ? INF : t->minv; }
RBST *update(RBST *t) {
  t->cnt = count(t->left) + count(t->right) + 1;
  t->minv = min(min(minv(t->left), minv(t->right)), t->value);
  return t;
}

RBST *merge(RBST *l, RBST *r) {
  if (!l || !r) return !l ? r : l;

  int cnt_sum = count(l) + count(r);
  // rand()?????¨?°????????????????????????????????£?????????£??????????????¨??????????????§???mt19937??¨????????????????£??????????
  if ((my_rand() % cnt_sum) < count(l)) {
    l->right = merge(l->right, r);
    return update(l);
  } else {
    r->left = merge(l, r->left);
    return update(r);
  }
}

pair<RBST*, RBST*> split(RBST *t, int k) {
  if (!t) return make_pair(nullptr, nullptr);
  
  if (k <= count(t->left)) {
    auto s = split(t->left, k);
    t->left = s.second;
    return make_pair(s.first, update(t));
  } else {
    auto s = split(t->right, k - count(t->left) - 1);
    t->right = s.first;
    return make_pair(update(t), s.second);
  }
}

RBST *insert(RBST *t, int k, Data v) {
  auto s = split(t, k);
  return merge(s.first, merge(new RBST(v), s.second));
}

RBST *erase(RBST *t, int k) {
  auto s1 = split(t, k);
  auto s2 = split(s1.second, 1);
  delete s2.first;
  return merge(s1.first, s2.second);
}

int main() {
  srand(0);
  RBST *root = nullptr;
  int n,q;
  cin>>n>>q;
  REP(i,n){
    int a;
    cin>>a;
    root = insert(root, i, a);
  }
  REP(i,q){
    int x,y,z;
    cin>>x>>y>>z;
    switch(x){
      case 0: {
        auto b = split(root, z+1);
        auto f = split(b.first, y);
        auto s = split(f.second, z-y);
        RBST *ns = merge(s.second, s.first);
        RBST *nf = merge(f.first, ns);
        root = merge(nf, b.second);
      } break;
      case 1: {
        auto b = split(root, z+1);
        auto f = split(b.first, y);
        cout << f.second->minv << endl;
        RBST *nf = merge(f.first, f.second);
        root = merge(nf, b.second);
      } break;
      case 2: {
        root = erase(root, y);
        root = insert(root, y, z);
      } break;
    }
  }
  return 0;
}

Measured memory_bytes: 12476
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
 
lst = [a, b, c, d, e]
lst = sorted(lst)

if n % lst[0] == 0:
    res = n // lst[0] + 4
else:
    res = n // lst[0] + 5
print(res)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final long A = sc.nextLong();
        final long B = sc.nextLong();
        final long C = sc.nextLong();
        final long D = sc.nextLong();
        final long L = lcm(C, D);
        System.out.println((B - B / C - B / D + B / L) - ((A-1) - (A-1) / C - (A-1) / D + (A-1) / L));
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    private static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int pow(int x, int n) {
  int i = 0;
  int res = 1;
  while(i != n) {
    res *= x;
    i++;
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  int a[n];
  int odd = 0;
  int even = 0;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    if(a[i] % 2 == 1) {
      odd++;
    }else {
      even++;
    }
  }
  cout << pow(3,n) -pow(2,even) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF -(1LL << 60)
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

int main()
{
	int n;
	cin >> n;
	vl vec(n);
	vi used[2];
	ll mx[2] = {0LL,0LL};
	rep(i,n){
		cin >> vec[i];
		if(vec[i] > 0){
			mx[i%2] += vec[i];
			used[(i+1)%2].pb(i);
		}else{
			rep(j,2){
				used[j].pb(i);
			}
		}
	}
	int st = 0;
	if(mx[1] > mx[0]){
		st = 1;
	}
	if(len(used[0]) == n && len(used[1]) == n){
		int id = max_element(all(vec)) - vec.begin();
		st = id % 2;
		cout << vec[id] << "\n";
		used[st].clear();
		rep(i,n){
			if(i != id){
				used[st].pb(i);
			}
		}
	}else{
		cout << mx[st] << "\n";
	}
	vector<bool> ch(n,false);
	rep(i,len(used[st])){
		ch[used[st][i]] = true;
	}
	vi opr;
	int last = 0;
	rrep(i,n){
		if(ch[i]){
			if(last == 0){
				opr.pb(i);
			}else if(last == 1 || last == 2){
				last++;
			}else{
				opr.pb(i+1);
				last = 2;
			}
		}else{
			if(last == 0){
				last++;
			}else{
				opr.pb(i+1);
				last = 1;
			}
		}
	}
	rep(i,last-1){
		opr.pb(0);
	}
	cout << len(opr) << "\n";
	rep(i,len(opr)){
		cout << opr[i]+1 << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;

int main(){
    int x[5];
    rep(i, 5){
        cin >> x[i];
    }
    rep(i, 5){
        if(x[i] == 0){
            cout << i+1 << endl;
            return 0;
        }
    }

}

Measured memory_bytes: 3588
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n/non_zero
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i/non_zero
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j/non_zero
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k/non_zero

print(dp[c[3]][c[2]][c[1]])


Measured memory_bytes: 496136
import math

if __name__ == '__main__':
    a,  b, x = map(int, input().split())
    if 2.0 * (b - x / a / a) <= b:
        print(math.degrees(math.atan(2.0 * (b - x / a / a) / a)))
    else:
        print(math.degrees(math.atan((a * b * b)/2.0/x)))



Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  int ans=1;
  string A="dreamer",B="eraser",C="dream",D="erase";
  S.insert(0,"dreamer");
  while(S.size()>0){
    int L=S.size(),X=1,Y=1,Z=1,W=1;
    for(int i=0;i<7;i++) X*=int(S[L-7+i]==A[i]);
    for(int i=0;i<6;i++) Y*=int(S[L-6+i]==B[i]);
    for(int i=0;i<5;i++) Z*=int(S[L-5+i]==C[i]);
    for(int i=0;i<5;i++) W*=int(S[L-5+i]==D[i]);
    if(X) S.erase(L-7);
    else if(Y) S.erase(L-6);
    else if(Z) S.erase(L-5);
    else if(W) S.erase(L-5);
    else{
      ans=0;
      break;
    }
  }
  cout<<(ans?"YES":"NO")<<endl;
}

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

int main() {
    int n,k;
    cin>>n>>k;
    ll a=0,b=0;
    for (int i=1;i<=n;i++) {
        if (i%k==0)
            a++;
        else if (i%k==k/2)
            b++;
    }
    ll ans=a*a*a;
    if (k%2==0)
        ans+=b*b*b;
    cout<<ans<<endl;
    return 0;
}

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

/*
// grp[i]:i番目の強連結成分に含まれる頂点一覧 iはトポロジカル順
class SCC {
	public:
	static const int MV = 100000;
	vector<vector<int> > grp; int NV,cmp[MV];
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) {vis[cu]=1; cmp[cu]=ind; grp[ind].push_back(cu);
		for(int i=0;i<RE[cu].size();++i) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; grp.clear(); grp.resize(MV); NUM.clear();
		memset(vis,0,sizeof(vis)); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		memset(vis,0,sizeof(vis)); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]])
			{ grp[c].clear(); revdfs(NUM[i],c); sort(grp[c].begin(),grp[c].end()); c++;}
		grp.resize(c);
	}
};
 */

int n, m, a, b, q, c[100100];
vector<int> e[100100];

/*
vector<int> scc(int n, vector<int> e[]) {
	int sz = 0, s = 0;
	vector<int> rg[n], stk, cmp(n, -1), added(n), visited(n), ord(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < e[i].size(); ++j) rg[e[i][j]].push_back(i);
		sz += e[i].size();
	}
	stk.resize(n + sz), sz = 0;
	for (int i = 0; i < n; i++) {
		if (visited[i]) continue;
		stk[s = 1] = i;
		while (s != 0) {
			int v = stk[s - 1];
			visited[v] = true;
			bool pushed = false;
			for (int j = 0; j < e[v].size(); ++j) {
				int dst = e[v][j];
				if (!visited[dst]) {
					stk[s++] = dst;
					pushed = true;
				}
			}
			if (pushed) continue;
			int t = stk[s - 1];
			if (!added[t]) added[t] = true, ord[n - ++sz] = t;
			--s;
		}
	}
	int k = 0;
	for (int i = 0; i < n; ++i) {
		if (cmp[ord[i]] != -1) continue;
		s = 0, stk[s++] = ord[i];
		while (s != 0) {
			int v = stk[--s];
			cmp[v] = k;
			for (int j = 0; j < rg[v].size(); ++j) {
				int d = rg[v][j];
				if (cmp[d] == -1) stk[s++] = d;
			}
		}
		++k;
	}
	return cmp;
}
*/

// paint
void rec(int v, int x) {
	c[v] = x;
	for (int i = 0; i < e[v].size(); ++i)
		if (c[e[v][i]]==0) rec(e[v][i],x);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		e[a].push_back(b), e[b].push_back(a);
	}
	
	int nm = 0;
	for (int i = 0; i < n; ++i) {
		if (c[i]==0) rec(i,++nm);
	}
	
	cin >> q;
	while (q--) {
		cin >> a >> b;
		cout << (c[a]==c[b] ? "yes" : "no") << endl;
	}
}


Measured memory_bytes: 12064
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        List<String> S = new ArrayList();
        List<Integer> P = new ArrayList();
        Map<String,Integer> namePointIndex = new HashMap();
        for(int i=0; i<N; i++){
            String name = scanner.next();
            Integer point = scanner.nextInt();
            S.add(name);
            P.add(point);
            namePointIndex.put(name + String.valueOf(point), i+1);
        }
        Set<String> nameset = new HashSet(S);
        S = new ArrayList(nameset);
        Collections.sort(S);
        Collections.sort(P,Comparator.reverseOrder());

        for(String name:S){
            for(int point:P){
                String key = name + String.valueOf(point);
                if(namePointIndex.containsKey(key)){
                    System.out.println(namePointIndex.get(key));
                }
            }
        }
    }

}

Measured memory_bytes: 23380
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=1000002;
int s,w;

int main()
{
    read(s); read(w);
    printf("%s",w>=s?"unsafe":"safe");
    return 0;
}

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

int main() {
  int a[] = {0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0};
  int x, y;
  cin >> x >> y;

  if (a[x] == a[y])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

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

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll n, m, a, b, p, q;
ll ans = 1e18;

void solve1() {
    ll timer = m / (p + q);
    chmin(timer, n);
    chmin(ans, abs(m - timer * (p+q)));
    timer++;
    chmin(timer, n);
    chmin(ans, abs(m - timer * (p+q)));
    return;
}

void solve2() {
    ll Mindex = 0;
    ll pak = p;
    ll qbk = q;
    for(ll i = 1; i < n; i++) {
        if(pak > 1e15 / a) break;
        if(qbk > 1e15 / b) break;
        chmax(Mindex, i);
        pak *= a;
        qbk *= b;
    }
    ll rest = m;
    while(Mindex >= 0) {
        //cerr << Mindex << " " << rest << " " << pak << " " << qbk << endl;
        chmin(ans, abs(rest - pak - qbk));
        if(rest - pak - qbk >= 0) {
            rest -= pak + qbk;
            chmin(ans, rest);
        }
        pak /= a;
        qbk /= b;
        Mindex--;
    }
}

void solve3() {
    ll Mindex = 0;
    ll qbk = q;
    for(ll i = 1; i < n; i++) {
        if(qbk > 1e15 / b) break;
        chmax(Mindex, i);
        qbk *= b;
    }
    for(int num = 1; num <= Mindex + 1; num++) {
        ll rest = m - num * p;
        ll restnum = num;
        ll nowqbk = qbk;
        for(int j = Mindex; j >= 0; j--) {
            if(j + 1 == restnum or (restnum >= 1 and rest - nowqbk >= 0)) {
                rest -= nowqbk;
                restnum--;
            } else {
                /*
                ll nowrest = rest;
                rest -= nowqbk;
                ll nowrestnum = restnum - 1;
                ll newqbk = q;
                for(ll i = 0; i < nowrestnum; i++) {
                    rest -= newqbk;
                    newqbk *= b;
                }
                */
                //chmin(ans, abs(nowrest));
            }
            nowqbk /= b;
        }
        chmin(ans, abs(rest));
    }
}

int main() {
    //cout.precision(10);
    cin >> n >> m >> a >> b >> p >> q;
    ans = m;
    if(a == 1 and b == 1) {
        solve1();
    } else if(a != 1 and b != 1) {
        solve2();
    } else {
        if(a != 1) {
            swap(a, b);
            swap(p, q);
        }
        solve3();
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    map<int, int> cnt;
    forn(i, 0, n) {
        int x;
        cin >> x;
        ++cnt[x];
    }
    int ans = 0;
    for (auto p : cnt) {
        if (p.sn >= p.fs) ans += p.sn - p.fs;
        else ans += p.sn;
    }
    cout << ans << '\n';
}


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

using namespace std;

int main() {
	long long int H, W, N;
	cin >> H >> W >> N;
	map<pair<long long int, long long int>, long long int>MLL;
	for( int i = 0; i < N; i++ ) {
		long long int a, b;
		cin >> a >> b;
		a--; b--;
		for( int j = -1; j <= 1; j++ ) {
			for( int k = -1; k <= 1; k++ ) {
				MLL[make_pair( a + j, b + k )]++;
			}
		}
	}
	vector<long long int>ans( 10 );
	for( auto n : MLL ) {
		if( 1 <= n.first.first&&n.first.first < H - 1 && 1 <= n.first.second&&n.first.second < W - 1 ) {
			//cout << n.first.first << " " << n.first.second << endl;
			ans[n.second]++;
		}
	}
	ans[0] = (H - 2)*(W - 2);
	for( size_t i = 1; i < 10; i++ ) {
		ans[0] -= ans[i];
	}
	for( size_t i = 0; i < 10; i++ ) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 56448
#include <stdio.h>
s[100],i,c=0;
main(n)
{
float w,t;
while(scanf("%d,%f,%f",&n,&w,&t)!=-1)
if(w/(t*t)>=25)s[c++]=n;
if(c==1)printf("ツ該ツ督鳴づ按つオ");
for(i=0;i<c;i++)printf("%d\n",s[i]);
return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

double P[3000];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%lf", &P[i]);
    }
    vector<double> dp(N+2, 0.0);
    dp[1] = 1.;
    for (int i = 1; i <= N; ++i) {
        for (int j = i+1; j >= 1; --j) {
            dp[j] = dp[j]*(1-P[i-1]) + dp[j-1]*P[i-1];
        }
    }
    double ans = 0.;
    for (int i = 2+N/2; i <= N+2; ++i) ans += dp[i];
    cout << setprecision(9) << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

bool vs[100010];
bool vt[100010];
ll ds[100010];
ll dt[100010];
ll ans[100010];
ll INF = 10e15;

struct Edge {
  int from, to;
  ll c1, c2;
};

struct Node {
  int id;
  ll cost;
  friend bool operator < (const Node& lhs, const Node& rhs) { return -lhs.cost < -rhs.cost; };
  friend bool operator > (const Node& lhs, const Node& rhs) { return rhs < lhs; };
  friend bool operator <= (const Node& lhs, const Node& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Node& lhs, const Node& rhs) { return !(lhs < rhs); };
};

typedef vector<vector<Edge>> Graph;
Graph g;

int n, m, s, t;

void dijkstra() { 
  for (int i = 0; i < n; ++i) { 
    ds[i] = INF;
  }
  priority_queue<Node> pq;
  pq.push((Node){s, 0});
  ds[s] = 0;
  while (!pq.empty()) { 
    Node node = pq.top(); pq.pop();
    vs[node.id] = true;
    for (Edge& e: g[node.id]) { 
      if (vs[e.to]) continue;
      ll d = ds[node.id]+e.c1;
      if (d >= ds[e.to]) continue;
      ds[e.to] = d;
      pq.push((Node){e.to, d});
    }
  }
}
void dijkstra2() { 
  for (int i = 0; i < n; ++i) { 
    dt[i] = INF;
  }
  priority_queue<Node> pq;
  pq.push((Node){t, 0});
  dt[t] = 0;
  while (!pq.empty()) { 
    Node node = pq.top(); pq.pop();
    vt[node.id] = true;
    for (Edge& e: g[node.id]) { 
      if (vt[e.to]) continue;
      ll d = dt[node.id]+e.c2;
      if (d >= dt[e.to]) continue;
      dt[e.to] = d;
      pq.push((Node){e.to, d});
    }
  }
}

int main() {
  cin >> n >> m >> s >> t;
  --s; --t;
  g.resize(n);
  for (int i = 0; i < m; ++i) { 
    int u, v;
    ll a, b;
    cin >> u >> v >> a >> b;
    --u; --v;
    g[u].push_back((Edge){u, v, a, b});
    g[v].push_back((Edge){v, u, a, b});
  }
  dijkstra();
  dijkstra2();
  ll best = INF;
  for (int i = n-1; i >= 0; --i) {
    best = min(best, ds[i]+dt[i]);
    ans[i] = 10e14-best;
  }
  for (int i = 0; i < n; ++i) {
    cout << ans[i] << endl;
  }
}



Measured memory_bytes: 13312
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int A, B;
    string S;
    cin >> A >> B >> S;
    bool res = true;
    rep(i, A+B+1) {
        if(i==A) continue;
        if(!(S[i]>='0' && S[i]<='9')) res = false;
    }
    if(res) if(!(S[A]=='-')) res = false;
    if(res) cout << "Yes";
    else cout << "No";
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main () {
	char alpha;
	scanf("%c", &alpha);
	
	if (alpha >= 'a' && alpha <= 'z') {
		printf("%c", 'a');
	}
	else if (alpha >= 'A' && alpha <= 'Z') {
		printf("%c", 'A');
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 1592
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a),i##Len_=(b);i<i##Len_;i++)

int main()
{
    int A,B,res;
    cin >> A >> B;

    res = B-A;
    if(B%A == 0)res = A+B;
    cout << res << endl;
}



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

long long N, W;
long long w[110], v[110];
long long dp[100100];


int main (){

	cin >> N >> W;
	for (int i=0; i < N; i++)
		cin >> w[i] >> v[i];
		
	for (int i=0; i < N; i++)
	{
		for (int j=W; j >= w[i]; j--)
		{
			dp[j]=max(dp[j-w[i]]+v[i], dp[j]);
		}
	}
	
	cout << dp[W];
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto&& V : v)
#define all(x) (x).begin(), (x).end()
using lint = long long;
const int INF = 1 << 29;
const double EPS = 1e-9;
using namespace std;

int main(void) {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int maxi = max({a, b, c});
  int left = a + b + c - maxi;
  rep(i, k) {
    maxi *= 2;
  }
  cout << left + maxi << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
queue = deque(list(range(1,10,1)))
#print(queue)

if n <= 9:
    ans = queue[n-1]
else:
    i = 9
    while(True):
        x = queue.popleft()
        if x % 10 != 0:
            next_num = 10 * x + (x % 10) - 1 
            i += 1
            if i == n:
                ans = next_num
                break
            queue.append(next_num)
        #必ず
        i += 1
        next_num = 10 * x + (x % 10)
        if i == n:
            ans = next_num
            break
        queue.append(next_num)
        if x % 10 != 9:
            next_num = 10 * x + (x % 10) + 1 
            i += 1
            if i == n:
                ans = next_num
                break
            queue.append(next_num)
        #print(queue)
print(ans)

Measured memory_bytes: 6088
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
const LL mod=1e9+7;
const LL LL_MAX=9223372036854775807;
using namespace std;
int main()
{
    int a[5],k;
    for(int i=0;i<5;i++)
    scanf("%d",&a[i]);
    scanf("%d",&k);
   // sort(a,a+5);
    if(a[4]-a[0]<=k)
        printf("Yay!\n");
    else
        printf(":(\n");
    return 0;
}


Measured memory_bytes: 256