akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ll       long long
#define DS       pair<ll, ll>
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<DS> v;
map<DS, ll> ans;

void brute() {
    for (int i = 1; i <= 100; i++) {
        multiset<int> ms;
        ms.insert(i);
        int cnt = 0;
        while (!ms.empty()) {
            int x = *ms.begin();
            if (x > 1) {
                ms.insert(x / 2);
                ms.insert(x / 2);
            }
            ms.erase(ms.lower_bound(x));
            cnt++;
        }
        cout << i << " : " << cnt << endl;
    }
}

void gen() {
    ll p = 4, s = 2, a = 2;
    ans[{1, 1}] = 1;
    v.push_back({1, 1});
    while (true) {
        ll x = s + a - 1;
        ans[{s, x}] = p - 1;
        v.push_back({s, x});
        s = x + 1;
        p *= 2;
        a *= 2;
        if (x > 1e12) break;
    }
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //brute();
    gen();
    ll n;
    cin >> n;
    for (int i = 0; i < v.size(); i++) {
//        cout << v[i].first << " " << v[i].second << " " << ans[v[i]] << endl;;
        if (n >= v[i].first && n <= v[i].second) {
            cout << ans[v[i]] << '\n';
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import sys

def f(x):
    if a[x]+m<a[p-1]: return 0
    elif v<=p+n-1-x: return 1
    able=(p+n-1-x)*m
    able+=sum([a[x]+m-a[k] for k in range(p-1,x)])
    if able>=m*v: return 1
    else: return 0

n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>0:
    if r-l==1 and f(l)==1 and f(r)==0: break
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(l+1)

Measured memory_bytes: 14964
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <complex>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << "\n"
static const int INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[200010],dp[300][300];
char field[200][200];

int main(){
  cin >> n >> m >> l;
  int p;
  cin >> p;
  int q = max(max(n,m),l);
  if(q == n)print(n * pow(2,p) + m + l);
  else if(q == m)print(m * pow(2,p) + n + l);
  else print(l * pow(2,p) + m + n);
  return 0;
}


Measured memory_bytes: 256
import sys 
from collections import Counter

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
Q = int(sys.stdin.readline().strip())

ans = sum(A)
counter = Counter(A)
# print(counter)
query = []
for _ in range(Q):
    b, c = map(int, sys.stdin.readline().strip().split())
    ans = ans - counter[b] * b + counter[b] * c
    print(ans)
    if c not in counter:
        counter[c] = 0
    counter[c] += counter[b]
    counter[b] = 0

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

using namespace std;

#define FOR(i, m, n) for(int i = m; i < n; i++)

int main() {
    FOR(i, 1, 10) FOR(j, 1, 10) {
            cout << i << "x" << j << "=" << i * j << endl;
        }
    return 0;
}

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

int main()
{
  int n, h, w; cin >> n>> h>> w;
  
  int count =0;
  for (int i=0; i<n; i++) {
    int a,b;
    cin >> a >> b;
      
      if (a >= h && b >=w)    count++;
    }
   cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
from string import ascii_letters as ascii

def Ss():
  return sys.stdin.readline().rstrip()

def Is():
  return map(int, Ss())

def get_kyu(score):
  if score >= 400 and score <= 599:
    return 8
  if score >= 600 and score <= 799:
    return 7
  if score >= 800 and score <= 999:
    return 6
  if score >= 1000 and score <= 1199:
    return 5
  if score >= 1200 and score <= 1399:
    return 4
  if score >= 1400 and score <= 1599:
    return 3
  if score >= 1600 and score <= 1799:
    return 2
  if score >= 1800 and score <= 1999:
    return 1
  return None

score = int(Ss())
print(get_kyu(score))

Measured memory_bytes: 9968
#abc136c
import sys

n=int(raw_input())
h=map(int,raw_input().split())
for i in xrange(n-2,-1,-1):
 if h[i+1]>=h[i]:
  continue
 elif h[i]-h[i+1]==1:
  h[i]-=1
 else:
  print 'No'
  sys.exit()
print 'Yes'


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

int main() {
    int N;
    cin >> N;
    vector<ll> A(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        A[i] += A[i - 1];
    }

    ll ans = 1e18;
    for (int q = 2; q <= N - 2; q++) {
        ll Left = A[q];
        ll Right = A[N] - A[q];

        int p = lower_bound(A.begin() + 1, A.begin() + q, Left / 2) - A.begin();
        if (p == q)
            p--;

        ll P = A[p];
        ll Q = A[q] - A[p];
        if (p + 1 < q && abs(A[q] - 2 * A[p + 1]) < abs(P - Q)) {
            P = A[p + 1];
            Q = A[q] - A[p + 1];
        }
        if (p - 1 >= 1 && abs(A[q] - 2 * A[p - 1]) < abs(P - Q)) {
            P = A[p - 1];
            Q = A[q] - A[p - 1];
        }

        int r = lower_bound(A.begin() + q + 1, A.end(), A[q] + Right / 2) - A.begin();
        if (r == N) {
            r--;
        }

        ll R = A[r] - A[q];
        ll S = A[N] - A[r];
        if (r + 1 < N && abs(A[N] - 2 * A[r + 1] + A[q]) < abs(R - S)) {
            R = A[r + 1] - A[q];
            S = A[N] - A[r + 1];
        }
        if (r - 1 > q && abs(A[N] - 2 * A[r - 1] + A[q]) < abs(R - S)) {
            R = A[r - 1] - A[q];
            S = A[N] - A[r - 1];
        }

        ans = min(ans, abs(max({P, Q, R, S}) - min({P, Q, R, S})));
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {

    	Main main=new Main();

    	main.run();

    }

    void run() {

    	Scanner sc=new Scanner(System.in);

    	int a=sc.nextInt();
    	int b=sc.nextInt();
    	
    	int result=(a+b)%24;
    	
    	System.out.println(result);
    }
}


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

bool DFS(int t_b,int t_c,int th,int* balls){
  if(th==10)return true;
  if(t_b<balls[th]&&t_c<balls[th])
      if(t_b>t_c)return DFS(balls[th],t_c,th+1,balls);
      else return DFS(t_b,balls[th],th+1,balls);
  else if(t_b<balls[th])return DFS(balls[th],t_c,th+1,balls);
  else if(t_c<balls[th])return DFS(t_b,balls[th],th+1,balls);
  else return false;
}
int main(){
  int n;
  cin>>n;
  for(int j=0;j<n;j++){
    int balls[10];
    for(int i=0;i<10;i++)cin>>balls[i];
    int t_b=0,t_c=0;int drop_balls=0;
    if(DFS(0,0,1,balls))cout<<"YES";
    else cout<<"NO";
    cout<<endl;
  }
}



Measured memory_bytes: 2960
import itertools

n=int(input())
p=list(input().split())
q=list(input().split())
l=[]
for v in itertools.permutations(p,n):
    l.append(list(v))
    
l=sorted(l)
p_val=0
q_val=0
m=0
for i in l:
    if i==p:
        p_val=m
    if i==q:
        q_val=m
    m+=1

print(abs(p_val-q_val))

Measured memory_bytes: 10868
package main

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

func main() {
	sc := NewScanner()

	x := sc.ReadInt()

	grade := 0
	if x < 600 {
		grade = 8
	} else if x < 800 {
		grade = 7
	} else if x < 1000 {
		grade = 6
	} else if x < 1200 {
		grade = 5
	} else if x < 1400 {
		grade = 4
	} else if x < 1600 {
		grade = 3
	} else if x < 1800 {
		grade = 2
	} else {
		grade = 1
	}

	fmt.Println(grade)
}

// from [my library](https://github.com/ikngtty/go-contestlib)
// -   math/simple

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

func Min(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}

	min := values[0]
	for _, v := range values {
		if v < min {
			min = v
		}
	}
	return min
}

func Max(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}

	max := values[0]
	for _, v := range values {
		if v > max {
			max = v
		}
	}
	return max
}

func Pow(base, exponent int) int {
	if exponent < 0 {
		panic(fmt.Sprintf("exponent (%d) should not be a minus", exponent))
	}

	answer := 1
	for i := 0; i < exponent; i++ {
		answer *= base
	}
	return answer
}

func Ceil(divident, dividor int) int {
	if dividor == 0 {
		panic("dividor should not be 0")
	}

	quo := divident / dividor
	rem := divident % dividor

	if rem != 0 {
		if (divident > 0 && dividor > 0) ||
			(divident < 0 && dividor < 0) {
			return quo + 1
		}
	}
	return quo
}

// -   sortutil

func ReverseInts(a []int) {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
}

func ReverseStrings(a []string) {
	sort.Sort(sort.Reverse(sort.StringSlice(a)))
}

// -   io

type Scanner struct {
	bufScanner *bufio.Scanner
}

func NewScanner() *Scanner {
	bufSc := bufio.NewScanner(os.Stdin)
	bufSc.Split(bufio.ScanWords)
	bufSc.Buffer(nil, 100000000)
	return &Scanner{bufSc}
}

func (sc *Scanner) ReadString() string {
	bufSc := sc.bufScanner
	bufSc.Scan()
	return bufSc.Text()
}

func (sc *Scanner) ReadInt() int {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}


Measured memory_bytes: 1772
#include<bits/stdc++.h>
using namespace std;
#define N 510000
struct ques{
	int l,r,id;
	int ans;
}q[N];
int pos[N],c[N],s[N],ans,n,m;
bool cmp(ques x,ques y)
{
	if(pos[x.l] == pos[y.l])
	return x.r < y.r;
	return x.l < y.l;
}
bool __id(ques x,ques y)
{
	return x.id < y.id;
}
void add(int color)
{
	s[color]++;
	ans += s[color] == 1;
}
void del(int color)
{
	s[color]--;
	ans -= s[color] == 0;
}
int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i++)
	cin>>c[i];
	int size = (int)sqrt(n);
	for(int i = 1;i <= n;i++)
	pos[i] = (i-1)/size+1;
	for(int i = 1;i <= m;i++)
	{
		cin>>q[i].l>>q[i].r;
		q[i].id = i;
	}	
	sort(q+1,q+1+m,cmp);
	int l = 1,r = 0;
	for(int i = 1;i <= m;i++)
	{
		while(q[i].l<l) add(c[--l]);
		while(q[i].l>l) del(c[l++]);
		while(q[i].r>r) add(c[++r]);
		while(q[i].r<r) del(c[r--]);
		q[i].ans = ans;
	}
	sort(q+1,q+1+m,__id);
	for(int i = 1;i <= m;i++ )
	cout<<q[i].ans<<endl;
	return 0;
}

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

int main(){
  int a, b, c, d; cin >> a >> b >> c >> d;
  if(a + b > c + d)
    cout << "Left" << endl;
  else if(a + b < c + d)
    cout << "Right" << endl;
  else cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    while(N){
        int sum = 0,a,maxi = 0,mini = INF;
        rep(i,0,N){
            cin >> a;
            sum += a;
            maxi = max(maxi, a);
            mini = min(mini, a);
        }
        sum -= (maxi + mini);
        cout << sum / (N - 2) << endl;
        cin >> N;
    }
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define     PI                       acos(-1)
typedef  long long     ll ;
typedef  unsigned long long ull;
const double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
const int N=100000+5;

int main(){
    GO();
    string st;
    cin>>st;
    if(st[0]==st[1]&&st[1]==st[2]&&st[2]=='R'){
        cout<<"3\n";
    }
    else if((st[0]==st[1]&&st[1]=='R')||(st[1]==st[2]&&st[1]=='R'))
        cout<<"2\n";
    else if(st[0]=='R'||st[1]=='R'||st[2]=='R')
        cout<<"1\n";
    else
       cout<<"0\n";
}





































































































































































































Measured memory_bytes: 3648
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,H = MI()
X = []
for i in range(N):
    a,b = MI()
    X.append((a,0))
    X.append((b,1))

X.sort(reverse=True)

i = 0
ans = 0
while H > 0:
    x,y = X[i]
    if y == 1:
        H -= x
        i += 1
        ans += 1
    else:
        ans += (H+x-1)//x
        break

print(ans)


Measured memory_bytes: 86784
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

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

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

  int n; cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  deque<int> dq;
  rep(i, n) {
    int itr = lower_bound(dq.begin(), dq.end(), a[i]) - dq.begin();
    if(itr == 0) dq.push_front(a[i]);
    else dq[itr-1] = a[i];
  }

  cout << dq.size() << '\n';
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
 
using namespace std;
using lli = long long int;
 
int main() {
    int N;
    cin >> N;
    vector<lli> x(N), y(N);
    lli mx = 0;
    int odd = 0, even = 0;
    for (int i = 0; i < N; i++) {
	cin >> x[i] >> y[i];
	mx = max(mx, abs(x[i]) + abs(y[i]));
	if (abs(x[i] - y[i]) % 2) {
	    odd++;
	} else {
	    even++;
	}
    }
    if (odd * even != 0) {
	cout << -1 << endl;
	return 0;
    }
 
    vector<lli> edges;
    lli sum = 0;
    if (even) {
	edges.push_back(1);
	sum += 1;
    }
    
    for (int i = 0; sum < mx; i++) {
	edges.push_back(1LL << i);
	sum += (1LL << i);
    }
 
    cout << edges.size() << endl;
    for (int i = 0; i < edges.size(); i++) {
	cout << edges[i] << " \n"[i + 1 == edges.size()];
    }
 
 
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    char ss[5] = "LDRU";
    for (int i = 0; i < N; i++) {
	vector<char> ans;
	for (int j = edges.size() - 1; j >= 0; j--) {
	    lli s = 1LL << 60;
	    int k_index = 0;
	    for (int k = 0; k < 4; k++) {
		if (abs(x[i] + dx[k] * edges[j]) + abs(y[i] + dy[k] * edges[j]) <= s) {
		    k_index = k;
		    s = abs(x[i] + dx[k] * edges[j]) + abs(y[i] + dy[k] * edges[j]);
		}
	    }
	    x[i] += dx[k_index] * edges[j];
	    y[i] += dy[k_index] * edges[j];
	    //cout << "!" << x[i] << " " << y[i] << endl;
	    ans.push_back(ss[k_index]);
	}
	for (int t = ans.size() - 1; t >= 0; t--) {
	    cout << ans[t];
	}
	cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
package main

import(
    "fmt"
)



func main() {
    var n,a,b int
    fmt.Scan(&n,&a,&b)
    ans := min32(n*a,b)
    fmt.Println(ans)
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

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

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func scanTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
const ll MOD = 1000000007;
using namespace std;

ll mpow(int base, int n)
{
    if (n == 0)
    {
        return 1ll;
    }
    ll prev = mpow(base, n / 2);
    if (n % 2 == 1)
    {
        return (((prev * prev) % MOD) * base) % MOD;
    }
    else
    {
        return (prev * prev) % MOD;
    }
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n)
    {

        cin >> a[i];
        a[i]++;
    }
    vector<int> mp(n + 1, 0);
    ll ans = 1;
    rep(i, n)
    {
        if (a[i] == 1)
        {
            ans *= (3 - mp[1]);
            mp[1]++;

            ans %= MOD;
        }
        else
        {
            //  cerr << a[i] << " " << (mp[a[i] - 1] - mp[a[i]]) << endl;
            ans *= (mp[a[i] - 1] - mp[a[i]]);
            ans %= MOD;
            mp[a[i]]++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
n = int(input())
h = list(map(int, input().split()))[::-1]
ans = "Yes"
for i in range(n-1):
    if h[i] >= h[i+1]: continue
    if h[i] >= h[i+1]-1:
        h[i+1] -= 1
    else:
        ans = "No"
        break
print(ans) 

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

//.define
// #define FILE_IN_OUT
#define RET(_x)                       return cout << (_x) << '\n', 0;
#define all(_obj)                     std::begin(_obj), std::end(_obj)
#define loop(_n)                      for (int i = 0; i < (_n); ++i)
#define ceilDiv(_dividend, _divider)  (((_dividend) - 1LL + (_divider)) / (_divider))
#define has(_obj, _val)               ((_obj).find(_val) != (_obj).end())
#define sz(_obj)                      static_cast<int>((_obj).size())
#ifdef SHJ_LOCAL
#define debug(_x)                     std::cerr << (#_x) << " = " << (_x) << '\n' << std::flush;
#else
#define debug(_x)                     {}
#endif
#define endl "\n"
template<typename Tp>
inline void outarr(Tp _begin, Tp _end, const char* _delim = " ") {
    for (Tp current = _begin; current != _end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll  = long long;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<const int>(1e9 + 7);

//.data
double arr[3000];
double dp[3005];

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream cin ("input.txt",  std::ios::in);
    std::ofstream cout("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int n;
    cin >> n;
    loop(n) {
        cin >> arr[i];
    }
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j > 0; --j) {
            dp[j] += dp[j - 1] * arr[i];
            dp[j - 1] *= 1 - arr[i];
        }
    }
    double ans = 0;
    for (int i = (n + 1) >> 1; i <= n; ++i) {
        ans += dp[i];
    }
    cout << fixed << setprecision(10) << ans << endl;

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1, (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

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

    vector<pair<int,ll>> vec(n);
    for(auto& i : vec){
        cin >> i.first >> i.second;
    }

    vector<vector<ll>> dp(n+1, vector<ll>(W+1, 0));

    for(int i=1; i<=n; i++){
        int w = vec[i-1].first;
        ll v = vec[i-1].second;
        REP(j, W+1){
            dp[i][j] = dp[i-1][j];
        }
        REP(j, W+1){
            if(j + w <= W){
                dp[i][j + w] = max(dp[i][j + w], dp[i-1][j] + v);
            }
        }
    }

    cout << *max_element(all(dp[n])) << endl;

    return 0;
}

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    char p = S[0];
    int c=1;
    for(int i=1;i<N;i++) {
        if(S[i] == p) continue;
        c++;
        p = S[i];
    }
    cout << c << endl;
}

Measured memory_bytes: 512
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
  string n;
  cin >> n;
  for (char c : n) {
    if (c == '1') cout << '9';
    if (c == '9') cout << '1';
  }

  cout << endl;

  return 0;
}


Measured memory_bytes: 256
l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
s = input()
for i in l:
    flag = False
    for aa in s:
        if aa == i:
            flag = True
    if flag == False:
        print(i)
        exit()
print("None")


Measured memory_bytes: 41068
inputs = input().split()

A = int(inputs[0])
B = int(inputs[1])

if not 0 <= A <= 100:
    exit(0)

if not 2 <= B <= 1000:
    exit(0)

if not B % 2 == 0:
    exit(0)

if A <= 5:
    B = 0
elif 5 < A < 13:
    B /= 2

print(int(B))


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


int main(){
    int H,W;
    cin>>H>>W;
    char s[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++)cin>>s[i][j];
    }

    bool S=true,t=false;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(s[i][j]=='#'){
                if(i-1>=0){
                    if(s[i-1][j]=='#')continue;
                }
                if(i+1<H){
                    if(s[i+1][j]=='#')continue;
                }
                if(j-1>=0){
                    if(s[i][j-1]=='#')continue;
                }
                if(j+1<W){
                    if(s[i][j+1]=='#')continue;
                }
                t=true;
                break;
            }
        }
        if(t)break;
    }

    if(t)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
S = ['0'] + list(input())
N = len(S)

ans = 0
flag = False #直前の文字を使って2文字にするとき True
for i in range(1, N):
    #同じ文字が連続している時
    if S[i] == S[i - 1]:
        # print ('A')
        if flag == True: #その前に連続で使っているとき
            ans += 1
            flag = False
        elif flag == False: #その前を不連続で使っているとき
            flag = None
        elif flag == None:
            ans += 1
            flag = True

    #直前の文字と異なるとき-->1文字だけで使う
    elif S[i] != S[i - 1]:
        # print ('B')
        if flag == True: #直前が連続
            ans += 1
            flag = False
        elif flag == False: #直前が不連続
            ans += 1
            flag = False
        elif flag == None:
            ans += 1
            flag = True

print (ans)

Measured memory_bytes: 6308
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

//#define DEBUG
#ifndef DEBUG
#define endl "\n"
#endif

const double PI=3.1415926535897932384626433;
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }

typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

void solve() {
    cini(n);
    cini(m);
    cins(s);

    vi pos(n+1, -1);
    pos[0]=0;
    int maxPos=0;   // max position per move

    while(true) {
        int nMaxPos=maxPos;
        for(int i=1; i<=m; i++) {
            if(maxPos+i>n)
                break;

            if(s[maxPos+i]!='1') {
                pos[maxPos+i]=pos[maxPos]+1;
                nMaxPos=max(nMaxPos, maxPos+i);
            }
        }
        if(nMaxPos>maxPos)
            maxPos=nMaxPos;
        else
            break;
    }

#ifdef DEBUG
    cout<<"dump"<<endl;
    for(int i=0; i<=n; i++)
        cout<<pos[i]<<" ";
    cout<<endl;
#endif


    if(pos[n]<0) {
        cout<<pos[n]<<endl;
        return;
    }

    stack<int> ans;
    int p=n;
    while(p>0) {
#ifdef DEBUG
cout<<"pos="<<p<<endl;
#endif
        if(p<=m) {
            //cout<<p<<endl;
            ans.push(p);
            break;
        }

        bool ok=false;
        for(int i=m; i>=1; i--) {
            if(pos[p-i]==pos[p]-1) {
                p-=i;
                ans.push(i);
                //cout<<i<<" ";
                ok=true;
                break;
            }
        }
        assert(ok);
    }

    while(ans.size()) {
        int a=ans.top();
        ans.pop();
        cout<<a<<" ";
    }
    cout<<endl;
}

int main() {
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t=1;
    while(t--)
        solve();
}



Measured memory_bytes: 1308
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

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

int n, m, q;
int sum[501][501];

int main() {
  cin >> n >> m >> q;
  rep(i, m) {
    int l, r;
    cin >> l >> r;
    sum[l][r] += 1;
  }
 

  rep(i, n) {
    rep(j, n) {
      sum[i+1][j+1] += sum[i+1][j];
    }
  }
  
  /**
  rep(i, n+1) {
    rep(j, n+1) {
      cout << sum[i][j] << " ";
    }
    cout << endl;
  }
  **/

  int ans[100000] ={0};

  rep(i, q) {
    int l, r;
    cin >> l >> r;
    for(int j = l; j <= r; j++) {
      ans[i] += sum[j][r];
     // cout << ans[i] << endl;
    }
  }

  rep(i, q) {
    cout << ans[i] << endl;
  }
 

  return 0;
}

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

class Node{
  int Date;
  Node* p;
  Node* n;
public:
  Node(int i){
    Date = i;
  }
  void SetPrev(Node* p){
    this->p = p;
  }
  void SetNext(Node* n){
    this->n = n;
  }
  void SetDate(int d){
    Date = d;
  }
  int GetData(){
    return Date;
  }
  Node* GetPrev(){
    return p;
  }
  Node* GetNext(){
    return n;
  }
};

class LinkedList{
  Node* First;
  Node* Last;
public:
  LinkedList(){
    First = new Node(0);
    Last = new Node(0);
    First->SetNext(Last);
    Last->SetPrev(First);
  }
  void insert(int x){
    Node* tmp = new Node(x);
    tmp->SetNext(First->GetNext());
    tmp->SetPrev(First);
    First->GetNext()->SetPrev(tmp);
    First->SetNext(tmp);
  }
  void Delete(int x){
    Node* tmp = First->GetNext();
    while(tmp!=Last){
      if(tmp->GetData() == x){
        tmp->GetPrev()->SetNext(tmp->GetNext());
        tmp->GetNext()->SetPrev(tmp->GetPrev());
        delete tmp;
        break;
      }
      tmp = tmp->GetNext();
    }
  }
  void DeleteFirst(){
    Node* tmp = First->GetNext();
    First->SetNext(tmp->GetNext());
    tmp->GetNext()->SetPrev(First);
    delete tmp;
  }
  void DeleteLast(){
    Node* tmp = Last->GetPrev();
    Last->SetPrev(tmp->GetPrev());
    tmp->GetPrev()->SetNext(Last);
    delete tmp;
  }
  friend ostream& operator<< (ostream& os,const LinkedList& ll);
};

ostream& operator<< (ostream& os,const LinkedList& ll){
  Node* tmp = ll.First->GetNext();
  while(1){
    os << tmp->GetData();
    tmp = tmp->GetNext();
    if(tmp == ll.Last){
      break;
    }
    os << ' ';
  }
  return os;
}

int main(){

  LinkedList ll;
  int num=0;
  cin >> num;
  string order="";
  int x=0;
  for(int i=0; i<num; i++){
    cin >> order;
    if(order == "insert"){
      cin >> x;
      ll.insert(x);
    }
    else if(order == "delete"){
      cin >> x;
      ll.Delete(x);
    }
    else if(order == "deleteFirst"){
      ll.DeleteFirst();
    }
    else if(order == "deleteLast"){
      ll.DeleteLast();
    }
  }
  cout << ll << endl;
  return 0;
}

Measured memory_bytes: 34400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template < typename T > string tost( const T& n ) {
    ostringstream stm;
    stm << n;
    return stm.str();
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}


int const INF = 1001001001;


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

vi dish(5);
rep(i,5) cin >> dish[i];

vi a(5);
int ans = INF;
rep(i,5) a[i] = i;
do {
    int sum = 0;
    rep(i,4) {
        sum += dish[a[i]];
        if(sum % 10 != 0) sum += 10 - (sum % 10);
    }
    sum += dish[a[4]];
    ans = min(ans, sum);
} while (next_permutation(all(a)));

cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    
    int n;
    cin >> n;
    pair<int,int> arr[n];
    for (int i=0;i<=n-1;i++)
    {
    	cin >> arr[i].first;
    	arr[i].second=i+1;
    }

    sort(arr,arr+n);
    for (int i=0;i<=n-1;i++)
    {
    	cout << arr[i].second << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<set>
#include<string.h>
#include<queue>
#include<map>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
 
#define pb push_back
#define ii pair<int, int> 
#define vai freopen("in","r",stdin);
#define inf 0x3f3f3f3f
#define f first
#define s second

const ll INF = 1e18;
const int MOD = 1000000007;

const int maxn = 2e5 + 100;
const int MAX = 2e4 + 10;
 



 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//~ vai
	int n , m, x;
	cin >> n >> m >> x;
	int l = 0 , r =  0;
	for(int i = 0 ;i < m;i++){
		int w;
		cin >> w;
		if ( w > x && w < n )++r;
		else if ( w < x && w > 0)++l;
	}
	cout << min ( l, r ) <<'\n';
}
 
	


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
   int k;
   vector<long> a; 
   cin >> k;
   for(int i=1;i<10;i++){
       a.push_back(i);
   }
   while(1){
        if(k<=a.size()){
           cout << a[k-1] << endl;
           return 0;
       } 
       k -= a.size();
       vector<long> old;
       swap(old,a);
       for(auto i:old){
           for(int j=-1;j<=1;j++){
               long d = i%10+j;
               if(d<0||9<d) continue;
               a.push_back(i*10+d);
           }
       }
   }
}

Measured memory_bytes: 1712
#include <vector>
#include <sstream>
#include <algorithm>
#include <fstream>
#include <list>
#include <map>
#include <istream>
#include <bitset>
#include <sstream>
#include <unordered_map>
#include <stack>
#include <set>
#include <cmath>
#include <random>
#include <iostream>
#include <bitset>
#include <iomanip>
#include <queue>
#include <string>

#define int long
#define endl "\n"
#define all(x) x.begin(),x.end()
#define rr return 0
#define xx first
#define yy second
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long double ld;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    double a, b;
    cin >> a >> b;
    int ans = ceil((b - 1) * 1.0 / (a - 1) * 1.0);
    cout << ans;
    rr;
}


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

typedef long long ll;
typedef long double ld;

#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

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

int main(){

    ll A, B;

    cin >> A >> B;

    cout << (A - 1) * (B - 1) << endl;

    return 0;
}

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

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

#define sz(v) ((int) v.size())
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    string s, t; cin >> s >> t;
    int n = sz(s), m = sz(t);
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    FOR(i, 1, n) FOR(j, 1, m) {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
    }
    string res;
    while (n && m) {
        if (s[n - 1] == t[m - 1]) {
            res.push_back(s[n - 1]);
            n--; m--;
        } else if (dp[n][m] == dp[n - 1][m]) n--;
        else m--;
    }
    reverse(all(res));
    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 35584
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
sortA = sorted(A, reverse=True)
maxA = sortA[0]
secondA = sortA[1]
for i in range(N):
    if A[i] != maxA:
        print(maxA)
    else:
        print(secondA)
        

Measured memory_bytes: 70104
s = input()
slist = list(s)
res = ""
for i in slist:
    if i =="0":
        res = res +"0"
    
    elif i == "1":
        res = res+"1"
    elif i == "B":
        if len(res)==0:
            pass
        else:
            res = res[:-1]
            
print(res)

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll D;
    cin>>D;
    V<ll> c(26);
    
    cinf(26,c);
    V<P> p(26);
    V<ll> t(D);
    set<P> st;
    ll sum=0;
    /*rep(i,26){
        p[i]=make_pair(c[i],i);
    }
    sort(all(p));*/
    ll s[D][26];
    rep(i,D){
        rep(j,26)cin>>s[i][j];
    }
    rep(i,D){
        cin>>t[i];
        t[i]--;
    }
    V<ll> ans(D);
    
    ll M;
    cin>>M;
    while(M--){
        ll d,q;
        cin>>d>>q;
        d--;q--;
        t[d]=q;
        ll now=0;
        V<ll> lst(26,1);
        rep(i,D){
        
        ll cnt=0;
        rep(j,26){
            if(j!=t[i]){
                cnt+=c[j]*lst[j];
            }
        }
        now+=s[i][t[i]]-cnt;
        

        lst[t[i]]=1;
        rep(j,26){
            if(j!=t[i]) lst[j]++;
        }
    }
    cout<<now<<'\n';
    }
    
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define pi acos(-1)
using namespace std;
 
const int N = 2e5 + 10, mod = 1e9 + 7;
 
 
 
int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1; 
    //scanf("%d", &tc);
    while(tc--) {
        int r; cin >> r;
        printf("%.20lf\n", 2 * pi * r);
    }    
    return 0;
}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  int N, D;
  cin >> N >> D;

  vector<vector<int>> A(N,vector<int>(D));
  REP(i, N){
    REP(j, D){
      cin >> A.at(i).at(j);
    }
  }
  
  int cnt = 0;
  REP(i,N){
    REP(j,i){
      double sum = 0;
      REP(k,D){
        sum += (A.at(i).at(k)-A.at(j).at(k))*(A.at(i).at(k)-A.at(j).at(k));
      }
      if((int)sqrt(sum) == sqrt(sum)){
        cnt++;
      }
    }
  }

  cout << cnt << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 整数の入力
