akhauriyash/Code-Regression huggingface dataset:
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}
	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	seg := Segment{}
	seg.init(n)
	pp := make([]int, n)
	for i := 0; i < n; i++ {
		pp[getNextInt(scanner)-1] = i
	}

	var ans int64
	for i := n; i > 0; i-- {
		seg.add(pp[i-1], 1)
		l := seg.nextLeft(pp[i-1])
		ll := seg.nextLeft(l)
		r := seg.nextRight(pp[i-1])
		rr := seg.nextRight(r)
		ans += int64(pp[i-1]-l) * int64(rr-r) * int64(i)
		ans += int64(r-pp[i-1]) * int64(l-ll) * int64(i)
	}
	fmt.Fprintln(writer, ans)

	writer.Flush()
}

// Segment ...
type Segment struct {
	n, h, i int
	unit    []int
	bucket  [][]int
}

func (seg *Segment) init(n int) {
	seg.n = n
	seg.unit = make([]int, 1)
	seg.unit[0] = 1
	seg.bucket = make([][]int, 1)
	seg.bucket[0] = make([]int, n)

	chunk := 2
	i := 0
	for n > chunk+1 {
		n = (n-1)/chunk + 1
		seg.bucket = append(seg.bucket, make([]int, n))
		seg.unit = append(seg.unit, seg.unit[i]*chunk)
		i++
	}
	seg.h = len(seg.unit)
}

func (seg *Segment) add(index, value int) {
	for i := 0; i < seg.h; i++ {
		seg.bucket[i][index/seg.unit[i]] += value
	}
}

func (seg *Segment) nextLeft(index int) int {
	raw := seg.bucket[0]
	for index = index - 1; index >= 0; index-- {
		if raw[index] > 0 {
			return index
		}
		for seg.i = 0; seg.i < seg.h; seg.i++ {
			if (index+1)%seg.unit[seg.i] != 0 {
				break
			}
			if seg.bucket[seg.i][index/seg.unit[seg.i]] != 0 {
				break
			}
		}
		seg.i--
		index -= seg.unit[seg.i] - 1
	}

	return -1
}

func (seg *Segment) nextRight(index int) int {
	raw := seg.bucket[0]
	for index = index + 1; index < seg.n; index++ {
		if raw[index] > 0 {
			return index
		}
		for seg.i = 0; seg.i < seg.h; seg.i++ {
			if index%seg.unit[seg.i] != 0 {
				break
			}
			if seg.bucket[seg.i][index/seg.unit[seg.i]] != 0 {
				break
			}
		}
		seg.i--

		index += seg.unit[seg.i] - 1
	}

	return seg.n
}


Measured memory_bytes: 4224
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, b, p;
		cin >> x >> y >> b >> p;
		int ans = 0;
		if (b >= 5 && p >= 2) {
			cout << 4 * (x * b + y * p) / 5 << endl;
		}
		else if (b < 5 && p >= 2) {
			ans = min(x * b + y * p, 4 * (x * 5 + y * p) / 5);
			cout << ans << endl;
		}
		else if (b >= 5 && p < 2) {
			ans = min(x * b + y * p, 4 * (x * b + y * 2) / 5);
			cout << ans << endl;
		}
		else {
			ans = min(x * b + y * p, 4 * (x * 5 + y * 2) / 5);
			cout << ans << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3216
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define int long long

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

    int n; cin >> n;

    int ans = 0;

    if(n % 2 == 1){
        cout << 0 << endl;
        return 0;
    }

    int a = 2;
    for(;;){
        a *= 5;
        ans += n / a;
        if(a > 1000000000000000000){
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int H, W; char c;
    scanf("%d %d", &H, &W);
    while (H != 0 && W != 0){
        int i, j;
        for (i = 0; i < H; i++){
            if ((i == 0) || (i == H - 1))
                c = '#';
            else
                c = '.';
            for (j = 0; j < W; j++) {
                if((j == 0) || (j == W -1))
                    printf("#");
                else
                    printf("%c", c);
            }
            printf("\n");
        }
        printf("\n");
        scanf("%d %d", &H, &W);
    }
    return 0;
}

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

namespace ABC138A
{
    class Program
    {
        static void Main(string[] args)
        {

            int a;

            a = int.Parse(Console.ReadLine());

            String s = Console.ReadLine();

            if (a < 3200)
                Console.WriteLine("red");

            else Console.WriteLine(s);

            Console.ReadKey();

        }
    }
}


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


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

	int n, d1, d2, doublet_count = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> d1 >> d2;
		if (d1 == d2) {
			if (++doublet_count > 2) {
				cout << "Yes";
				return 0;
			}
		}
		else
			doublet_count = 0;
	}
	
	cout << "No";

	return 0;
}

Measured memory_bytes: 3652
n, k = map(int, input().split())
s = input().rstrip()

def findEx(s, f, pos, notfound):
  pos = s.find(f, pos)
  if pos == -1:
    pos = notfound
  return pos
    
