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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pp;

#define mod 1000000007

int H, N;
vector<int> A(1001), B(1001);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    ll dp[H + 1];
    fill(dp, dp + H + 1, 1e9);
    dp[H] = 0;
    for (int h = H; h > 0; h--) {
        for (int i = 0; i < N; i++) {
            if (dp[h] != 1e9) {
                int hh = max(h - A[i], 0);
                dp[hh] = min(dp[hh], dp[h] + B[i]);
            }
        }
    }
    cout << dp[0] << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(a) (a).begin(),(a).end()
 
using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;
 
const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

struct UnionFind {
    vector<ll> parent;
    vector<ll> usize;
 
    UnionFind(int n) : parent(n), usize(n, 1LL){
        rep(i, n)parent[i]=i;
    }
    
    int root(int x){
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }
    
    bool issame(int x, int y){
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
 
        if(x == y)return false;
 
        if(parent[x] > parent[y]) swap(x, y);

        usize[x] += usize[y];
        parent[y] = x;
 
        return true;
    }
    
    int size(int x) {
        return usize[root(x)];
    }
};

int main(){
    ll v, e;
    cin >> v >> e;

    vector<ll> s(e), t(e), w(e);
    rep(i, e)cin >> s[i] >> t[i] >> w[i];

    vector<ll> ord(e);
    iota(ALL(ord), 0);
    sort(ALL(ord), [&](ll x, ll y){
        return w[x] < w[y];
    });

    UnionFind uf(v);

    ll ans = 0;
    rep(i, e){
        if(!uf.issame(s[ord[i]], t[ord[i]])){
            ans += w[ord[i]];
            uf.merge(s[ord[i]], t[ord[i]]);
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 6272
/* Simplicity and Goodness */
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//             tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 2e5+2;


void solve()
{   
    int n, h;
    scn(n); scn(h);

    int b[n], a_max = 0;

    rep(i, 0, n) {
        int a;
        scn(a); scn(b[i]);
        a_max = max(a_max, a);
    } 
        
    sort(b, b+n, greater<int>()); int cnt = 0;

    rep(i, 0, n) {
        if(h <= 0)
            break;

        if(b[i] >= a_max)
            h -= b[i], cnt ++;
        else
            break;
    }

    if(h > 0)
        cnt += (h + a_max - 1) / a_max;

    prin(cnt);
}

int main()
{
    int t = 1;
    // scn(t);

    while(t --) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4180
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> d(n);
  for(int i=0;i<n;++i) cin>>d[i];
  reverse(d.begin(),d.end());
  for(int i=0;i<n;++i){
    if(i) cout<<" ";
    cout<<d[i];
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3104
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#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 FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#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)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素


int main(){

    int A, B;
    cin >> A >> B;
    cout << A*B << endl;


}

Measured memory_bytes: 3596
# C
import sys

N = int(input())
left = 0
right = N-1
ans_left = ''
ans_right = ''

cnt = 0

print(0)
cnt += 1
s = input()
ans_left = s

if s != "Vacant":
    print(N-1)
    cnt += 1
    s = input()
    ans_right = s


    
while s != "Vacant" and cnt < 20:
    
    # find which is unusual
    mid = (left + right) // 2
    print(mid)
    cnt += 1
    s = input()
    
    m = (mid - left) % 2
    if m == 0:
        if ans_left != s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    else:
        if ans_left == s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    

Measured memory_bytes: 3660
N=gets.to_i

l = N.to_s.length
n = ['3','5','7']
m = ['3','5','7']
2.upto(l) do |i|
    tmp = []
    m.each do |j|
        n.each do |k|
            if k.length == i-1
                tmp << k + j
            end
        end
    end
    n += tmp
end

ans = 0
n.each do |v|
    if v.include?('3') && v.include?('5') && v.include?('7')
        if v.to_i <= N
            ans += 1
        end
    end
end
puts ans


Measured memory_bytes: 4220
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int a, b;
	
	cin>>a>>b;
	
	if(a <= 0 && b >= 0) cout<<"Zero"<<endl;
	else if(a >= 0) cout<<"Positive"<<endl;
	else {
		if((b-a)%2) cout<<"Positive"<<endl;
		else cout<<"Negative"<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int x = 0;
  int y = 0;
  int money = 0;
  scanf("%d %d",&x,&y);
  if(x == 3){
    money += 100000;
  }else if(x == 2){
    money += 200000;
  }else if(x == 1){
    money += 300000;
  }
  if(y == 3){
    money += 100000;
  }else if(y == 2){
    money += 200000;
  }else if(y == 1){
    money += 300000;
  }
  if( x == 1 && y == 1){
    money += 400000;
  }
  printf("%d",money);
  return 0;
}
  


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

int main(){
  int x, n;

  n = 1;
  while (1) {
    cin >> x;
    if (x == 0) {
      break;
    }
    cout << "Case " << n << ": " << x << endl;
    n++;
  }

  return 0;
}


Measured memory_bytes: 2988
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s; cin >> s;
  FOR(i,0,s.length()-8) {
    cout << s[i];
  }
  cout << endl;
  return 0;
}

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

using namespace std;

#define int long long 
#define INF 21000000000

signed main(){
		int n;
		cin >> n;
		vector<int> a;
		vector<int> b;
		vector<int> c;
		for(int i=0;i<n;i++){
				int tmp;
				cin >> tmp;
				a.push_back(tmp);
		}
		for(int i=0;i<n;i++){
				int tmp;
				cin >> tmp;
				b.push_back(tmp);
		}
		for(int i=0;i<n-1;i++){
				int tmp;
				cin >> tmp;
				c.push_back(tmp);
		}
		int ans = accumulate(b.begin(),b.end(),0);
		for(int i=0;i<n;i++){
				if(i != 0 && a[i-1] + 1 == a[i]) ans += c[a[i-1]-1];
		}
		cout << ans << endl;
}



Measured memory_bytes: 256
X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
eat=p[:X]+q[:Y]+r
eat.sort(reverse=True)
eat=eat[:(X+Y)]
print(sum(eat))

Measured memory_bytes: 22720
import itertools
N, M, Q = map(int, input().split())
P = [[int(x) for x in input().split()] for _ in range(Q)]

li = [x for x in range(1, M+1)]
Com = itertools.combinations_with_replacement(li, N)

ans=0
for com in Com:
    reg=0
    for a,b,c,d in P:
        if com[b-1] - com[a-1] == c:
            reg += d
    ans = max(reg, ans)
print(ans)

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
    return 0;
}

Measured memory_bytes: 3604
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	//数値の入力
		int n = sc.nextInt();
      	//配列
        int num[] = new int[n];
        for(int i = 0; i < n; i++){
        	num[i] = sc.nextInt();
        }
      	//カウント用
        int count = 0;
      	//添え字が「小中大」もしくは「大中小」でn[i]が真ん中
      	//（エラーが出たのでforの条件修正）
        for(int i = 1; i < n-1; i++){
        	if((num[i]>num[i-1] && num[i]<num[i+1]) || (num[i]>num[i+1] && num[i]<num[i-1])){
            	count++;
            }
        }
        System.out.println(count);
     }
}

Measured memory_bytes: 35608
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <cassert>

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

using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;

int main() {
    int a = 0;
    int b = 0;
    char x;
    REP(i,3){
        cin >> x;
        if (x == '5') a++;
        if (x == '7') b++;
    }
    if (a == 2 && b == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int num = 1000000;
const int m = 13;
int i, a[num], n, cnt = 0, G[m], j, p, cn = -1, v;
inline void insertionSort(int g) {
	for (i = g; i < n; i++) {
		int j = i - g;
		int v = a[i];
		while (j >= 0 && a[j] > v) {
			a[j + g] = a[j];
			j -= g;
			cnt++;
		}
		a[j + g] = v;
	}
}
void shellSort() {
	int h = 1;
	for(int i = 0; h <= n; i++){
		G[i] = h;
		h = h * 3 + 1;
		cn++;
	}
	v = cn;	for (int i = cn; i >= 0; i--) {
		insertionSort(G[i]);
	}
}
int main(){
	cin >> n;
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	shellSort();
	cout << v + 1 << endl;
	for (i = v; i >= 0; i--) {
		printf("%d", G[i]);
		if(i != 0)printf(" ");
	}
	cout << endl << cnt << endl;
	for(i = 0; i< n; i++)printf("%d\n", a[i]);
	return 0;
}

Measured memory_bytes: 7108
n = int(input())
lis = [int(i) for i in input().split()]
alice = 0
bob =0


for i in range(n):
  curmax = max(lis)
  lis.remove(curmax)
  if i%2 == 0:
    alice += curmax
  else:
    bob += curmax
    
print(alice-bob)

Measured memory_bytes: 3060
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main() {

    int N,M; cin>>N>>M;
    vector<int> contest(N,0);
    int AC=0;
    int WA=0;
    for (int i = 0; i < M; ++i) {
        int p; cin>>p;
        string S; cin>>S;
        if(contest[p]!=-1){ //未提出のとき
            if(S == "AC"){
                AC++;
                WA += contest[p];
                contest[p] = -1;
            }else contest[p]++;
        }
    }

    cout<<AC<<" "<<WA<<endl;

    return 0;

}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    double l;
    cin >> l;
    double ans =  pow(l/3, 3);
    printf("%.9f\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main()
{
    scanf("%d",&n);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i%3==0||i%5==0) continue;
        ans+=i;
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 3816
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        if(a-b >= 0){
            System.out.println("delicious");
        }else if(b-a <= x){
            System.out.println("safe");
        }else{
            System.out.println("dangerous");
        }
    }
}


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

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

vector<ll> divisors(ll n)
{
    vector<ll> ds;

    for (ll i = 1; i * i <= n; ++i)
    {
        if (n % i)
            continue;

        ds.push_back(i);

        ll k = n / i;

        if (k != i)
            ds.push_back(k);
    }

    sort(ds.begin(), ds.end(), greater<ll>());

    return ds;
}

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll cost(ll y, const vector<ll>& xs)
{
    const ll oo { 1LL << 62 };
    ll c = 0, last = 0;

    vector<ll> rs(xs.size());

    for (size_t i = 0; i < xs.size(); ++i)
        rs[i] = xs[i] % y;

    sort(rs.begin(), rs.end());

    int L = 0, R = xs.size() - 1;

    while (L <= R)
    {
        if (last <= 0)
        {
            c += rs[L];
            last += rs[L++]; 
        } else
        {
            last -= (y - rs[R--]);
        }
    }

    return last ? oo : c;
}

ll solve(ll, ll K, const vector<ll>& xs)
{
    ll sum = 0, d = xs[0];
    
    for (auto x : xs)
    {
        sum += x;
        d = gcd(d, x);
    }

    auto ys = divisors(sum);

    for (auto y : ys)
    {
        auto c = cost(y, xs);
#ifdef DEBUG
cout << "y = " << y << ", c = " << c << endl;
#endif
        if (c <= K)
            return y;
    }

    return d;
}

int main()
{
    ios::sync_with_stdio(false);

    ll N, K;
    cin >> N >> K;

    vector<ll> xs(N);

    for (int i = 0; i < N; ++i)
        cin >> xs[i];

    auto ans = solve(N, K, xs);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
/*
...........__________    							 |										    ___  __
.............|       |     						     |											 |   /
.............|       |     						     |									  		 |  /
.............|       |                               |                         __                | /      _______
.............|_______|  _______            _______   |______   ________   /|  /  |               |/       |      |
.............| \               | |      | |          |      |          | / | /   |               |\       |
.............|  \       _______| |      | |_______   |      |   _______|   |/    |               | \      |
.............|   \      |      | |      |         |  |      |  |       |   |     |               |  \     |
.........  __|    \__|  |______| |______| ________|  |      |_ |_______|   |     |__|           _|   \__ _|        .

*/
#include<bits/stdc++.h>
using namespace std ;
#define int 				long long
#define ull 				unsigned long long int
#define ld 					long double
#define vi 					vector<int>
#define vii 				vector<pair<int,int>>
#define vvi 				vector<vector<int>>
#define pf 					push_front
#define popb 				pop_back
#define pb 					push_back
#define eb 					emplace_back
#define pii 				pair<int,int>
#define prec(x) 			fixed<<setprecision(15)<<x
#define all(x) 				x.begin(),x.end()
#define rall(x) 			x.rbegin(),x.rend()
#define mset(a,b) 			memset(a,b,sizeof(a))
#define mcpy(a,b) 			memcpy(a,b,sizeof(a))
#define fo0(i,n) 			for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) 			for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) 			for(int i=a,i##end=b;i<=i##end;i++)
#define foe(i,x)			for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)			for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define inf 1e18
const int mod=1e9+7;
const int N=4e5+10;

void solve(){
	int n,k;
	cin>>n>>k;
	int r,sc,p;cin>>r>>sc>>p;
	string s;cin>>s;
	int pos[n];
	mset(pos,-1);
	int ans=0;
	fo0(i,k){
		if(s[i]=='r'){
			ans+=p;
			pos[i]=1;
		}
		else if(s[i]=='s'){
			ans+=r;
			pos[i]=2;
		}
		else{
			ans+=sc;
			pos[i]=3;
		}
	}
	for(int i=k;i<n;i++){
		if(s[i]=='r'){
			if(pos[i-k]!=1){
				pos[i]=1;
				ans+=p;
			}
		}
		else if(s[i]=='s'){
			if(pos[i-k]!=2){
				pos[i]=2;
				ans+=r;
			}
		}
		else{
			if(pos[i-k]!=3){
				pos[i]=3;
				ans+=sc;
			}
		}
	}
	cout<<ans;
}

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

}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
#define double  float
//#define int long long int

//priority queue of minimum data is created 


signed main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
  int n;
  cin>>n;
  string s;
  cin>>s;
  int cnt=1;
  for(int i=0;i<s.length()-1;i++)
  {
    if(s[i+1]!=s[i])
    {
      cnt++;
    } 
  }
  cout<<cnt;
  
  
 return 0;

}

Measured memory_bytes: 512
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		S = "A" + S;
		if( S.length()==3 ){
			System.out.println(S.charAt(1)==S.charAt(2)?1+" "+2:"-1"+" "+"-1");          
        }else{          
		for( int i=1; i<=S.length()-3; i++ ){
			char ch1 = S.charAt(i);
			char ch2 = S.charAt(i+1);
			char ch3 = S.charAt(i+2);
			if( ch1==ch2 || ch1==ch3 || ch2==ch3 ){
				System.out.println(i+" "+(i+2));
				break;
			}
			if( i==S.length()-3 ){
				System.out.println("-1"+" "+"-1");
			}
		}
        }          
	}
}


