akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        void solve(InputReader in, PrintWriter out) {
            int A = in.nextInt();
            int B = in.nextInt();
            int C = in.nextInt();
            int D = in.nextInt();

            String ans = "Balanced";
            if (A + B > C + D) {
                ans = "Left";
            } else if (A + B < C + D) {
                ans = "Right";
            }
            out.println(ans);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Measured memory_bytes: 21460
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin>>N>>M;
  int s[M];
  string a[N],p[N],c[M];
  for(int i=0;i<M;i++){
    cin>>s[i]>>c[i];
  }
  for(int i=0;i<N;i++){
    a[i]="0";
    p[i]="No";
  }
  
  bool judge=true;
  
  for(int i=0;i<M;i++){
    if(p[s[i]-1]=="No"||a[s[i]-1]==c[i]){
      a[s[i]-1]=c[i];
      p[s[i]-1]="Yes";
    }
    else{
      judge=false;
    }
  }
  string ans;
  if(a[0]=="0"&&N!=1&&p[0]=="No"){
    a[0]="1";
  }
  else if(a[0]=="0"&&N!=1&&p[0]=="Yes"){
    judge=false;
  }
  for(int i=0;i<N;i++){
    ans+=a[i];
  }
  
  
  if(judge){
    cout<<ans<<endl;
  }
  else{
    cout<<-1<<endl;
  }
}


Measured memory_bytes: 256
MOD = 10**9+7
n, m = map(int, input().split())

i = 2
counts = []
while i**2 <= m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c > 0:
        counts.append(c)
    i += 1
if m > 1:
    counts.append(1)

def combi(p, r):
    f = 1
    r = min(r, p-r)
    for i in range(r):
        f *= (p-i)
        f //= (i+1)
    return f

ans = 1
for c in counts:
    ans = (ans * combi(c+n-1, c))%MOD
print(ans)


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

int main() {
  int N; cin >> N;
  string S; cin >> S;
  
  int count =0;
  for (int i =0; i<1000; i++) {
    int a,b,c;
    a = i / 100; 
    b = (i - a * 100) / 10;
    c = i % 10;
    int count3 =0;
    for (int j =0; j<N; j++) {
      if (S.at(j) - '0' == a && count3 == 0) {
        count3++;
      } else if (S.at(j) - '0' == b && count3 == 1) {
        count3++;
      } else if (S.at(j) - '0' == c && count3 == 2) {
        count3++;
      }
      if (count3 == 3) break;
    }
    if (count3 == 3) {
      count++;
    }
  }
  cout << count << endl;  
}


Measured memory_bytes: 3620
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		//Scanner scan = new Scanner(System.in);
        String[] ana = new String[3];
        ana=line.split("");
        
		
        if(ana[0].equals(ana[2]))
        System.out.println("Yes");
        else
        System.out.println("No");
        
}
}

Measured memory_bytes: 21204
using static System.Console;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var str = ReadLine().Split().Select(x=>int.Parse(x)).ToArray();
        int sx = str[0], sy = str[1], tx = str[2], ty =str[3];
        var fx = tx - sx;
        var fy = ty - sy;

        mvx(fx);
        mvy(fy);
        mvx(-fx);
        mvy(-fy);

        if (fy > 0) mvy(-1);
        else mvy(1);

        if (fx > 0) mvx(++fx) ;
        else mvx(--fx);

        if (fy > 0) mvy(++fy);
        else mvy(--fy);

        if (fx > 0) mvx(-1);
        else mvx(1);

        if (fy > 0) mvy(1);
        else mvy(-1);

        if (fx > 0) mvx(-fx);
        else mvx(fx);

        if (fy > 0) mvy(-fy);
        else mvy(fy);

        if (fx > 0) mvx(1);
        else mvx(-1);
    }

    static void mvx(int move)
    {
        if(move > 0)
        {
            for (; move > 0; move--)
            {
                Write("R");
            }
        }else
        {
            move *= -1;
            for (; move > 0; move--)
            {
                Write("L");
            }
        }
    }
    static void mvy(int move)
    {
        if (move > 0)
        {
            for (; move > 0; move--)
            {
                Write("U");
            }
        }
        else
        {
            move *= -1;
            for (; move > 0; move--)
            {
                Write("D");
            }
        }
    }
}

