akhauriyash/Code-Regression huggingface dataset:
local DBG = false
local function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end

-- returns (b^n) % m
local function modpow(b, n, m)
    if n == 0 then
        return 1
    else
        return b * modpow(b, n - 1, m) % m
    end
end

---
local MOD = 998244353
local N = io.read("*n")
local a = {}
local S = 0
for i=1,N do
    a[i] = io.read("*n")
    S = S + a[i]
end


local function fill90000(t, v)
    for i=1,900000 do
        t[i] = v
    end
end

local function default0(t)
    local mt = {
        __index = function(t,k)
            return 0
        end
    }
    setmetatable(t, mt)
end

-- ∑A = S/2 and ∑B = S/2 and ∑C = 0
local function getY()
    if S % 2 == 1 then
        return 0
    end
    local cache = {}
    --default0(cache)
    fill90000(cache, 0)
    cache[0] = 1
    local curmax = 0
    for i=1,N do
        local cur = a[i]
        curmax = curmax + cur
        for s=curmax,cur,-1 do
            cache[s] = (cache[s] + cache[s-cur]) % MOD
        end
    end
    return cache[math.floor(S/2)]
end

-- ∑A >= S/2
local function getX()
    local cache = {}
    --default0(cache)
    fill90000(cache, 0)
    cache[0] = 1
    local curmax = 0
    for i=1,N do
        local cur = a[i]
        curmax = curmax + cur
        for s=curmax,cur,-1 do
            cache[s] = (2 * cache[s] + cache[s-cur]) % MOD
        end
        for s=cur-1,0,-1 do
            cache[s] = 2 * cache[s] % MOD
        end
    end
    local sum = 0
    for s = math.ceil(S/2), curmax, 1 do
        sum = sum + cache[s]
    end
    return sum
end

local X, Y = getX(), getY()
local Total = modpow(3, N, MOD)
--dbgpr(Total, X, Y)
local ans = (Total - (3 * X) % MOD + (3 * Y) % MOD) % MOD
print(ans)


Measured memory_bytes: 18432
#include <bits/stdc++.h>
using namespace std;
int main(){
   int n,m;
   cin >> n >> m;
   bool v[100001];
   long long h[100001],b[100001],c[100001];
   for (int i = 1;i <= n;i++){
       cin >> h[i];
       v[i]=true;
   }
   long long cnt[100001]={0};
  

   
long long s[100001]={0},ans=0;
   for (int i = 1;i <= m;i++){
       cin >> b[i] >> c[i];

      if (h[b[i]]-h[c[i]]>0){  
         //ans++;
        v[c[i]]=false;
        
       }
      else if(h[b[i]]-h[c[i]]<0){
           
           v[b[i]]=false;
           
       }
         else {
             v[b[i]]=false;
             v[c[i]]=false;
         }
   }
    for (int i = 1;i <= n;i++){
       if(v[i]) ans++;
    }
   cout << ans << endl;

}

Measured memory_bytes: 6000
def oddmoji(x):
  lx=int(len(x)/2)
  if x[:lx]==x[lx:]:
    return True
  else:
    return False

s=input()
ls=len(s)
for i in range(ls-2, 0, -2):
  if oddmoji(s[:i]):
    print(i)
    break

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

using namespace std;

typedef long long ll;

