akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <stdexcept>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define debug(a) cout << (a) << endl
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;
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 (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}

ll M = 1000000007;

void solve()
{
	int n;
	cin>>n;
	set<int>a,b;
	map<int,ll>cnta,cntb;
	rep(i,n){
		int h;
		cin>>h;
		int ite=i+1;
		if(ite>=h){
			cntb[ite-h]++;
			b.insert(ite-h);
			//cout<<ite-h<<" "<<ite<<endl;
		}
		cnta[ite+h]++;
		//cout<<ite+h<<" "<<ite<<endl;
		a.insert(ite+h);
	}
	ll ans=0;
	for(auto i=a.begin(); i!=a.end();i++){
		int t=*i;
		ans+=(ll)cnta[t]*cntb[t];
	}
	cout<<ans<<endl;
}

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


Measured memory_bytes: 39588
H, W = [int(x) for x in input().split()]
A = [input().strip() for _ in range(H)]

B = []
for i in range(H):
    if "#" in A[i]:
        B.append(A[i])

ans = []
for j in range(W):
    for i in range(len(B)):
        if "#" ==  B[i][j]:
            ans.append(j)
            break

for i in range(len(B)):
    for j in ans:
        print(B[i][j], end="")
    print()






Measured memory_bytes: 9088
use std::io;

fn main() {
    let mut s = String::new();
    io::stdin().read_line(&mut s);
    let nm: Vec<_> = s.trim().split(' ').map(|x| x.parse().unwrap()).collect();

    let mut xs: Vec<(i64, bool)> = vec![(1, false); nm[0]];
    xs[0] = (1, true);
    for _ in 0..nm[1] {
        s = String::new();
        io::stdin().read_line(&mut s);
        let xy: Vec<usize> = s.trim().split(' ').map(|x| x.parse().unwrap()).collect();
        let nf: (i64, bool) = xs[xy[0] - 1];
        let mf: (i64, bool) = xs[xy[1] - 1];

        if nf.1 && nf.0 == 1 {
            xs[xy[0] - 1] = (0, false);
            xs[xy[1] - 1] = (mf.0 + 1, true);
        }
        else if nf.1 {
            xs[xy[0] - 1] = (nf.0 - 1, true);
            xs[xy[1] - 1] = (mf.0 + 1, true);
        }
        else {
            xs[xy[0] - 1] = (nf.0 - 1, false);
            xs[xy[1] - 1] = (mf.0 + 1, mf.1);
        }
    }

    let mut c = 0;
    for (_, f) in xs {
        if f {
            c += 1;
        }
    }

    println!("{}", c);
}


