akhauriyash/Code-Regression huggingface dataset:
import java.util.HashMap;
import java.util.Map;

public class Main {

  static int n;
  static long W;
  static int[][] a;
  private static void solve() {
    n = ni();
    W = nl();
    a = ntable(n, 2);
    
    long ret = dfs(0, 0);
    System.out.println(ret);
  }
  
  static Map<Long, Long> memo = new HashMap<>();
  private static long dfs(int i, long w) {
    if (i >= n) return 0;

    long h = w * 10000 + i;
    if (memo.containsKey(h)) {
      return memo.get(h);
    }

    
    long ret = dfs(i + 1, w);
    if (w + a[i][0] <= W) {
      ret = Math.max(ret, dfs(i + 1, w + a[i][0]) + a[i][1]);
    }
    memo.put(h, ret);
    return ret;
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = System.getProperty("debug");
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

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

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 47484
N=int(input())

A=list(map(int,input().split()))

B=list(map(int,input().split()))

suma=0
for i in range(N):
    if A[i]>=B[i]:
        A[i]-=B[i]
        suma+=B[i]
        #B[i]=0
    else:
        B[i]-=A[i]
        suma+=A[i]
        if A[i+1]>=B[i]:
            A[i+1]-=B[i]
            suma+=B[i]
        else:
            suma+=A[i+1]
            A[i+1]=0

print(suma)

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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M;
  cin >> N >> M;
  vint a(N), b(N), c(M), d(M);
  rep(i, N) cin >> a[i] >> b[i];
  rep(i, M) cin >> c[i] >> d[i];
  rep(i, N) {
    int idx = 0;
    rep(j, M) {
      if(llabs(a[i]-c[j])+llabs(b[i]-d[j]) < llabs(a[i]-c[idx])+llabs(b[i]-d[idx])) idx = j;
    }
    cout << idx+1 << endl;
  }

  return 0;
}


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

int main() {
    int N;
    cin >> N;
    if (N < 105) {
        cout << 0 << endl;
    }
    else if (N >= 105 && N < 135){
        cout << 1 << endl;
    }
    else if (N >= 135 && N < 165) {
        cout << 2 << endl;
    }
    else if (N >= 165 && N < 189) {
        cout << 3 << endl;
    }
    else if (N >= 189 && N < 195) {
        cout << 4 << endl;
    }
    else {
        cout << 5 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int i, j;
    int h, w;
    
    while(scanf("%d %d", &h, &w), h > 0 && w > 0){
        for(i = 0; i < h; ++i){
            for(j = 0; j < w; ++j){
                putchar((i + j) % 2 == 0 ? '#' : '.');
            }
            
            putchar('\n');
        }
        
        putchar('\n');
    }
    
    return 0;
}

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

#define int long long
#define vec vector
using namespace std;

signed main(){
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while(n) n /= k, ans++;
    ans = max(ans, 1LL);
    cout << ans;
	return 0;
}


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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


void Main() {
  ll r;
  cin >> r;
  COUT(3 * r * r)
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*

3 2
*/


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const size_t MAX_N = (size_t) 1e5 + 5;
ll a[MAX_N], b[MAX_N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    ll res = 0;
    for (int i = n - 1; i + 1; i--) 
        res += (b[i] - (a[i] + res) % b[i]) % b[i];
    cout << res;
}

Measured memory_bytes: 1792
import java.util.Scanner;

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

    public static void solve(Scanner sc) {
        char[] aHand = sc.nextLine().toCharArray();
        char[] bHand = sc.nextLine().toCharArray();
        char[] cHand = sc.nextLine().toCharArray();
        int a = 0;
        int b = 0;
        int c = 0;

        int next = aHand[a];
        a++;

        while (true) {
            switch (next) {
            case 'a':
                if (aHand.length <= a) {
                    System.out.println("A");
                    return;
                }
                break;
            case 'b':
                if (bHand.length <= b) {
                    System.out.println("B");
                    return;
                }
                break;
            case 'c':
                if (cHand.length <= c) {
                    System.out.println("C");
                    return;
                }
                break;
            }

            switch (next) {
            case 'a':
                next = aHand[a];
                a++;
                break;
            case 'b':
                next = bHand[b];
                b++;
                break;
            case 'c':
                next = cHand[c];
                c++;
                break;
            }
        }
    }
}

Measured memory_bytes: 21844
%:pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;

int n, a[201000], pos[201000], b[201000], l[200100], r[200100], M[19][200100], p[19][200100];

int Query(int l, int r, int ty) {
	int t = (int)log2((r - l + 2) / 2);
	if((r - l) & 1) r--;
//	printf("%d : %d %d\n", t, p[t][l], p[t][r - (1 << t)]);
//	system("pause");
	int mi = min(M[t][l], M[t][r - (1 << (t + 1)) + 2]);
	if(!ty) return mi;
	else return M[t][l] == mi ? p[t][l] : p[t][r - (1 << (t + 1)) + 2];
} 

struct Node{
	int l, r;
	Node(int l = 0, int r = 0) : 
		l(l), r(r) {}
	bool operator < (const Node &b) const {
		return Query(l, r, 0) > Query(b.l, b.r, 0);
	}
};

void Read(int &x) {
	char ch = getchar(); x = 0;
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}

priority_queue<Node> q;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		Read(a[i]);
		M[0][i] = a[i];
		p[0][i] = i;
	}
	
