akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {

	ll n, m; cin >> n >> m;
	vector<pair<ll, ll>> pa;
	for (ll i = 0; i < n; i++) {
		ll a;  cin >> a;
		pa.push_back({ a,1 });
	}
	for (ll i = 0; i < m; i++) {
		ll b, c; cin >> b >> c;
		pa.push_back({ c,b });
	}
	sort(pa.rbegin(), pa.rend());
	ll ans = 0;
	ll cnt = 0;
	for (ll i = 0; i < pa.size(); i++) {
		if (cnt + pa[i].second <= n) {
			ans += pa[i].second * pa[i].first;
			cnt += pa[i].second;
		}
		else { // n < cnt + pa[i].second
			if (cnt <= n) {
				ans += (n - cnt) * pa[i].first;
				cnt = n;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

int ans[3][1000][1000] = {};
int main()
{
	int n,m;
	string x[1000];
	string an[2];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
	cin >> an[0];
	cin >> an[1];
	int mmm[4] = { 0, 0, 1, 1 };
	int nnn[4] = { 0, 1, 0, 1 };
	int sum = 0;
	for (int i = 0; i < n - 1; i++)
	{
		for (int I = 0; I < m - 1; I++)
		{
			int a = -1;
			int ji = -1;
			int jI = -1;
			char as;
			for (int k = 0; k < 4; k++)
			{
				if (x[i + mmm[k]][I + nnn[k]] == an[mmm[k]][nnn[k]])
				{

				}
				else
				{
					a++;
					as = an[mmm[k]][nnn[k]];
					ji = i + mmm[k];
					jI = I + nnn[k];
				}
			}
			if (a == -1)
			{
				sum++;
				for (int k = 0; k < 4; k++)
				{
					for (int s = 0; s < 3;s++)
						ans[s][i + mmm[k]][I + nnn[k]]--;
					
				}
			}
			else if (a == 0)
			{
				switch (as)
				{
				case'J':
					ans[0][ji][jI]++;
					break;
				case'O':
					ans[1][ji][jI]++;
					break;
				case'I':
					ans[2][ji][jI]++;
					break;
				}
			}
		}
	}
	int gh = 0;
	for (int i = 0; i < n; i++)
	{
		for (int k = 0; k < m; k++)
		{
			for (int s = 0; s < 3;s++)
				if (gh < ans[s][i][k])gh = ans[s][i][k];
		}
	}
	cout << sum + gh << endl;
	

}

Measured memory_bytes: 13976
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def isBipartite():
    sign = [-1] * N
    sign[0] = 0
    st = [0]
    while st:
        now = st.pop()
        p = sign[now] ^ 1

        for to in edges[now]:
            if sign[to] == -1:
                st.append(to)
                sign[to] = p
                continue
            if sign[to] != p:
                return -1

    return sum(sign)

s = isBipartite()

if s == -1:
    print(N * (N - 1) // 2 - M)
else:
    print(s * (N - s) - M)


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

int main() {
  
  int A, B, C; cin >> A >> B >> C;
  
  for (int i = 1; i < 101; i++) {
    
    int tmp = A * i;
    
    if (tmp % B == C) {
      cout << "YES" << endl;
      return 0;
    }
    
  }
  
  cout << "NO" << endl;
  
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string n; cin>>n;
	int r=count(n.begin(),n.end(),'0');
	int b=count(n.begin(),n.end(),'1');
	cout<<min(r,b)*2<<"\n"s;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
 
using namespace std;
 
struct Edge {
  int t,next;
  Edge() {}
  Edge(int a,int b):t(a),next(b) {}
};
 
Edge e[200005];
int head[100005],d[100005],rt1,rt2;
 
void dfs(int x,int fa) {
  for(int i=head[x];i;i=e[i].next)
    if (e[i].t!=fa) {
    	int u=e[i].t;
    	if (d[u]==2) dfs(u,x);
    	else if (u==rt1) {
    		puts("Yes");
    		exit(0);
		}
	}
}
 
int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[2*i-1]=Edge(y,head[x]);
  	head[x]=2*i-1;
  	e[2*i]=Edge(x,head[y]);
  	head[y]=2*i;
  	d[x]++;d[y]++;
  }
  for(int i=1;i<=n;i++)
    if (d[i]&1) {
    	puts("No");
    	return 0;
	}
  int cnt=0;
  for(int i=1;i<=n;i++)
    if (d[i]>=6) {
    	puts("Yes");
    	return 0;
	}
	else if (d[i]==4) cnt++;
  if (cnt<2) {
  	puts("No");
  	return 0;
  }
  if (cnt>2) {
  	puts("Yes");
  	return 0;
  }
  for(int i=1;i<=n;i++)
    if (d[i]==4) {
    	if (!rt1) rt1=i; else rt2=i;
	}
  dfs(rt1,0);
  puts("No");
  return 0;
}

Measured memory_bytes: 3328
import math

def plot(x,y):
    print(f'{x:.8f} {y:.8f}')

def Koch(n,x1,y1,x2,y2):
    if n==0:
        plot(x1,y1)
        return
    sx=(2*x1+x2)/3
    sy=(2*y1+y2)/3
    tx=(x1+2*x2)/3
    ty=(y1+2*y2)/3
    ux=(tx-sx)*(1/2)-(ty-sy)*(math.sqrt(3)/2)+sx
    uy=(tx-sx)*(math.sqrt(3)/2)+(ty-sy)*(1/2)+sy
    Koch(n-1,x1,y1,sx,sy)
    Koch(n-1,sx,sy,ux,uy)
    Koch(n-1,ux,uy,tx,ty)
    Koch(n-1,tx,ty,x2,y2)

   

n=int(input())    
Koch(n,0,0, 100,0)
plot(100,0)
    
    
    


Measured memory_bytes: 5752
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == -1\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x,y))
print(ans)

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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string>vst;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef map<int,int> dct;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define all(ct) ct.begin() , ct.end()
#define endl "\n"
#define fr(i,a) for(auto i:a)
#define f(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define in(d,v) d.find(v)!=d.end()
#define mp make_pair
#define size(a) int(a.size())

const ll mod = 1e9 + 7;
const ll inf = ll(1e18);
const double PI = acos(-1);

ll modexp(ll x,ll n,ll md){
    if(n==0)return 1;
    if(n%2==0)return modexp((x*x)%md,n/2,md);
    return (x*modexp((x*x)%md,n/2,md))%md;
}

int main(){
    fastio;
    //clock_t tm = clock();
    int h,a;
    cin>>h>>a;
    cout<<ceil((h*1.0)/a)<<endl;
    //cout<<((clock()-tm)*1.0)/CLOCKS_PER_SEC<<endl;
}

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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    ll sumA = 0, sumB = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sumA += A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
        sumB += B[i];
    }
    if (sumA < sumB) {
        cout << -1 << endl;
        return;
    }
    priority_queue<ll> Q;

    ll sum = 0;
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] >= B[i]) {
            Q.push(A[i] - B[i]);
        } else {
            sum += B[i] - A[i];
            ans++;
        }
    }

    while(!Q.empty() && sum > 0) {
        sum -= Q.top(); Q.pop();
        ans++;
    }

    cout << ans << endl;

}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();

    #ifdef LOCAL_ENV
    assert(cin.rdstate() & ios_base::eofbit);
    #endif
}


