akhauriyash/Code-Regression huggingface dataset:
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
// clang-format on

using State = tuple<int, int, int>;
using D = double;
using P = pair<D, State>;

const D INF = 1e7;
const D eps = 1e-7;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

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

    int h, w, k;
    cin >> h >> w >> k;

    int sy, sx, gy, gx;
    cin >> sy >> sx >> gy >> gx;
    --sy;
    --sx;
    --gy;
    --gx;

    vector<string> c(h);
    rep(i, h) cin >> c[i];

    auto OK = [&](int y, int x) {
        return 0 <= y && y < h && 0 <= x && x < w && c[y][x] == '.';
    };

    vector<vector<vector<D>>> dp(h, vector<vector<D>>(w, vector<D>(4, INF)));
    priority_queue<P, vector<P>, greater<P>> pq;
    rep(i, 4) {
        dp[sy][sx][i] = 0;
        pq.push({0, {sy, sx, i}});
    }

    while (!pq.empty()) {
        P now = pq.top();
        pq.pop();

        State s = now.se;
        int y = get<0>(s), x = get<1>(s), d = get<2>(s);
        D val = dp[y][x][d];
        if (now.fi - eps > val) continue;

        int ny = y + dy[d], nx = x + dx[d];
        if (OK(ny, nx)) {
            D ndp = val + 1.0 / k;
            if (dp[ny][nx][d] - eps > ndp) {
                dp[ny][nx][d] = ndp;
                pq.push({ndp, {ny, nx, d}});
            }
        }

        rep(i, 4) {
            D ndp = ceil(val - eps);
            if (dp[y][x][i] - eps > ndp) {
                dp[y][x][i] = ndp;
                pq.push({ndp, {y, x, i}});
            }
        }
    }

    D mn = INF;
    rep(i, 4) mn = min(mn, dp[gy][gx][i]);

    int ans = (int)(ceil(mn - eps) + eps);
    if (abs(mn - INF) < eps) ans = -1;
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 144960
H, W = map(int,input().split())
s = []*H
flag = 0
tmp = 0
ans = ''
t = [-1,0,1]
for i in range(H):
    s.append(input())

for i in range(H):
    ans =''
    for j in range(W):
        if s[i][j] == '.':
            tmp = 0
            for k in t:
                for m in t:
                    try:
                        if s[i-k][j-m] == '#' and i-k != -1 and j-m != -1:
                            tmp += 1
                    except IndexError:
                        pass
            ans += str(tmp)
        else:
            ans += '#'
    print(ans)


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

using pii = pair<int, int>;

// 0-indexed
template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n) : n(n), dat(n, 0) {}

    void add(int i, T value) {
        for(; i<n; i |= i + 1) {
            dat[i] += value;
        }
    }

    T sum(int i) const {
        T res = 0;
        for(; i>=0; i = (i & (i+1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) const {
        return sum(r-1) - sum(l-1);
    }

private:
    const int n;
    std::vector<T> dat;
};


int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> ls(n + 1);
    for(int i = 0; i < m; ++i) {
        int L, R;
        cin >> L >> R;
        ls[R].push_back(L - 1);
    }
    vector<vector<pii>> qs(n + 1);
    for(int i = 0; i < q; ++i) {
        int p, q;
        cin >> p >> q;
        qs[q].emplace_back(p - 1, i);
    }

    vector<int> ans(q);
    fenwick_tree<int> bit(n + 1);
    for(int r = 1; r <= n; ++r) {
        for(auto& l : ls[r]) {
            bit.add(l, 1);
        }
        for(auto& q : qs[r]) {
            ans[q.second] = bit.sum(q.first, r);
        }
    }

    for(auto& x : ans) {
        cout << x << endl;
    }
}


Measured memory_bytes: 3712
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	 //cin.tie(0);
	//ios::sync_with_stdio(false);
	//std::cout << std::fixed;
	//std::cout << std::setprecision(12);
	//std::cout << std::defaultfloat;
	int n;
	cin>>n;
	vector<int> a(n);
	priority_queue<int> p;
	priority_queue<int> ng;
	LL ans=0;
	FOR(i,0,n){
		cin>>a[i];
		if(a[i]>=0){
			p.push(-a[i]);
			ans+=a[i];
		}else{
			ng.push(a[i]);
			ans+=-a[i];
		}
	}
	int sz=ng.size();
	if(sz%2==1){
		if(p.empty()){
			ans-=-ng.top()*2;
		}else if(-p.top()>-ng.top()){
			ans-=-ng.top()*2;
		}else{
			ans-=-p.top()*2;
		}
	}else{

	}
	cout<<ans;

	return 0;
}


Measured memory_bytes: 1404
import sys
from collections import defaultdict

N, X, D = map(int, input().split())

if D == 0:
  print(1 if X == 0 else N + 1)
  sys.exit()

if D < 0:
  X *= -1
  D *= -1

dic = defaultdict(list)