int main()
{
  ll n, m;
  cin >> n >> m;
  if (m == 1 && n == 1)
  {
	cout << 1 << endl;
  }
  else if (n == 1)
  {
	cout << (m - 2) << endl;
  }
  else if (m == 1)
  {
	cout << (n - 2) << endl;
  }
  else
  {
	cout << ((n - 2) * (m - 2)) << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
 
int main(void){
  int A, B;
  cin >> A >> B;
  int temp = 1;
  for(int temp = 1; temp <= 1000; temp++){
    if((int)((double)temp * 0.08) == A && (int)((double)temp * 0.1) == B){
      cout << temp;
      return 0;
    }
  
  }
  cout << "-1";
  return 0;
}

Measured memory_bytes: 256
#  --*-coding:utf-8-*--


def main():
    L, R = map(int, input().split())

    a = L%2019
    b = min(R-L+1, 2019)+a
    m = 2018

    for i in range(a, b):
        for j in range(i+1, b):
            m = min(m, i*j%2019)
            
    print(m)



if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll modpow(ll a, ll n, ll mod){
	
	ll res = 1;
	while(n > 0){
		if(n & 1) res = res * a % mod;
		a = a*a % mod;
		n /= 2;
	}
	return res;
}



ll inva(ll a, ll mod){
	
	ll inv_a = modpow(a, mod-2, mod);
	
	return inv_a;
}



ll modcon(ll n, ll k, ll mod){
	
	ll numer = 1;
	ll denom = 1;
	
	rep(i, k){
		numer = numer * (n-i) % mod;
		denom = denom * (k-i) % mod;
	}
	ll ans = numer * inva(denom, mod) % mod;
	
	return ans;
	
}

int main() {
	
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	
	ll n, a, b, m, ans; cin >> n >> a >> b;
	
	m = 1000000007;
	
	ll p2n = modpow(2, n, m);
	
	ll nCa = modcon(n, a, m);
	ll nCb = modcon(n, b, m);
	
	ans = 
	
	ans = p2n - ((nCa + nCb) % m + 1);
	
	cout << (ans+m) % m << endl;
	
	return 0;
}


Measured memory_bytes: 256
s = input()
a_idx = 0
z_idx = len(s)
for i in range(len(s)) :
    if s[i] == "A" :
        a_idx = i
        break
for i in range(len(s) - 1, -1, -1) :
    if s[i] == "Z" :
        z_idx = i
        break
print(z_idx - a_idx + 1)


Measured memory_bytes: 3512
n = gets.chomp.to_i
arr = gets.chomp.split(' ').map(&:to_i)
dp = Array.new(n)
dp[0] = 0
dp[1] = (arr[0] - arr[1]).abs
(2...n).each do |i|
  dp[i] = [
      dp[i - 2] + (arr[i - 2] - arr[i]).abs,
      dp[i - 1] + (arr[i - 1] - arr[i]).abs
  ].min
end
puts dp[n - 1]

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

#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;

int main(){
  ll a,b;
  cin>>a>>b;
  if(a<10&&b<10)cout<<a*b;
  else cout<<"-1";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c) { return b / c - (a - 1) / c; }

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}

int main() {
    long long r, d, ans = 0, n, m, sum = 0;
    string t;
    cin >> n >> m;
    vector<vector<char>> as(n, vector<char>(m));
    vector<vector<char>> bs(n, vector<char>(m));
    if (n == 1 && m == 1) {
        cout << "No" << endl;
        return 0;
    }
    if (n == 1 && m == 2) {
        cout << "No" << endl;
        return 0;
    }
    if (n == 2 && m == 1) {
        cout << "No" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> as[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            bs[i][j] = '.';
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (as[i][j] == '#') {
                r = 0;
                if (j != m - 1) {
                    if (as[i][j + 1] == '#') {
                        bs[i][j] = '#';
                        bs[i][j + 1] = '#';
                        r++;
                    }
                }
                if (i != n - 1) {
                    if (as[i + 1][j] == '#' && i != n - 1) {
                        bs[i][j] = '#';
                        bs[i + 1][j] = '#';
                        r++;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (bs[i][j] != as[i][j]) {
                cout << "No" << endl;
                // cout << i << j << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m1, m2, d1, d2;
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    if (m1 == m2) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split();
        var d = new int[N];
        for (int i = 0; i < N; i++)
        {
            d[i] = int.Parse(input[i]);
        }

        var output = new List<int>();
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                output.Add(d[i] * d[j]);
            }
        }

        Console.WriteLine(output.Sum());
    }
}


Measured memory_bytes: 13268
// ------------------------------------
// Date:2018/ 2/22
// Problem:ABC 044 TakAndCards c.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()

using ll = long long;

//  dp[i][j][sum] i枚のカードからj枚選んだ時の合計(sum)をメモ
ll dp[51][51][2601] = {0ll};

int main()
{
  int N,A,n;
  cin >> N >> A;
  vector<int> x(N);
  REP(i,N) cin >> x[i];
  
  dp[0][0][0] = 1;
  REP(i,N){
    REP(j,i+1) {
      REP(sum,2601) {
        // x[i]を選んだ時
        dp[i+1][j+1][sum+x[i]] += dp[i][j][sum];
        // x[i]を選ばなかった時
        dp[i+1][j][sum] += dp[i][j][sum];
      }
    }
  }
  
  ll res = 0ll;
  REP(i,N+1) {
    if (i >= 1) res += dp[N][i][i*A];
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 51072
#include<bits/stdc++.h>
using namespace std;
const int N=4005,mod=998244353;
int n,k,pw[N],C[N][N];
void init()
{
	for(int i=pw[0]=1;i<N;i++)pw[i]=(pw[i-1]*2)%mod;
	for(int i=0;i<N;i++)C[i][0]=1;
	for(int i=1;i<N;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
int c(int n,int m){if(m<0||n<0)return 0;return C[n][m];}
int calc(int x,int n,int k)
{
	int ans=0,tot=max(0,x/2-max(0,x-1-k));
	for(int i=0;i<=tot;i++)ans=(1ll*pw[i]*C[tot][i]%mod*c(n+k-2*tot-1,k-tot*2+i-1)+ans)%mod;
	return ans;
}
int main()
{
	init();
	scanf("%d%d",&k,&n);
	for(int i=2;i<=2*k;i++)if(i&1)printf("%d\n",calc(i,n,k));else printf("%d\n",(calc(i-1,n,k-1)+calc(i-1,n-1,k-1))%mod);
	return 0;
}

Measured memory_bytes: 61440
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int h,n;
	int cnt=0;
	cin>>h>>n;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		cnt+=a;
	}
	if(cnt>=h)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	return 0;
} 

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;

int n, pos;
vector<int> pre, in, post;

void rec(int l, int r)
{
  if(l >= r) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(l, m);
  rec(m+1,r);
  post.push_back(root);
}

void solve()
{
  pos = 0;
  rec(0, pre.size());
  for(int i = 0; i < n; i++)
  {
    if(i) cout << " ";
    cout << post[i];
  }
  cout << endl;
}

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

  for(int i = 0; i < n; i++)
  {
    cin >> k;
    pre.push_back(k);
  }
  for(int i = 0; i < n; i++)
  {
    cin >> k;
    in.push_back(k);
  }
  solve();
  return 0;
}

Measured memory_bytes: 1220
N=int(input())
A=list(map(int,input().split()))
cnt=0
L=[0 for i in range(100005)]
for i in range(N):
    if A[i]<=100000:
        L[A[i]]+=1
    else:
        cnt+=1
    
for j in range(100002):
    
    if L[j]==j:
        pass
    elif L[j]<j:
        cnt+=L[j]
    elif L[j]>j:
        cnt+=L[j]-j
print(cnt)

Measured memory_bytes: 14268
n = int(input())
A = list(map(int,input().split()))
print(' '.join(map(str,A)))
for i in range(1,n):
    v = A[i]
    j = i-1
    while(j >= 0 and A[j] > v):
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(' '.join(map(str,A)))




Measured memory_bytes: 5600
using System;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = input[0];
            var M = input[1];
            var Q = input[2];
            var abcd = new ABCD[Q];
            for (int i = 0; i < Q; i++) abcd[i] = new ABCD(Console.ReadLine().Split().Select(int.Parse).ToArray());

            var A = new int[N + 1];
            A[0] = 1;

            Console.WriteLine(Max(0, A, N, M, abcd));
        }

        private static int Max(int i, int[] A, int N, int M, ABCD[] abcd)
        {
            if (i == N) return Calc(A, abcd);

            var max = 0;
            for (int j = A[i]; j <= M; j++)
            {
                A[i + 1] = j;
                max = Math.Max(Max(i + 1, A, N, M, abcd), max);
            }

            return max;
        }

        private static int Calc(int[] A, ABCD[] abcd)
        {
            return abcd.Where(s => A[s.B] - A[s.A] == s.C).Sum(s => s.D);
        }

        class ABCD
        {
            public int A { get; set; }
            public int B { get; set; }
            public int C { get; set; }
            public int D { get; set; }

            public ABCD(int[] array)
            {
                A = array[0];
                B = array[1];
                C = array[2];
                D = array[3];
            }
        }
    }
}


Measured memory_bytes: 40560
N, x = map(int, input().split())
alist = list(map(int, input().split()))
gokei = 0
if alist[0] > x:
    reduceBox = alist[0] - x
    gokei += reduceBox
    alist[0] = alist[0] - (reduceBox)
 
for i in range(N - 1):
    eat = alist[i] + alist[i+1] - x
    if eat > 0:
        gokei += eat
        alist[i+1] = alist[i+1] - eat
print(gokei)

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

ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return (a / g) * b;
}

int main() {
    ll A = 0;
    ll B = 0;
    ll C = 0;
    ll D = 0;
    cin >> A >> B >> C >> D;

    ll CDlcm =  lcm(C, D);

    ll underAperC = (A-1) / C;
    ll underBperC = B / C;

    ll underAperD = (A-1) / D;
    ll underBperD = B / D;

    ll underAperlcm = (A-1) / CDlcm;
    ll underBperlcm = B / CDlcm;

    ll underperC = underBperC - underAperC;
    ll underperD = underBperD - underAperD;
    ll underLcm = underBperlcm - underAperlcm;

    ll Count = B - A + 1;
    ll ans = Count - (underperC + underperD - underLcm);

    cout << ans << endl;
}

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

int main()
{
  string S, T;
  cin >> S >> T;
  int cnt = 0;
  if (S[0] == T[0]) ++cnt;
  if (S[1] == T[1]) ++cnt;
  if (S[2] == T[2]) ++cnt;
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 20//the maximum number of first elements
int solve(int[],int,int,int);
int main(void)
{
  int i;//counter
  int n;//the number of elements that can be used
  int arr[N];//input of second line
  int q;//the number of elements judged
  int x;//input of forth line
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&arr[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&x);
      if(solve(arr,n,0,x)==1) printf("yes\n");
      else printf("no\n");
    }
  return 0;
}
int solve(int arr[],int n,int p,int t)//checks whether we can make t by selecting after p-th element (inclusive)
{
  //printf("solve(arr,%d,%d,%d)\n",n,p,t); //debugging
  if(p>=n||t<0) return 0;
  if(t==arr[p]) return 1;
  if(solve(arr,n,p+1,t-arr[p])==1) return 1;
  if(solve(arr,n,p+1,t)==1) return 1;
  return 0;
}


Measured memory_bytes: 2144
import numpy

N, C = map(int, input().split())
STC = [list(map(int, input().split())) for i in range(N)]
Channel = numpy.array([[0]*(2*10**5+1) for i in range(C+1)])

for s, t, c in STC:
    Channel[c][2*s-1] += 1
    Channel[c][2*t] -= 1
    
for i in range(len(Channel)):
    Channel[i] = numpy.cumsum(Channel[i])
bool_Channel = Channel.astype(numpy.bool_)

needs = numpy.sum(bool_Channel, axis=0)
print(needs.max())



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

char printline[301];

class chessboard {
	int height;
	int width;
public:
	int setheight(int h);
	int setwidth(int w);
	int getheight(void);
	int getwidth(void);
	char* printboardline(int h);
};

int chessboard::setheight(int h) {
	if(h >=1 && h <=300){
		height = h;
		return h;
	} else
		return -1;
}

int chessboard::setwidth(int w) {
	if(w >= 1 && w <= 300) {
		width = w;
		return w;
	} else
		return -1;
}

int chessboard::getheight(void){
	if(height>= 1 && height <= 300)
		return height;
	else
		return -1;
}

int chessboard::getwidth(void){
	if(width >= 1 && width <= 300)
		return width;
	else
		return -1;
}

char* chessboard::printboardline(int h){
	int j;

	if(height >= 1 && height <= 300 && width >= 1 && width <= 300){
		if(h >= 0 && h <= height-1){
			if((h/2)*2 == h)
				j=1;
			else
				j=-1;
			for(int i=0;i<width;i++){
				if(j>0)
					printline[i]='#';
				else
					printline[i]='.';
				j *= -1;
			}
			printline[width]='\0';
			return printline;
		} else {
			printline[0] = '\0';
			return printline;
		}
	} else {
		printline[0] = '\0';
		return printline;
	}
}

int main() {
	int i=0,n;
	int h,w;
	class chessboard x[10001];

	while((cin >> h >> w)&&(!(h == 0 && w == 0))){
		x[i].setheight(h);
		x[i].setwidth(w);
		i++;
	}
	n=i;

	for(i=0;i<n;i++){
		h = x[i].getheight();
		for(int j=0;j<h;j++)
			cout << x[i].printboardline(j) << endl;
		cout << endl;
	}

	return 0;
}



Measured memory_bytes: 3108
import java.util.*;
/**
 * Created by 卢嘉昊 on 2017/8/12.
 */
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        int a = k%10;
        int b = k/100;
        if(a==b){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

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

#define maxn 100002
#define FOR(i, l, r) for (int i=l; i<=r; ++i)
#define FORD(i, r, l) for (int i=r; i>=l; --i)
#define REP(i, r) for (int i=0; i<(int)r; ++i)
#define REPD(i, r) for (int i=(int)r-1; i>=0; --i)
#define fi first
#define se second
#define mk make_pair
#define nil NULL
#define y0 y902
#define y1 y232
#define x0 x92
#define x1 x899
#define next asdfa
#define sz size
#define Debug(X) {cerr << #X << " = " << X << '\n';}
#define PR(A, n) {cerr << #A << " = "; FOR(i, 1, n) cerr << A[i] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; REP(i, n) cerr << A[i] << ' '; cerr << '\n';}
typedef long long ll;
typedef double db;
typedef pair<db, db> dd;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int inf = 1e9;
template<class T> int getbit(T x, int pos) {return (x>>(pos-1)) & 1;}
template<class T> void turn_on(T &x, int pos) {x = x | ((T)1<<(pos-1));}
template<class T> void turn_off(T &x, int pos) {x = x & ~((T)1<<(pos-1));}
template<class T> T sqr(T a) {return a*a;}

int n;
vector<int> a[maxn];

int grundy(int u, int par) {
    int res = 0;
    REP(i, a[u].sz()) {
        int v = a[u][i];
        if (v==par) continue;
        res ^= (grundy(v, u)+1);
    }
    return res;
}

int main() {
    //freopen("treegame.inp", "r", stdin);
    //freopen("", "w", stdout);
    //ios::sync_with_stdio(0); cin.tie(0);
    scanf("%d", &n);
    FOR(i, 1, n-1) {
        int u, v; scanf("%d%d", &u, &v);
        a[u].push_back(v); a[v].push_back(u);
    }
    if (grundy(1, 0)==0) printf("Bob");
    else printf("Alice");
}



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

typedef long long ll;

int main(){
    int n;
    ll c, k;
    cin >> n >> c >> k;
    vector<ll> v(n);
    for(int i=0; i<n; i++){
        cin >> v.at(i);
    }
    sort(v.begin(), v.end());
    ll ans = 1, start = v.at(0), cnt = 1;
    for(int i=1; i<n; i++){
        if(cnt >= c || v.at(i)-start > k){
            ans++;
            start = v.at(i);
            cnt = 1;
        }else{
            cnt++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <cstdio>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(x) x.begin(), w.end()

int main()
{
    ll a;
    double b;
    cin >> a >> b;
    int B = 100 * b;
    ll ans = a * B;

    cout << ans / 100 << "\n";
}

Measured memory_bytes: 3720
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <tuple>
#include <functional>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define rep(i,n) for(long long  i = 0; i < n; i++)
#define rep2(i,a,n) for(long long  i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl

using namespace std;

int main() 
{
    int a[3];
    rep(i,3) cin >> a[i];
    vector<int> index(3); 
    rep(i,3) index[i]=i;
    int ans = INF;
    
    do {
        int task = 0;
        for(int i = 0; i < 2; i++) {
            task += abs(a[index[i]]-a[index[i+1]]);
        }
        ans = min(ans, task);

    } while(next_permutation(index.begin(), index.end()));
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> &a, bool invert)
{
    int n = a.size();
    if (n == 1)
        return;

    vector<cd> a0(n / 2), a1(n / 2);
    for (int i = 0; 2 * i < n; i++)
    {
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }
    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * PI / n * (invert ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; 2 * i < n; i++)
    {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        if (invert)
        {
            a[i] /= 2;
            a[i + n / 2] /= 2;
        }
        w *= wn;
    }
}

vector<long long> multiply(vector<long long int> const &a, vector<long long int> const &b)
{
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<long long int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

const int N = 1e+5 + 5;
long long n, m;
long long int a[N];

int main()
{
    cin >> n >> m;
    int t = 0, g = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        a[t]++;
        g = max(t, g);
    }
    vector<long long int> A, B;
    for (int i = 0; i <= g; i++)
    {
        A.push_back(a[i]);
        B.push_back(a[i]);
    }
    vector<long long int> C = multiply(A, B);
    long long int ans = 0;
    long long int i = 0;
    for (long long int j = C.size() - 1; j >= 0; j--)
    {
        i += C[j];
        if (i >= m)
        {
            ans += j * max(C[j]-(i-m), 0LL);
            break;
        }
        ans += (j)*C[j];
        // j++;
    }
    cout << ans;
}

Measured memory_bytes: 21044
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]
Count=[0]
count=0
for i in range(1,10**5):
  if i in S:
    count+=1
  Count +=[count]

N=int(input())
for i in range(N):
  l,r=map(int,input().split())
  print(Count[r]-Count[l-1])

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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    int N, M;
    cin >> N >> M;
    int accum = 0;
    REP (i, M) {
        int Ai;
        cin >> Ai;
        accum += Ai;
    }
    cout << (N < accum ? -1 : N - accum) << endl;
    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
#define all(a) begin(a),end(a)

int main()
{
    int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
    vector<int> P(A), Q(B), R(C); cin >> P >> Q >> R;

    sort(all(P), greater<int>());
    sort(all(Q), greater<int>());
    sort(all(R), greater<int>());

    vector<int> S;
    S.insert(S.end(), P.begin(), P.begin() + X);
    S.insert(S.end(), Q.begin(), Q.begin() + Y);
    S.insert(S.end(), R.begin(), R.begin() + min(X + Y, C));
    sort(all(S), greater<int>());
    
    ll ans = accumulate(S.begin(), S.begin() + X + Y, 0LL);

    cout << ans << endl;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

typedef pair<int, int> P;

int main() {
    int H, W, D;
    cin >> H >> W >> D;

    vector<P> A(H * W + 1);
    rep(i, H) {
        rep(j, W) {
            int a;
            cin >> a;
            A[a] = make_pair(i, j);
        }
    }

    vector<vector<int>> S(D, vector<int>(((H + 1) * (W + 1)) / D));
    rep(i, D) {
        int k = 0;
        int offset = 0;
        if (i == 0) offset = D;
        for (int j = i + offset; j + D <= H * W; j += D) {
            P p1 = A[j];
            P p2 = A[j + D];
            S[i][k + 1] = S[i][k] + abs(p1.first - p2.first) + abs(p1.second - p2.second);
            k++;
        }
    }

//    rep(i, D) {
//        rep(j, H + W) {
//            cout << "(" << i << "," << j << ") " << S[i][j] << " : ";
//        }
//        cout << endl;
//    }

    int Q;
    cin >> Q;
    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        int d = l % D;
        if (d == 0) {
            r -= D;
            l -= D;
        }
        cout << S[d][r / D] - S[d][l / D] << endl;
    }
}

Measured memory_bytes: 6016
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>

bool f(std::vector<std::string> v1, std::vector<std::string> v2, int a, int b) {
    for (int k = a; k < v2.size() + a; k++) {
        for (int l = b; l < v2.size() + b; l++) {
            if (v1[k][l] != v2[k - a][l - b]) return false;
        }
    }
    return true;
}

int main() {
    int n, m;

    std::cin >> n >> m;

    std::vector<std::string> v1(n), v2(m);

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

    for (int i = 0; i < m; i++) {
        std::cin >> v2[i];
    }

    for (int i = 0; i <= n - m; i++) {
        for (int j = 0; j <= n - m; j++) {
            if (f(v1, v2, i, j)) {
                std::cout << "Yes" << std::endl;
                return 0;
            }
        }
    }
    std::cout << "No" << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int n, a, b, c, x;
	while (cin >> n >> a >> b >> c >> x) {
		if (!n && !a && !b && !c && !x)return 0;
		int y[114514];
		for (int i = 0; i < n; i++) cin >> y[i];
		int i, cnt = 0;
		for (i = 0; i < 10010; i++) {
			if (x == y[cnt]) { cnt++; if (cnt == n)break; }
			x = (a*x + b) % c;
		}
		if (i > 10000)cout << "-1\n";
		else cout << i << endl;
	}
}

Measured memory_bytes: 3096
#include <iostream>
#include <array>
#include <algorithm>
#include <cstdlib>

using namespace std;

constexpr int MAX_N = 100;
constexpr int MAX_M = MAX_N * MAX_N;
int par[MAX_N];
int myrank[MAX_N];
int n, m;


struct edge {
    int a, b, d;

    bool operator<(const edge &r) {
      return d < r.d;
    }
};

array<edge, MAX_M> e;


// Union Find Tree?????????????????????
//????????¶?????§??????????????????????????§???
//?????¨??????????´???????????????????
void init() {
  for (int i = 0; i < MAX_N; i++) {
    par[i] = i;
    myrank[i] = 0;
  }
}

// x?????????????´?????±??????????????????£??¨????????????
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// x,y????±?????????????????????¨??????
bool unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y)
    return false;

  if (myrank[x] < myrank[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (myrank[x] == myrank[y]) myrank[x]++;
  }

  return true;
}

int main() {
  int count, t;

  while (cin >> n, n) {
    cin >> m;
    init();

    t = 0;
    for (int i = 0; i < m; i++)
      scanf("%d,%d,%d", &(e[i].a), &(e[i].b), &(e[i].d));

    sort(e.begin(), e.begin() + m);
    for (int i = 0; i < m; ++i) {
      if (unite(e[i].a, e[i].b))
        t += e[i].d - 100 ;
    }
    cout << t / 100 << endl;
  }

  return 0;
}

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

typedef pair<int, int> P;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

ll division(ll x, ll y) {
  if (x % y == 0)
    return x / y;
  else
    return x / y + 1;
}

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

  int N;
  ll A, T;
  cin >> N;
  vector<pair<ll, ll> > p(N);
  rep(i, N) {
    cin >> T >> A;
    p[i] = make_pair(T, A);
  }
  pair<ll, ll> ans = p[0];
  for (int i = 1; i < N; i++) {
    ll tmp = max(division(ans._1, p[i]._1), division(ans._2, p[i]._2));
    ans = make_pair(p[i]._1*tmp, p[i]._2*tmp);
    // cout << ans._1 << ' ' << ans._2 << endl;
  }
  cout << ans._1 + ans._2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long int
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(),v.rend() //reverse
#define vl vector<long long>v(n);
#define mii unordered_map<ll,ll>
#define pb push_back
double pi = 2*acos(0.0);
//ll power(ll a,ll b){ ll res=1;while(b){if(b&1)res=res*a;b=b/2; a=(a*a); }return res;}

      
 int main()
 {
       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
       ll tst;
       tst=1;
       //cin>>tst;
    
       while(tst--)
       {
         ll n;
         cin>>n;
         vector<long long>v(n+1);ll cnt=0;
         for(int i=1;i<=n;i++)
         {
                   cin>>v[i];
                   if(i%2!=0&&v[i]%2!=0)
                   {
                             cnt++;
                   }
         }
         cout<<cnt<<endl;
       }
 }

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N,Z,W;
    cin >>N>>Z>>W;
    vector<ll>A(N);
    rep(i,N)cin>>A[i];
    ll ans1,ans2;
    ll X1,Y1,X2,Y2;
    if(N==1){
        cout<<abs(A[0]-W)<<endl;
    }else{
        X1=A[N-2];
        Y1=A[N-1];
        ans1=abs(X1-Y1);
        X2=A[N-1];
        Y2=W;
        ans2=abs(X2-Y2);
        cout<<max(ans1,ans2)<<endl;;
    }



    return 0;
    

}

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

using namespace std;

#define int long long
#define N 100005



int32_t main()
{
    int l;
    cin>>l;

    vector < pair < pair < int , int > , int > > ans;

    int n = 1;
    int cur = 2, sum = 0;
    for(int i=1;i<=21;i++)
    {
        sum=cur;
        if( (cur*2) > l)
        {
            n = i;
            break;
        }
        cur*=2;
    }
    cur = 1;
    int pp = 1;
    n++;

    for(int i=1;i<=n-1;i++)
    {
        if(l==0)
            break;
        if(l%2!=0)
        {
            l--;
            ans.push_back({{i, n}, sum}); 
            sum+=cur;  
        }
        cur*=2;
        ans.push_back({{i, i+1}, pp});
        ans.push_back({{i, i+1}, 0});
        pp*=2;
        l/=2;
    }

    cout<<n<<" "<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ll = int64_t;
#define MAX_N 1010
#define MAX_M 100010
const long long mod = pow(10, 9) + 7;
#define vec vector<int>
#define vecll vector<ll>
#define vecllvec vector<vector<ll>>
#define vecb vector<bool>
#define vecBvec vector<vector<bool>>
#define vecst vector<string>
#define veche vector<char>
#define vecd vector<double>
#define vecvec vector<vector<int>>
#define vecDvec vector<vector<double>>
#define vecHvec vector<vector<char>>
#define all(x) (x).begin(),(x).end()
#define ent cout<<endl
#define printvec(vec) for(int aqw=0;aqw<vec.size();aqw++){cout<<vec[aqw]<<" ";}ent;
#define rep1(n) for(ll i = 0; i < (n); ++i)
#define rep2(i, n) for(ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define INF 1e+9
#define print(x) cout<<x<<endl;
using P = pair<int, int>;
#define PLL pair<ll, ll>;
#define MAX_V 10010
#define PI 3.141592653589793
#define vecP vector<P>
//cout << setprecision(15) << std::fixed;

vector<vector<long long>> comb(int n, int r) {
    vector<vector<long long>> v(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i < v.size(); i++) {
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for (int j = 1; j < v.size(); j++) {
        for (int k = 1; k < j; k++) {
            v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
        }
    }
    return v;
}

int main() {
    int a, b;
    cin >> a >> b;
    vector<vector<long long>> v = comb(100, 2);
    print(v[a][2] + v[b][2]);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  int X, N, e;
  string kekka;
  cin >> X;
  e = X;
  N = 0;
  for (int i = 0; i < 8; i++){
    if (X < 1){
      break; 
    }
    N += X % 10;
    X = X / 10;
  }
  if (e % N == 0){
    kekka = "Yes";
  }else{
    kekka = "No";
  }
  cout << kekka << endl;
}

Measured memory_bytes: 256
//2020年4月17日現在

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

using namespace std;

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


namespace {
    // printElems(&a[0], &a[n]);　みたいな感じで使う。
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << ' ';
        }
        std::cout << std::endl;
    }
}

#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)
#define FOR(i,j,n) for(int i=j; i < n; i++)
#define souatari(i,j,n) rep1(i,n-1)rep(j,i)
#define souatari1(i,j,n) for(int i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
const ll BIG = 1LL<<60;

map<ll,ll> factorize(ll n)
{
    map<ll,ll> ret;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n/=i;
        }
    }
    if(n!=1) ret[n]++;
    return (ret);
}