Measured memory_bytes: 2936
import java.io.*;
public class Main {
   public static void main(String[] args) throws IOException{
	   BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
	   String str;
	   StringBuffer s = new StringBuffer("");
	   str = buf.readLine();
	   s.append(str);
	   s.reverse();
	   System.out.println(s);
   }
}

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

int main() {
  int m, d1, d10;
  int M, D;
  cin >> M >> D;

  int count=0;
  for(m=0; m<M; m++)
    {
    for(int d=0; d<D; d++)
      {
      d1  = (d+1) % 10;
      d10 = (d+1) / 10;
      if(d1>=2 && d10>=2 && m+1==d1*d10)
        {
        count += 1;
        //cout << m+1 << ' ' << d+1 << endl;
        }
      }
    }
  cout << count;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define Pi 3.1415926535
#define MOD 1000000007;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}
void yes(){cout << "Yes" << endl;}
void no(){cout << "No" << endl;}

int solve(){
    double a,b; cin >> a;


    cout << a*2*Pi << endl;

    return 0;
}

int main(){
    cin.tie(0);
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 3772
a,b=map(int,input().split())
ans=-1
arr = [list(map(int,input().split())) for i in range(b)]

for i in range(1001):
  j=str(i)
  if len(j)==a and all(j[s-1]==str(t) for s,t in arr):
    ans = i
    break
print(ans)

Measured memory_bytes: 3064
#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(){
    ll n;
    vector<ll> v(5);
    cin >> n;
    for(auto& i : v) cin >> i;
    ll m = *min_element(all(v));
    cout << (n + m - 1) / m + 4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;

int main()
{
    int h, w;
    cin >> h >> w;
    vvc b(h);
    for (int r = 0; r < h; r++)
    {
        b[r] = vc(w);
        for (int c = 0; c < w; c++)
        {
            cin >> b[r][c];
        }
    }

    vi rows;
    for (int r = 0; r < h; r++)
    {
        for (int c = 0; c < w; c++)
        {
            if (b[r][c] == '#')
            {
                rows.push_back(r);
                break;
            }
        }
    }

    vi cols;
    for (int c = 0; c < w; c++)
    {
        for (int r = 0; r < h; r++)
        {
            if (b[r][c] == '#')
            {
                cols.push_back(c);
                break;
            }
        }
    }

    for (auto r : rows)
    {
        for (auto c : cols)
        {
            cout << b[r][c];
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	N := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	result := 0
	for i := 0; i < 60; i++ {
		t := 0
		bs := (A[N-1] >> uint(i)) & 1
		for j := N - 2; j > -1; j-- {
			if (A[j]>>uint(i))&1 == 0 {
				t += bs
			} else {
				t += (N - (j + 1)) - bs
				bs++
			}
		}
		t %= 1000000007
		B := (1 << uint(i)) % 1000000007
		result += (t * B) % 1000000007
		result %= 1000000007
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 8960
#include <stdio.h>
int chmax(int a, int b){
	return a > b ? a : b;
}
int main(){
  int n, ans, i, j, max=0;
  scanf("%d",&n);
  int map[n][2];
  for (j = 0; j < 2; j++)for(i = 0; i < n; i++)scanf("%d",&map[i][j]);
  for (i = 0; i < n; i++) {
  	int sum=0;
    for (j = 0; j <= i; j++) sum+= map[j][0];
    for (j = n - 1; j >= i; j--) sum += map[j][1];
    max = chmax(max, sum);
  }
  printf("%d",max);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0); 
    cin.tie(0);   
	ll n,a[200009];
	string s;
	for(int i=0;i<5;i++)
	{
		cin>>a[i];
		if(a[i]==0)
			cout<<i+1;
	}
	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,T ; cin >> N >> T;
vector<pair<int, int>> c(N);
int ans,a,b;
bool flag = false;
for(int i = 0; i < N ; i++){
  cin >> a >> b;
  c[i] = make_pair(a,b);
}
  sort(c.begin(),c.end());
  for(int j = 0; j < N; j++){
    if(c[j].second <= T){
      ans = c[j].first;
      flag = true;
      break;
    }

  }
  if(flag){
    cout << ans << endl;
  }
  else{
    cout << "TLE" <<endl;
  }
}

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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

int n,y;

int main()
{
  cin >> n >> y;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; i+j <= n; j++) {
      if (i*10000+j*5000+(n-i-j)*1000 == y) {
        printf("%d %d %d\n",i,j,n-i-j);
        return 0;
      }
    }
  }

  cout << "-1 -1 -1" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); bool s=false; if(c=='-'){s=true;c=getchar_unlocked();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); int s=0; if(c=='-'){s=1;c=getchar_unlocked();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar_unlocked(); while(c==' '||c=='\n') c=getchar_unlocked(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar_unlocked(); } *s='\0'; return len; }

char **m;
int **d;

int s[1000000][2];
int main(void){
	int h=nextint();
	int w=nextint();
	int k=nextint();
	int x1=nextint()-1;
	int y1=nextint()-1;
	int x2=nextint()-1;
	int y2=nextint()-1;
	m = malloc(h*sizeof(char*));
	d = malloc(h*sizeof(int*));
	for(int i=0; i<h; i++){
		m[i] = malloc(w+1);
		d[i] = calloc(w, sizeof(int));
		nextstr(m[i]);
	}
	int sl=0, sr=0;
	d[x1][y1]=1;
	s[sr][0]=x1; s[sr][1]=y1; sr++;
	while(sl<sr){
		int x=s[sl][0], y=s[sl][1]; sl++;
		int D=d[x][y]+1;
		{
			int X=x-1, Y=y;
			for(int i=0; i<k && X>=0 && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]==D); i++){ if(d[X][Y]==0){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} X--; }
		}
		{
			int X=x+1, Y=y;
			for(int i=0; i<k && X<h  && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]==D); i++){ if(d[X][Y]==0){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} X++; }
		}
		{
			int X=x, Y=y-1;
			for(int i=0; i<k && Y>=0 && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]==D); i++){ if(d[X][Y]==0){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} Y--; }
		}
		{
			int X=x, Y=y+1;
			for(int i=0; i<k && Y<w  && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]==D); i++){ if(d[X][Y]==0){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} Y++; }
		}
		//printf("%d %d %d ", x+1, y+1, D-1);
	}
	printf("%d\n", d[x2][y2]==0?-1:d[x2][y2]-1);
}