for i in range(N + 1):
  l = X*i + i*(i-1)//2*D
  r = X*i + (N-1+N-1-(i-1))*i//2*D
  dic[l % D].append((l // D, r // D + 1))

ans = 0
for v in dic.values():
  v.sort()
  ima = -10**100
  for l, r in v:
    if ima < l:
      ans += r - l
      ima = r
    elif r > ima:
      ans += r - ima
      ima = r
print(ans)



Measured memory_bytes: 86540
num = int(input())
B_seq = list(map(int,input().split()))
#print(num)
#print(B_seq)
A_seq=[]
#A_seq[0]=B_seq[0]
for i in range(0,num-1):
    A_seq.append(B_seq[i])
#A_num=seq[num-2]
#print(A_seq)
A_seq.insert(0,B_seq[0])
#print(A_seq)
cnt = 0
for j in range(num-1):
    if max(A_seq[j],A_seq[j+1])<=B_seq[j]:
        pass
    else:
        A_seq[j]=A_seq[j+1]
#print(A_seq)
cnt=0
for x in range(num):
    cnt = cnt+A_seq[x]
print(cnt)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<set>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int t,a[maxn];
int main(){
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<k;i++){
        ans+=a[i];
    }
    printf ("%d\n",ans);




}



Measured memory_bytes: 3220
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

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



int main(void){

	int N, T, A; cin >> N >> T >> A;
	int H;
	int ans = 1;
	double min_value = 10000000;
	REP(i,N){
		cin >> H;
		double ave_temp = T - (H*0.006);
		if(abs(ave_temp-A) < min_value){
			min_value = abs(ave_temp-A);
			ans = i+1;
		}
	}

	cout << ans << endl;


		return 0;

}


Measured memory_bytes: 256
/* template.cpp [[[ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)s)
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)s)
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
ll in(){ ll x; cin >> x; return x; }
vector<ll> in(size_t n){ vector<ll> v(n); each(x, v) cin >> x; return v; }
/* ]]] */

int n, m;
string s[100];

int main(){
  cin >> n >> m;
  rep(i, n) cin >> s[i];
  int res = 0;
  rep(i, 1, n) rep(j, m){
    if (s[i][j] != '-') continue;
    bool f = true;
    if (j - 1 >= 0 && s[i][j - 1] != '-') f = false;
    if (j + 1 < m && s[i][j + 1] != '-') f = false;
    rep(k, 8){
      int ii = i + dx[k];
      int jj = j + dy[k];
      if (ii < 0 || n <= ii) continue;
      if (jj < 0 || m <= jj) continue;
      if (s[ii][jj] == 'x') f = false;
    }
    if (f) res++;
  }
  cout << res << endl;
}

Measured memory_bytes: 3252
#include <bits/stdc++.h>
#define fixed fixed_
using namespace std;

int T, n, fa1[55], fa2[55], ind[55];
bool fixed[55];
vector<int> g1[55], g2[55], g[55];

void dfs1(int u) {
	for (int v : g1[u])
		if (v != fa1[u]) {
			fa1[v] = u;
			dfs1(v);
		}
}
void dfs2(int u) {
	for (int v : g2[u])
		if (v != fa2[u]) {
			fa2[v] = u;
			dfs2(v);
		}
}
void dfs3(int u) {
	fixed[u] = true;
	vector<int> tmp(g1[u].size() + g2[u].size());
	merge(g1[u].begin(), g1[u].end(), g2[u].begin(), g2[u].end(), tmp.begin());
	for (int i = 1; i < tmp.size(); ++i)
		if (tmp[i] == tmp[i - 1] && tmp[i] != fa1[u]) dfs3(tmp[i]);
}

int solve(int rt) {
	for (int i = 1; i <= n; ++i) g[i].clear(), ind[i] = fixed[i] = 0;
	fa1[rt] = 0, dfs1(rt);
	fa2[rt] = 0, dfs2(rt);
	dfs3(rt);
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (i == rt) continue;
		if (fa1[i] == fa2[i]) {
			if (!fixed[i]) return n;
			continue;
		}
		++cnt;
		if (!fixed[fa1[i]]) g[i].push_back(fa1[i]), ++ind[fa1[i]];
		if (!fixed[fa2[i]]) g[fa2[i]].push_back(i), ++ind[i];
	}
	static int q[55];
	int st = 0, ed = 0;
	for (int i = 1; i <= n; ++i) if (!ind[i]) q[ed++] = i;
	while (st < ed) {
		int u = q[st++];
		for (int v : g[u]) if (!--ind[v]) q[ed++] = v;
	}
	return ed == n ? cnt : n;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) g1[i].clear(), g2[i].clear();
		set<pair<int, int>> s1, s2;
		for (int i = 1, x, y; i < n; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) swap(x, y);
			s1.emplace(x, y);
			g1[x].push_back(y), g1[y].push_back(x);
		}
		for (int i = 1, x, y; i < n; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) swap(x, y);
			s2.emplace(x, y);
			g2[x].push_back(y), g2[y].push_back(x);
		}
		if (s1 == s2) {
			puts("0");
			continue;
		}
		for (int i = 1; i <= n; ++i) sort(g1[i].begin(), g1[i].end()), sort(g2[i].begin(), g2[i].end());
		int ans = n + 1;
		for (int rt = 1; rt <= n; ++rt)
			if (g1[rt].size() == 1) {
				int v = g1[rt][0];
				g1[rt].clear();
				g1[v].erase(lower_bound(g1[v].begin(), g1[v].end(), rt));
				for (int i = 1; i <= n; ++i) {
					if (i == v) continue;
					g1[rt] = {i};
					g1[i].insert(lower_bound(g1[i].begin(), g1[i].end(), rt), rt);
					ans = min(ans, 1 + solve(rt));
					g1[i].erase(lower_bound(g1[i].begin(), g1[i].end(), rt));
					g1[rt].clear();
				}
				g1[rt] = {v};
				g1[v].insert(lower_bound(g1[v].begin(), g1[v].end(), rt), rt);
			}
		if (ans > n) ans = -1;
		printf("%d\n", ans);
	}
}