Measured memory_bytes: 27100
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  int N,Q;
  cin>>N>>Q;
  vector<pair<lint,pair<int,int> > > m;
  REP(i,N){
    int S,T,X;
    cin>>S>>T>>X;
    m.push_back(make_pair(S-X,make_pair(X,1)));
    m.push_back(make_pair(T-X,make_pair(X,-1)));
  }
  sort(ALL(m));
  set<lint> s;
  lint D[Q];
  REP(i,Q){
    cin>>D[i];
  }
  auto itr=m.begin();
  REP(i,Q){
    while(itr->first<=D[i] and itr!=m.end()){
      if(itr->second.second==1)s.insert(itr->second.first);
      else s.erase(itr->second.first);
      itr++;
    }
    if(s.empty())cout<<-1<<endl;
    else cout<<*s.begin()<<endl;
  }

  return 0;
}


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

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

  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;

  vector<int> nums;
  int cnt = 0;
  int now = 1;
  rep(i, n) {
    if(s[i] == (char) '0' + now) cnt++;
    else {
      nums.push_back(cnt);
      cnt = 1;
      now = 1 - now;
    }
  }

  if(cnt != 0) nums.push_back(cnt);
  if(nums.size() % 2 == 0) nums.push_back(0);

  int add = k * 2 + 1;
  int ans = 0;

  int left = 0;
  int right = 0;
  int tmp = 0;

  for(int i = 0; i < nums.size(); i += 2) {
    int nextLeft = i;
    int nextRight = min(i + add, (int)nums.size());

    while(nextLeft > left) {
      tmp -= nums[left];
      left++;
    }
    while(nextRight > right) {
      tmp += nums[right];
      right++;
    }
    ans = max(ans, tmp);
  }

  cout << ans << endl;
}


