akhauriyash/Code-Regression huggingface dataset:
N, X, M = map(int, input().split())

ans = 0
A = []
T = [-1]*M
i = 0
f = False
while i<N:
  if T[X]!=-1 and not f:
    f = True
    ans += sum(A[T[X]:])*((N-i)//(i-T[X]))
    i += (N-i)//(i-T[X])*(i-T[X])
    continue
  A += [X]
  T[X] = i
  ans += X
  X = X*X%M
  i += 1
print(ans)


Measured memory_bytes: 15364
#include<bits/stdc++.h>
using namespace std;
#define bitCount(num)  __builtin_popcount(num)
#define pb push_back
#define ll long long
#define bye return 0;
#define f(i,a,b) for( long long i=a;i<b;i++)
#define testCases long long t;cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define newLine <<"\n"
#define all(x) (x).begin(), (x).end()
#define vll vector<long long>

int main()
{
    fast
   ll d,t,s;
   cin>>d>>t>>s;
   ll tt= d/s;
   if(tt<t) cout<<"Yes\n";
   else if(tt==t)
   {
   	if(d%s==0) cout<<"Yes\n";
   	else cout<<"No\n";
   }
   else cout<<"No\n";
    bye
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

int main()
{
    int N, A, B;
    cin >> N >> A >> B;
    int sum = 0;
    for(int i = 1; i <= N; ++i){
        ostringstream oss;
        oss << i;
        string num = oss.str();
        int tmp = 0;
        for(char digit : num){
            tmp += digit - '0';
        }
        if(tmp >= A && tmp <= B)
            sum += i;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/ruby
require 'prime'
class Integer
	def sopfr()      self.prime_division.reduce(0){|s,(n,p)|s+(n*p)} end
	def factornum()  self.prime_division.reduce(0){|s,(n,p)|s+p} end
	def dfactornum() self.prime_division.reduce(0){|s,(n,p)|s+1} end
	def sopf()       self.prime_division.reduce(0){|s,(n,p)|s+n} end

	def divisornum() self.prime_division.reduce(1){|s,(n,p)|s*(p+1)} end
	def divisorsum() self.prime_division.reduce(1){|s,(n,p)|s*(n**(p+1)-1)/(n-1)} end
	def totient()    self.prime_division.reduce(1){|s,(n,p)|s*(n-1)*n**(p-1)} end

	def derivative() self.prime_division.reduce(0){|s,(n,p)|s+self*p/n} end
end

n=gets.to_i
p (1..1/0.0).find{|e|e.divisornum==n}

Measured memory_bytes: 9028
/*
    アリナ・グレイが好きです。
*/

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

int num[5000][3];

int main(void){
    int n; string s;
    long long sum = 0;
    cin >> n >> s;
    
    string rgb = "RGB";
    
    for(int i = 0;i < n;i++){
        if(s[i] == 'R')num[i][0]++;
        else if(s[i] == 'G')num[i][1]++;
        else if(s[i] == 'B')num[i][2]++;
        
        if(i > 0){
            num[i][0] += num[i-1][0];
            num[i][1] += num[i-1][1];
            num[i][2] += num[i-1][2];
        }
    }
    
    for(int i = 0;i < n;i++){
        long long ans = 1;
        int memo = 0;
        
        if(s[i] == 'R')memo = 0;
        else if(s[i] == 'G')memo = 1;
        else memo = 2;
        
        for(int j = 0;j < 3;j++){
            if(j == memo)continue;
            ans *= (num[n-1][j]-num[i][j]);
        }
        
        for(int j = i+1;j < n;j++){
            if(s[i] == s[j] || (2*(j+1)-(i+1)) > n)continue;
            
            if(s[i] != s[j] && s[j] != s[2*(j+1)-(i+1)-1] && s[i] != s[2*(j+1)-(i+1)-1])ans--;
        }
        sum += ans;
    }
    cout << sum << endl;
    
    //for(int i = 0;i < 3;i++)cout << num[n-1][i] << endl;
}

Measured memory_bytes: 3668
package main

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

func main() {
	n := readi()
	k := readi()
	x := make([]int, n)
	for i := 0; i < n; i++ {
		x[i] = readi()
	}

	ans := INF
	for i := 0; i <= n-k; i++ {
		l := x[i]
		r := x[i+k-1]
		v1 := abs(l) + abs(r-l)
		v2 := abs(r) + abs(l-r)
		ans = min(min(v1, v2), ans)

		// tmp := abs(l-r) + abs(0-x[i])
		// ans = min(ans, tmp)
	}

	fmt.Println(ans)
}

/*-------------------utilities-------------------*/

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func chmin(x *int, y int) bool {
	if *x > y {
		*x = y
		return true
	}
	return false
}

func chmax(x *int, y int) bool {
	if *x < y {
		*x = y
		return true
	}
	return false
}

// 最大公約数
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

// 最小公倍数
func lcm(a, b int) int {
	return (a * b) / gcd(a, b)
}

func comb(n, k int) int {
	if n < k {
		return 0
	}
	if n < 0 || k < 0 {
		return 0
	}
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
}

func factorical(n int) int {
	if n > 0 {
		return n * factorical(n-1)
	}
	return 1
}

/*-------------------init-------------------*/

const (
	INF = 1000000000000000000
	MOD = 1e9 + 7

	COMB_MAX = 510000
)

var (
	readString func() string
)

var (
	fac  = [COMB_MAX]int{}
	finv = [COMB_MAX]int{}
	inv  = [COMB_MAX]int{}
)

func init() {
	readString = newReadString(os.Stdin)
}

func combInit() {
	fac[0] = 1
	fac[1] = 1
	finv[0] = 1
	finv[1] = 1
	inv[1] = 1
	for i := 2; i < COMB_MAX; i++ {
		fac[i] = fac[i-1] * i % MOD
		inv[i] = MOD - inv[MOD%i]*(MOD/i)%MOD
		finv[i] = finv[i-1] * inv[i] % MOD
	}
}

/*-------------------inputs-------------------*/

func readi() int {
	return int(readi64())
}

func readi64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readf() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}


Measured memory_bytes: 2944
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,c,k=map(int, input().split())
    l=[int(input()) for i in range(n)]
    l.sort()
    saisyo=l[0]
    ninzu=1
    ans=0
    for j in range(1,n):
        x=l[j]-saisyo
        if x<=k and ninzu<c:
            ninzu+=1
        else:
            ans+=1
            saisyo=l[j]
            ninzu=1
    print(ans+1)
resolve()

Measured memory_bytes: 44508
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

int main()
{
  int n,k;
  int i,j;

  cin>>n>>k;

  ll ans=k;
  rep(i,n-1)
    ans*=k-1;
  cout<<ans<<endl;

}


Measured memory_bytes: 256
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		String t=sc.next();
		int[] sb=new int[s.length()+1];
		int[] tb=new int[t.length()+1];
		for(int i=1; i<=s.length(); i++){
			if(s.charAt(i-1)=='A'){
				sb[i]=sb[i-1]+2;
			}else{
				sb[i]=sb[i-1]+1;
			}
		}
		for(int i=1; i<=t.length(); i++){
			if(t.charAt(i-1)=='A'){
				tb[i]=tb[i-1]+2;
			}else{
				tb[i]=tb[i-1]+1;
			}
		}
		int q=sc.nextInt();
		PrintWriter p=new PrintWriter(System.out);
		for(int i=0; i<q; i++){
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			int d=sc.nextInt();
			if((sb[b]-sb[a-1]-(tb[d]-tb[c-1]))%3==0){
				p.println("YES");
			}else{
				p.println("NO");
			}
		}
		p.flush();
	}
}


Measured memory_bytes: 109132
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.first+a.second > b.first+b.second; }