Measured memory_bytes: 256
#include  <bits/stdc++.h>
using namespace std;
#define    error(args...){string _s=#args;replace(_s.begin(), _s.end(), ',', ' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);err(_it,args);}
void err  (istream_iterator<string> it) {}
template  <typename T, typename... Args>
void err  (istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a <<" ; ";
    err(++it, args...);
    cout << endl;
}
/*----------------------------------------------------------------------------------------------------------------------------------------------------*/
/*Let's start.............*/
#define   ll                long long
#define   pb                push_back
#define   ff                first
#define   ss                second
#define   srt(v)            sort(v.begin(),v.end())
#define   inf               200000000000000000
#define   mxn               1000009
#define   MOD               1000000007
#define   pi                acos(-1)

int main()
{
    ll ans = -1;
    ll n,m;
    cin >> n >> m;
    while(m--){
        ll x;cin >> x;
        n -= x;
    }
    cout << max(ans,n) << endl;
    return 0;
}

/*-------------------------------------------------------------------------------------------------------------------------------------------------------
".....but the truth is that you can increase it slightly."
Day 34.

// Learn to calculate the number of paths going through it
6
1 2 2 2 1 3
1 2
2 3
3 4
4 5
3 6

*/


Measured memory_bytes: 3632
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
   long long int N,count=1;
   cin >>N; long long int M[N];
   for(long long int i=0;i<N;i++){
   cin >> M[i];
   }
   long long int a=M[0];
   for(long long int i=1;i<N;i++){
       a=max(a,M[i]);
       if(a<=M[i])count++;
   }
   cout <<count;

}


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

using namespace std;
using ll = unsigned long long;
ll mo=1e9+7;
int main() {
    string str;
    int n;
    cin>>n;
    cin>>str;
    int red,blue;
    red = blue = 0;
    for(int i=0;i<str.size();++i){
        if(str[i] == 'R')red++;
        else blue++;
    }
    if(red > blue)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost {ios_base::sync_with_stdio(false);}
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PII, PII> PP;
typedef pair <PII, int> PPI;
typedef pair <int, PII> PIP;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
typedef vector <int> vi;
const int mod = 1e9+7;
const int inf = 1e9+10;
const ll MOD = 1e9+696969;
const ll INF = 1000LL * 1000LL * 1000LL * 10LL + 5;
#define maxn 100100
const int C = 2200;
bool prime[maxn + 5];
ll tab[maxn], para[maxn], pt[maxn];
vi primes;
int n;

int main()
{
	boost;
	FOR(i, 2, maxn) prime[i] = 1;
	FOR(i, 2, maxn)
	{
		if (prime[i])
		{
			for (int j=i+i; j<=maxn; j+=i) prime[j] = 0;
			if (i <= C) primes.pb(i);
		}
	}
	
	map <ll, int> jest;
	jest.clear();
	
	cin >> n;
	FOR(i, 1, n) cin >> tab[i];
	int res = 0;
	FOR(i, 1, n)
	{
		para[i] = 1; pt[i] = 1;
		for (auto u : primes)
		{
			int cc = 0;
			while (tab[i] % u == 0) ++cc, tab[i] /= u;
			cc %= 3;
			if (cc == 0) continue;
			else
			{
				FOR(j, 1, cc) pt[i] *= u;
				if (cc == 1) ++cc;
				else --cc;
				FOR(j, 1, cc) 
				{
					para[i] = para[i] * u;
					para[i] = min(para[i], INF);
				}
			}
		}
		ll s = tab[i], sr = sqrt(s);
		if (sr * sr == s)
		{
			if (prime[sr]) para[i] *= sr;
			para[i] = min(para[i], INF);
		}
		else
		{
			if (s > maxn) para[i] = INF;
			else
			{
				para[i] *= s;
				para[i] = min(para[i], INF);
				para[i] *= s;
				para[i] = min(para[i], INF);
			}
		}
		pt[i] *= s;
		jest[pt[i]]++;
	}
	map <ll, bool> used;
	used.clear();
	
	bool jed = 1;
	FOR(i, 1, n)
	{
		if (para[i] == 1)
		{
			res += jed;
			jed = 0;
		}
		else
		{
			if (used[para[i]] || used[pt[i]]) continue;
			res += max(jest[para[i]], jest[pt[i]]);
			used[pt[i]] = 1;
			if (para[i] <= (ll)1e10) used[para[i]] = 1;
		}
	}
	
	//FOR(i, 1, n) cout << pt[i] << ' ';
	//cout << endl;
	//FOR(i, 1, n) cout << para[i] << ' ';
	
	cout << res;
}


Measured memory_bytes: 23296
import java.util.*;

public class Main {
    public static void main(String[] args ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        long K = sc.nextLong();
      
        if(K <= A) {
            System.out.println(K);
        } else if(K < A+B) {
            System.out.println(A);
        } else {
            System.out.println(A-(K-A-B));
        }

    }
}


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

bool is_even(int n) {
  return n % 2 == 0;
}

int get_times_div2(int n) {
  int times = 0;
  while (is_even(n)) {
    n /= 2;
    times++;
  }
  return times;
}

void answer1(vector<int> a) {
  // 工夫した実装
  int mi = INT_MAX;
  //cout << INT_MAX << endl;
  for (int a_i: a) {
    int a_i_count = get_times_div2(a_i);
    mi = min(mi, a_i_count);
  }
  cout << mi << endl;
}

void answer2(std::vector<int> a) {
  // 素朴な実装
  int count = 0;
  bool can_continue = true;
  while (can_continue) {
    for (int& a_i: a) {
      if (is_even(a_i)) {
        a_i /= 2;
      } else {
        can_continue = false;
        break;
      }
    }
    if (can_continue) {
      count++;
    }
  }
  std::cout << count << '\n';
}

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int& a_i: a) {
    cin >> a_i;
  }
  //answer1(a);
  answer2(a);
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#define MAX_N 1010*1010
using namespace std;
int n,a[1010][1010];
int get(int u,int v)
{
	if(u>v)swap(u,v);
	return u+(v-1)*n;
}
queue<int>q;
struct edge
{
	int v,next;
}e[MAX_N<<1];
int eid,p[MAX_N<<1];
int deg[MAX_N];
void insert(int u,int v)
{
	deg[v]++;
	e[++eid]={v,p[u]};
	p[u]=eid;
}
int ans;
bool vis[MAX_N];
void dfs(int u,int x)
{
	vis[u]=1;
	ans=max(ans,x);
	for(int i=p[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis[v])
		{
			cout<<-1<<endl;
			exit(0);
		}
		dfs(v,x+1);
	}
}
int d[MAX_N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<n;++j)
			cin>>a[i][j];
	for(int i=1;i<=n;++i)
		for(int j=1;j<n-1;++j)
			insert(get(i,a[i][j]),get(i,a[i][j+1]));
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
			if(!deg[get(i,j)])
				q.push(get(i,j)),vis[get(i,j)]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=1;
		for(int i=p[u];i;i=e[i].next)
		{
			int v=e[i].v;
			deg[v]--;
			if(!deg[v])
				q.push(v),d[v]=d[u]+1;
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
		{
			if(!vis[get(i,j)])
			{
				cout<<-1<<endl;
				return 0;
			}
			ans=max(ans,d[get(i,j)]);
		}
	cout<<ans+1<<endl;
	return 0;
}

