akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr int MOD = 1000000007;
using namespace std;

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; }

VL prime_decomposition(ll n) {
	ll i = 2;
	VL table{};
	while (i * i <= n) {
		while (n % i == 0) {
			n /= i;
			table.emplace_back(i);
		}
		++i;
	}
	if (n > 1) {
		table.emplace_back(n);
		return table;
	}
}

int main() {
	string str;
	cin >> str;
	string a = "YAKI";

	if (str.size() < 4) {
		cout << "No" << endl;
		return 0;
	}
	REP(i, 4) {
		if (str[i] != a[i]) {
			cout << "No" << endl;
			return 0 ;
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = make_multi_list(0, [3, C])
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

print(ans)


Measured memory_bytes: 44508
N = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)

    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)

    return arr

arr = factorization(N)
if N==1:
  arr = []
def solv(c):
    D = (1 - 8*(-c)) ** (1/2)
    x_1 = (-1 + D) / 2
    x_2 = (-1 - D) / 2
    
    return int(max(x_1, x_2))
ans = 0
for i in arr:
  ans += solv(i)

print(ans)

Measured memory_bytes: 9524
from operator import itemgetter
n = int(input())
lis = []
for _ in range(n):
    x,l = map(int,input().split())
    lis.append([x-l,x+l])
lis.sort(key = itemgetter(1))
ans = 0
last = -float("inf")
for i in range(n):
    if lis[i][0] >= last:
        ans += 1
        last = lis[i][1]
print(ans)

Measured memory_bytes: 25572
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define rep(i,n) for(i=0;i<n;i++)
#define PI 3.14159265358979323846264338327950L
  /* 配列の要素を交換する */
void Swap(long int x[ ], int i, int j)
{
    int temp;

    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}
void Qdsort(long int x[ ], int left, int right)
{
    int i, j;
    int pivot;

    i = left;                      /* ソートする配列の一番小さい要素の添字 */
    j = right;                     /* ソートする配列の一番大きい要素の添字 */

    pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */

    while (1) {                    /* 無限ループ */

        while (x[i] > pivot)       /* pivot より小さい値が */
            i++;                   /* 出るまで i を増加させる */

        while (pivot > x[j])       /* pivot より大きい値が */
            j--;                   /*  出るまで j を減少させる */
        if (i >= j)                /* i >= j なら */
            break;                 /* 無限ループから抜ける */

        Swap(x, i, j);             /* x[i] と x[j]を交換 */
        i++;                       /* 次のデータ */
        j--;
    }
    if (left < i - 1)              /* 基準値の左に 2 以上要素があれば */
        Qdsort(x, left, i - 1);     /* 左の配列を Q ソートする */
    if (j + 1 <  right)            /* 基準値の右に 2 以上要素があれば */
        Qdsort(x, j + 1, right);    /* 右の配列を Q ソートする */
}
int main(){
    int n,k,i;
    scanf("%d%d",&n,&k);
    long int h[n],sum=0;
    rep(i,n){
        scanf("%ld",&h[i]);
        sum+=h[i];
    }
    if(n<=k){
        printf("0");
    }else{
        Qdsort(h,0,n-1);
        rep(i,k) sum=sum-h[i];
        printf("%ld",sum);
    }
    return 0;
}

Measured memory_bytes: 3292
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderB
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long m = sc.NextLong();

        List<long>[] from = new List<long>[n + 1];
        Tuple<long, long>[] edge = new Tuple<long, long>[m];

        for (int i = 0; i <= n; i++)
        {
            from[i] = new List<long>();
        }

        for (int i = 0; i < m; i++)
        {
            long a = sc.NextLong();
            long b = sc.NextLong();
            from[a].Add(b);
            from[b].Add(a);
            edge[i] = Tuple.Create(a, b);
        }

        long answer = 0;
        for (int i = 0; i < m; i++)
        {
            var ng1 = edge[i].Item1;
            var ng2 = edge[i].Item2;

            bool[] can = new bool[n + 1];
            can[0] = true;

            Queue<long> que = new Queue<long>();
            que.Enqueue((long)1);
            while (que.Count > 0)
            {
                var point = que.Dequeue();
                if (can[point])
                {
                    continue;
                }
                can[point] = true;

                foreach (var target in from[point])
                {
                    if ((ng1 == point && ng2 == target) || (ng2 == point && ng1 == target))
                    {
                        continue;
                    }
                    que.Enqueue(target);
                }
            }
            if (can.Where(c => !c).Count() > 0)
            {
                answer++;
            }
        }

        Console.Write(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 28200
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    ll X =0;
    ll last = 0;
    for(int i=0;i<N;i++){
        ll diff = A[i]-last;
        if(diff%2==0 ){
            continue;
        }
        X ^= (N-i);
        last =A[i];
    }
    if(X==0){
        cout <<"second"<<endl;
    }else{
        cout <<"first" << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
import math
n=int(input())
r=0
a=[0]*n#2 for ii in range(n)]
for ii in range(n):
  for jj in range(n):
      a[math.gcd(ii+1,jj+1)-1]+=1
"""
for ii in range(n):
    print(a[ii])
"""
for kk in range(n):
  for ll in range(n):
      r+=math.gcd(ll+1,kk+1)*a[ll]
print(r)


Measured memory_bytes: 9132
#include <iostream>
#include <string>
#include <stddef.h>
#include <stack>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>

using namespace std;


int main() {
	string s;
	string p, q;
	int m;
	int h[100];
	while (1) {
		cin >> s >> m;
		for (int i = 0; i < m; i++) {
			cin >> h[i];
		}
		if (s == "-") break;
		for (int i = 0; i < m; i++) {
			p = s.substr(0, h[i]);
			q = s.substr(h[i], s.size()-h[i]);
			s = q + p;
		}
		cout << s << endl;
	}
}

Measured memory_bytes: 1216
#include <stdio.h>

int main(){
	int i,sum,v1,v2;
	int l[10];
	double len,tmp;

	while(scanf("%d,",&l[0]) != EOF){
		sum = l[0];
		for(i = 1;i < 10;i++){
			scanf("%d,",&l[i]);
			sum += l[i];
		}
		scanf("%d,%d",&v1,&v2);

		len = (sum*1.0)/((v1+v2)*1.0)*v1;

		tmp = 0.0;
		for(i = 0;i < 10;i++){
			tmp += (l[i]*1.0);
			if(tmp >= len){
				printf("%d\n",i+1);
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 596
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7; 

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF_INT (1<<30)
#define INF_LL (1ll<<62)

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 a,b,c;

int main(){
    cin>>a>>b>>c;

    if(a+b-c>=0)out("No");
    else if(a*a+b*b+c*c+2*a*b-2*a*c-2*b*c>4*a*b)out("Yes");
    else out("No");

    
}

Measured memory_bytes: 256
s = input()
l = int(s[:2])
r = int(s[2:])
if (l > 12 or l < 1) and (r > 12 or r < 1):
    print("NA")
elif l > 12 or l < 1:
    print("YYMM")
elif r > 12 or r < 1:
    print("MMYY")
else:
    print("AMBIGUOUS")


Measured memory_bytes: 38384
#!/usr/bin/env python3

from itertools import product
import sys
sys.setrecursionlimit(100000)

def get_label(labels, target):
    if labels[target] == -1:
        return target
    else:
        temp = get_label(labels, labels[target])
        labels[target] = temp
        return temp


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [-1] * n
    groups = {}
    for i in range(n):
        groups[i] = 1

    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        label_a = get_label(labels, ai)
        label_b = get_label(labels, bi)
        if label_a != label_b:
            next_val = result[-1]
            next_val -= groups[label_a] * groups[label_b]
            result.append(next_val)
            groups[label_a] += groups[label_b]
            labels[label_b] = label_a
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()


Measured memory_bytes: 34692
#include <iostream>
#include <iomanip>
#include <string>

using namespace std; 
int main(){
    int i=0,j=0;
    int m=1,h=1;
    do{
        cin >> m >> h;
        if(m !=0 && h != 0){
            for ( i = 0; i < m; i++){
                for ( j = 0; j < h; j++){
                    if(i ==0 || i == m-1){
                        cout << "#";
                    }else if(j ==0 || j == h-1){
                        cout << "#";
                    }else{
                        cout << ".";
                    }
                }
                cout << "\n";
            }
            cout << "\n";
        }
    }while(m !=0 && h != 0);
}


Measured memory_bytes: 2996
#include <stdio.h>

using namespace std;

int main()
{
    int n,k,i;
    char s[51];
    scanf("%d %d",&n,&k);
    for(i=1;i<=n+1;i++)
    {
        scanf("%c",&s[i]);
    }
    s[k+1]=s[k+1]+'a'-'A';
    for(i=1;i<=n+1;i++)
    {
        printf("%c",s[i]);
    }

    return 0;
}


Measured memory_bytes: 128
import collections

N = int(input())
list = [''.join(sorted(input())) for i in range(N)]

c = collections.Counter(list)
ans_list = c.most_common()
ans = [ans[1]*(ans[1]-1)//2 for ans in ans_list if not ans[1]==1]
ans_len = len(ans)
if ans_len==0:
    print(0)
else:
    print(sum(ans))

Measured memory_bytes: 24496
x, y, a, b, c = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

pnum, qnum, rnum = 0, 0, 0
ans = 0
time = 0
while time < x+y:
    #P, Q, Rのなかで現状最大の値を取り出す(x,yの値も考慮)
    #P
    if pnum >= x:
        p = 0
    else:
        p = P[pnum]
    #Q
    if qnum >= y:
        q = 0
    else:
        q = Q[qnum]
    #R
    if rnum >=  c:
        r = 0
    else:
        r = R[rnum]
    Option = [p, q, r]

    #今の状況の中でおいしさ最大のものを取り出す
    m = 0
    color = 0
    for i in range(3):
        if m < Option[i]:
            m = Option[i]
            color = i
        else:
            pass
    ans += m

    #選択済みのリンゴを反映
    if color == 0:
        pnum += 1
    elif color == 1:
        qnum += 1
    elif color == 2:
        rnum += 1
    else:   
        print('error')

    #今まで選んだリンゴの数を反映
    time += 1

print(ans)

Measured memory_bytes: 23200
import java.util.*;

public class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        while(true){
            int n = sc.nextInt();
            if(n==0) break;

            int[] d = new int[n];
            int[] a = new int[n];
            for(int i=0; i<n; i++){
                String[] s1 = sc.next().split(":"); 
                String[] s2 = sc.next().split(":");
                String s = s1[0]+s1[1]+s1[2];
                d[i] = Integer.parseInt(s);
                s = s2[0]+s2[1]+s2[2];
                a[i] = Integer.parseInt(s);
            }

            for(int i=0; i<n; i++){
                int min = i;
                for(int j=i; j<n; j++){
                    if(d[min]>d[j]) min = j;
                }
                int tmp = a[min];
                a[min] = a[i];
                a[i] = tmp;
                tmp = d[min];
                d[min] = d[i];
                d[i] = tmp;
            }

            PriorityQueue<Integer> q  = new PriorityQueue<Integer>
                (n,new Comparator<Integer>(){
                    public int compare(Integer a, Integer b){
                        return a-b;
                    }
                });
            q.add(a[0]);
            int cnt = 1;
            for(int i=1; i<n; i++){
                if(q.peek()>d[i]) cnt++;
                else q.poll();
                q.add(a[i]);
            }

            System.out.println(cnt);
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

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

int main() {
    int n, q;
    int a, b, c;
    map<int, int> mp;
    long long sum[100010] = {};

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        mp[a]++;
        sum[0] += a;
    }

    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> b >> c;
        sum[i+1] = sum[i] + (c - b) * mp[b];
        mp[c] += mp[b];
        mp[b] = 0;
    }

    for (int i = 1; i <= q; i++) cout << sum[i] << endl;
}

Measured memory_bytes: 8796
import sys


N, M, X = map(int, input().split())
A = [None] * N
C = [None] * N
for i, s in enumerate(sys.stdin.readlines()):
    C[i], *A[i] = map(int, s.split())

ans = 10 ** 8
for i in range(1 << N):
    k = 0
    v = 0
    S = [0] * M
    while (i >> k) > 0:
        if (i >> k) & 1:
            for j in range(M):
                S[j] += A[k][j]
            v += C[k]
        k += 1

    if all(a >= X for a in S):
        ans = min(ans, v)
        

if ans < 10 ** 8:
    print(ans)
else:
    print(-1)


Measured memory_bytes: 9224
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
using namespace std;
typedef long long int ll;

void chmin(ll &a, ll b){
  if (a > b) a = b;
}
ll INF = 1LL << 60;
ll dp[100010]; //DPテーブル
int h[100010];

ll rec(int N){
  
  ll res = INF;
  //ベースケース
  if (N == 0){
    return 0;
  }

  //計算済みであればその値を返す
  if (dp[N] < INF){
    return dp[N];
  }

  //i+1の場合
  chmin(res, rec(N-1) + abs(h[N] - h[N-1]));
  //i+2の場合(Nが1以下の時はオーバーフローするので呼ばない)
  if(N > 1) chmin(res, rec(N-2) + abs(h[N] - h[N-2]));
  

  return dp[N] = res; //DPテーブルに記録しながらリターン
}


int main(){
  int N; cin >> N;
  
  for (int i = 0; i < N; i++){
    cin >> h[i];
  }
  
  for (int i = 0; i < 100010; i++){
    dp[i] = INF;
  }  
  
  cout << rec(N-1);
  return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
const ll p = 1e9 + 7;
//const ll p = 998244353;
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

vll factorial(2e5, 1);
void make_table() {
	for (ll i = 2; i <= 2e5; i++) {
		factorial[i] = factorial[i - 1] * i % p;
	}
}

//モジュラ逆数
long long modinv(long long n, long long p) {
	long long a = p, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= p;
	if (u < 0) u += p;
	return u;
}

struct rerooting {
	ll n; //頂点数
	vector<vll> nx; //隣接リスト
	unordered_map<ll, unordered_map<ll, ll>> dp1; //有向辺 i -> j で表される部分木における場合の数
	unordered_map<ll, unordered_map<ll, ll>> dp2; //有向辺 i -> j で表される部分木の頂点数
	vll dp3; //頂点 i を根としたときの求める場合の数

	//コンストラクタ
	rerooting(ll m, vector<vll> &v) {
		n = m;
		nx = v;
		dp3.resize(n, 0);
	}

	void calc_sub(ll a, ll b) {
		if (dp1[a][b] > 0 && dp2[a][b] > 0) return;
		if (nx[b].size() == 1) {
			dp1[a][b] = 1;
			dp2[a][b] = 1;
			return;
		}
		if (dp3[b] > 0) {
			dp2[a][b] = n - dp2[b][a];
			ll x = dp3[b];
			x *= modinv(dp1[b][a], p);
			x %= p;
			x *= factorial[dp2[b][a]];
			x %= p;
			x *= modinv(factorial[n - 1], p) * factorial[n - 1 - dp2[b][a]] % p;
			x %= p;
			dp1[a][b] = x;
		}
		else {
			ll x = 1, sum = 0;
			for (ll i = 0; i < nx[b].size(); i++) {
				if (nx[b][i] == a) continue;
				calc_sub(b, nx[b][i]);
				x *= dp1[b][nx[b][i]];
				x %= p;
				x *= modinv(factorial[dp2[b][nx[b][i]]], p);
				x %= p;
				sum += dp2[b][nx[b][i]];
			}
			x *= factorial[sum];
			x %= p;
			dp1[a][b] = x;
			dp2[a][b] = sum + 1;
		}
	}

	void calc(ll a) {
		ll ret = factorial[n - 1], sum = 0;
		for (ll i = 0; i < nx[a].size(); i++) {
			calc_sub(a, nx[a][i]);
			ret *= dp1[a][nx[a][i]];
			ret %= p;
			ret *= modinv(factorial[dp2[a][nx[a][i]]], p);
			ret %= p;
		}
		dp3[a] = ret;
		return;
	}

	void bfs() {
		queue<ll> task;
		vector<bool> seen(n, false);
		task.push(0);
		seen[0] = true;
		while (task.size()) {
			calc(task.front());
			for (ll i = 0; i < nx[task.front()].size(); i++) {
				if (!seen[nx[task.front()][i]]) {
					task.push(nx[task.front()][i]);
					seen[nx[task.front()][i]] = true;
				}
			}
			task.pop();
		}
	}
};

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

	ll n;
	cin >> n;
	vector<vll> nx(n, vll(0));
	for (ll i = 0; i < n - 1; i++) {
		ll a, b;
		cin >> a >> b;
		nx[a - 1].push_back(b - 1);
		nx[b - 1].push_back(a - 1);
	}

	make_table();

	rerooting rr(n, nx);
	rr.bfs();
	for (ll i = 0; i < n; i++) {
		cout << rr.dp3[i] << endl;
	}
}


Measured memory_bytes: 107248
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define _GLIBCXX_DEBAC
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

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

int sort_greater(int m,int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(),greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
		return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t,sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;
struct mint {
	ll x;
	mint(ll x = 0):x(x%mod){}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		res -= a;
	}
	mint operator*(const mint a)const {
		mint res(*this);
		return res *= a;
	}
};

map<string, int> memo;

using P=pair<int, int>;

struct Clock {
	int hour, minute, second;
	void set(int h, int m, int s) {
		hour = h; minute = m; second = s;
	}
	string to_str() {
		string h, m, s;
		h = to_string(hour);
		m= to_string(minute);
		s= to_string(second);
		if (h.size() < 2) h = "0" + h;
		if (m.size() < 2) m = "0" + m;
		if (s.size() < 2) s = "0" + s;
		return h + ":" + m + ":" + s;
	}
	void shift(int diff_second) {
		int h, m;
		h = diff_second / 3600;
		m = diff_second / 60;
		diff_second %= 60;
		second += diff_second;
		
	}
};


/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
int main() {
	int s;
	cin >> s;
	int a, b;
	a = s / 100; b = s % 100;
	if (1 <= a && a <= 12) {
		if (1 <= b && b <= 12) cout << "AMBIGUOUS";
		else cout << "MMYY";
	}
	else {
		if (1 <= b && b <= 12)cout << "YYMM";
		else cout << "NA";
	}
	
	return 0;
}










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

int main(){

	int N, M;
	cin >> N;
	string s[110], t[110];
	for(int i = 0; i < N; i++)
	{
		cin >> s[i];
	}
	cin >> M;
	for(int i = 0; i < M; i++)
	{
		cin >> t[i];
	}
	int ans = 0;
	for(int i = 0; i < N; i++)
	{	
		int score = 0;
		for(int j = 0; j < N; j++)
		{
			if(s[i] == s[j]) score++;
		}
		for(int j = 0; j < M; j++)
		{
			if(s[i] == t[j]) score--;
		}
		ans = max(ans, score);
	}

	cout << ans << endl;
	
	
}

Measured memory_bytes: 256
import math

def solve(x,k,d):
	x = abs(x)
	if x >= k*d:
		return x-k*d
	else:
		n = x//d
		x -= n*d
		k -= n
		if k%2==0: return x
		else: return abs(x-d)

x,k,d=map(int,input().split())
print(solve(x,k,d))


Measured memory_bytes: 9176
#include <stdio.h>

int main(int argc, char const *argv[])
{
    float a,b,t;

    scanf("%f %f %f", &a, &b, &t);

    t += 0.5;
    t /= a;
    int m = (int)t;
    printf("%d", (int)b * m );

    return 0;
}

Measured memory_bytes: 256
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int q = in.nextInt();
		String s = in.next();
		
		TreeMap<Integer, Integer> ml = new TreeMap<>();
		//TreeMap<Integer, Integer> mr = new TreeMap<>();
		//int[] a = new int[q];
		int idx = 0;
		int d = 0;
		while (true) {
			idx = s.indexOf("AC", idx);
			if (idx == -1) {
				break;
			}
			ml.put(idx, ++d);
			idx++;
		}

		for (int i = 0; i < q; i++) {
//			System.out.println("----");
//			System.out.println(i);
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			int c = d;
//			System.out.println(c);
			if (l != 0) {
				Entry<Integer, Integer> lower = ml.lowerEntry(l);
				if (lower != null) {
//					System.out.println("L " + lower.getValue());
					c -= lower.getValue();
				}
			}
			if (r != n) {
				Entry<Integer, Integer> ceil = ml.ceilingEntry(r);
				if (ceil != null) {
//					System.out.println("R " + ceil.getValue());
//					System.out.println("R' " + (d - ceil.getValue() + 1));
					c -= (d - ceil.getValue() + 1);
				}
			}
			System.out.println(c);
		}
	}

}


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

template<class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[";
  for (int i = 0; i < (int) V.size(); i++) {
    if (i > 0) {
      cout << ", ";
    }
    cout << V[i];
  }
  return os << "]\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<pair<int, int>> vec(n);
  for (int j = 0; j < n; j++) {
    cin >> vec[j].first;
    vec[j].second = j;
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < n; i++) {
    if (vec[n - 1].second == i) {
      cout << vec[n - 2].first << '\n';
    } else cout << vec[n - 1].first << '\n';
  }
  return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define X first
#define Y second

using namespace std;

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

int valid[256];
int cnt[256];
int kind;

void add(char c){
	if (!valid[c]) return;
	if (cnt[c]++) return;
	++kind;
}

void sub(char c){
	if (!valid[c]) return;
	if (--cnt[c]) return;
	--kind;
}

int main(){
	string str, key;
	while (1){
		str.clear();
		key.clear();

		while (true){
			getline(cin, key);
			if (key.empty() || !cin) break;
			str += key;
		}
		if (str.empty() || !cin) break;

		getline(cin, key);
		cin.ignore();

		//cout << str << endl;
		//cout << key << endl;
		MEMSET(cnt, 0);
		MEMSET(valid, 0);
		kind = 0;
		for (auto &c : key) valid[c] = 1;
		int n = str.size(), m = key.size();

		int l = 0, r = 0;
		int ans = n + 1;
		int anscnt = 0;
		P p;
		while (1){
			while (kind < m && r < n){
				add(str[r++]);
			}
			if (kind == m){
				if (r - l < ans){
					ans = r - l;
					p = make_pair(l, r);
					anscnt = 1;
				}
				else if (r - l == ans){
					++anscnt;
				}
			}
			if (l >= r) break;
			sub(str[l++]);
		}

		cout << anscnt << endl;
		int chr = 0;
		if (anscnt){
			cout << endl;
			for (int i = p.first; i < p.second; ++i){
				cout << str[i];
				++chr;
				if (chr % 72 == 0) cout << endl;
			}
			if (chr % 72) cout << endl;
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1692
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin>>s;
  int counter=10000;
  long long n=stoll(s);
  deque<int>a;
  while(n>0){
  a.push_front(n%10);
  n=n/10;}
  for(int i=0;i<a.size()-2;i++){
  counter=min(counter,abs(a.at(i)*100+a.at(i+1)*10+a.at(i+2)-753));
  }
  cout<<counter<<endl;}
  

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

#define fastio                  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define input_output            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 

#define ll                      long long
#define read1(x)                 cin>>x
#define read2(x,y)               cin>>x>>y
#define print(x)                cout<<x<<endl
#define pii                     pair<int, int>
#define pli                     pair<ll, int>
#define pil                     pair<int, ll>
#define pll                     pair<ll, ll>
#define vi                      vector<int>
#define vll                     vector<ll>
#define vb                      vector<bool>
#define vd                      vector<double>
#define vs                      vector<string>
#define ff                      first
#define ss                      second
#define pb                      push_back
#define ppb                     pop_back
#define pf                      push_front
#define ppf                     pop_front
#define vpii                    vector<pii>
#define umap                    unordered_map
#define uset                    unordered_set
#define clr(a,b)                memset(a,b,sizeof a)
#define all(ds)                 ds.begin(), ds.end()
#define rev(ds)                 ds.rbegin(), ds.rend()
#define asc(A)                  sort(A.begin(), A.end())
#define dsc(A)                  sort(A.begin(), A.end(), greater<int>())
#define gcd(x,y)                __gcd(x,y)
#define clr(a,b)                memset(a,b,sizeof a)
#define fr(i, n)                for(int i=0; i<n;++i)
#define fr1(i, n)               for(int i=1; i<=n; ++i)
#define rfr(i, n)               for(int i=n-1; i>=0; --i)
#define printVector(v)          for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define precise(x)              cout<<fixed<<setprecision(x)
#define inf                     10000000000000

 

ll lcm(ll a, ll b) {return (a*b)/__gcd(a, b); }
ll power(ll x, ll y, ll m) { if(!y) return 1; ll p=power(x, y>>1, m)%m; p=p*p%m; return (y&1)?(x*p)%m:p;}
ll modInverse(ll a, ll m){ return power(a, m-2, m); }
bool isPrime(ll num){bool flag=true;for(ll i =2;i<=num/2;i++){if(num%i==0) {flag=false; break;} }return flag;}
ll sumofdigits(ll n){ll c=0;while(n>0){c++;n/=10;}return c;}
bool sortinrev(const pair<int,int>&a,const pair<int,int>&b) {return a.first > b.first; }
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {return a.second < b.second; }

//const double PI= 2*acos(0.0);
const long long MOD= 1000000007;



void solve(){
    int n; ll d;
    cin>>n>>d;
    vector<pair<ll, ll>>v(n);
    int count = 0;
    fr(i,n){
        ll x, y; cin>>x>>y;
        v[i].first = x;
        v[i].second = y;
        if(x*x + y*y <= d*d)count++; 
    }
    print(count);

}
int main()
{
#ifndef ONLINE_JUDGE  
    input_output  
#else   
    fastio
#endif

    int t =1 ;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

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

int main() {
  int N, K;

  cin >> N >> K;

  int result = 0;
  for (int i = 0; i < N; i++) {
    int x;

    cin >> x;

    int diffKx = K - x;

    if (diffKx < 0) {
      diffKx *= -1;
    }

    if (x < diffKx) {
      result += x * 2;
    } else {
      result += diffKx * 2;
    }
  }

  cout << result << endl;
}


Measured memory_bytes: 3596
#include <stdio.h>

int main()
{
    int n, m, A[100][100], B[100], C[100];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &A[i][j]);
        }
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &B[i]);
    }
    for (int i = 0; i < n; i++)
    {
        C[i] = 0;
        for (int j = 0; j < m; j++)
        {
            C[i] = C[i] + A[i][j] * B[j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", C[i]);
    }

    return 0;
}


Measured memory_bytes: 2112
#include <stdio.h>

int main(){
  int n,i;
  int t,x,y,flag=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d %d",&t,&x,&y);
    
    if(t%2!=(x+y)%2){
      flag=1;
    } else if((x+y)>t){
      flag=1;
    }
  }
  if(flag==1){
    printf("No");
  } else {
    printf("Yes");
  }
}

Measured memory_bytes: 128
nks = input().split(' ');
n = int(nks[0]);
k = int(nks[1]);
s = int(nks[2]);



for i in range(k) :
	if n - k == 0 and i== k-1 :
		print(s);
	else :
		print(s,'',end='');
for i in range(n-k) :
	nokori = 0;
	if s <= 2 :
		nokori = s+1;
	else :
		nokori = s-1;
	if i == n-k-1 :
		print(nokori);
	else :
		print(nokori,'',end='');

Measured memory_bytes: 4592
#include<iostream>

using namespace std;

int main(){
  int Y1000;
  int Y5000;
  int Y10000;
  int x,y,z;
  int N;
  int Y;
  bool flag = false;
  cin >> N >> Y;
  
  int i,j,k;
  for(i=0;i<=N;i++){
    Y1000 = 1000*i;
    for(j=0;j<=N-i;j++){
		Y5000 = 5000*j;
      for(k=0;k<=N-i-j;k++){
           Y10000 = 10000*k;
          if( (Y1000+Y5000+Y10000)==Y && i+j+k==N){
            flag = true;
            x=k;
            y=j;
            z=i;
    	   }
      }
    }
  }
  
  if(flag) cout <<x<<" "<<y<<" "<<z<<endl;
  else	cout << "-1" <<" "<< "-1" <<" "<< "-1" << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define print(x) cout << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T> >
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vl A(x), B(y), C(z);

  rep(i, x) cin >> A[i];
  rep(i, y) cin >> B[i];
  rep(i, z) cin >> C[i];
  sort(rng(A),greater<ll>());
  sort(rng(B),greater<ll>());
  sort(rng(C),greater<ll>());
  vl ans;
  rep(i,x)rep(j,y)rep(l,z){
    if((i+1)*(j+1)*(l+1)>k) break;
    else ans.push_back(A[i]+B[j]+C[l]);
  }
  sort(rng(ans),greater<ll>());
  rep(i,k){
    print(ans[i]);
  }
  return 0;
}

Measured memory_bytes: 1404
// be name khoda
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e9 + 10;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,a[4];
    a[0]=a[1]=a[2]=a[3]=0;
    string x;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>x;
        if (x.compare("AC")==0) a[0]++;
        else if (x.compare("WA")==0) a[1]++;
        else if (x.compare("TLE")==0) a[2]++;
        else a[3]++;
    }
    cout << "AC x "<<a[0]<<endl;
    cout << "WA x "<<a[1]<<endl;
    cout << "TLE x " << a[2] << endl;
    cout << "RE x " << a[3] << endl;
    return 0;
}

Measured memory_bytes: 3668
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 200001;
int n, m;
vector<int> G[MAX_N]; //隣接リスト;
bool used[MAX_N]; //訪問済みかどうか

int dfs(int v) {
  used[v] = true;
  int sum = 1;
  for (int i = 0; i < G[v].size(); i++) {
    if (!used[G[v][i]]) {
      sum += dfs(G[v][i]);
    }
  }
  return sum;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    //辺を張る
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  // 全てを点を試す
  int ans = 0;
  int res = 0;
  for (int i = 0; i < n; i++) {
    res = dfs(i);
    ans = max(ans, res);
  }
  
  cout << ans;
}

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

int main() {
  int n, d, x;
  std::cin >> n >> d >> x;
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    sum += 1;
    for (int j = 1 + a; j <= d; j += a)
      ++sum;
  }

  std::cout << sum + x << std::endl;
}


Measured memory_bytes: 3144
n = int(input())
p = input().split()
c = 0
for i in range(n-2):
    if int(p[i]) < int(p[i+1]) < int(p[i+2]):
        c += 1
    elif int(p[i]) > int(p[i+1]) > int(p[i+2]):
        c += 1
        
print(c)

Measured memory_bytes: 3064
let () =
  Scanf.scanf "%d %d" @@ fun n m ->
  let uf = Array.make (n+1) (-1) in
  let rec find x =
    if uf.(x) < 0 then x else begin
      let x' = find uf.(x) in
      uf.(x) <- x'; x'
    end in
  let unite x y =
    let x, y = find x, find y in
    if x <> y then begin
      if uf.(x) < uf.(y) then (
        uf.(x) <- uf.(x) + uf.(y); uf.(y) <- x
      ) else (
        uf.(y) <- uf.(x) + uf.(y); uf.(x) <- y)
    end in
  let same x y = find x = find y in

  let p = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  for _ = 1 to m do Scanf.scanf " %d %d" unite done;

  Array.init n (fun i -> if same (i+1) p.(i) then 1 else 0)
  |> Array.fold_left (+) 0 |> Printf.printf "%d\n"

Measured memory_bytes: 6272
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int N,A,B;
	String S;
	public void solve() {
		N = nextInt();
		A = nextInt();
		B = nextInt();

		S = next();
		char[] c = S.toCharArray();
		int a = 0;
		int b = 1;
		for(int i = 0;i < N;i++){
			if(c[i] == 'a'){
				if(a < A + B){
					out.println("Yes");
					a++;
				}else{
					out.println("No");
				}
			}else if(c[i] == 'b'){
				if(a < A + B && b <= B){
					out.println("Yes");
					a++;
					b++;
				}else{
					out.println("No");
				}
			}else{
				out.println("No");
			}
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 12036
package main

import (
	"fmt"
)

func main() {

	n := int(0)
	fmt.Scan(&n)
	x := make([]int64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&x[i])
	}

	exec(n, x)

	// exec(2, []int64{1, 4})
	// exec(7, []int64{14, 14, 2, 13, 56, 2, 37})

}

func exec(n int, x []int64) {
	min := int64(0)
	minIndex := 0

	sum := int64(0)
	max := int64(0)
	for _, v := range x {
		sum += v
		if max < v {
			max = v
		}
	}

	// fmt.Println(x, sum)

	for i := 1; i <= int(max); i++ {
		cur := int64(n*i*i) - 2*sum*int64(i)
		if i == 1 || min > cur {
			min = cur
			minIndex = i
		}
	}

	result := int64(0)
	p := int64(minIndex)
	for _, v := range x {
		result = result + (v-p)*(v-p)
	}
	fmt.Println(result)

}


Measured memory_bytes: 512
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <iostream>

using namespace std;
typedef long long ll;
const ll MD = 1e9+7;
ll dp[220][11000];
bool used[220][11000] = {};
int n, w;
int d[220];

ll solve(int i, int u) {
	if (u < 0) return 0;
	if (u == 0) return 1;
	if (i >= n) return 0;
	if (used[i][u]) return dp[i][u];
	used[i][u] = true;
	ll r = solve(i+1, u) + solve(i+1, u-d[i]);
	r %= MD;
	dp[i][u] = r;
	return r;
}

int main() {
	cin >> n >> w;
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	sort(d, d+n);
	ll r = 0;
	for (int i = w; i >= 0; i--) {
		int u = i;
		int j = 0;
		for (j = 0; j < n; j++) {
			if (d[j] <= (w-i)) {
				u -= d[j];
			} else {
				break;
			}
		}
		r += solve(j, u);
		r %= MD;
	}
	cout << r << endl;
}

Measured memory_bytes: 21632
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define c2(n,m) cin>>n>>m
#define c3(n,m,k) cin>>n>>m>>k
#define co(n) cout<<n<<endl
using namespace std;

int main(){
  int a, b, c, d;
  c3(a,b,c); c(d);
  int x=0;
  bool ali=false, bob=false;
  rep(i,0,101){
    if(i==a) ali=true;
    if(i==b) ali=false;
    if(i==c) bob=true;
    if(i==d) bob=false;
    if(ali==true && bob==true) x++;
  }
  co(x);
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;
 
// 入力
int N, M;
vector<vector<int> > G; // グラフ
vector<int> deg; // 各頂点の入次数
 
int dp[100100];
int main() {
    // 入力受け取り, 入次数も管理する
    cin >> N >> M;
    G.assign(N, vector<int>());
    deg.assign(N, 0);
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        --x, --y; // 0-indexed にする
        G[x].push_back(y);
        deg[y]++;
    }
 
    // source をキューに突っ込む
    queue<int> que;
    for (int v = 0; v < N; ++v) if (deg[v] == 0) que.push(v);
 
    // BFS
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            dp[nv] = dp[v] + 1;
            deg[nv]--; // エッジ (v, nv) を破壊する
            if (deg[nv] == 0) {
                que.push(nv); // それによって入次数が 0 にあったならキューに突っ込む
            }
        }
    }
 
    // 答え
    int res = 0;
    for (int v = 0; v < N; ++v) chmax(res, dp[v]);
    cout << res << endl;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
multiset<int> s;
vector<int> a,b;
int n,x;
int main(){
	cin>>n;
	for (int i=0;i<(1<<n);i++){cin>>x;s.insert(x);}
	auto no=s.end();no--;
	a.pb(*no);s.erase(no);
	for (int i=1;i<=n;i++){
		for (auto j:a){
			auto k=s.lower_bound(j);
			if (k==s.begin()){puts("No");return 0;}
			k--;b.pb(*k);s.erase(k);
		}
		for (auto j:b)a.pb(j);b.clear();
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 13816
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;



ll power(ll a, ll b) {
    ll ans = 1;
    ll t = a;
    while (b) {
        if (b % 2) {
            ans = (ans * t) % 998244353;
        }

        t = (t * t) % 998244353;
        b /= 2;
    }

    return ans;
}



int main() {
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    int n;
    string s;
    cin >> n >> s;
    if (n % 2) {
        cout << "No";
        return 0;
    }
    
    
    n = n / 2;
    for (int i = 0; i < n; i++) {
        if (s[i] != s[i + n]) {
            cout << "No";
            return 0;
        }
    }
    
    cout << "Yes";

}


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

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

using namespace std;
string s;

int solve() {
    string t;
    REP(i, s.size()) {
        if (s[i] != 'x') {
            t += s[i];
        }
    }

    int l = 0;
    int r = t.size() - 1;
    while (r - l >= 1) {
        if (t[l] != t[r]) {
            return -1;
        }
        l++;
        r--;
    }

    int ans = 0;
    l = 0;
    r = s.size() - 1;
    while (r - l >= 1) {
        if (s[l] == 'x' && s[r] != 'x') {
            l++;
            ans++;
        } else if (s[l] != 'x' && s[r] == 'x') {
            r--;
            ans++;
        } else {
            l++;
            r--;
        }
    }
    return ans;
}

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

    cin >> s;
    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 592
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N, M, Q;
int A[100011];
int cnt[100011];
int rnk[100011];
int len[100011];
VI ord;

void MAIN() {
    scanf("%d%d%d", &N, &M, &Q);
    REP (i, Q) scanf("%d", A+i), A[i]--;;

    for (int i=Q; i--;) {
	int v = A[i];
	if (cnt[v] == 0) {
	    rnk[v] = ord.size();
	    ord.push_back(v);
	    len[0]++;
	    cnt[v]++; 
	} else if (cnt[v] < N && len[cnt[v]] == rnk[v]) {
	    len[cnt[v]]++;
	    cnt[v]++; 
	}
    }

    REP (i, M) if (cnt[i] == 0) ord.push_back(i);
    bool yes = true;
    for (int i=len[N-1]; i<M-1; i++) if (ord[i] > ord[i+1]) yes = false;
    puts(yes? "Yes": "No");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 2044
using DataStructures
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function cutN(A,L)
  N = length(A)
  c = 0
  for i in 1:N
    c += A[i]÷L
    if A[i]%L == 0
      c -= 1
    end
  end
  return c
end

function main()
  N,K = readint()
  A = readint()

  LB = 0
  for i in 1:N
    if LB < A[i]
      LB = A[i]
    end
  end
  LA = 1
  #LB = 10^9
  KA = cutN(A,LA)
  KB = cutN(A,LB)

  if K==0
    println(LB)
    return
  elseif KA <= K
    println(1)
    return
  end

  while true
    if LA + 1 >= LB
      println(LB)
      return
    end
  LC = (LA + LB)÷2
  KC = cutN(A,LC)
  if cutN(A,LC) <= K < cutN(A,LC-1)
    println(LC)
    return
  end

  if cutN(A,LC-1) <= K
    LB = LC
  else
    LA = LC
  end

  #println(KA," ", KB," ", KC)
end  



end

main()

Measured memory_bytes: 209560