signed main() {
  SS(int,a,b);
  p(a*b);



}


Measured memory_bytes: 3648
#include<string>
#include<vector>
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<cmath>
#include<ctime>
#include<complex>

using namespace std;

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


int n,s,c=0;

void f(int i,int sum,int t){

if(0<=i && i<=9){
sum+=i;
t++;
}

if(t==n)
if(sum==s) c++;

if(0<=i && i<=8){
REP(j,i+1,9) f(j,sum,t);
}


}

int main(){

while(true){

cin >> n >> s;
if(n==0 && s==0) break;


REP(i,0,9) f(i,0,0);

cout << c << endl;

c=0;

}

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>
#include <numeric>
#include <queue>
#include <set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

ll lis(ll n, vector<ll> a)
{
  vector<ll> dp(n);
  dp[0] = 1;
  ll res = dp[0];
  for (ll i = 1; i < n; i++)
  {
    if (a[i] < a[i - 1])
    {
      dp[i] = 1;
    }
    else
    {
      dp[i] = dp[i - 1] + 1;
    }
    res = max(res, dp[i]);
  }
  return res;
}

int main(int argc, char const *argv[])
{
  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n)
  {
    cin >> a[i];
    a[i] = -a[i];
  }
  multiset<ll> color;
  color.insert(a[0]);
  for (ll i = 1; i < n; i++)
  {
    auto it = color.upper_bound(a[i]);
    if (it == color.end())
    {
      color.insert(a[i]);
    }
    else
    {
      color.erase(it);
      color.insert(a[i]);
    }
  }
  cout << color.size() << endl;
  return 0;
}


Measured memory_bytes: 5760
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	sum := 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			for k := 1; k <= n; k++ {
				sum += gcd(gcd(i, j), k)
			}
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 1776
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>

using namespace std;

