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

void input(string& rsMaxNum)
{
  cin >> rsMaxNum;
}

int digitDp(string sMaxNum)
{
  // dp[nPos][nSmall][nFlag] :=  nPos  : 上位 nPos 桁目まで決定
  //                             nSmall: small(数字を自由に選べる)か
  //                             nFlag : 上位 nPos 桁までで {3,5,7} を選択したかflag
  //                             ( 0:選択なし, 1: 3   選択, 2: 5   選択, 3: 3 5   選択, 
  //                               4: 7 選択 , 5: 3 7 選択, 6: 5 7 選択, 7: 3 5 7 選択 )
  //                             の条件を満たす数値の数
  int dp[11][2][8] = {};
  dp[0][0][0] = 1;

  int nLen = sMaxNum.size();

  for (int nPos = 0; nPos < nLen; ++nPos)
    for (int nSmall = 0; nSmall < 2; ++nSmall)
      for (int nFlag = 0; nFlag < 8; ++nFlag)
      {
        if (!dp[nPos][nSmall][nFlag]) continue;

        if (nSmall == 1)               // small ([0, 9] から数字を選べる)か
        {
          if (!nFlag)
            dp[nPos + 1][1][0]       += dp[nPos][1][0];                    // nothing

          dp[nPos + 1][1][nFlag | 1] += dp[nPos][1][nFlag];                // +3
          dp[nPos + 1][1][nFlag | 2] += dp[nPos][1][nFlag];                // +5
          dp[nPos + 1][1][nFlag | 4] += dp[nPos][1][nFlag];                // +7
        }
        else                           // not small ([0, nDgt] から数字を選べる)か
        {
          int nDgt = sMaxNum[nPos] - '0';

          if (!nFlag)    dp[nPos + 1][1][0]         += dp[nPos][0][0];     // nothing

          if (nDgt == 3) dp[nPos + 1][0][nFlag | 1] += dp[nPos][0][nFlag]; // +3
          if (3 < nDgt ) dp[nPos + 1][1][nFlag | 1] += dp[nPos][0][nFlag]; // +3
          if (nDgt == 5) dp[nPos + 1][0][nFlag | 2] += dp[nPos][0][nFlag]; // +5
          if (5 < nDgt ) dp[nPos + 1][1][nFlag | 2] += dp[nPos][0][nFlag]; // +5
          if (nDgt == 7) dp[nPos + 1][0][nFlag | 4] += dp[nPos][0][nFlag]; // +7
          if (7 < nDgt ) dp[nPos + 1][1][nFlag | 4] += dp[nPos][0][nFlag]; // +7
        }
      }
/*
  for (int nPos = 0; nPos <= nLen; ++nPos)
     for (int nSmall = 0; nSmall < 2; ++nSmall)
       for (int nFlag = 0; nFlag < 8; ++nFlag)
         if (dp[nPos][nSmall][nFlag])
         {
           cout << "dp[" << nPos << "][" << nSmall << "][" << nFlag << "] = (";
           cout << dp[nPos][nSmall][nFlag] << ")" << endl;
         }
*/
  return dp[nLen][0][7] + dp[nLen][1][7];
}