Measured memory_bytes: 2776
#include <iostream>
#include <bits/stdc++.h>
#define ll long long int    
#define mod 1000000007
using namespace std;
int main()
{	
	ll n, k;
    cin>>n>>k;
    vector<ll> v(n+1);
    for(ll i=0; i<n; i++) cin>>v[i+1]; //one based indexing
 
    //floyd warshall cycle detection algorithm starts here to find start of cycle
    ll l = v[1];
    ll r = v[v[1]];
    while(l!=r){
        l = v[l];
        r = v[v[r]];
    }
    l = 1;
    while(l!=r){
        l=v[l];
        r=v[r];
               }
    //floyd warshall cycle detection algorithm ends here to find start of cycle
 
    ll cycleStar = l;  //starting point of cycle
    ll cnt = 0;  //number of elements before the starting point of cycle
    l = 1;
    while(l!=cycleStar){
        cnt++;
        l = v[l];
    }
 
    ll eleBefore = cnt;  //number of elements before the starting point of cycle
    ll lenn = 1;   //length of cycle(num of elements in it)
    l = cycleStar;
    while(v[l]!=cycleStar){
        l=v[l];
        lenn++;
    }
    
    // moving king to the starting point of cycle if k becomes zero in between we are breaking early and printing the answer
    l = 1;
    while((eleBefore!=0)&&(k)){
        l=v[l];
        eleBefore--;
        k--;
    }
    
    // printing answer if k becomes zero in between reaching the start of cycle
    if(k==0){
        cout<<l<<endl;
        return 0;
    }
    
    // now we are at start of cycle we can reduce k to k%lenn because if k> len king will move in cycle
    k=k%lenn;
    
    //now k is less than length of cycle
    //just move king k steps forward
    while(k){
        l=v[l];
        k--;
    }
    //print ans
    cout<<l<<endl;
    return 0;
}

Measured memory_bytes: 4844
#include<iostream>
using namespace std;
int main()
{
    // 文字列の入力
    char c;
    cin >> c;
    // 出力
  	if(c>=65 && 90>=c){
    	cout << "A" << endl;
    }
  	else cout << "a" << endl;

    return 0;
}

Measured memory_bytes: 3008
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  int n;
  string s;
  cin>>n>>s;
  
  int ans=0;
  for(int i=1;i<n;i++){
    int cnt=0;
    for(char c='a';c<='z';c++){
      bool left=false,right=false;
      for(int j=0;j<i;j++){
        if(s[j]==c)left=true;
      }
      for(int j=i;j<n;j++){
        if(s[j]==c)right=true;
      }
      if(left==true&&right==true){
        cnt++;
      }
    }
    ans=max({cnt,ans});
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var (currentT, currentA) = Pair(1L, 1L)

    for (i in 1..n) {
        val (t, a) = readLine()!!.split(' ').map(String::toLong)
        if (t >= currentT && a >= currentA) {
            currentT = t
            currentA = a
            continue
        }
        val tDiv = currentT / t + if (currentT % t == 0L) 0 else 1
        val aDiv = currentA / a + if (currentA % a == 0L) 0 else 1
        currentT = t * if (tDiv > aDiv) tDiv else aDiv
        currentA = a * if (tDiv > aDiv) tDiv else aDiv
    }
    println(currentT + currentA)
}