Measured memory_bytes: 28928
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int inf=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;

int main(){
  ll n;cin>>n;
  string s;cin>>s;
  ll r=0,w=0,lr=0,lw=0,ans=MOD;
  rep(i,0,n){
    if(s[i]=='R')r++;
    else w++;
  }
  ans=max(lw,r-lr);
  rep(i,0,n){
    if(s[i]=='R')lr++;
    else lw++;
    ans=min(ans,max(lw,r-lr));
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3744
N = int(input())
a, b = [], []

for i in range(N):
    c, d = map(int, input().split())
    a.append(c)
    b.append(d)

total = 0
for i, j in zip(a[::-1], b[::-1]):
    k = i + total
    if k % j != 0:
        total += int((k / j) + 1)*j - k
print(total)


Measured memory_bytes: 18432
#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#pragma GCC optimize ("O3")
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-9;
const int maxn = 2e5+9;
const double pi=acos(-1.0);
const ll inf = 1e17;
const int mod = 1e9+7;
ll op[maxn];
bool cmp(ll a,ll b){
    return llabs(a)>llabs(b);
}
int main()
{
    ios::sync_with_stdio(false);
    int n,k,jk=0;
    cin>>n>>k;
    for(int i=0;i<n;++i){
        cin>>op[i];
        if(op[i]<0) ++jk;
    }
    sort(op,op+n,cmp);
    ll ans=1;
    if(n==k){
        for(int i=0;i<n;++i) ans=ans*op[i]%mod;
    }
    else if(jk==n&&(k&1)){
        for(int i=n-1;i>=n-k;--i) ans=ans*op[i]%mod;
    }
    else{
        for(int i=0;i<k;++i) ans=ans*op[i]%mod;
        if(ans<0){
            int a=-1,b=-1,c=-1,d=-1;
            for(int i=k-1;i>=0;--i){
                if(op[i]>=0&&a<0) a=i;
                if(op[i]<0&&b<0) b=i;
            }
            for(int i=k;i<n;++i){
                if(op[i]>=0&c<0) c=i;
                if(op[i]<0&&d<0) d=i;
            }
            int p1,p2;
            if(a>=0&&c>=0&&b>=0&&d>=0){
                if(op[d]*op[b]>=op[a]*op[c]) p1=a,p2=d;
                else p1=b,p2=c;
            }
            else if(a>=0&&d>=0) p1=a,p2=d;
            else p1=b,p2=c;
            ans=1;
            for(int i=0;i<k;++i) if(i!=p1) ans=ans*op[i]%mod;
            ans=ans*op[p2]%mod;
        }
    }
    cout<<(ans+mod)%mod;
    return 0;
}


Measured memory_bytes: 5124
//k_k_dubey_
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define inf 999999999999
#define mx 200005
#define gcd __gcd
#define pb push_back
#define mk make_pair
#define bs binary_search
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
#define endl "\n"
#define vl vector<ll>
#define vs vector<string>
#define non __builtin_popcount
#define ml map<ll, ll> 
#define ms map<string , ll> 
using namespace std;

bool isp[mx];

void sv(){

	ll i,j;
	memset(isp, true, sizeof(isp));
	
	isp[1]= false;
	for(i=2;i*i<mx;i++){
		if(isp[i]){
			for(j=i*i;j<mx;j+=i)
			isp[j]= false;
		}
	}
}

ll powr(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	//sv();
	
	
	
	ll n,i,j,h[mx];
	cin>>n;
	for(i=1; i< n+1; i++)
	cin>>h[i];
	
	for(i=n; i>1; i--){
	    
	    if(h[i-1] > h[i])
	    h[i-1]--;
	}
	
	ll ck[mx];
	for(i=1; i< n+1; i++)
	ck[i]= h[i];
	
	sort(ck+1, ck+n+1);
	
	
	ll fl=0;
	for(i=1; i< n+1; i++)
	if(ck[i] != h[i])
	fl=1;
	
	if(fl)
	cout<<"No";
	else
	cout<<"Yes";
    return 0;
}























Measured memory_bytes: 3072
/*
Author: Sagar Gupta
E mail: sagar.june97p@gmail.com
*/
#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;
#define newline ("\n")
#define deb(n) cerr << #n << " = " << (n) << '\n'
#define FOR(i, n) for (int(i) = 0; (i) < n; (i)++)
#define PI (3.141592653589)
#define ordered_set tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define MOD 1000000007

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

    // Pikachu, I choose you
    long long k,a,b;
    cin >> k >> a >> b;
    long long profit = b-a;
    long long biscuit = 1ll;
    if(profit > 2)
    {
        if(biscuit < a)
        {
            long long diff = min(k, a - biscuit);
            k -= diff;
            biscuit+= diff;
        }
        if(k > 0)
        {
            biscuit += profit*(k/2ll);
            if(k%2ll)
            {
                biscuit++;
            }
        }
    }
    else
    {
        biscuit += k;
    }
    cout << biscuit;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int A[100];
int n;
int fo(){
    for ( int i = 0; i < n; i++){
        if ( A[i]%2)return A[i];
    }
}
main(){
    
    int sum = 0;
    cin >> n;
    for ( int i = 0; i < n; i++){
        cin >> A[i];
        sum += A[i];
    }
    sort(A, A+n);
    if ( sum % 2 == 0) cout << sum/2 << endl;
    else cout << (sum - fo())/2 << endl;
}


Measured memory_bytes: 3160
#!/usr/bin/ruby
#encoding: utf-8

require 'matrix'

#input
n,d = gets.split.map(&:to_i)
x = Array.new(n)
v = Array.new(n)
(0..n-1).each do |i|
  x[i] = gets.split.map(&:to_i)
  v[i] = Vector.elements(x[i],true)
end

ans = 0

(0..n-1).each do |i|
  (i+1..n-1).each do |j|
    dist = (v[i] - v[j]).r
    if dist == dist.to_i
      ans += 1
    end
  end
end

puts ans

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

int gcd(int a, int b){
  if (a%b==0) return(b);
  else return(gcd(b, a%b));
}

int main(){
  int N, X; cin>>N>>X;
  vector<int> D(N);
  for(int i=0; i<N; i++){
    int a; cin>>a;
    D[i]=abs(a-X);
  }
  int ans=D[0];
  for(int i=1; i<N; i++) ans=gcd(ans, D[i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
using namespace std;

int check(int x) {
	bool P =false;

	for (int i = 2; i * i < x; i++) {
		if (x % i == 0) {
			P = true;
			break;
		}
	}

	return P;
};

int main() {
	int X;

	cin >> X;

	while (check(X) == true) {
		X++;
	}

	cout << X;

	return 0;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int N = 5050;
using namespace std;
bool c[N][N],b[N][N];
short int g[N][N],f[N][N];
int a[N];
int main(){
  int n,k; cin>>n>>k;
  for (int i=1; i<=n; ++i)
    cin>>a[i];
  if (n==1){
    printf("%d",a[1]<k);
    return 0;
  }
  g[0][0]=f[n+1][0]=1;
  for (int i=1; i<=n; ++i)
    for (int j=0; j<=k; ++j)
      if (g[i-1][j]){
	g[i][j]=1;
	if (j+a[i]<=k)
	  g[i][j+a[i]]=1;
      }
  for (int i=n; i>=1; --i)
    for (int j=0; j<=k; ++j)
      if (f[i+1][j]){
	f[i][j]=1;
	if (j+a[i]<=k)
	  f[i][j+a[i]]=1;
      }
  for (int i=1; i<=n; ++i){
    b[i][0]=c[i][0]=1;
    for (int j=1; j<=k; ++j){
      b[i][j]=g[i][j],c[i][j]=f[i][j];
      f[i][j]+=f[i][j-1],g[i][j]+=g[i][j-1];
    }
  }
  int ans=0,w;
  for (int i=1; i<=n; ++i){
    w=0;
    for (int j=0; j<k; ++j)
      if (j+a[i]>=k&&(b[i-1][j]||c[i+1][j]))
	{ w=1; break; }
    if (!w){
      for (int j=0; j<k; ++j){
	if (b[i-1][j]&&(f[i+1][k-j-1]-f[i+1][k-j-a[i]-1])>0)
	  { w=1; break; }
	if (c[i+1][j]&&(g[i-1][k-j-1]-g[i-1][k-j-a[i]-1])>0)
	  { w=1; break; }
      }
    }
    ans+=(w^1);
  }
  cout<<ans;
  return 0;
}


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

int main() 
{
    int N;
    cin >> N;
    set<string>S;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        S.insert(str);
    }
    cout << S.size() << endl;
}

Measured memory_bytes: 19048
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

lint n, k;
string s;

int main() {
    cin >> n >> k >> s;
    char head = s[0];

    lint ans = 0;
    for(lint i = 1; i < n; i++) {
        if(s[i-1] == 'L' && s[i] == 'L')  ans++;
    }
    reverse(s.begin(), s.end());
    for(lint i = 1; i < n; i++) {
        if(s[i-1] == 'R' && s[i] == 'R')  ans++;
    }
    reverse(s.begin(), s.end());

    // headから切り替わる回数を数える
    lint cnt = 0;
    for(lint i = 1; i < n; i++) {
        if(s[i-1] == head && s[i] != head)  cnt++;
    }

    if(cnt > k)  ans += 2 * k;
    else         ans = n - 1;

    cout << ans << endl;
}

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

int main() {
  string a,b;
  cin >> a >> b;
  if(a.length()>b.length()) {
    cout << "GREATER" << endl;
  }
  else if(a.length()<b.length()) {
    cout << "LESS" << endl;
  }
  else {
    if(a<b) {
      cout << "LESS" << endl;
    }
    else if(a>b) {
      cout << "GREATER" << endl;
    }
    else {
      cout << "EQUAL" << endl;
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	if(B<C||A>D)cout<<0;
	else if(C<=A&&B<=D)cout<<abs(A-B);
	else if(A<=C&&D<=B)cout<<abs(C-D);
	else if(D>=B&&B>=C&&C>=A)cout<<abs(B-C);
	else if(D>=A&&A>=C&&B>=D)cout<<abs(A-D);
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long ggcd(long long a, long long b){
  if(a % b == 0){
    return b;
  }
  return ggcd(b,a%b);
}
long long saisyo(long long a, long long b){
  return (a*(b/ggcd(a,b)));
}
#define rep(i,q) for(int i = 0; (q) > i; i++)
int main(){
  long long kekka=1;
  long long N;cin>>N;
  for(int i = 0; N > i; i++){
    long long t;cin>>t;
    kekka = saisyo(kekka,t);
  }
  cout << kekka << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) (a).begin(), (a).end()


int main() {
    char a, b;
    cin >> a >> b;
    if((a == 'H' and b == 'H') or (a=='D' and b=='D')) cout << 'H' << endl;
    else cout << 'D' << endl;
}


Measured memory_bytes: 256
#include <stack>
#include <iostream>
#pragma warning(disable : 4996)
using namespace std;
int Q, x, s1[100009], s2[100009];
int main() {
	while (scanf("%d", &Q), Q) {
		int l = 0;
		for (int i = 1; i <= Q; i++) {
			scanf("%d", &x);
			if (i & 1) {
				if (l == 0 || x != s1[l - 1]) s1[l] = x, s2[l++] = 1;
				else s2[l - 1]++;
			}
			else {
				if (x == s1[l - 1]) s2[l - 1]++;
				else {
					if (l == 1) s1[l - 1] ^= 1, s2[l - 1]++;
					else s2[l - 2] += s2[l - 1] + 1, l--;
				}
			}
		}
		int ret = 0;
		for (int i = 0; i < l; i++) {
			if (s1[i] == 0) ret += s2[i];
		}
		printf("%d\n", ret);
	}
	return 0;
}

Measured memory_bytes: 3084
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int i, j, k;
	long long int x[200005], y[200005];
	for (i = 0; i < n; i++)
		scanf("%lld %lld", &x[i], &y[i]);
	long long int c[200005];
	for (i = 0; i < n; i++)
		c[i] = x[i] + y[i];
	j = k = 0;
	for (i = 0; i < n; i++)
	{
		if (c[i] < c[j])
			j = i;
		if (c[i] > c[k])
			k = i;
	}
	long long int ans = c[k] - c[j];
	for (i = 0; i < n; i++)
		c[i] = x[i] - y[i];
	for (i = 0; i < n; i++)
	{
		if (c[i] < c[j])
			j = i;
		if (c[i] > c[k])
			k = i;
	}
	if (ans < c[k] - c[j])
		ans = c[k] - c[j];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6372
#include <stdio.h>

int main(void)
{
	long long a, b, c;
	scanf("%lld%lld%lld", &a, &b, &c);
	
	if (c-a-b>0 && 4*a*b<(c-a-b)*(c-a-b))
		puts("Yes");
	else puts("No");
	
	return 0;
}

Measured memory_bytes: 128
import java.util.*;

class AOJ0289 {
    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int s = sc.nextInt();
            int d = sc.nextInt();
            int cnt = 0;
            while(d > s) {
                cnt += (s & 1) + (d & 1);
                s += s & 1;
                s >>= 1;
                d >>= 1;
            }
            System.out.println(cnt);
        }
    }
}
public class Main {
    public static void main(String... args) {
        AOJ0289.main();
    }
}

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

int main(){
  int num;
  while(cin>>num){
    if(num==0) break;
    int c = 0;
    for(int i=num+1;i <= 2*num;i++){
      bool f = true;
      for(int j=2;j<=sqrt(i);j++){
	if(i%j==0){
	  f = false;
	  break;
	}
      }
      if(f) c++;
    }
    cout<<c<<endl;
  }
  return 0;
}

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

int main(void){
    int n,l;
    cin >> n >> l;
    list<string> dict;
    for (size_t i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        dict.push_back(s);
    }
    dict.sort();
    for(auto var : dict)cout << var;
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}  
vector<ll>divisor_enum(ll n){
  vector<ll>ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      if(i*i==n)ret.PB(i);
      else{
        ret.PB(i);
        ret.PB(n/i);
      }
    }
  }
  return ret;
}
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n;cin>>n;
  auto v=divisor_enum(n-1);
  res+=(ll)v.size()-1;
  v=divisor_enum(n);
  for(auto z:v){
    if(z==1)continue;
    buf=n;
    while(buf%z==0)buf/=z;
    res+=buf%z==1;
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 384
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		HashSet<String> set = new HashSet<String>();

		for(int idx = 0; idx < 3; idx++) {
			String num = sc.next();
			set.add(num);
		}

		System.out.println(set.size());
		
		sc.close();
	}

}

Measured memory_bytes: 35792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
string a = "afkpu";
int main(void){
  string line;
  while(cin>>line){
    string ans;
    bool na = false;
    if(line.size()%2){
      na = true;
    }
    for(int i=0;i<(int)line.size(); i+=2){
      if(na) break;
      if(line[i+1]>='6'||line[i+1]<='0'){
        na = true;
        break;
      }
      if(line[i]<='5'){
        ans+=(char)(a[line[i]-'1']+line[i+1]-'1');
      }else if(line[i]=='6'){
        if(line[i+1]=='1') ans+='z';
        if(line[i+1]=='2') ans+='.';
        if(line[i+1]=='3') ans+='?';
        if(line[i+1]=='4') ans+='!';
        if(line[i+1]=='5') ans+=' ';
      }else{
        na = true;
        break;
      }
    }
    if(!na)cout<<ans<<endl;
    else cout<<"NA"<<endl;
  }
  return 0;
}

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

int main () {
    int N, K;
    cin >> N >> K;
    vector<int> l(N);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        cin >> l.at(i);
    }
    sort(l.begin(), l.end());
    reverse(l.begin(), l.end());
    for (int i = 0; i < K; i++) {
        ans += l.at(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#include <numeric>
#include <cmath>
#include <limits>

using namespace std;

int main(void){

	int n,h,w;
	cin >> n >> h >> w;
	int a[n],b[n];
	int cnt = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		if(h<=a[i] && w<=b[i]){
			cnt ++;
		}
	}
	cout <<cnt <<endl;
	return 0;



}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }

inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

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

    var(string, s, t);
    vector<int> indexes[128];

    const i64 lenS = s.length();
    s = "_"s + s;

    reps(i, 1, lenS) {
        indexes[s[i]].push_back(i);
    }

    i64 backToHeadCount = 0;
    int head = 1;
    for (const char c : t) {
        const auto &ps = indexes[c];
        auto itr = lower_bound(all(ps), head);


        if (itr == ps.end()) {
            ++backToHeadCount;
            head = 1;
            itr = lower_bound(all(ps), head);
            if (itr == ps.end()) {
                print(-1);
                return 0;
            } else {
                head = *itr + 1;
            }
        } else {
            head = *itr + 1;
        }
    }

    print(lenS * backToHeadCount + head - 1);

    return 0;
}


Measured memory_bytes: 1260
#include <iostream>
using namespace std;
long long gcd(long long m,long long n){
    if(n==0){
        return m;
    }else{
        return gcd(n,m%n);
    }
}
int main(void){
    long long A,B,C,D,l,a,b;
    cin>>A>>B>>C>>D;
    A--;
    a=gcd(C,D);
    l=C*D/a;
    a=A/C+A/D-A/l;
    b=B/C+B/D-B/l;
    a=A-a;b=B-b;
    b-=a;
    cout<<b<<endl;
}


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


int main(void){
    double a, b, C, S, L, h;
    const double PI = acos(-1);

    cin >> a >> b >> C;
    C = C * PI / 180;
    h = b * sin(C);
    S = a * h / 2;
    L = a + b + sqrt(a * a + b * b - 2 * a * b * cos(C));
    cout << fixed << setprecision(5) << S << endl << L << endl << h << endl;
    return 0;
}


Measured memory_bytes: 3560
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }

void _main() {
  int N;
  cin >> N;
  int A[2][N];
  rep(i, 0, 2) rep(j, 0, N) cin >> A[i][j];

  int ans = 0;
  rep(i, 0, N) {
    int tmp = 0;
    rep(j, 0, i+1)  tmp += A[0][j];
    rep(j, i, N)    tmp += A[1][j];
    chmax(ans, tmp);
  }
  cout << ans << "\n";
}

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

using namespace std;
#define int long long
const int p=1e9+7;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
    int n;
    cin>>n;
    pair <int,pair<int,int> > a[n];
    int ans=0;
    for(int i=0;i<n;++i)
    {
        cin>>a[i].first>>a[i].second.first>>a[i].second.second;
        ans+=max(a[i].second.first,a[i].second.second);
    }
    sort(a,a+n);
    int curr=0;
    set <int> v1;
    map <int,int> v2;
    int s=0;
    for(int i=0;i<=n;++i)
    {
        while(curr<n && i==a[curr].first)
        {
            if(!(a[curr].second.first>=a[curr].second.second)){++curr;continue;}
            ++s;
            int o=a[curr].second.first-a[curr].second.second;
            if(!v1.count(o))
            {
                v1.insert(o);
                v2[o]=1;
            }
            else
            {
                v2[o]++;
            }
            ++curr;
        }
        while(s>i)
        {
            int z=(*v1.begin());
            s--;
            ans-=z;
            v2[z]--;
            if(!v2[z])
            {
                v1.erase(v1.begin());
            }
        }
    }
    //cout<<ans<<" ans "<<endl;
    s=0;
    curr=0;
    for(int i=0;i<n;++i)
    {
        a[i].first=(n-a[i].first);
    }
    sort(a,a+n);
    for(int i=0;i<n;++i)
    {
        swap(a[i].second.second,a[i].second.first);
    }
    v1.clear();v2.clear();
    for(int i=0;i<=n;++i)
    {
        while(curr<n && i==a[curr].first)
        {
            if(!(a[curr].second.first>=a[curr].second.second)){++curr;continue;}
            ++s;
            int o=a[curr].second.first-a[curr].second.second;
            if(!v1.count(o))
            {
                v1.insert(o);
                v2[o]=1;
            }
            else
            {
                v2[o]++;
            }
            ++curr;
        }
        while(s>i)
        {
            int z=(*v1.begin());
            s--;
            ans-=z;
            v2[z]--;
            if(!v2[z])
            {
                v1.erase(v1.begin());
            }
        }
    }
    cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 14776
#include <bits/stdc++.h>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
using namespace std;

int N, K;
int DP[100003][3], V[100003][3];
int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> V[i][j];
    DP[0][0] = DP[0][1] = DP[0][2] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < 3; ++j) {
            DP[i][j] = V[i][j] + max(DP[i - 1][(j + 2) % 3], DP[i - 1][(j + 1) % 3]);
        }
    }
    cout << max(max(DP[N][0], DP[N][1]) , DP[N][2]);
    return 0;
}



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