ans = 0
left = 0
right = 0
while right < n:
    if k > 0:
        right = findEx(s, '01', right, n-1) + 1
        k = k - 1
        right = findEx(s, '10', right, n-1) + 1
        ans = max(ans, right - left)
    else:
        left = findEx(s, '01', left, n-1) + 1
        k = k + 1

print(ans)

Measured memory_bytes: 3316
n, k = map(int, input().split())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)


ans = Base_10_to_n(n, k)
print( len(ans) )

Measured memory_bytes: 3060
import collections
n = int(input())
lst = []
for i in range(n):
	lst.append(input())

a = dict(collections.Counter(lst))

try:
	print('AC x '+str(a['AC']))
except :
	print('AC x 0')
try:
	print('WA x '+str(a['WA']))
except :
	print('WA x 0')
try:
	print('TLE x '+str(a['TLE']))
except:
	print('TLE x 0')
try:
	print('RE x '+str(a['RE']))
except :
	print('RE x 0')

Measured memory_bytes: 16484
#include<stdio.h>

int main(){
    int N,Alice = 0,Bob = 0;
    scanf("%d",&N);
    int a[N];
    for(int i = 0; i < N; i++){
        scanf("%d",&a[i]);
    }
    int str;
    for(int j = 0; j <= N; j++){
        for(int i = 0; i < N - 1; i++){
            str = a[i];
            if(a[i] < a[i + 1]){
                a[i] = a[i + 1];
                a[i + 1] = str;
            }
        }
    }
    /*if(N % 2 == 0){
        for(int i = 0; i < N; i += 2){
            Alice += a[i];
            Bob += a[i + 1];
        }
    } else {
        Alice += a[0];
        for(int i = 1; i < N; i += 2){
            Alice += a[i];
            Bob += a[i + 1];
        }
    }*/
    for(int i = 0; i < N; i++){
        if(i % 2 == 0){
            Alice += a[i];
        } else {
            Bob += a[i];
        }
    }
    int ans = Alice - Bob;
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 1732
#include <stdio.h>

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

Measured memory_bytes: 580
DIV = 1_000_000_007
n = gets.to_i
l = n.times.map{ gets.chomp }
l.delete('-')
s = l.size
u = l.count('U')
dp = (s+1).times.map{ [0]*(s+1) }
dp[0][0] = 1
case_u = 1
case_d = 0
for i in (0...s)
  case_d += 1 if l[i] == 'U'
  for j in (0..i+1)
    dp[i+1][j] = dp[i][j-1]*(case_u - j) if j > 0 
    dp[i+1][j] += dp[i][j]*(case_d - j)
    dp[i+1][j] %= DIV
  end
  case_u += 1 if l[i] == 'U'
end
p dp[s][u]

Measured memory_bytes: 9068
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>
//#include<bits/stdc++.h>

using namespace std;
long long MOD = 1000000007LL;
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define endl "\n"

int main() {
	int x, y, z;
	cin >> x >> y >> z;
	swap(x, y);
	swap(x, z);

	cout << x << " " << y << " " << z << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>

using namespace std;
int n,m,t[55][55];
char c[55][55];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin>>c[i][j];
		t[i][j]=(c[i][j]=='#');
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(c[i][j]=='#')cout<<'#';
			else cout<<t[i-1][j-1]+t[i-1][j]+t[i-1][j+1]+t[i][j-1]+t[i][j+1]+t[i+1][j-1]+t[i+1][j]+t[i+1][j+1];
		}
		cout<<"\n";
	}	
	
	return 0;
}

Measured memory_bytes: 256
import sys

def insertionSort(A, n, g):
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            global cnt
            cnt += 1
        A[j+g] = v

def shellSort(A, n):
    G = list()
    h = 1
    while h ==1 or h < n:
        G.append(h)
        h = h * 3 + 1
    G.reverse()
    m = len(G)
    for i in range(m):
        insertionSort(A, n, G[i])
    print(m)
    print(*G)
    global cnt
    print(cnt)
    for item in A:
        print(item)

cnt = 0
n = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(n)]
shellSort(A, n)


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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	int a,b;
	cin>>a>>b;
	if(a>b)swap(a,b);
	if(a==1&&b==2)
		cout<<3<<endl;
	else if(a==1&&b==3)
		cout<<2<<endl;
	else
		cout<<1<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <list>
#include <vector>
#include <algorithm>

#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;//print
typedef long long ll;
using namespace std;

