akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

string s;
int i;
int P, Q, R;

int formula() {
  if (s[i] == '(') {
    i++;
    int A = formula();
    char op = s[i++];
    int B = formula();
    int tmp;
    if (op == '*') {
      if (A == 0 || B == 0) tmp = 0;
      else if (A == 1 || B == 1) tmp = 1;
      else tmp = 2;
    } else {
      if (A == 2 || B == 2) tmp = 2;
      else if (A == 1 || B == 1) tmp = 1;
      else tmp = 0;
    }
    i++;
    return tmp;
  } else if (s[i] == '-') {
    i++;
    int tmp = formula();
    if (tmp == 0) return 2;
    if (tmp == 1) return 1;
    if (tmp == 2) return 0;
  } else {
    char ch = s[i];
    i++;
    if (ch == 'P') return P;
    if (ch == 'Q') return Q;
    if (ch == 'R') return R;
    return ch - '0';
  }
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> s, s != ".") {
    int ans = 0;
    for (P = 0; P <= 2; P++) {
      for (Q = 0; Q <= 2; Q++) {
        for (R = 0; R <= 2; R++) {
          i = 0;
          int tmp = formula();
          ans += tmp == 2;
        }
      }
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 3004
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <queue>

using namespace std;

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;

ll pow_mod(ll a, ll d, ll p){
    if(d == 0) return 1;
    if(d % 2){
        return a * pow_mod(a, d - 1, p) % p;
    }
    return pow_mod(a * a % p, d / 2, p);
}


int main(){
    ll H, W, A, B;
    ll p = 1e9+7;

    cin >> H >> W >> A >> B;
    vector<ll> fs(H + W + 1, 1);

    for(int i = 0; i < fs.size() - 1; i ++){
        fs[i + 1] = (i + 1) * fs[i] % p;
    }

    ll ans = 0;

    for(int i = B + 1; i <= W; i ++){
        ll up = fs[H - A + i - 2] * pow_mod(fs[H - A - 1], p - 2, p) % p;
        up = (up * pow_mod(fs[i - 1], p - 2, p)) % p;

        ll down = fs[A - 1 +  W - i] * pow_mod(fs[A - 1], p - 2, p) % p;
        down = (down * pow_mod(fs[W - i], p - 2, p)) % p;

        ans = (ans + up * down) % p;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<iostream>

using namespace std;
 
int main(){
	int n, a, b;
	bool p = true;
	
	cin >> n;
	
	cin >> a;
	for(int i = 1; i < n; i++){
		cin >> b;
		if(a > b) p = false;
		if(a < b) b--;
		a = b;
	}
	
	if(p) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/ruby
N,X=gets.split.map &:to_i
a=N.times.map{gets.split.map &:to_i}
r=Float::INFINITY
(1<<N).times{|i|
	s=X
	r0=0
	N.times{|j|
		if i[j]>0
			r0+=a[j][0]
			s-=a[j][0]*100*-~j+a[j][1]
		end
	}
	(N-1).downto(0){|j|
		if i[j]==0&&s>0
			k=100*-~j
			n=[(s+k-1)/k,a[j][0]].min
			r0+=n
			s-=n*k
		end
	}
	r=[r,r0].min
}
p r

Measured memory_bytes: 1788
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

def comb(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1)
		q = q * i
	return p // q

def binsearch(l, r, f):
	while r - l > 1:
		c = (r + l) // 2
		if f(c):
			r = c
		else:
			l = c
	return r

N, K = rl()
A = rl()

pos = 0
neg = 0
zero = 0
Ap = []
An = []
for a in A:
	if a > 0:
		pos += 1
		Ap.append(a)
	elif a < 0:
		neg += 1
		An.append(a)
	else:
		zero += 1
Ap.sort()
An.sort()
n_pos = comb(pos, 2) + comb(neg, 2)
n_neg = pos * neg
n_zero = zero*(N-zero) + comb(zero, 2)

def num_gt(A, x):
	j = len(A) - 1
	cnt = 0
	for i in range(len(A)):
		while i < j and A[i] * A[j] > x:
			j -= 1
		if i >= j:
			break
		cnt += max(j - i, 0)
	return cnt

def num_gt2(A, B, x):
	j = len(B) - 1
	cnt = 0
	for i in reversed(range(len(A))):
		while j >= 0 and A[i] * B[j] > x:
			j -= 1
		if j < 0:
			break
		cnt += max(j+1, 0)
	return cnt

def check_plus(x):
	cnt = n_neg + n_zero
	cnt += num_gt(Ap, x)
	cnt += num_gt(list(reversed(An)), x)
	return cnt >= K

def check_minus(x):
	cnt = num_gt2(Ap, An, x)
	return cnt >= K

ans = 0
if K <= n_neg:
	l = An[0] * Ap[-1] - 1
	r = 0
	ans = binsearch(l, r, check_minus)
elif K <= n_neg + n_zero:
	ans = 0
else:
	l = 0
	r = 1
	if len(Ap) >= 2:
		r = max(r, Ap[-1] * Ap[-2]) + 1
	if len(An) >= 2:
		r = max(r, An[0] * An[1]) + 1
	ans = binsearch(l, r, check_plus)
print(ans)

Measured memory_bytes: 119172
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 頂点数・距離２の個数 - 取得
	int liVCnt, liL2Cnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &liVCnt, &liL2Cnt);

	// 最大数
	int liMax = (liVCnt - 1) * (liVCnt - 2) / 2;

	// 追加数
	int liACnt = liMax - liL2Cnt;

	// 辺数
	int liECnt = liVCnt - 1 + liACnt;

	// 存在しない
	if (liACnt < 0) {
		liVCnt = -1;
		liECnt = -1;
	}

	// １行出力 - 辺数
	sprintf(lc1Buf, "%d\n", liECnt);
	fOutLine(lc1Buf);

	// １行出力 - 辺
	for (i = 0; i < liVCnt - 1; i++) {
		sprintf(lc1Buf, "1 %d\n", i + 2);
		fOutLine(lc1Buf);
	}
	
	// １行出力 - 追加辺
	int liSNo = 2;
	int liENo = 3;
	for (i = 0; i < liACnt; i++) {
		sprintf(lc1Buf, "%d %d\n", liSNo, liENo);
		fOutLine(lc1Buf);

		// 次の辺
		if (liENo < liVCnt) {
			liENo++;
		}
		else {
			liSNo++;
			liENo = liSNo + 1;
		}
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n;
    scanf("%d",&n);
    long int t=0;
    long int s=0;
    long int x[200000]={};
    long int y[200000]={};
    int xmax=0;
    int xmin=0;
    int ymax=0;
    int ymin=0;
    long int ans=0;
    for(int i=0;i<n;i++){
        scanf("%ld %ld",&t,&s);
        x[i]=t+s;
        y[i]=t-s;
        //printf("%ld %ld\n",x[i],y[i]);
        
        if(!i){
            xmax=i;
            xmin=i;
        }else if(x[i]>x[xmax]){
            xmax=i;
        }else if(x[i]<x[xmin]){
            xmin=i;
        }
        if(!i){
            ymax=i;
            ymin=i;
        }else if(y[i]>y[ymax]){
            ymax=i;
        }else if(y[i]<y[ymin]){
            ymin=i;
        }
    }
    
    //printf("%ld %ld %ld %ld\n",x[xmax],x[xmin],y[ymax],y[ymin]);
    
    for(int i=0;i<n;i++){
        //printf(";%ld\n",(abs(x[i]-x[xmax])>=abs(y[i]-y[xmax])?abs(x[i]-x[xmax]):abs(y[i]-y[xmax])));
                                                                                                  //(abs(x[i]-x[xmax])>=abs(y[i]-y[xmax])?abs(x[i]-x[xmax]):abs(y[i]-y[xmax]))
        if(ans < (abs(x[i]-x[xmax])>=abs(y[i]-y[xmax])?abs(x[i]-x[xmax]):abs(y[i]-y[xmax]))  )ans=(abs(x[i]-x[xmax])>=abs(y[i]-y[xmax])?abs(x[i]-x[xmax]):abs(y[i]-y[xmax]));
        if(ans < (abs(x[i]-x[xmin])>=abs(y[i]-y[xmin])?abs(x[i]-x[xmin]):abs(y[i]-y[xmin]))  )ans=(abs(x[i]-x[xmin])>=abs(y[i]-y[xmin])?abs(x[i]-x[xmin]):abs(y[i]-y[xmin]));
        if(ans < (abs(x[i]-x[ymax])>=abs(y[i]-y[ymax])?abs(x[i]-x[ymax]):abs(y[i]-y[ymax]))  )ans=(abs(x[i]-x[ymax])>=abs(y[i]-y[ymax])?abs(x[i]-x[ymax]):abs(y[i]-y[ymax]));
        if(ans < (abs(x[i]-x[ymin])>=abs(y[i]-y[ymin])?abs(x[i]-x[ymin]):abs(y[i]-y[ymin]))  )ans=(abs(x[i]-x[ymin])>=abs(y[i]-y[ymin])?abs(x[i]-x[ymin]):abs(y[i]-y[ymin]));
    
        
    }
   printf("%ld\n",ans);
    
}

Measured memory_bytes: 4852
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <math.h>
#include <iomanip>

using namespace std;

//void C_159()
int main()
{
  int L;
  cin >> L;

  long double volume = (long double)((float)L / 3.0 )*  ((float)L / 3.0) * ((float)L / 3.0);

  cout << setprecision(12) <<volume << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip>

using namespace std;

template <class T> using V = vector<T>;

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

const long long INF = 1LL << 60;

using ll = long long;
using db = long double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
using graph = V<V<int>>;
using pq = priority_queue<ll>;



#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define pb(a) push_back(a);




ll Sum(ll n) {
ll m=0;
  while(n){
    m+=n%10;
    n/=10;
  }
  return m;
}



const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    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;
    }
}


#define comuse Comuse()

ll combi(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;
}

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


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


vll div(ll n){
  vll ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      ret.push_back(i);
      if(i*i!=n){
        ret.push_back(n/i);
      }
    }
  }
  SORT(ret);
  return (ret);
}


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

    a=a*a%mod;
    
    n>>=1;
  }

  return ans;
}