int main(){
    ll n;
    cin >> n;
    map<ll,ll> m = factorize(n);
    ll ans = 0;
    for(auto itr = m.begin(); itr != m.end(); ++itr) {
        ll value = itr->second;
        ll tmp = 1;
        while(value>=tmp){
            value-=tmp;
            tmp++;
            ans++;
        }
    }
    prints(ans);


    return 0;
}




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

int main() {
  int K,A,B;
  cin >> K >> A >> B;
  
  int bai = (B / K) * K; //倍数を出力
  
  if (bai >= A) {
    cout << "OK" << endl;
  }
  else {
    cout << "NG" << endl;
  }
}

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

using namespace std;

long long Solve(long long a, long long b, long long g) {
    return b / g - (a - 1) / g;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   long long a, b, c, d;
   cin >> a >> b >> c >> d;
   long long g = c / __gcd(c, d) * d;
   long long Not = Solve(a, b, c) + Solve(a, b, d) - Solve(a, b, g);
   long long ans = b - a + 1 - Not;
   cout << ans << endl;
}

Measured memory_bytes: 3616
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
//const LL mod = 1000000007ll;
const int mod_int = 1000000007;

const LL mod = 998244353ll;

LL N,S;
LL A[3000];

LL ans = 0;

void solve(){
	//dp[i][j]:
	//L<=x1<=...<=xk<=RかつAx1+...+Axk=jを満たす
	//数列(Ax1,...,Axk)の個数をg(L,R)とおく
	//この時1<=L<=R<=iを満たす整数(L,R)の組全てに対する
	//g(L,R)の和をdp[i][j]とおく
	//こうすれば答えは
	//ans = dp[1][S] + dp[2][S] + ..... + dp[N][S]
	//とすれば良い。
	vector<vector<LL>> dp(N+1,vector<LL>(3001,0));
	for(int i=0;i<N;i++){
		//数列のi番目から見て、0個取るような方法は
		//各iに対して必ず1つずつある
		dp[i][0] += 1;
		//+=1としているのは数列の0~i-1番目それぞれからみて、
		//0個取るような方法が既にdp[i][0]に記録されていなければならないため
		for(int j=0;j<=3000;j++){
			//A[i]を使わない時
			dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod;
			//A[i]を使う時
			if(j+A[i]<=3000)dp[i+1][j+A[i]] = (dp[i+1][j+A[i]]+dp[i][j])%mod;
		}
	}
	for(int i=0;i<=N;i++) ans = (ans+dp[i][S])%mod;
}

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

    solve();

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