namespace _001_FindingMissingCards
{

    class Program
    {
        static void Main()
        {
            string givenLine = Console.ReadLine();
            string []splitedWords = givenLine.Split(' ');
            double a = Convert.ToDouble(splitedWords[0]);
            double b = Convert.ToDouble(splitedWords[1]);
            double c = Convert.ToDouble(splitedWords[2]);

            double s = a * b * Math.Sin(Math.PI * c / 180.0)/2.0;
            double l = a + b + Math.Sqrt(Math.Pow(a, 2.0) - 2.0 * a * b * Math.Cos(Math.PI * c / 180.0) + Math.Pow(b, 2));
            double h = b * Math.Sin(Math.PI * c / 180.0);
            Console.WriteLine(s);
            Console.WriteLine(l);
            Console.WriteLine(h);

        }
    }
}

Measured memory_bytes: 9420
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define float long double
#define f(i,a,b) for(int i = a;i < b;i++)
#define ff(i,a,b)  for(int i = a-1;i>=b;i--)
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false), cin.tie(NULL)
const int mod = 1e9+7;
//int to string -> to_string()
//string to int -> stoi()

int32_t main()
{
   IOS;
   int n,m;
   float sum=0;
   cin>>n>>m;
   int a[n];
   f(i,0,n)
   {
    cin>>a[i];
    sum += a[i];
   }
   int cnt = 0;
   sum /= 4*m;
   f(i,0,n)
   {
    if(sum<=a[i])
      cnt++;
   }
   if(cnt>=m)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define  fo(i,n) for(ll i=0;i<n;i++)
#define rfo(i,n) for(ll i=n;i>=0;i--)
#define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define pb push_back
#define deb(x) cout<< #x << " = "<<x<<endl;
#define F first
#define S second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
void solve()
{
	ll d,t,s;
	cin>>d>>t>>s;
	if((s*t) >= d)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3644
n=int(input())
v=[int(x) for x in input().split()]

p=[0]+sorted(v[0:n-1:2])+[0]
l=r=o1=o2=0
for i in range(1,n//2+2):
  if p[i-1] != p[i]:
    if l>=o1:
      o2,o1,r=o1,l,p[i-1]
    elif l>o2:
      o2=l
    l=1
  else:
    l+=1

pr = r
po1 = o1
po2 = o2

p=[0]+sorted(v[1:n:2])+[0]
l=r=o1=o2=0
for i in range(1,n//2+2):
  if p[i-1] != p[i]:
    if l>=o1:
      o2,o1,r=o1,l,p[i-1]
    elif l>o2:
      o2=l
    l=1
  else:
    l+=1

if pr != r:
  print(n-po1-o1)
else:
  print(min(n-po1-o2,n-o1-po2))


Measured memory_bytes: 15684
#include <stdio.h>
#include <list>
#include <iterator>

using namespace std;

int main()
{
  list<int> lst;
  list<int>::iterator itr = lst.begin();
  int q;
  long x;
  int t;
  int d;

  scanf("%d", &q);

  for (int i = 0; i < q; i++) {
    scanf("%d", &t);
    if (t == 0){
      scanf("%ld", &x);
      itr=lst.insert(itr, x);
    } else if(t == 1){
      scanf("%d", &d);
      advance(itr,d);
    } else if(t == 2){
      itr=lst.erase(itr);
    }
  }

  for(itr = lst.begin(); itr != lst.end(); ++itr) {
    printf("%d\n",*itr);
  }

  return 0;
}



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

vector<ll> adj[200006];
vector<bool> vis(200004, 0);

void dfs(ll node, ll &c)
{
    vis[node] = 1;
    c++;
    for (auto child : adj[node])
    {
        if (vis[child] == 0)
        {
            dfs(child, c);
        }
    }
}

void solve()
{
    ll n, e, a, b, res = 0, c, i;
    cin >> n >> e;
    // vis.resize(n+1,false);

    while (e--)
    {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (i = 1; i <= n; i++)
    {
        if (vis[i] == false)
        {
            c = 0;
            dfs(i, c);
            res = max(res, c);
        }
    }

    cout << res;
}

int main()
{
    solve();
}


Measured memory_bytes: 23776