akhauriyash/Code-Regression huggingface dataset:
//g++ -std=c++14 test.cpp -o test.out
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

double xs,ys,xt,yt;
LL N;
double x[1002],y[1002],r[1002];

double ans = 0;

void solve(){
	//pair<Ldouble,LL> = 点iまでの最短距離、i
	typedef pair<double,LL> DIST;
	N = N + 2;
	x[N-2] = xs; y[N-2] = ys; r[N-2] = 0;//始点
	x[N-1] = xt; y[N-1] = yt; r[N-1] = 0;//終点
	//ダイクストラ
	priority_queue<DIST,vector<DIST>,greater<DIST>> q;
	q.push(DIST(0,N-2));//スタート地点
	vector<double> dist(N,900000000000.0);
	dist[N-2] = 0;//スタート地点
	while(!q.empty()){
		double now_dist = q.top().first;
		LL now_node = q.top().second;
		q.pop();
		if(now_node==N-1) continue;//終点からはどこへも行かなくて良い
		for(int next_node=0;next_node<N;next_node++){
			double dx = x[next_node] - x[now_node];
			double dy = y[next_node] - y[now_node];
			double diff_dist = max(sqrt(dx*dx + dy*dy) - r[next_node] - r[now_node],0.0);
			double next_dist = now_dist + diff_dist;
			if(next_dist<dist[next_node]){
				dist[next_node] = next_dist;
				q.push(DIST(next_dist,next_node));
			}
		}
	}
	ans = dist[N-1];
}
 
int main(){
	cin >> xs >> ys >> xt >> yt;
	cin >> N;
	for(int i=0;i<N;i++) cin >> x[i] >> y[i] >> r[i];
 
    solve();

	cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 7036
n = int(input())
l = [[] for _ in range(n)]
d = [[] for _ in range(n)]
for i in range(n):
    l[i] = list(map(int,input().split()))
    d[i] = [l[i][0]-l[i][1],l[i][0]+l[i][1]]

d.sort(key=lambda x:x[1])
ma = -9999999
c = 0
for i in range(n):
    if(d[i][0] >= ma):
        ma = d[i][1]
        c += 1
print(c)

Measured memory_bytes: 43072
#include <iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int H,W;
  while(1){
  cin >> H >> W;
  if(H==0 && W==0)
    break;
  REP(i,H){
    REP(j,W)
     cout <<"#";
  cout << endl;
  }
  cout << endl;
  }
}

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

#define ll long long int
using namespace std;