void Solve();


const int MAX_N = 131072;
//segment tree 
int NN;
int seg[MAX_N*2-1];
void seguse(){
  for(int i=0;i<2*NN-1;i++){
    seg[i]=INT_MAX;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}




/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
//segtreeの葉の先頭の添え字はn-1
void Solve(){
  //vll segtree(524287);
  //ll N=262144;
  ll h,a;
    cin>>h>>a;
  cout<<(h+a-1)/a<<"\n";
}

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

using namespace std;

#define int long long

signed main(){
	int n;
	cin >> n;
	int a[n];
	int dp[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		dp[i]=INT_MAX;
	}
	dp[0]=0;
	dp[1]=abs(a[0]-a[1]);
	for(int i=2;i<n;i++){
		dp[i]=min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]));
		//cout << "i " << i << " dp " << dp[i] << endl;
	}
	cout << dp[n-1] << endl;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
    int D,N;
    cin>>D>>N;
    int X=1;
    for(int i=0;i<D;i++){
        X=X*100;
    }
    if(N==100){
        cout<<101*X<<endl;
    }
    else{
        cout<<(N*X)<<endl;
    }
    
    
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long


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

    int n,k,s; cin >> n >> k >> s;
    vector<int> ans(n);

    if(s < 1000000000){
        for(int i = 0;i < k;i ++) ans.at(i) = s;
        for(int i = k;i < n;i ++) ans.at(i) = 1000000000;
        for(int i = 0;i < n;i ++) cout << ans.at(i) << " ";
        cout << endl;
    }
    else{
        for(int i = 0;i < k;i ++) ans.at(i) = s;
        for(int i = k;i < n;i ++) ans.at(i) = 99999999;
        for(int i = 0;i < n;i ++) cout << ans.at(i) << " ";
        cout << endl;
    }
}