# a = int(input())
# スペース区切りの整数の入力
# 文字列の入力
# s = input()
# 出力
# print("{} {}".format(a+b+c, s))
# b, c = map(int, input().split())

N, M = map(int, input().split())
array = list(map(int, input().strip().split()))
for value in array :
  N -= value
if N < 0 :
  N = -1
print(N)


Measured memory_bytes: 9884
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  cin >> c;
  if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int[] a = new int[5];
		int[] b = new int[5];
		int[] c = new int[5];
		int d = 0;
		int min = 9;
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		for (int i = 0; i < a.length; i++) {
			if (a[i] % 10 == 0) {
				b[i] = a[i];
				c[i] = 1;

			} else {
				int temp = a[i] / 10;
				b[i] = temp * 10 + 10;
				String str = String.valueOf(a[i]);
				String check = str.substring(str.length() - 1);
				if (min > Integer.parseInt(check)) {
					min = Math.min(min, Integer.parseInt(check));
					d = i;
				}
			}
		}

		b[d] = a[d];

		int sum = 0;
		for (int i = 0; i < b.length; i++) {
			sum += b[i];
		}
		System.out.println(sum);
	}

}


Measured memory_bytes: 23124
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class DKnapsackQueriesOnATree {
public:

    void format(vector<P>& vec) {
      sort(all(vec));
      for(int i=0; i<vec.size()-1; i++) {
        if (vec[i].second > vec[i+1].second) {
          vec[i+1].second = vec[i].second;
        }
      }
    }

    void solve(istream& cin, ostream& cout) {
      SPEED;
      ll n; cin >> n;
      vector<int> v(1<<18), w(1<<18);
      for(int i=1; i<=n; i++) {
        cin >> v[i] >> w[i];
      }

      vector<vector<P>> dp(1024, vector<P>());
      for(int i=1; i<=1023; i++) {
        for(int k=0; k<1024; k++) {
          int tmp = i;
          int nowv = 0;
          int noww = 0;
          for(int p=0; p<10; p++) {
            if (k&(1<<p)) {
              nowv += v[tmp];
              noww += w[tmp];
            }
            tmp /= 2;
          }
          dp[i].emplace_back(noww, nowv);
        }
        format(dp[i]);
      }

      int q; cin >> q;
      while(q--) {
        int p, l; cin >> p >> l;
        if (p < 1024) {
          ll ret = 0;
          auto it = upper_bound(all(dp[p]), P(l, INT_MAX));
          auto pos = distance(dp[p].begin(), it);
          if (pos > 0) {
            chmax(ret, dp[p][pos-1].second);
          }
          cout << ret << endl;
        } else {
          ll ret = 0;
          int idx = -1;
          for(int k=0; k<256; k++) {
            int tmp = p;
            int nowv = 0;
            int noww = 0;
            for(int kk=0; kk<8; kk++) {
              if (k&(1<<kk)) {
                nowv += v[tmp];
                noww += w[tmp];
              }
              tmp /= 2;
              if (tmp < 1024) {
                idx = tmp;
                break;
              }
            }

            auto it = upper_bound(all(dp[idx]), P(l-noww, INT_MAX));
            auto pos = distance(dp[idx].begin(), it);
            if (pos > 0) {
              chmax(ret, dp[idx][pos-1].second + nowv);
            }

          }

          cout << ret << endl;
        }
      }
    }
};