	for(int i = 1; i <= 18; i++)
		for(register int j = 1; j <= n - (1 << (i + 1)) + 2; j++) {
			M[i][j] = min(M[i - 1][j], M[i - 1][j + (1 << i)]);
			p[i][j] = M[i][j] == M[i - 1][j] ? p[i - 1][j] : p[i - 1][j + (1 << i)];
		}

	q.push(Node(1, n));
	while(!q.empty()) {
		Node now = q.top(); q.pop();
		int mi = Query(now.l, now.r, 1);
		int mii = Query(mi + 1, now.r, 1);
		printf("%d %d ", a[mi], a[mii]);
		
		if(mii - mi > 1) q.push(Node(mi + 1, mii - 1));
		if(mi != now.l) q.push(Node(now.l, mi - 1));
		if(mii != now.r) q.push(Node(mii + 1, now.r));
	}
	return 0;
}
/*
6
1 4 5 2 3 6
12 
9 8 6 10 12 4 1 3 11 5 2 7
*/












Measured memory_bytes: 31356
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define fix(n) cout<<fixed<<setprecision(n)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
using namespace std;
typedef long long ll;
const ll mod=1000000007;
double pi=3.1415926535;

int main(){
  int a[3][3],b,c,ans=0;
  rep(i,0,3) rep(j,0,3) cin>>a[i][j];
  b=a[0][0]-a[0][1]; c=a[0][1]-a[0][2];
  rep(i,1,3) if(a[i][0]-a[i][1]==b && a[i][1]-a[i][2]==c) ans++;
  b=a[0][0]-a[1][0]; c=a[1][0]-a[2][0];
  rep(i,1,3) if(a[0][i]-a[1][i]==b && a[1][i]-a[2][i]==c) ans++;
  if(ans==4) co("Yes");
  else co("No");
  return 0;
}

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

#define MAXNUM 1000001

bool prime[MAXNUM];

void eratosthenes()
{
	prime[0]=prime[1]=false;

	for(int i=2; i<MAXNUM; i++)
	{
		prime[i]=true;
	}
	
	for(int i=2; i*i<MAXNUM; i++)
	{
		if(prime[i])
		{
			for(int j=i*i; j<MAXNUM; j+=i)
			{
				prime[j]=false;
			}
		}
	}
}


bool dp[1000001];

int main()
{
	eratosthenes();
	int N,B,c[30];
	while(cin >> N >> B, (N||B))
	{
		memset(dp,0,sizeof(dp));
		for(int i=0; i<N; i++)
			cin >> c[i];
			
		dp[0]=1;
		
		for(int i=0; i<N; i++)
		for(int j=0; j<B; j++)
		{
			if(j+c[i]>B) break;
			if(dp[j]) dp[j+c[i]]=1;
		}
		
		bool g=false;
		for(int i=B; i>1; i--)
		{
			if(dp[i]&&prime[i])
			{
				g=true;
				cout << i << endl;
				break;
			}
		}
		if(!g) cout << "NA" << endl;
	}
}

Measured memory_bytes: 2816
import sys

n,a,b = map(int,input().split())