Measured memory_bytes: 38080
#include<stdio.h>
int main(void){
	int n,m,i,j,sum;
	
	scanf("%d %d",&n,&m);
	int a[n][m];
	int b[m];
	
	for(i = 0;i < n;i++){
		for(j = 0;j < m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(j = 0;j < m;j++){
		scanf("%d",&b[j]);
	}
	for(i = 0;i < n;i++){
		sum = 0;
		for(j = 0;j < m;j++){
			sum += a[i][j]*b[j];
		}
			printf("%d\n",sum);
	}
	return 0;
}

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

using namespace std;
int cnt;

void merge(vector<int> &a,int left,int mid,int right){
    int l_side = mid - left;
    int r_side = right - mid;
    int i = 0,j = 0;
    vector<int> l(l_side + 1),r(r_side + 1);
    
    for(i = 0;i<l_side;i++){
        l[i] = a[left + i];
    }
    
    for(i = 0;i<r_side;i++){
        r[i] = a[mid + i];
    }
    l[l_side] = 2000000000;
    r[r_side] = 2000000000;
    
    i = 0;
    j = 0;
    
    for(int k = left;k<right;k++){
        cnt++;
        if(l[i] <=r[j]){
            a[k] = l[i];
            i++;
        }else{
            a[k] = r[j];
            j++;
        }
    }
}

void mergesort(vector<int> &a,int n,int l,int r){
    if(l + 1 < r){
        int mid = (l + r) / 2;
        mergesort(a,n,l,mid);
        mergesort(a,n,mid,r);
        merge(a,l,mid,r);
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    
    mergesort(a,n,0,n);
    
    for(int i = 0;i < n;i++){
        if(i)cout << " ";
        cout << a[i];
    }
    cout << endl;
    cout << cnt << endl;
}


Measured memory_bytes: 6728
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

const int INF = 99999999;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

const int MAX_H = 1000;
int H, W;
string s[MAX_H];

bool inside(int x, int y) {
    return 0 <= x && x < H && 0 <= y && y < W;
}

int bfs(int sx, int sy, int gx, int gy) {
    queue<P> que;
    que.push(P(sx, sy));
    vector<vector<int>> d(H, vector<int>(W, INF));
    d[sx][sy] = 0;

    while (!que.empty()) {
        P p = que.front(); que.pop();
        if (p.first == gx && p.second == gy)
             break;

        rep(k, 4) {
            int nx = p.first + dx[k], ny = p.second + dy[k];

            if (inside(nx, ny) && s[nx][ny] != 'X' && d[nx][ny] == INF) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gx][gy];
}

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

    int N;
    cin >> H >> W >> N;
    N++;
    vector<int> x(N);
    vector<int> y(N);
    rep(i, H) {
        cin >> s[i];
        rep(j, W) {
            if (s[i][j] == 'S') s[i][j] = '0';

            if (isdigit(s[i][j])) {
                x[s[i][j] - '0'] = i;
                y[s[i][j] - '0'] = j;
            }
        }
    }

    int ans = 0;
    rep(i, N - 1) {
        ans += bfs(x[i], y[i], x[i + 1], y[i + 1]);
    }
    cout << ans << endl;

}

Measured memory_bytes: 11748
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = s1.replace("/", "");
		sc.close();
		if (s2.compareTo("20190430") <= 0) {
			System.out.println("Heisei");
		} else {
			System.out.println("TBD");
		}
	}
}


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

typedef long long ll;
typedef vector < ll > vl;
typedef vector < int > vi;
typedef vector < bool > vb;
typedef vector < vl > vvl;
typedef vector < vi > vvi;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef vector < pll > vpll;
typedef vector < pii > vpii;
typedef vector < vpll > vvpll;
typedef vector < vpii > vvpii;

#define pb push_back
#define eb emplace_back
#define pf push_front
#define all(c) (c).begin(), (c).end()
#define ff first
#define ss second
#define mp(x,y) make_pair((x), (y))
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL)



void solve(){
    
    int a; cin >> a;
    cout << a * (1 + a * (1 + a)) << '\n';
    
}


int main(){
	boost;
	int t = 1;
// 	cin >> t;
// 	precompute();
	for(int i = 1; i <= t; i++){
	   // cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
int main() {
	char s[3][101], c, buf;
	int Apt = 0, Bpt = 0, Cpt = 0, turn = 0;
	for (int i = 0; i < 3; i++) {
		scanf("%s", s[i]);
	}
	c = s[0][0];
	while (c != '\0') {
		buf = c;
		if (c == 'a') {
			c = s[0][Apt];
			Apt++;
		} else if (c == 'b') {
			c = s[1][Bpt];
			Bpt++;
		} else {
			c = s[2][Cpt];
			Cpt++;
		}
	}
	printf("%c\n", buf + ('A' - 'a'));
	return 0;
}

Measured memory_bytes: 128
a,b,x = gets.chomp.split(' ').map(&:to_f)
if (a**2)*b <= x*2
  puts Math.atan(2*((a**2 * b) - x) / (a**3)) * (180 / Math::PI)
else
  puts Math.atan(a*(b**2)/(2*x)) * (180 / Math::PI)
end


Measured memory_bytes: 14740
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int main(){
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());

  int N;
  cin>>N;
  vector<int> H(N);
  for(int i=0;i<N;i++) cin>>H.at(i);

  int ans=0,now=0;

  for(int i=0;i<N-1;i++){
    //cout<<i<<','<<now<<endl;
    if(H.at(i)>=H.at(i+1)){
      now++;
    }else{
      if(ans<now) ans=now;
      now=0;
    }
  }
  if(ans<now) ans=now;
  cout<<ans<<endl;
}

Measured memory_bytes: 640
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
A.sort(reverse=True)

dp = [[0] * (N + 1) for _ in range(N + 1)]

for s, (a, i) in enumerate(A):
    for l in range(s + 1):
        r = s - l
        L = dp[l][r] + a * (i - (l + 1))
        R = dp[l][r] + a * (N - r - i)

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

ans = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i])
print(ans)


Measured memory_bytes: 124736
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int calc(int a, int k){
    // cout << a << " " << k << endl;
    if (a < k) return 0;
    if (a % k == 0) return a / k;
    int x = a / k + 1, r = a % k;
    int t = (r + x - 1) / x;
    return calc(a - t * x, k); 
}

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

    int gr = 0;

    REP(i,n){
        int a, k;
        cin >> a >> k;
        gr ^= calc(a, k);
    }

    cout << (gr == 0 ? "Aoki" : "Takahashi") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <cmath>