int main(){
    int N;   
    cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++) cin>>A[i];

    sort(A.begin(),A.end());
    int ans=1;
    int count=1;
    for(int i=1;i<N;i++){
        if(A[i]==A[i-1]){
            if(count==1){
                count=0;
                ans--;
            }else{
                count=1;
                ans++;
            }
        }else{
            count=1;
            ans++;
        }
    }
    cout<<ans<<endl; 
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int main()
{
char a,b,c,d;
    scanf("%c%c%c%c",&a,&b,&c,&d);
    
    if(a==b && b==c && c==d && a==d)
        printf("No");
        
    else if(a==c && b==d)
        printf("Yes");
        
    else if(a==d && b==c)
        printf("Yes");
        
    else if(a==b && c==d)
    printf("Yes");
    
     else
        printf("No");
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(){
	int a, b, c, d, l;
	int la, lb;
	scanf("%d%d%d%d%d", &l, &a, &b, &c, &d);
	la=l;
	lb=l;
	while(1)
	{
		if(a<=0)
		{
			break;
		}
		else
		{
			a=a-c;
			la=la-1;
		}
	}
	while(1)
	{
		if(b<=0)
		{
			break;
		}
		else
		{
			b=b-d;
			lb=lb-1;
		}
	}
	if(la<lb)
	{
		printf("%d\n", la);
	}
	else if(la>lb)
	{
		printf("%d\n", lb);
	}
	else
	{
		printf("%d\n", la);
	}
	return 0;
}

Measured memory_bytes: 596
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    while(true){
      int m = scanner.nextInt();
      int f = scanner.nextInt();
      int r = scanner.nextInt();
      if(m == -1 && f == -1 && r == -1) break;
      else if(m == -1 || f == -1) System.out.println("F");
      else if(m + f >= 80) System.out.println("A");
      else if(m + f >= 65) System.out.println("B");
      else if(m + f >= 50) System.out.println("C");
      else if(m + f >= 30){
        if(r < 50) System.out.println("D");
        else System.out.println("C");
      }
      else System.out.println("F");
    }
  }
}

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

int main() {
	int a, b;
	string op;

	cin >> a >> op >> b;

	if (op == "+") {
		cout << a + b << endl;
	}
	else if (op == "-") {
		cout << a - b << endl;
	}
	else {
		cout << "error" << endl;
	}
	return 0;

}

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

typedef long long ll;  const int M=998244353;
 
int main()
{
  int n,k;
  cin>>n>>k;
  int method[n+1]={0};
  int pre[n+1]={0};
  int l[k],r[k];
  for(int i = 0; i < k; i++)
  
      cin >> l[i] >> r[i];
  
  method[1]=1;
  pre[1]=1;

  for(int i=2;i<=n;i++)
  {
    
	for(int j=0;j<k;j++)
    {
      
	  if(i<=l[j])   continue;  // if segement left>=cell 
	  
	  //if cells/i ==5 and segment left node ==5/>=5 we cant add this segment and go to 5 cells..so discard the segment
       
      int left = l[j];
      int right = min(r[j], i - 1);
	  
	   //if cell/i=5  segment-->2-6 but we can take at most 4 to reach 5th cell as we are 1th at first
    
	
	
	  int x = (pre[i - left] - pre[i- right - 1] + M) % M; //steps possible
	 
	  method[i]=(method[i]+x)%M;  //for eacg segment update dp

	 
    
	  method[i]%=M;
    }

    pre[i]=(pre[i-1]%M+method[i]%M)%M;
    
  
  }
  cout<<method[n];
  
 
}

Measured memory_bytes: 5072
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999999;

	public static void Main(string[] args)
	{
		var p = Console.ReadLine();
      	Console.WriteLine("ABC{0}", p);	
	}
	

	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	}
}

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

#define pb push_back
#define pp pop_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
typedef long long ll;

using namespace std;

const int N = 1000, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1.0), eps = 1e-10;

bool a[3][N][N];
char c[N][N];
int n, m;

void colorit(int type, int hw, int l, int r, int color){
 if(type == 0){
  for(int i = l; i <= r; ++i)
   a[color][hw][i] = 1;
 }else{
  for(int i = l; i <= r; ++i)
   a[color][i][hw] = 1;
 }
}

void rec(int xa, int ya, int xb, int yb, int col){
	if(xa == xb || xa + 1 == xb || ya == yb || ya + 1 == yb)
		return;
	for(int i = ya + 1; i < yb; ++i)
		if(c[xa + 1][i] == '#')
			a[col][xa + 1][i] = 1;
	for(int i = xa + 1; i < xb; ++i)
		if(c[i][ya + 1] == '#')
			a[col][i][ya + 1] = 1;
	for(int i = ya + 1; i < yb; ++i)
		if(c[xb - 1][i] == '#')
			a[3 - col][xb - 1][i] = 1;
	for(int i = xa + 1; i < xb; ++i)
		if(c[i][yb - 1] == '#')
			a[3 - col][i][yb - 1] = 1;
	if(xa + 2 == xb || ya + 2 == yb)
		return;
	colorit(0, xa + 1, ya + 1, yb - 1, 3 - col);
	colorit(1, ya + 1, xa + 1, xb - 2, 3 - col);	
	colorit(0, xb - 1, ya + 1, yb - 1, col);
	colorit(1, yb - 1, xa + 2, xb - 1, col);
	rec(xa + 1, ya + 1, xb - 1, yb - 1, 3 - col);
}