int main() {

    int n, W;
    cin >> n >> W;
    vector<int> weight(n), value(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    int sum = 0;
    for (auto &i : value) sum += i;
    vector<ll> dp(sum + 1, 10e10 + 1);
    dp[0] = 0;
    for (int item = 0; item < n; item++) {
        for (int value_already = sum - value[item]; value_already >= 0; value_already--) {
            dp[value_already + value[item]] = min(dp[value_already + value[item]], dp[value_already] + weight[item]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= sum; i++) {
        if (dp[i] <= W) ans = max(ans, i);
    }
    cout << ans;
}

Measured memory_bytes: 1024
N=int(input())
A=[int(i) for i in input().split()]
D=set()
S=set()
for i in range(N):
    if A[i] in S:
        D.add(A[i]) # ダブったやつ
    else:
        S.add(A[i])# かぶり除去
M=max(S) #最大値
X=[1 for i in range(M+1)] #M個の1のリスト
for a in S:
    if a in D:# かぶってたらフラグ除去
        X[a]=0
    for i in range(2*a,M+1,a): # aのN倍をフラグ除去
        X[i]=0
ans=0
for i in range(N):
    if X[A[i]]==1:
        ans+=1
print(ans)


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    string s;
    cin >> s;
    ll n = s.size();
    ll ans = 1;
    bool flag = false;
    i = 1;
    while(i < n){
        if(!flag){
            if(s.at(i) != s.at(i-1)){
                ++ans;
                ++i;
            }else{
                if(i == n-1) break;
                flag = true;
                ++ans;
                i += 2;
            }
        }else{
            flag = false;
            ++ans;
            ++i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
n=int(input())
h_list=[int(s) for s in input().split()]

max_ans=0
tmp_ans=0

for i in range(n-1):
    left=i
    right=i+1
    if h_list[left]>=h_list[right]:
        tmp_ans+=1
        max_ans=max(max_ans,tmp_ans)
    else:
        max_ans=max(max_ans,tmp_ans)
        tmp_ans=0
print(max_ans)

Measured memory_bytes: 14252
#include<fstream>
#include<sstream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include <stdlib.h>
#include <iostream>
using namespace std;

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

	if (s[0] == s[1] && s[2] == s[3] && s[0] != s[2])
		cout << "Yes" << endl;
	else if (s[0] == s[2] && s[1] == s[3] && s[0] != s[1])
		cout << "Yes" << endl;
	else if (s[0] == s[3] && s[1] == s[2] && s[0] != s[1])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
*/

	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec.at(i);
	int ans = 0;
	for (int i = 1; i < n - 1; i++) {
		if (vec.at(i - 1) < vec.at(i) && vec.at(i) < vec.at(i + 1))
			ans++;
		else if (vec.at(i + 1) < vec.at(i) && vec.at(i) < vec.at(i - 1))
			ans++;
		else
			continue;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
int n,ans,d[55];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
	for(int i=1;i<n;i++)
	    for(int j=i+1;j<=n;j++)
	        ans+=d[i]*d[j];
	printf("%d",ans);
}

Measured memory_bytes: 128
from collections import Counter


N, M = map(int, input().split())
A = list(map(int, input().split()))
A1 = [a % M for a in A]

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = (S[i] + A1[i]) % M

T = sorted(S)
C = Counter(S)
key = list(C.keys())
ans = 0
for i, s in enumerate(S):
    C[s] -= 1
    ans += C[s]

print(ans)


Measured memory_bytes: 64280
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;


typedef struct t{
	int x,y;
	int loop;
	int scanned;
}za;

za gyou[100][100];

int loop;

int tansaku(int x,int y){
	if(gyou[x][y].scanned&&gyou[x][y].loop){
		return gyou[x][y].loop;
	}else if(gyou[x][y].scanned){
		++loop;
		gyou[x][y].loop=loop;
		return gyou[x][y].loop;
	}else{
		gyou[x][y].scanned=1;
		gyou[x][y].loop=tansaku(gyou[x][y].x,gyou[x][y].y);
	}
	return gyou[x][y].loop;
}

main(){
	int N;
	while(cin>>N){
		if(N==0)break;
		
		
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				int x,y;
				cin>>x>>y;
				gyou[j][i].x=x;
				gyou[j][i].y=y;
				gyou[j][i].loop=0;
				gyou[j][i].scanned=0;
			}
		}
		
		loop=0;
		
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(gyou[i][j].scanned==0){
					gyou[i][j].loop=tansaku(i,j);
				}
			}
		}
		
		cout<<loop<<endl;
	}
}

Measured memory_bytes: 0
open System

let [| h; w |] = stdin.ReadLine().Split() |> Array.map int
let n = stdin.ReadLine() |> int
let a = stdin.ReadLine().Split() |> Array.map int

let s = Array.mapi (fun i a -> Array.replicate a (i+1)) a |> Array.concat

for i in [0 .. h-1] do
    let t = s.[i*w .. (i+1)*w-1]
    let t = if i % 2 = 0 then t else Array.rev t
    Array.map string t
    |> String.concat " "
    |> printfn "%s"


Measured memory_bytes: 14812
#include <iostream>
        #include <string>
        #include <unordered_map>
        #include <algorithm>
         
        using namespace std;
         
        int main() {
          int n;
          cin >> n;
          unordered_map<string, int> mp;
         
          for (int i=0; i<n; ++i) {
            string s;
            cin >> s;
            sort(s.begin(), s.end());
            mp[s]++;
          }
         
          long long result = 0;
          for (auto &e : mp) {
            int v = e.second;
            result += (long long)v*(v - 1)/2;
          }
         
          cout << result << "\n";
         
          return 0;
        }


Measured memory_bytes: 10660
from functools import reduce
def nCr(n,r,DIV):
  # X/Y mod DIV == X*Y**(DIV-2)
  X=reduce(lambda x,y:x*y%DIV,range(n-r+1,n+1))
  Y=reduce(lambda x,y:x*y%DIV,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

DIV=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,DIV)-1
ans-=nCr(n,a,DIV)
ans-=nCr(n,b,DIV)
print(ans%DIV)

Measured memory_bytes: 3572
#include <cstdio>

int main() {
    char a[100];
    while (~scanf("%s", a)) {
        bool flag = false;
        for (int i = 0;a[i];i++) {
            if (a[i] == '9') flag = true;
        }
        if (flag) puts("Yes");
        else puts("No");
    }
}


Measured memory_bytes: 128
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int ans = 700;
  if(s[0] == 'o') ans += 100;
  if(s[1] == 'o') ans += 100;
  if(s[2] == 'o') ans += 100;
  cout << ans << endl;
  return 0;
}
//templete by private_yusuke

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

using namespace std;

long long N, A, B;
long long h[100100];
bool p(long long u){
	long long cu = 0;
	for(long long x=0; x<N; x++){
		if(h[x]>(u*B)){
//			cout << h[x] << endl;
			long long sh = h[x] - (u*B);
			if(sh%(A-B)==0){
				cu += sh/(A-B);
			} else {
				cu += (sh/(A-B)+1);
			}
		}
	}
//	cout << cu << endl;
	return cu<=u;
}

int main(){
	cin>>N>>A>>B;
	priority_queue<long long> q;
	for(long long n=0; n<N; n++){
		cin>>h[n];
		q.push(h[n]);
	}
	long long l = 0, r=1e9;
	while(l!=r){
		if(p((l+r)/2)){
			r = (l+r)/2;
		} else {
			l = (l+r)/2+1;
		}
	}
//	cout << p(2) << endl;
//	cout << p(800000000) << endl;
	cout << l << endl;
	return 0;
}