#include <tuple>
using namespace std;
#define fio ios::sync_with_stdio(0),cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll __gcd(ll a,ll b){
	return a?__gcd(b%a,a):b;
}
ll N,M;
char S[100005],T[100005];
ll Si[100005],Ti[100005];
int main(){
    scanf("%lld %lld",&N,&M);
    scanf("%s %s",S+1,T+1);
    if(N<M) swap(N,M),swap(S,T);
    ll gcd = __gcd(N,M);
    ll lcm=N*M/gcd;
    ll gN=lcm/N,gM=lcm/M;
    for(int i=1;i<=N;i++){
    	Si[i]=gN*(i-1)+1;
    }
    for(int i=1;i<=M;i++){
    	Ti[i]=gM*(i-1)+1;
    	int idx=lower_bound(Si+1,Si+N+1,Ti[i])-Si;
    	if(Si[idx]==Ti[i] && S[idx]!=T[i]) return !printf("-1");
    }
    printf("%lld",lcm);



}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO                     \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0);
typedef long long ll;
/**
 * Uncomment the #define below if problem contains multiple test cases
 */
// #define MULTIPLE_TESTS 1

void solve() {
  int x[5];
  int ans = -1;
  for (int i = 0; i < 5; ++i) {
    cin >> x[i];
    if (x[i] == 0) {
      ans = i + 1;
    }
  }
  cout << ans << endl;
}

int main() {
  FAST_IO;
  int t = 1;
#ifdef MULTIPLE_TESTS
  cin >> t;
#endif

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

  return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[26];
char s[200];
int k, p, l;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		for (int j = 0; j < m; j++) {
			a[s[j] - 'a']++;
		}
	}
	for (int i = 0; i < 26; i++) {
		k += a[i] / 4;
		a[i] -= a[i] / 4 * 4;
		p += a[i] / 2;
		l += a[i] & 1;
	}
	if (n & 1) {
		if (m & 1) {
			if (l == 1 && k >= (n - 1)*(m - 1) / 4) {
				printf("Yes\n");
				return 0;
			}
		}
		else if (k >= (n*m - m) / 4&&l==0) {
			printf("Yes\n");
			return 0;
		}
	}
	else if (m & 1) {
		if ((n*m - n) / 4 <= k && l == 0) {
			printf("Yes\n");
			return 0;
		}
	}
	else if (n*m / 4 == k) {
		printf("Yes\n");
		return 0;
	}
	printf("No\n");
}

Measured memory_bytes: 256
#include<stdio.h>

int selectionSort(int A[], int N){ 
    int i, j, t, sw = 0,minj;
    for(i = 0; i < N - 1; i++){
        minj = i;
        for (j = i; j < N; j++){
            if ( A[j] < A[minj]) minj = j;
        }   
        t = A[i]; A[i] = A[minj];A[minj] = t;
        if (i != minj) sw++;
    }   
    return sw; 
}

int main(){
    int A[100], N, i, sw; 
    scanf("%d", &N);
    
    for (i = 0; i < N; i++) scanf("%d", &A[i]);
    
    sw = selectionSort(A, N); 
    
    for (i = 0; i < N; i++){
        if (i > 0) printf(" ");
        printf("%d", A[i]);
    }   
    printf("\n");
    printf("%d\n", sw);

    return 0;

}

Measured memory_bytes: 2744
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 1e9;
const int MOD = 1000000007;