Measured memory_bytes: 1020
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class ABC126_A
    {
        static void Main(string[] args)
        {
            string[] str1 = Console.ReadLine().Split(' ');
            int k = int.Parse(str1[1]);
            string str2 = Console.ReadLine();
            string str3;
            if(k == 1)
            {
                str3 = char.ToLower(str2[k - 1]) + str2.Substring(1);
            }
            str3 = str2.Substring(0, k-1) + char.ToLower(str2[k-1]) + str2.Substring(k);
            Console.Write(str3);
        }
    }
}


Measured memory_bytes: 13140
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

const int INF = 1050000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int N_MAX = 2010;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

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

int main() //input->compute->output
{
        int a;
        string s;

        cin >> a >> s;

        if (a >= 3200)
        {
                cout << s;
        }
        else
        {
                cout << "red";
        }

        return 0;
}

Measured memory_bytes: 256
# define _CRT_SECURE_NO_WARNINGS 1
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
//# define M_PI 3.141592
# define INF ((int)(1<<30))
# define FOR(i,n) for(int i=0;i<(int)n;i++)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define toRad 2.0*M_PI/360.0
# define inin(x) int x;cin>>x;
# define all(x) x.begin(),x.end()
# define debug(x) cout<<#x<<" :"<<x<<endl;
# define rep(i,n) for(int i=0;i<(int)n;i++)
# define EPS 1e-12
# define CHECK(i,a) FOR(i,a.size())cout<<#a<<"["<<i<<"] : "<<a[i]<<endl; 
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int dx[4] = { 0,-1,1,0 }, dy[4] = { 1,0,0,-1 };