signed main() {
  DKnapsackQueriesOnATree solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 21716
//逆

#include<iostream>
#include<algorithm>
#include<bitset>

#include<cmath>
#include<cstring>
#include<climits>

#include<vector>
#include<set>
#include<map>
#include<unordered_set>
//#include<unordered_map>
#include<tr1/unordered_map>

#include<fstream>
#include<chrono>

using namespace std;
using namespace std::tr1;
using namespace std::chrono;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef vector<int> v32;
typedef vector<ll> v64;

const ll MOD7 = 1e9 + 7;
const ll MOD9 = 1e9 + 9;
const ll INF  = 1LL << 57LL;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ITER iterator
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define ones __builtin_popcount
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

int main()
{
    // DANGER;
    ofstream out("output.txt");

    // ll t;
    // cin>>t;

    auto start = high_resolution_clock::now();

    ll n;
    cin>>n;
    ll a[n];
    rep(i,0,n-1) cin>>a[i];

    ll dp[n];
    dp[0] = 0, dp[1] = abs( a[1]-a[0] );
    rep(i,2,n-1) dp[i] = min( dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]) );

    cout<<dp[n-1]<<"\n";

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, M, C, ans;
std::vector<LL>l, c, w;
std::vector<std::pair<LL, LL>>list;

