akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N , K;
    cin >> N >> K;
    int list[N];
    for(int i = 0; i<N; i++) cin >> list[i];

    int dp[N];
    dp[0] = 0;
    dp[1] = abs(list[0] - list[1]);

    for (int i = 2; i<N; i++) {
        int base = 999999999;
        for(int j = 1; j <= K; j++) {
            if(i - j >= 0) base = min(base, dp[i - j] + abs(list[i] - list[i - j]));
        }
        dp[i] = base;
    }

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

Measured memory_bytes: 1024
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np
 
def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
# N!を素因数分解したときの指数
e = [0] * (N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j

def num(m):
    cnt = 0
    for ei in e:
        if ei >= m-1:
            cnt += 1
    return cnt

print(num(75) + \
      num(25) * (num(3) - 1) + \
      num(15) * (num(5) - 1) + \
      num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Measured memory_bytes: 38512
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);

int main() {
	char s;
	cin >> s;

	if ('A' <= s && s <= 'Z') {
		cout << "A\n";
	}
	else {
		cout << "a\n";
	}

	return 0;
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        string S; cin >> S;
        vector<string> A = {"Sunny", "Cloudy", "Rainy"};
        rep(i, 3) {
            if(A[i] == S) {
                cout << A[(i + 1) % 3] << endl;
                break;
            }
        }

        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

int s[50];

int main()
{
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> a >> b;
		s[a]++;
		s[b]++;
	}
	for (int i = 1; i <= n; ++i)
		cout << s[i] << "\n";
}

Measured memory_bytes: 256
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use smallvec::alloc::collections::VecDeque;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let mut a = Vec::with_capacity(n);
    for _ in 0..n {
        let ai = sc.next_usize();
        a.push(ai);
    }
    
    let mut b = VecDeque::with_capacity(n);
    for i in 0..n {
        if i % 2 == 0 {
            b.push_back(a[i]);
        } else {
            b.push_front(a[i]);
        }
    }
    
    if n % 2 != 0 {
        b = b.into_iter().rev().collect();
    }
    
    println!("{}", b.into_iter().join(" "));
}

pub struct Scanner {
    buf: std::collections::VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: std::collections::VecDeque::new(),
        }
    }
    
    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }
            
            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }
    
    pub fn next<T: std::str::FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }
    
    pub fn next_usize(&mut self) -> usize {
        self.next()
    }
    
    pub fn next_isize(&mut self) -> isize {
        self.next()
    }
    
    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }
    
    pub fn next_string(&mut self) -> String {
        self.next()
    }
    
    pub fn next_char(&mut self) -> char {
        self.next()
    }
    
    pub fn next_float(&mut self) -> f64 {
        self.next()
    }
}


Measured memory_bytes: 16836
use std::io::*;
use std::str::FromStr;

#[test]
fn test() {
    assert_eq!(red_or_not(3200, &"pink".to_string()), "pink".to_string());
    assert_eq!(red_or_not(3199, &"pink".to_string()), "red".to_string());
    assert_eq!(red_or_not(4049, &"red".to_string()), "red".to_string());
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
            .bytes()
            .map(|c| c.expect("failed to read char") as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
    token.parse().ok().expect("failed to parse token")
}

fn red_or_not(a: u32, s: &String) -> String {
    if a < 3200 {
        return "red".to_string();
    }
    s.to_string()
}

fn main() {
    let a: u32 = read();
    let s: String = read();
    println!("{}", red_or_not(a, &s));

}



Measured memory_bytes: 4352
loop do
  n,k = gets.split(" ").map(&:to_i)
  break if n == 0 && k == 0
  a = Array.new(n) {gets.to_i}
  sum = 0
  0.upto(k-1) {|i| sum += a[i]}
  max = sum

  (k).upto(n-1) do |i|
    sum -= a[i-k]
    sum += a[i]
    max = sum if max < sum
  end

  puts max
end

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

int main() {
    int K;
    cin >> K;

    vector<vector<vector<string>>> num(10, vector<vector<string>>(10, vector<string>()));
    for (int i = 0; i <= 9; i++) {
        num[0][i].push_back(to_string(i));
    }
    for (int n = 1; n < 10; n++) {
        for (ll i = 0; i <= 9; i++) {
            if (i - 1 >= 0) {
                for (string m : num[n - 1][i - 1]) {
                    string nxt = to_string(i) + m;
                    num[n][i].push_back(nxt);
                }
            }
            for (string m : num[n - 1][i]) {
                string nxt = to_string(i) + m;
                num[n][i].push_back(nxt);
            }
            if (i + 1 <= 9) {
                for (string m : num[n - 1][i + 1]) {
                    string nxt = to_string(i) + m;
                    num[n][i].push_back(nxt);
                }
            }
        }
    }

    int cnt = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
            for (string a : num[i][j]) {
                cnt++;
                if (cnt == K) {
                    cout << a << endl;
                    return 0;
                }
            }
        }
    }
}


Measured memory_bytes: 13032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long> vl;