Measured memory_bytes: 12328
n=int(input())

p_list=list(map(int, input().split()))
p_list_asc=sorted(p_list)

count=0

for i in range(n):
  if p_list[i] != p_list_asc[i]:
    count+=1

if 2 < count:
  print('NO')
else:
  print('YES')

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>

int main() {
	int n,count=0,a;
	std::cin >> n;

	std::vector<int> v(n);
	std::vector<int> s(n);

	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		v[i] = x;
		s[i] = x;
	}

	std::sort(v.begin(), v.end());


	for (int i = 0; i < v.size(); i++) {
		if (v[i] == s[i]) {
			count++;
		}
	}

	a=v.size() - count;

	//std::cout << count << std::endl;

	if (a==0||a==2) {
		std::cout << "YES" << std::endl;
		return 0;
	}


	std::cout << "NO" << std::endl;
	


	
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  HelloWorld
//
//  Created by purple on 2020/04/13.
//  Copyright © 2020 Purple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <cmath>

using namespace std;

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

    int x,y;
    int i=1;
    while(1){
        cin >> x >> y;
        
        if(x==0 && y==0)
            break;
        else{
            if(x>y)
                cout << y << " " << x << endl;
            else
                cout << x << " " << y << endl;
            
        }

        i++;
    }

    return 0;
    
}



Measured memory_bytes: 3092
//using my submission of https://www.codechef.com/problems/TOMJERGA
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#define ll long long int
using namespace std;

struct node{
	int val,vertex;
	node()
	{
		val=0;vertex=-1;
	}
	node(int v1,int v2)
	{
		val=v1;
		vertex=v2;
	}
};

int timer=0,n,lim;
node data[100011][2]={};
vector< int > graph[100011];
int times[100011][2]={};
int anc[100011][20]={};
int depth[100011]={};
int dp[100011]={};
int dfs(int u,int pa,int d=0)
{
	timer++;
	anc[u][0]=pa;
	depth[u]=d;
	times[u][0]=timer;
	data[u][0]={0,u};
	data[u][1]={0,-1};
	for(auto v:graph[u])
		if(v!=pa){
			int r=dfs(v,u,d+1);
			node temp={1+r,v};
			if(temp.val>=data[u][0].val){
				swap(data[u][0],data[u][1]);
				data[u][0]=temp;
			}
			else if(temp.val>=data[u][1].val)
				data[u][1]=temp;
		}
	times[u][1]=timer;
	return data[u][0].val;
}