int main()
{
	in >> N >> M >> C;
	l.resize(C);
	c.resize(N), w.resize(N);
	rep(i, C) in >> l[i];
	rep(i, N) in >> c[i] >> w[i];
	rep(i, N)
	{
		list.push_back(std::make_pair(w[i], c[i]));
	}
	std::sort(list.begin(), list.end(), std::greater<std::pair<LL, LL>>());
	LL tmp = 0;
	rep(i, N)
	{
		if (tmp == M) break;
		if (l[list[i].second - 1] > 0)
		{
			--l[list[i].second - 1];
			ans += list[i].first;
			++tmp;
		}
	}
	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 7000
import java.util.*;


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

    char c = scanner.nextLine().charAt(0);
    int i = c;
    int z = 'Z';

    if(i <= z){
        System.out.println("A");
    }else{
        System.out.println("a");
    }
   
    scanner.close();
    return;
    

  }
}


Measured memory_bytes: 35716
import copy

n, k = map(int, input().split())
a = list(map(int, input().split()))

const = 1000000007
c = 0
d = 0

for i in range(n):
    for j in range(n - i - 1):
        if a[i] > a[n - j - 1]:
            c += 1

b = copy.deepcopy(a)

for i in range(n):
    for j in range(n):
        if b[i] > a[j]:
            d += 1

# print("c", c)

# print("d", d)

ans = c * k + d * (k * (k - 1) // 2)

print(int(ans) % const)


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

int cnt = 0;

void bubbleSort(int A[], int N)
{
  bool flag = true;
  while (flag)
  {
    flag = false;
    for (int i = N - 1; i > 0; i--)
    {
      if (A[i] < A[i - 1])
      {
        int temp = A[i];
        A[i] = A[i - 1];
        A[i - 1] = temp;
        flag = true;
        cnt++;
      }
    }
  }
}

int main(void)
{
  int N, A[100];
  cin >> N;

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

  bubbleSort(A, N);

  for (int i = 0; i < N; i++)
  {
    if (i > 0)
      cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << cnt << endl;

  return 0;
}


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

int main() {
  int N;
  int64_t x;
  cin >> N >> x;
  vector<int64_t> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  int count = 0;

  for (int i = 0; i < N; i++) {
    if (i == N - 1 && x - vec[i] > 0) {
      break;
    }
    if (x - vec[i] >= 0) {
      x -= vec[i];
      count++;
    } else {
      break;
    }
  }

  cout << count << endl;
}

Measured memory_bytes: 3608