ll solve(int N, int K, vi& t, vi& d){
  map<int, vi> sushi_list;
  for (int i=0;i<N;i++){
    sushi_list[t[i]].push_back(d[i]);
  }

  vi head, tail;
  for(auto p:sushi_list){
    sort(p.second.begin(), p.second.end());
    head.push_back(p.second.back());

    p.second.pop_back();

    tail.insert(tail.end(), p.second.begin(), p.second.end());
  }

  sort(head.begin(), head.end(), greater<int>());
  sort(tail.begin(), tail.end(), greater<int>());

  int H=head.size();
  int T=tail.size();
  vl head_cum(H+1);
  vl tail_cum(T+1);

  head_cum[0]=0;
  tail_cum[0]=0;

  for (int i=1;i<H+1;i++){
    head_cum[i]=head_cum[i-1]+head[i-1];
  }
  for (int i=1;i<T+1;i++){
    tail_cum[i]=tail_cum[i-1]+tail[i-1];
  }

  ll best=0;
  for (int n_unique=1;n_unique<=H;n_unique++){
    if(n_unique<=K&&K-n_unique<=T){
      ll tmp=head_cum[n_unique]+tail_cum[K-n_unique]+(ll)n_unique*n_unique;
      best=max(best, tmp);
    }
  }
  return best;
}

int main(){
  int N, K;cin>>N>>K;
  vi t, d;
  for (int i=0;i<N;i++){
    int t_, d_;cin>>t_>>d_;
    t.push_back(t_);
    d.push_back(d_);
  }
  cout<< solve(N, K, t, d);
  return 0;
}


Measured memory_bytes: 13300
program name

    implicit none
    character(len=1) r,g,b
    character(len=3) rgb
    integer rgb_int,i
    logical flg
    flg = .False.
    read*, r,g,b
    rgb = r//g//b
    read (rgb,*) rgb_int
do i = 112, 999, 4
    if ( rgb_int==i ) then
        flg = .True.
        print*, "YES"
        exit
    end if
end do

if ( .not. flg ) then
    print*, "NO"