int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    if(n>=90||n%10==9){
        P("Yes");
    }else{
        P("No")
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define lli long long int
#define pb push_back
#define loop(i,a,n) for(int i=(a);i<(n);i++)
#define MOD 1000000007
#define mem(x,a) memset(x,a,sizeof(x))

int main()
{
	long long int a,b,s;
	cin>>a>>b;
	if(a>=13)
		s=b;
	else if(a>=6 && a<=12)
		s=b/2;
	else
		s=0;
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
X, Y = map(int, input().split())
first = 300000
second = 200000 
third = 100000
if ((X==1 and ((X<205 and X>=1) and (Y>=1 and Y<205)) and Y==1)):
    print(first+first+400000)
elif (X==2 and Y==2):
    print(second+second)
elif (X==3 and Y==3):
    print(third+third)
elif ((X==1 and Y==2) or(X==2 and Y==1)):
    print(first+second)
elif ((X==1 and Y==3) or(X==3 and Y==1) ):
     print(first+third)
elif ((X==2 and Y==3) or(X==3 and Y==2) ):
    print(second+third)
elif ((X==3 and Y>3) or(X>3and Y==3) ):
    print(third)
elif ((X==2 and Y>3) or(X>3 and Y==2) ):
    print(second)
elif ((X==1 and Y>3) or(X>3 and Y==1) ):
    print(first)
else:
    print(0)

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

int main(void)
{
    int R;
    cin >> R;

    if(R < 1200)
        cout << "ABC" << endl;
    else if((R >=1200) &&  (R < 2800))
        cout << "ARC" << endl;
    else if(R  >= 2800)
        cout << "AGC" << endl;

}


Measured memory_bytes: 256
import Data.List
import Data.Maybe

findString :: (Eq a) => [a] -> [a] -> Maybe Int
findString search str = findIndex (isPrefixOf search) (tails str)

sol s
    | isNothing i = 0
    | otherwise   = 1 + (sol $ drop (fromJust i + 3) s)
    where
        i = findString "ABC" s

main=do
    _ <- getLine
    s <- getLine
    print $ sol s


Measured memory_bytes: 508
#include <bits/stdc++.h>
#define LL long long
#define rgi register int
#define rgl register long long
#define il inline

int n, now;

il int read() {
	rgi x = 0, f = 0, ch;
	while(!isdigit(ch = getchar())) f |= ch == '-';
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int main() {
	n = read();
	for(rgi i = 1; i <= n; ++i) {
		int x = read();
		if(x == now + 1) now++;
	}
	if(now) printf("%d", n - now);
	else puts("-1");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    map<string,int> M{};
    int a,b;
    string s,t[110];
    cin >> a;
    for(int i=0; i<a; i++){
        cin >> t[i];
        M[t[i]]++;
    }
    cin >> b;
    for(int i=0; i<b; i++){
        cin >> s;
        M[s]--;
    }
    int ans = 0;
    for(int i=0; i<a; i++){
        ans = max(ans,M[t[i]]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <string>
#include <fstream>
#include <algorithm>
#include <complex>
using namespace std;

typedef long long ll;
const int NMAX=2*1e5+5;

int n,a[NMAX],b[NMAX];
ll ans=0;

pair<int,int> p;
bool possible=true;
priority_queue< pair<int,int> > valeurs;

int main(){
	ios::sync_with_stdio(false);
	
	cin >> n;
	
	for(int i=1;i<=n;i++)
		cin >> a[i];
	
	a[0]=a[n];
	a[n+1]=a[1];
	
	for(int i=1;i<=n;i++){
		cin >> b[i];
		if(b[i]!=a[i]) valeurs.push( make_pair(b[i],i) );
	}
	
	b[0]=b[n];
	b[n+1]=b[1];
	
	while( !valeurs.empty() && possible){
		
		p=valeurs.top();
		valeurs.pop();
		
		int id=p.second;
		//cout << (int)valeurs.size() << '\n';
		//cout << id << ' ' << b[id] << ' ';
		if( b[id]-(b[id-1]+b[id+1]) < a[id])
			possible=false;
		else{
			
			int rep=(b[id]-a[id])/(b[id-1]+b[id+1]);
			
			ans+=rep;
			b[id]-=(b[id-1]+b[id+1])*rep;
			
			if(id==n) b[0]=b[id];
			if(id==1) b[n+1]=b[id];
			
			if(b[id]!=a[id]) valeurs.push( make_pair(b[id],id) );
		}
		//cout << b[id] << ' ' << a[id] << '\n';
	}
	/*for(int i=1;i<=n;i++) cout << b[i] << ' ';
	cout << '\n';*/
	
	if(possible) cout << ans << '\n';
	else cout << -1 << '\n';
	
	return 0;
	
	
}



Measured memory_bytes: 4724
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
// #define int ll
// #define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
 
const int N=1e5+5,OO=1e9;
vector<pii> gg[N];
vector<int> v[N];
vector<int> num[N];
int xx[N*4],zz[N*4],dist[N*4];
vector<vector<int>> g[N];
int u[N];
int q[N*8];
int32_t main(){
    int n,m;
    cin>>n>>m;
    forn(i,m){
        int x,y,z;
        cin>>x>>y>>z;
        gg[x].pb(y,z);
        gg[y].pb(x,z);
        v[x].pb(z);
        v[y].pb(z);
    }
    int cnt=0;
    for(int i=1;i<=n;++i){
        sort(v[i].begin(), v[i].end());
        v[i].resize(unique(v[i].begin(), v[i].end())-v[i].begin());
        g[i].resize(sz(v[i]));
        num[i].resize(sz(v[i]));
        forn(j,sz(v[i])){
            xx[cnt]=i;zz[cnt]=j;
            dist[cnt]=OO;
            num[i][j]=cnt++;
        }
        for(pii p:gg[i]){
            int to=p.f,z=p.s;
            z=lower_bound(v[i].begin(), v[i].end(),z)-v[i].begin();
            g[i][z].pb(to);
        }
    }
    int l=N*3,r=N*3;
    forn(i,sz(v[1])){
        dist[num[1][i]]=1;
        q[r++]=num[1][i];
    }
    u[1]=1;
    while(l<r){
        int nu=q[l++];
        int x=xx[nu],pz=zz[nu];
        int z=v[x][pz];
        if(!u[x]){
            u[x]=1;
            forn(i,sz(v[x])){
                int nt=num[x][i];
                if(dist[nt]>dist[nu]+1){
                    dist[nt]=dist[nu]+1;
                    q[r++]=nt;
                }
            }
        }
        for(int to:g[x][pz]){
            int pzt=lower_bound(v[to].begin(), v[to].end(),z)-v[to].begin();
            int nt=num[to][pzt];
            if(dist[nt]>dist[nu]){
                dist[nt]=dist[nu];
                q[--l]=nt;
            }
        }
    }
    int ans=OO;
    forn(i,sz(v[n]))upn(ans,dist[num[n][i]]);
    if(ans==OO)ans=-1;
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 54980
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int (x); SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long (x); SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x,y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1000000007;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////
int main(){
	priority_queue<ll> kind[100002];
	ll N,K; SCLLD2(N,K);
	REP(i,N){
		int t; ll d;
		SCD(t); SCLLD(d);
		kind[t-1].push(d);
	}

	priority_queue<ll> best;
	priority_queue<ll> nobest;

	REP(i,N){
		if (kind[i].empty()) continue;
		best.push(kind[i].top());
		kind[i].pop();
	}

	REP(i,N){
		while(!kind[i].empty()){
			nobest.push(kind[i].top());
			kind[i].pop();
		}
	}

	vector<ll> bestsum = {0};
	vector<ll> nobestsum = {0};

	while(!best.empty()){
		bestsum.PB(bestsum.back() + best.top());
		best.pop();
	}

	while(!nobest.empty()){
		nobestsum.PB(nobestsum.back() + nobest.top());
		nobest.pop();
	}

	ll ans = -1;
	for(ll x = 1; x <= K; ++x){
		if (x >= bestsum.size()) break;
		if (K-x >= nobestsum.size()) continue;
		ans = max(ans,bestsum[x] + nobestsum[K-x] + x*x);
	}

	PRINTLLD(ans);
}

Measured memory_bytes: 8820
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
long long arr[Maxn],ans;
pair<long long,int> p[Maxn];
int t,k,n,m;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>arr[i],ans+=arr[i];
	sort(arr,arr+n);
	for(int i=0,a,b;i<m;i++)
		cin>>a>>b,p[i]=make_pair(b,a);
	sort(p,p+m);
	reverse(p,p+m);
	for(int i=0;i<n;i++){
		if(t>=m || p[t].first<=arr[i])break;
		ans+=p[t].first-arr[i];
		k++;
		if(k==p[t].second)k=0,t++;
	}
	cout<<ans;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    string s; cin>>s;

    vint sum(N+1);
    REP(i,N){
        sum[i+1]=sum[i]+(s[i]=='#');
    }
    
    int ans=N;
    for(int i=0;i<=N;i++){
        int b=sum[i];
        int w=(N-i)-(sum[N]-sum[i]);
        ans=min(ans,b+w);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2180
using System;

public class ITP1_8_C
{
    static void Main()
    {
        int[] aryCount = new int[26];
        string alpha = "abcdefghijklmnopqrstuvwxyz";

        while (true)
        {
            string Data = Console.ReadLine();

            if (Data == null || Data.Length == 0) break;

            for (int i = 0; i < Data.Length; i++ )
            {
                if (char.IsLower(Data[i]))
                {
                    int num = Data[i] - 'a';
                    aryCount[num]++;
                }
                else if (char.IsUpper(Data[i]))
                {
                    int num = Data[i] - 'A';
                    aryCount[num]++;
                }
            }
        }

        for (int i = 0; i < aryCount.GetLength(0); i++)
        {
            Console.WriteLine("{0} : {1}", alpha[i], aryCount[i]);
        }

    }
}

Measured memory_bytes: 9308
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
typedef pair<ll,ll> Pair;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }

const ll INF=99999999999999;
const ll MOD=1000000007;

using Edge = pair<ll,ll>;  //　1つ目は結んでいるノード、2つ目はその辺の重みを指す
using Graph = vector<vector<Edge> >;  //隣接リスト
using Matrix = vector<vector<ll> >;  //隣接行列

void warshall(const Matrix &G, Matrix &dist){
  ll n = G.size();
  dist = G;
  rep(k,n){
    rep(i,n){
      rep(j,n){
        if(dist[i][k] == INF || dist[k][j] == INF) continue;
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}
 
int main() {
  ll n,m;
  cin >> n >> m;
  Matrix G(n,vl(n,INF)),dist;
  
  rep(i,n){
    G[i][i] = 0;
  }
  rep(i,m){
    ll x,y,z;
    cin >> x >> y >> z;
    G[x-1][y-1] = z;
    G[y-1][x-1] = z;
  }
  
  warshall(G,dist);
  
  
  
  ll ans = 0;
  rep(i,n){
    rep(j,n){
      if(G[i][j] == INF) continue;
      if(G[i][j] > dist[i][j]) ans++;
    }
  }
      cout << ans/2;
 return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define ull unsigned long long
#define mp make_pair
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
vector<int> v;
pair<int,int> a[105];
int main(){
	int n=read(),k=read()+1;
	for(int i=1;i<=n;i++)a[i]=mp(read(),i);
	sort(&a[1],&a[n+1]);
	for(int T=1;T<=k;T++){
		for(int i=n;i>=(T==1?1:2);i--){a[i].first--; v.push_back(a[i].second);}
		if(T>1){swap(a[1],a[2]); sort(&a[2],&a[n+1]);}
	}
	for(int i=1;i<=n;i++)if(a[i].first<0){
		puts("-1"); return 0;
	}
	writeln(v.size());
	for(auto i:v)wri(i); puts("");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    unsigned long N,K,c=0;
    cin >> N >> K;
  	if(K>=N){
      cout << 0 << endl;
      return 0;
    }
    vector<unsigned long> H(N);
    for(unsigned long i=0;i<N;i++){
        cin >> H[i];
    }
    sort(H.begin(),H.end());
    H.erase(H.end()-K,H.end());
    cout << accumulate(H.begin(),H.end(),c) << endl;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
inline int C(int n,int m)
{
	if(n<m) return 0;
	if(n<=1) return 1;
	return C(n%2,m%2)&C(n/2,m/2);
}
int n,flag=0,v[maxn];
int main()
{
	cin>>n;char c;int ans=0;
	for(int i=1;i<=n;i++) cin>>c,v[i]=c-'0'-1;
	for(int i=1;i<=n;i++) if(v[i]==1) {flag=1;break;}
	if(flag) {for(int i=1;i<=n;i++) if(v[i]==1&&C(n-1,i-1)) ans^=1;}
	else {for(int i=1;i<=n;i++) if(v[i]==2&&C(n-1,i-1)) ans^=2;}
	printf("%d\n",ans);
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#include <bitset>

#define Z class
#define ln cout<<'\n'
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
// sort(vec.begin(), vec.end()); std::greater<>()
// reverse(vec.begin(), vec.end());
// scanf("%s",s);
// printf("%d\n",end-start+1);
// ceil (a + (b - 1)) / b

using namespace std;
using pll = pair<long long, long long>;

template<class T> inline bool chmax(T& a, T b){ if(a < b) { a=b; return 1; }return 0;}
template<class T> inline bool chmin(T& a, T b){ if(a > b) { a=b; return 1; }return 0;}
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;


int main(){
    //pairにしてすべていれる
    //このときランレングス圧縮しないと計算量がO(NM)になるので注意
    //具体的には、数字と個数のペアを置いておけばいい
    int N, M; cin >> N >> M;
    vector<pll> v;
    rep (i, N) {
        //Aは一個ずつ
        int A; cin >> A;
        v.push_back({A, 1});
    }
    rep (i, M) {
        //CはB個ずつ
        int B, C; cin >> B >> C;
        v.push_back({C, B});
    }
    
    //まとめてソート
    sort(v.begin(), v.end(), greater<pll>());
    
    ll count = 0;
    ll res = 0;
    for (auto p : v) {
        //これから入れ替える数が溢れないように調整
        if (count + p.second <= N) {
            res += p.first * p.second;
            count += p.second;
        } else {
            // ここが最後に入れ替えるセクションになるのでbreak
            res += p.first * (N - count);
            count = N;
            break;
        }
    }
    cout << res << endl;  
}


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

using namespace std;

bool IsIncreaseConsecutive(int n) {
    if (n / 10 == 0) return true;

    int bf = n % 10;
    n /= 10;

    while (n) {
        if ((n % 10) != bf - 1) return false;
        bf = n % 10;
        n /= 10;
    }

    return true;
}

int Solve(const int n, const vector<int> &a) {
    int max_p = -1;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (IsIncreaseConsecutive(a[i] * a[j]))
                max_p = max(max_p, a[i] * a[j]);
        }
    }

    return max_p;
}

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

    int n;

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

    cout << Solve(n, a) << endl;

    return 0;
}

Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=5005,mod=1e9+7,inv2=(mod+1)/2;
int f[N][N],fac[N],rev[N],g[N],sz[N],t[N],n,x,y;
vi e[N];

int power(int x,int p){
	int res=1;
	for(;p;p>>=1,x=(ll)x*x%mod)
		if(p&1)res=(ll)res*x%mod;
	return res;
}

void dfs(int u,int fa){
	f[u][1]=sz[u]=1;
	for(auto v:e[u])
		if(v!=fa){
			dfs(v,u);
			fill(g,g+sz[u]+sz[v]+1,0);
			rep(a,1,sz[u])rep(b,0,sz[v])
				g[a+b]=(g[a+b]+(ll)f[u][a]*f[v][b])%mod;
			sz[u]+=sz[v];
			rep(a,1,sz[u])f[u][a]=g[a];
		}
	int sum=0;
	rep(i,1,sz[u])
		if(i%2==0&&f[u][i])
			sum=(sum+(ll)f[u][i]*t[i])%mod;
	f[u][0]=mod-sum;
}

int main(){
	read(n);
	fac[0]=1;
	rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;
	rev[n]=power(fac[n],mod-2);
	per(i,n,1)rev[i-1]=(ll)rev[i]*i%mod;
	rep(i,1,n)if(i%2==0)
		t[i]=(ll)fac[i]*rev[i/2]%mod*power(inv2,i/2)%mod;
	rep(i,1,n-1){
		read(x),read(y);
		e[x].pb(y),e[y].pb(x);
	}
	dfs(1,0);
	printf("%d\n",(mod-f[1][0])%mod);
	return 0;
}

Measured memory_bytes: 97536
#include<stdio.h>
#include<stdbool.h>
#define N 8
#define NOTF -1
#define FREE 1

int A[N][N];
int x,row[N],col[N],dpos[2*N-1],dneg[2*N-1];

void printboard(){
  int i,j;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(A[i][j]){
	if(row[i]!=j) return;
      }
    }
  }

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if (row[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void putQueen(int i){
  int j;
  if(i==N){
    printboard();
    return;
  }
  for(j=0;j<N;j++){
    if(col[j]==NOTF || dpos[i+j]==NOTF || dneg[i-j+N-1] == NOTF) continue;
    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=NOTF;
    putQueen(i+1);
    col[j]=dpos[i+j]=dneg[i-j+N-1]=FREE;
  }
}

int main(){
  
  int i,j,t,w;
  
  scanf("%d",&x);

  for(i=0;i<2*N-1;i++) dpos[i]=dneg[i]=FREE;

  for(i=0;i<N;i++) col[i]=row[i]=FREE;
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      A[i][j]==false;
    }
  }

  for(i=0;i<x;i++){
    scanf("%d%d",&t,&w);
      A[t][w]=true;
  }
  putQueen(0);
  
  return 0;

}

Measured memory_bytes: 572
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

class Point{
public:
  int x,y,c;
  Point(int x = 0,int y = 0,int c = 0):x(x),y(y),c(c){}
};

int main(){
  int i,j,k,l,n,h,w,x[10],y[10],ans;
  bool a[1000][1000];
  string str;
  while(cin >> h >> w >> n){

    for(i=0;i<h;i++){
      cin >> str;
      for(j=0;j<w;j++){
	if(str[j] == 'S'){
	  a[i][j] = false;
	  x[0] = j;
	  y[0] = i;
	}
	else if(str[j] == '.') a[i][j] = false;
	else if(str[j] == 'X') a[i][j] = true;
	else{
	  a[i][j] = false;
	  int c = str[j] - '0';
	  x[c] = j;
	  y[c] = i;
	}
      }
    }

    ans = 0;
    for(i=0;i<n;i++){
      Point u,v;
      queue<Point> Q;
      bool f[1000][1000];

      for(j=0;j<h;j++){
	for(k=0;k<w;k++) f[j][k] = false;
      }

      u.x = x[i];
      u.y = y[i];

      Q.push(u);
      while(!Q.empty()){
	u = Q.front();
	Q.pop();
	f[u.y][u.x] = true;
	if(u.x == x[i+1] && u.y == y[i+1]){
	  ans += u.c;
	  break;
	}

	int dx[4] = {-1,0,1,0};
	int dy[4] = {0,1,0,-1};
	for(j=0;j<4;j++){
	  v = u;
	  v.x += dx[j];
	  v.y += dy[j];
	  if(v.x >= 0 && v.x < w && v.y >= 0 && v.y < h && !f[v.y][v.x] && !a[v.y][v.x]){
	      v.c++;
	   Q.push(v);
	   f[v.y][v.x] = true;
          }
         }
       }
     }

    cout << ans << endl;

  }
  return 0;
}

Measured memory_bytes: 2844
#include <stdio.h>

int main() {
	
	int H;
	int A;
	
	scanf("%d", &H);
	
	scanf("%d", &A);
	
	H%A == 0 ? printf("%d", H/A) : printf("%d", (H/A) + 1) ;
	
	return 0;
}

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

int main(void) {
	// in
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; ++i) std::cin >> a[i];
	
	long long f_max = 0;
	for(int i = 0; i < n; ++i) {
		f_max += a[i] - 1;
	}

	std::cout << f_max << std::endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner kb = new Scanner( System.in);	
		int x,y;
		
		while( true ) {
			x=kb.nextInt();
			y=kb.nextInt();
			
			if( 0==x && 0==y ) { break; }
			if( x <= y ) {
				System.out.println( x+" "+y );
			} else {
				System.out.println( y+" "+x );
			}
		}
	}
}

Measured memory_bytes: 27224
import java.util.*;
import static java.lang.System.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int x = sc.nextInt();
      if(x == 0){
        out.println("1");
      }
      else{
        out.println("0");
      }
    }
}

Measured memory_bytes: 35688
#include<iostream>

using namespace std;

int N;
int a, b, cnt = 0;


bool checkSum(int val) {
    int res = 0;
    while (true) {
        res += val % 10;
        if (val < 10)
            break;
        val /= 10;
    }

    if (a <= res && b >= res) {
        return true;
    } else {
        return false;
    }
}



int main() {
    cin >> N >> a >> b;
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        if(checkSum(i)) sum += i;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
def move(moves):
  b = []
  for (y1,x1),(y2,x2) in zip(moves[:-1],moves[1:]):
    b.append((y1,x1,y2,x2))
  return b

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
now = 0
moves = []
ans = []
for y,coins in enumerate(a,1):
  if y % 2:
    for x,coin in enumerate(coins,1):
      if now:
        moves.append((y,x))
        if coin % 2:
          b = move(moves)
          ans += b
          moves = []
          now = 0
      else:
        if coin % 2:
          moves.append((y,x))
          now = 1
  else:
    for x,coin in enumerate(coins[::-1]):
      x = w - x
      if now:
        moves.append((y,x))
        if coin % 2:
          b = move(moves)
          ans += b
          moves = []
          now = 0
      else:
        if coin % 2:
          moves.append((y,x))
          now = 1
print(len(ans))
for i in ans:
  print(*i)

Measured memory_bytes: 23668
n = int(input())
S = []
for _ in range(n):
    cmd, s = input().split()
    S.append((cmd, s))
    

D = {}
for cmd, s in S:
    if cmd == 'insert':
        D[s] = True
    if cmd == 'find':
        if s in D:
            print('yes')
        else:
            print('no')


Measured memory_bytes: 208504
//  problem
//  Created by 聂小楠 on 2017/8/12.
//  All rights reserved.

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define MAX_N 1000
#define Mem(a,b) memset(a,b,sizeof(a))
#define FREI freopen("in.txt","r",stdin)
#define FREO freopen("out.txt","w",stdout)
#define INF  2147483647
using namespace std;
const ll mod =1e9+7;

int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int cnt[5];
    memset(cnt,0,sizeof(cnt));
    int tmp;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        if(tmp%4==0)
            cnt[4]++;
        else if(tmp%2==0)
            cnt[2]++;
        else
            cnt[1]++;
    }
 //   cout<<cnt[1]<<" "<<cnt[2]<<" "<<cnt[4]<<endl;
    if(cnt[4]>=cnt[1]||(cnt[2]==0&&cnt[4]>=cnt[1]-1))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


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

int main(){
	ll K, A, B;
	cin >> K >> A >> B;
	ll ans = K+1;
	if (A<B) {
		K -= A-1;
	}
	ll tmp = A;
	while (K>1) {
		tmp += B-A;	
		K -= 2;
	}
	if (K == 1) tmp++;
	ans = max(ans, tmp);
	cout << ans << endl;
return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
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;}
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;

double dp[3000][3000];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<double> p(N);
    REP(i,N) cin >> p[i];
    dp[0][0] = 1.0;
    for(int i = 0;i < N; ++i){
        for(int j = 0; j <= i; ++j){
            dp[i+1][j+1] += dp[i][j] * p[i];
            dp[i+1][j] += dp[i][j] * (1-p[i]);
        }
    }
    double ans = 0.0;
    for(int i = N; i >= N/2 + 1; --i) ans += dp[N][i];
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 68992
import java.util.*;
public class Main  {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      int n = sc.nextInt();
      if (n%2 == 0) {
         System.out.println(n/2);
      } else {
         System.out.println(n/2 + 1);
      }
   }  
}


Measured memory_bytes: 21716
program sample
    implicit none
    
    integer(8) :: a,b,c,i,j,m,n,k,a1,b1,c1
    integer(8), allocatable  ::x(:) 

    read(*,*) n
  
    read(*,*) k
    if (n==1)then
        read(*,*)a
        write(*,*) k-abs(k-2*a)
        stop
    end if
    allocate(x(n))
    read(*,*) x
    m=0
    do i=1,n
        m=m+k-abs(k-2*x(i))
    end do
    write(*,*)m
    deallocate(x)
    stop
end program sample
  



Measured memory_bytes: 256
#include <cstdio>

int J[1000][1000];
int O[1000][1000];
int I[1000][1000];

int res[100000][3];

int main() {
	int m, n, k;
	scanf("%d%d", &m, &n);
	scanf("%d", &k);
	
	char s[n+1];
	for(int i=0;i<m+1;i++) {
		J[i][0] = 0;
		O[i][0] = 0;
		I[i][0] = 0;
	}
	for(int j=0;j<n+1;j++) {
		J[0][j] = 0;
		O[0][j] = 0;
		I[0][j] = 0;
	}
	for(int i=1;i<m+1;i++) {
		scanf("%s", s);
		for(int j=1;j<n+1;j++) {
			J[i][j] = J[i][j-1]+(s[j-1]=='J'?1:0);
			O[i][j] = O[i][j-1]+(s[j-1]=='O'?1:0);
			I[i][j] = I[i][j-1]+(s[j-1]=='I'?1:0);
		}
	}
	
	
	int im[2], in[2];
	int lm, sm, ln, sn;
	for(int i=0;i<k;i++) {
		scanf("%d %d %d %d", &im[0], &in[0], &im[1], &in[1]);
		lm = (im[0]>im[1]?im[0]:im[1]);
		sm = (im[0]<im[1]?im[0]:im[1]);
		ln = (in[0]>in[1]?in[0]:in[1]);
		sn = (in[0]<in[1]?in[0]:in[1]);
		res[i][0] = 0;
		res[i][1] = 0;
		res[i][2] = 0;
		for(int j=sm;j<lm+1;j++) {
			res[i][0] += J[j][ln]-J[j][sn-1];
			res[i][1] += O[j][ln]-O[j][sn-1];
			res[i][2] += I[j][ln]-I[j][sn-1];
		}
	}
	
	for(int i=0;i<k;i++) {
		printf("%d %d %d\n", res[i][0], res[i][1], res[i][2]);
	}
	
	return  0;
}

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

import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = [(0, 0, src)]
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        _, k, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxtk][nxt], nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    # けんけんぱの回数なので/3する
    print(res[0][T]//3)


Measured memory_bytes: 84460
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> stack = {};
void push(int a) {
    stack.push_back(a);
}
int pop() {
    int a = stack.back();
    stack.pop_back();
    return a;
}

int main() {

    while (true) {
        std::string s;
        std::cin >> s;
        if (std::cin.eof()) {
            break;
        }

        if (s == "+") {
            push(pop()+pop());
        } else if (s == "-") {
            auto aa = pop();
            auto ab = pop();
            push(ab-aa);
        } else if (s == "*") {
            push(pop()*pop());
        } else { // instant value
            push(std::stoi(s));
        }
    }

    std::cout << pop() << std::endl;

    return 0;
}


Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 1;
int n, m, k;
long long int cs[N]; 
int main(){
    int n;
    cin >> n;
    long long int sum = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n ; j += i)
            cs[j]++;
        sum += 1LL * i * cs[i];
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 81720
#pragma comment(linker, "/STACK:64000000")
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define y1 stupid_cmath
#define left stupid_left
#define right stupid_right
#define vi vector <int>
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))

const int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);

int n, a[100100];
int b[100100];

int main(){

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        b[i] = abs(i - (n - i - 1));
    }

    sort(a, a + n);
    sort(b, b + n);

    int res = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) res = 0;
    }

    int t = n / 2;

    while (t--) {
        res = (res + res) % mod;
    }

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

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll INF = 1LL<<60;
 