int n, m;
double d[22][22];
double memo[1 << 20];
double dp(int bit)
{
	int t = 0;
	for (int i = 0; i < n; i++)if (bit & 1 << i)t++;
	if (t == m)return 0.0;
	if (memo[bit] >=0)return memo[bit];
	double ans = 0.0;
	for (int i = 0; i < n; i++)
	{
		if (!(bit & 1 << i))
		{
			double temp = 0.0;
			for (int j = 0; j < n; j++)
			{
				if (bit & 1 << j)
				{
					temp += d[i][j];
				}
			}
			ans = max(ans, temp + dp(bit | 1 << i));
		}
	}
	return memo[bit]=ans;
}

int main()
{
	cin >> n >> m;
	FOR(i, 1 << 20)memo[i] = -1;
	double L[22], A[22], B[22];
	FOR(i,n)
	{
		cin >> L[i] >> A[i] >> B[i];
	}
	FOR(i,n)
	{
		FOR(j,n)
		{
			d[i][j] =
				(L[i] - L[j])*(L[i] - L[j]) +
				(A[i] - A[j])*(A[i] - A[j]) +
				(B[i] - B[j])*(B[i] - B[j]);
		}
	}
	printf("%.8f\n", dp(0));
}

Measured memory_bytes: 11500
sx, sy, tx, ty = map(int, input().split())