Measured memory_bytes: 70784
#include<iostream>
#include<algorithm>
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
using namespace std;
#define D 10000
int dp[D][D];
void LS(string a,string b)
{
	REP(i,a.size()+1)dp[i][0] = i;
	REP(i,b.size()+1)dp[0][i] = i;	
	for(int i = 1;i <= a.size() ;i++)
	{
		for(int j = 1;j <= b.size() ;j++)
		{
			int q = 1;
			if(a[i-1] == b[j-1])q = 0;
			dp[i][j] = min(min(dp[i-1][j-1]+q,dp[i][j-1]+1),dp[i-1][j]+1);
		}
	}	
}
int main()
{
	string a,b;cin >> a >> b;
	cout << (LS(a,b),dp[a.size()][b.size()]) << endl;
	return 0;
}

Measured memory_bytes: 11116
// abc134c: Exception Handling
#include <stdio.h>

#define rep(i,s,e) for(int i=s;i<e;i++)
#define in(n) scanf("%d",n)
#define outi(d) printf("%d\n",d)

int main(){
  int n;in(&n);
  int a[n+1],ix[2];
  a[0] = ix[0] = ix[1] = 0;
  rep(i,1,n+1){
    in(a+i);
    if(a[ix[0]]<a[i]) ix[0] = i;
    if(ix[0]!=i && a[ix[1]]<a[i]) ix[1] = i;
  }

  rep(i,1,n+1) outi(i==ix[0]? a[ix[1]]: a[ix[0]]);
  return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    int a[4]; rep(i,4) cin>>a[i];
    sort(a,a+4);
    if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w,v,s=0,ans=0;
long long f[100005];
int main()
{
	scanf("%d%d",&n,&m);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&w,&v);
		s+=v;
		for(int j=s;j>=v;--j)
			f[j]=min(f[j],f[j-v]+w);
	}
	for(int i=0;i<=s;++i)
		if(f[i]<=m)ans=max(ans,i);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 896