void dfs2(int u,node tmp){
	dp[u]=((tmp.vertex>0)?tmp.val:0);
	tmp.val+=1;
	node tmp2=tmp;

	if(tmp.val<=(data[u][1].val+1))
		tmp={data[u][1].val+1,u};

	if(tmp2.val<=(data[u][0].val+1))
		tmp2={data[u][0].val+1,u};	

	for(int v:graph[u])
		if(v!=anc[u][0])
			dfs2(v,((data[u][0].vertex!=v)?tmp2:tmp));
}

bool is_anc(int u,int v){
	return (!u)||(times[u][0]<=times[v][0] && times[u][1]>=times[v][1]);
}

int lca(int v1,int v2)
{
	int k=1+lim,v;
	while(k--){
		v=anc[v1][k];
		if(!is_anc(v,v2))
			v1=v;
	}
	return (!is_anc(v1,v2))?(anc[v1][0]):v1;
}

int up(int u,int d)
{
	int i=0;
	while(d)
	{
		if(d&1) u=anc[u][i];
		d>>=1; i++;
	}
	return u;
}

void pre_lca()
{
	int i,j; anc[0][0]=0;
	for(i=1;i<=lim;i++)
		for(j=0;j<=n;j++)
			anc[j][i]=anc[anc[j][i-1]][i-1];
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T,i,u,v,x,y;
	
		cin>>n>>y>>x;
		lim=ceil(log2(n));
		timer=0;

		for(i=0;i<=n;i++)
			graph[i].clear();

		for(i=1;i<n;i++)
		{
			cin>>u>>v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}
		
		dfs(1,0,1);

		pre_lca();
		node tmp;

		dfs2(1,tmp);
		
		u=lca(x,y); int l=depth[x]+depth[y]-2*depth[u];
		if(depth[x]<=depth[y])
			cout<<(((x==y)?0:((l-((l-1)/2))+data[up(y,(l-1)/2)][0].val))-1)<<endl;
		else{
			u=up(x,l-(l-1)/2);
			cout<<((l-((l-1)/2)+max(dp[u],data[u][is_anc(data[u][0].vertex,x)].val))-1)<<endl;
		}
	
}

Measured memory_bytes: 24832
/*
 * atcoder/dp_3rd/i.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
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; }

const int MAX = 3100;
ll N;
vector<double> A;
double dp[MAX][MAX];

void input() {
  cin >> N;
  double a;
  loop(n,0,N) {
    cin >> a;
    A.push_back(a);
  }
}

void solve() {
  loop(i,0,N+1) loop(j,0,N+1) dp[i][j] = 0.0;
  dp[0][0] = 1.0;
  for (int n=1; n<=N; n++) {
    for (int heads=0; heads<=n; heads++) {
      // 全部裏
      if (heads==0) { dp[n][0] = dp[n-1][0] * (1.0-A[n-1]); continue; }
      // n枚振ったときにheads枚表である確率
      // 1) 前回まででheads-1枚出て今回表
      // 2) 前回まででheads枚かつ今回裏
      dp[n][heads] = dp[n-1][heads-1] * A[n-1]; // 1)
      dp[n][heads] += dp[n-1][heads] * (1.0 - A[n-1]); // 2)
      // cout << dp[n][heads] << " " << n << " " << heads << endl;
    }
  }

  double total = 0.0;
  for (int j=(N+1)/2; j<=N; j++) {
    total += dp[N][j];
  }
  cout << total << endl;
}

void dump() {
  for (int heads=0; heads<=N; heads++) {
    for (int n=0; n<=N; n++) {
      cout << dp[n][heads] << "\t";
    }
    cout << endl;
  }
}

int main() {
  cout.precision(15);
  input();
  solve();
  // dump();
  return 0;
}


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

#define loop(s, e, i) for (int i = s; i < e; ++i)
#define print(s) cout << s << endl;
#define DIV 1000000007
#define ll long long
using namespace std;

/*
浮動小数点の入力
cout << fixed << setprecision(9) << endl;
*/

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll a, b, c, d;
  cin >> a >> b >> c >> d;

  ll result = a * c;
  result = max(result, a*d);
  result = max(result, b*c);
  result = max(result, b*d);
  print(result);
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	int s=1;
	for(int i=0;i<n;i++){
		s=min(s*2,s+k);
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(obj) (obj).begin(),(obj).end()
typedef long long llong;
llong mod=1e9+7;

void Count(vector<int> A,vector<int> &B,int n){
  vector<int> C(10000,0);
  for(int i=0;i<n;i++){
    C.at(A.at(i))++;
  }
  for(int i=1;i<10000;i++){
    C.at(i)+=C.at(i-1);
  }
  for(int i=n-1;i>=0;i--){
    B.at(C.at(A.at(i))-1)=A.at(i);
    C.at(A.at(i))--;
  }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
 int n;
 cin>>n;
vector<int> A(n),B(n);
for(int i=0;i<n;i++)cin>>A.at(i);
Count(A,B,n);
for(int i=0;i<n;i++){
  cout<<B.at(i);
  if(i!=n-1)cout<<" ";
}
cout<<endl;
return 0;
}




Measured memory_bytes: 26352
N = int(input())
P = list(map(lambda a: int(a) - 1, input().split()))

ans = 0
for i in range(N):
    p = P[i]
    if p == i:
        if i < N - 1:
            P[i], P[i + 1] = P[i + 1], P[i]
        ans += 1

print(ans)

Measured memory_bytes: 13880
from itertools import product

N = int(input())

F = []
for i in range(N):
  F.append(list(map(int, input().split())))

P = []
for i in range(N):
  P.append(list(map(int, input().split())))
  
ans = -1e9-1
for i in product((0,1),repeat=10):
  gain = 0
  if i == (0,0,0,0,0,0,0,0,0,0):
    continue
  for j in range(N):
    cnt = 0
    for k in range(10):
      cnt += i[k]*F[j][k]
    gain += P[j][cnt]
  ans = max(ans,gain)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
using namespace std;
signed main() {
  int N, K;
  cin >> N >> K;
  int h[N];
  vector<int> dp(N, INF);
  for (int i = 0; i < N; i++) cin >> h[i];
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 1; j <= K && i+j < N; j++) {
      dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j])); 
    }
  }
  cout << dp[N-1] << endl; 
}