Measured memory_bytes: 1916
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
int main(){
    int n;
    while(cin >> n && n){
        vector<string> name(n), sup(n);
        vector<int> high(n), low(n);
        REP(i, n) cin >> name[i] >> high[i] >> sup[i] >> low[i];
        map<string, int> index;
        REP(i, n) index[ name[i] ] = i;
        vector<int> color(n, 0);
        int ans = 0;
        REP(i, n) if(color[i] == 0){
            vector<int> list;
            int u = i;
            while(color[u] == 0){
                list.push_back(u);
                color[u] = 1;
                u = index[ sup[u] ];
            }
            if(color[u] == 1){
                int min_sum = INT_MAX;
                bool in_roop = false;
                for(int h : list){
                    if(h == u) in_roop = true;
                    if(!in_roop) continue;
                    int sum = 0;
                    for(int li : list){
                        sum += (li == h ? high[li] : low[li]);
                    }
                    if(min_sum > sum) min_sum = sum;
                }
                ans += min_sum;
            }else if(color[u] == 2){
                for(int li : list){
                    ans += low[li];
                }
            }
            for(int li : list){
                color[li] = 2;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

int n, m;
int a[1000], b[1000], c[1000];
int dist[100][100];

bool check(int i) {
	for (int j = 0; j < n; j++) {	//始点
		for (int k = 0; k < n; k++) {	//終点
			if (dist[j][a[i]] + c[i] + dist[b[i]][k] == dist[j][k]) {
					return false;
			}
		}
	}
	return true;
}

int main() {
	int i, j, k;
	
	cin >> n >> m;
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) dist[i][j] = 1000000000;
	for (i = 0; i < n; i++) dist[i][i] = 0;
	
	for (i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;
		b[i]--;
		dist[a[i]][b[i]] = c[i];
		dist[b[i]][a[i]] = c[i];
	}
	
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			for (k = 0; k < n; k++)
				dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
	
	int ans = 0;
	for (i = 0; i < m; i++) {
		if (check(i)) {
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
ns=tuple(map(int,input().split()))

def rot(d, r):
    if r == 'N':
        return (d[1], d[5], d[2], d[3], d[0], d[4])
    if r == 'E':
        return (d[3], d[1], d[0], d[5], d[4], d[2])
    if r == 'W':
        return (d[2], d[1], d[5], d[0], d[4], d[3])
    if r == 'S':
        return (d[4], d[0], d[2], d[3], d[5], d[1])
    return d

ds = { ns }

while 1:
    d2 = { rot(d, r) for d in ds for r in list('NEWS') }.union(ds)
    if ds == d2: break
    ds = d2

q=int(input())
for _ in range(q):
    qs=list(map(int,input().split()))
    print([ d for d in ds if d[0] == qs[0] and d[1] == qs[1] ][0][2])

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

const int N = 200054;

int n;
char s[N], ans[N];
int next[N][26];
int f[N], go[N];

inline bool down(int &x, const int y) {return x > y ? x = y, 1 : 0;}

int main() {
	int i, j;
	scanf("%s", s), n = strlen(s);
	std::fill(next[n], next[n] + 26, n);
	for (i = n - 1; i >= 0; --i) memcpy(next[i], next[i + 1], 104), next[i][s[i] - 97] = i;
	f[n] = 1;
	for (i = n - 1; i >= 0; --i) {
		f[i] = INT_MAX;
		for (j = 0; j < 26; ++j) if (down(f[i], f[ next[i][j] + 1 ])) go[i] = j;
		++f[i];
	}
	for (j = i = 0; i <= n; i = next[i][ go[i] ] + 1) ans[j++] = go[i] + 97;
	return puts(ans), 0;
}

Measured memory_bytes: 22272
// https://atcoder.jp/contests/abc152/tasks/abc152_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    int res = 0;
    vector<vector<int>> num(10, vector<int>(10));
    for (int n = 1; n <= N; ++n) {
        vector<int> d;
        int nn = n;
        while (nn) {
            d.push_back(nn % 10);
            nn /= 10;
        }
        int a = d.front();
        int b = d.back();
        if (a > 0 && b > 0) {
            num[a][b]++;
        }
    }
    for (int a = 1; a < 10; ++a) {
        for (int b = 1; b < 10; ++b) {
            res += num[a][b] * num[b][a];
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N;
    int A[100000];
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    int prev_max = 1;
    long ans = A[0]-1;
    for(int i = 1; i < N; i++){
        int tmp = prev_max+1;
        if(A[i] == tmp){
            prev_max = tmp;
        }else if(A[i]%tmp == 0){
            ans += (A[i]/tmp-1);
        }else{
            ans += (A[i]/tmp);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1272
N = gets.to_i
ichi = gets.strip.split.map(&:to_i)
ary = []
m = ichi.min
n = ichi.max
i = 0

(m..n).each do |x|
  sum = 0
  (0..N-1).each do |j|
    sum += (x-ichi[j])**2
  end
  ary[x-m] = sum
end
puts ary.min

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

int main(){
	long long N;
	cin >> N;
	vector<long long> a(N);
	vector<long long> ans(N,0);
	for(auto &i:a)cin >> i;
	
	vector<pair<long long,int>> v;
	for(int i=0;i<N;i++)v.push_back(make_pair(a[i],i));
	
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	
	set<int> s;
	for(int i=0;i<N;i++){
		s.insert(v[i].second);
		ans[*s.begin()]+=(long long)(i+1)*(v[i].first-((i<N-1)?(v[i+1].first):(0)));
	}
	
	for(auto i:ans)cout << i << endl;
	return 0;
}

Measured memory_bytes: 8944
#include <iostream>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
using namespace std;

int main() {

    int A, B, C, D;
    cin >> A >> B >> C >> D;
    
    double m_Taka = C / B;
    double m_Aoki = A / D;
    if((int)C % (int)B != 0) m_Taka++;
    if((int)A % (int)D != 0) m_Aoki++;
    
    if(m_Taka > m_Aoki){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    
    //cout << m_Taka << " " << m_Aoki << endl;
    
    
}



Measured memory_bytes: 3132
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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








int n;
char s[11];

void dfs(int k, int u){
    if(k == n){
        printf("%s\n", s);
        return;
    }
    for(char c = 'a'; c <= 'a' + u; c++){
        s[k] = c;
        dfs(k + 1, c == 'a' + u ? u + 1 : u);
    }
}



int main(){
    scanf("%d", &n);
    dfs(0, 0);
}

Measured memory_bytes: 1536
using System;
using System.Collections.Generic;
using System.Linq;


namespace AtCoder
{
    partial class Program
    {
        static void Main(string[] args)
        {
			//↓



            var a = int.Parse(Console.ReadLine());
            var s = Console.ReadLine();
            if (a >=3200)
            {
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("red");
            }


			//↑
        }
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n, h;
    cin >> n >> h;
    vector<long long> b;
    long long amax = 0;
    REP(i, n)
    {
        long long ta, tb;
        cin >> ta >> tb;
        amax = max(ta, amax);
        b.push_back(tb);
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());

    long long cnt = 0;
    REP(i, n)
    {
        if (b[i] > amax)
        {

            h -= b[i];
            cnt++;
            if (h <= 0)
            {
                break;
            }
        }
        else
        {
            break;
        }
    }

    if (h > 0)
    {
        cnt += (h + amax - 1) / amax;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,x,n;cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >>a.at(i);
  }
  x=1;n=0;
  for (int i=0;i<N;i++){
    x=a.at(x-1);
    n++;
    if (x==2){break;}
  }
  if (x==2){cout <<n<<endl;}
  else {cout <<"-1"<<endl;}
}

Measured memory_bytes: 640
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using System.Threading.Tasks;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
    

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int AB = int.Parse(cin.next() + cin.next());
        int SQ = (int)Math.Sqrt(AB + 0.3);

        if (SQ * SQ == AB) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
    
}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}



Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = 10000000;
const long long INFL = (1LL<<50);
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};

template< typename T >
using Edges =vector< edge<T> >;
template< typename T >
using WeightedGraph =vector< Edges<T> >;
using UnWeightedGraph =vector< vector<int> >;
template< typename T >
using Matrix =vector< vector<T> >;

template< typename T >
vector< T > bellman_ford(Edges< T > &edges, int V, int s) {
    // ベルマンフォード法。O(V E)だが負辺があっても動作し、負の閉路がある場合は戻り値 dist に対して　dist.empty() == true。
    // それ以外の場合は各vertexへの最短距離を格納したvectorが戻る。
    const auto INF = numeric_limits< T >::max();
    vector< T > dist(V, INF);
    dist[s] = 0;
    for(int i = 0; i < V - 1; i++) {
        for(auto &e : edges) {
            if(dist[e.src] == INF) continue;
            dist[e.to] = min(dist[e.to], dist[e.src] + e.cost);
        }
    }
    
    T ds = dist[V-1];
    for(int i = 0; i<V-1;i++){
        for(auto &e : edges) {
            if(dist[e.src] == INF) continue;
            dist[e.to] = min(dist[e.to], dist[e.src] + e.cost);
        }
    }
    if(dist[V-1]< ds)return vector<T>();
    return dist;
}

int main() {
    int n,m;cin>>n>>m;
    Edges<ll> G;
    rep(i,m){
        int a, b;ll c;cin>>a>>b>>c;
        a--;b--;
        edge<ll> e(a,b,-c);
        G.push_back(e);
    }
    
    vector<ll> out = bellman_ford(G,n,0);
    
    if(out.size()==0)cout<<"inf"<<endl;
    else cout<<-out[n-1]<<endl;
    
    return 0;
}












Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define v(type) vector<type>

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

    int ans = INT_MAX;    
    for (int i = 1; i < n; i++) {
        string a = to_string(i);
        string b = to_string(n-i);
        int sum = 0;
        for (int i = 0; i < a.size(); i++) sum += a[i] - '0';
        for (int i = 0; i < b.size(); i++) sum += b[i] - '0';
        ans = min(ans, sum);
    }
    cout << ans << endl;
}

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

int main(){
  int a;
  cin >> a;
  cout << (a / 100) + ((a - (a / 100) * 100) / 10) + (a - (a / 100) * 100) - (((a - (a / 100) * 100) / 10) * 10) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(),(a).end()
#define N_MAX 1000
#define ll long long int
using namespace std;

int main() {
	ll N, M; cin >> N >> M;
	vector<pair<ll, ll>> AB(N);
	for (int i = 0; i < N; i++) {
		cin >> AB[i].first >> AB[i].second;
	}

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

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans += AB[i].first * min(AB[i].second, M); 
		M -= AB[i].second;
		if (M <= 0) break;
	}

	cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d,n,i,j,k=1,t[8][3]={0,0,0,1,1,1,0,0,1,0,1,0,1,0,0,1,1,0,1,0,1,0,1,1};
    cin>>n;
    a=n/1000;
    n=n-1000*a;
    b=n/100;
    n=n-100*b;
    c=n/10;
    n=n-10*c;
    d=n;
    for(i=0;i<8;++i)
    {
        n=a;
        for(j=0;j<3;++j)
        {
            if(j==0)
            {
                if(t[i][j]==1)n+=b;
                else n-=b;
            }
             if(j==1)
            {
                if(t[i][j]==1)n+=c;
                else n-=c;
            }
             if(j==2)
            {
                if(t[i][j]==1)n+=d;
                else n-=d;
            }
            if(n==7)
            {
                cout<<a;
                if(t[i][0]==1)cout<<"+";
                else cout<<"-";
                cout <<b;
                if(t[i][1]==1)cout<<"+";
                else cout<<"-";
                cout<<c;
                if(t[i][2]==1)cout<<"+";
                else cout<<"-";
                cout<<d<<"="<<n;
                k=0;
                break;
            }
        }
        if(k==0)break;
    }
    return 0;
}


Measured memory_bytes: 256
import glob
import numpy as np


# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\137\\A'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class A(Common):

    def resolve(self):

        tmp = [int(i) for i in self.input_data().split()]
        A = tmp[0]
        B = tmp[1]

        result = A + B
        if A - B > result:
            result = A -B
        if A * B > result:
            result = A * B

        print(str(result))


solver = A(REL_PATH)
solver.exec_resolve()

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

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

  int v,k;
  for(int j=1;j<=N;j++){
    for(int l=0;l<N-1;l++){
      cout << A[l] << " ";
    }
    cout << A[N-1] << endl;
    v = A[j];
    k = j - 1;
    while( k>=0 && A[k]>v){
      A[k+1] = A[k];
      k--;
    }
    A[k+1] = v;
  }
  
  return 0;
}

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

const int MAX=100005;
vector<long long int> S(MAX,10000000000),A(MAX),B(MAX);
int N,W;

void DP(int u){
    for(int j=1;j<=u;j++){
    for(int i=N*1000;i>=0;i--){
        if(i==0||(S[i]!=10000000000&&S[i]+A[j]<=W)) S[B[j]+i]=min(S[B[j]+i],S[i]+A[j]);
        }
    }
    int ans=0;
    for(int i=0;i<=N*1000;i++){
        if(S[i]!=10000000000) ans=i;
    }
    cout<<ans<<endl;
}

int main(){
    
    cin>>N>>W;
    for(int i=0;i<N;i++){
        cin>>A[i+1]>>B[i+1];
    }
    S[0]=0;
    DP(N);
}


Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map>
#include <map>
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
#include <memory>
#include <complex>
#include<fstream>
using namespace std;
typedef long long LL;

int main(void)
{
	int h,a;
	cin >>h>>a;
	if (h % a == 0) {
		cout <<h/a<<endl;
	}
	else {
		cout <<(h/a)+1<<endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}



int main(){
    ll N,K;
    string S;
    cin >> S;
    cin >> K;
    N = S.size();
    //vector<string> v;
    map<string,ll> mp;
    rep(i,N){
        rep(j,min(N-i,ll(5))){
            mp[S.substr(i,j+1)]++;
        }
    }
    //sort(v.begin(), v.end());
    //PR(v,10);
    ll id = 0;
    for(auto& e:mp){
        if(id == K-1){
            cout << e.first << endl;
        }
        id++;
    }
}

Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>

#define F first
#define S second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())


//INT_MAX
//INT_MIN
//LLONG_MAX
//LLONG_MIN
//DBL_MIN
//DBL_MAX
//LDBL_MIN
//LDBL_MAX

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    if (n % 4 == 0 || n % 7 == 0) {
        cout << "Yes" << endl;
    }else{
        bool flag = false;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (4 * i + 7 * j == n) {
                    flag = true;
                }
            }
        }
        if (flag) {
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    string S;
    cin >> S;
    bool ans = true;
    if(S.size() < 5){
        ans = false;
    }else{
        while(S.size() > 0){
            if(S.size() >= 7 && S.substr(S.size()-7, 7) == "dreamer"){
                S.erase(S.end()-7, S.end());
            }else if(S.size() >= 6 && S.substr(S.size()-6, 6) == "eraser"){
                S.erase(S.end()-6, S.end());
            }else if(S.size() >= 5 && (S.substr(S.size()-5, 5) == "dream" || S.substr(S.size()-5, 5) == "erase")){
                S.erase(S.end()-5, S.end());
            }else{
                ans = false;
                break;
            }
        }
    }

    if(ans == true){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }


    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    if(a==b)cout << "Yes"<<endl;
    else cout << "No"<<endl;
    return 0;
}


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

int main()
{
    int i, j, size, str;
    int *num; // 割り振られた領域のアドレスを格納するためのint型のポインタnumを宣言
    
    scanf("%d", &size);
    num = (int *)malloc(size * sizeof(int));
    if(num == NULL)exit(0);
    for(i=0; i < size; i++){
        scanf("%d", &num[i]);
    }
    for(i=0; i < size; i++){
        for(j=0; j < size; j++){ // 配列の内容を表示
            printf("%d", num[j]);
            if(j < size-1)printf(" ");
        }
        printf("\n");
        if(num[i] > num[i+1]){
            str = num[i+1];
            num[i+1] = num[i];
            num[i] = str;
            for(j=i; j > 0; j--){
                if(num[j-1] > num[j]){
                    str = num[j-1];
                    num[j-1] = num[j];
                    num[j] = str;
                }
                else break;
            }
        }
    }
    free(num);
    return 0;
}



Measured memory_bytes: 2036
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define ll long long
#define INF LLONG_MAX/3
#define P std::pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
int n,a[200010],b[200010],c[200010],d[200010];
signed main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	int ans=0;
	rep(i,30){
		int cnt=0;
		rep(j,n){
			c[j]=a[j];
			d[j]=b[j];
			c[j]%=((ll)1<<(i+1));
			d[j]%=((ll)1<<(i+1));
		}
		sort(d,d+n);
		rep(j,n){
			cnt+=lower_bound(d,d+n,((ll)1<<i)*2-c[j])-lower_bound(d,d+n,((ll)1<<i)-c[j]);
			cnt%=2;
			cnt+=lower_bound(d,d+n,((ll)1<<i)*4-c[j])-lower_bound(d,d+n,((ll)1<<i)*3-c[j]);
			cnt%=2;
		}
		if(cnt%2)ans+=((ll)1<<i);
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6528
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,a,b,c,d=LI()
  s=S()

  if '##' in s[a-1:c-1]:
    return 'No'
  if '##' in s[b-1:d-1]:
    return 'No'
  
  if d<c:
    # print(s[b-2:d+1])
    if '...' not in s[b-2:d+1]:
      return 'No'

  return 'Yes'

print(main())


Measured memory_bytes: 6312
//In the name of Allah 
#include <bits/stdc++.h>

using namespace std; 

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define int long long

const int N=3e5+100;

int a[N];

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int ans=0;
	int n; 
	cin>>n; 
	n*=3;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	int id=-1;
	for(int i=n-1;i>id;i-=2){
		id++;
		ans+=a[i-1];
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
constexpr auto INF = 1000000000;
constexpr auto LLINF = 1LL << 62;
constexpr auto mod = 1000000007;
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; }

ll gcd(ll a, ll b) {
    if (b == 0)return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;
    cout << b - a - (b / c + b / d - b / lcm(c, d) - (a / c + a / d - a / lcm(c, d))) << "\n";
}

Measured memory_bytes: 256
/* ex 7_1
   TakayukiY*/

#include<stdio.h>

typedef struct point{
    int x_elem;
    int y_elem;
} point;

point shift_point(point base,int x_diff,int y_diff){
    point shift;
    shift.x_elem=base.x_elem+y_diff;
    shift.y_elem=base.y_elem-x_diff;
    return shift;
}

int main(void){
    //各頂点
    point p1,p2,p3,p4;
    //頂点1・2間の各成分の差分
    int x,y;
    //代入
    scanf("%d%d%d%d",&p1.x_elem,&p1.y_elem,&p2.x_elem,&p2.y_elem);
    //1と2の差分を計算
    x=p1.x_elem - p2.x_elem;
    y=p1.y_elem - p2.y_elem;
    //p3,p4を復元
    p3=shift_point(p2,x,y);
    p4=shift_point(p1,x,y);
    //出力
    printf("%d %d %d %d",p3.x_elem,p3.y_elem,p4.x_elem,p4.y_elem);

    return 0;
}

Measured memory_bytes: 1712
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
a=N()
print(a+a*a+a**3)

Measured memory_bytes: 61916
import java.util.Scanner;

class Main{

static int ans = Integer.MAX_VALUE;
static int[] l;
static int A;
static int B;
static int C;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int N = sc.nextInt();
		A = sc.nextInt();
		B = sc.nextInt();
		C = sc.nextInt();
		l = new int[N];
		for(int i = 0;i < N;i++){
			l[i] = sc.nextInt();
		}
		
		//深さ優先探索　
		dfs(0,0,0,0,0);
		System.out.println(ans);
	}
	
	static void dfs(int sum,int index,int a,int b,int c){
		if(index == l.length){
			if(a == 0 || b == 0 || c == 0){
				return;
			}else{
				sum += Math.abs(a - A) + Math.abs(b - B) + Math.abs(c - C) - 30;
				ans  = Math.min(ans, sum);
				return;
			}
			
		}
		
		dfs(sum + 10, index+1, a+l[index], b, c);		//index番目の木をAの材料とする
		dfs(sum + 10, index+1, a, b+l[index], c);		//index番目の木をBの材料とする
		dfs(sum + 10, index+1, a, b, c+l[index]);		//index番目の木をCの材料とする
		dfs(sum, index+1, a, b, c);						//index番目の木を使わない

		
		
		
		
		
		
	}
}



Measured memory_bytes: 25172
let () =
  let open Queue in
  let (que : (string * int) Queue.t) = create () in
  let n, q = Scanf.scanf "%d %d\n" (fun n q -> n, q) in
  let rec read i =
    if i < n then (add (Scanf.scanf "%s %d\n" (fun s t -> s, t)) que; read (i + 1))
  in
  read 0;
  let rec doit cnt =
    if not (is_empty que) then begin
      let s, t = take que in
      let rest = t - q in
      if rest <= 0 then (let x = cnt + t in Printf.printf "%s %d\n" s x; doit x)
      else (add (s, rest) que; doit (cnt + q))
    end
  in
  doit 0

Measured memory_bytes: 12640
// ABC145C - Average Length

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

int main() {
	int N;
	cin >> N;
	int x[N], y[N];
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}

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

	double sum = 0.0;
	int no = 0;

	do {
		for (int i = 0; i < N - 1; i++) {
			sum += sqrt((x[p[i]]-x[p[i+1]])*(x[p[i]]-x[p[i+1]]) + (y[p[i]]-y[p[i+1]])*(y[p[i]]-y[p[i+1]]));
		}
		++no;
	} while (next_permutation(p, p + N));

	printf("%lf\n", sum / no);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lln long long int
#define llu unsigned lln
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define scd(n) scanf("%lf",&n);
#define pf(res) printf("%d\n",res);
#define pfl(res) printf("%lld\n",res);
#define pfd(res) printf("%lf\n",res);
#define maxii 200005
using namespace std;
typedef pair<int,int> pii;
typedef pair<lln,lln> pll;
 vector<int> vi[maxii];
 vector<int>::iterator child;
typedef vector<lln> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


int arr[maxii];
int arr2[maxii];


int main()
{
    char a;
    cin>>a;
    if(a=='a'|| a=='e'|| a=='i'|| a=='o'|| a=='u' )cout<<"vowel";
    else cout<<"consonant";
}






Measured memory_bytes: 8276
t=s=gets.chomp
ws=['dream','dreamer','erase','eraser']
l=s.length
loop do
  w = ws.detect { |w| l>=w.length && s.slice(l-w.length,w.length) == w }
  break if w.nil?
  l-=w.length
end
puts l == 0 ? 'YES' : 'NO'


Measured memory_bytes: 3964
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

typedef long long ll;

int gcd(int a, int b) {
	if (a < b) {
		int temp = a;
		a = b;
		b = temp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int gcd(int a, int b, int c) {
	return gcd(gcd(a, b), c);
}

int main() {
	int k;
	cin >> k;
	ll sum = 0;
	rep(i, k)rep(j, k)rep(h, k) {
		sum += gcd(i+1, j+1, h+1);
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long,long long>
#define mod 1000000007
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

ll power(ll a,ll b){
	ll ans=1;
	while(b>0){
		if(b%2!=0){
			ans=(ans*a)%mod;
		}
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
bool palin(string s){
	int i=0,j=s.size()-1;
	while(i<j){
		if(s[i]!=s[j])
		return false;
		i++;
		j--;
	}
	return true;
}

int main() {
	IOS;
	int t=1;
	//cin>>t;
	while(t--){
		double l;
		cin>>l;
		l/=3;
		cout<<fixed<<setprecision(7)<<l*l*l;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn][4],dp[maxn][4],t,ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
	}
	for(int i=1;i<=3;i++){
		dp[1][i]=a[1][i]; 
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=3;j++){
			t=-1;
			for(int k=1;k<=3;k++){
				if(k!=j){
					t=max(t,dp[i-1][k]);
				}
			}
			dp[i][j]=t+a[i][j];
		}
	}
	for(int i=1;i<=3;i++){
		ans=max(ans,dp[n][i]);
	}
	printf("%d",ans);
}

Measured memory_bytes: 3328
#include <stdio.h>

int r, c, p;

int main() {
  while((c = getchar_unlocked()) > 10) {
    if (c == p) {
      p = 1;
    }
    else {
      r += 1;
      p = p == 1 ? 0 : c;
    }
  }
  printf("%d\n", r);
}


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

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

ll const mod = 1e9+7;

int main() {
  int N,K,d,a;
  cin >> N >> K;
  set<int> cnt;
  rep(i,K) {
    cin >> d;
    rep(j,d) {
      cin >> a;
      cnt.insert(a);
    }
  }
  cout << -cnt.size() + N << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

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



int main(){
    int k,n;
    cin>>k>>n;
    int *A = new int [n];
    int *diff = new int [n];
    int min = k+1;
    forn(i,n){
        cin>>A[i];
    }
    for(int i = 0;i<n;i++){
        if(i == 0){
            int clock = A[n-1] -A[0];
            int anti = k-( A[1] - A[0]);
            if(clock<min){
                min = clock;
            }
            if(anti<min){
                min = anti;
            }
        }else if(i==n-1){
            int clock = A[n-1] -A[0];
            int anti = A[n-1] - A[0];
            if(clock<min)
                min = clock;
            if(anti<min)
                min = anti;
        }else{
            int clock = k - ( A[i] - A[i-1] );
            if(clock < min)
                min = clock;
            int anti = k - ( A[i+1]-A[i] );
            if(anti < min)
                min = anti;
        }
    }
    cout<<min<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
#define pb push_back
#define NeedForSpeed ios_base::sync_with_stdio(0), cin.tie(0)
#define PI acos(-1)
#define all(c) c.begin(), c.end()
#define SET(x, y) memset((x), y, sizeof(x))
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const ll INF64 = 1e18;

template <typename T>
string to_string(const vector<T> &v) {
  string ret = "<";
  for (auto it : v) {
    ret += to_string(it) + ", ";
  }
  ret.pop_back(); ret.pop_back();
  ret += ">";
  return ret;
}

void debug_print() { cerr << endl; }

template <typename T, typename ...U>
void debug_print(T t, U... u) {
  cerr << " " << to_string(t);
  debug_print(u...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_print(__VA_ARGS__)
const int N = 1e5 + 5;

int main() {
  ll x;
  cin >> x;
  ll cur = 100;
  ll now = 0;
  while (cur < x) {
    now++;
    cur += (cur / 100);
  }
  cout << now << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

/* modとる */
inline ll modu(ll a){
    return(a % mod + mod) % mod;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll N , K;
    cin >> N >> K;
    ll answer = 0;
    for(ll i = K;i < N+2;i++){
        answer = modu(answer + i*(N-i+1) + 1);
    }
    cout << answer << "\n";
}

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

int main()
{
    int n, mi = MOD, m = 0;
    cin >> n;
    ll sum = 0;
    rep(i, n)
    {
        int a;
        cin >> a;
        sum += abs(a);
        if (a < 0)
            m++;
        mi = min(mi, abs(a));
    }
    if (m % 2 == 0)
        cout << sum << endl;
    else
        cout << sum - 2 * mi << endl;
}

Measured memory_bytes: 256
program main
  
  implicit none
  integer :: a(3)  ,i
  
  read(*,*) a
  do i = 1, 3
    if ( a(i) /= 5 .and. a(i) /= 7 ) then
      print*, "NO"
      stop
    end if
  end do
  

  if( sum( a ) == 17 ) then 
    print*, "YES"
  else
    print*, "NO"
  end if
end program main


Measured memory_bytes: 256
def checkA(s):

    l = len(s)
    if l % 2 == 0:
        return False

    ll = (l-1)//2

    for i in range(ll):
        if s[i] != "=" or s[l-1-i] != "=":
            return False

    if s[ll] != "#":
        return False

    return True

def checkB(s):
    l = len(s)

    if l % 2 == 1:
        return False

    ll = l // 2
    for i in range(ll):
        if s[2*i] != "Q" or s[2*i+1] != "=":
            return False

    return True

def check(s):
    if len(s) < 6:
        return "NA"

    if s[0:2] == ">'" and s[-1:] == "~":
        if checkA(s[2:-1]):
            return "A"
        else:
            return "NA"

    if s[0:2] == ">^" and s[-2:] == "~~":
        if checkB(s[2:-2]):
            return "B"
        else:
            return "NA"

    return "NA"

N = int(input())

for i in range(N):
    s = input()
    print(check(s))


Measured memory_bytes: 5628
#include<stdio.h>
#include<iostream>

using namespace std;
int main(){
    long long x,a,b;
    cin>>x>>a>>b;
    if(a>=b) cout<<"delicious";
    else{
        if(b-a<=x) cout<<"safe";
        else cout<<"dangerous" ;
    }

    return 0;
}


Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var s = Console.ReadLine().Trim();
        var a = new int[n];
        var b = new int[n];
        var count = 0; var cmax = -99999999; var imax = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'E') count++;
            a[i] = count;
            b[i] = i + 1 - a[i];
            if (a[i] - b[i] > cmax) { imax = i; cmax = a[i] - b[i]; }
        }
        int ret;
        if (imax == 0) ret = a[n - 1] - a[imax];
        else if (imax == n - 1) ret = b[imax];
        else ret = b[imax] + (a[n - 1] - a[imax]);
        Console.WriteLine(ret);
    }
}

Measured memory_bytes: 14432
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cmin = min(C)
    for i in range(N+1):
        C[i] -= cmin  # offset
    cmax = max(C)+1
    fw = FenwickTree(cmax)
    cnt = 0
    for i in range(N+1):
        cnt += fw.sum(C[i])
        fw.add(C[i], 1)

    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)


Measured memory_bytes: 123048
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int main(){
  string s;
  cin >> s;

  int first_size = s.size();

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

  auto itr = s.find("1");
  auto itr0 = s.find("0");
  string s0, s1;
  if(itr == string::npos || itr0 == string::npos || s.size() == 1) {
    cout << 0 << endl;
    return 0;
  }

  s0 = s.substr(0, itr);
  s1 = s.substr(itr, s.size()-1);

  auto after_size = max(s0.size(), s1.size()) - min(s0.size(), s1.size());
  cout << first_size - after_size << endl;

  return 0;
}


Measured memory_bytes: 3848
#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define D                double
#define F                first
#define S                second
#define pb               push_back
#define pf               push_front
#define MP               make_pair
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define it(it,mp)        for(auto it=mp.begin() ; it!=mp.end() ; it++)
#define IOS              ios_base :: sync_with_stdio(false); cin.tie(NULL);
const int N = 1e5 + 5;
const int inf = 1e9 + 1;
const double eps = 1e-15;
const double EPS = 1e-9;
const double PI = acos(-1.0);
typedef long long int                   ll;
typedef pair<int,int>                   PII;
int main()
{
    IOS
    ll n , h , a,  b ;
    cin >> n >> h ;
    vector<PII>v;
    for(int i=0 ; i<n ; i++){
        cin >>a>>b;
        v.pb({a,1});
        v.pb({b,0});
    }
    sort_d(v);
    ll need= 0;
    for(int i=0 ; i<v.size() ; i++){
        if(v[i].S){
           if(h <= v[i].F){
            need++;
            break;
           }
           else if(h%v[i].F==0){
               need = need + h/v[i].F;
               break;
           }
           else{
                need = need + h/v[i].F;
                need++;
               break;
           }
        }
        else{
            if(h <= v[i].F){
                need++;
                break;
            }
            else{
                h-=v[i].F;
                need++;
            }
        }
    }
    cout<<need;
}



Measured memory_bytes: 2420
#pragma GCC optimize("O3")
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdlib>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#include <iomanip>
#include<unordered_set>
constexpr auto INF = 9223372036854775807;
typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned long int ul;
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i+=1)
#define endl '\n'
#define all(x) x.begin(),x.end()
using namespace std;
inline int mex(unordered_set<int> st)
{
	int m = 0;
	while (st.find(m) != st.end())
	{
		m += 1;
	}
	return m;
}
inline int calculateGrundy(int n)
{
	if (n == 1)
		return 0;
	unordered_set<int> mexi;
	for (int i = 1; i <= sqrt(n); i += 1)
	{
		if (n % i == 0)
		{
			if(n/i!=n)
				mexi.insert(calculateGrundy(n/i));
			mexi.insert(calculateGrundy(i));
		}
	}
	return mex(mexi);
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n, a, b;
	cin >> n >> a >> b;
	ll ans = n % (a + b);
	ll chk = a*(n / (a + b));
	chk += min(a, ans);
	cout << chk;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <numeric> 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
#define fi first
#define se second
 
#define p 1000000007
 
using namespace std;
 
typedef long long ll;
 
int A[100];
int B[101];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n-1;i++){
		cin >> A[i];
	}
	for(int i=1;i<n-1;i++){
		B[i] = min(A[i-1], A[i]);
	}
	B[0] = A[0];
	B[n-1] = A[n-2];
	cout << accumulate(B, B+n, 0LL) << endl;
	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

ll dp[55][2];

int main() {
  int N,P;
  cin >> N >> P;
  vector<int> A(N);
  rep(i,N) { cin >> A[i]; A[i] %= 2; }
  dp[0][0] = 1;
  rep(i,N) {
    rep(j,2) {
      dp[i+1][j] += dp[i][j];
      dp[i+1][(j+A[i])%2] += dp[i][j];
    }
  }
  cout << dp[N][P] << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

ll a[200100];

int main(void)
{
  ll k, n;
  cin >> k >> n;
  REP(i, n) cin >> a[i];

  ll lmax = k-a[n-1]+a[0];
  REP(i, n-1) {
    ll l = a[i+1]-a[i];
    if(lmax < l) lmax = l;
  }
  cout << k - lmax << endl;

}


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

int main(){
  int n,h,m,s;
  cin >> n;

  h = n / 3600;
  m = n % 3600 / 60;
  s = n % 3600 % 60;

  cout << h << ':' << m << ':' << s << endl;
}

Measured memory_bytes: 1160
import sys
sys.setrecursionlimit(10**9)

n, c, k = map(int, input().split())
t = sorted([int(input()) for _ in range(n)])


def AirportBus(x=0,ans=0):
    y = x
    for i in range(x, n):
        if t[x]+k < t[i] or i - x >= c:
          y = i
          break
    if y == x:
      print(ans+1)
      return
    ans += 1
    AirportBus(y,ans)
    
AirportBus()

Measured memory_bytes: 116184