int main(){
    int x,y,z;
    cin >> x >> y >> z;
    cout << z <<" "<< x <<" " << y << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x, y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x, y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=pow(10,9)+7;
bool cmp(pair<long double ,int > x, pair<long double , int> y){ return x.F<y.F && x.S<y.S; }
const ll maxn=1e4+10;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
ll solve(ll n){
	if (n==1) return 1;
	else return 1+2*solve(n/2);
}
int main(){ 
    
//    #ifndef ONLINE_JUDGE
//  		freopen("input.txt", "r", stdin);
//    #endif
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
	ll n;
    cin>>n;
    ll ans=solve(n);
    cout<<ans<<endl;
    
    
	return 0;
}


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



void solve(){
    int n,m;
    cin >> n >> m;
    int a[n+10];
    priority_queue<int> que;
    rep(i,n){
      cin >> a[i];
      que.push(a[i]);
    }
    /*
    rep(i,m){
      int ma = 0;
      int pointer = 0;
      rep(j,n){
        if(ma<a[j]) {
          pointer =j;
          ma = a[j];
        }
      }
      a[pointer] = a[pointer]/2;
    }
    ll sum=0;
    rep(i,n){
      sum += a[i];
    }
    cout << sum << endl;
    */
    rep(i,m){
      int tmp = que.top();
      que.pop();
      que.push(tmp/2);
    }
    ll sum = 0;
    rep(i,n){
      sum += que.top();
      que.pop();
    }
    cout << sum << endl;
}

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

Measured memory_bytes: 1148
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

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

		int a = getInt(sc);
		int b = getInt(sc);
		int c = getInt(sc);
		int x = getInt(sc);

		int count = 0;
		for (int i = 0; i <= a; i++) {
			for (int j = 0; j <= b; j++) {
				for (int k = 0; k <= c; k++) {
					if (500 * i + 100 * j + 50 * k == x) {
						count++;
					}
				}
			}
		}
		System.out.println(count);

	}

	/**
	 * *汎用メソッド<br>
	 * 入力した配列に対する順列を取得
	 *
	 * @param numArray
	 * @return
	 */
	private static List<Integer[]> getPermutation(int[] numArray) {
		List<Integer[]> permutation = new ArrayList<>();
		Integer[] ans = new Integer[numArray.length];
		boolean[] used = new boolean[numArray.length];

		return buildPermutaion(permutation, numArray, ans, used, 0);
	}

	/**
	 * *汎用メソッド(内部)<br>
	 * 入力した配列に対する順列を作成
	 *
	 * @param list
	 * @param numArray
	 * @param ans
	 * @param used
	 * @param depth
	 * @return
	 */
	private static List<Integer[]> buildPermutaion(List<Integer[]> list, int[] numArray, Integer[] ans, boolean[] used,
			int depth) {

		// 全部使い切った時=>できた順列を返す
		if (depth == numArray.length) {
			list.add(ans.clone());
			return list;
		}
		// 使い切っていない場合

		for (int i = 0; i < numArray.length; i++) {
			if (used[i]) {
				continue;
			}
			ans[depth] = numArray[i];
			used[i] = true;
			list = buildPermutaion(list, numArray, ans, used, depth + 1);

			used[i] = false;
		}

		return list;
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}

class Status {
	long x;
	long tmpCoins;

	public Status(long x, long tmpCoins) {
		this.x = x;
		this.tmpCoins = tmpCoins;
	}
}


Measured memory_bytes: 21332
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

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

ans = None
for x in it.product([0, 1], repeat=10):
    if not any(x):
        continue
    sumP = 0
    for i in range(N):
        c = sum(map(lambda fijkxjk: (1 if all(fijkxjk) else 0), zip(F[i], x)))
        dump(i, c, list(x), P[i][c])
        sumP += P[i][c]
    ans = max([ans, sumP]) if ans else sumP
dump(N, F, P)
print(ans)


Measured memory_bytes: 4720
#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>

using namespace std;
typedef long long ll;