Measured memory_bytes: 1912
#include <vector>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>

using namespace std;


struct edge {
    int src;
    int dst;
    int weight;

    edge(int src, int dst, int w) : src(src), dst(dst), weight(w) {}
};

bool operator < (const edge &a, const edge &b) {
  return a.weight > b.weight;
}


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

    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;

        for (int j = 0; j < k; ++j) {
            int v, c;
            cin >> v >> c;
            G[u].emplace_back(v, c);
        }
    }

    // Dijkstra's algorithm (with pritority queue)
    vector<int> d(n, -1);
    vector<bool> visited(n, false);
    priority_queue<edge> Q;

    Q.emplace(-1, 0, 0);
    while (!Q.empty()) {
        auto e = Q.top(); Q.pop();
        if (visited[e.dst])
            continue;
        d[e.dst] = e.weight;
        visited[e.dst] = true;

        for (auto& x : G[e.dst]) {
            if (visited[x.first])
                continue;
            int w = x.second + d[e.dst];
            Q.emplace(e.dst, x.first, w);
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << i << " " << d[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 10700
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
using ll = long long int;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

ll dp[N], seg[4*N + 4];

void upd(int node, int l, int r, int pos, ll val)
{
	if (l == r)
	{
		seg[node] = val;
		return;
	}
	int mid = (l+r)/2;
	if (mid >= pos) upd(2*node, l, mid, pos, val);
	else upd(2*node+1, mid+1, r, pos, val);
	seg[node] = max(seg[2*node], seg[2*node+1]);
}

ll qu(int node, int l, int r, int x, int y)
{
	if (l > y or r < x) return 0;
	if (l >= x and r <= y) return seg[node];
	int mid = (l+r)/2;
	return max(qu(2*node, l, mid, x, y), qu(2*node+1, mid+1, r, x, y));
}

void solve()
{
	int n; cin >> n;
	int h[n], val[n], pos[n];
	vector<array<int, 2>> v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> h[i];
		v[i] = {h[i], i};
	}
	sort(v.begin(), v.end(), [](auto a, auto b) {return a[0] < b[0] or (a[0] == b[0] and a[1] > b[1]);});
	for (int i = 0; i < n; ++i)
	{
		pos[v[i][1]] = i;
	}
	for (int i = 0; i < n; ++i)
	{
		cin >> val[i];
	}
	for (int i = 0; i < n; ++i)
	{
		dp[i] = val[i] + qu(1, 0, n-1, 0, pos[i]);
		upd(1, 0, n-1, pos[i], dp[i]);
	}
	cout << *max_element(dp, dp+n);
}

//  ---------------------Template---------------------------
void InputSetup()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif
}

int main(void)
{
	auto start = chrono::high_resolution_clock::now();

	InputSetup();
	solve();

	auto finish = chrono::high_resolution_clock::now();
	cerr << "Time elapsed: " << (chrono::duration<long double>(finish-start)).count() << "s\n";
}
//  ---------------------Template---------------------------

Measured memory_bytes: 11904
#include <stdio.h>
#include <stdlib.h>
int asc(const void *a, const void *b)
{
    return *(long int *)a - *(long int *)b;
}
int dis(const void *a, const void *b)
{
    return *(long int *)b - *(long int *)a;
}
int main()
{
    long long int x;
    scanf("%lld", &x);
    long long int y, m;
    m = 100;
    for (y = 0; m < x; y++)
    {
        m += m / 100;
    }
    printf("%lld", y);
    return 0;
}

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

using namespace std;

int main(void)
{
	int x;
	cin >> x;
	if (x == 7 || x == 5 || x == 3) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
for i in range(1,5):
    
    t_i,n_i=map(int,input().split())

    if t_i==1:
        print(n_i*6000)
    if t_i==2:
        print(n_i*4000)
    if t_i==3:
        print(n_i*3000)
    if t_i==4:
        print(n_i*2000)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL N;
LL M;
LL A[100001];
int main(){
	cin>>N>>M;
	REP(i,N+1){
	    A[i]=2;
	}
	REP(i,M){
	    int a,b;
	    cin>>a>>b;
	    A[a]++;
	    A[b]++;
	}
	REP(i,N+1){
	    if(A[i]%2!=0){
	       cout<<"NO"<<endl;
	       return 0;
	    }
	}
        cout<<"YES"<<endl;
	return(0);
}

Measured memory_bytes: 1024
#include "bits/stdc++.h" // {{{
using namespace std;
#define eb emplace_back
#define emp emplace
#define fi first
#define se second
#define X first
#define Y second
#define outl(x) cout << (x) << '\n'
#define rep(i,n) for(int i=0; i < (int)(n); ++i)
#define ALL(x) begin(x), end(x)
#define FILL(a,val) memset((a), (val), sizeof(a))
#define ten(n) ((int)(1e##n))
#define TMPLT(T,U) template<class T, class U>
#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define show(x) clog << #x << " \t= " << (x) << '\n'
#define LN() fputs("\n--------------------------------\n", stderr)
#else
#define debug(...)
#define show(x)
#define LN()
#endif
using ll = long long;
using pii = pair<int,int>;
TMPLT(T,U) inline bool chmax(T &a, U b){return b>a ? a=b,1 : 0;}
TMPLT(T,U) inline bool chmin(T &a, U b){return b<a ? a=b,1 : 0;}
TMPLT(T,U) inline constexpr common_type_t<T,U> gcd(T x, U y) { return (x<y)? gcd(y,x) : (y <= 0)? x : gcd(y, x%y); }
TMPLT(T,U) inline constexpr ll lcm(T x, U y) { return (ll)x/gcd(x,y) * y; }
inline bool inner(int val, int min, int max){ return min <= val && val < max; }
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f'3f3f3f3fLL;

namespace ydk{ // }}}
constexpr int MXN = 5005;
constexpr int MOD = ten(9) + 7;


int N, L;
string s;
int dp[MXN][MXN];

constexpr ll modPow(ll x, ll n)
{
    ll ret = 1;
    while(n > 0) {
        if(n&1) (ret *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return ret;
}

ll fn(int cnt, int len)
{
    if (~dp[cnt][len]) { return dp[cnt][len]; }
    if (cnt == N) { return (len == L)? 1 : 0; }

    return dp[cnt][len] =
        (fn(cnt+1, len+1)*2 + fn(cnt+1, max(0, len-1))) % MOD;
}

signed _vim_is_god_()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> s;
    L = s.length();

    FILL(dp, -1);
    ll ans = fn(0, 0);

    ans = ans * modPow(modPow(2, L), MOD-2) % MOD;
    outl(ans);

    return 0;
}

} // {{{
signed main(){ydk::_vim_is_god_(); return 0;} // }}}



Measured memory_bytes: 98304
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int P;
  while (cin >> P) {
    vector<int> A(P);
    for (int& x : A) cin >> x;
    vector<int> B(P);
    B[0] = A[0];
    for (int i = P - 1; i >= 1; i--) {
      int sum = 0;
      for (int x = 0; x < P; x++) {
        sum = (sum + A[x]) % P;
        A[x] = A[x] * x % P;
      }
      B[i] = sum * (P - 1) % P;
    }
    for (int x : B) cout << x << " ";
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

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

int m,nmin,nmax;
int p[210];

int main(){
	while(1){
		cin>>m>>nmin>>nmax;
		if(m==0&&nmin==0&&nmax==0)break;
		for(int i=0;i<m;i++){
			cin>>p[i];
		}
		int gapmax=0;
		int gap=-1;
		for(int i=nmin;i<=nmax;i++){
			if(p[i-1]-p[i]>=gapmax){
				gapmax=p[i-1]-p[i];
				gap=i;
			}
		}
		cout<<gap<<endl;
	}
	return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
int ans,n;
int head,tail;
int h[234234],a[234234];

int getbig(int l,int r,int x)
{
  while(1)
    {
	  int mid=(l+r)/2;
	  if(x<=h[mid]) 
	    {
	      if(l==mid) break;
		  l=mid;
		}
	  else r=mid;
	}
  return l+1;
}

int main()
{
	int i,t;
  scanf("%d",&n);
  for(i=1;i<=n;i++) scanf("%d",&a[i]);
  head=1,tail=1,ans=1;
  h[1]=a[1];
  for(i=2;i<=n;i++)
    {
	  if(a[i]<=h[tail]) ans++,h[++tail]=a[i];
	  else
	    {
	      h[head-1]=2e9;
		  t=getbig(head-1,tail+1,a[i]);
		  h[t]=a[i];
		}
	}
  printf("%d\n",ans);
} 

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

int main(){
    int n;
    cin>>n;
    long long a[n],b[n-1];
    for(int i=0;i<n-1;i++) cin>>b[i];
    int sum=0;
    for(int i=0;i<n;i++){
        if(i!=n-1) a[i]=min(b[i],b[i-1]);
        else a[i]=b[i-1];
        sum+=a[i];
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();

        int res = A - B;
    	if (res >= C) {
    		res = 0;
    	} else {
    		res = C - res;
    	}

        System.out.println(res);
    }
}

Measured memory_bytes: 21972
// clang-format off
#include <bits/stdc++.h>

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep(i, n) for(int i = (n)-1; i >= 0; i--)

#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define pii pair<int, int>
#define vi vector<int>

using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T>& p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T>& vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
using ll = long long;
constexpr ll MOD = 1000000007;

constexpr std::size_t ALPHA = 26;
int alpha[ALPHA];
int alpha2[ALPHA];

inline int toi(char c)
{
    return c - 'a';
}

inline char toc(int n)
{
    return 'a' + n;
}

int main()
{
    rep(i, ALPHA){
        alpha[i] = numeric_limits<int>::max();
    }
    int n;
    cin >> n;
    rep(i , n){
        rep(j, ALPHA){
            alpha2[j] = 0;
        }
        string s;
        cin >> s;
        rep(j, s.size()){
            alpha2[toi(s[j])]++;
        }
        rep(j, ALPHA){
            alpha[j]= min(alpha[j], alpha2[j]);
        }
    }
    vector<char> s;
    rep(i, ALPHA){
        rep(j, alpha[i]){
            s.pb(toc(i));
        }
    }
    rep(i, s.size()){
        cout << s[i];
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MX 100005
int dp[MX][3];
int main() {
	int n;
	cin >> n;
	int arr[n][3];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < 3; ++j)
			cin >> arr[i][j];
	dp[0][0] = arr[0][0], dp[0][1] = arr[0][1], dp[0][2] = arr[0][2];
	for (int i = 1; i < n; ++i) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
		dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + arr[i][2];
	}

	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << endl;
}


Measured memory_bytes: 2560
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();
        n %= k;
        while (Math.abs(n - k) < n) {
            n = Math.abs(n - k);
        }
        System.out.println(n);
    }
}


Measured memory_bytes: 21716
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
b=Hash.new(0)
c=Hash.new(0)

a.each_with_index{|item,i|
    b[i+1-item]+=1
    c[i+1+item]+=1
}
keys = b.keys & c.keys
ans = keys.map{|i|b[i] * c[i]}.sum
p ans

Measured memory_bytes: 51308
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var NA = Sarray();
            var N = NA[0];
            var A = NA[1];
            var X = Sarray();
            var dp = new long[N+1, N+1,N * A+1];//N枚目、選んだ枚数、選んだものの合計

            for (var i = 1; i <= N; ++i)//枚目
            {
                dp[i - 1, 0, 0] = 1;
                var x = X[i - 1];
                for (var n = 1; n <= N; ++n)//枚選んだ
                {
                    for (var j = 1; j <= N * A; ++j)
                    {
                        dp[i, n, j] += dp[i - 1, n, j];//i枚目を選ばない
                        if (0 <= j - x && 0 != dp[i - 1, n - 1, j - x])
                            dp[i, n, j] += dp[i - 1, n - 1, j - x];//選んだ
                    }
                }
            }
            var ans = 0L;
            for (var i = 1; i <= N; ++i)
                ans += dp[N, i, i * A];
            WriteLine(ans);
        }
    }
}