Measured memory_bytes: 1792
var
  i,j,a1,a2,n,r:integer;
  a:array[1..100005] of integer;
begin
  read(n);
  r:=0;
  j:=1;
  for i:=1 to n do read(a[i]);
  while j<=n do
  begin
    r:=r+1;
    a1:=a[j];
    j:=j+1;
    while (a[j]=a1) and (j<=n) do j:=j+1;
    a2:=a[j];
    j:=j+1;
    while ((a1-a2) * (a[j-1]-a[j]) >= 0) and (j<=n) do j:=j+1;
  end;
  writeln(r);
end.


Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

int main(){
	ll n ; cin >> n ;
	ll ans = 0 ;
	for(int i=1;i<=n;i++) ans += (n+1-i)*i ;
	for(int i=0;i<n-1;i++){
		ll a,b ;
		cin >> a >> b ;
		ans -= min(a,b)*(n-max(a,b)+1) ;
	}
	cout << ans << endl ;
}

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

int Fibonacci(const int& n)
{
	int TwicePreviousValue = 1;
	int PreviousValue = 1;
	if(n == 0) return TwicePreviousValue;
	if(n == 1) return PreviousValue;
	int CurrentValue = TwicePreviousValue + PreviousValue;
	for(int i = 2; i < n; i++){
		CurrentValue  += PreviousValue;
		PreviousValue += TwicePreviousValue;
		TwicePreviousValue = PreviousValue - TwicePreviousValue;
	}
	return CurrentValue;
}

int main()
{
	int n;
	cin >> n;
	cout << Fibonacci(n) << endl;
	return 0;
}

Measured memory_bytes: 3088
def main():
    import sys
    from itertools import accumulate

    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))

    b = list(accumulate(a))
    diff = b[-1]
    total = b[-1]
    for x in b:
        diff = min(diff, abs(total - 2 * x))
    print(diff)

if __name__ == '__main__':
     main()


Measured memory_bytes: 25748
#include<cstdio>

const int A = 1e9 + 7;
int h, w, a, b;

int po(int x, int y) {
    int ans = 1;
    while (y > 0) {
        if (y & 1) ans = static_cast<long>(ans) * x % A;
        x = static_cast<long>(x) * x % A;
        y >>= 1;
    }
    return ans;
}

int main() {
    scanf("%d %d %d %d", &h, &w, &a, &b);
    const int n = h + w - 1;
    int per[n];
    int inv[n];
    
    per[0] = 1;
    for (int i = 1; i < n; i++) per[i] = static_cast<long>(per[i - 1]) * i % A;
    inv[n - 1] = po(per[n - 1], A - 2);
    for (int i = n - 2; i >= 0; i--) inv[i] = static_cast<long>(inv[i + 1]) * (i + 1) % A;
    
    int ans = 0;
    for (int i = 0; i < h - a; i++) {
        int ans1 = static_cast<long>(per[i + b - 1])
                 * inv[i] % A * inv[b - 1] % A
                 * per[h - i + w - b - 2] % A
                 * inv[h - i - 1] % A * inv[w - b - 1] % A;
        ans = (static_cast<long>(ans) + ans1) % A;
    }

    printf("%d\n", ans);
    return 0;
}


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

using ll = long long;
const ll amari = 1e9+7;
const char BC = 'A' - 'a';
#define ben(a) a.begin(),a.end()
#define pb(a,b) a.push_back(b)

int main(){
	string s;
	cin >> s;
	string ans = "";
	for(int i = 0; i < s.size(); i++){
		if(s[i] != 'B')pb(ans,s[i]);
		else if(ans.size())ans.pop_back();
	}
	cout << ans << endl;
	return 0; 
}

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

int N, M, Q;

tuple<int, int, int, int> scores[55];
int seq[15];

int calculateScore()
{
	int ans = 0;
	for(int i = 1; i <= Q; i++)
	{
		int ai = get<0>(scores[i]), bi = get<1>(scores[i]), ci = get<2>(scores[i]), di = get<3>(scores[i]);
		if(seq[bi] - seq[ai] == ci)
			ans += di;
	}
	
	return ans;
}