int main()
{
  string sMaxNum;

  input(sMaxNum);
  cout << digitDp(sMaxNum) << endl;
  
  return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define reep(i, s, t) for(int i=s;i<(int)t;i++)
#define irep(i, n) for(int i=(int)n-1;i>=0;i--)
#define ireep(i, n, s) for(int i=(int)n-1;i>=s;i--)
#define all(v) v.begin(), v.end()
#define vc vector
#define pb push_back

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

int idx;
string s;

bool perse() {
	char var[3];
	bool no[3];
	rep(i, 3) {
		if(s[idx] == '~') {
			no[i] = true;
			idx++;
			var[i] = s[idx++];
		} else {
			no[i] = false;
			var[i] = s[idx++];
		}
		idx++;
	}
	rep(i, 3) {
		if(var[i] == var[(i+1)%3] && no[i] != no[(i+1)%3]) {
			return false;
		}
	}
	return true;
}

int main(){
	while(cin >> s) {
		if(s == "#") break;
		idx = 0;
		bool ok = false;
		while(idx < s.size()) {
			idx++;
			if(perse()) {
				ok = true;
				break;
			}
			idx++;
		}
		if(ok) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Measured memory_bytes: 1180
from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

Measured memory_bytes: 95612
m, k = input().split()
m, k = int(m), int(k)


xx = 0
for i in range(2**m):
    xx = xx ^ i

if k == 0:
    arr = [0] * (2 ** (m+1))
    for i in range(2**m):
        arr[2*i] = i
        arr[2*i+1] = i
    print(" ".join([str(x) for x in arr]))
elif xx != 0 or k >= 2 ** m:
    print(-1)
else:
    arr = [0] * (2 ** (m+1))
    f = (2 ** (m+1))
    arr[0] = k
    arr[f//2] = k
    pt1 = f // 2 - 1
    pt2 = f // 2 + 1
    curr = 0
    for i in range((f - 2) // 2):
        if (curr == k):
            curr += 1
        arr[pt1] = curr
        arr[pt2] = curr
        pt1 -= 1
        pt2 += 1 
        curr += 1
    print(" ".join([str(x) for x in arr]))

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

vector<int> eratos(int n) {
  vector<bool> isPrime(n+1, true);
  vector<int> res;
  isPrime.at(0) = false;
  isPrime.at(1) = false;
  for (int i = 2; i <= n; i++) {
    if (isPrime.at(i)) {
      res.push_back(i);
      for (int j = i*2; j <= n; j += i) isPrime.at(j) = false;
    }
  }
  return res;
}

int main() {
  int N; cin >> N;
  vector<int> primes = eratos(55555);
  int cnt = 0;
  for (int p : primes) {
    if (cnt == N) break;
    if (p % 5 == 1) {
      cout << p << " ";
      cnt++;
    }
  }
  cout << endl;
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,k,q;cin>>n>>k>>q;
    vector<ll> seikai(n,0);
    rep(i,q){
        ll a;cin>>a;

        seikai[a-1]++;
    }
    rep(i,n){
        if(k-q+seikai[i]>0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;cin>>A;
  if(A>1799){
    cout<<1<<endl;
  }
  else if(A>1599){
    cout<<2<<endl;
  }
  else if(A>1399){
    cout<<3<<endl;
  }
  else if(A>1199){
    cout<<4<<endl;
  }
  else if(A>999){
    cout<<5<<endl;
  }
  else if(A>799){
    cout<<6<<endl;
  }
  else if(A>599){
    cout<<7<<endl;
  }
  else if(A>399){
    cout<<8<<endl;
  }
}

Measured memory_bytes: 3628
using System;

public class Program{
    public static void Main(){
        string s = Console.ReadLine();
        string t = Console.ReadLine();
        int changeTime = 0;
        
        for(int i = 0; i < s.Length; i++){
            if(!s[i].Equals(t[i])){
                changeTime++;
            }
        }
        
        Console.WriteLine(changeTime);
    }
}


Measured memory_bytes: 27412
#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>
#include <math.h>

using namespace std;

const int M = 100001+3;

int solve( int N );

int main(void) {
	
	int N;
	cin >> N;
	cout << solve(N) << endl;
	
	return 0;
}


int solve( const int N ) {

	int ans = 0;

	//?´????????????¨???
	vector< int > v(M,0);

	v[0]++;
	v[v.size()-1]--;
	for( int i = 0; i < N; i++ ) {
		int a, b;
		cin >> a >> b;
		v[a]++;
		v[b+1]--;
	}

	for( int i = 0; i+1 < M; i++ )
		v[i+1] += v[i];

	for( int i = 0; i < M; i++)
		if( min(v[i],i) > ans && (v[i] >= i) )
			ans = min(v[i],i);

	return max(ans-1,0);

}

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

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

int main() {
    int q;
    set<int> s;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (x == 1)cout << s.count(y) << endl;
        else if (!x) {
            s.insert(y);
            cout << s.size() << endl;
        } else if (x == 2)s.erase(y);
        else {
            int l = y, r;
            cin >> r;
            set<int>::iterator end, it;
            it = s.lower_bound(l);
            end = s.upper_bound(r);
            for (; it != end; it++) {
                cout << (*it) << endl;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 12368
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string str;
    cin >> str;
    for(int i = 0; i < (int)str.size(); i++) {
        if (str[i] == '?') cout << "D";
        else cout << str[i];
    }
    return 0;
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 2000000000
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int main(){
	int n,a,b;
	while(~getIII(n,a,b)) printf("%d\n",min(n*a,b));
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<queue>
#include<set>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<int,int> P;
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define elif else if
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mp make_pair
#define fr(i,n)for(ll i=0;i<(n);i++)

int N, M,sx, sy, gx, gy;
char maze[110][110];
const int INF = 100000000;
int d[100][100];

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

int bfs(){
  queue<P> que;
  fr(i,N){
    fr(j,M)d[i][j] = INF;
  }
  que.push(P(sx, sy));
  d[sx][sy] = 0;
  
  while(que.size()){

    P p = que.front(); que.pop();

    if(p.first == gx && p.second == gy) break;

    fr(i,4){
      int nx = p.first + dx[i], ny = p.second + dy[i];

      if(0<=nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF){
        que.push(P(nx, ny));
        d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return d[gx][gy];
}

int main(){
  // 入力
  cin >> N >> M; 
  ll q = 0;
  fr(i,N){
    fr(j,M){
      cin >> maze[i][j];
      if(maze[i][j]=='#')q++;
    }
  }
  sx = 0;
  sy = 0;
  gx = N-1;
  gy = M-1;

  int res = bfs();
  if(res==INF)cout<<-1<<endl;
  else cout << N*M-res-q-1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<math.h>

using namespace std;
int main() {

	int N,A,B;

	cin >> N >> A >> B;
	if ((N*A)>B)
	{
		cout << B << endl;
	}
	if ((N*A)<B)
	{
		cout << N*A << endl;
	}
	if ((N*A)==B)
	{
		cout << B << endl;
	}

	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner

object Main extends App { 
  val sc = new Scanner(System.in)
  val N = sc.nextInt()
  val seq = (for (i <- 1 to N) yield sc.nextInt).toList

  class DP(n:Int, seq:List[Int]) {
    val Inf = Int.MaxValue >> 1
    val memo = Array.fill(n)(Inf)

    def find(x:Int):Int = {
      def iter(l:Int,r:Int):Int = {
        if (l+1==r || l==r) l
        else {
          val i = (l + r) >> 1
          (x - memo(i)) match {
            case d if d  < 0 => iter(l, i)
            case d if d == 0 => i
            case d if d  > 0 => iter(i, r)
          }
        }
      }
      iter(0, n-1)
    }

    def solver():Int = {
      for (e <- seq) {
        val i = find(e)
        if (memo(i) < e) memo(i+1) = e else memo(i) = e
      }
      memo.filter(_!=Inf).length
    }
  }

  val dp = new DP(N, seq)

  println(dp.solver())
}


Measured memory_bytes: 139480
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MOD 1000000007
#define f(i,a,n) for(lli i = a; i < n; i++)
#define pb push_back
#define mp make_pair

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    int a,b;
    cin>>a>>b;
    if(a<=5)
    	cout<<0;
    else if(a<13)
    	cout<<b/2;
    else
    	cout<<b;
return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int gcd(int a, int b);
int gcd2(int a, int b, int c);

int main(void)
{
    
    int n, res;
    
    res = 0;
    
    cin >> n;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                res += gcd2(i, j, k);
            }
        }
    }
    
    cout << res;

}

int gcd(int a, int b)
{
    if(a < b)
    {
        int tmp = b;
        b = a;
        a = tmp;
    }
    
    int r = a % b;
    
    while(r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    
    return b;
}

int gcd2(int a, int b, int c)
{
    int t = 0;
    
    t = gcd(a, b);
    t = gcd(t, c);
    
    return t;
}

Measured memory_bytes: 3632
s = int(input())
k = 10**9+7
n = s//3
x = 0
for i in range(1,n+1):
  y = 1
  m = min(s-2*i-1,i-1)
  for j in range(m):
    y *= s-2*i-1-j
  for j in range(m):
    y //= m-j
  x = (x+y)%k
print(x)

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

int N,tmp,mincost,ans;

int main(){
  mincost = IINF, ans = -IINF;
  cin >> N;
  rep(_,N){
    cin >> tmp;
    if(mincost!=IINF)ans = max(ans,tmp-mincost);
    mincost = min(tmp,mincost);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1164
import java.util.*;

public class Main{
	int totalVertex;
	ArrayList<LinkedList<Integer>> adjList;
	
	public void loadAdjList() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjList = new ArrayList<>();
		
		for (int i = 0; i < totalVertex; i++) {
			LinkedList<Integer> neighbors = new LinkedList<>();
			in.nextInt(); // Discard node. we don't use 1 2 3 4
			int numNeighbors = in.nextInt();
			for (int j = 0; j < numNeighbors; j++) {
				neighbors.add(in.nextInt() - 1); //-1 to set index so we can start at 0 instead of -1
			}
			
			adjList.add(neighbors);
		}
		in.close();
	}
	
	public void shortestPath() {
		int[] distance = new int[totalVertex];
		boolean[] visited = new boolean[totalVertex];
		for(int i = 1; i < distance.length; i++) {
			distance[i] = Integer.MAX_VALUE; //set to a max value if it hasn't been vistied
		}
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			visited[cur] = true;
			LinkedList<Integer> neighbors = adjList.get(cur);
			for(Integer n : neighbors) {
				if(!visited[n]) {
					queue.add(n);
					distance[n] = Math.min(distance[n], distance[cur] + 1); 
				}
			}
		}
		for(int i = 0; i < distance.length; i++) {
			if(distance[i] == Integer.MAX_VALUE) {
				distance[i] = -1;
			}
			System.out.println((i + 1) + " " + distance[i]);
		}
	}
	
	public static void main(String[] args) {
		Main Graph = new Main();
		Graph.loadAdjList();
		Graph.shortestPath();
		
		
	}
}



Measured memory_bytes: 38140
#include <bits/stdc++.h>
using namespace std;
 
#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define mp make_pair
#define mod 1000000007
#define qmod 998244353
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const ll LINF = LLONG_MAX;

int main(){
  int a,b; cin>>a>>b;
    int ans=a;
    int count=1;
    if(b==1) cout<<0<<endl;
    else{
    while(ans<b){
        ans+=a;
        ans--;
        count++;
    }
    cout<<count<<endl;
    }
    return 0;  

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <cstdlib>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MAX = 100000;
#define fi first
#define se second

int main() {
    ios::sync_with_stdio(false);
    int n, k, x, y;
    int sum = 0;
    cin >> n >> k >> x >> y;
    for (int i = 1; i <= n; i++) {
        if (i <= k) sum += x;
        else sum += y;
    }
    cout << sum << endl;
    return 0;
}

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

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;

constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};

int K;
int T;

int main(){
     cin>> K>> T;
     vi a(T);
     priority_queue<pii,vector<pii>,greater<pii>> que;
     rep(i,T){
         cin>>a[i];
         que.push(pii(a[i],i));
     }
    
     sort(ALL(a));
     reverse(all(a));
     int ans=0;
     for(int i=0;i<T;i++){
         if(a[i]==0) continue;
         for(int j=i+1;j<T;j++){
             if(a[j]==0) continue;
             if(a[i]>=a[j]){
                 int t = a[j];
                 a[i] -= t;
                 a[j] = 0;
             }else{
                 int t = a[i];
                 a[i] -= t;
                 a[j] -= t;
             }
         }
     }

    rep(i,T) if(a[i]>0){
        ans += (a[i]-1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        //入れ替えを一度行うことで違反させる
        //AG GC A Cのペアが存在するとダメ
        //含むステートを列挙

        //まずAGCを全て含むパターンを列挙
        long[] states = new long[64];
        states[0] = 1;
        for (int i = 0; i < n; i++)
        {
            long[] newstates = new long[64];
            for (int j = 0; j < newstates.Length; j++)
            {
                var lastTwo = j & 15;
                var lastOne = lastTwo & 3;
                var firstTwo = j >> 2;
                var firstOne = j >> 4;
                //  t,a,g,c←last
                //t 0,1,2,3
                //a 4,5,6,7
                //g 8,9,a,b
                //c c,d,e,f
                //↑
                //second
                for (int k = 0; k < 4; k++)
                {
                    if (lastTwo == 0x6/*ag*/ && k == 3) continue;
                    if (lastTwo == 0x7/*ac*/ && k == 2) continue;
                    if (lastTwo == 0x9/*ga*/ && k == 3) continue;

                    if (firstTwo == 0x6/*ag-*/ && k == 3) continue;
                    if (firstOne == 1 && lastOne == 2/*a-g*/ && k == 3) continue;

                    var newLast = (lastTwo << 2) | (k);
                    newstates[newLast] += states[j];
                    newstates[newLast] %= 1000000007;
                }
            }
            states = newstates;
        }
        var res = states.Sum() % 1000000007;
        Console.WriteLine(res);
    }

    static long Power(long n, long m)
    {
        const int mod = 1000000007;
        long pow = n;
        long res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res = (res * pow) % mod;
            pow = (pow * pow) % mod;
            m >>= 1;
        }
        return res;
    }
}

enum Base
{
    t = 0,
    a = 1,
    g = 2,
    c = 3
}

Measured memory_bytes: 13268
#include<stdio.h>
int gcd(int a,int b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}
int main(void){
    int i,n,a;
    scanf("%d",&n);
    int ary[n];
    for(int i=0;i<n;i++)scanf("%d",&ary[i]);
    int l[n],r[n];
    l[0]=0;
    r[n-1]=0;
    for(i=1;i<n;i++){
        l[i]=gcd(l[i-1],ary[i-1]);
        r[n-i-1]=gcd(r[n-i],ary[n-i]);
    }
    int max=r[0];
    for(i=1;i<n;i++){
        a=gcd(r[i],l[i]);
        if(a>max)max=a;
    }
    printf("%d\n",max);
    return 0;
}

Measured memory_bytes: 1280
N, K = map(int,input().split())
L = []

import math

def calc_prob1(n, k):
    return (1/N) * (1/2)**(math.ceil(math.log2(k/n)))

if K == 1:
    print(1.0)
elif N < K:
    for i in range(1,N+1):
        L.append(calc_prob1(i, K))
    print(sum(L))
else:
    for i in range(1, K+1):
        L.append(calc_prob1(i, K))
    L.append((1 - K/N))
    print(sum(L))


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

using namespace std;

int main()
{
	long long ans = 0, i = 0, j = 0, k = 0, N, wl[100];
	string W[100], a[100], z[100];

	cin >> N;
	for (i; i < N; i++) {
		cin >> W[i];	wl[i] = W[i].length();
	}


	for (i = 0; i < N-1; i++) {
		for (j=i+1; j < N; j++) {
			if (W[i] == W[j]) {
				cout << "No" << endl;
				return 0;
			}
		}

		k++;
		if (W[i][wl[i] - 1] != W[k][0]) {
			cout << "No" << endl;
			return 0;
		}
	}

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

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

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    unordered_map<ll, ll> mp;
    rep(i, N){
        cin >> A[i];
        if (mp.find(A[i]) == mp.end()){
            mp[A[i]] = 1;
        }else{
            mp[A[i]] += 1;
        }
    }

    vector<pair<ll, ll>> c;
    for(auto x: mp){
        if (x.second > 1){
            c.push_back(make_pair(x.first, x.second/2));
        }
    }

    if (c.size() < 2){
        puts("0");
        return 0;
    }
    sort(c.begin(), c.end(), greater<pair<ll, ll>>());

    ll ans = 0;
    if (c[0].second > 1) {
        ans = c[0].first * c[0].first;
    }else{
        ans = c[0].first * c[1].first;
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 7980
N=int(input())
X=N*(1+N)//2
a=N//3
S3=a*(3+3*a)//2
b=N//5
S5=b*(5+5*b)//2
c=N//15
S15=c*(15+15*c)//2
print(X-S3-S5+S15)


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int n;
    cin >> n;
    int a[n];
    int ans = 1, bad=1;
    rep(i, n) {
        cin >> a[i];
        ans *= 3;
        if(a[i] % 2 == 0) bad *= 2;
    }
    cout << ans - bad << endl;
    return 0;
}

Measured memory_bytes: 3572
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<iomanip>
#include<cassert>
#include<functional>
typedef long long ll;

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	
	int all_inputs;
	ll difference;
	ll ans;
	
	std::cin >> all_inputs;
	std::vector<ll> input(all_inputs);
	std::vector<ll> current_min(all_inputs);//その時点での最小値
	for (int i = 0; i < all_inputs; i++){
		std::cin >> input[i];
		if (i == 0){
			current_min[i] = input[0];
		}
		else{
			current_min[i] = std::min(input[i], current_min[i - 1]);
		}
	}

	for (int i = all_inputs - 1; i >= 1; i--){
		if (i == all_inputs - 1){
			ans = input[i] - current_min[i - 1];
		}
		else{
			difference = input[i] - current_min[i - 1];
			ans = std::max(ans, difference);
		}
	}

	std::cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 5996
S = input()
T = input()
 
alphabet = 'abcdefghijklmnopqrstuvwxyz'
 
S_list = []
T_list = []
 
for i in alphabet:
    Scnt = S.count(i)
    Tcnt = T.count(i)
    if Scnt > 0:
        S_list.append(Scnt)
    if Tcnt > 0:
        T_list.append(Tcnt)
 
if sorted(T_list) == sorted(S_list):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3632
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
    int a,b,c;
    cin>>a>>b>>c;
    int k;
    cin>>k;
    int tot=0;
    tot=min(k,a);
    k-=tot;
    k=max(0,k-b);
    tot-=k;
    cout<<tot;
    return 0;
}

Measured memory_bytes: 3640
// D - Blue and Red Balls
#include <bits/stdc++.h>

using namespace std;

#define	MOD	1000000007
#define	N	2010

int main(int argc, char *argv[])
{
	vector<vector<long long> > C(N, vector<long long>(N));
	for (int i = 0; i < C.size(); i++) {
		C[i][i] = C[i][0] = 1;
		for (int j = 1; j <= i / 2; j++)
			C[i][j] = C[i][i - j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}

	long long n, k;
	cin >> n >> k;
	long long r = n - k;
	for (long long i = 1; i <= k; i++) {
		long long c = r - (i - 1);
		if (c < 0) {
			cout << 0 << "\n";
			continue;
		}
		long long ans = C[i + c][c] * C[k - 1][i - 1] % MOD;
		cout << ans << "\n";
	}

	return 0;
}


Measured memory_bytes: 32000
import bisect
A, B, Q = map(int, input().split())
S_list = [int(input()) for i in range(A)]
T_list = [int(input()) for i in range(B)]
X_list = [int(input()) for i in range(Q)]


# print("---------------")
for X in X_list:
    # 両側の最も近い寺、神社を調べる
    left_S_index = bisect.bisect(S_list, X)
    if left_S_index == 0:
        left_S = -10**11
    else:
        left_S = S_list[left_S_index-1]
    if left_S_index <= A-1:
        right_S = S_list[left_S_index]
    else:
        right_S = 10 ** 11

    left_T_index = bisect.bisect(T_list, X)
    if left_T_index == 0:
        left_T = -10 ** 11
    else:
        left_T = T_list[left_T_index-1]

    if left_T_index <= B-1:
        right_T = T_list[left_T_index]
    else:
        right_T = 10 ** 11

    a1 = right_T-X + abs(right_S-right_T)  # 右寺　右神社
    a2 = right_T-X + abs(left_S-right_T)  # 右寺　左神社
    a3 = X-left_T + abs(right_S-left_T)  # 左寺　右神社
    a4 = X-left_T + abs(left_S-left_T)  # 左寺　左神社
    a5 = right_S-X + abs(right_T-right_S)  # 右神社　右寺
    a6 = right_S-X + abs(left_T-right_S)  # 右神社　左寺
    a7 = X-left_S + abs(right_T-left_S)  # 左神社　右寺
    a8 = X-left_S + abs(left_T-left_S)  # 左神社　左寺

    print(min(a1, a2, a3, a4, a5, a6, a7, a8))


Measured memory_bytes: 16168
#include<bits/stdc++.h>
#include <queue>
using namespace std;
priority_queue<int > p;
int main(){
	int n,a,sum=0;
	cin>>n>>a;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x; p.push(x);
	}
	for(int i=1;i<=a;i++){
		sum+=p.top();
		p.pop();
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main()
{
	int i, Q;
	long long A, B, C, ans;
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%lld %lld", &A, &B);
		C = (long long)sqrt(A * B);
		ans = (C - 1) * 2;
		if (C * (C + 1) < A * B) ans++;
		else if (C * C == A * B) ans--;
		if (A != B) printf("%lld\n", ans);
		else printf("%lld\n", A + B - 2);
	}

	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2124
void main() {
    int[] tmp = readln.split.to!(int[]);
    int n = tmp[0], k = tmp[1];
    double prob = 1.0 / n;
    double ans = 0.0;
    foreach (i; 1 .. n+1) {
        ans += prob * 0.5 ^^ max(0, ceil(log2(k.to!double / i)));
    }
    writefln("%.12f", ans);
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.container;
import std.typecons;

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long  n, m;
    cin >> n >> m;
    
    if (n == 1 && m == 1) cout << 1 << endl;
    else if (n == 1) cout << m-2 << endl;
    else if (m == 1) cout << n-2 << endl;
    else {
        cout << (n-2) * (m-2) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //static int[] dp;
    //static decimal[,,] dp;
    //static decimal N;
    static void Main(string[] args)
    {
        // 入力
        int[] input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
        int N = input[0];
        input = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();

        int ret = input[0];

        for(int i=0; i<N-2; i++)
        {
            ret += Math.Min(input[i], input[i + 1]);
        }

        ret += input[N - 2];

        Console.WriteLine(ret + "");
    }
}


Measured memory_bytes: 13268
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
// #include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;


int main(){
  int n,r = 0;
  cin  >> n >> r;
  if(n >= 10){
    cout << r;
    return 0;
  }
  else{
    cout << r + 1000 - 100*n;
  }

 
}



Measured memory_bytes: 256
N = int(input())
*S, = list(input())
A = [chr(i) for i in range(97, 97+26)]
K = 0
for L in range(1,N):
    cnt = 0
    for alpha in A:
        if alpha in S[:L] and alpha in S[L:]:
            cnt += 1
    K = max(K,cnt)
print(K)

Measured memory_bytes: 3060
#include <stdio.h>
#include <bits/stdc++.h>
  
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
  
using namespace std;
  
const int N = 1000000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int PPP = 239;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;
  
int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    //ll TL = 2.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    string s;
    cin >> s;
    int n = sz(s);
    int last[26]; fill(last, last + 26, inf);
    int dp[n];
    repb(i, n - 1, -1)
    {
        last[s[i] - 'a'] = i;
        int p = 0;
        rep(j, 0, 26)
            if (last[j] > last[p])
                p = j;
        if (last[p] == inf)
            dp[i] = 1;
        else if (last[p] == n - 1)
            dp[i] = 2;
        else
            dp[i] = 1 + dp[last[p] + 1];
    }
    deque<int> pos[26];
    rep(i, 0, n)
        pos[s[i] - 'a'].push_back(i);
    rep(i, 0, 26)
        pos[i].push_back(inf);
    int len = dp[0], curr = 0;
    string ans;
    while (true)
    {
        int xxx = -1;
        rep(i, 0, 26)
        {
            int p = pos[i].front();
            int v;
            if (p == inf)
                v = 1;
            else if (p == n - 1)
                v = 2;
            else
                v = 1 + dp[p + 1];
            if (v == len)
            {
                xxx = i;
                break;
            }
        }
        ans += (char)('a' + xxx);
        xxx = pos[xxx].front();
        len--;
        if (len == 0)
            break;
        while (curr <= xxx)
        {
            pos[s[curr] - 'a'].pop_front();
            curr++;
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 2068
#include<bits/stdc++.h>
#define stt static
#define rg register
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define y1 substitute_of_y1
#define DEBUG(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

template<typename T> T rd(){
	T nmb=0;int sgn=0;char chr=getchar();
	while(!isdigit(chr)){if(chr=='-')sgn=1;chr=getchar();}
	while(isdigit(chr)){nmb=(nmb<<3)+(nmb<<1)+chr-'0';chr=getchar();}
	return sgn?-nmb:nmb;
}
template<typename T> void wt(T nmb){
	if(nmb>9)wt(nmb/10);
	putchar(nmb%10+'0');
}
template<typename T> void cmax(T &x,T y){x=x>y?x:y;}
template<typename T> void cmin(T &x,T y){x=x<y?x:y;}
void proc_status(){
	freopen("/proc/self/status","r",stdin);
	string chr;
	while(getline(cin,chr))
		if(chr[2]=='P'){
			cerr<<chr<<endl;
			break;
	}
}

const int N=1e4+10;
const ll inf=1e17;

int n;
ll mnx,mxx,mny,mxy;
struct node{ll x,y;}a[N];

void Init(){
	n=rd<int>();
	mnx=mny=inf,mxx=mxy=-inf;
	for(int i=1;i<=n;++i){
		a[i].x=rd<ll>(),a[i].y=rd<ll>();
		cmin(mnx,a[i].x);
		cmin(mny,a[i].y),cmax(mxy,a[i].y);
	}
	for(int i=1;i<=n;++i)
		cmax(mxx,a[i].x+a[i].y-mny);
}

bool dp[65][3][2],sum[3];
void sol(ll up,ll dn,int bs){
	cmin(dn,up);
	if(!dn){
		sum[bs]^=1;
		return;
	}
	int lim=(int)ceil(log2(dn));
	memset(dp,0,sizeof dp);
	for(int x=0;x<=lim;++x)
		for(int r=0;r<3;++r)
			for(int tp=0;tp<=1;++tp){
				if(!x){
					if((tp||(dn&1))&&(up&1)&&r==1)dp[x][r][tp]^=1;
					if(!r)dp[x][r][tp]^=1;
					continue;
				}
				if(tp||(dn&(1ll<<x))){
					dp[x][r][tp]^=dp[x-1][r][1];
					int rx=r-(1ll<<x)%3+3;
					if(rx>=3)rx-=3;
					if(up&(1ll<<x))dp[x][r][tp]^=dp[x-1][rx][tp];
				}
				else dp[x][r][tp]^=dp[x-1][r][tp];
	}
	for(int i=0;i<3;++i)
		sum[(i+bs)%3]^=dp[lim][i][0];
}
void Sol(ll l,ll r){
	sum[0]=sum[1]=sum[2]=0;
	for(int i=1;i<=n;++i){
		int bs=(a[i].x-mnx)%3+3;
		if(bs>=3)bs-=3;
		if(a[i].x<=r)sol(a[i].y-mny,r-a[i].x,bs);
		if(a[i].x<=l-1)sol(a[i].y-mny,l-1-a[i].x,bs);
	}
}
ll Getpoint(){
	ll lft=mnx,rgt=mxx;
	while(lft<rgt){
		ll mid=(lft+rgt)>>1;
		Sol(lft,mid);
		if(sum[0]||sum[1]||sum[2])rgt=mid;
		else lft=mid+1;
	}
	return lft;
}

bool check(ll x){
	bool res=0;
	for(int i=1;i<=n;++i){
		ll up=a[i].y-mny,dn=x-a[i].x;
		if(dn>=0&&(up&dn)==dn)res^=1;
	}
	return res;
}

void Solve(){
	ll x=Getpoint();
	ll lft=x,rgt=x;
	for(int i=60;~i;--i){
		if(check(lft-(1ll<<i)))lft-=(1ll<<i);
		if(check(rgt+(1ll<<i)))rgt+=(1ll<<i);
	}
	printf("%lld %lld\n",lft,mny+rgt-lft);
}

int main(){
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 512
import math
 
n = int(input())
s = 0
if n > 2:
  for p in range(1, int(math.sqrt(n)) + 1):
    t = (n - p) / p
    if t.is_integer():
      if (n // int(t)) == (n % int(t)):
        s += int(t)
  print(s)

else:
  print(0)


Measured memory_bytes: 3060
n,k = map(int,input().split())
a = list(map(int,input().split()))


s = []
ord = [-1] * (n+1)

v = 1
c = 1
l = 0
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - ord[v]
l = ord[v]

if l > k:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])
    

Measured memory_bytes: 32376
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int A,B,M;
	const long long n=1e5+10;
	int MINA=1000000000,MINB=1000000000;
	cin>>A>>B>>M;
	int a[n],b[n],x[n],y[n],c[n];
	for(int i=1;i<=A;i++)
	{
		cin>>a[i];
		if(a[i]<MINA) MINA=a[i];
	} 
	for(int i=1;i<=B;i++)
	{
		cin>>b[i];
		if(b[i]<MINB) MINB=b[i]; 
	} 
	int MIN=MINA+MINB;
	for(int i=1;i<=M;i++)
	{
		cin>>x[i]>>y[i]>>c[i];
		if(a[x[i]]+b[y[i]]-c[i]<MIN)
		{
			MIN=a[x[i]]+b[y[i]]-c[i];
		}
	}
	cout<<MIN<<endl; 
 	return 0;
}


Measured memory_bytes: 2176
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef long long ll;

int	desc(const void *a, const void *b)
{
	long *A = (long *)a;
	long *B = (long *)b;
	if (*B > *A) return 1;
	if (*B < *A) return -1;
	return 0;
}

// long deside(long *a, int n)
// {
// 	int i = 0;
// 	int max = a[0];
// 	while (i < n)
// 	{
// 		if (max < a[i])
// 		{
// 			max = a[i];
// 			a[i] = -1;
// 		}
// 		i++;
// 	}
// 	return max;
// }

// long deside2(long *a, int n)
// {
// 	int i = n - 1;
// 	int min = a[0];
// 	while (i > 0)
// 	{
// 		if (min > a[i] && a[i] != -1)
// 		{
// 			min = a[i];
// 			a[i] = -1;
// 		}
// 		i--;
// 	}
// 	return min;
// }

int main()
{
	int N;
	scanf("%d", &N);
	int n = N*3;
	long a[n];
	// long b[N + 1][4];
	int i = 0;
	while (i < n)
	{
		scanf("%ld", &a[i]);
		i++;
	}
	qsort(a, sizeof a / sizeof *a , sizeof *a, desc);
	i = 0;
	int cnt = 0;
	long ans = 0;
	while (i < n)
	{
		if (i % 2)
		{
			ans += a[i];
			cnt++;
		}
		if (cnt == N)
			break;
		i++;
	}
	printf("%ld", ans);
	return (0);
}

Measured memory_bytes: 4860
def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

def witness(a, n, t, u):
    x = pow(a, u, n)  # x0 = a^u mod nを計算
    y = x

    for _ in range(0, t):
        y = (x * x) % n

        # 法nの下での1の非自明な平方根が存在するのはnが合成数であるときに限る
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n // 2
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    if n <= 3:
        return True
    return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val)
{
    std::fill((T*)array, (T*)(array + N), val);
}

double dp[3005][3005]; // dp[i+1][j]:i枚目までのコインを投げて，j枚のコインが表になる確率
// dp[i+1][j] = dp[i][j]*(1-p[i]) + dp[i][j-1] * p[i];

int main()
{
    int N;
    cin >> N;
    Fill(dp, 0.0);
    vector<double> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }

    dp[0][0] = 1.0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i + 1; j++) {
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
            if (j != 0) {
                dp[i + 1][j] += dp[i][j - 1] * p[i];
            }
        }
    }
    double ans = 0.00;
    for (int j = (N + 1) / 2; j <= N; j++) {
        ans += dp[N][j];
    }
    cout << fixed << setprecision(9);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 74392
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-15;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}
struct Point{double x,y;};
double dis(Point a,Point b){
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point tri(Point a, Point b, Point c){
  double a1,a2,b1,b2,c1,c2;
  a1=2*(b.x-a.x);
  b1=2*(b.y-a.y);
  c1=a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y;
  a2=2*(c.x-a.x);
  b2=2*(c.y-a.y);
  c2=a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y;
  Point p;
  p.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
  p.y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
  return p;
}
int main(){
  startupcpp();
  // ll test;cin>>test;while(test--){
  ll i,j,k,l,N;
  cin>>N;
  double ans=inf,fir;
  vector<Point> v(N);
  Point x;
  rep(i,N)cin>>v[i].x>>v[i].y;
  //sort(all(v),[](auto const& a,auto const& b){if(a.x!=b.x){return a.x<b.x;}else if(a.y!=b.y){return a.y<b.y;}else{return true;}});
  rep(i,N)For(j,i+1,N){
    double res=dis(v[i],v[j])*0.5;
    fir=res;
    x.x=(v[i].x+v[j].x)/2;
    x.y=(v[i].y+v[j].y)/2;
    rep(k,N){
      if(i==k||j==k)continue;
      if(dis(x,v[k])>fir+eps){
        res=inf;
        break;
      }
    }
    chmin(ans,res);
  }
  rep(i,N)For(j,i+1,N)For(k,j+1,N){
    if((v[i].x-v[k].x)*(v[j].y-v[k].y)!=(v[i].y-v[k].y)*(v[j].x-v[k].x)){
      x=tri(v[i],v[j],v[k]);
      fir=dis(x,v[i]);
      rep(l,N){
        if(dis(x,v[l])>fir+eps){
        fir=inf;
        break;
        }
      }
      chmin(ans,fir);
    }
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-

n, a, b = map(int, input().split())
count = 0
for i in range(n+1):
        sum = 0
        x = str(i)
        for j in range(0,4):
                try:
                        sum += int(x[j])
                except IndexError:
                        pass
        if a <= sum and sum <= b:
                count += i
print(count)

Measured memory_bytes: 3188
#include <iostream>

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

int main() {
  int n, m;
  std::cin >> n >> m;

  std::cout << n * (n - 1) / 2 + m * (m - 1) / 2 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void){

    int H, W, i, j;

    while(true){

        cin >> H >> W; //???????????????????????\???

        if(H == 0 && W == 0)break; //H???W???0?????¨?????????
 
          for(j = 0;j < H;j++){

             for(i = 0;i < W;i++){

                 if(i == W - 1)cout << "#" << endl;

                 else{cout << "#";

                 }

             } //?¨???????????????????????????????

            if(j == H - 1){ cout << endl;
              
            }
 
        } //?????? ?????????????¨???????????????????
        
    }

return 0;

}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string s;
  cin >> s;
  if (s.at(0) == 'S') cout << "Cloudy" << endl;
  else if (s.at(0) == 'C') cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    
    int x;
    scanf("%d",&x);
    int ans=0;
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int k=0;k<=c;k++)
            {
                int z=500*i+100*j+50*k;
                if(z==x)
                ans++;
            }
        }
    }
    cout<<ans;
    
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
using ll = long long;
int main(){
    ll n,m;
    cin >> m >> n;
    ll left=1,right=m;
    for(ll i=0;i<n;i++){
        ll l,r;
        cin >> l >> r;
        left = max(left,l);
        right = min(right,r);
    }
    ll ans = right-left+1;
    if(ans<0)  ans=0;
    cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,k;
    cin >> n >> k;
    ll ans = 0;
    rep2(b,1,n+1) {
        if(b <= k) continue;
        ans += n/b*(b-k);
        if(k == 0) ans--;
        ans += max(0,n%b-k+1);
    }
    cout << ans << endl;
}


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

int n, deg[101000];
vector<int>G[101000];

queue<int>q;

int main(){
  cin.tie(0); int x,y;
  cin>>n;
  for (int i=n-1;i--;){
    cin>>x>>y; ++deg[x]; ++deg[y];
    G[x].push_back(y); G[y].push_back(x);
  }
  for (int i=1;i<=n;++i) if (deg[i]==1) q.push(i);
  
  for (;!q.empty();){
    x=q.front(); deg[x]=0; q.pop();
    for (auto y:G[x])
      if (deg[y]>0){
        deg[y]=0;
        for (auto z:G[y]){
          if (!--deg[z]) return puts("First"), 0;
          if (deg[z]==1) q.push(z);
        }
      }
  }
  puts("Second");
}

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

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

	int n, m;

	cin >> n >> m;
	vector<int> v(m);
	rep(i, n)
	{
		int k;

		cin >> k;
		rep(j, k)
		{
			int a;

			cin >> a;
			v.at(a - 1)++;
		}
	}
	int count;
	count = 0;
	rep(i, m)
	{
		if (v.at(i) == n)
			count++;
	}
	cout << count << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

void call(int n)
{
	int i = 1;
	int x;

	do {
		x = i;
		if (x % 3 == 0) {
			printf(" %d", i);
		}
		else {
			do {
				if (x % 10 == 3) {
					printf(" %d", i);
					x = 0;
				}
				else x /= 10;
			} while (x);
		}
	} while (++i <= n);
	putchar('\n');
}

#if 1
int main()
{
	int n;

	scanf("%d", &n);
	call(n);
	return 0;
}
#endif


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;

int main() {
  int N, X; cin >> N >> X;
  vi m(N); rep(i,N) cin >> m.at(i);
  
  int S = accumulate(all(m),0);
  int M = *min_element(all(m));
  
  int ans = N + (X-S)/M;
  cout << ans << endl;
}

Measured memory_bytes: 256