Measured memory_bytes: 58848
N, P = map(int, input().split())
A = list(map(int, input().split()))
a = [i%2 for i in A]
zero = a.count(0)
one = a.count(1)

if one == 0 and P == 1:
    print(0)
else:
    print( (2**zero) * (2**(max(0, one-1))) )


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {

    int w,h,n; cin >>w>>h>>n;
    vector<int> x(n); vector<int> y(n); vector<int> a(n);
    REP(i,n) cin >> x[i] >> y[i] >> a[i];

    int xmx = 0;
    int xmn = w;
    int ymx = 0;
    int ymn = h;

    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            xmx = max(xmx, x[i]);
        } else if (a[i] == 2) {
            xmn = min(xmn, x[i]);
        } else if (a[i] == 3) {
            ymx = max(ymx, y[i]);
        } else {
            ymn = min(ymn, y[i]);
        }
    }

    if (xmx - xmn <= 0 && ymx - ymn <= 0) {
        cout << (xmx - xmn) * (ymx - ymn) << endl;
    } else {
        cout << 0 << endl;
    } 
    
    
    return 0;
}







Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long INF = 1LL << 60;
template <class T> bool chmin(T& a, T b){if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b){if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  string s;
  cin >> s;
  int N = s.size();
  
  for (int i = 0; i < N; i += 2) cout << s.at(i);
  cout << endl;
}