xdist = abs(tx - sx)
ydist = abs(ty - sy)

rt1 = "U" * ydist + "R" * xdist
rt2 = "D" * ydist + "L" * xdist
rt3 = "L" + "U" * (ydist + 1) + "R" * (xdist + 1) + "D"
rt4 = "R" + "D" * (ydist + 1) + "L" * (xdist + 1) + "U"
print(rt1 + rt2 + rt3 + rt4)


Measured memory_bytes: 3060
def isEven( num )
    return num % 2 == 0 ? true : false
end

def initializeStr()
    cnt = STDIN.gets
    inputstring = STDIN.gets
    array = inputstring.split(" ")

    array.each{|str|
        num = str.to_i()
        isEven(num) ? $evenArray.push(num) : $oddArray.push(num)
    }
end

$oddArray = Array.new()
$evenArray = Array.new()

initializeStr()
if(!isEven($oddArray.size()))
    puts "NO"
else 
    puts "YES"
end

Measured memory_bytes: 8644
N = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return None
	if 0 == a % b:
		return b
	return gcd(b, a % b)

l, r = [A[0]], [A[-1]]
for n in range(1, N):
	l += [gcd(l[-1], A[n])]
	r += [gcd(r[-1], A[N - n - 1])]
r = r[::-1]

list_gcd = [l[-2], r[1]]
for n in range(N - 2):
	list_gcd += [gcd(l[n], r[n + 2])]

#print(l)
#print(r)
#print(list_gcd)

print(max(list_gcd))


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

using namespace std;
typedef pair<int,int> P;

int main() {
    int i,j,a,n,p,q,temp;
    int t=0;
    int flag=0;
    string s;
    cin>>a>>p;
    temp=3*a+p;
    cout<<temp/2;
    return 0;
}


Measured memory_bytes: 764
import java.util.*;import java.io.*;import java.math.*;

public class Main
{

    public static void process()throws IOException
    {
        long n=nl();
        long res=n/500l*1000l;
        res+=(n%500l)/5*5;
        pn(res);
    }


       static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;

        //oj = System.getProperty("ONLINE_JUDGE") != null;
        if(!oj) sc=new AnotherReader(100);