int main(){
    ll n, m, p;
    cin >> n >> m >> p;

    vector<vector<pair<int, int>>> to(n);
    vector<vector<int>> from(n);
    for(int i = 0; i < m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        if(a == b && c - p <= 0){ continue; }
        to.at(a).push_back(make_pair(b, c - p));
        from.at(b).push_back(a);
    }

    vector<bool> can_goal(n, false);
    can_goal.at(n - 1) = true;
    unordered_set<int> pos[2];
    pos[0].insert(n - 1);
    for(int i = 0; i < n; ++i){
        const int j = i % 2;
        const int j2 = (i + 1) % 2;
        pos[j2].clear();
        for(int x : pos[j]){
            for(int next : from.at(x)){
                if(!can_goal.at(next)){
                    can_goal.at(next) = true;
                    pos[j2].insert(next);
                }
            }
        }
    }

    vector<ll> coins(n, numeric_limits<ll>::min());
    coins.at(0) = 0;
    pos[0].clear();
    pos[0].insert(0);
    for(int i = 0; i <= m; ++i){
        const int j = i % 2;
        const int j2 = (i + 1) % 2;

        pos[j2].clear();
        for(int x : pos[j]){
            for(auto& p : to.at(x)){
                if(coins.at(p.first) < coins.at(x) + p.second
                   && can_goal.at(p.first)){
                    pos[j2].insert(p.first);
                    coins.at(p.first) = coins.at(x) + p.second;
                }
            }
        }
        if(i >= m && pos[j2].size()){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << max(0LL, coins.at(n - 1)) << endl;
    return 0;
}


Measured memory_bytes: 888
N, K = map(int, input().split())
LR = []
for k in range(K):
    LR.append(list(map(int, input().split())))

kMod = 998244353

counts = [0] * N
counts[0] = 1
window_sums = [0] * K

for i in range(1, N):
    for k in range(K):
        l, r = LR[k]
        leave, enter = i-r-1, i-l
        if leave >= 0:
            window_sums[k] -= counts[leave]
        if enter >= 0:
            window_sums[k] += counts[enter]
        window_sums[k] %= kMod
    counts[i] = sum(window_sums) % kMod
print(counts[-1])

Measured memory_bytes: 16812
n, time=map(int,raw_input().split())
p = []
t = []
for _ in xrange(n):
    a = raw_input().split()
    p.append(a[0])
    t.append(int(a[1]))
alltime = 0
while True:
    if len(p)==0:
        break
    if t[0]<=time:
        alltime+=t[0]
        print p.pop(0),
        t.pop(0)
        print alltime
    else:
        t.append(t[0])
        t.pop(0)
        t[-1]-=time
        alltime += time
        p.append(p[0])
        p.pop(0)

Measured memory_bytes: 9504
def pm_table(n):
    """
    素数テーブル
    n以下の素数のリストを返却する
    :param n:
    :return:素数のリスト
    """
    res = [1] * (n + 1)
    res[:2] = 0, 0

    for i in range(2, n):
        if i ** 2 > n:
            break

        if res[i] == 1:
            for j in range(i * 2, n + 1, i):
                res[j] = 0

    return [i for i, x in enumerate(res) if x == 1]


X = int(input())
tbl = pm_table(10 ** 6)
for p in tbl:
    if X <= p:
        print(p)
        exit()


Measured memory_bytes: 14048
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
cnt = 0
lack = 0

for i in range(n):
    diff = a[i] - b[i]
    if diff < 0:
        cnt += 1
        lack -= diff
    elif diff > 0:
        c.append(diff)

c = sorted(c)[::-1]

if sum(a) < sum(b):
    print(-1)
    exit()

for i in c:
    if lack <= 0:
        break
    lack -= i
    cnt += 1

print(cnt)

Measured memory_bytes: 24276
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B, C, D = map(int, read().split())

    print(min(A, B) + min(C, D))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  int ans=0;
  for(int k=2;k<N;k++){
    for(int j=1;j<k;j++){
      for(int i=0;i<j;i++){
        if(A.at(i)+A.at(j)>A.at(k)&&A.at(j)+A.at(k)>A.at(i)&&A.at(k)+A.at(i)>A.at(j)&&A.at(i)!=A.at(j)&&A.at(j)!=A.at(k)&&A.at(k)!=A.at(i)){
          ans++;
        }
      }
    }
  }
  cout<<ans<<endl;
}
        

Measured memory_bytes: 3628
p [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][gets.to_i - 1]


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int S = 0;
  cin >> N;
  vector<int> cards(N);
  
  for (int i = 0; i < N; i++) {
    cin >> cards.at(i);
  }
  
  sort(cards.begin(), cards.end());
  reverse(cards.begin(), cards.end());
  
  if (N % 2 == 0) {
    for (int i = 0; i < N; i+=2) {
      S += (cards.at(i) - cards.at(i + 1));
    }
  }
  else {
    for (int i = 0; i < N - 1; i+=2) {
      S += (cards.at(i) - cards.at(i + 1));
    }
    S += cards.at(N - 1);
  }
  
  cout << S << endl;
}

Measured memory_bytes: 3580
#include<stdio.h>
#define N 100
int main(){
  int n,i,l,j,k,p[N+1],m[N+1][N+1];
  scanf("%d",&n);
  for(i =1;i <= n;i++){
    scanf("%d%d",&p[i-1],&p[i]);
  }
  for(i =1;i <= n;i++) m[i][i] = 0;
  for(l =2;l <= n;l++){
    for(i =1; i<= n - l + 1; i++){
      j = i + l - 1;
      m[i][j] = (1<<21);
      for(k = i;k <= j - 1;k++){
        if(m[i][j] > m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]){
          m[i][j] = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
        }
      }
    }
  }
  printf("%d\n",m[1][n]);
  return 0;
}



Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
int main()
{
    //ifstream cin("input.in");
    //ofstream cout("output.out");
    ios::sync_with_stdio(0);cin.tie(0);
    string s;
    cin>>s;
    cout<<s[0]<<s.size()-2<<s[s.size()-1];
}

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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	
	string ans = "NO";
	if (a == 7 && b == 5 && c == 5) ans = "YES";
	if (a == 5 && b == 7 && c == 5) ans = "YES";
	if (a == 5 && b == 5 && c == 7) ans = "YES";
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll width[35]={1};
ll cal(ll x1,ll y1,ll x2,ll y2,int level) {
	if(level==0) return abs(y1-y2);
	ll w=width[level-1];
	if(x1/w!=x2/w) return abs(x1-x2)+abs(y1-y2);
	if(x1/w==1&&abs(y1/w-y2/w)>=2) {
		return min(x1%w+x2%w+2,w*2-x1%w-x2%w)+abs(y1-y2);
	}
	return cal(x1%w,y1,x2%w,y2,level-1);
}
int main() {
    //freopen("in.txt","r",stdin);
	for(int i=1;i<35;i++) width[i]=width[i-1]*3;
    int T;
	scanf("%d",&T);
	while(T--) {
		ll a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d),a--,b--,c--,d--;
		if(abs(a-c)>abs(b-d)) swap(a,b),swap(c,d);
		printf("%lld\n",cal(a,b,c,d,30));
	}
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;