Measured memory_bytes: 2176
// バケット法による解
#include <iostream>
using namespace std;

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

    int num[110] = {0};  // バケット
    for (int i = 0; i < N; ++i) {
        num[d[i]]++;  // d[i] が 1 個増える
    }

    int res = 0;  // 答えを格納
    for (int i = 1; i <= 100; ++i) {  // 1 <= d[i] <= 100 なので 1 から 100 まで探索
        if (num[i]) {  // 0 より大きかったら
            ++res;
        }
    }
    cout << res << endl;
}

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

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
int main() {
	string S;
	ll K;
	cin >> S >> K;
	int x = min((ll)S.size(), K);
	for (int i = 0; i < x; ++i) {
		if (S[i] != '1') {
			cout << S[i] << endl;
			return 0;
		}
	}
	cout << 1 << endl;
	return 0;
}


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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;


int main(){

    int a[] = {1, 3, 5, 7, 8, 10, 12};
    int b[] = {4, 6, 9, 11};

    int x, y;
    cin >> x >> y;
    if((x == 2) || (y == 2)) cout << "No" << endl;
    else{
        bool ok = false;
        for(auto v: a){
            if(x == v){
                for(auto w: a){
                    if(y == w) ok = true;
                }
            }
        }
        for(auto v: b){
            if(x == v){
                for(auto w: b){
                    if(y == w) ok = true;
                }
            }
        }
        if(ok) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    int len = s.length();
    int ans = 0;
    for (int i = 1; i < len; ++i)
    {
        if (s[i] == s[i - 1])
        {
            ans++;
            if(s[i] == '0')
                s[i] = '1';
            else
                s[i] = '0';
        }
    }
    printf("%d", ans);
    return 0;
}

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

namespace ABC085
{
    class D
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int H = input[1];

            int[] A = new int[N];
            int[] B = new int[N];
            for (int i = 0; i < N; i++)
            {
                input = Console.ReadLine().Split().Select(int.Parse).ToArray();
                A[i] = input[0];
                B[i] = input[1];
            }

            A = A.OrderByDescending(x => x).ToArray();
            B = B.OrderByDescending(x => x).ToArray();

            int Amax = A[0];
            int Bcount = B.Count(b => Amax < b);

            for (int i = 0; i < Bcount; i++)
            {
                H -= B[i];
                if (H <= 0) { Console.WriteLine(i + 1); return; }
            }

            int res = H / Amax;
            if (H % Amax == 0) Console.WriteLine(res + Bcount);
            else Console.WriteLine(res + Bcount + 1);
        }
    }
}


Measured memory_bytes: 23484
import math
import copy

inputa = input().split()
inputb = input().split()
# inputc = input().split()

a = int(inputa[0])
# b = int(inputa[1])
# c = int(inputa[2])

# a = inputa[0]
# inputList = list(a)

# x = int(inputb[0])
# y = int(inputb[1])