end if
end program

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    char c;
    int n,i,j,x,card[4][14];
    for(i=0;i<4;i++)
    {
        for(j=1;j<=13;j++)
        {
            card[i][j]=0;
        }
    }
    scanf("%d",&x);
    for(i=0;i<x;i++)
    {
        scanf(" %c %d",&c,&n);
        if(c=='S')
        {
            card[0][n] = 1;
        }
        else if(c=='H')
        {
            card[1][n] = 1;
        }
        else if(c=='C')
        {
            card[2][n] = 1;
        }
        else if(c=='D')
        {
            card[3][n] = 1;
        }
    }
    for(i=1;i<=13;i++)
    {
        if(card[0][i]!=1)
        {
            printf("S %d\n",i);
        }
    }
    for(i=1;i<=13;i++)
    {
        if(card[1][i]!=1)
        {
            printf("H %d\n",i);
        }
    }
    for(i=1;i<=13;i++)
    {
        if(card[2][i]!=1)
        {
            printf("C %d\n",i);
        }
    }
    for(i=1;i<=13;i++)
    {
        if(card[3][i]!=1)
        {
            printf("D %d\n",i);
        }
    }

    return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    int aj = 1000;
    int sum = 0;
    for(int i=0; i<N; i++){
        int s; cin >> s;
        if(s%10 != 0) aj = min(aj, s);
        sum += s;
    }

    if(sum%10 == 0){
        if(aj == 1000) cout << 0 << endl;
        else cout << sum - aj << endl;
    }
    else cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int main()
{
    cin>>n>>s;
    int w=0,r=0;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='W') w++;
        //else if(s[i]=='R') r++; 
    }
    int cnt=0;
    //cout<<w<<endl;
    //cout<<n-w<<endl;
    for(int i=n-1;i>=n-w;--i)
    {
        if(s[i]=='R') cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 3716
x, n = map(int, input().split())
p = list(map(int, input().split()))
np =[0]*102 

for i in p:
    np[i] = 1

dist = 1000
ans = 1000
for i in reversed(range(102)):
    if np[i] == 0:
        if abs(x-i) <= dist:
            dist = abs(x-i)
            ans = i
    
print(ans)

Measured memory_bytes: 9172
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
#include<set>
using namespace std;


const long long int mod=1000000007;
const long long int INF=99999999999999999;


//セグメント木
class SegmentTree{
    public:
	long long int dataSize,identityElement;
	pair<long long int,long long int>* treeDataRange;
	long long int* treeData;

	//要素数nと単位元e
	SegmentTree(long long int n,long long int e){
		dataSize=2;
		while(dataSize<n){
			dataSize*=2;
		}
		identityElement=e;
		treeData=new long long int [2*dataSize+1];
		treeDataRange=new pair<long long int,long long int> [2*dataSize+1];
		for(int i=dataSize;i<2*dataSize;i++){
			treeDataRange[i]={i-dataSize,i-dataSize+1};
		}
		for(int i=dataSize-1;i>=1;i--){
			treeDataRange[i]={treeDataRange[2*i].first,treeDataRange[2*i+1].second};
		}
		for(int i=1;i<2*dataSize;i++){
			treeData[i]=e;
		}
	}

    long long int DataChange(long long int id,long long int data){
        treeData[id+dataSize]=data;
        DataChangeLoop((id+dataSize)/2);
    }
    long long int DataChangeLoop(long long int id){
        treeData[id]=Calculation(treeData[2*id],treeData[2*id+1]);
        if(id==1){return 0;}
        DataChangeLoop(id/2);
    }

	long long int Calculation(long long int x,long long int y){
		return x+y;
	}
	//[l,r)の結果を出力
	long long int OutPut(long long int l,long long int r){
		return OutPutLoop(1,l,r);
	}
	
	long long int OutPutLoop(long long int now,long long int l,long long int r){
		
		if(l>=r){return identityElement;}

        if(l==treeDataRange[now].first&&r==treeDataRange[now].second){return treeData[now];}

		return Calculation(OutPutLoop(2*now,l,min(treeDataRange[2*now].second,r)),OutPutLoop(2*now+1,max(treeDataRange[2*now+1].first,l),r));
		
	}
};

int main() {
	cout << fixed << setprecision(18);
    long long int n,e,q,com,x,y;
    cin>>n>>q;
    SegmentTree seg(n,0);
    for(int i=0;i<q;i++){
        cin>>com>>x>>y;
        if(com==0){seg.DataChange(x-1,y+seg.treeData[seg.dataSize+x-1]);}
        else{cout<<seg.OutPut(x-1,y)<<endl;}
    }
    
} 



Measured memory_bytes: 9280
#include <stdio.h>
#define NUMBER 1000
int main(void)
{
	int i,n;
	int a[NUMBER];
	
	scanf ("%d",&n);
	
	for (i = 0; i < n; i++) {
		scanf ("%d",&a[i]);
	}
	for (i = 0; i < (n/2); i++) {
		int temp = a[i];
		a[i] = a[(n-1)-i];
		a[(n-1)-i] = temp;
	}
	for (i =0; i < n-1; i++) {
		printf ("%d ",a[i]);
	}
	int P = a[n-1];
	printf ("%d\n",P);
	
	return 0;
}

Measured memory_bytes: 600
L,R = map(int,input().split())
# R-LはLからRまでの個数を表す
#解の最小は０であり、LからRまでに2019の倍数が存在すればよい
# R-L > 2018ならRからLに2019の倍数が出てくることになる
if R - L >= 2018:
    print(0)
else:
    ans = 2019
    #iとj=i+1でi*jmod2019の最小値を全探索
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = min(ans,i*j % 2019)
    print(ans)

Measured memory_bytes: 40684
from collections import Counter
N,K,Q=map(int,input().split())
a=[]
for q in range(Q):
  a.append(int(input()))
C=Counter(a)
for i in range(N):
  if i+1 in C.keys():
    if K-Q+C[i+1]>0:
      print("Yes")
    else:
      print("No")
  else:
    if K-Q>0:
      print("Yes")
    else:
      print("No")

Measured memory_bytes: 11904
#include <iostream>
#include<math.h>
using namespace std;


unsigned GetDigit(unsigned num);

int main() {
    int n, ans;
    cin >> n;

    for(int i=1; i<=n; i++) {
        int tmp = GetDigit(i)%2;
        if (tmp == 1) {
            ans++;
        };
    };

    cout << ans << endl;
}

unsigned GetDigit(unsigned num) {
    return to_string(num).length();
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

const int MX=1003;
int a[MX];

int main()
{
    int n,k,ans=0;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<k;i++) ans+=a[i];
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 3828
object Main {
  def main(args: Array[String]): Unit = {
    val _ = io.StdIn.readLine()
    val d = io.StdIn.readLine().split(" ").map(_.toLong) zip io.StdIn.readLine().split(" ").map(_.toLong) map { case (x, y) => Math.abs(x - y) }

    println(f"${d.sum.toDouble}%.8f")
    println(f"${Math.sqrt(d.map(v => v * v).sum)}%.8f")
    println(f"${Math.cbrt(d.map(v => v * v * v).sum)}%.8f")
    println(f"${d.max.toDouble}%.8f")
  }
}

Measured memory_bytes: 44448
#include<stdio.h>
int main()
{
	int a, b, c, i;
	scanf("%d%d%d", &a, &b, &c);
	for (a; a <= b; a++) {
		if (c%a == 0)
			i++;
	}
	printf("%d\n", i);
	return 0;
}

Measured memory_bytes: 596
#include<stdio.h>
int n,a[50];
int solve(int i,int m)
{  int res;
   if(m==0)  return 1;
   if(i>=n)  return 0;  
   res=solve(i+1,m)||solve(i+1,m-a[i]);
   return res;
}
int main()
{  int q,m,i;
   scanf("%d",&n);
   for(i=0;i<n;i++)
     scanf("%d",&a[i]);
   scanf("%d",&q);
   for(i=0;i<q;i++)
   {  scanf("%d",&m);
      if(solve(0,m))  printf("yes\n");
      else printf("no\n");
   }
   return 0;  
}  


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

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9+7

dp = [[0 for _ in range(N+1)] for _ in range(M+1)]

for i in range(M):
    for j in range(N):
        if S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] + 1
        else:
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
        dp[i+1][j+1] %= mod

ans = (dp[M][N] + 1) % mod
print(ans)

Measured memory_bytes: 75100
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, count=0;
    cin >> n;
    
    int p[n];
    for (int i=0; i < n; i++) cin >> p[i];
    
    
    for (int j=0; j < n; j++) {
        if (p[j] != j+1) {
            count++;
        }
    }
    
    if(count == 0 || count == 2) {
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    
    
}


Measured memory_bytes: 256
import sys

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def main():
    while True:
        map = []
        count = 0
        for i in range(12):
            map.append([x for x in input()])

        for i in range(12):
            for j in range(12):
                if map[i][j] == '1':
                    dfs(map, j, i)
                    count += 1
        print(count)

        if not sys.stdin.readline():
            break


def dfs(map, x, y):
    if x < 0 or y < 0 or x >= 12 or y >= 12:
        return

    map[y][x] = '0'
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x >= 0 and next_x < 12 and next_y >= 0 and next_y < 12:
            if map[next_y][next_x] == '1':
                dfs(map, next_x, next_y)


if __name__ == '__main__':
    main()

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

long long gcd(long long a, long long b) {
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

void solve(long long N, long long X, std::vector<long long> x){
  sort(x.begin(), x.end(), [&](auto a, auto b){ return abs(X - a) < abs(X - b); });

  long long acc = abs(X - x[0]);

  for(long long i = 1; i < N; i++){
    acc = gcd(acc, abs(X - x[i]));
  }

  cout << acc << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  long long X;
  scanf("%lld",&X);
  std::vector<long long> x(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&x[i]);
  }
    solve(N, X, std::move(x));
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

typedef long long signed int ll;

ll a[510];
int h;

void rk(int n) {
    if(a[n*2+1]) cout << "right key = " << a[n*2+1] << ", ";
}
void lk(int n) {
    if(a[n*2]) cout << "left key = " << a[n*2] << ", ";
}
void pk(int n) {
    if(a[n/2]) cout << "parent key = " << a[n/2] << ", ";
}

void print(int n){
    cout << "node " << n << ": key = " << a[n] << ", ";
    pk(n);lk(n);rk(n);
    cout << endl;
}

int main() {
    cin >> h;
    for (int i = 1; i <= h; i++) cin >> a[i];
    for (int i = 1; i <= h; i++) print(i);
    return 0;
}


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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	string s;
	cin >> s;

	bool f = true;
	string t = "";
	for(int i=s.size()-1; i>=0; i--){
		t += s[i];
		if(t.size() == 5){
			reverse(t.begin(), t.end());
			if(i-2 >= 0 && t == "eamer"){
				if(s[i-1] == 'r' && s[i-2] == 'd'){
					i-=2;
				}else{
					f = false;
					break;
				}
			}else if(i-1 >= 0 && t == "raser"){
				if(s[i-1] == 'e'){
					i--;
				}else{
					f = false;
					break;
				}
			}else if(t != "dream" && t != "erase"){
				f = false;
				break;
			}
			t = "";
		}
	}

	if(f) puts("YES");
	else puts("NO");


	

	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<boost/algorithm/string/replace.hpp>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::algorithm;
using namespace boost::multiprecision;
 
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1LL<<60;
const int MOD = 1e9+7;

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; }
//C++17以上
template<typename T>
T GCD(T a,T b){ return b ? GCD(b,a%b) : a ;}
template<typename T>
T LCM(T a,T b){ return a*b / GCD(a,b) ;}

template<typename T>//文字列の置換/Boost:replace_all()
T replace_str(T str, string target, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(target, pos), pos != string::npos) {
        str.replace(pos, target.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main() {
    int n,d;cin >> n >> d;
    vector<vector<int>> x(n,vector<int>(d));
    rep(i,n)rep(j,d)cin>>x[i][j];
    int ans = 0;
    rep(i,n-1){
        for(int j=i+1;j<n;j++){
            double tmp = 0.0;
            rep(k,d){
                tmp += abs(x[i][k]-x[j][k])*abs(x[i][k]-x[j][k]);
            }
            if(floor(sqrt(tmp)) == ceil(sqrt(tmp)))ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define NMAX 1000
#define WMAX 10000

int mincost(short *, int, int);

int main(){

  int i, j, n, d, wtemp, wmin=WMAX, cost=0;
  short w[NMAX], s[NMAX], l[NMAX];
  char c[WMAX+1]={0}, flag[NMAX]={0};

  scanf("%d",&n);

  for (i=0; i<n; i++) {
    scanf("%d",&w[i]);
    if (wmin > w[i]) wmin = w[i];
    c[w[i]]++;
  }

  j=0;

  for (i=0; i<=WMAX; i++) {
    if(c[i]) {
      s[j] = i;
      j++;
    }
  }

  for (i=0; i<n; i++) {
    if( flag[i]==0 ) {
      d = 0;
      flag[i]++;
      l[d] = w[i];
      d++;
      wtemp = w[i];
      while (1) {
        j = 0;
        while (s[j] != wtemp) j++;
        if(j == i) break;
        flag[j]++;
        l[d] = w[j];
        d++;
        wtemp = w[j];
      }
      cost += mincost(l, d, wmin);
    }
  }

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

  return 0;
}

int mincost(short *l, int d, int wmin)
{
    int i, c1=0, c2, lmin=WMAX, imin;

    for (i=0; i<d; i++) {
        c1 += l[i];
        if(lmin > l[i]) {
            lmin = l[i];
        }
    }

    c2 = c1;
    c1 += (d-2)*lmin;
    c2 += lmin + (d+1)*wmin;

    if (c1 < c2) return c1;
    else return c2;
}

Measured memory_bytes: 2772
n=int(input())
c=input()
a=0
i=0
j=len(c)-1
while(i<j):
  while(c[i]=="R" and i<j):
      i+=1
  while(c[j]=="W" and i<j):
      j-=1
  if i<j:
    a+=1
    i+=1
    j-=1
print(a)  

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

string replace(string str)
{
	int a, b;
	string p;
	cin >> a >> b >> p;
	for(int i = 0; i <= b-a; ++i){
		str[a+i] = p[i];
	}
	return str;
}
string reverse(string str)
{
	int a, b;
	cin >> a >> b;
	string result = str;
	for(int i = 0; i <= b-a; i++){
		result[a+i] = str[b-i];
	}
	return result;
}
string print(string str)
{
	int a, b;
	cin >> a >> b;
	for(int i = 0; i <= b-a; i++){
		cout << str[a+i];
	}
	cout << endl;
	return str;
}

string execCommand(string command, string str)
{
	if(command == "replace") return replace(str);
	if(command == "reverse") return reverse(str);
	if(command == "print")   return print(str);
}
int main()
{
	string str;
	int q;
	cin >> str >> q;
	for(int i = 0; i < q; i++){
		string command;
		cin >> command;
		str = execCommand(command, str);
	}
	return 0;
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define ll long long

#define TASKNAME ""

using namespace std;

const ll INF = 1e9 + 7;
const ll MAXN = 1e6 + 7;
const double EPS = 1e-8;

int main() {
    #ifdef MY
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #else
        //freopen(TASKNAME".in", "r", stdin);
        //freopen(TASKNAME".out", "w", stdout);
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    #endif // MY
    ll n;
    cin >> n;
    ll sum = 0;
    vector <ll> a(n + 2, 0);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += abs(a[i] - a[i - 1]);
    }
    sum += abs(a[n]);
    for (ll i = 1; i <= n; i++) {
        ll sum1 = sum;
        sum1 -= abs(a[i - 1] - a[i]);
        sum1 -= abs(a[i] - a[i + 1]);
        sum1 += abs(a[i - 1] - a[i + 1]);
        cout << sum1 << "\n";
    }
}


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

int No(){
	cout << "No" << endl;
	return 0;
}

int main(){
	int H,W;
	cin >> H >> W;
	vector<string> S(H);
	for(auto &i:S)cin >> i;
	
	vector<int> count(26,0);
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)count[S[i][j]-'a']++;
	
	if((H*W)%2==1){
		for(int i=0;i<26;i++){
			if(count[i]%2==1){
				count[i]--;
				break;
			}
			if(i==25)return No();
		}
	}
	
	for(int k=0;k<(H/2)*(W/2);k++){
		for(int i=0;i<26;i++){
			if(count[i]>=4){
				count[i]-=4;
				break;
			}
			if(i==25)return No();
		}
	}
	
	if(H%2==1){
		for(int k=0;k<W/2;k++){
			for(int i=0;i<26;i++){
				if(count[i]>=2){
					count[i]-=2;
					break;
				}
				if(i==25)return No();
			}
		}
	}
	
	if(W%2==1){
		for(int k=0;k<H/2;k++){
			for(int i=0;i<26;i++){
				if(count[i]>=2){
					count[i]-=2;
					break;
				}
				if(i==25)return No();
			}
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}

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

void main_()
{
    int A, B, K;
    cin >> A >> B >> K;

    if (B - A + 1 > K * 2) {
        for (int i = A; i < A + K; ++i) {
            cout << i << "\n";
        }
        for (int i = B - K + 1; i <= B; ++i) {
            cout << i << "\n";
        }
    } else {
        for (int i = A; i <= B; ++i) {
            cout << i << "\n";
        }
    }
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define debug int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<int> VE;
const ll mod = 1e9 + 7; //10^9+7

int main(){
    int n, m, x, y;
    VE X;
    VE Y;
    cin >> n >> m >> x >> y;
    int q, p;
    REP(i, n){
        cin >> q;
        X.push_back(q);
    }
    REP(i, m){
        cin >> p;
        Y.push_back(p);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    int z = X[n - 1] + 1;
    if(z <= Y[0] && z > X[n-1] && z <= y && x < z){
        print("No War");
    }else{
        print("War");
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                                                                                               
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
#define mk_p(a,b)   make_pair((a),(b))
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

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

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string q,e;
    cin >> q >> e;
    int nq = q.size();
    int ne = e.size();
    rep(i,nq){
        cout << q[i];
        if(ne > i) cout << e[i];
    }   
    cout << '\n';
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
c = 0
k = True

while k:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            k = False

    if k:
        c += 1

print(c)

Measured memory_bytes: 2940
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace contest
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            int n = s.Length;
            for (int i = 0; i < n - 1; i++)
            {
                if (s[i] == s[i + 1])
                {
                    Console.WriteLine("{0} {1}", i + 1, i + 2);
                    return;
                }
            }
            for (int i = 0; i < n - 2; i++)
            {
                if (s[i] == s[i + 2])
                {
                    Console.WriteLine("{0} {1}", i + 1, i + 3);
                    return;
                }
            }
            Console.WriteLine("-1 -1");
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13140
#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;
    cin >> N;
    vector<ll> a(N);

    ll res = 0;
    rep(i, N) {
        cin >> a[i];
        ll temp = 0;
        while(a[i]%2 == 0) {
            a[i] /=2;
            temp++;
        }
        res += temp;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
n = list(input())
digit = len(n)


s1 = ['0']
s2 = ['1']
for i in range(2,digit+1):
  if i%2==0:
    s1.append('1')
    s2.append('0')
  else:
    s1.append('0')
    s2.append('1')
count1 = 0
count2 = 0
for i in range(digit):
  if n[i]!=s1[i]:
    count1 += 1
  if n[i]!=s2[i]:
    count2 += 1
print(min(count1,count2))

Measured memory_bytes: 5540
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    int m,a,b,c,d;
    int ans;

    cin >> m;
    a = m / 1000;
    b = (m - 1000*a) / 100;
    c = (m - 1000*a- 100*b) / 10;
    d = m - 1000*a - 100*b - 10*c;


    ans = a + b + c + d;
    if(ans ==7){
        cout << a << '+' << b << '+' << c << '+' << d << "=7" << endl;
        return 0;
    }

    ans = a - b + c + d;
    if(ans ==7){
        cout << a << '-' << b << '+' << c << '+' << d << "=7" << endl;
        return 0;
    }

    ans = a + b - c + d;
    if(ans ==7){
        cout << a << '+' << b << '-' << c << '+' << d << "=7" << endl;
        return 0;
    }

    ans = a + b - c - d;
    if(ans ==7){
        cout << a << '+' << b << '-' << c << '-' << d << "=7" << endl;
        return 0;
    }

    ans = a + b + c - d;
    if(ans ==7){
        cout << a << '+' << b << '+' << c << '-' << d << "=7" << endl;
        return 0;
    }

    ans = a - b + c - d;
    if(ans ==7){
        cout << a << '-' << b << '+' << c << '-' << d << "=7" << endl;
        return 0;
    }

    ans = a - b - c - d;
    if(ans ==7){
        cout << a << '-' << b << '-' << c << '-' << d << "=7" << endl;
        return 0;
    }

    ans = a - b - c + d;
    if(ans ==7){
        cout << a << '-' << b << '-' << c << '+' << d << "=7" << endl;
        return 0;
    }

}

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

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if((a==1&&b==2)||(a==2&&b==1))
        printf("3");
    else if((a==1&&b==3)||(a==3&&b==1))
        printf("2");
    else if((a==2&&b==3)||(a==3&&b==2))
        printf("1");
}


Measured memory_bytes: 128
<?php
fscanf(STDIN, "%d", $N);
$ans = 0;
if ($N % 2 === 0) {
    $b = 10;
    while($b < PHP_INT_MAX) {
        $ans += intdiv($N, $b);
        $b *= 5;
    }
}
printf("%d", $ans);


Measured memory_bytes: 4856
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define LL long long
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int main(){
  int N,M;
  string S;
  vector<string> B,R;
  cin>>N;
  FOR(i,0,N){
    cin>>S;
    B.PB(S);
  }
  cin>>M;
  FOR(i,0,M){
    cin>>S;
    R.PB(S);
  }
  int ans=0;
  FOR(i,0,N){
    S=B[i];
    int cnt=0;
    FOR(j,0,N){
      if(S==B[j]){
        cnt++;
      }
    }
    FOR(j,0,M){
      if(S==R[j]){
        cnt--;
      }
    }
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(void){
    int X,n,i,j,max=1;
    scanf("%d",&X);
    for(n=1;n<=X;n++){
        for(i=2;i<X;i++){
            j=pow(n,i);
            if(j<=X){
                if(max<j){
                    max=j;
                }
            }
            else{
                break;
            }
        }
    }
    printf("%d\n",max);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define F first
#define S second
#define pss pair<string,string>
#define pcc pair<char,char>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define vs vector<string>
#define vl vector<ll>
#define vs vector<string>
#define vll vector<pll>
#define vss vector<pss>
#define vcc vector<pcc>
#define MP make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define Very_fast std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int N = 1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
inline ll gcd(ll a,ll b){if(b==0)return a;else return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll lowbit(ll x){return (x&-x);}
int n,m,p,x[N],y[N],a[N],b[N],c,ans=1e9;
int main()
{
	cin>>n>>m>>p;
	rep(i,n)cin>>x[i];
	rep(i,m)cin>>y[i];
	rep(i,p)cin>>a[i]>>b[i]>>c,a[i]--,b[i]--,ans=min(ans,x[a[i]]+y[b[i]]-c);
	sort(x,x+n);
	sort(y,y+m);
	ans=min(ans,x[0]+y[0]);
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 1792
def main():
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))
    mod = sum(xy[0]) % 2
    for x, y in xy:
        if (x + y) % 2 != mod:
            print(-1)
            exit()
    print(33 - mod)
    D = [2 ** i for i in range(31, -1, -1)]
    if mod == 0:
        D.append(1)
    print(' '.join(map(str, D)))

    for x, y in xy:
        temp = []
        for d in D:
            if x >= y and x + y >= 0:
                temp.append("R")
                x -= d
            elif x < y and x + y >= 0:
                temp.append("U")
                y -= d
            elif x >= y and x + y < 0:
                temp.append("D")
                y += d
            else:
                temp.append("L")
                x += d
        print(''.join(temp))


main()


Measured memory_bytes: 3188
#include<cstdio>
#include<iostream>

#include<algorithm>
using namespace std;
int main()
{
  int x,a,b,c,n=0;
  cin>>a>>b>>c>>x;
  for(int i=0;i<=a;i++)
    for(int j=0;j<=b;j++)
    for(int k=0;k<=c;k++)
    if(i*500+j*100+k*50==x)
    n+=1;
  cout<<n;
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.lang.*;
import java.util.*;

class Main {

   
    public static void main(String[] args) {
         Scanner input = new Scanner(System.in);
         int A = input.nextInt();
         int B = input.nextInt();
         int C = input.nextInt();
         
         int N = A-B;
         int count = C-N;
         if(count < 0)
         {
             System.out.println("0");
         }
         else
         {
             System.out.println(count);
         }
         
    }
    
}


Measured memory_bytes: 20820
N=int(input())
M=[]
A=[]
R=[]
C=[]
H=[]

for i in range(N):
    tmp=input()
    if tmp[0]=="M":
        M.append(tmp)
    elif tmp[0]=="A":
        A.append(tmp)
    elif tmp[0]=="R":
        R.append(tmp)
    elif tmp[0]=="C":
        C.append(tmp)
    elif tmp[0]=="H":
        H.append(tmp)

m=len(M)
a=len(A)
r=len(R)
c=len(C)
h=len(H)

if len(M)+len(A)+len(R)+len(C)+len(H)<=2:
    print(0)
else:
    print(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*c*h+ a*r*h+r*c*h)

Measured memory_bytes: 16608
#include <iostream>                                             
using namespace std;                                            
                                                                
int main() {                                                    
  for (int i=1; i<10; i++) {                                    
    for (int j=1; j<10; j++) {                                  
      int QQ = i*j;                                             
      cout << i << "x" << j << "=" << QQ << endl;               
    }                                                           
  }                                                             
  return 0;                                                     
}                       

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>

using namespace std;

int main(void){
    int a,b;
    cin >> a;
    cin >> b;
    int d = a / b;
    int r = a % b;
    double f = double(a) / double(b);
    cout << d;
    cout << " ";
    cout << r;
    cout << " ";
    cout << fixed << setprecision(5) << f;
    cout << endl;
}



Measured memory_bytes: 3284
#include<cstdio>
#include<iostream>
using namespace std;
int a[11];
int main()
{
	int i,max1=-1,max2=-1,max3=-1;
	for(i=1;i<=10;i++)
	{
		cin>>a[i];
		if(a[i]>max1){max3=max2;max2=max1;max1=a[i];}
		else if(a[i]>max2){max3=max2;max2=a[i];}
		else if(a[i]>max3)max3=a[i];
	}
	cout<<max1<<endl<<max2<<endl<<max3<<endl;
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pint;
#define ms(arr) memset(arr,0,sizeof(arr))


int main() {
    int n;
    cin>>n;
    int ans=3*n*n;
    cout<<ans;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	P := make([]float64, N)
	for i := 0; i < N; i++ {
		P[i] = sc.nextFloat()
	}
	dp := make([][]float64, N+1)
	for i := 0; i <= N; i++ {
		dp[i] = make([]float64, N+1)
	}
	dp[0][0] = 1
	for i := 0; i < N; i++ {
		for j := 0; j <= N; j++ {
			dp[i+1][j] = dp[i][j] * (1.0 - P[i])
			if j > 0 {
				dp[i+1][j] += dp[i][j-1] * P[i]
			}
		}
	}

	ans := 0.0
	for i := N; i >= ceil(N, 2); i-- {
		ans += dp[N][i]
	}
	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}


Measured memory_bytes: 75264
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,ans[maxn],f[maxn],a[maxn];
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(register int i=n;i>=1;i--)
	{
		int sum=0;
		for(register int j=i*2;j<=n;j+=i)
			sum^=f[j];
		if((sum&1)==a[i])
			f[i]=0;
		else
		{
			f[i]=1;
			m++;
			ans[m]=i;
		}
	}
	printf("%d\n",m);
	for(register int i=m;i>=1;i--)
		printf("%d ",ans[i]);
	return 0;
}

Measured memory_bytes: 2944
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
static const int MAX_N = 100000;
 
ll merge_count(vector<ll> &a){
	int n = a.size();
	if(n <= 1) return 0;

	ll cnt = 0;
	vector<ll> b(a.begin(), a.begin() + n / 2);
	vector<ll> c(a.begin() + n / 2, a.end());

	cnt += merge_count(b);
	cnt += merge_count(c);

	int ai = 0, bi = 0, ci = 0;
	while(ai < n){
		if(bi < b.size() && (ci == c.size() || b[bi] <= c[ci])){
			a[ai++] = b[bi++];
		}else{
			cnt += n / 2 - bi;
			a[ai++] = c[ci++];
		}
	}

	return cnt;
}
 
int main(){
	ll N, A[MAX_N];
 
	cin >> N;
	ll max_a = 0, min_a = 1LL << 60;
	for(int i = 0; i < N; i++){
		cin >> A[i];
		max_a = max(max_a, A[i]);
		min_a = min(min_a, A[i]);
	}

	ll lb = min_a - 1, ub = max_a + 1;
	while(ub - lb > 1){
		ll mid = lb + (ub - lb) / 2;
		vector<ll> B(N + 1);
		for(int i = 1; i < N + 1; i++){
			if(A[i - 1] < mid) B[i] = -1;
			else B[i] = 1;
		}
		for(int i = 1; i < N + 1; i++){
			B[i] += B[i - 1];
		}
		ll cnt = merge_count(B);
		
		ll M = (ll)(N + 1) * (ll)N / 2LL;
		if(M - cnt >= (M + 1LL) / 2LL) lb = mid;
		else ub = mid;
	}
	cout << lb << endl;
 
	return 0;
}


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

int main(void) {
  string S;
  cin >> S;
  int64_t K;
  cin >> K;
  uint lp = 0;
  for (lp = 0; lp < S.size(); lp++) {
    if (S[lp] != '1')
      break;
  }
  if(lp < K)
    cout << S[lp] << endl;
  else
    cout << "1" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(int X = 0; X < N; X++)
#define repvin(V,N) for(int i = 0; i < N; i++) {int tmp; cin >> tmp; V.push_back(tmp);}

using namespace std;

ll mypow(int n, int x){
    ll ans = 1;
    rep(i, x){
        ans = ans * n;
    }
    return ans;
}

int main(){

    ll n;

    cin >> n;

    if(n == 0){
        cout << "0" << endl;
    }else if(n == 1){
        cout << "1" << endl;
    }else{

        ll plusable1 = 1;
        ll plusable2 = 4;
        ll base = -2;

        int k = 1;

        ll plusable;

        bool addfrontone = false;

        string ans = "10";

        while(true){


            if(base <= n &&  n <= base + plusable1){
                plusable = n - base;
                break;
            }

            plusable1 = plusable1 * 2 + 1;


            if(base + plusable2 <= n &&  n <= base + plusable1 + plusable2){
                plusable = n - base - plusable2;
                addfrontone = true;
                break;
            }

            ans = ans + "10";
            k++;

            base = base * 4 - 2;
            plusable1 = plusable1 * 2 + 1;
            plusable2 = plusable2 * 4;

            
        }

        /*
        if(addfrontone){
            cout << base << " " << plusable << " " << plusable2 <<  endl;
        }else{
            cout << base << " " << plusable <<  endl;
        }
        */


        vector<int> diffv(ans.size(), 0);

        ll tmpadd = mypow(2, ans.size() - 1);

        rep(i, ans.size()){
            if(plusable >= tmpadd){
                diffv[i] = 1;
                plusable = plusable - tmpadd;
            }
            tmpadd = tmpadd / 2;
        }

        rep(i, ans.size()){
            if(diffv[i] == 1){
                if(ans[i] == '1'){
                    ans[i] = '0';
                }else{
                    ans[i] = '1';
                }
            }
        }   

        if(addfrontone) ans = "1" + ans;
        cout << ans << endl;

    }
    
    return 0;
}

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 P = pair<int,int>;

int main(){
  int X;
  cin >> X;
  int ans = 0;
  for(int a = 1; a < 1000; a++){
    ll a5 = 1;
    rep(i,5)a5 *= a;
    for(int b = -1000; b < 1000; b++){
      ll b5 = 1;
      rep(i,5)b5 *= b;
      
      if(a5 - b5 == X){
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double W = scan.nextDouble();
        double H = scan.nextDouble();
        double x = scan.nextDouble();
        double y = scan.nextDouble();
        int ans = 0;
        if (W / 2 == x && H / 2 == y) ans = 1;
        System.out.printf("%.10f %d", W * H / 2, ans);
    }
}

Measured memory_bytes: 24916
#include <iostream>
#include <cstdio>

using namespace std;

#define loop(n) for(int lp=0; lp<(n); lp++)
#define ascent(i, a, b)  for(int (i)=(a); (i)<(b); (i)++)
#define descent(i, a, b) for(int (i)=(a); (i)<(b); (i)--)

#define cl clear()

int main() {
	int n, k, s[100000], b[100][100];
	bool flg;
	while(cin >> n >> k, n!=0&&k!=0) {
		ascent(i,0,100000) s[i]=0;
		ascent(i,0,100)
			ascent(j,0,100)
				b[i][j] = 0;
		flg = true;
		
		ascent(i,0,k) {
			cin >> s[i];
		}
		ascent(i,0,n) {
			ascent(j, 0, k) {
				cin >> b[i][j];
			}
		}
		
		ascent(j,0,k) {
			ascent(i,0,n) {
				s[j] -= b[i][j];
				if(s[j] < 0) {
					flg = false;
					break;
				}
			}
			if(!flg)break;
		}
		
		if(flg) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 1580
#include <iostream>
#include <string>
#include <vector>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int mx = 0;
  mx = std::max(A, std::max(B, C));

  int sum = A + B + C - mx;
  rep(i, K) mx *= 2;
  sum += mx;

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256