if (b-a)%2 == 0:
  print((b-a)//2)
else:
  tmp1 = (n-b+1) + (b-a-1) //2
  tmp2 = a + (b-a-1) //2
  
  print(min(tmp1,tmp2))

Measured memory_bytes: 2940
import itertools

H,W,K=map(int,input().split())
c = [input() for j in range(H)]

black=[]
for i in range(H):
    for j in range(W):
        if c[i][j] == '#':
            black.append([i,j])
black_cnt=len(black)
            
cnt=0
ans_list=[]
for i in range(H):
    for comb_H in itertools.combinations(range(H),i):
        for j in range(W):          
            for comb_W in itertools.combinations(range(W),j):
                temp_black=black.copy()
                temp=temp_black.copy()
                for k in temp_black:
                    if k[0] in list(comb_H):
                        if k in temp:
                            temp.remove(k)
                    if k[1] in list(comb_W):
                        if k in temp:
                            temp.remove(k)

                if len(temp) == K:
                    #print("comb:",comb_H,comb_W)
                    if [list(comb_H),list(comb_W)] in ans_list:
                        pass
                    else:
                        ans_list.append([list(comb_H),list(comb_W)])
                    
                    
print(len(ans_list))
                
                

Measured memory_bytes: 9384
#include <bits/stdc++.h>
using namespace std;
 
int two(long a) {
  int ret = 0;
  while (a % 1024 == 0) {
    ret += 10;
    a /= 1024;
  }
  while (a % 2 == 0) {
    ret += 1;
    a /= 2;
  }
  return ret;
}

int main() {
  int N;
  cin >> N;
  vector<long> a(N);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    ans += two(a[i]);
  }
  cout << ans;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
long long n,k,res;
vector<long long> v;
long long lowgbnum(long long x,long long y)
{
	const long long x1=x;
	const long long y1=y;
	while(y) 
	{
	    long long z=x%y;
	    x=y;
	    y=z;
	}
	return x1*y1/x;
}
int main()
{
	cin>>n>>k;
	for(long long i=1;i<=n;i++)
	{
		res=0;
		res+=n;
		long long tmp=i,z=1;
		while(tmp<k)
		{
			tmp*=2;
			z*=2;
		}
		res*=z;
		v.push_back(res);
	}
	long long tmp=1;
	long long ans=0;
	for(long long i=0;i<v.size();i++)
		tmp=lowgbnum(tmp,v[i]);
	for(long long i=0;i<v.size();i++)
		ans+=tmp/v[i];
	double u=(double)ans/tmp;
	printf("%0.12lf",u);
	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	string s;
 
    int a, b;
 
    cin >> a >> b;
    cin >> s;
 
    for(int i=0; i<s.size(); i++)
    {
    	if(i==a)
    	{
    		if(s[i]!='-')
    		{
    			cout << "No";
    			return 0;
    		}
    	}
    	else if(!isdigit(s[i]))
    	{
    		cout << "No";
    		return 0;
    	}
    }
    
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=70010,mod=1e9+7;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    if(f) x=-x;
}
int n,m,N,ans,a[20],f[18][maxn],fac[maxn],inv[maxn],cnt[maxn];
int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x<y?x-y+mod:x-y;}
int C(int n,int m){return m>n?0:(ll)fac[n]*inv[m]%mod*inv[n-m]%mod;}
int power(int x,int y)
{
	int res=1;
	for(;y;y>>=1,x=(ll)x*x%mod)
	  if(y&1)
	    res=(ll)res*x%mod;
	return res;
}
int main()
{
	read(n);read(m);N=1<<n;fac[0]=1;
	for(int i=1;i<=m;i++) read(a[i]);
	for(int i=1;i<=N;i++) fac[i]=(ll)fac[i-1]*i%mod;
	inv[N]=power(fac[N],mod-2);
	for(int i=N-1;~i;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
	reverse(a+1,a+m+1);f[0][0]=1;
	for(int i=0;i<m;i++)
	{
		for(int s=0;s<N;s++) f[i+1][s]=f[i][s];
		for(int s=0;s<N;s++)
		  for(int j=0;j<n;j++)
		    if(~s&(1<<j))
		    {
		    	f[i+1][s|(1<<j)]=(f[i+1][s|(1<<j)]+(ll)C(N-a[i+1]-s,(1<<j)-1)*fac[1<<j]%mod*f[i][s])%mod;
		    }
	}
	for(int s=0;s<N;s++)
	{
		cnt[s]=cnt[s>>1]+(s&1);
		if(cnt[s]&1) ans=dec(ans,(ll)f[m][s]*fac[N-s-1]%mod);
		else ans=(ans+(ll)f[m][s]*fac[N-s-1])%mod;
	}
	ans=(ll)ans*N%mod;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 5248
#include<stdio.h>

int main(void)


{


int a,b,d,r;


double f;


scanf("%d",&a);


scanf("%d",&b);


d=a/b;


r=a%b;


f=(double)a/(double)b;


printf("%d %d %lf\n",d,r,f);


return 0;


}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long long> a(n);
  for_each(begin(a), end(a), [](auto &e) {
    cin >> e;
  });

  const int neg_count = count_if(begin(a), end(a), [](auto e) {
    return e < 0;
  });
  const int zero_count = count_if(begin(a), end(a), [](auto e) {
    return e == 0;
  });
  
  for_each(begin(a), end(a), [](auto &e) {
    e = abs(e);
  });
  if (neg_count % 2 == 0 || (neg_count + zero_count) % 2 == 0) {
    cout << accumulate(begin(a), end(a), 0LL) << endl;
  } else {
    const auto min_val = *min_element(begin(a), end(a));
    cout << accumulate(begin(a), end(a), 0LL) - min_val * 2 << endl;
  }
}


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

int main() {
    int d, L, R;
    cin >> L >> R >> d;
    int count = 0;
    for(int i = L; i <= R; i++) {
        if(i%d == 0) {
            count++;
        }
    }
    cout << count;
    return 0;
}

Measured memory_bytes: 3584
mod = 998244353
S, K = input().split()
a = [len(x) for x in S.split("0")]
K = min(int(K), sum(a)+1)

# f[i][j][k] : 右からi個目の区間まで見て、これまでにj個の1をpick upして、そのうちk個の置き場所が確定しているような操作を行った後の"状態数"
# ans -> f[len(a)][0][0] + f[len(a)][1][1] + ... + f[len(a)][K][K]


def solve_naive():  # TLE解
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    for num in range(1, j-k+1):
                        if k + num > K:
                            break
                        f[i][j][k+num] += f[i-1][j][k]  # a[-i]に1をnum個置く
                        f[i][j][k+num] %= mod

                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    for num in range(1, a[-i]+1):
                        if j + num > K:
                            break
                        f[i][j+num][k] += f[i-1][j][k]  # a[-i]から1をnum個取る
                        f[i][j+num][k] %= mod
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


def solve():
    f = [[[0 for k in range(K+1)] for j in range(K+1)]
         for i in range(len(a)+1)]

    for i in range(len(a)+1):
        if i == 0:
            # 区間を一つも見ていないので、1を選ぶことができない
            f[i][0][0] = 1
        else:
            for j in range(K+1):
                cum2 = 0
                for k in range(j+1):
                    # 1. 右からi番目の区間a[-i]では何もしない（i.e. a[-i]から1を取らないし、持ってる1をa[-i]に置かない）
                    f[i][j][k] += f[i-1][j][k]
                    f[i][j][k] %= mod

                    # 2. a[-i]に1をいくつか置く
                    # f[i][j][k] += f[i-1][j][0] (a[-i]にk個置く) + f[i-1][j][1]+ ... + f[i-1][j][k-1] (a[-i]に1個置く)
                    f[i][j][k] += cum2
                    f[i][j][k] %= mod
                    cum2 += f[i-1][j][k]

            for k in range(K+1):
                cum3 = 0
                for j in range(k, K+1):
                    # 3. a[-i]から1をいくつか取る。
                    # 注: a[-1]に1を「置く」と「取る」を両方することは考えなくてよい。より少ない回数の操作で同じ状態が実現されるので。
                    # f[i][j][k] += f[i-1][k][k] (a[-i]からj-k個取る) + f[i-1][k+1][k] + .... + f[i-1][j-1][k] (a[-i]から1個取る)
                    if j < a[-i]:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k]
                    else:
                        f[i][j][k] += cum3
                        f[i][j][k] %= mod
                        cum3 += f[i-1][j][k] - f[i-1][j-a[-i]][k]
    ans = 0
    for num in range(K+1):
        ans += f[len(a)][num][num]
        ans %= mod
    return ans