# inputList=[]
# for i in range(a):
#     inputNum = input()
#     inputList.append(inputNum)

b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

sum = 0
for i in range(len(b)-1, -1, -1):
    flg = True
    for j in range(i):
            if b[j] > b[i]:
               flg = False
               break
    if flg == True:
        sum += 1

print(sum)









Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int D;
  cin>>D;
  vector<int> c(26);
  for(int &i:c)
    cin>>i;
  vector<vector<int>> s(D,vector<int>(26));
  for(vector<int> &v:s)
    for(int &i:v)
      cin>>i;
  vector<int> t(D);
  vector<int> A(26,0);
  int mzint=0;
  for(int i=0;i<D;i++){
    int mzi=mzint,mzin=0,k;
    for(int j=0;j<26;j++)
      mzi-=(i+1-A[j])*c[j];
    for(int j=0;j<26;j++){
      int l=mzi+s[i][j]-(i+1-A[j])*c[j];
      if(l>mzin){
        k=j;
        mzin=l;
      }
    }
    A[k]=i+1;
    mzint=mzin;
    t[i]=k+1;
  }
  int M=1000,ans=mzint;
  while(M--){
    int d=rand()%D,q=rand()%26,ans2=ans;
    ans+=s[d][q]-s[d][t[d]-1];
    int mae=-1,ato=D;
    for(int i=d-1;i>=0;i--){
      if(t[i]==t[d]){
        mae=i;
        break;
      }
    }
    for(int i=d+1;i<D;i++){
      if(t[i]==t[d]){
        ato=i;
        break;
      }
    }
    ans-=(ato-d)*(d-mae)*c[t[d]-1];
    mae=-1,ato=D;
    for(int i=d;i>=0;i--){
      if(t[i]==q+1){
        mae=i;
        break;
      }
    }
    for(int i=d;i<D;i++){
      if(t[i]==q+1){
        ato=i;
        break;
      }
    }
    ans+=(ato-d)*(d-mae)*c[q];
    if(ans2<ans)
      t[d]=q+1;
    else
      ans=ans2;
  }
  for(int i:t)
    cout<<i<<endl;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    string s;
    cin >> s;
    ll ans = 0;
    rep1(i, 4){
        if (s[i]=='+') ans++;
        else ans--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
fun main(args: Array<String>) {
    val s = readLine()!!
    val modVal = 1e9.toLong() + 7

    // どういうDPを構築するかが大事 (求めたい状況をどうやって表現するか)
    // dp[i-1][j]
    // dp には４つの状態 0 <= j <= 3 を考える

    // ~ A ~ B ~ C ~
    // sからABCを選んだ結果があると考え，現在 ~ の位置にあるという状態が 4 パターン
    // 直前 i - 1 文字まで考慮したときの各状態の数がわかっていれば
    // i 文字目が A, B, C, ? であった場合の状態間の遷移を表現できる

    // 自分の場合 (dp間の遷移をうまく構築できなかった ( ? が続く場合等）
    // dp[i-1][j]
    // dp には 3つの状態 0 <= j <= 2 を考える

    // i 文字目までの A の数
    // i 文字目までの AB の数
    // i 文字目までの ABC の数
    // この方法でなぜ駄目だったのか？
    // 「選ぶ」観点が抜けていたか？？　数の数え上げとしては正しい

    // 回答実装

    val dp = Array(s.length + 1) { LongArray(4) { 0L } }
    dp[0][0] = 1

    for (i in 1..(s.length)) {

        val c = s[i - 1]

        if (c == 'A' || c == '?') {
            dp[i][0] += dp[i-1][0]
            dp[i][1] += dp[i-1][1]
            dp[i][2] += dp[i-1][2]
            dp[i][3] += dp[i-1][3]

            dp[i][1] += dp[i-1][0]

            for (j in 0..3) {
                dp[i][j] = dp[i][j] % modVal
            }
        }

        if (c == 'B' || c == '?') {
            // 現在の B を選ばない場合
            dp[i][0] += dp[i-1][0]
            dp[i][1] += dp[i-1][1]
            dp[i][2] += dp[i-1][2]
            dp[i][3] += dp[i-1][3]

            // 現在の B を選ぶ場合
            dp[i][2] += dp[i-1][1]

            for (j in 0..3) {
                dp[i][j] = dp[i][j] % modVal
            }
        }

        if (c == 'C' || c == '?') {
            dp[i][0] += dp[i-1][0]
            dp[i][1] += dp[i-1][1]
            dp[i][2] += dp[i-1][2]
            dp[i][3] += dp[i-1][3]

            dp[i][3] += dp[i-1][2]

            for (j in 0..3) {
                dp[i][j] = dp[i][j] % modVal
            }
        }
    }

    println(dp[s.length][3])
}

Measured memory_bytes: 42872
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main() {
	int n=read();
	string s;
	cin>>s;
	for (int i=0; i<n; i++) {
		if (s[i]=='.') ++a[i+1];
		if (s[i]=='#') ++b[i+1];
	}
	for (int i=1; i<=n; i++) {
		a[i]+=a[i-1];
		b[i]+=b[i-1];
	}
	int ans=n+1;
	for (int i=0; i<=n; i++) {
		ans=min(ans,i-a[i]+n-i-(b[n]-b[i]));
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2180
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;
// ------------------------------

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> vec(H, vector<char>(W));
    vector<vector<char>> tmp(H, vector<char>(W));
    rep(i, H) rep(j, W) cin >> vec[i][j];
    int ans = 0;
    rep(hbit, 1 << H) {
        rep(wbit, 1 << W) {
        rep(i, H) rep(j, W) tmp[i][j] = vec[i][j];
            int cnt = 0;
            rep(i, H) if (hbit & (1 << i)) rep(j, W) tmp[i][j] = '.';
            rep(i, W) if (wbit & (1 << i)) rep(j, H) tmp[j][i] = '.';
            rep(i, H) rep(j, W) if (tmp[i][j] == '#') cnt += 1;
            if (cnt == K) ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    string str;cin>>str;
    vector<char>a;
    for(int i=0;i<4;++i){
        a.push_back(str[i]);
    }
    sort(a.begin(),a.end());
    if(a[0]==a[1]&&a[1]!=a[2]&&a[2]==a[3])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String str[] = br.readLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int a = Integer.parseInt(str[1]);
            int b = Integer.parseInt(str[2]);
            if (n * a > b) {
                System.out.println(b);
            } else {
                System.out.println(n * a);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 25172
#include <stdio.h>

int solve(int W, int H){
  char room[20][20];
  int x, y, i;
  
  for(i = 0; i < H; i++){
    scanf("%s\n", room[i]);
  }

  for(y = 0; y < H; y++){
    for(x = 0; x < W; x++){
      if(room[y][x] == '@')
	return dfs(room , W, H, x, y, 0);
    }
  }
  return 0;
}

int dfs(char room[][20], int W, int H, int x, int y, int n){
  int nx, ny, i;
  if(room[y][x] == '@') n = 1;
  else if(room[y][x] == '.') n++;

  room[y][x] = '/';

  for(i = 0; i < 4; i++){
    switch(i){
    case 0:  //left
      nx = x - 1;
      ny = y;
      break;
    case 1:  //up
      nx = x;
      ny = y - 1;
      break;
    case 2:  //right
      nx = x + 1;
      ny = y;
      break;
    case 3:  //down
      nx = x;
      ny = y + 1;
      break;				      
    } 
    if((0 <= nx && nx < W) && (0 <= ny && ny < H)){
      if(room[ny][nx] == '.'){
	n = dfs(room, W, H, nx, ny, n);
      }
    }
  }
  return n;
}

int main(void){
  int W, H;
  while(1){
    scanf("%d %d", &W, &H);
    if(W == 0 && H == 0) return 0; 
    else printf("%d\n", solve(W, H));
  }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
#define yn(f) cout<<(f?"yes":"no")<<endl
#define Yn(f) cout<<(f?"Yes":"No")<<endl
#define YN(f) cout<<(f?"YES":"NO")<<endl
#define COUT(x) cout<<(x)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================

// Template End ======================================================

constexpr int MOD=1e9+7;

int main(void){
  int a,b; cin>>a>>b; COUT(TF(a%b>0));
}













Measured memory_bytes: 256
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#define rp(i,a,b) for(int (i)=(int)(a);i<(int)(b);++i)
using namespace std;
char l[101][101];
int xx,yy,ans=0;
int movex[]={0,0,1,-1},movey[]={1,-1,0,0};
void dfs(int sx,int sy,char c){
    l[sx][sy]='n';
    for(int i=0;i<4;i++){
        int x=sx+movex[i],y=sy+movey[i];
        if(0<=x and x<xx and 0<=y and y<yy){
            if(c==l[x][y]) dfs(x,y,c);
        }
    }
}
int main(){

    while(1){
        int a,b;
        cin>>a>>b;
        xx=a;
        yy=b;
        if(a==0 and b==0) break;
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                cin>>l[i][j];
            }
        }
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if(l[i][j]!='n') {dfs(i,j,l[i][j]);ans++;}
                
            }
        }
        cout<<ans<<endl;
        ans=0;

    }
}

Measured memory_bytes: 3544
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//試してて御免

const int cm = 1 << 17;
char ci[cm];
int cn;
inline char getcha() { 
	if (!cn) { fread(ci, 1, cm, stdin); cn = cm; }
	cn--;
	return ci[cm - cn - 1];
}

int getint() {
	int A = getcha() - '0';
	char C;
	while (isdigit(C = getcha())) {
		A = A * 10 + C - '0';
	}
	return A;
}

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


	int N, X;
	N = getint();
	X = getint();

	int A = 0;
	ll kotae = 0;
	rep(i, N) {
		int B = getint();
		if (A + B > X) {
			kotae += A + B - X;
			B = X - A;
		}
		A = B;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define CVector CPoint
#define INF 0x3f3f3f3f
#define MAXN 1e5
const LL mod=1e9+7;
const double PI=acos(-1.0);
const double EPS=1e-10;
inline int readint(){int sum=0;char c=getchar();bool f=0;while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}if(f) return -sum;return sum;}
inline LL readLL(){LL sum=0;char c=getchar();bool f=0;while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}if(f) return -sum;return sum;}

int a[200005],b[200005];
int main(){ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int p=1,q=n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int j=n;
    while(j>=1){
        b[p++]=a[j];
        j-=2;
    }
    if(n%2) j=2;
    else j=1;
    while(j<=n){
        b[p++]=a[j];
        j+=2;
    }
    for(int i=1;i<=n;i++){
        cout<<b[i];
        if(i<n) cout<<" ";
        else cout<<endl;
    }
    return 0;
}

//cout.setf(ios::fixed);
//cout<<fixed<<setprecision(10)<<s<<endl;


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define ll long long
#define P pair<ll, ll>
using namespace std;

const ll inf = 1e18;

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


int main(){
    int n;
    cin >> n;
    vector<int>ans;
    for(int i=1;i<=55555;i++){
        if(!is_prime(i))continue;
        if(i%5 == 1) ans.push_back(i);
    }

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

Measured memory_bytes: 3632
import java.util.Scanner;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = 0;
        long a = 0;
        long r = 0;
        long c = 0;
        long h = 0;
        for(int i = 0; i < n; i++){
            String str = sc.next().substring(0,1);
            if(str.equals("M")){
                m++;
            }
            if(str.equals("A")){
                a++;
            }
            if(str.equals("R")){
                r++;
            }
            if(str.equals("C")){
                c++;
            }
            if(str.equals("H")){
                h++;
            }
        }
        long ans = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h;
        System.out.println(ans);
    }
}

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

int main(){
    int n, i, R_min, R, prof_max;
    cin >> n;

    cin >> R_min;
    prof_max = 1 - 1e9;

    for(i = 1; i < n; i++){
        cin >> R;
        prof_max = max(prof_max, R - R_min);
        R_min = min(R_min, R);
    }
    cout << prof_max << endl;
    return 0;
}


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

f = [list(map(int, input().split())) for _ in range(n)]
# f = zip(*f)

p = [list(map(int, input().split())) for _ in range(n)]
# p = zip(*p)

ans = -10**10
for i in range(1,1<<10):
    c = [0] * n # 同時に店を開いている時間帯数
    for j in range(10):
        if i & (1<<j):
            for k,F in enumerate(f):
                if F[j]:
                    c[k] += 1
    profit = 0
    for j in range(n):
        profit += p[j][c[j]]
    ans = max(ans, profit)

print(ans)

Measured memory_bytes: 9208
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;
int main(){
    ll n;
    cin>>n;
    vector<ll> v(n);
    REP(i,n){
        cin>>v[i];
    }
    sort(ALL(v));
    ll s=SIZE(v)/2, right=v[s],left=v[s-1];
    cout<<right-left;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int n; cin >> n;
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    int ans = 0;
    rep(i,n){
        bool res = true;
        for(int j = 0; j < i; ++j){
            if(v[j] >v[i]) res = false;
        }
        ans += res;
    }
    cout << ans << endl;
}




Measured memory_bytes: 256
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;


int main(void){
    long long X, Y;

    cin >> X >> Y;
    
    int ans=1;
    bool judge = true;
    long long tmp=X;

    while(judge){
        
        tmp = 2*tmp;
        if(tmp > Y){
            break;
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Bisect
{
    public static int BisectRight<T>(T[] a, T x) where T : IComparable
    {
	int lo = 0, hi = a.Length;
	while (lo < hi)
	{
	    int mid = (lo + hi) / 2;
	    if (x.CompareTo(a[mid]) < 0) { hi = mid; }
	    else { lo = mid + 1; }
	}
	return lo;
    }
}

class Program
{
    public static void Main()
    {
	var tmp = ReadIntArray();
	int n = tmp[0], m = tmp[1];
	int[] p = new int[m];
	int[] y = new int[m];
	List<int>[] dat = new List<int>[n];

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

	for (int i = 0; i < m; i++)
	{
	    tmp = ReadIntArray();
	    p[i] = tmp[0]; y[i] = tmp[1];
	    dat[p[i]-1].Add(y[i]);
	}

	int[][] dat2 = new int[n][];
	
	for (int i = 0; i < n; i++)
	{
	    dat2[i] = dat[i].ToArray();
	    Array.Sort(dat2[i]);
	}

	for (int i = 0; i < m; i++)
	{
	    int pn = p[i];
	    int yn = Bisect.BisectRight(dat2[pn-1], y[i]);
	    Write(String.Format("{0:000000}", pn));
	    WriteLine(String.Format("{0:000000}", yn));
	}
    }
}


Measured memory_bytes: 35812
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<long long,long long> a,pair<long long,long long> b){
    return a.first<b.first;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,k,i;
    cin>>n>>k;
    long long a[n];
    map<long long,long long> m;
    for(i=0;i<n;i++){
        cin>>a[i];
        m[a[i]]++;
    }
    if(m.size()<=k){
        cout<<0<<endl;
        return 0;
    }
    vector<pair<long long,long long> > v;
    for(auto i=m.begin();i!=m.end();i++){
       // cout<<i->first<<" "<<i->second<<endl;
        v.push_back({i->second,i->first});
    }
    long long sum=0;
    sort(v.begin(),v.end());
    for(i=0;i<v.size()-k;i++){
       // cout<<v[i].second<<" "<<v[i].first<<" ";
        sum+=(v[i].first);
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 19568
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f
#define pi 3.1415926535898
using namespace std;
const int mod=1e9+7;
const int N=1e6+10;
struct A
{
    int  w,v;
} a[3050];
bool cmp(A a,A b)
{
    return a.w<b.w;
}
ll dp[3500][6050];
int main()
{
    ll n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].w>>a[i].v;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<a[i].w+m; j++)
        {
            if(j>=a[i].w)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    ll res=0;
    for(int i=1; i<=n; i++)
        res=max(dp[n][m+a[i].w-1],res);
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 145384
# E - Colorful Blocks

n, m, k = map(int, input().split())

modulus = 998244353

# nブロック m色で塗る → m ** n 通り
# 隣り合うブロックの組 n - 1組のうち 高々k組が同色

# n個ばらばら m * (m-1) ** (n-1)
# k組同色 == n-k個ばらばら * choose(n-1, n-k-1)

def inv(x):
    e = 1
    for b in bin(modulus - 2)[2:]:
        e *= e
        if b == '1':
            e *= x
        e %= modulus
    return e

pow = [1]  # (m-1) ** i
for i in range(n):
    pow.append(pow[-1] * (m - 1) % modulus)
choose = [1]  # choose(n-1, i)
for i in range(1, n):
    choose.append(choose[-1] * (n-1-i+1) * inv(i) % modulus)

def solve(n, k):
    x = m * pow[n-k-1]
    return x * choose[n-k-1] % modulus

print(sum(solve(n, i) for i in range(k+1)) % modulus)


Measured memory_bytes: 24756
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;

int main(void) {
	int N, K;
	cin >>N >> K;

	vector<int> ans(N+3);

	for (int i = 0; i < N; i++) {
		ans[i] = 0;
	}

	for (int i = 0; i < K; i++) {
		int d;
		cin >> d;
		for (int j = 0; j < d;j++) {
			int a;
			cin >> a;
			ans[a-1] = 1;
		}

	}

	int count = 0;
	for (int i = 0; i < N; i++) {
		if (ans[i] == 0) {
			count++;
		}
	}

	cout << count;

	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fo for(int i=0;i<n;i++)
#define clear cin.clear();cin.ignore(numeric_limits<streamsize>::max(), '\n');
#define loopSolve int t; cin>>t; while(t--){solve();}
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

//INT_MAX         2,147,483,647                       <10^10
//U_INT_MAX       4,294,967,295                       <10^10
//LONG_LONG_MAX   9,223,372,036,854,775,807           <10^18
//U_LONG_LONG_MAX 18,446,744,073,709,551,615          <10^18
//ll power(int a, int b){
//    return (ll)(pow(a,b)+0.5);
//}

vector<int> gV(int n){
    vector<int> v(n);
    fo { cin>>v[i];  }
    return v;
}

int* gA(int n){
    int* arr = new int[n];
    fo cin>>arr[i];
    return arr;
}


void solve(){
    string s;
    cin>>s;

    int count=0,ans=0;
    for(int i=0;i<3;i++){
        if(s[i]=='R'){
            while(i<3 && s[i]=='R'){
                count++;
                i++;
            }
        }
        ans=max(ans,count);
        count=0;
    }
    cout<<ans<<endl;
}


int main() {
	ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    solve();
    //loopSolve;

	return 0;
}


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

int cmp(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;
}

int main()
{
	int p[1000] = {0};
	int n, k, sum = 0;
	scanf("%d%d", &n, &k);

	for(int i = 0; i < n; i++) scanf("%d", &p[i]);
	qsort(p,n,sizeof(int),cmp);
	for(int i = 0; i < k; i++) sum += p[i];
	printf("%d\n", sum);

	return 0;
}

Measured memory_bytes: 1744
#include<iostream>
#include<math.h>

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s_a, s_b, s_c;   //読み込んだ文字列
  char ans;               //勝者
  int i_a = 0, i_b = 0, i_c = 0;      //次に何番目を捨てるのか
  bool a, b, c;           //現在だれのターンか

  cin >> s_a >> s_b >> s_c;

  a = true;
  b = false;
  c = false;              //初期設定　Aのターンから始まる

  while(1){
    if(a == true){
      if(i_a == s_a.length()){
	ans = 'A';
	break;
      }
      else if(s_a[i_a] == 'b'){
	a = false;
	b = true;
      }
      else if(s_a[i_a] == 'c'){
	a = false;
	c = true;
      }
      i_a++;
    }
    else if(b == true){
      if(i_b == s_b.length()){
	ans = 'B';
	break;
      }
      else if(s_b[i_b] == 'a'){
	b = false;
	a = true;
      }
      else if(s_b[i_b] == 'c'){
	b = false;
	c = true;
      }
      i_b++;
    }
    else{
      if(i_c == s_c.length()){
	ans = 'C';
	break;
      }
      else if(s_c[i_c] == 'a'){
	c = false;
	a = true;
      }
      else if(s_c[i_c] == 'b'){
	c = false;
	b = true;
      }
      i_c++;
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>

#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define NL << endl

using namespace std;
using ll = long long;
using ull = unsigned long long;


int main() {

	int a, b, c;

	cin >> a >> b >> c;
	int ab = abs(a - b), bc = abs(b - c), ac = abs(a - c);

	int ans = ab + bc + ac - max(ab, max(bc, ac));
	
	cout << ans NL;

	return 0;
}


Measured memory_bytes: 256
using System;

namespace ABC166A
{
    class Program
    {
        static void Main(string[] args)
        {

            string[] word = Console.ReadLine().Split(' ');
            int n = int.Parse(word[0]);
            int m = int.Parse(word[1]);
            if (m >= n)
                Console.WriteLine("Yes");
            else Console.WriteLine("No");




        }
    }
}


Measured memory_bytes: 27008
N, M = map(int, input().split())
arr = sorted(list(map(int, input().split())))

if N >= M:
    print(0)
    exit()

org_kyori =[]
for i in range(len(arr)-1):
    org_kyori.append(arr[i+1]-arr[i])

kyori =sorted(org_kyori)

ans = sum(kyori)
for i in range(N-1):
    ans -= kyori[-1*(i+1)]

print(ans)



Measured memory_bytes: 92176
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int D;
  cin>>D;

  const int A = 26;
  vector<int> cs(A+1);
  for(int j=1;j<=A;j++) cin>>cs[j];

  vector s(D+1,vector<int>(A+1));
  for(int i=1;i<=D;i++)
    for(int j=1;j<=A;j++)
      cin>>s[i][j];

  vector<int> ts(D+1);
  for(int i=1;i<=D;i++) cin>>ts[i];

  auto calcScore=[&]()->int{
    int res=0;
    vector<int> ls(A+1,0);
    for(int i=1;i<=D;i++){
      res+=s[i][ts[i]];
      ls[ts[i]]=i;
      for(int j=1;j<=A;j++)
        res-=cs[j]*(i-ls[j]);
    }
    return res;
  };

  int m;
  cin>>m;
  for(int i=0;i<m;i++){
    int d,q;
    cin>>d>>q;
    ts[d]=q;
    cout<<calcScore()<<newl;
  }
  return 0;
}


Measured memory_bytes: 3712
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define pb push_back
#define pf push_fron
#define INF 1e9
#define PI acos(-1)
typedef long long ll;

vector<int> G[100010];
ll V, M;
int color[100010];//頂点iの色(1 or -1)

bool dfs(int v, int c) {
	color[v] = c;
	for (int i = 0; i < G[v].size(); i++) {
		if (color[G[v][i]] == c)return false;

		//隣接している頂点がまだ塗られていないなら-cで塗る
		if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))return false;
	}
	//全ての頂点が塗れたらtrue
	return true;
}


int main() {
	cin >> V >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].pb(b); G[b].pb(a);
	}
	if (!dfs(0, 1)) {
		cout << (ll)(V*(V - 1) / 2) - M << endl;
	}
	else {
		ll x = count(color,color+V, 1);
		ll y = count(color, color + V, -1);
		cout << (ll)x * y - M << endl;
	}
	return 0;
}

Measured memory_bytes: 6528
N, M = map(int, input().split())
S=[[0, ""] for j in range(M)]
ACcheck=[False for j in range(N)]
AC=0
WA=[0 for j in range(N)]
WA2 = 0
for i in range(M):
  ps = input().split()
  S[i][0]=int(ps[0])
  S[i][1]=ps[1]
for i in range(M):
  if S[i][1]=="AC":
    if ACcheck[S[i][0]-1]==False:
      AC+=1
      ACcheck[S[i][0]-1]=True
      WA2+=WA[S[i][0]-1]
  else:
    if ACcheck[S[i][0]-1]==False:
      WA[S[i][0]-1]+=1

print(AC, WA2)


Measured memory_bytes: 23624
fun main(args: Array<String>) {

    val x = readInts()[0]
    
    println(getList().maxBy { it <= x })
}

fun getList() =
    (1 .. 31).flatMap {base ->
        (2 .. 9).map { Math.pow(base.toDouble(), it.toDouble()).toInt() }.filter { it <= 1000 }
    }.distinct().sortedDescending()

fun readInts(): List<Int> = readStrings().map { it.toInt() }
fun readStrings(): List<String> = readLine()!!.split(" ")

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

int main(){
  string s; cin>>s;
  if(s[2]==s[3]){
    if(s[4]==s[5])
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 3616