int main(){
    ll N;
    cin >> N;
    vector<ll> a(N);
    REP(i, N) cin >> a[i];
    DESC(a);
    ll Alice = 0, Bob = 0;
    REP(i, N) {
        if(i%2 == 0) Alice += a[i];
        else Bob += a[i];
    }
    cout << Alice - Bob << "\n";
}


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



int main() {
    int a, b;
    cin >> a >> b;
    int ans = max({a+b, a-b, a*b});
    cout << ans;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod=1e9+7;
int main()
{
	
	ll n,k;
	cin>>n>>k;
	ll sum=1;
	for(ll i=n;i>=k;i--)
	{
		if(i==n)
		{
			sum+=n+1;
			continue;
		}
		sum+=((n+(n-i+1))*(i)/2-(i-1)*(i)/2)+1;
	//	cout<<((n+(n-i+1))*(i)/2-(i-1)*(i)/2)+1<<endl;
		sum%=mod;
	}
	cout<<sum<<endl;
	
	
	return 0;
} 

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 10100000
#define INF 1e15
#define MAP 110
#define initial_value -1
#define LINF 1LL << 60
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
ll N,M,a[100100][3],mx = -(1LL << 60);
int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j < 3; j++) cin >> a[i][j];
    }
    for(int i = 0; i < 8; i++){
        vector<ll> vec;
        for(int j = 1; j <= N; j++){
            ll S = 0;
            for(int k = 0; k < 3; k++){
                if((i / (1 << k)) % 2 == 0) S += a[j][k];
                else S -= a[j][k];
            }
            vec.push_back(S);
        }
        sort(vec.begin(),vec.end());
        reverse(vec.begin(),vec.end());
        ll ans = 0;
        for(int j = 0; j < M; j++) ans += vec[j];
        mx = max(mx,ans);
    }
    cout << mx << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);

	int N,M;cin>>N>>M;
	cout << M*(M-1)/2 + N*(N-1)/2 << endl;
    
}

Measured memory_bytes: 256
n,m=map(int,input().split())
ks=[]
for i in range(m):
    temp=list(map(int,input().split()))
    ks.append(temp)
p=list(map(int,input().split()))
cnt_ans=0
for i in range(1<<n):
    cnt_on=0
    for j in range(0,m):
        cnt=0
        for k in range(1,ks[j][0]+1):
            if (i>>(ks[j][k]-1))%2==1:
                cnt+=1
        if cnt%2==p[j]:
            cnt_on+=1
    if cnt_on==m:
        cnt_ans+=1
print(cnt_ans)



Measured memory_bytes: 9128
using System;

namespace nikkei2019_2_qual_a
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = decimal.Parse(Console.ReadLine());
            var r = Math.Floor(N / 2);
            Console.WriteLine(N % 2 == 0 ? r - 1 : r);
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define sz(a) ((int)a.size())
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijoMOD(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll div_num(ll n){
  vl div(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      div[i]++;
    }
  }
  if(n!=1)div[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=div[i];
  }
  return num;
}
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}