int main() {
	int N;
  	cin >> N;
  	string s;
  	string t;
  	cin >> s >> t;
  	int ans = 2 * N;
  	int j = 0;
  	if(s == t){
      ans = N;
      cout << ans << endl;
      return 0;
    }
  	string temps = "";
  	string tempt = "";
  	for(int i = N-1; i >= 0; --i){
      temps = s[i] + temps;
      tempt = tempt + t[j];
      if(temps == tempt){
        ans -= temps.size();
      }
      ++j;
    }
  	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

#define OK 0;
#define INIT 0;
using namespace std;


int main(void) {
    unsigned int a = INIT;
    unsigned int b = INIT;
    unsigned int c = INIT;

    //scanf
    cin >> a >> b >> c;

    if ((a < b) && (b < c)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;

    }

    return OK;
}

Measured memory_bytes: 1152
import java.util.Scanner;
import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    HashSet hs = new HashSet();
    for(int i=0; i<N; i++) {
      hs.add(scan.next());
    }
    scan.close();

    System.out.println(hs.size());
  }
}

Measured memory_bytes: 65884
import java.util.*

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toLong() }
    val A = readLine()!!.split(" ").map { -it.toLong() }

    val q = PriorityQueue(A)
    for (i in 1..m)
        q.add(q.poll() / 2)

    println(-q.sum())
}

Measured memory_bytes: 75880
#include<cstdio>
using namespace std;

int n,num[100];
int bukkit[100];
int cot;

int main()
{
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&num[i]);
		if(bukkit[num[i]]==0)
		{
			cot++;
		}
		bukkit[num[i]]++;
	} 
	printf("%d",cot);
	return 0;
}

Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include <bits/stdc++.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++)
#define all(v) v.begin(), v.end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main(){
  int64_t M;
  cin >> M;
  vector<int64_t> d(M);
  vector<int64_t> c(M);
  rep(i, M){
    cin >> d.at(i) >> c.at(i);
  }
  int64_t digit = 0;
  int64_t sum = 0;
  rep(i, M){
    digit += c.at(i);
    sum += d.at(i) * c.at(i);
  }
  cout << digit - 1 + (sum-1) / 9 << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>

using namespace std;

int main() {
	int n, m;
	int c[20];
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> c[i];
	int dp[50001] = {};
	fill_n(&dp[1], 50000, INT_MAX / 2);
	for (int i = 0; i < m; i++)
		for (int j = c[i]; j <= n; j++)
			dp[j] = min(dp[j], dp[j-c[i]] + 1);
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1364