print(solve())


Measured memory_bytes: 107040
import java.util.Scanner;

class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		if (sc.nextInt() + sc.nextInt() + sc.nextInt() < 22) {
			System.out.println("win");
		} else {
			System.out.println("bust");
		}
	}
}

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

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

Measured memory_bytes: 21716
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e10;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

const ll mod = 1e9 + 7;

int main(){
    ll H, W; cin >> H >> W;
    vvc a(H, vc(W)); REP(i, H) REP(j, W) cin >> a[i][j];
    
    vvl dp(H+1, vl(W+1, 0)); dp[1][1] = 1;
    FOR(i, 1, H) FOR(j, 1, W){
        if(i == 1 && a[i-1][j] != '#') dp[i][j+1] = dp[i][j];
        if(j == 1 && a[i][j-1] != '#') dp[i+1][j] = dp[i][j];
        if(i < H && j < W && a[i][j] != '#') dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]) % mod;
    }
    cout << dp[H][W] % mod << endl;
    return 0;
}


Measured memory_bytes: 9088
import java.io.*;
import java.util.*;
import java.lang.*;

class Pair<E,F>{
    E first;
    F second;
    public Pair(E first, F second){
        this.first=first;
        this.second=second;
    }
    public E getFirst(){return first;}
    public F getSecond(){return second;}
    public String toString(){
        return "<"+first.toString()+","+second.toString()+">";
    }
    public int hashCode(){
        return first.hashCode()*30011+second.hashCode()+2;
    }
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair another = (Pair) obj;
        return this.getFirst().equals(another.getFirst())&&this.getSecond().equals(another.getSecond());
    }
}

public class Main {
    static int firstDigit(int n){
        return Integer.toString(n).charAt(0)-'0';
    }
    static int lastDigit(int n){
        return n%10;
    }

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