int main(){
 srand(time(NULL));
 cin.tie(0);
 cout.tie(0);
 ios_base::sync_with_stdio(0);
 cout << setprecision(10) << fixed;

 cin >> n >> m;

 for(int i = 1; i <= n; ++i)
 for(int j = 1; j <= m; ++j)
  cin >> c[i][j];


 colorit(0, 1, 1, m, 1);
 colorit(1, 1, 1, n - 1, 1);
 colorit(0, n, 1, m, 2);
 colorit(1, m, 2, n, 2); 

 rec(1, 1, n, m, 1);

 for(int i = 1; i <= n; ++i, cout << endl)
 for(int j = 1; j <= m; ++j)
 	if(a[1][i][j] == 1)
 		cout << '#';
 	else cout << '.';
	cout << endl;
	for(int i = 1; i <= n; ++i, cout << endl)
	for(int j = 1; j <= m; ++j)
		if(a[2][i][j] == 1)
			cout << '#';
		else cout << '.';

 return 0;
 //cout << (clock() + 0.0) / CLOCKS_PER_SEC; 
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
const ll p=1000000007;
int main(){
  int h,w,a,b;
  cin >> h >> w >> a >> b;
  int ans[h][w];
  rep(i,h)rep(j,w)ans[i][j]=0;
  rep(i,h-b){
    rep(j,a){
      ans[i][j]=1;
    }
  }
  rep(i,b){
    rep(j,w-a){
      ans[h-i-1][w-1-j]=1;
    }
  }
  rep(i,h){
    rep(j,w)cout << ans[i][j];
    cout << endl;
  }
}


Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <sstream>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define LOOP_IT(s) for(auto it=(s).begin();it!=(s).end();++it)

int main(int argc, char* argv[])
{
    ZOOM


    string s;
    cin>>s;
    int n = s.size();
    bool f=1;
    if(n==1)
    {
        cout<<"No";
        return 0;
    }
    for(int i=0,j=1;i<n;++i,++j)
    {
        if(s[i] == 'h'&&s[j] == 'i');
        else
        {
            f=0;
            break;
        }
        ++i,++j;
    }
    cout<<(f?"Yes":"No");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;


const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll MAXN = 3e3 + 10;
const ll INF = 1e18;
ld dp[MAXN][MAXN];
ld p[MAXN];
ll n;
int main(){
	IOS;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	dp[1][0] = 1 - p[1];
	dp[1][1] = p[1];
	for (int i = 2; i <= n; i++){
		dp[i][0] = dp[i - 1][0] * (1.0 - p[i]);
	}
	for (int i = 2; i <= n; i++){
		for (int j = 1; j <= i; j++){
			dp[i][j] = dp[i - 1][j] * (1 - p[i]) + dp[i - 1][j - 1] * p[i];
			//cout << i << ' ' << j << ' ';
			//cout << fixed << setprecision(20) << dp[i][j] << '\n';		
	}
	}
	ld ans = 0;
	for (int i = n / 2 + 1; i <= n; i++){
		ans += dp[n][i];
	}
	
	cout << fixed << setprecision(20) << ans;
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




Measured memory_bytes: 139776
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

vector<int> uset(100000);
vector<ll> u(100000),v(100000),mask(100000),deg(100000);
vector<vector<ll> > adj(100000);
vector<pii> edges;
ll findIt(ll i)
{
    if(uset[i]==-1)
        return i;
    else
    {
        return uset[i] = findIt(uset[i]);
    }
}

bool set_insert(ll i,ll j)
{
    ll pi = findIt(i),pj = findIt(j);
    if(pi==pj)
        return false;
    uset[pj] = pi;
    return true;
}

int main()
{
    int t;ll n,m;
        cin>>n>>m;
        for(ll i=0;i<n;i++)
        {
            uset[i] = -1;
            adj[i].clear();
            deg[i] = 0;
        }
        for(ll i=0;i<m;i++)
        {
            cin>>u[i]>>v[i];
            edges.push_back({u[i],v[i]});
            mask[i] = -1;
            if(!set_insert(u[i]-1,v[i]-1))
            {
                mask[i] = 0;
                deg[v[i]-1]++;
            }
            else
            {
                adj[u[i]-1].push_back(i);
                adj[v[i]-1].push_back(i);
            }
        }
        if(m%2==1)
        {
            cout<<"-1"<<endl;
            return 0;
        }
        vector<ll> vec;
        ll ind = 0;
        vec.push_back(0);
        while(ind<vec.size())
        {
            for(ll i=0;i<adj[vec[ind]].size();i++)
            {
                if(mask[adj[vec[ind]][i]]!=-2)
                {
                    (u[adj[vec[ind]][i]]!=vec[ind]+1)?(vec.push_back(u[adj[vec[ind]][i]]-1)):(vec.push_back(v[adj[vec[ind]][i]]-1));
                    mask[adj[vec[ind]][i]] = -2;
                }
            }
            ind++;
        }
        for(ll i=vec.size()-1;i>=0;i--)
        {
            for(ll j=0;j<adj[vec[i]].size();j++)
            {
                if(mask[adj[vec[i]][j]]!=0&&mask[adj[vec[i]][j]]!=1)
                {
                    if(deg[vec[i]]%2==0)
                    {
                        if(u[adj[vec[i]][j]]==vec[i]+1)
                        {
                            mask[adj[vec[i]][j]] = 0;
                            deg[v[adj[vec[i]][j]]-1]++;
                        }
                        else
                        {
                            mask[adj[vec[i]][j]] = 1;
                            deg[u[adj[vec[i]][j]]-1]++;
                        }
                    }
                    else
                    {
                        if(v[adj[vec[i]][j]]==vec[i]+1)
                            mask[adj[vec[i]][j]] = 0;
                        else
                            mask[adj[vec[i]][j]] = 1;
                        deg[vec[i]]++;
                    }
                }
            }
        }
        for(ll i=0;i<m;i++)
        {
            if(mask[i]==0)cout<<edges[i].second<<" "<<edges[i].first<<endl;
            else cout<<edges[i].first<<" "<<edges[i].second<<endl;
        }   
    return 0;
}

Measured memory_bytes: 12916
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
#define ceil(a,b) (a+b-1)/b
 
using namespace std;

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

//START OF CODE ->->->->->->->

void solve()
{
    int h,w,m;
    cin>>h>>w>>m;
    int mx_r = 0;
    int mx_c = 0;
    vector<pair<int,int>> p;
    map<pair<int,int>,int> chk;
    map<int,int> f,s;
    rep(i,0,m){
        int x,y;
        cin>>x>>y;
        s[x]++;
        f[y]++;
        chk[{x,y}]++;
        p.pb({x,y});
    }
    vector<int> r,c;
    fori(it,s){
        if ( it->sd > mx_r ){
            mx_r = it->sd;
        }
    }
    fori(it,s){
        if ( it->sd == mx_r ){
            r.pb(it->ft);
        } 
    }
    fori(it,f){
        if ( it->sd > mx_c ){
            mx_c = it->sd;
        }
    }
    fori(it,f){
        if ( it->sd == mx_c ){
            c.pb(it->ft);
        } 
    }
    // rep(i,0,r.size()){
    //     out1(r[i]);
    // }
    // rep(i,0,c.size()){
    //     out1(c[i]);
    // }
    int ans = 0;
    rep(i,0,r.size()){
        rep(j,0,c.size()){
            if ( chk[{r[i],c[j]}] > 0 ){
                ans = max(ans,mx_r+mx_c-1);
            }
            else{
                ans = max(ans,mx_r+mx_c);
                cout<<ans<<endl;
                return;
            }
        }
    }

    cout<<ans<<endl;
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 72908
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const int dx[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
const int dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
char field[100][100];
bool visit[30][30];
int h, w;

int main() {
  while (scanf("%d %d", &h, &w), h|w) {
    REP(y, h) {
      scanf("%s", field[y]);
    }
    string ans = "0";
    map<string, int> open;
    REP(sy, h) {
      REP(sx, w) {
        REP(dir, 8) {
          MEMSET(visit, false);
          string s;
          int x = sx;
          int y = sy;
          while (!visit[y][x]) {
            visit[y][x] = true;
            s += field[y][x];
            if (s.size() > 1) {
              open[s]++;
              if (open[s] >= 2) {
                if (ans.size() < s.size() ||
                    (ans.size() == s.size() && s < ans)) {
                  ans = s;
                }
              }
            }
            x = (x + dx[dir] + w) % w;
            y = (y + dy[dir] + h) % h;
          }
        }
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 0
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include <iomanip>
#include <limits>
#include <thread>
#include <map>
#include <stack>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <list>
#include <functional>
#include <bitset>
#include <tuple>

#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)

#define elif else if

using namespace std;
typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double D;


const ll llINF =  numeric_limits<ll>::max();
const int intINF = numeric_limits<int>::max();
const double doubleINF = numeric_limits<double>::infinity();
const ll MOD = 1000000007;


template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }

int dp[100005];

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

  int n;
  cin >> n;
  rep(i,100005) dp[i] = intINF;
  vi numlist;
  numlist.push_back(1);
  int k = 1;
  while(k< 10){
    if(pow(6,k) < 100005) numlist.push_back(pow(6,k));
    if(pow(9,k) < 100005) numlist.push_back(pow(9,k));
    k++;
  }
  dp[0] = 0;
  rep(i,100005){
    for(const auto& j : numlist){
      if(i+j < 100005) dp[i+j] = min(dp[i+j], dp[i] + 1);
    }
  }

  prints(dp[n]);

  return 0;

}


Measured memory_bytes: 640
#include <cstdio>

using namespace std;

int nrow, ncol;
char mat[100][100];

bool check(int r, int c) {
	if (r < 0 || r >= nrow)
		return false;
	if (c < 0 || c >= ncol)
		return false;
	return mat[r][c] == '#';
}

int main() {
	scanf("%d%d", &nrow, &ncol);
	for (int i = 0; i < nrow; ++i)
		scanf("%s", mat[i]);

	bool flag = true;
	for (int r = 0; r < nrow; ++r) {
		for (int c = 0; c < ncol; ++c) {
			if (check(r, c) && !check(r-1, c) && !check(r+1, c) && !check(r, c-1) && !check(r, c+1))
				flag = false;
		}
	}
	puts(flag ? "Yes" : "No");

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std; 
   
int main(){
  string S,T,U;
  cin >> S >> T;
  int A=S.size(),B=T.size(),mincount=1000;
  for(int i=0;i<A-B+1;i++){
    int count=0;
    U=S.substr(i,B);
    for(int j=0;j<B;j++){
      if(T.at(j)!=U.at(j)){
        count++;
      }
    }
    mincount=min(mincount,count);
  }
  cout << mincount << endl;
}
  
  

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define ll long long  int
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
void solve()
{
            ll n;
            cin>>n;
           ll arr[n],i;
           for(i=0;i<n;i++)
           {
            cin>>arr[i];
           }
           ll mx=0,sum=0;
           for(i=0;i<n-1;i++)
           {
               mx=max(mx,arr[i]);
               if(mx>=arr[i+1])
               {
                  sum=sum+abs(mx-arr[i+1]);
               }

           }
           cout<<sum;
} 
int main()
{
  
    solve();
  
    return 0;
}


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

int main()
{
  int input, n,  k;
  cin >> n;
  cin >> k;
  int sum = 0;
  vector<int> v;
  for(int i = 0; i<n; i++ ) {
    cin >> input;
    v.push_back(input);
  }
  sort(v.begin(), v.end());
  for(int i=0; i<k; i++) {
    sum += v[i];
  }
  cout << sum << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
 using namespace std;
#define INF 1000000000
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long LL;
int H,W,K;
bool A[803][803];
int d[803][803];
typedef pair<int,int> P;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int main(){
    cin>>H>>W>>K;
    REP(i,H+2){
        REP(j,W+2){
             A[i][j]=false;
             d[i][j]=1000000;
        }
    }
    queue<P>que;
    REP(i,H){
        string s;
        cin>>s;
        REP(j,W){
            if(s[j]=='#'){
               A[i+1][j+1]=false;
            }else{
               A[i+1][j+1]=true;
            }
            if(s[j]=='S'){
               d[i+1][j+1]=0;
               que.push(P(i+1,j+1));
            }
        }
    }
    
    while(!que.empty()){
        int x,y;
        tie(x,y)=que.front();
        que.pop();
        if(d[x][y]==K)continue;
        REP(i,4){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(A[xx][yy]==true){
               if(d[xx][yy]==1000000){
                  d[xx][yy]=d[x][y]+1;
                  que.push(P(xx,yy));
               }
            }
        }
    }
    int ans=1000000000;
    REP(i,H+2){
        REP(j,W+2){
            if(d[i][j]<K+1){
               ans=min(ans,(i-1+K-1)/K);
               ans=min(ans,(H-i+K-1)/K);
               ans=min(ans,(j-1+K-1)/K);
               ans=min(ans,(W-j+K-1)/K);
            }
        }
    }
    cout<<ans+1<<endl;
    
    return 0;
}

Measured memory_bytes: 3456
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned long long ll;
const int maxn=1e5+10;
const ll mm=1e9+7;
int main()
{
    ll ans=0;
    ll n;
    cin>>n;
    if(n==2)cout<<0<<endl;
    else{
    for(ll i=1;i*i<n;++i)
    {
        ll now=(n-i)%i;
        if(now==0)
        {
            if(i<(n-i)/i)
            ans=ans+((n-i)/i);
        }
    }
    cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
input=lambda :sys.stdin.readline()
N,Q=map(int, input().split())
tree_dist={}
for i in range(N):
    tree_dist[i+1] = []
for i in range(N-1):
    a,b = map(int, input().split())
    tree_dist[a].append(b)
    tree_dist[b].append(a)
    
z=[0]*N
for i in range(Q):
    p,x = map(int, input().split())
    z[p-1] += x

def saiki(i,p):
    L = list(tree_dist[i])
    for l in L:
        if l != p:
            z[l-1] += z[i-1]
            saiki(l,i)
saiki(1,0)
print(" ".join(map(str,z)))




Measured memory_bytes: 266972
N = int(input())
al = [int(input()) for _ in range(0, N)]

max_a = max(al)  
tmp_al = al[:]
tmp_al.remove(max_a)
snd_a = max(tmp_al)
  
for a in al:
  if a == max_a:
    print(snd_a)
  else:
    print(max_a)

Measured memory_bytes: 70104
#include<stdio.h>
const int MAX_V=1000000;
int prime[MAX_V+1];
int sum[MAX_V+2];
int main(){
  int i,k,n;
  for(i=2;i<=MAX_V;i++){
    prime[i]=1;
  }
  for(i=2;i*i<=MAX_V;i++){
    if(prime[i]){
      for(k=2*i;k<=MAX_V;k+=i){
        prime[k]=0;
      }
    }
  }
  for(i=0;i<MAX_V+1;i++){
    sum[i+1]+=sum[i]+prime[i];
  }
  while(scanf("%d",&n)!=EOF){
    printf("%d\n",sum[n+1]);
  }
  return 0;
}

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

int main(){
  ll n,W;
  int i,j,k,l;
  ll w,w1;
  ll value;
  ll max = -100100100100;
  pair <ll,ll> a[106];
  vector <ll> v[5];

  scanf("%lld %lld", &n, &W);
  for(i = 0;i < n;i++){
    scanf("%lld %lld", &a[i].first, &a[i].second);
  }

  w1 = a[0].first;

  sort(a,a + n);

  // for(i = 0;i < n;i++) printf("%lld %lld\n", a[i].first, a[i].second);
  j = 0;
  for(i = 0;i < n - 1;i++){
    v[j].push_back(a[i].second);
    if(a[i].first != a[i + 1].first) j++;
  }

  v[j].push_back(a[n - 1].second);

  for(i = 0;i < 4;i++){
    sort(v[i].begin(),v[i].end());
    reverse(v[i].begin(),v[i].end());
  }
  
  for(i = 0;i <= v[0].size();i++){
    for(j = 0;j <= v[1].size();j++){
      for(k = 0;k <= v[2].size();k++){
        for(l = 0;l <= v[3].size();l++){
          value = 0;
          w = i*w1 + j*(w1 + 1) + k*(w1 + 2) + l*(w1 + 3);

          if(w > W) break;

          int d;
          for(d = 0;d < i;d++) value += v[0][d];
          for(d = 0;d < j;d++) value += v[1][d];
          for(d = 0;d < k;d++) value += v[2][d];
          for(d = 0;d < l;d++) value += v[3][d];

          if(value > max) max = value;
        }
      }
    }
  }

  printf("%lld\n", max);

  return 0;
}

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

int a[200] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
  int k;
  cin >> k;
  cout << a[k - 1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

int main()
{
  int N;
  std::cin >> N;
  long long int a[3*N];
  long long int ans = 0;
  for ( int i = 0; i < 3*N; i++ ) std::cin >> a[i];
  std::sort(a, a+3*N, std::greater<int>());
  for ( int i = 1; i <= 2*N; i += 2 ) ans += a[i];
  std::cout << ans << std::endl;
  return 0;
}


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

int main(){

    int n, k; cin >> n >> k;
    vector<int> c(n);
    vector<int> g(n);
    //for(int i = 0; i < n; i++) cin >> c[i] >> g[i];
    vector<vector<int> > a(10);
    for(int i = 0; i < n; i++){
        int c, g; cin >> c >> g;
        g--;
        a[g].push_back(c);
    }

    for(int i = 0; i < 10; i++){
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end());
    }

    for(int i = 0; i < 10; i++){
        for(int j = 1; j < (int)a[i].size(); j++){
            a[i][j] += a[i][j - 1];
        }
    }

    vector<vector<int> > dp(11, vector<int> (k + 1, 0));
    for(int i = 0; i < 10; i++){
        for(int j = 0; j <= k; j++){
            int ub = (int)a[i].size();
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            //cout << "i = " << i << " j = " << j << " ub = " << ub << endl;
            if(ub == 0) continue;
            for(int l = 1; l <= ub; l++){
                //cout << i << " " << j << " " << l << endl;
                if(j + l <= k){
                    //cout << "ok" << endl;
                    int val = a[i][l - 1] + (l - 1) * l;
                    dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j] + val);
                }
                //cout << i << " " << j << " " << l << endl;                
            }
        }
    }

    cout << dp[10][k] << endl;

    return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  int N; cin >> N;
  vector<int> ab;
  ll sum = 0;
  rep(i, N) {
    int a, b; cin >> a >> b;
    ab.push_back(a + b);
    sum -= b;
  }
  sort(ab.rbegin(), ab.rend());
  for (int i = 0; i < N; i += 2) {
    sum += ab[i];
  }
  cout << sum << "\n";
}


Measured memory_bytes: 892
//============================================================================
// Name        : tokuteigai.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int a,b,c,d,n;
	cin>>a>>b;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>c>>d;
		if(a<d&&d<b){
			cout<<"1"<<endl;
			return 0;
		}
		if(c<b&&a<c){
			cout<<"1"<<endl;
			return 0;
		}
		if(a==c&&b==d){
			cout<<"1"<<endl;
			return 0;
		}
		if(c<a&&b<d){
			cout<<"1"<<endl;
			return 0;
		}
		if(a==c){
			cout<<"1"<<endl;
			return 0;
		}
		if(b==d){
			cout<<"1"<<endl;
			return 0;
		}
		c=0;
		d=0;
	}
	cout<<"0"<<endl;
	return 0;
}



Measured memory_bytes: 3112
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    long N,cnt=0,keep=0;
    cin >> N;
    vector<long>H(N);
    for(int i=0;i<N;i++){
        cin >>H[i];
    }
    for(int i=0;i<N-1;i++){
        if(H[i]>=H[i+1]){
            keep++;
        }else{
            if(cnt<keep){
                cnt = keep;
            }
            keep=0;
        }
    }
    if(cnt<keep){
        cnt = keep;
    }
    cout << cnt;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void print(const vector<int> &v) {
  for(auto x : v) {
    cout << x << " ";
  }
  cout << endl;
}

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string s;
  cin >> s;
  VI r(n, 0), l(n, 0), rr(n, 0), rl(n, 0);

  FOR(i, 1, n) {
    if(s[i - 1] == 'E') {
      l[i] = l[i - 1];
    }
    else {
      l[i] = l[i - 1] + 1;
    }
  }

  for(int i = n - 2; i >= 0; --i) {
    if(s[i + 1] == 'E') {
      rr[i] = rr[i + 1] + 1;
    }
    else {
      rr[i] = rr[i + 1];
    }
  }

  int ans = INF;
  rep(i, n) {
    ans = min(ans, l[i] + rr[i]);
  }

  out(ans);

  return 0;
}


Measured memory_bytes: 5396
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#define LL long long
#define N 1000001
#define NN 2002
using namespace std;
LL i,j,k,n;
int main()
{
	scanf("%lld",&n);
	if(n) printf("0");
	else printf("1");
	return 0;
}

Measured memory_bytes: 3744
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		sc.close();

		int max = 0;
		for ( int i = 0 ; i < N - 1 ; i++ ) {
			max = Math.max(max, A[i+1] - A[i]);
		}
		max = Math.max(max, K - A[N-1] + A[0]);

		System.out.println(K - max);
	}
}


Measured memory_bytes: 77204
n,m=[int(i) for i in raw_input().split()]
l=[i for i in range(n)]
r=[0 for i in range(n)]
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
for _ in range(m):
    u,v=[int(i)-1 for i in raw_input().split()]
    px=find(u)
    py=find(v)
    if r[px]<r[py]:
            l[px]=py
    elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
    else:
            l[py]=px
ct=0
for i in range(n):
    if find(i)==i:
        ct+=1
print ct-1


Measured memory_bytes: 89100
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define yes(n) cout << ((n) ? "yes" : "no") << endl

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &a, int b) { if (a > b) a = b; }

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) {
    ll g = GCD(a, b);
    return a / g * b;
}


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

    int n = s.length();
    bool ok = true;
    rep(i, n) {
        if (i % 2 == 0) {
            if (s[i] == 'L') {
                cout << "No" << endl;
                return 0;
            }
        } else {
            if (s[i] == 'R') {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

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

int main(){
  string s; cin >> s;
  int slen = s.size();
  int ans;
  
  for(int i = 0; i < slen; i++){
    if(s.at(i) == 'A'){
      ans = i;
      break;
    }
  }
  
  for(int j = slen-1; j > 0; j--){
    if(s.at(j) == 'Z'){
      ans = j - ans;
      break;
    }
  }
  
  cout << ans + 1 << endl;
  
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const long long int inf=9999999999999999;
int main(){
	int n;cin>>n;
	vector<long long int>a(n);
	vector<long long int>b(n);
	for(int i=0;i<n;++i){
		cin>>a[i];
		b[0]=a[0];
		if(i!=0)b[i]=b[i-1]+a[i];
	}
	long long int ans=inf;
	for(int i=0;i<n-1;i++){
		long long int s_ans=abs(b[i]-(b[n-1]-b[i]));
		ans=min(ans,s_ans);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#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++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> N;
    if(N < 1200) cout << "ABC";
    else if(N < 2800) cout << "ARC";
    else cout << "AGC";
    return 0;
}

Measured memory_bytes: 256
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()
  

  
  

Measured memory_bytes: 55088
package main

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

const Mod = int(1e9) + 7

var dp [10002][2][100]int

func main() {
	K, D := ReadString(), ReadInt()
	n := make([]int, len(K))
	for i := 0; i < len(K); i++ {
		n[i] = int(K[i] - '0')
	}
	dp[0][0][0] = 1
	for i := 0; i < len(K); i++ {
		for smaller := 0; smaller < 2; smaller++ {
			for j := 0; j < D; j++ {
				for x := 0; x <= ifelse(smaller == 1, 9, n[i]); x++ {
					ns := ifelse(smaller == 1 || x < n[i], 1, 0)
					nj := (j + x) % D
					dp[i+1][ns][nj] += dp[i][smaller][j]
					dp[i+1][ns][nj] %= Mod
				}
			}
		}
	}
	cnt := 0
	for smaller := 0; smaller < 2; smaller++ {
		cnt += dp[len(K)][smaller][0]
		cnt %= Mod
	}
	fmt.Println((cnt - 1 + Mod) % Mod)
}

func ifelse(cond bool, a int, b int) int {
	if cond {
		return a
	} else {
		return b
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 17676