Measured memory_bytes: 512
fn read_line(s: &mut String) -> &str {
  std::io::stdin().read_line(s).unwrap();
  s.trim()
}

fn main() {
  let mut tmp = String::new();
  let ary: Vec<isize> = read_line(&mut tmp).split(" ").map(|n| n.parse().unwrap()).collect();
  let part1: Vec<&isize> = ary.iter().filter(|n| *n == &ary[0]).collect();
  let part2: Vec<&isize> = ary.iter().filter(|n| *n != &ary[0]).collect();
  let ans = if part1.len() == 2 {
    part2[0]
  } else {
    part1[0]
  };
  println!("{}", ans);
}


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

int main() {
  int N,K;
  int P[200000];
  cin >> N >> K;
  for(int i = 0;i < N;i++) cin >> P[i];
  
  //初めからKまでの和
  int s = 0;
  for(int i = 0;i<K;i++){
    s +=P[i];
  }
  int sum = s;
  //ずらしていくときの和
  for(int i = 0;i < N-K;i++){ 
    s += - P[i] + P[i+K];
    if(s > sum) sum = s;
  }
  cout << fixed << setprecision(12) << double(sum+K)/2.0;
  
  return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

#define int ll
const ll MOD = 1e9+7;
typedef string::const_iterator state;

string t;
int expr(state &end);

ll power(ll a,ll b/*,ll mod*/){
    ll ret=1;
    if(b>0){
        ret = power(a,b/2/*,mod*/);
        if(b%2==0)ret = (ret*ret)/*%mod*/;
        else ret = (((ret*ret)/*%mod*/)*a)/*%mod*/;
    }
    return ret;
}

int number(state &end){
    string str="";
    while(isdigit(*end)){
        str+=*end;
        end--;
    }
    reverse(all(str));
    
    int ret = 0;
    rep(i,str.size()){
        ret*=10;
        ret+=str[i]-'0';
    }
    return ret;
}

int term(state &end){
    if(*end=='>'){
        end--;
        int res = expr(end);
        end-=2;
        return (res*res)%MOD;
    }else if(isdigit(*end)){
        int res = number(end);
        return res;
    }else{
        throw"impossible";
        return -1;
    }
}

int expr(state &end){
    if(end+1==t.begin())throw "empty";
    
    vector<int> res;
    res.pb( term(end) );
    
    while(end+1!=t.begin()&&*end!='<'){
        end-=2;
        res.pb( term(end) );
    }
    
    reverse(all(res));
    int tmp = res[0];
    
    for(int i=1;i<res.size();i++){
        rep(j,res[i]){
            if(tmp==0)break;
            tmp/=2;
        }
    }
    
    return tmp;
}

signed main(){
    string s;
    while(getline(cin,s)&&s!="#"){
        t = "";
        rep(i,s.size())if(s[i]!=' ')t+=s[i];
        
        state st = t.end()-1;
        int ans;
        try{
            ans = expr(st);
        }catch(char const* e){
            cout<<"error"<<e<<endl;
            exit(-1);
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 6348
n = gets.chomp.to_i
ary1 = gets.chomp.split.map(&:to_i)
ary2 = Array.new(n,0)
ary1.each{|elem|
  ary2[elem-1] +=1
  }
sum = ary2.map{|elem| (elem*(elem-1))/2}.inject(&:+)
ary1.each{|elem|
  puts sum-ary2[elem-1]+1
  }



Measured memory_bytes: 26116
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>


using namespace std;

using ll = long long;


vector<vector<ll>> graph;
vector<bool> discovered;

ll N, M;


void dfs(ll n, list<ll> &out)
{
    discovered[n] = true;
    for (auto e : graph[n]) {
        if (!discovered[e])
            dfs(e, out);
    }
    out.push_front(n);
}


void topological_sort(list<ll> &out)
{
    for (ll i = 1; i <= N; i++)
        if (!discovered[i])
            dfs(i, out);
}


int main()
{
    cin >> N >> M;
    vector<ll> dp(N + 1, 0);

    graph.resize(N + 1);
    discovered.resize(N + 1, false);

    for (ll i = 0; i < M; i++) {
        ll x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    list<ll> sorted;
    topological_sort(sorted);

    for (auto s : sorted) {
        for (auto t : graph[s]) {
            dp[t] = max(dp[t], dp[s] + 1);
        }
    }
    cout << *max_element(dp.begin() + 1, dp.end()) << endl;
}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

int main(){
int N;
cin >> N;
ll mi = 1e12;
ll a;
cin >> a;
REP(i, N - 1){
 int x;
 cin >> x;
 a = gcd(a, x);
}

print(a);

}

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

int main() {
 
int k;
cin>>k;
vector <int>a ;
a= { 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 };
cout<<a.at(k-1)<<endl;


}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

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

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int a,b;
	cin>>a>>b;
	if(a<=8&&b<=8)cout<<"Yay!";
	else cout<<":(";
    return 0;
}


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

int main() {
	long long h,w;
	cin>>h>>w;
	//Bishop can reach all diagonals.
	//Basically that's like
	if(h==1 || w==1)
		cout<<1;
	else
		cout<<(h*w + 1)/2;
	return 0;
}

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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MOD = (int) 1e9 + 7;
const int MAXN = (int) 3e3;

// Template-Libs

namespace MATH
{
	inline int fpm(int x, int y)
	{
		int res = 1;
		for(; y; y >>= 1, x = (LL) x * x % MOD) if(y & 1) res = (LL) res * x % MOD;
		return res;
	}
}

using MATH::fpm;

// END

int n, Q;

int A[MAXN + 5];

inline void input()
{
	n = read<int>(), Q = read<int>();
	for(int i = 1; i <= n; ++i) A[i] = read<int>();
}

int val[MAXN + 5], len = 0;

inline void discrete()
{
	for(int i = 1; i <= n; ++i) val[++len] = A[i];
	sort(val + 1, val + len + 1), len = unique(val + 1, val + len + 1) - val - 1;
	for(int i = 1; i <= n; ++i) A[i] = lower_bound(val + 1, val + len + 1, A[i]) - val;
}

inline void solve()
{
	discrete();

	static int f[MAXN + 5][MAXN + 5];

	for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j)
	{
		if(A[i] < A[j]) f[i][j] = 1;
		if(A[i] > A[j]) f[j][i] = 1;
	}

	static const int inv2 = (MOD + 1) / 2;
	for(int k = 1; k <= Q; ++k)
	{
		int u = read<int>(), v = read<int>();

		static int res[MAXN + 5][MAXN + 5];
		for(int i = 1; i <= n; ++i) res[i][u] = res[i][v] = res[u][i] = res[v][i] = 0;

		for(int i = 1; i <= n; ++i) if(i != u && i != v)
		{
			(res[i][v] += (f[i][u] + f[i][v]) % MOD) %= MOD;
			(res[i][u] += (f[i][u] + f[i][v]) % MOD) %= MOD;
			(res[u][i] += (f[u][i] + f[v][i]) % MOD) %= MOD;
			(res[v][i] += (f[u][i] + f[v][i]) % MOD) %= MOD;
		}
		res[u][v] = res[v][u] = (f[u][v] + f[v][u]) % MOD;

		for(int i = 1; i <= n; ++i)
		{
			f[i][u] = (LL) res[i][u] * inv2 % MOD;
			f[i][v] = (LL) res[i][v] * inv2 % MOD;
			f[u][i] = (LL) res[u][i] * inv2 % MOD;
			f[v][i] = (LL) res[v][i] * inv2 % MOD;
		}
	}

	int ans = 0;
	for(int i = 1; i <= n; ++i) for(int j = 1; j < i; ++j) (ans += f[i][j]) %= MOD;
	ans = (LL) ans * fpm(2, Q) % MOD;
	printf("%d\n", (ans + MOD) % MOD);
}

int main()
{
	input();
	solve();

	return 0;
}



Measured memory_bytes: 70784
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

const long long MOD = 998244353;
long long modpow(long long a,unsigned long long b,unsigned long long MOD){
  long long base=a,ans=(1LL);
  while(b){
    if(b&1){
      ans=ans*base%MOD;
    }
    base=base*base%MOD;
    b>>=1;
  }
  return ans;
}
long long invpow(long long a,unsigned long long MOD){
  return modpow(a,MOD-2,MOD);
}
void solve(long long N, long long S, std::vector<long long> A){
  vector<vector<ll>> dp(N+1,vector<ll>(S+1));
  ll inv2=invpow(2,MOD);
  REP(N+1)dp[i][0]=modpow(2,N,MOD);
  FOR(i,1,N+1){
    FOR(j,1,S+1){
      dp[i][j]=dp[i-1][j];
      if(j>=A[i-1]){
        dp[i][j]=(dp[i][j]+dp[i-1][j-A[i-1]]*inv2%MOD)%MOD;
      }
    }
  }
  cout<<dp[N][S]<<endl;
}

int main(){
  cout<<setprecision(1000);
    long long N;
    scanf("%lld",&N);
    long long S;
    scanf("%lld",&S);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, S, std::move(A));
    return 0;
}


Measured memory_bytes: 73660
#include "bits/stdc++.h"
  using namespace std;
  #define ll long long

  ll inf = 1000000000000001;

  int main()
  {
    ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    int x=0;
    for(int i=0;i<n;i++) {
      cin >> a[i];
      x ^= a[i];
    }
    for(int i=0;i<n;i++) {
      cout << (x^a[i])<< " ";
    }

    return 0;
  }

Measured memory_bytes: 4432
//#include <cstdio>
#include <iostream>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

#define DEBUG(x) cerr << #x << ": " << x << endl

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;



int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N;
   cin >> N;

   string S;
   cin >> S;

   set<int> pos[26];
   REP(i, N) {
      int k = S[i]-'a';
      pos[k].insert(i);
   }

   int Q;
   cin >> Q;
   REP(q, Q) {
      int t;
      cin >> t;
      if (t == 1) {
         int idx;
         char c;
         cin >> idx >> c;
         idx--;
         int k = S[idx]-'a';
         pos[k].erase(idx);
         k = c-'a';
         pos[k].insert(idx);
         S[idx] = c;
      }
      else {
         int L, R;
         cin >> L >> R;
         --L, --R;
         int res = 0;
         REP(k, 26) {
            auto it = pos[k].lower_bound(L);
            if (it != pos[k].end() && *it <= R)
               ++res;
         }
         cout << res << '\n';
      }
   }

   return 0;
}


Measured memory_bytes: 24220
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
ans = 0
 
for i in range(N):
  ans += B[A[i]-1]
  if i >0 and A[i] - A[i-1] ==1:
    ans += C[A[i]-2]
        
print(ans)

Measured memory_bytes: 9060
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

typedef pair<int, int> P;

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

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    vector<P> sum(N);
    REP(i, N) {
        cin >> A[i] >> B[i];
        sum[i] = {A[i] + B[i], i};
    }

    sort(sum.begin(), sum.end(), greater<P>());

    int taka = 0;
    int aoki = 0;
    REP(i, N) {
        int t = sum[i].second;
        if (i % 2 == 0) {
            taka += A[t];
        } else {
            aoki += B[t];
        }
    }

    cout << taka - aoki << endl;


    return 0;
}