//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//vc Alp ={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
//cout<<""<<endl;
int main(){
  int N,Q;cin>>N>>Q;
  vvi G(N);//あってる？
  vb s(N);
  rep(i,N){
    s[i]=false;
  }
  vl p(N);
  rep(i,N-1){
    int a,b;cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  rep(i,Q){
   ll pu,x; cin>>pu>>x;
    pu--;
    p[pu] +=x;
  }
  queue<int> que;
  que.push(0);s[0]=true;
  while(!que.empty()){
    int curr=que.front();que.pop();
    rep(i,G[curr].size()){
      if(!s[G[curr][i]]){
        p[G[curr][i]]+=p[curr];
        que.push(G[curr][i]);
        s[G[curr][i]]=true;
      }      
    }
  }
  rep(i,N){
   cout<<p[i];
   if(i!=N-1)cout<<" ";
   else cout<<endl;
  }
}







Measured memory_bytes: 16372
#include <bits/stdc++.h>
#include <vector>
#include <math.h>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <ctype.h>
#include <unordered_map>
#include <set>
#include <iterator>
#include <deque>
using namespace std;

typedef long long int lli;


#define MOD (lli)(1e9+7)
#define endl "\n"
#define pb push_back
#define TEST_CASES  lli t;cin >> t;while(t--)

lli mod = 998244353;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,s;
  cin>>n>>s;
  vector<lli> a(n+1);
  vector< vector<lli> > f(n+1,vector<lli> (s+1,0));
  vector< vector<vector<lli>> > dp(n+1,vector<vector<lli>> (s+1,vector<lli>(3,0)));
  for (int i = 1; i <= n; ++i)
  {
    cin>>a[i];
    //f[i][a[i]] = 1;
    if(a[i] <= s)
      dp[i][a[i]][1] = 1;
  }
 
 /* for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= s; ++j)
    {
      f[i][j] += (f[i-1][j]);
      if(j>a[i])
        f[i][j] += f[i-1][j-a[i]];
      f[i][j] %=mod;
    }
  }*/
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 0; j <= s; ++j)
    {
        if(j == 0){
          dp[i][j][1] = i;
        }
        else{
          dp[i][j][1] += dp[i-1][j][1];
          if(j>=a[i])
            dp[i][j][1] += dp[i-1][j-a[i]][1];
          dp[i][j][2] += dp[i-1][j][2] + dp[i][j][1];
          dp[i][j][2] %=mod;
          dp[i][j][1] %=mod; 
        }
    }
  }
  /*for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= s; ++j)
    {
      cout<<dp[i][j][2]<<" "; 
    }
    cout<<endl;
  }*/
  cout<<dp[n][s][2]<<endl;  
}






Measured memory_bytes: 563456
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

struct mint {
	ll x;
	mint(ll x=0):x((x%mod+mod)%mod){}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod-2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res/=a;
	}
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
	assert(n < mod);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
	ifact[n] = fact[n].inv();
	for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
	if (k < 0 || k > n) return 0;
	return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,a,b;
	cin>>n>>a>>b;
	mint now=2;
	mint ans=now.pow(n)-1;
	mint x=1;
	FOR(i,n-a+1,n+1) x*=i;
	FOR(i,1,a+1) x/= i;;
	mint y=1;
	FOR(i,n-b+1,n+1) y*=i;
	FOR(i,1,b+1) y/= i;;
	ans-=x;
	ans-=y;
	cout<<ans.x<<endl;
}

Measured memory_bytes: 256
<?php
$count = trim(fgets(STDIN));
$out = 0;
for ($i = 0; $i < $count; $i++) {
    $n = trim(fgets(STDIN));
	$out = $out + isprime($n);
}
	print($out);
function isprime($n) {
	if ($n == 2) {
		return 1;
	} else if ($n % 2 == 0) {
		return 0;
	} else {
		for ($i = 3; sqrt($n) >= $i; $i+=2) {
			if ($n % $i == 0) {
				return 0;
				break;
			}
		}
		return 1;
	}
}
?>

Measured memory_bytes: 15340
#include <stdio.h>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define irep(i,a,b) for(int i=(a);i>=(b);i--)

using namespace std;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;


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

  int X, A;
  cin >> X >> A;

  if (X < A) cout << 0 << endl;
  else cout << 10 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<queue>

using namespace std;
typedef long long ll;

int main(){
	while(1){
		int n;
		int w[301];
		int dp[301][301];
		scanf("%d",&n);
		if(n==0) break;
		
		for(int i=0;i<n;i++) scanf("%d ",&w[i]);
		for(int i=0;i<301;i++) fill_n(dp[i],301,0);
		
		for(ll W=2;W<n+1;W++){
			for(int i=0;i<n;i++){
				int j=i+W-1;
				if(j>=n) continue;
				if(dp[i+1][j-1]==W-2 && abs(w[i]-w[j])<=1)
				dp[i][j]=W;
				for(ll k=i;k<j;k++){
					dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
				}
			}
		}
		printf("%d\n",dp[0][n-1]);
	}
}


Measured memory_bytes: 3496
#include <stdio.h>
void fibonacci(int n){
  int F[n];
  int i;
 
  F[0]=1;
  F[1]=1;
  for(i=2;i<=n;i++){
    F[i]=F[i-1]+F[i-2];
  }
  printf("%d\n",F[n]);
}
int main(){
  int n;
  

  scanf("%d",&n);
  fibonacci(n);

  return 0;
}

Measured memory_bytes: 596