int maxScore = 0;
void recurse(int pos, int val)
{
	seq[pos] = val;
	if(pos == N)
	{
		//printf("%d\n", calculateScore());
		maxScore = max(maxScore, calculateScore());
	}
	
	else
	{
		for(int i = val; i <= M; i++)
			recurse(pos + 1, i);
	}
}

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	
	int i;
	for(i = 1; i <= Q; i++)
	{
		int ai, bi, ci, di;
		scanf("%d%d%d%d", &ai, &bi, &ci, &di);
		
		scores[i] = make_tuple(ai, bi, ci, di);
	}

	recurse(1, 1);
	printf("%d", maxScore);
}


Measured memory_bytes: 3816
#include <iostream>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

using ll = long long int;
ll gcd (ll a, ll b)
{
	ll tmp;
	while (0 != b)
	{
		tmp = a % b;
		a = b;
		b = tmp;
	}

	return a;
}

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

	for (int i=0; i<t; ++i)
	{
		ll a, b, c, d; cin >> a >> b >> c >> d;

		if (b > a || b > d)
		{
			cout << "No" << endl;
			continue;
		}
		if (b <= c)
		{
			cout << "Yes" << endl;
			continue;
		}

		ll g = gcd(b, d);
		if (b - g + a % g <= c)
		{
			cout << "Yes" << endl;
			continue;
		}

		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  while(cin >> n){
    int ans[100]={},cnt=0;
    while(n){
      ans[cnt]=n%2;
      n/=2;
      cnt++;
    }
    int tmp=1;
    bool f=true;
    for(int i=0;i<cnt;i++){
      if(ans[i]>0){
        if(!f){
          cout << " ";
        }
        cout << ans[i]*tmp;
        f=false;
      }
      tmp*=2;
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 2964
#include<stdio.h>
int main(){
    int K;
    int A,B;
    scanf("%d",&K);
    scanf("%d %d",&A,&B);
    for(int i=A;i<=B;i++){
        if(i%K==0){
            printf("OK\n");
            return 0;
        }else if(i%K!=0){
            
        }
    }
    printf("NG\n");
}

Measured memory_bytes: 1620
#include <stdio.h>
#include <string.h>
#include <stack>
#include <iostream>
using namespace std;

#define LARGE_NUM 114514
 
using namespace std;
 
int main(void)
{
	int N;
	cin >> N;;
	int t[LARGE_NUM];
	int a[LARGE_NUM];

	int ti[LARGE_NUM] = {0};
	int ai[LARGE_NUM] = {0};

	int v[LARGE_NUM] = {0};//想定しうる山の数

	int M = N;

	long V = 1;

	for(int i=0;i<N;i++){
		cin >> t[i];
	}
	for(int i=0;i<N;i++){
		cin >> a[i];
	}


	for(int i=0;i<N;i++){
		if(i==0 ||t[i]!=t[i-1]){
			v[i]  = 1;
			ti[i] = 1;
		}
		if(i==N || a[i]!=a[i+1]){
			v[i]  = 1;
			ai[i] = 1;
		}
	}

	for(int i=0;i<N;i++){
		if(v[i]!=1){
			v[i]=min(t[i],a[i]);
		}
		else{
			if(ti[i] == 1 && t[i] > a[i]){
				v[i] = 0;
			}
			if(ai[i] == 1 && a[i] > t[i]){
				v[i] = 0;
			}
		}
	}

	for(int i=0;i<N;i++){
		V *= (long)v[i];
		V %= 1000000007;
	}
	
	cout << V << endl;
	return 0;
 
}

Measured memory_bytes: 2432
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

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

func nextFloat() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	for {
		h := nextInt()
		w := nextInt()
		if h == 0 {
			break
		}
		for i := 0; i < h; i++ {
			for j := 0; j < w; j++ {
				if i%2 == j%2 {
					fmt.Printf("#")
				} else {
					fmt.Printf(".")
				}
			}
			fmt.Println()
		}
		fmt.Println()
	}
}



Measured memory_bytes: 1084
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>

using namespace std;
struct Node{
  int value;
  Node *left;
  Node *right;
};

struct Node *NIL;

class BinarySearchTree{
  private:
    Node *root;
  public:
    BinarySearchTree(){
      root=NIL;
    }
    void insert(int value){
      Node *node = (Node*)malloc(sizeof(Node));
      node->value = value;
      node->right = NIL;
      node->left = NIL;
      Node* x=root;
      Node* y=NIL;
      while(x!=NIL){
        y = x;
        if(node->value < x->value){
          x = x->left;
        }
        else{
          x = x->right;
        }
      }
      if(y==NIL)root = node;
      else if(node->value < y->value)y->left = node;
      else y->right = node;
    }
    void print(){
      inorderWalk(root);
      cout << endl;
      preorderWalk(root);
      cout << endl;
    }
    void inorderWalk(Node *node){
      if(node == NIL)return;
      inorderWalk(node->left);
      cout << ' ' << node->value;
      inorderWalk(node->right);
    }
    void preorderWalk(Node *node){
      if(node == NIL)return;
      cout << ' ' << node->value;
      preorderWalk(node->left);
      preorderWalk(node->right);
    }
};


int main(){
  int n;cin >> n;
  string com;
  BinarySearchTree T;
  for(int i=0;i<n;i++){
    cin >> com;
    if(com == "insert"){
      int num;cin >> num;
      T.insert(num);
    }
    else if(com == "print"){
      T.print();
    }
  }
}


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

#define sc second
#define fr first

#define ll long long
#define pi pair<int,int>
#define ppi pair<pi,pi>
#define mp make_pair
using namespace std;



int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	string s; cin >> s;
	int n = s.size();
	int mn = 1e9;
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		cnt += (s[i] - '0') ^ (i & 1);
	}
	mn = min(mn, cnt);
	cnt = 0;
	for (int i = 0; i < n; i++)
	{
		cnt += (s[i] - '0') ^ (!(i & 1));
	}
	mn = min(mn, cnt);
	cout << mn << '\n';




	return 0;
}


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