//的場梨沙★担当
//結城晴★副担当
//日野茜★副担当
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string.h>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main(void) {
    string S;
    cin>>S;
    int A=0;
    int B=0;
    int C=0;

    for(int i=0;i<3;i++){
        if(S[i]=='a'){
            A++;
        }
        else if(S[i]=='b'){
            B++;

        }
        else if(S[i]=='c'){
            C++;

        }
    }
    if(A!=0&&B!=0&&C!=0){
            cout<<"Yes"<<endl;

    }
    else{
        cout<<"No"<<endl;
    }


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n;
ll a[100001],b[100001],c[100001];
ll dp[5][100001];
ll solve(ll i,ll ch)
{
  if(i>=n)
  return 0;
  if(dp[ch][i]!=-1)
    return dp[ch][i];
  ll ans=0;
  if(ch!=0)
  ans=max(a[i]+solve(i+1,0),ans);
  if(ch!=1)
  ans=max(b[i]+solve(i+1,1),ans);
  if(ch!=2)
  ans=max(c[i]+solve(i+1,2),ans);
  return dp[ch][i]=ans;
}
int main()
{
  ll i,j;
  for(i=0;i<5;i++)
  {
    for(j=0;j<100001;j++)
    {
      dp[i][j]=-1;
    }
  }
  cin>>n;
 for(i=0;i<n;i++)
  {
    cin>>a[i]>>b[i]>>c[i];
  }
  solve(0,4);
  cout<<dp[4][0];
}
  
  

Measured memory_bytes: 11136
// D - Knight
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

#define MOD 1000000007
#define MAX 1000001
ll fac[MAX]; // 累乗 n!
ll inv[MAX]; // 逆元 1/n
ll finv[MAX]; // 逆元の累乗 (n^-1)! = (1/n)!

void init(int n, int p){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	rp(i, 2, n+1){
		fac[i] = fac[i-1] * i % p;
		inv[i] = p - inv[p%i] * (p/i) % p;
		finv[i] = finv[i-1] * inv[i] % p;
	}
}

ll comb(int n, int r, int m){
	if(n<r || n<0 || r<0) return 0;
	return fac[n] * (finv[n-r] * finv[r] % m) % m;
}

int main(){
	int X,Y; cin>>X>>Y;
	init(max(X,Y)+1, MOD);
	if((X+Y)%3 != 0){
		puts("0");
	}
	else{
		int r = (2*X-Y)/3;
		int n = (2*Y-X)/3 + r;
		cout<< comb(n, r, MOD) % MOD << endl;
	}
}

Measured memory_bytes: 23680
#include <stdio.h>

#define N 100

int main(){
  int a[N],n,i,j,t,min,count=0;
  scanf("%d",&n);
  for(i=0; i<n; i++) scanf("%d",&a[i]);
  for(i=0; i<n-1; i++){
    min=i;
    for(j=i+1; j<n; j++){
      if(a[j]<a[min]) min=j;
    }
    if(i!=min){
      t=a[i];a[i]=a[min];a[min]=t;
      count++;
    }
  }
  for(i=0; i<n-1; i++) printf("%d ",a[i]);
  printf("%d\n",a[i]);
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 2124
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    l = len(s)
    i = 0
    j = l-1
    r = 0
    while i<j:
        if s[i] == s[j]:
            i+=1
            j-=1
        elif s[i] == 'x':
            r += 1
            i+=1
        elif s[j] == 'x':
            r += 1
            j -= 1
        else:
            return -1
    return r


print(main())




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

signed main(void)
{
	char x, y;
	cin >> x >> y;

	if (x < y)
		cout << "<" << endl;
	else if (x > y)
		cout << ">" << endl;
	else
		cout << "=" << endl;
	return 0;
}


Measured memory_bytes: 256