        int[][] count = new int[10][10];
        for(int n=1; n<=N; n++) count[firstDigit(n)][lastDigit(n)]++;

        long ans = 0;
        for(int i=0; i<10; i++) for(int j=0; j<10; j++){
            ans += count[i][j]*count[j][i];
        }
        System.out.println(ans);
    }


}


Measured memory_bytes: 32596
//Name: Unique number
//Level: 1
//Category: やるだけ
//Note:
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int> > v(3, vector<int>(N));
    vector<int> score(N, 0);

    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < 3; ++j) {
            cin >> v[j][i];
        }
    }

    for(int j = 0; j < 3; ++j) {
        map<int,int> cnt;
        for(int i = 0; i < N; ++i) {
            cnt[v[j][i]]++;
        }
        for(int i = 0; i < N; ++i) {
            if(cnt[v[j][i]] == 1) {
                score[i] += v[j][i];
            }
        }
    }

    for(int i = 0; i < N; ++i) {
        cout << score[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

ll cnt[10000000];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    ll n;cin>>n;
    for(ll i=1;i<=n;i++){
        for(ll j=i;j<=n;j+=i) cnt[j]++;
    }

    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans+=i*cnt[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 81732
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int in_or_not(const vector<int> &c, int a){
  bool flag = false;
  int i;
  for(i = 0; i < c.size(); ++i){
    if(c[i] == a){
      flag = true;
      break;
    }
  }
  if(flag){
    return i;
  }
  else{
    return -1;
  }
}

int main() {
  string a, b;
  cin >> a >> b;
  vector<int> ca(26);
  vector<int> cb(26);
  bool flag = true;
  int l = (int)a.size();

  for(int i = 0; i < l; ++i){
    int x = in_or_not(ca, a[i]);
    if(x == -1){
      ca.push_back(a[i]);
    }
    int y = in_or_not(cb, b[i]);
    if(y == -1){
      cb.push_back(b[i]);
    }
    if (x != y){
      flag = false;
      break;
    }
  }

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

Measured memory_bytes: 776
#include<bits/stdc++.h>
#define rep(i,N) for(ll (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;
const int mod = 1000000007;
const int INF = 1001001001;

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

  rep(cc, 26) {
    string st = s;
    char c = 'a' + cc;
    int cnt = 0;

    while(1) {
      // cout << st << endl;
      bool ok = true;
    
      rep(i, st.length()) {
        if (st[i] != c) ok = false;
      }
      if (ok) break;
      string t;
      rep(i, st.length() - 1) {
        if (st[i] == c || st[i + 1] == c) t.push_back(c);
        else t.push_back(st[i]);
      }
      st = t;
      cnt++;
    }
    chmin(ans, cnt);
  }

  cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    double n,c;
    cin >> n >> c;
    ll sum = 0;
    rep(i,c){
        int in = 0;
        cin >> in;
        sum += in;
    }
    cout << ceil(sum/(n+1)) << endl;
    return 0;
}


Measured memory_bytes: 3288
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	N = int(input())
	A = input().split()
	A = [int(s) for s in A]

	ans = 0
	dels = 0
	naiCounts = 0
	lasts = -1
	for i, val in enumerate(A):
		if val < 0:
			lasts = i
			naiCounts += 1
		if val == 0:
			lasts = -1
			naiCounts = 0
			break

	if naiCounts % 2 == 0 or naiCounts == 0:
		for i, val in enumerate(A):
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val
		print(ans)
		sys.exit()

	tmp = -1
	for i, val in enumerate(A):
		if tmp == -1 or tmp > abs(val):
			tmp = abs(val)
			dels = i
	
	#print(dels)
	for i, val in enumerate(A):
		if i == dels:
			#print(val)
			if val < 0:
				ans += val
			else:
				ans -= val
		else:
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val


	print(ans)



def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()
	

Measured memory_bytes: 14712
#include<stdio.h>
#include<stdlib.h>

#define MAX 500000
#define INFTY 1000000000

void MargeSort(int *,int,int);
void Marge(int *,int,int,int);

int count=0;

int main(void){
  int n,i,A[MAX];

  scanf("%d", &n);
  for(i=0;i<n;i++) scanf("%d", &A[i]);

  MargeSort(A,0,n);
  //for(i=0;i<n;i++) printf("%d", A[i]);
  //printf("\n");

  for(i=0;i<n;i++){
    if(i!=n-1) printf("%d ",A[i]);
    else printf("%d\n", A[i]);
  }
  printf("%d\n", count);

  return 0;
}

void MargeSort(int *A,int left, int right){
  int mid;

  if(left+1<right){
    mid=(left+right)/2;
    MargeSort(A,left,mid);
    MargeSort(A,mid,right);
    Marge(A,left,mid,right);
  }

}

void Marge(int *A,int left, int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int L[n1+1],R[n2+1];
  int i,j,k;

  for(i=0;i<n1;i++) L[i]=A[left+i];
  for(i=0;i<n2;i++) R[i]=A[mid+i];

  L[n1]=INFTY; R[n2]=INFTY; i=0; j=0;

  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    } else {
      A[k]=R[j];
      j++;
    }
    count++;
  }

}

Measured memory_bytes: 4504
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


int main()
{
	int A,B,D;
	char op;
	scanf("%d %c %d", &A,&op,&B);

	if (op == '+') {
		D = A + B;
	}else {
		D = A - B;
	}

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

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
	int n;
	int i, j, k;
	cin >> n;
	unsigned long *a = new unsigned long[n];
	unsigned long *ans = new unsigned long[n];

	unsigned long calc;
	cin >> a[0];
	calc = a[0];
	cin >> a[1];
	for (i = 2; i < n; i++) {
		cin >> a[i];
		calc = calc ^ a[i];
	}

	ans[1] = calc;
	ans[0] = a[0] ^ a[1] ^ ans[1];
	for (i = 2; i < n; i++) {
		ans[i] = a[i] ^ a[0] ^ ans[0];
	}

	cout << ans[0];
	for (i = 1; i < n; i++) {
		cout <<" "<< ans[i];
	}
	cout << endl;
	return 0;

	cout << endl;
	for (i = 0; i < n; i++) {
		if (i == 0) {
			calc = ans[1];
			j = 2;
		}
		else {
			calc = ans[0];
			j = 1;
		}
		for (; j < n; j++) {
			if (i != j) {
				calc = calc ^ ans[j];
			}
		}
		cout << calc << endl;
	}

	return 0;
}


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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

struct unionfind
{
    unionfind(int n) : par(n), rank(n, 0)
    {
        rep(i, n) par[i] = i;
    }

    int find(int x)
    {
        return par[x] == x ? x : par[x] = find(par[x]);
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (rank[x] < rank[y])
        {
            par[x] = y;
        }
        else
        {
            par[y] = x;
            if (rank[x] == rank[y])
                ++rank[x];
        }
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    vint par, rank;
};

void Main()
{
    int n = in(), m = in();
    unionfind uf(n);
    rep(i, m)
    {
        int x = in(), y = in(), z = in();
        --x, --y;
        uf.unite(x, y);
    }

    setint st;
    rep(i, n)
    {
        st.insert(uf.find(i));
    }
    cout << st.size() << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 5760
#include <cstdio>
#include <algorithm>

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

using namespace std;

int A, B, K;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int x;
	scanf("%d %d %d", &A, &B, &K);
	int i = 1;
	int num = gcd(A, B);
	while (i < K) {
		num--;
		if (A % num == 0 && B % num == 0) {
			i++;
		}
	}
	printf("%d\n", num);
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#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 pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n, t;
    cin >> n >> t;
    VI a(n);
    REP(i,n) scanf("%d", &a[i]);

    int ma = 0, dif = 0, ans = 0;
    FORR(i,n-1,0){
        ma = max(ma, a[i]);
        int x = ma - a[i];
        if (x == dif) ans++;
        if (x > dif){
            dif = x;
            ans = 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

string s;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> s;
	for (int i = 0; i < s.size(); i += 2) cout << s[i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 592
#include<cstdio>
#include<iostream>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define MAX_V 500000
int heap[MAX_V]{0};

int left(int i){return 2*i+1;}
int right(int i){return 2*i+2;}
int parent(int i){return (i-1)/2;}
bool has_left(int size,int i){return size>left(i);}
bool has_right(int size,int i){return size>right(i);}

void max_heapify(int n, int i){
  int l,r,largest;
  l=left(i); r=right(i);
  if(has_left(n,i)&&heap[l]>heap[i])
    largest=l;
  else
    largest=i;
  if(has_right(n,i)&&heap[r]>heap[largest])
    largest=r;
  if(largest!=i){
    swap(heap[i],heap[largest]);
    max_heapify(n,largest);
  }
}
void build_max_heap(int size){
  for(int i=(size-1)/2;i>=0;i--)
    max_heapify(size,i);
}

int main(){
  int n; scanf("%d",&n);
  REP(i,n) scanf("%d",&heap[i]);
  build_max_heap(n);
  REP(i,n) printf(" %d",heap[i]);
  puts("");
}

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

typedef long long ll;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

// bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) {
//     return arg1.first > arg2.first;
// }

int main(void) {
    int a,b,c,x,y,z,buff;
    cin >> x >> y >> z;

    a=x;
    b=y;
    c=z;

    buff=a;
    a=b;
    b=buff;

    buff=a;
    a=c;
    c=buff;

    cout << a << " " << b << " " << c << endl;

    return 0;
}


Measured memory_bytes: 256
<?php

fscanf(STDIN, "%d", $n);

while ($line = fgets(STDIN)) {
   $S[] = trim($line);
}

$dbtmp = array_count_values($S);
ksort($dbtmp);
$db = max($dbtmp);

foreach($dbtmp as $d => $b){
    if($b == $db){
        echo($d."\n");
    }
}
  
?>

Measured memory_bytes: 29680
import java.util.*;
import java.io.*;

public class Main {
	static FastReader f = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);
	

	public static void main(String[] args) {
		//int t = f.nextInt();
		//while(t-- > 0)
			solve();
		out.close();
	}

	static int MOD = 998244353;
	static void solve() {
		int n = f.nextInt();
		int k = f.nextInt();
		int[][] arr = new int[k][2];
		for(int i=0;i<k;i++) {
			arr[i][0] = f.nextInt();
			arr[i][1] = f.nextInt();
		}

		SegmentTree seg = new SegmentTree(n);
		seg.update(0,1);
		for(int i=1;i<n;i++) {
			long loc = 0;
			for(int j=0;j<k;j++) {
				loc = (loc + seg.get(Math.max(0,i-arr[j][1]), Math.max(i-arr[j][0]+1,0))) % MOD; 
			}
			seg.update(i, (int) loc);
		}

		out.println(seg.get(n-1,n));
	}

	static class SegmentTree {
        int n;
        int[] arr;
 
        SegmentTree(int l) {
            this.n = calc(l);
            arr = new int[n << 1];
        }
 
        private static int calc(int size) {
            int ans = 1;
            while (ans < size) {
                ans <<= 1;
            }
            return ans;
        }

        void update(int i, int x) {
            int ind = n - 1 + i;
            arr[ind] = x;
            while (ind > 0) {
                ind = (ind-1)/2;
                arr[ind] = (arr[2*ind+1]+ arr[2*ind+2]) % MOD;
            }
        }
 
        long get(int left, int right) {
            return search(left, right, 0, 0, n);
        }
 
        long search(int l, int r, int x, int lx, int rx) {
 
            if(rx <= l || r <= lx) {
                return 0;
            }
            if(l <= lx && rx <= r) {
                return arr[x];
            }
 
            return (search(l, r, 2*x+1, lx, (rx+lx)/2)+
                    search(l, r, 2*x+2, (rx+lx)/2, rx)) % MOD;
        }
 
    }
 
 

	static class FastReader {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException ioe) {
					ioe.printStackTrace();
				}
			}
			return st.nextToken();
		}

		String nextLine() {
			String s = "";
			try {
				s = br.readLine();
			} catch(IOException ioe) {
				ioe.printStackTrace();
			}

			return s;
		}

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

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

int main(){
  string s;
  int q;
  cin >> s >> q;
  bool rev = false;
  vector<char> top(0);
  vector<char> end(0);
  
  for(int i = 0; i < q; i++){
    int t; cin >> t;
    if(t == 1){
      if(rev)
        rev = false;
      else
        rev = true;
    }
    else{
      int f; cin >> f;
      char c; cin >> c;
      if(f == 1){
        if(rev)
          end.push_back(c);
        else
          top.push_back(c);
      }
      else{
        if(rev)
          top.push_back(c);
        else
          end.push_back(c);
      }
    }
  }
  
  string ans;
  
  for(int i = 0; i < top.size(); i++)
    ans += top[top.size()-i-1];
  
  ans += s;
  
  for(int i = 0; i < end.size(); i++)
    ans += end[i];
  
  for(int i = 0; i < ans.size(); i++){
    int n = i;
    if(rev)
      n = ans.size()-i-1;
    cout << ans[n];
  }
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 1368
#include<stdio.h>

int main(){
    int i,j,k,n,m,x,y;
    char b[101][101];

    scanf("%d",&n);
    while(n--){
        for(i=0;i<101;i++){
            for(j=0;j<101;j++){
                b[i][j]=' ';
            }
        }
        scanf("%d",&m);

        x=m;y=1;
        b[x][y]='#';
        for(i=0,k=m-1;i<m;i++){
            for(j=0;j<k;j++){
                if(i%4==0){
                    //puts("0");
                    b[--x][y]='#';
                    //if(i!=0||j!=k-1)x--;
                }
                if(i%4==1){
                    //puts("1");
                    b[x][++y]='#';
                    //y++;
                }
                if(i%4==2){
                    //puts("2");
                    b[++x][y]='#';
                    //x++;
                }
                if(i%4==3){
                    //puts("3");
                    b[x][--y]='#';
                    //y--;
                }
                //printf("x:%d y:%d k:%d\n",x,y,k);
            }
            if(i==0)k;
            else if(i%2==0){
                k-=2;
            }
        }
        for(i=1;i<=m;i++){
            for(j=1;j<=m;j++){
                printf("%c",b[i][j]);
            }
            puts("");
        }if(n)puts("");
    }
    return 0;
}

Measured memory_bytes: 592
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
   unsigned int ar[n];
   int i;
   for(i=0;i<n;i++)
   {
       scanf("%d",&ar[i]);
   }
    int c=1;
    for(i=0;i<n;i++)
    {
        if(ar[i]%2==0)
        {
            if(ar[i]%5!=0)
            {
               if(ar[i]%3!=0)
               {
                   c=0;
               }

            }
        }
    }
    if(c==1)
        printf("APPROVED");
    else
        printf("DENIED");
    return 0;


}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5+5;
int a[maxn];
 
int main()
{
  int n,k,q;
  int temp;
  while(cin>>n>>k>>q){
	memset(a, 0, sizeof(a));
    for(int i=0;i<q;i++){
      cin>>temp;
      a[temp]++;
    }
    for(int i=1;i<=n;i++){
      a[i] += k-q;
      if(a[i] > 0)
        puts("Yes");
      else
        puts("No");
    }
  }
  return 0;
}

Measured memory_bytes: 1024
# include <algorithm>
# include <cassert>
# include <cctype>
# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <cmath>
# include <iostream>
# include <map>
# include <queue>
# include <set>
# include <sstream>
# include <stack>
# include <string>
# include <vector>
# include <iomanip>
 
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
# define irep(i, n) for (int i = int(n) - 1; i >= 0; i--)
# define FOR(i, m, n) for (int i = int(m); i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
 
int main() {
  int n, i, j, res;
  int ary[100005];
  ary[0] = 0;
  res = 0;
  cin >> n;
  rep(a, n){
  	cin >> ary[a+1];
  }
  
  rep(k, n){
  	i = k+1;
  	j = ary[k+1];
  	if(ary[j]==i){
  		res++;
  	}
  }
  cout << res/2 << endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
typedef long long ll;

const ll mod = 1000000007;

vector<vector<int>> graph;
vector<vector<ll>> memo;

ll dp(int now, int b, int p) {
  if (memo[now][b] != -1) return memo[now][b];
  ll count = 1;
  if (b) {
    for (auto v : graph[now]) {
      if (v == p) continue;
      (count *= dp(v, 0, now)) %= mod;
    }
  } else {
    for (auto v : graph[now]) {
      if (v == p) continue;
      (count *= dp(v, 1, now) + dp(v, 0, now)) %= mod;
    }
  }
  return memo[now][b] = count % mod;
}

int main() {
  int n;
  cin >> n;
  graph.resize(n);
  rep(i, n - 1) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  memo.resize(n);
  rep(i, memo.size()) memo[i].resize(2, -1);
  cout << (dp(0, 0, -1) + dp(0, 1, -1)) % mod << endl;
}

Measured memory_bytes: 19584
N = int(input())
S = list(map(str,input().split()))
count = 0
if "G" in S:
    count+=1
if "W" in S:
    count+=1
if "Y" in S:
    count+=1
if "P" in S:
    count+=1
if count == 3:
    print("Three")
elif count == 4:
    print("Four")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
if(k >=n){
	cout << 0 << endl;
	return 0;
}

else{
	vector<int> h(n);
	int t = n - k;
	long long int ans = 0;
	for(int i =0; i < n; i++){
		cin >> h[i];
	}
		// we have filled the vector h.
		// now, we can kill the biggest ones with k moves which we have.
		// we need to sort the array.
		sort(h.begin(), h.end());
		// now the last k will be direct 0.
		// we only need first t;
		
	   
	   for(int i =0; i < t; i++){
	   	ans += h[i];
	   }
	   
	   cout << ans << endl;
	   return 0;
	}
	
	
}







Measured memory_bytes: 1024
import java.util.Scanner;

class Main {
    static Scanner in = new Scanner(System.in);
    public static void main(String[] args) {
        String[] s = in.nextLine().split(" ");
        System.out.println(s[0].charAt(0) + "" + s[1].charAt(0) + "" + s[2].charAt(0));

    }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, m, n) for (int i = m; i < n; ++i)
const int MOD = 998244353;
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    COMinit();
    int N, A, B;
    ll K;
    cin >> N >> A >> B >> K;
    ll ans = 0;
    rep(i, 0, N+1) {
        if((K - A * i) % B == 0) {
            ll j = (K - A * i) / B;
            if(j >= 0 && j <= N) {
                ans += COM(N, i) * COM(N, j);
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12160