int main(){
  string s;
  cin >> s;
  int t = stoi(s);
  //0を+ 1を-
  for(int i = 0; i < (1 << 3); i++){
    int result = t / 1000, s_i = t % 1000;
    vector<char> op(3);
    bitset<3> b(i);
    for(int j = 0; j < 3; j++){
      if(b.test(j)){
        result = result - s_i % 10;
        op.at(j) = '-';
      }else{
        result = result + s_i % 10;
        op.at(j) = '+';
      }
      s_i = s_i / 10;
    }
    if(result == 7){
      cout << s.at(0) << op.at(2) << s.at(1) << op.at(1) << s.at(2) << op.at(0) << s.at(3) << "=7" <<endl;
      break;
    }
  }
}
      

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int a, b, c, x, y; cin >> a >> b >> c >> x >> y;
    c *= 2;
    if (c >= a + b) cout << x * a + y * b << endl;
    else {
        int z = min(x, y);
        cout << (x - z) * min(a, c) + (y - z) * min(b, c) + z * c << endl;
    }
}


Measured memory_bytes: 256
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
int n , S;
int A[MAXN] , f[MAXN];

void solve() {
	cin >> n >> S;
	int x = 1;
	f[0] = 1;
	rep( i , 1 , n ) {
		scanf("%d",A + i);
		x = ( x + x ) % P;
		per( j , S , A[i] ) f[j] = ( f[j] + ( P + 1 ) / 2 * 1ll * f[j - A[i]] % P ) % P;
	}
	cout << f[S] * 1ll * x % P << endl;
	
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}



Measured memory_bytes: 3708
function Main(input) {
    var input = input.split(' ');
    var rgb = parseInt(input[0] + input[1] + input[2], 10);
    if(rgb % 4 === 0) {
        console.log('YES');
    } else{
        console.log('NO');
    }

    }
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
n = int(input())
ans = 0
p = -999
a = [i - 1 for i in map(int, input().split())]
b = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in a:
    ans += b[i]
    if i == p + 1:
        ans += c[p]
    p = i
print(ans)

Measured memory_bytes: 3064
import bisect

n, k = map(int, input().split())
*v, = map(int, input().split())
candidate = []
for i in range(k+1):
    for j in range(k+1-i):
        if i + j >= n:
            candidate.append(v)
        elif j == 0:
            candidate.append(v[:i])
        else:
            candidate.append(v[:i]+v[j*(-1):])
ans = 0
for cand in candidate:
    cand.sort()
    idx = bisect.bisect(cand, -1)
    rem = k-len(cand)
    p = min(idx, rem)
    if ans < sum(cand[p:]):
        ans = sum(cand[p:])
print(ans)


Measured memory_bytes: 43372
n,k=map(int,input().split())
li=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:(x[1],x[0]))
ans=float("INF")
#print(li)
for i in range(n):
    for j in range(i+1,n):
        ux,lx=max(li[i][0],li[j][0]),min(li[i][0],li[j][0])
        l,r=0,0
        cnt=int(lx<=li[r][0]<=ux)
#        print("!",ux,lx,"!",end="")
        while True:
#            print("cnt:",cnt,end="")
            while r<n-1 and cnt<k:
                r+=1
                cnt+=int(lx<=li[r][0]<=ux)
            if cnt<k or not(0<=r<=n-1) or not(0<=l<=n-1) or r<=l :break
            if ans>(ux-lx)*(li[r][1]-li[l][1]):
                ans=(ux-lx)*(li[r][1]-li[l][1])
#                print(i,j,l,r,cnt,ans)
            cnt-=int(lx<=li[l][0]<=ux)
            l+=1
print(ans)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main(void){
  int a[3];
  int fcount = 0, scount = 0;
  
  cin >> a[0] >> a[1] >> a[2];
  
  for(int x : a){
    if(x == 5) fcount++;
    else if(x == 7) scount++;
  }
  
  if(fcount == 2 && scount == 1) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}
  

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

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	int Five=0, Seven=0;
	if(a==5)	Five++;
	else		Seven++;
	if(b==5)	Five++;
	else		Seven++;
	if(c==5)	Five++;
	else		Seven++;
	
	if(Five==2 && Seven==1)	cout << "YES" << endl;
	else			cout << "NO" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,p[100003],h[100003];
