akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct WeightedUnionFind {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    vector<int> diff_weight;

    WeightedUnionFind(int sz) : data(sz, -1), diff_weight(sz, 0) {}

    // weight(y) - weight(x) = w となるように merge する
    bool unite(int x, int y, int w) {
        w += weight(x);
        w -= weight(y);
        x = find(x);
        y = find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) {
                swap(x, y);
                w = -w;
            }
            data[x] += data[y];
            data[y] = x;
            diff_weight[y] = w;
        } else {
            if (diff(x, y) == w) return true;
        }
        return is_union;
    }

    int find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            int par = data[x];
            data[x] = find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            diff_weight[x] += diff_weight[par];
            return data[x];
        }
    }

    int weight(int x) {
        find(x);
        return diff_weight[x];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int diff(int x, int y) {
        return weight(y) - weight(x);
    }

    int size(int x) {
        return -data[find(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    WeightedUnionFind wuf(n);
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        if (!wuf.unite(x, y, z)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1024
import numpy as np
b_card = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
nums = [int(input()) for _ in range(N)]

card_st = np.zeros((3, 3))

for num in nums:
    for index, card_num in enumerate(b_card):
        if num in card_num:
            card_st[index][card_num.index(num)] = 1

if True in np.all(card_st, axis=0):
    print('Yes')
elif True in np.all(card_st, axis=1):
    print('Yes')
elif np.all(np.diag(card_st) == 1):
    print('Yes')
elif np.all(np.diag(np.fliplr(card_st)) == 1):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 12424
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

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

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)



int main() {
	ll X;
	std::cin >> X;
	ll m = 100;
	ll cnt = 0;
	while (m<X) {
		cnt++;
		m += m / 100;
	}
	std::cout << cnt << endl;
	return 0;
}


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

const int LIM = 100000;
int n, k, cnt;
pair<int, int> dt[LIM];
ll ans;
map<int, int> cnts;

int main() {
    cin >> n >> k;
    rep(i, n) cin >> dt[i].second >> dt[i].first;
    sort(dt, dt + n, greater<pair<int, int> >());
    
    // まずd多い順にとる
    rep(i, k) {
        int d = dt[i].first, t = dt[i].second;
        if(cnts[t] == 0) {
            // 初体験
            ans += cnt * 2 + 1;
            cnt++;
        }
        ans += d;
        cnts[t]++;
    }

    // 種類だんだん多くする
    int idx1 = k - 1, idx2 = k;
    ll num = ans;
    while (idx1 >= 0) {
        // 2個以上ある種類の寿司を1個減らす
        int d = dt[idx1].first, t = dt[idx1].second;
        idx1--;

        if (cnts[t] > 1) {
            cnts[t]--;
            num -= d;
        } else {
            continue;
        }
        
        // 1種類増やす
        while (idx2 < n) {
            d = dt[idx2].first; t = dt[idx2].second;
            idx2++;
            if (cnts[t] > 0) {
                // すでに食べてる
            } else {
                num += d + cnt * 2 + 1;
                cnt++;
                cnts[t]++;
                ans = max(ans, num);
                break;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        UL N, Q; scanf("%d%d", &N, &Q);
        vector<ULL> A(N); rep(i, N) { scanf("%lld", &A[i]); }
        while (Q--) {
            ULL X; scanf("%lld", &X);
            ULL Z = 0; UL q = 0;
            ULL ans = 0;
            rep(p, N) {
                Z += A[p];
                while (X < Z) { Z -= A[q]; q++; }
                ans += (p + 1 - q);
            }
            printf("%lld\n", ans);
        }
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    //cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}




Measured memory_bytes: 3620
k, a, b = map(int, input().split())
if a < k and b >= a:
  print('-1')
elif a >= k:
  print('1')
else:
  ans = k // (a - b) * 2 - 4
  while ans // 2 * a - ans // 2 * b + b < k:
    ans += 2
  print(ans - 1)

Measured memory_bytes: 38256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut s: Vec<char> = read::<String>().chars().collect();
    s[3] = '8';
    let mut ans: String = String::new();
    for i in 0..s.len() {
        let si = s[i];
        ans += &si.to_string();
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const ll INF=2e+16;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    ll N;
    cin>>N;
    vector<ll> a(N);
    REP(i,N) cin>>a[i];
    sort(ALL(a));
    ll l=-1;
    ll r=INF;
    while(r-l>1){
        ll mid=(l+r)/2;
        ll x=mid*N;
        ll cnt=0;
        REP(i,N){
            ll tmp=x+a[i]-(N-1);
            ll n;
            if(tmp<=0) n=0;
            else n=(tmp-1)/(N+1)+1;
            cnt+=n;
        }
        if(x>=cnt) r=mid;
        else l=mid;
    }

    ll ans;
    
    REP(i,200*N+1){
        ll x=N*(l-100)+i;
        if(x<0) continue;
        ll cnt=0;
        REP(i,N){
            ll tmp=x+a[i]-(N-1);
            ll n;
            if(tmp<=0) n=0;
            else n=(tmp-1)/(N+1)+1;
            cnt+=n;
        }
        if(x>=cnt){
            ans=x;
            break;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3612
H,W = map(int,input().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
counter = 0
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "#":
            M[i][i2] = True
            que.append([i,i2,0])
while counter != H * W:
    k = que[counter]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    counter += 1
print(k[2])

Measured memory_bytes: 158756
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
	int N,K;
	double arr[200000];
	double ans=0;
	scanf("%d %d",&N,&K);
	for (int i=0; i<N; i++){
		double num;
		scanf("%lf",&num);
		arr[i] = (1.0+num)/2;
	}
	double ret =0;
	for (int i=0; i<K; i++){
		ret+= arr[i];
	}
	ans = max(ans,ret);
	for (int i=K; i<N; i++){
		ret += (arr[i] - arr[i-K]);
		ans = max(ans,ret);
	}

	printf("%lf\n",ans);

}

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

int main() {
  int n;
  cin >> n;
  
  vector<int> vt(n);
  for(int i = 0; i < n; i++)
  {
    cin >> vt.at(i);
  }

  int min = vt.at(0);
  int count = 0;
  for(int i = 0; i < n; i++)
  {
    int j = vt.at(i);
    if(j <= min) {
      min = j;
      count++;
    }
  }
  cout << count << endl;
}

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

int memo[3002][3002];
int dir[3002][3002];
string s, t;
int dfs(int n, int m) {
  if (memo[n][m] != -1) return memo[n][m];
  int ret = 0;
  if (s[n] == t[m]) {
    ret = 1 + ((n > 0 && m > 0) ? dfs(n - 1, m - 1) : 0);
    dir[n][m] = 3;
  }
  if (n > 0) {
    int tmp = dfs(n - 1, m);
    if (tmp > ret) {
      ret = tmp;
      dir[n][m] = 2;
    }
  }
  if (m > 0) {
    int tmp = dfs(n, m - 1);
    if (tmp > ret) {
      ret = tmp;
      dir[n][m] = 1;
    }
  }
  return memo[n][m] = ret;
}

int main(void) {
  cin >> s >> t;
  s = "$" + s;
  t = "#" + t;
  
  int n = s.size();
  int m = t.size();
  memset(memo, -1, sizeof(memo));
  dfs(n - 1, m - 1);

  int now_n = n - 1, now_m = m - 1;

  if (dir[now_n][now_m] == 0) {
    cout << " " << endl;
    return 0;
  }

  string track;
  while (now_n > 0 && now_m > 0) {
    int d = dir[now_n][now_m];
    if (d == 0) break;
    if (d == 1) now_m--;
    if (d == 2) now_n--;
    if (d == 3) {
      track += s[now_n];
      now_n--, now_m--;
    }
  }
  reverse(track.begin(), track.end());
  cout << track << endl;

  return 0;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;

const int MAX = 2E5+5;
int link[MAX], sz[MAX];

int find(int a){
	if (link[a] == a)
		return a;
	else{
		link[a] = find(link[a]);
		return link[a];
	}
}

void unite(int a, int b){
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a,b);
	sz[a] += sz[b];
	link[b] = a;
}

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

    int n,q;

    cin >> n >> q;
    for (int i=0; i<n; ++i){
    	link[i] = i;
    	sz[i] = 1;
    }
    for (int i=0; i<q; ++i){
    	int t,u,v;
    	cin >> t >> u >> v;
    	if (t == 0){
    		unite(u,v);
    	}else{
    		u = find(u);
    		v = find(v);
    		cout << (u == v) << endl;
    	}
    }

    
	return 0;
}

Measured memory_bytes: 5092
def print_list_inline(tr_list):
    inline = map(lambda string:"{:>5}".format(string),tr_list)
    inline = list(inline)
    print(("").join(inline))


while True:
    n = int(input())
    if n != 0:
        sum_col = [0 for i in range(n+1)]
        for i in range(n):
            list_row = list(map(int,input().split(" ")))
            sum_row = sum(list_row)
            list_row.append(sum_row)
            for j in range(len(list_row)):
                sum_col[j] += list_row[j]
            print_list_inline(list_row)
        print_list_inline(sum_col)
    else:
        break

Measured memory_bytes: 7736
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N):
        u, k, *vc = (int(i) for i in input().split())
        for i in range(0, len(vc), 2):
            G[u].append((vc[i], vc[i+1]))
    d = [[(1 << 63)-1, i] for i in range(N)]
    from heapq import heapify, heappop, heappush

    def dijkstra(s):
        d[s][0] = 0
        que = [(d[s][0], s)]
        heapify(que)
        finished = set()
        while len(finished) < N:
            u = heappop(que)
            while u[1] in finished:
                u = heappop(que)
            if d[u[1]][0] < u[0]:
                print('yeah')
            for v, c in G[u[1]]:
                if v in finished:
                    continue
                if d[v][0] > u[0] + c:
                    d[v][0] = u[0] + c
                    heappush(que, (d[v][0], v))
            finished.add(u[1])
    dijkstra(0)
    for i, val in enumerate(d):
        print(i, val[0])


if __name__ == '__main__':
    main()



Measured memory_bytes: 68852
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  int cur = 0;
  bool ans = false;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    if (a == b) cur++;
    else cur = 0;
    if (cur >= 3) ans = true;
  }

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

Measured memory_bytes: 3632
k = int(input())
n = 50
print(n)

l = []
for i in range(n):
    tmp = [n+1-i]*i + [-i]*(n-i)
    l.append(tmp)

res = []
for i in range(n):
    res.append(k//n + i + l[k%n][i])
print(*res)

"""
for s in l:
    print(*s)
"""


Measured memory_bytes: 3064
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)


Measured memory_bytes: 235572
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807

using namespace std;

long long GCD(long long a, long long b) {
	if (a < b)
		swap(a, b);
	if (b == 0) return a;
	else return GCD(b, a % b);
}
bool sosuu_check(int num) {
	int i;
	for (i = 2; i <= sqrt(num); ++i) {
		if (num%i == 0)
			return false;
	}
	return (num < 2) ? false : true;
}
int main() {
	int N,i;
	cin >> N;
	string ans="";
	REP(i, 3) {
		ans += (N % 10 == 1) ? '9' : '1';
		N /= 10;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
}

Measured memory_bytes: 256
def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
ans = 1000

for i in range(1, N):
    tmp = ans
    if A[i] > A[i - 1]:
        purchase = tmp // A[i - 1]
        ans = max(ans, tmp + (A[i] - A[i - 1]) * purchase)
        
print(ans)

Measured memory_bytes: 61948
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" ";
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define ll long long
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pdd pair<double,double>
#define pdi pair<double,int>
#define mp(u,v) make_pair(u,v)
#define sz(a) a.size()
#define ull unsigned long long
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
const int mod = 1e9+7;
const int maxn = 8e3+5;
const double EPS = 1e-6;
using namespace std;
int base = 8000;
char s[maxn];
int a[maxn];
int dp[2*maxn],g[2*maxn];
int main()
{
	int x,y;
	scanf("%s",s+1);
	scanf("%d%d",&x,&y);
	int len = strlen(s+1);
	int d = 0,cnt = 0;
	rep(i,1,len+1){
		if(s[i]=='F') d++;
		else a[++cnt] = d, d = 0;
	}
	if(d) a[++cnt] = d;
	dp[base] = 1;
	repp(i,1,len+1,2){
		if(i==1) {
			dp[base] = 0;
			dp[base+a[i]] = 1;
			continue;
		}
		rep(j,0,2*base+1) if(dp[j]) g[j-a[i]]=g[j+a[i]]=1;
		rep(j,0,2*base+1) dp[j]=g[j],g[j]=0;
	}
	if(!dp[x+base]) return puts("No"),0;
	mt(dp,0);dp[base]=1;
	repp(i,2,len+1,2){
//		if(i==2) {
//			dp[base] = 0;
//			dp[base+a[i]] = 1;
//			continue;
//		}
		rep(j,0,2*base+1) if(dp[j]) g[j-a[i]]=g[j+a[i]]=1;
		rep(j,0,2*base+1) dp[j]=g[j],g[j]=0;
	}
	if(!dp[y+base]) return puts("No"),0;
	puts("Yes");
	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

ll n,m;
ll solve(){
   ll ans=0;
    if(n==1&&m==1)return 1;
    if(n==1)return m-2;
    if(m==1)return n-2;
    ans=(n-2)*(m-2);

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

    cin>>n>>m;
    cout<<solve()<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

func nextInt() int{
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil{
		panic(e)
	}
	return i
}
var sc = bufio.NewScanner(os.Stdin)

func main(){
	var n, min, ans, num int
	ans = -1000000009
	n = nextInt()
	min = nextInt()
	for i:=1; i<n; i++{
		num = nextInt()
		if ans < num - min{
			ans = num - min
		}
		if min > num{
			min = num
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4088
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Ma,Mb = LI()
a,b,c = LIR(N,3)

n = N//2

d1 = defaultdict(lambda:5000)
d2 = defaultdict(lambda:5000)

for bit in range(1<<n):
    val_a = 0
    val_b = 0
    cost = 0
    for i in range(n):
        if bit>>i&1:
            val_a += a[n-1-i]
            val_b += b[n-1-i]
            cost += c[n-1-i]
    if cost < d1[(val_a,val_b)]:
        d1[(val_a,val_b)] = cost

for bit in range(1<<(N-n)):
    val_a = 0
    val_b = 0
    cost = 0
    for i in range(N-n):
        if bit>>i&1:
            val_a += a[N-1-i]
            val_b += b[N-1-i]
            cost += c[N-1-i]
    if cost < d2[(val_a,val_b)]:
        d2[(val_a,val_b)] = cost

vals = []
now = 1
while True:
    if Ma*now <= sum(a) and Mb*now <= sum(b):
        vals.append((Ma*now,Mb*now))
        now += 1
    else:
        break

ans = 5000
for k in d1.keys():
    for v in vals[::-1]:
        left_a = v[0]-k[0]
        left_b = v[1]-k[1]
        if left_a < 0 or left_b < 0:
            break
        if d1[k]+d2[(left_a,left_b)] < ans:
            ans = d1[k]+d2[(left_a,left_b)]

if ans == 5000:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 49628
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	vector<int> ans;
	int now = -1;
	while(ans.size() < 9){
		int count = 0;
		cout<<"? ";
		rep(i,ans.size()){
			cout<<ans[i];
			count++;
		}
		if(now == -1){
			cout<<4;
			count++;
		}else{
			cout<<now;
			count++;
		}
		rep(i,18-count){
			cout<<"9";
		}
		cout<<endl;
		char yn;
		cin>>yn;

		if(yn == 'N'){
			if(now == -1){
				now = 5;
			}else if(now == 3){
				ans.push_back(4);
				now = -1;
			}else if(now == 8){
				ans.push_back(9);
				now = -1;
			}else{
				now++;
			}
		}else{
			if(now == -1){
				now = 0;
				if(ans.size() == 0) now = 1;
			}else{
				ans.push_back(now);
				now = -1;
			}
		}

	}

	int keta = 10;
	if(ans[0] != 9){
		reps(i, 9){
			cout<<"? ";
			rep(j,i){
				cout<<9;
			}
			cout<<endl;

			char yn;
			cin>>yn;
			if(yn == 'Y'){
				keta = i;
				break;
			}
		}		
	}else{
		reps(i,9){
			cout<<"? ";
			rep(j,i+1){
				cout<<1;
			}
			cout<<endl;

			char yn;
			cin>>yn;
			if(yn == 'N'){
				keta = i;
				break;
			}
		}
	}

	ans.push_back(0);
	cout<<"! ";
	rep(i,keta){
		cout<<ans[i];
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 596
#include<stdio.h>
#include<string.h>

static  int N =1000;

int max(int a,int b){
  if(a>b) return a;
  else return b;
}

int lcs(char x[],char y[]){
  int c[N+1][N+1];
  int m=strlen(x);
  int n=strlen(y);
  int maxl=0,i,j;

  
  for(i=0;i<=m;i++) c[i][0]=0;
  for(j=1;j<=n;j++) c[0][j]=0;

  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(x[i-1]==y[j-1]){
	c[i][j]=c[i-1][j-1]+1;
      }
      else{
	c[i][j]=max(c[i-1][j],c[i][j-1]);
      }
      maxl=max(maxl,c[i][j]);
    }
  }
  return maxl;
}

int main(){
  char s1[1500],s2[1500];
  int n,i;
 scanf("%d",&n);
for(i=0;i<n;i++){
    scanf("%s%s",s1,s2);
    printf("%d\n",lcs(s1,s2));
  }
 return 0;
}




Measured memory_bytes: 5656
A, B, C = map(int, input().split())

if (A == B) and (B == C):
  print("No")
  quit()
  
if A == B:
  print("Yes")
  quit()
if B == C:
  print("Yes")
  quit()
if A == C:
  print("Yes")
  quit()
  
print("No")

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

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

  ll c1 = 0, c2 = 0, s1 = 0, s2 = 0;

  for(int i=0; i<n; i++){
    s1 += a[i]; s2 += a[i];
    if(s1 > 0 && i%2 == 1){
      c1 += s1+1;
      s1 = -1;
    }
    if(s1 < 0 && i%2 == 0){
      c1 += -s1+1;
      s1 = 1;
    }
    if(s2 < 0 && i%2 == 1){
      c2 += -s2+1;
      s2 = 1;
    }
    if(s2 > 0 && i%2 == 0){
      c2 += s2+1;
      s2 = -1;
    }
    if(s1 == 0){
      s1 = (i%2)? -1: 1;
      c1++;
    }
    if(s2 == 0){
      s2 = (i%2)? 1: -1;
      c2++;
    }
  }

  cout << min(c1, c2) << endl;

  return 0;
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int solve(vector<int> a)
{
    if(a[0] % 2 == 0 && a == vector<int>(3, a[0]))
        return -1;

    int ans = 0;
    for(;;){
        vector<int> b(3, 0);
        for(int i=0; i<3; ++i){
            if(a[i] % 2 != 0)
                return ans;
            for(int j=1; j<=2; ++j)
                b[(i+j)%3] += a[i] / 2;
        }
        a.swap(b);
        ++ ans;
    }
}

int main()
{
    vector<int> a(3);
    for(int i=0; i<3; ++i)
        cin >> a[i];

    cout << solve(a) << endl;

    return 0;
}


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

long long A;
long long B;
long long iCnt;
long long C;

void Chk( const string &S )
{
int i;
int iLen;
bool b;

	iLen = strlen( S.c_str() );
	if( S[ 0 ] == 'B' ) B++;
	if( S[ iLen - 1 ] == 'A' ) A++;
	if( S[ 0 ] == 'B' && S[ iLen - 1 ] == 'A' ) C++;

	b = (bool) ( S[ 0 ] == 'A' );
	for( i = 1; i < iLen; i++ )
	{
		if( b )
		{
			if( S[ i ] == 'B' ) iCnt++;
		}
		
		b = (bool) ( S[ i ] == 'A' );
	}
}

int main()
{
int i;
int N;
string S;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> N;

	for( i = 0; i < N; i++ )
	{
		cin >> S;

		Chk( S );
	}

	if( A == 0 )
		cout << iCnt << endl;
	else if( A == B && A == C )
		cout << iCnt + A - 1 << endl;
	else
		cout << iCnt + min( A, B ) << endl;

	return 0;
}






Measured memory_bytes: 256
// Author -- Frame
 
#include<bits/stdc++.h>
 
#define lowbit(x) ((x)&(-(x)))
#define Finline __inline__ __attribute__ ((always_inline))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back
 
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;
 
const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;
 
Finline uint rnd(){static uint seed=416;return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;}
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return (!b)?a:gcd(b,a%b);}
template <typename _Tp>Finline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>Finline void chmax(_Tp &a,const _Tp &b){(a<b)&&(a=b);}
template <typename _Tp>Finline void chmin(_Tp &a,const _Tp &b){(b<a)&&(a=b);}
template <typename _Tp>Finline void read(_Tp &x)
{
	char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	f&&(x=-x);
}
template <typename _Tp,typename... Args>Finline void read(_Tp &t,Args &...args){read(t);read(args...);}
template <typename _Tp,typename... Args>Finline _Tp min(const _Tp &a,const _Tp &b,const Args &...args){return a<b?min(a,args...):min(b,args...);}
template <typename _Tp,typename... Args>Finline _Tp max(const _Tp &a,const _Tp &b,const Args &...args){return a<b?max(b,args...):max(a,args...);}
Finline int read_str(char *s)
{
	char ch(getchar());while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;*tar=ch,ch=getchar();while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *(++tar)=ch,ch=getchar();
	return tar-s+1;
}
 
const int N=200005;
std::set<int> valid;
struct node{
	int pos,val;
	Finline bool operator < (const node &o)const
	{
		return pos<o.pos;
	}
};
std::multiset<node> S;
int dis[N],ans[N],A[N],B[N];
std::multiset<int> values;
int main()
{
	memset(ans,63,sizeof(ans));
	memset(dis,63,sizeof(dis));
	int n,m;read(n,m);
	for(int i=1;i<=n;++i) read(A[i],B[i]);
	for(int i=1;i<=m;++i) valid.insert(i);
	for(int i=1;i<=n+1;++i)
	{
		if(!valid.empty()) ans[i]=0;
		std::set<int>::iterator L=valid.lower_bound(A[i]),R=valid.upper_bound(B[i]);
		for(auto it=L;it!=R;++it) chmin(dis[i],B[i]-*it);
		valid.erase(L,R);
		
		std::set<node>::iterator _L=S.lower_bound((node){A[i],0}),_R=S.upper_bound((node){B[i],0});
		if(!values.empty()) chmin(ans[i],*values.begin());
		for(auto it=_L;it!=_R;++it)
		{
			chmin(dis[i],it->val+B[i]-it->pos);
			values.erase(values.find(it->val));
		}
		S.erase(_L,_R);
		if(B[i]<m)
		{
			S.insert((node){B[i]+1,dis[i]+1});
			values.insert(dis[i]+1);
		}
	}
	for(int i=1;i<=n+1;++i) ans[i]+=i-1;
	for(int i=2;i<=n+1;++i)
	{
		if(ans[i]>=1e6) ans[i]=-1;
		printf("%d\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 16176
def main():
	N, M = map(int, input().split())
	S = list(map(int, input().split()))
	T = list(map(int, input().split()))
	S.append(0)
	T.append(0)
	MOD = 10**9+7

	dp0 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp1 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp0[0][0] = 1
	for i in range(N+1):
		for j in range(M+1):
			dp0[i+1][j] += dp0[i][j]
			dp0[i+1][j] %= MOD
			dp1[i][j] += dp0[i][j]
			dp1[i][j] %= MOD
			dp1[i][j+1] += dp1[i][j]
			dp1[i][j+1] %= MOD

			if S[i] == T[j]:
				dp0[i+1][j+1] += dp1[i][j]
				dp0[i+1][j+1] %= MOD
	print(dp1[N][M])


if __name__ == '__main__':
	main()

Measured memory_bytes: 108124
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x;
    cin>>x;
    if(x>=30){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

struct drag {
    int a, b, c;
};

constexpr int INF = 1e9;

int main() {
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    vector<drag> v(N);
    for(int i=0; i<N; ++i) {
        cin >> v[i].a >> v[i].b >> v[i].c;
    }
    vector<vector<int>> tmp(401, vector<int>(401, INF));
    tmp[0][0] = 0;
    for(int i=0; i<1 << (N/2); ++i) {
        int x = 0, y=0, z=0;
        for(int j=0; j<N/2; ++j) {
            if(i & (1 << j)) {
                x += v[j].a;
                y += v[j].b;
                z += v[j].c;
            }
        }
        tmp[x][y] = min(tmp[x][y], z);
    }
    int res = INF;
    for(int i=0; i<1<<(N - N/2); ++i) {
        int x=0, y=0, z=0;
        for(int j=0; j<N - (N/2); ++j) {
            if(i & (1 << j)) {
                x += v[N/2 + j].a;
                y += v[N/2 + j].b;
                z += v[N/2 + j].c;
            }
        }
        for(int k=1; k*Ma <= 400 && k*Mb <= 400; ++k) {
            int Maa = k*Ma, Mbb = k*Mb;
            Maa -= x;
            Mbb -= y;
            if(Maa >= 0 && Mbb >= 0 && tmp[Maa][Mbb] != INF) {
                res = min(res, z + tmp[Maa][Mbb]);
            }
        }
    }
    if(res == INF) {
        cout << -1 << endl;
    } else {
        cout << res << endl;
    }
}


Measured memory_bytes: 896
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

class topological_sort {
private:
	int V;
	vector<vector<int>> edges;
	vector<int> in;
public:
	topological_sort(int n) :V(n), edges(n), in(n) {}
	topological_sort(vector<vector<int>> &edges) :V(edges.size()), in(edges.size()) { this->edges = edges; }

	void add_edge(int from, int to) { edges[from].emplace_back(to); }

	int build() {

		for (int i = 0; i < V; i++) for (const auto &e : edges[i]) in[e]++;
		vector<int> used(V), res;
		res.reserve(V);

		queue<int> que;
		for (int i = 0; i < V; i++) {
			if (in[i] == 0 && !used[i]) {
				used[i] = 1;
				que.emplace(i);
			}
		}

		while (!que.empty()) {
			int now = que.front();
			DMP(now, in);
			que.pop();
			res.emplace_back(now);
			for (const auto &e : edges[now]) {
				in[e]--;
				if (in[e] == 0) {
					if (used[e]) return -1; // unable to sort
					used[e] = used[now] + 1;
					que.emplace(e);
				}
			}
		}

		if (res.size() != V) return -1;
		else return *max_element(used.begin(), used.end());
	}

};

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	auto id = [&](int l, int r) { return min(l, r)*N + max(l, r); };

	topological_sort ts(N * N);
	for (int i = 0; i < N; i++) {
		vector<int> A(N - 1);
		for (int j = 0; j < N - 1; j++) cin >> A[j];
		for (int j = 0; j < N - 2; j++) ts.add_edge(id(i, A[j] - 1), id(i, A[j + 1] - 1));
	}

	cout << ts.build() << "\n";

	return 0;
}


Measured memory_bytes: 53032
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iostream>


using namespace std;

int main()
{
	int a[4], b[4];
	while (scanf("%d %d %d %d %d %d %d %d",
		a, a+1, a+2, a+3, b, b+1, b+2, b+3) != EOF)
	{
		set<int> included;
		for (int i = 0; i < 4; ++i)
			included.insert(a[i]);
		
		int hit, blow;
		hit = blow = 0;
		for (int i = 0; i < 4; ++i)
		{
			if (a[i] == b[i])
				++hit;
			else if (included.count(b[i]) > 0)
				++blow;
		}
		printf("%d %d\n", hit, blow);
	}
	
	return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL N;
  cin >> N;
  VL xs(N), ps(N);
  REP(i,N){
	cin >> xs[i] >> ps[i];
  }
  VL acc(N+1);
  REP(i,N) acc[i+1] = acc[i] + ps[i];
  VL B(N);
  REP(i,N) B[i] = acc[i+1] - xs[i];

  VL mxr(N);
  mxr[N-1] = B[N-1];
  for(int i=N-2;i>=0;--i){
	mxr[i] = max(B[i], mxr[i+1]);
  }

  LL lb = 0, ub = 1e15;
  while(ub-lb>1){
	LL L = (lb + ub) / 2;
	bool ok = false;
	REP(l,N){
	  if(mxr[l] >= L - xs[l] + acc[l]){
		ok = true;
		break;
	  }
	}
	if(ok) lb = L;
	else ub = L;
  }
  cout << lb << endl;

  return 0;
}


Measured memory_bytes: 8064
import sys
import math

def main():

    lst = []

    for line in sys.stdin:
        line = line.rstrip()
        a = int(line)
        lst.append(a)

    n = lst[0]
    a_to_e = lst[1:]

    # ボトルネック基準でやる
    bottle = min(a_to_e)

    # ボトルの場所
    ind = a_to_e.index(bottle)

    if n <= bottle:
        print(5)
        return 0

    ans = 5 + (n // bottle) - 1

    if n % bottle != 0:
        ans += 1
    print(ans)
    return 0

if __name__ == '__main__':
    sys.exit(main())


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

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

int main(){
    string s; cin >> s;
    int n = s.length();

    string count = "";
    ll ans = 0;
    int num = 0;

    while(num+1 < n){
        if(s[num] == 'A'){
            count += "A"; num++;
        }
        else if(count.length() && s[num] == 'B' && s[num+1] == 'C'){
            count += "D"; num++; num++;
        }
        else if(count.length()){
            int count2 = count.length();
          	ll jj = 0;
            rep(j,count2) if(count[j] == 'D') { ans += j-jj; jj++;}
            count = ""; num++;
        }
        else num++;
    }
    int count2 = count.length();
    ll jj = 0;
    rep(j,count2) if(count[j] == 'D') { ans += j-jj; jj++;}

    cout << ans << endl;
}



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

int main(){
    using namespace std;
    constexpr unsigned long MOD = 998244353;

    unsigned long N;
    cin >> N;
    vector<unsigned long> a(N);
    for(auto& i : a)cin >> i;

    unsigned long M = accumulate(a.begin(), a.end(), 0UL);
    vector<unsigned long> dp(M + 1), tapi(M + 1), tape(M + 1), tapa(M + 1);
    dp[0] = 1;
    tape[0] = 1;
    for(const auto i : a){
        transform(dp.begin(), dp.end(), tapi.begin(), [&MOD](auto a){auto tmp = a + a;return tmp - (tmp >= MOD) * MOD;});
        copy(tape.begin(), tape.end(), tapa.begin());
        for(unsigned long j = i; j <= M; ++j){
            (tapi[j] += dp[j - i]) %= MOD;
            (tape[j] += tapa[j - i]) %= MOD;
        }
        swap(tapi, dp);
    }

    auto modpow = [&MOD](unsigned long n){
        unsigned long a = 3, ret = 1;
        while(n){
            if(n & 1)(ret *= a) %= MOD;
            (a *= a) %= MOD;
            n >>= 1;
        }
        return ret;
    };

    auto tabu = accumulate(dp.begin() + (M + 1) / 2, dp.end(), 0UL);
    if(~M & 1)tabu += MOD - tape[M / 2];
    tabu %= MOD;

    cout << (modpow(N) + 3 * (MOD - tabu)) % MOD << endl;
}

Measured memory_bytes: 3072
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    cout << max(a-2*b,0);
        
    cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
void change(int n){
	int d=n/-2,r=n%-2;
	if(n){
		if(n<0&&r){d++;r=-r;}
		change(d);
		printf("%d",r);
	}
}
int main(void){
	int n;
	scanf("%d",&n);
	if(n){
		change(n);
	}
	else{
		printf("0");
	}
	return 0;
}

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

using namespace std;

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

    string s;
    cin >> s;

    if (s == "ABC")
        cout << "ARC\n";
    if (s == "ARC")
        cout << "ABC\n";
    
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	cout<<(n-2)/(k-1)+1<<endl;

	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
v = list(map(int, input().split()))
res = []
for i in range(K+1):
    for j in range(K-i+1):

        _v = v[::]
        stock = []
        stock.extend(_v[:i])
        _v = _v[i:]
        _v.reverse()
        stock.extend(_v[:j])
        stock.sort()
        for k in range(K-i-j+1):
            res.append(sum(stock[k:]))
print(max(res))

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int cnt[4]={};
    rep(i,3){
        int a,b;
        cin>>a>>b;
        a--;b--;
        cnt[a]++;cnt[b]++;
    }

    if(*max_element(cnt,cnt+4)==3){
        cout<<"NO"<<endl;
    }
    else{
        cout<<"YES"<<endl;
    }
    return 0;
}


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

int n, lim, a[500500], cnt;
map<int, int> mp;
vector<int> g[500500];

void dfs(int x) {
  for(int v : g[x]) {
    dfs(v);
  }
  a[x] = ++cnt;
}

int main(void) {
  scanf("%d%d", &n, &lim);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  mp[n + 1] = 0;
  for(int i = 1; i <= n; i++) {
    if(i > lim) {
      mp.erase(a[i - lim]);
    }
    g[(mp.upper_bound(a[i]))->second].push_back(i);
    mp[a[i]] = i;
  }
  dfs(0);
  for(int i = 1; i <= n; i++) {
    cout << a[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 48768
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string HEX = "0123456789ABCDEF";
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define Yn(b) puts(b?"Yes":"No")
#define YN(b) puts(b?"YES":"NO")

int main(void) {
    int n;
    cin >> n;
    int a,b,c,d;
    a = n/1000;
    b = (n % 1000)/100;
    c = (n % 100)/10;
    d = n % 10;
    if (a+b+c+d==7) {
        cout << a << '+' << b << '+' << c << '+' << d << "=7";
        return 0;
    }
    if (a+b+c-d==7) {
        cout << a << '+' << b << '+' << c << '-' << d << "=7";
        return 0;
    }
    if (a+b-c+d==7) {
        cout << a << '+' << b << '-' << c << '+' << d << "=7";
        return 0;
    }
    if (a+b-c-d==7) {
        cout << a << '+' << b << '-' << c << '-' << d << "=7";
        return 0;
    }
    if (a-b+c+d==7) {
        cout << a << '-' << b << '+' << c << '+' << d << "=7";
        return 0;
    }
    if (a-b+c-d==7) {
        cout << a << '-' << b << '+' << c << '-' << d << "=7";
        return 0;
    }
    if (a-b-c+d==7) {
        cout << a << '-' << b << '-' << c << '+' << d << "=7";
        return 0;
    }
    if (a-b-c-d==7) {
        cout << a << '-' << b << '-' << c << '-' << d << "=7";
        return 0;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;

ll X1[200005], X2[200005];
ll dp1[200005], dp2[200005];
ll Ans, L, N, A;

ll Max(ll a, ll b, ll c)
{
	return max(max(a, b), c);
}

int main()
{
	cin >> L >> N;

	X1[N + 1] = L;
	X2[N + 1] = L;

	for ( int i = 1; i <= N; i++ )
	{
		cin >> A;
		X1[i] = A;
		X2[N + 1 - i] = L - A;
	}

	dp1[0] = X1[N + 1] - X1[N];
	dp2[0] = X2[N + 1] - X2[N];

	Ans = Max(Ans, L - dp1[0], L - dp2[0]);

	for ( int i = 1; i < N; i++ )
	{
		dp1[i] = dp1[i - 1] + X1[N - ((i - 1) / 2)] + X1[N - (i / 2)] - 2 * X1[N - i];
		dp2[i] = dp2[i - 1] + X2[N - ((i - 1) / 2)] + X2[N - (i / 2)] - 2 * X2[N - i];
		Ans = Max(Ans, (i + 1)*L - dp1[i], (i + 1)*L - dp2[i]);
	}

	cout << Ans;
}

Measured memory_bytes: 6528
// https://atcoder.jp/contests/abc074/tasks/arc083_b

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 300;
const int A_JI_MAX = 1e9;

int N;
int A[N_MAX][N_MAX];

void solve() {
  ll ans = 0;
  REP(i, N) REP(j, N) {
    bool b = true;
    REP(k, N) {
      if (A[i][j] > A[i][k] + A[k][j]) {
        puts("-1");
        return;
      }
      if (i != j && j != k && k != i && A[i][j] == A[i][k] + A[k][j]) {
        b = false;
      }
    }
    if (b) ans += A[i][j];
  }
  printf("%lld\n", ans / 2);
}

void input() {
  scanf("%d", &N);
  REP(i, N) REP(j, N) scanf("%d", &A[i][j]);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 640