        long s = System.currentTimeMillis();
        int t=1;
        while(t-->0)
            process();
        out.flush();
        if(!oj)
            System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static boolean multipleTC=false;



/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
    
    
    

Measured memory_bytes: 23124
package main
/* 
aaa
*/
import (
        "bufio"
        "fmt"
        "os"
	"strconv"
	"math"
)

func main() {

        stdin := bufio.NewScanner(os.Stdin)
        stdin.Scan()
        a := stdin.Text()
        n,_ := strconv.Atoi(a)
	fmt.Println(float64(n)*2*math.Pi)
}


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



int main() {
    int N,M;
    cin>>N>>M;
    vector<int> A(N);
    rep(i,N)cin>>A.at(i);
    int total=0;
    rep(i,N){
        total+=A.at(i);
    }
    total--;
    total/=(4*M);total++;
    int count=0;
    rep(i,N){
        if(A.at(i)>=total){
            count++;
        }
    }
    if(count>=M){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main(void) {
    string S;
    unsigned long long int N, count = 0;
 
    cin >> S;
    
    N = S.length();
    
    for(int i = 0 ; i < N ; i++){
        if(S[i] == 'o'){
            count++;
        }
    }
    
    if(count + 15 - N >= 8){
        cout << "YES" << endl;
    }
    else{
	    cout << "NO" << endl;
    }
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

int main(){
    int A, B;
    cin >> A >> B;
    cout << max(max(A+B, A-B), A*B) << endl;
    return 0;
}


Measured memory_bytes: 256
H, W, N = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
dic = {}
for l in L:
  try:
    dic[l[0]].append(l[1])
  except:
    dic[l[0]] = [l[1]]
def get(H, N):
  if N == 0:
    return H
  area = 1.
  for i in range(1, H):
    try:
      for block in sorted(dic[i+1]):
        if 1 <= block and block <= area:
          return i
      if not area+1 in dic[i+1]:
        area += 1
    except:
      area = area+1
  return H
print(get(H, N))

Measured memory_bytes: 81380
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    tetrahedral_num = [i*(i+1)*(i+2)//6 for i in range(1, 201)]
    tetrahedral_num_odd = [i for i in tetrahedral_num if i%2==1]
    n = []
    while True:
        tmp = int(input())
        if tmp==0:
            break
        else:
            n.append(tmp)
    max_n = max(n)

    # dp[i]: 数iを構成する最小個数
    dp = [float('inf')]*(max_n+1)
    dp[0] = 0
    for i in range(1, max_n+1):
        tmp = []
        for j in tetrahedral_num:
            if i-j>=0:
                tmp.append(dp[i-j])
        dp[i] = min(tmp) + 1

    dp_odd = [float('inf')]*(max_n+1)
    dp_odd[0] = 0
    for i in range(1, max_n+1):
        tmp = []
        for j in tetrahedral_num_odd:
            if i-j>=0:
                tmp.append(dp_odd[i-j])
        dp_odd[i] = min(tmp) + 1

    for i in n:
        print(dp[i], dp_odd[i])

if __name__ == '__main__':
    resolve()


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

int main() {
    int s;  cin >> s;
    vector<bool> seq(1e6+1, false);

    int cnt = 1;
    while (!seq[s]) {
        seq[s] = true;
        if (s % 2 == 0) s /= 2;
        else s = 3 * s + 1;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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 T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



int N;
double A, B, C;
double P[2100];

int main() {
    while (cin >> N >> A >> B >> C) {
        for (int i = 0; i < N; ++i) cin >> P[i];
        sort(P, P+N, greater<double>());
        
        double tot = C;
        double pr = A;
        
        double res = tot/pr;
        for (int i = 0; i < N; ++i) {
            tot += P[i];
            pr += B;
            chmax(res, tot/pr);
        }
        
        cout << (int)(res) << endl;
    }
    return 0;
}


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

int INF = 1e9;
int main() {
    int n, m, rr;
    cin >> n >> m >> rr;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    vector<int> r(rr);
    for (int i = 0; i < rr; i++) cin >> r[i];
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        dist[a][b] = dist[b][a] = c;
    }
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int ans = INF;
    sort(r.begin(), r.end());
    do {
        int sum = 0;
        for (int i = 0; i < rr - 1; i++) sum += dist[r[i] - 1][r[i + 1] - 1];
        ans = min(ans, sum);
    } while (next_permutation(r.begin(), r.end()));
    cout << ans << endl;
    return 0;
}


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

int main() {
  string s;
  int count = 0;
  cin >> s;
  int a,z;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'A') {
      a = i-1;
      break;
    }
  }
  for (int i = s.size()-1; i >= 0; i--) {
    if (s.at(i) == 'Z') {
      z = i;
      break;
    }
  }
  cout << z - a << endl;
}

Measured memory_bytes: 640
#pragma GCC optimize(2)
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include<cstring>
#include <stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include <string>
const int maxn = 1000 * 100;
const int maxa = 1000 * 1000 * 1000 + 7;
typedef long long ll;
const int mod = 1000 * 1000 * 1000 + 7;
using namespace std;
int t, n, m, T,d;
int main()
{
#ifdef _DEBUG
	freopen("E:\\input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	int i, j;
	std::ios::sync_with_stdio(false); cin.tie(0);
	while (cin >> n>>d) {
		int D = 2 * d + 1;
		if (n % D == 0) {
			cout << n / D << "\n";
		}else{
			cout << n / D +1<< "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define l(s) (s*2)
#define r(s) (s*2+1)
using namespace std;
int tp,n,q,s,w[200010],a[200010];
map<int,int> mp;
long long ad;
struct segs
{
	long long m1[1000100],m2[1000100],m3[1000100];
	void build(int ql,int qr,int root=1)
	{
		if (ql==qr) {m1[root]=1e18-w[ql];m2[root]=1e18+w[ql];m3[root]=1e18;return;}
		int mid=(ql+qr)>>1;
		build(ql,mid,l(root));build(mid+1,qr,r(root));
		m1[root]=min(m1[l(root)],m1[r(root)]);
		m2[root]=min(m2[l(root)],m2[r(root)]);
		m3[root]=min(m3[l(root)],m3[r(root)]);
	}
	void modify(int s,long long p,int root=1,int pl=1,int pr=tp)
	{
		if (pl==pr) {m1[root]=p-w[pl];m2[root]=p+w[pl];m3[root]=p;return;}
		int mid=(pl+pr)>>1;if (s<=mid) modify(s,p,l(root),pl,mid);else modify(s,p,r(root),mid+1,pr);
		m1[root]=min(m1[l(root)],m1[r(root)]);
		m2[root]=min(m2[l(root)],m2[r(root)]);
		m3[root]=min(m3[l(root)],m3[r(root)]);
	}
	long long getmin1(int ql,int qr,int root=1,int pl=1,int pr=tp)
	{
		if ((pl==ql)&&(pr==qr)) return m1[root];
		int mid=(pl+pr)>>1;long long ans=1e18;
		if (ql<=mid) ans=min(ans,getmin1(ql,min(mid,qr),l(root),pl,mid));
		if (qr>mid) ans=min(ans,getmin1(max(mid+1,ql),qr,r(root),mid+1,pr));
		return ans;
	}
	long long getmin2(int ql,int qr,int root=1,int pl=1,int pr=tp)
	{
		if ((pl==ql)&&(pr==qr)) return m2[root];
		int mid=(pl+pr)>>1;long long ans=1e18;
		if (ql<=mid) ans=min(ans,getmin2(ql,min(mid,qr),l(root),pl,mid));
		if (qr>mid) ans=min(ans,getmin2(max(mid+1,ql),qr,r(root),mid+1,pr));
		return ans;
	}
	long long getmin3(int ql,int qr,int root=1,int pl=1,int pr=tp)
	{
		if ((pl==ql)&&(pr==qr)) return m3[root];
		int mid=(pl+pr)>>1;long long ans=1e18;
		if (ql<=mid) ans=min(ans,getmin3(ql,min(mid,qr),l(root),pl,mid));
		if (qr>mid) ans=min(ans,getmin3(max(mid+1,ql),qr,r(root),mid+1,pr));
		return ans;
	}
}seg;
int main()
{
	scanf("%d%d%d%d",&n,&q,&s,&a[0]);mp[a[0]]=0;mp[s]=0;
	for (int i=1;i<=q;i++) {scanf("%d",&a[i]);mp[a[i]]=0;}
	tp=0;for (map<int,int>::iterator it=mp.begin();it!=mp.end();it++) it->second=++tp;
	for (int i=0;i<=q;i++) {w[mp[a[i]]]=a[i];a[i]=mp[a[i]];}
	w[mp[s]]=s;s=mp[s];
	seg.build(1,tp);
	seg.modify(s,0);
	for (int i=1;i<=q;i++)
	{
		long long d=min(seg.getmin1(1,a[i])+w[a[i]],seg.getmin2(a[i],tp)-w[a[i]])+ad;
		ad+=abs(w[a[i-1]]-w[a[i]]);
		seg.modify(a[i-1],d-ad);
	}
	printf("%lld\n",seg.getmin3(1,tp)+ad);
}

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

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define N 111111

const int INF = 1 << 30 ;
typedef long long ll ;
typedef pair < int , int > pii ;

int main() {
  int n, ans = 0 , mx = 0 ;
  string s ;
  scanf("%d",&n) ;
  cin>>s ;

  for(int i = 0 ;i<n ;i++){
    if(s[i] == 'I') ans+=1 ;
    else ans-=1 ;
    mx = max(mx , ans) ;
  }
  cout << mx << endl ;	
  return 0 ;
}



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

#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

typedef long long ll;
const int mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

void solve()
{
  int n; cin >> n;
  vector<string> s(n);
  for (int i=0; i<n; i++) {
    cin >> s[i];
  }
  int a=0,b=0;
  int ab=0;
  bool flg = true;
  for (int i=0; i<n; i++) {
    int aa = !!(s[i][SZ(s[i])-1]=='A');
    int bb = !!(s[i][0]=='B');
    a += aa;
    b += bb;
    if ((aa && !bb) || (!aa && bb)) flg=false;
    for (int j=0; j<SZ(s[i])-1; j++) {
      ab += !!(s[i].substr(j,2) == "AB");
    }
  }
  int aab = min(a,b);
  if (flg&&aab>0) aab--;
  cout << ab+aab << endl;
}

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


Measured memory_bytes: 768
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

typedef long long ll;
inline void read(ll &T) {
	ll x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

ll x;

ll qpow(ll a,ll b) {
	ll ans=1,base=a;
	while(b) {
		if(b&1) ans=ans*base;
		base=base*base;
		b>>=1;
	}
	return ans;
}

int main() {
	read(x);
	for(ll i=-200;i<=200;++i) {
		for(ll j=-200;j<=200;++j) {
			if(qpow(i,5)-qpow(j,5)==x) {
				std::cout<<i<<" "<<j<<'\n';
				return 0;
			}
		}
	}
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;

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

    int n, m;
    cin >> n >> m;

    int ans = n*(n-1) / 2 + m*(m-1) / 2;
    cout << ans << endl;

    return 0;
}


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

long long n, m, k, t, w = 0;
long long a[200001], b[200001];

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

	a[0] = 0;

	for (int i = 0; i < n; i++) {
		cin >> t;
		a[i + 1] = a[i] + t;
	}
	
	b[0] = 0;

	for (int i = 0; i < m; i++) {
		cin >> t;
		b[i + 1] = b[i] + t;
	}

	long long j = 0;

	for (long long i = n; i >= 0; i--) {		
		while (j < m && a[i] + b[j] < k) {
			w = max(w, i + j);
			j++;			
		}

		if(a[i] + b[j] == k)
			w = max(w, i + j);
	}

	cout << w << endl;
}


Measured memory_bytes: 6752
class SegTree:
	"""
	1-indexed
	"""
	def __init__(self,size,funcComp,funcUpd,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = funcComp		# suppose to min or max
		self.updateFunc = funcUpd		# suppose to add or update
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		# num:size以上の最小の2のべき乗
		self.datSize = 2**size.bit_length()

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		"""
		i: index(1-indexed)
		bottom-up
		"""
		# i -= 1	# 1-orderで指定され、内部では0-Order想定?
		# i += (self.datSize - 1)
		i += self.datSize
		self.datTree[i] = self.updateFunc(self.datTree[i],val)
		while 0 < i:
			i >>= 1
			self.datTree[i] = self.compareFunc( self.datTree[i<<1|0], self.datTree[i<<1|1] )

	def query(self,a,b):
		""" get minimun/maximum value of range[a,b)
		non-recursive
		bottom-up
		all 1-indexed
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:

			if b & 1:
				# shrink right
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b])

			if a & 1:

				# shrink left
				ret = self.compareFunc(ret, self.datTree[a])
				a += 1

			a >>= 1; b >>= 1

		return ret

	def printLeaf(self):
		print(self.datTree[self.datSize-1:])

def update(x,val):
	return val


def LongestSeaquence(A,K):
	N = len(A)
	lis = 0

	# === Range Maximum Query ===
	MAX_A = max(A)
	tree = SegTree(MAX_A,max,update,0,-1e18)
	# tree.update( 0, 1 )

	for n in range(N):
		x = A[n]
		l = max(0,x-K)
		r = min(MAX_A,x+K)
		tmp = tree.query(l,r+1)+1
		tree.update( x, tmp )
		# lis = max(lis, tmp)

	lis=tree.query(0,MAX_A)

	return lis

def main():
	N,K = map(int,input().split())
	A = [ int(input()) for _ in range(N)]

	print(LongestSeaquence(A,K))



if __name__ == "__main__":
	main()

Measured memory_bytes: 166884
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod        1000000007 
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod;}
ll power(ll x, ll y){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod-2);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<ll> >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    if(a.first==b.first)
    return (a.second < b.second);
    return (a.first < b.first); 
} 
ll ans=0;
vector<ll>root;
void calldfs(ll v,int visit[])
{
 visit[v]=1;
 for(int i=0;i<m1[v].size();i++)
 {
  if(visit[m1[v][i]]==0)
  {
   calldfs(m1[v][i],visit);
  }
 }
}
void dfs(ll n)
{
 ll i;
 int visit[1000000]={0};
 fli(i,1,n+1)
 {
  visit[i]=0;
 }
 fli(i,1,n+1)
 {
  if(visit[i]==0)
  {
   calldfs(i,visit);
   ans++;
  } 
 }
}
void comp()
{
 ll n,i,k,temp;
 string s;
 cin>>n>>k>>s;
 fl(i,n)
 {
  if(i==k-1)
  {
   temp=s[i]-'A';
   s[i]='a'+temp;
  }
  
 }
 cout<<s<<"\n";
} 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

Measured memory_bytes: 256
"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] o(1000)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもmax7*7*3通り)o(1000) 
    どうやってもO(10**6)には入りそう
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var value int
  fmt.Scanf("%d", &value)
  
  if value % 1000 == 0 {
    fmt.Print(0)
  } else {
    var tmp = int(value / 1000) + 1
    
    fmt.Printf("%d", 1000 * tmp - value)
  }
}


Measured memory_bytes: 1832
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Maybe

main = do
  n <- fst . fromJust . BS.readInt <$> BS.getLine
  as <- sort . zipWith (\x y -> y - x) [1 ..] <$> unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  let c = as !! (div n 2)
  print $ sum $ map (\x -> abs (x - c)) as

Measured memory_bytes: 35288
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;

using ll = long long;

int main()
{
    ll N;
    cin >> N;
    ll sum = 0;
    for(ll i = 1;i <= N;i++)
    {
        ll a;
        cin >> a;
        if(i % 2 == 1 && a % 2 == 1)sum++;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3100