Measured memory_bytes: 3456
a,b,c=map(int,input().split())
if a%2==b%2==c%2==0 and a==b==c:print(-1);exit()
else:
    ans=0
    while a%2==b%2==c%2==0:
        a,b,c=b//2+c//2,a//2+c//2,a//2+b//2
        ans+=1
print(ans)

Measured memory_bytes: 3060
N=parse(Int,readline())
A=zeros(Int,100)
for i=1:N
	for j=2:i
		while i%j==0
			A[j]+=1
			i=div(i,j)
		end
	end
end
B=zeros(Int,100)
for a=A
	for i=1:a+1
		B[i]+=1
	end
end
println(B[75]+B[25]*(B[3]-1)+B[15]*(B[5]-1)+div(B[5]*(B[5]-1)*(B[3]-2),2))

Measured memory_bytes: 110524
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    string s;
    ll k;
    cin>>s>>k;
    for(ll i=0;i<k;i++){
        if(s[i]!='1'){
            cout<<s[i]<<endl;
            break;
        }
        if(i==k-1){
            cout<<'1'<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
void 
solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int N, M;
vector<int> A;
vector<int> dp;
int MOD = 1e9 + 7;

void solve() {
	cin >> N >> M;
	A.resize(M + 1);
	for (int m = 0; m < M; m++) {
		cin >> A[m];
	}
	A[M] = N + 1;
	if (N == 1) {
		cout << 1 << endl;
		return;
	}
	else if(N == 2){
		if (M == 0)cout << 2 << endl;
		else cout << 1 << endl;
		return;
	}
	dp.resize(N+1);
	dp[0] = 1;
	int m = 0;
	for (int n = 1; n <= N; n++) {
		if (A[m] == n) {
			dp[n] = -1;
			m++;
			continue;
		}
		dp[n] = 0;
		if (n - 1 >= 0) {
			if (dp[n - 1] != -1)dp[n] += dp[n - 1];
		}
		if (n - 2 >= 0) {
			if (dp[n - 2] != -1)dp[n] += dp[n - 2];
		}
		dp[n] %= MOD;
	}
	if (dp[N] == -1)cout << 0 << endl;
	else cout << dp[N] << endl;
	return;
}

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

int num[10] = { 0, 2,5,5,4,5,6,3,7,6 };

void update(int i,int *dp,int m,vector<int> a) {
	int max = -10000;
	for (int j = 0; j < m; j++) {
		if (i - num[a[j]] >= 0) {
			if (max < dp[i - num[a[j]]] + 1)max = dp[i - num[a[j]]] + 1;
		}
	}
	dp[i] = max;
}


int main() {
	
	int n, m;
	cin >> n >> m;
	vector<int> a;
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		a.push_back(temp);
	}
	sort(a.begin(), a.end(), greater<int>());
	int *dp = new int[n+1];
	for (int i = 0; i < n; i++) {
		dp[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		update(i, dp, m, a);
	}
	
	while(n!=0){
		for (int i = 0; i < m; i++) {
			if (dp[n - num[a[i]]] == dp[n] - 1&&n-num[a[i]]>=0) {
				n -= num[a[i]];
				cout << a[i];
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){
  int N,K;
  cin >> N >> K;
  int x[N];
  for(int i=0;i<N;i++){
    cin >> x[i];
  }
  vector<int> ans;
  for(int i=0;i<N-K+1;i++){
    if(x[i]<=0&&x[i+K-1]<=0) ans.push_back(abs(x[i]));
    else if(x[i]<0&&x[i+K-1]>0){
      ans.push_back(2*x[i+K-1]+abs(x[i]));
      ans.push_back(x[i+K-1]+2*abs(x[i]));
    }else if(x[i]>=0&&x[i+K-1]>=0) ans.push_back(x[i+K-1]);
  }
  sort(ans.begin(),ans.end());
  cout << ans[0] << endl;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const ll MOD = (ll)(1e9 + 7);
string s[1005];
ll dp[1005][1005];

int main2() {
  CLR(dp, 0);
  int H, W; cin >> H >> W;
  REP(i, H) cin >> s[i];
  dp[0][0] = 1;
  REP(r, H) REP(c, W) {
    dp[r][c] %= MOD;
    if (r+1 < H && s[r+1][c] == '.') dp[r+1][c] += dp[r][c];
    if (c+1 < W && s[r][c+1] == '.') dp[r][c+1] += dp[r][c];
  }
  ll ans = dp[H-1][W-1];
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


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

int main(){
 int N;
  cin >> N;
  priority_queue<double,vector<double>,greater<double>> Q;
  for(int i=0;i<N;i++){
    double A;
    cin >> A;
    Q.push(A);
  }
  for(int i=0;i<N-1;i++){
    double A=Q.top();
    Q.pop();
    double B=Q.top();
    Q.pop();
    Q.push((A+B)/2);
  }
  cout << fixed << setprecision(10) << Q.top() << endl;
}

Measured memory_bytes: 3828