long long ans;
struct Inpdata{
    int r, c;
}arr[100003];
struct data{
    int g, idx;
    bool operator<(const data &r)const{
        return g<r.g;
    }
}res[100003];
vector<int> er[100003],ec[100003];
set<int> rlib,clib;
int fnd(int num){
    return (p[num]==num)?num:(p[num]=fnd(p[num]));
}
void uni(int a, int b){
    a=fnd(a),b=fnd(b);
    if(h[a]>h[b]) p[b]=a;
    else if(h[a]<h[b]) p[a]=b;
    else{
        p[a]=b;
        h[b]++;
    }
    return;
}
int main(){
    int i,j,cnt;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        p[i]=i;
        scanf("%d %d",&arr[i].r,&arr[i].c);
        er[arr[i].r].push_back(i);
        ec[arr[i].c].push_back(i);
    }
    for(i=1;i<=100000;i++)if(er[i].size()>=2){
        vector<int>::iterator vi=er[i].begin();
        for(++vi;vi!=er[i].end();++vi){
            uni(er[i][0],*vi);
        }
    }
    for(i=1;i<=100000;i++)if(ec[i].size()>=2){
        vector<int>::iterator vi=ec[i].begin();
        for(++vi;vi!=ec[i].end();++vi){
            uni(ec[i][0],*vi);
        }
    }
    for(i=1;i<=n;i++){
        res[i]={fnd(i),i};
    }
    sort(res+1,res+1+n);
    for(i=1;i<=n;i=j){
        j=i;
        cnt=0;
        do{
            rlib.insert(arr[res[j].idx].r);
            clib.insert(arr[res[j].idx].c);
            j++;
            cnt++;
        }while(res[j].g==res[j-1].g);
        ans+=(long long)rlib.size()*clib.size()-cnt;
        rlib.clear();
        clib.clear();
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> x(N);
    rep(i, 0, N){
        cin >> x[i];
    }

    ll ans = 1e18;
    rep(i, 0, N-K+1){
        if(x[i] < 0 && x[K+i-1] > 0){
            ll tmp = 2 * abs(x[i]) + x[i + K -1];
            tmp = min(tmp, abs(x[i]) + 2 * x[i + K -1]);
            ans = min(ans, tmp);
        }else if(x[i + K - 1] <= 0){
            ans = min(ans, abs(x[i]));
        }else{
            ans = min(ans, x[i+K-1]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,X,Y,ans=0;
  cin >>A >>B >>C;
  X=max(A,B), X=max(X,C), X*=3;
  Y=A+B+C;
  ans+=(X-Y)/2;
  if((X-Y)%2!=0) ans+=2;
  cout <<ans <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
        char str[5];
        scanf("%s", str);

        int A;
        int B;
        A = (str[0] - '0')*10;
        A += (str[1] - '0');

        B = (str[2] - '0')*10;
        B += (str[3] - '0');

        if( A < 1 && B < 1 ) {
                printf("NA\n");
                return 0;
        }
        if( A > 12 && B > 12 ) {
                printf("NA\n");
                return 0;
        }
        if( A > 0 && A <= 12 && B > 0 && B <= 12) {
                printf("AMBIGUOUS\n");
                return 0;
        }
        if( A > 0 && A <=12 ) {
                printf("MMYY\n");
                return 0;
        }
        if( B > 0 && B <=12 ) {
                printf("YYMM\n");
                return 0;
        }

        printf("NA\n");
        return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	string s;
	cin >> s;
	string ans = "Yes";

	for (int i=0; i < s.size(); i++){
		if (i % 2 == 0 && (s[i] == 'R' || s[i] == 'U' || s[i] == 'D'))
			continue;
		else if(i % 2 == 1 && (s[i] == 'L' || s[i] == 'U' || s[i] == 'D'))
			continue;
		else
			ans = "No";
			break;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
using namespace std;
typedef pair<int, int> P;

signed main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int sum = 0;
    rep(i, 0, n){
        cin >> a[i];
        if(a[i] > 0) sum += a[i];
    }
    int n1 = 0, n2 = 0;
    rep(i, 0, k){
        if(a[i] > 0) n1 += a[i];
        else n2 += -a[i];
    }
    // o(n1 << " " << n2);
    int MIN = 1e16;
    rep(i, 0, n - k + 1){
        MIN = min(MIN, min(n1, n2));
        if(a[i] > 0) n1 -= a[i];
        else n2 -= -a[i];
        if(a[i + k] > 0) n1 += a[i + k];
        else n2 += -a[i + k];
    }
    o(sum - MIN);
}

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

int n, a[100001];

int main(void){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  int c = 0;
  int p = 1;
  while(true){
    c++;
    if(c > n){
      cout << -1 << endl;
      return 0;
    }
    p = a[p];
    if(p == 2){
      cout << c << endl;
      return 0;
    }
  }
}


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

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

    int n;
    cin >> n;
    vector<int> x(n+1, 0), y(n+1, 0), t(n+1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        int posX = abs(x[i] - x[i-1]);
        int posY = abs(y[i] - y[i-1]);
        int elapse = t[i] - t[i-1];

        if (posX + posY > elapse || (posX+posY) % 2 != elapse % 2) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 1408
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    h,n = map(int,input().split())
    ab = [list(map(int,input().split())) for i in range(n)]
    a = [ab[i][0] for i in range(n)]
    b = [ab[i][1] for i in range(n)]
    inf = float("inf")
    dp = [inf for i in range(h+max(a)+1)] #dp[i]...体力をi削るために必要な最低の魔力
    dp[0] = 0
    for i in range(n):
        for j in range(h+1):
            dp[j+a[i]] = min(dp[j]+b[i],dp[j+a[i]])

    print(min(dp[h:]))
if __name__ == "__main__":
    main()
#endline===============================================

Measured memory_bytes: 71784