akhauriyash/Code-Regression huggingface dataset:
s = input()
key = s[0]
value = 1
key_list = []
for i in range(len(s)-1):
    if s[i+1] == s[i]:
        value += 1
    else:
        key_list.append(value)
        value = 1
key_list.append(value)

ans = 0
if key == ">":
    p = key_list[0]
    ans += p*(p+1)//2
    for i in range((len(key_list)-1)//2):
        p, q = key_list[2*i+1], key_list[2*i+2]
        p, q = max([p, q]), min([p, q])
        ans += (p*(p+1)+q*(q-1))//2
    if len(key_list)%2 == 0:
        p = key_list[-1]
        ans += p*(p+1)//2
else:
    for i in range((len(key_list))//2):
        p, q = key_list[2*i], key_list[2*i+1]
        p, q = max([p, q]), min([p, q])
        ans += (p*(p+1)+q*(q-1))//2
    if len(key_list)%2 == 1:
        p = key_list[-1]
        ans += p*(p+1)//2
print(ans)

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

int main(){
	int n,a[100]={},v,i,j;
	cin >> n;
	for(i=0;i<n;i++){
		cin >>a[i];
		if(i!=n-1)cout <<a[i]<<" ";
		else cout <<a[i]<<endl;
	}
	for(i=1;i<n;i++){
		v=a[i];
		j=i-1;//j????????\??????????????????0?????\??????????????§???i(=1)-1??§????????????
		while(j>=0&&a[j]>v){
			a[j+1]=a[j];
			j--;
			a[j+1]=v;
		}
	for (j=0;j<n;j++){if(j!=n-1)cout << a[j] << " ";
					else cout << a[j] << endl;
	}
	}
}

Measured memory_bytes: 3120
#include <iostream>
using namespace std;
int main() {
  int a;
  int b;
  cin >> a;
  cin >> b;
  if ((a + b) % 2 == 1)
  {
    cout << "IMPOSSIBLE" << endl;
  }
  else
  {
    cout << (a + b)/2 << endl;
  }
  return 0;
}

Measured memory_bytes: 888
n = int(input())
s = input()

ws = []
count = 0
for v in s:
  ws.append(count)
  if v == 'W':
    count += 1
  

count = 0
es = []
for v in s[::-1]:
  es.append(count)
  if v == 'E':
    count += 1

  
es = list(reversed(es))
ans = 10**9
for w,e in zip(ws,es):
  ans = min(ans, w+e)
  
print(ans)

Measured memory_bytes: 20768
#define R register
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 5;

int n, val, sum;
bitset<maxn> f;

int main()
{
	scanf("%d", &n);
	f[0] = 1;
	for (R int i = 1; i <= n; ++i) scanf("%d", &val), f |= (f << val), sum += val;
	if(n == 1) return printf("%d", sum), 0;
	for (R int i = (sum >> 1); i; --i) if(f[i]) return printf("%d", sum - i), 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import math
Q = int(input())
num = lambda x: (x, max(0, (x - 1) // K))
sub = lambda xs, ys: [x - y for (x, y) in zip(xs, ys)]
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    K = math.ceil(max(A, B) / (min(A, B) + 1))
    l, r = 0, A + 1
    while r - l > 1:
        m = (l + r) // 2
        rA, rB = sub((A, B), num(m))
        l, r = ((m, r), (l, m))[(rA + 1) * K < rB]

    f = ''
    for i in range(C - 1, D):
        na, nb = num(l)
        if i < na + nb:
            f += ('A', 'B')[i % (K + 1) == K] if i < nb * (K + 1) else 'A'
        else:
            nb, na = num(B - nb)
            j = A + B - i - 1
            f += ('B', 'A')[j % (K + 1) == K] if j < na * (K + 1) else 'B'
    print(f)


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

ll calc(ll N){
  if(N == -1) return 0;
  if(N % 4 == 0) return N;
  if(N % 4 == 1) return 1;
  if(N % 4 == 2) return 1 ^ N;
  if(N % 4 == 3) return 0;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC121D - XOR World
  // f(A, B) = f(0, A-1) ^ f(0, B)
  // f(0, 4m) = 4m
  // f(0, 4m+1) = 1
  // f(0, 4m+2) = 1 ^ (4m+2)
  // f(0, 4m+3) = 0
  ll A, B, ans;
  cin >> A >> B;
  ans = calc(A-1) ^ calc(B);
  cout << ans << endl;
}

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

int main() {
  ll K;
  cin >> K;
  if (K % 2 == 0 || K % 5 == 0) {
    cout << -1 << endl;
    return 0;
  }
  ll ans = 1;
  ll x = 7;
  x %= K;
  while (x) {
    ans++;
    x = x * 10 + 7;
    x %= K;
  }
  cout << ans << endl;
  return 0;
}

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

string s;
int n;

long long result;

void Build(int pos, long long sum, long long last) {
    if (pos == n) {
        result += last;
        result += sum;
        return;
    }

    Build(pos + 1, sum + last, s[pos] - '0');
    Build(pos + 1, sum, last * 10 + s[pos] - '0');
}

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

    cin >> s;
    n = s.length();

    result = 0;

    Build(1, 0, s[0] - '0');

    cout << result << endl;

    return 0;
}

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

int main(){
    int N;
    string S;
    cin >> N >> S;
    int nxt[30001][10], now[10];
    for(int j=0; j<10; j++) now[j] = N+1;
    for(int i=N; i>=0; i--){
        for(int j=0; j<10; j++) nxt[i][j] = now[j];
        if(i) now[S[i-1]-'0'] = i;
    }
    int ans = 0;
    for(int a=0; a<10; a++) for(int b=0; b<10; b++) for(int c=0; c<10; c++){
        int pos = nxt[0][a];
        if(pos <= N) pos = nxt[pos][b];
        if(pos <= N) pos = nxt[pos][c];
        if(pos <= N) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1536
def main():
    days = int(input())
    value = [list(map(int, input().split())) for _ in range(days)]
    dp = [[0, 0, 0] for _ in range(days)]
    for i in range(3):
        dp[0][i] = value[0][i]
    for i in range(1, days):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + value[i][0]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + value[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + value[i][2]
    print(max(dp[-1][0], dp[-1][1], dp[-1][2]))


if __name__ == '__main__':
    main()



Measured memory_bytes: 47280
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int mod = (int)1e9 + 7;
const int MX = (int)1e7 + 10;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);

	ll n;
	cin >> n;

	int res = 0;

	for(int i = 2; i * 1LL * i <= n; ++i){
		if(n % i) continue;
		// this is a prime
		int cnt = 0;
		while(n % i == 0){
			cnt++;
			n /= i;
		}
		// find max(x) where : x * (x + 1) / 2 <= cnt
		// int l = 1, r = sqrt(cnt) + 2;
		// while(l <= r){
		// 	int md = (l + r) / 2;
		// 	int calc = md * (md + 1) / 2;
		// 	if(calc <= cnt) l = md + 1;
		// 	else r = md - 1;
		// }
		// res += r;
		int sum = 0;
		for(int j = 1; j <= cnt; ++j){
			sum += j;
			if(sum <= cnt) res++;
			else break;
		}
	}

	if(n > 1){ // prime
		res++;
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>

int main(void)
{
  int a, b, i;
  char op;

  for (i=1; ; i++){
    scanf("%d %c %d", &a, &op, &b);
    if (op == '?')
      break;
    
    switch (op) {
      case '+':
	printf("%d\n", a+b);
        break;
      case '-':
        printf("%d\n", a-b);
        break;
      case '*':
        printf("%d\n", a*b);
        break;
      case '/':
        printf("%d\n", a/b);
        break;
    }
  }

  return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ll x[5555];
ll dp[5011][5011];
int b[222][5011];

void add(int x1, int y1, int x2, int y2, int v)
{
	dp[x1][y1]+=v; dp[x2+1][y2+1]+=v; dp[x1][y2+1]-=v; dp[x2+1][y1]-=v;
}

const int LG=13;
const int MX=5011;
const ii INF=mp(-1,-1);
struct SparseTable //Warning : Change query return value manually if needed. INF is the dummy val
{
	pair<int,int> st[LG][MX];
	pair<int,int> initial[MX];
	
	pair<int,int> combine(pair<int,int> a, pair<int,int> b) //warning : change if neccesary
	{
		if(a>b) return a;
		return b;
	}
	
	SparseTable()
	{
		for(int i = 0; i < MX; i++) initial[i] = INF;
	}
	
	void init()
	{
		for(ll j = 0; j < LG; j++)
		{
			for(ll i = 0; i < MX; i++)
			{
				st[j][i] = INF;
				if(i + (1<<j) - 1 < MX)
				{
					if(j == 0) st[j][i] = initial[i];
					else st[j][i] = combine(st[j-1][i], st[j-1][i + (1<<(j-1))]);
				}
			}
		}
	}
	
	pair<int,int> query(int l, int r)
	{
		int k = 31 - __builtin_clz(r-l);
		if(l==r) k=0;
		return combine(st[k][l], st[k][r - (1<<k) + 1]);
	}
};

int n,m;
SparseTable st;

void recurse(int l, int r)
{
	if(l>r) return ;
	ii tmp = st.query(l,r);
	add(l,tmp.se,tmp.se,r,tmp.fi);
	recurse(l,tmp.se-1); recurse(tmp.se+1,r);
}

void solve_row(int id)
{
	for(int i=1;i<=n;i++) st.initial[i]=mp(b[id][i],i);
	st.init();
	recurse(1,n);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n;i++)
	{
		cin>>x[i]; x[i]+=x[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>b[j][i];
		}
	}
	for(int j=1;j<=m;j++) solve_row(j);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]+=dp[i-1][j];
			dp[i][j]+=dp[i][j-1];
			dp[i][j]-=dp[i-1][j-1];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			ans=max(ans,dp[i][j]-(x[j]-x[i]));
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 200960
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll po(ll a, ll b)
{
	if (b == 0)return 1;
	ll z = po(a, b / 2);
	z = z*z%mod;
	if (b % 2 == 1)z = z*a%mod;
	return z;
}
int main()
{
	ll num, kai;
	scanf("%lld%lld", &num, &kai);
	vector<ll>vec;
	for (ll i = 1; i*i <= num; i++)
	{
		if (num%i == 0)
		{
			vec.push_back(i);
			if (i != num / i)vec.push_back(num / i);
		}
	}
	sort(vec.begin(), vec.end());
	vector<ll>ans;
	vector<ll>ret;
	for (int i = 0; i < vec.size(); i++)
	{
		if (num % 2 == 0)
		{
			if (vec[i] % 2 == 0)ans.push_back(num / vec[i]),ret.push_back(po(kai, ans[i])*(num / vec[i]) % mod);
			else ans.push_back(0),ret.push_back(0);
		}
		else ans.push_back((num / vec[i] + 1) / 2),ret.push_back(po(kai, ans[i])*(num / vec[i]) % mod);
	}
	for (int i = vec.size() - 1; i >= 0; i--)
	{
		if (num % 2 == 0 && vec[i] % 2 == 1)continue;
		for (int j = i + 1; j < vec.size(); j++)
		{
			if (vec[j] % vec[i] == 0)ret[i] = (ret[i] + mod - ret[j] * (vec[j] / vec[i]) % mod) % mod;
		}
		//printf("%lld %lld\n", vec[i], ret[i]);
	}
	ll r = 0;
	for (int i = 0; i < vec.size(); i++)
	{
		r += ret[i];
		r %= mod;
	}
	printf("%lld\n",r);
}

Measured memory_bytes: 256
from fractions import Fraction as F
for _ in xrange(input()):
    x1, y1, r1, x2, y2, r2 = map(F, raw_input().split())
    d = (x1-x2)**2+(y1-y2)**2 
    if d < (r1-r2)**2:
        print 2 if r1 > r2 else -2
    elif (r1-r2)**2 <= d <= (r1+r2)**2:
        print 1
    else:
        print 0

Measured memory_bytes: 7884
#include <iostream>

int main() {
  int X, Y;
  std::cin >> X >> Y;
  if (Y % 2 == 0 && Y >= X * 2 && Y <= X * 4) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  return 0;
}


Measured memory_bytes: 3636
// And in the end, the love you take is equal to the love you make.
//                      Paul McCartney (the Beatles). The End. Abbey Road.

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

using LL = long long;

namespace _buff {

const size_t BUFF = 1 << 19;
char buff[BUFF], *begin = buff, *end = buff;
char getc() {
  if (begin == end) {
    begin = buff;
    end = buff + fread(buff, 1, BUFF, stdin);
  }
  return begin == end ? -1 : *begin++;
}

}

LL read() {
  using namespace _buff;
  LL ret = 0;
  bool pos = true;
  char c = getc();
  for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
    assert(~c);
  }
  if (c == '-') {
    pos = false;
    c = getc();
  }
  for (; c >= '0' && c <= '9'; c = getc()) {
    ret = (ret << 3) + (ret << 1) + (c ^ 48);
  }
  return pos ? ret : -ret;
}

const size_t N = 1e5 + 5;
const int MOD = 1e9 + 7;

int rmod(int x) {
  if (x >= MOD) x -= MOD;
  if (x  <  0 ) x += MOD;
  return x;
}

void add(int &dp, int val) {
  dp = rmod(dp + val);
}

int n; LL s[N], a, b;
int f[N], g[N], df[N], dg[N];
int suma[N], sumb[N];

bool calcfg(int j, int i) {
  return sumb[i] - sumb[j + 1] == 0;
}

bool calcgf(int j, int i) {
  return suma[i] - suma[j + 1] == 0;
}

int main() {
  n = read(); a = read(); b = read();
  generate_n(s + 1, n, read);
  s[0] = -2e18;
  s[n + 1] = 2e18;
  for (int i = 1; i <= n; ++i) {
    suma[i] = suma[i - 1] + (s[i] - s[i - 1] < a);
    sumb[i] = sumb[i - 1] + (s[i] - s[i - 1] < b);
  }
  f[0] = g[0] = 1;
  df[0] = dg[0] = 1;
  df[1] = dg[1] = MOD - 1;
  for (int i = 0; i <= n; ++i) {
    if (i) {
      add(df[i], df[i - 1]);
      add(dg[i], dg[i - 1]);
    }
    f[i] = df[i];
    g[i] = dg[i];
    if (i == n) break;
    /* calc f to g */ {
      static int l = 1, r = 1;
      while (s[l + 1] - s[i] < a) ++l;
      if (l <= i) l = i + 1;
      if (calcfg(i, l)) {
        if (r < l) r = l;
        while (r < n && calcfg(i, r + 1)) ++r;
        add(dg[l], f[i]);
        add(dg[r + 1], -f[i]);
      }
    } /* calc g to f */ {
      static int l = 1, r = 1;
      while (s[l + 1] - s[i] < b) ++l;
      if (l <= i) l = i + 1;
      if (calcgf(i, l)) {
        if (r < l) r = l;
        while (r < n && calcgf(i, r + 1)) ++r;
        add(df[l], g[i]);
        add(df[r + 1], -g[i]);
      }
    }
  }
  cout << rmod(f[n] + g[n]) << '\n';
  return 0;
}


Measured memory_bytes: 3840
using System;

public class Program{
  public static void Main(string[] args){
    var numbers = Console.ReadLine().Split(' ');
    var num1 = int.Parse(numbers[0]);
    var num2 = int.Parse(numbers[1]);
    var result = (num1 + num2)/2;
    if((num1 + num2)%2 == 0)
    {
      Console.WriteLine(result);
    }
    else
    {
      Console.WriteLine("IMPOSSIBLE");
    }
  }
}

Measured memory_bytes: 11092
H,W = map(int,input().split())
G = [str(input()) for _ in range(H)]

def search(x,y):
    flag = 0
    if x > 0:
        if G[y][x-1] == "#":
            flag = 1
    if x < W-1:
        if G[y][x+1] == "#":
            flag = 1
    if y > 0:
        if G[y-1][x] == "#":
            flag = 1
    if y < H-1:
        if G[y+1][x] == "#":
            flag = 1
    if flag == 1:
        return True
    else:
        return False

res = 1
for i in range(H):
    for j in range(W):
        x = j
        y = i
        if G[y][x] == "#":
            if search(x,y):
                pass
            else:
                res = 0
if res:
    print("Yes")
else:
    print("No")

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    double n1 = n + 1 - 0.0001;
    double low = n * 1. / 1.08;
    double high = n1 * 1. / 1.08;
    int now = (int)low;
    while (now <= high) {
        if (now >= low) {
            print(now);
            return 0;
        }
        now++;
    }
    print(":(");

    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

status = [[-1]*i for i in range(N)] #-1:new 0:active 1:finished
def has_cycle(v):
    a0,b0 = v
    status[a0][b0] = 0
    for a1,b1 in es[a0][b0]:
        if status[a1][b1] == 0: return True
        if status[a1][b1] == -1:
            if has_cycle((a1,b1)): return True
    status[a0][b0] = 1
    return False

for i in range(N):
    for j in range(i):
        if status[i][j] != -1: continue
        if has_cycle((i,j)):
            print(-1)
            exit()

from collections import deque
q = deque()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))

ans = -1
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            q.append((a1,b1,d+1))
print(ans)

Measured memory_bytes: 198604
/**
 *    author        : Trisha 
 *    created       : July 11, 2020 2:07 PM
 *    Problem Name  : A - The Number of Even Pairs
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/abc159/tasks/abc159_a
**/

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

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

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

    int sum=0;

    for(int i=1; i<n; i++){
        sum = sum + i;
    }

    for(int i=1; i<m; i++){
        sum = sum + i;
    }
    cout << sum << endl;

    return 0 ;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< pair<int,int> > vpii;
typedef vector< pair<ll,ll> > vpll;
typedef vector< vector<int> > matrix;
 
#define SET(Ar,val) memset(Ar,val,sizeof(Ar))
#define rep(i,val,n)  for(int i=val;i<n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LMAX LONG_LONG_MAX
#define LMIN LONG_LONG_MIN
#define IMAX INT_MAX
#define IMIN INT_MIN
#define M 1000000007
 
/*--------------------------------------------------------------------------------------------------------------------------------*/
 
template <class T> T modpower(T a,T b,T MOD)
{
    T ans=1;
    while(b!=0)
    {
        if(b%2==1)
        ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b/=2;
    }
    return ans;
}
 
void init()
{
    int N,mx = -1;
    cin >> N;
    int a[N+5],b[N+5];
    rep(i,0,N)
    {
        cin >> a[i];
        mx = max(mx,a[i]);
    }
    rep(i,0,N)
    {
        cin >> b[i];
        mx = max(mx,b[i]);
    }
    int ans = 0,d, u = log(mx);
    vi a1,b1;
    rep(i,0,30)
    {
        d = (1<<(i+1));
        a1.clear();
        b1.clear();
        rep(i,0,N)
        {
            a1.pb(a[i]%d);
            b1.pb(b[i]%d);
        }
        sort(b1.begin(),b1.end());
 
        /*for(auto it : b1)
            cout << it << endl ;*/
 
        rep(j,0,N)
        {
            int v = 0;
            int id1 = lower_bound(b1.begin(),b1.end(),d/2 - a1[j]) - b1.begin();
            int id2 = upper_bound(b1.begin(),b1.end(),d - a1[j] - 1) - b1.begin() - 1;
            if(id1 < N && id2>=id1)
                v += (id2-id1+1);
 
            int id3 = lower_bound(b1.begin(),b1.end(),(3*(d/2)) - a1[j]) - b1.begin();
            int id4 = upper_bound(b1.begin(),b1.end(),2*d - a1[j] - 1) - b1.begin() - 1;
            if(id3 < N && id4>=id3)
                v += (id4-id3+1);
 
            //cout << id1 << " " << id2 << " " << id3 << " " << id4 << endl ;
 
            if(v%2 == 1)
                ans^=(d/2);// cout <<"asd" << ans << endl;
         }
    }
    cout << ans << endl ;
}
 
int main()
{
    clock_t time1=clock();
	/*#ifndef ONLINE_JUDGE
	freopen("abc_091.in","r",stdin);
	#else
	//ONLINE_JUDGE
	#endif*/
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    init();
    clock_t time2 = clock();
    cerr <<"Time: " <<(double)(time2-time1)/CLOCKS_PER_SEC <<" seconds" <<endl;
	return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int , int>
#define psi pair <string , int >
#define pll pair <ll , ll>
using namespace std;
int main()
{
    string s;
    cin >> s;
    if(s.end() != find(s.begin() , s.end() , '7')) cout << "Yes" << '\n';
    else cout << "No" << '\n';
    return 0;
}



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

int main()
{
	int A, B, C, N;
	int count = 0;
	int res = 0;

	cin >> A >> B >> C >> N;

	for (int i = 0; i <= A; i++)
	{
		for (int j = 0; j <= B; j++)
		{
			for (int k = 0; k <= C; k++)
			{
				if (500 * i + 100 * j + 50 * k == N)
					count++;
			}
		}
	}

	cout << count << endl;

	return 0;
}

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

int main(void)
{
  int k, a, b;
  std::cin >> k;
  std::cin >> a >> b;

  int range = (b / k) * k;
  if (range >= a) {
    std::cout << "OK" << std::endl;
  }
  else {
    std::cout << "NG" << std::endl;
  }
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp make_pair
#define sz(x) ((int)(x).size())
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(),x.end()
#define y1 omg
#define INF 1000000010
#define FOR(x, n) for(int x=0; x<n; x++)
#define ini(x, n) memset(x, n, sizeof(x));
#define MOD ((int)1e9 + 7)
#define atoi(x) ((x)-'0')
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

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

int n;

int main() {
	cin >> n;
	cout << n + n * n + n * n * n;
}

Measured memory_bytes: 3620
// フェルマーの小定理
package main

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

const (
	m = 1000000007
)

func mpow(x, y int) int {
	result := 1
	for y != 0 {
		if y&1 == 1 {
			result *= x
			result %= m
		}
		x *= x
		x %= m
		y >>= 1
	}
	return result
}

var (
	fac []int
)

func initFactorialTable(n int) {
	fac = make([]int, n+1)
	fac[0] = 1
	for i := 0; i < n; i++ {
		fac[i+1] = fac[i] * (i + 1) % m
	}
}

func mcomb(n, k int) int {
	if n == 0 && k == 0 {
		return 1
	}
	if n < k || k < 0 {
		return 0
	}
	return (fac[n] * mpow(fac[n-k], m-2) % m) * mpow(fac[k], m-2) % m
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	X := readInt()
	Y := readInt()

	if (X+Y)%3 != 0 {
		fmt.Println(0)
		return
	}

	a := (2*Y - X) / 3
	b := (2*X - Y) / 3

	if a < 0 || b < 0 {
		fmt.Println(0)
		return
	}

	n := a + b
	k := min(a, b)

	initFactorialTable(n)

	fmt.Println(mcomb(n, k))
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


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

using namespace std;
#define int long long
#define die(x) return cout << x << "\n", 0

int32_t main() {
    int n, a, b, Xor = 0; cin >> n >> a >> b;
    if (n == 2) {
        if (a + b % 2 == 1 || a < b) die(-1);
        die((a - b)/2);
    }
    for (int i = 0; i < n - 2; i++) {
        int x; cin >> x;
        Xor ^= x;
    }
    int Sum = a + b - Xor;
    if (Sum < 0 || Sum % 2 == 1) die(-1);
    Sum /= 2;
    if ((Sum&Xor) || Sum > a || Sum + Xor < b) die(-1);
    int res = Sum;
    for (int i = 60; i >= 0; i--) if ((Xor>>i)&1) {
        Xor ^= 1ll<<i;
        if (res + Xor < b) res += (1ll<<i);
    }
    if (res == a + b) die(-1);
    cout << res - b << "\n";
}


Measured memory_bytes: 3588
package main
import (
  "container/list"
  "fmt"
  "strconv"
)
func main() {
  var ni,k,l,c,min int
  var n,d,max string
  m := make(map[string]struct{},10)
  for i:=0;i<10;i++ {
    m[strconv.Itoa(i)] = struct{}{}
  }
  fmt.Scan(&n,&k)
  for i:=0;i<k;i++ {
    fmt.Scan(&d)
    delete(m,d)
  }
  l = len(n)
  d = "0"
  for r,_ := range m {
    if d < r { d = r }
  }
  max = ""
  for i:=0;i<l;i++ {
    max += d
  }
  if max < n {
    max += d
    l++
  }
  queue := list.New()
  queue.PushBack("")
  c = 1
  for i:=0;i<l;i++ {
    for j:=0;j<c;j++ {
      t,_ := queue.Remove(queue.Front()).(string)
      for r,_ := range m {
        queue.PushBack(r+t)
      }
    }
    c *= len(m)
  }
  ni,_ = strconv.Atoi(n)
  min,_ = strconv.Atoi(max)
  for j:=0;j<c;j++ {
    t,_ := queue.Remove(queue.Front()).(string)
    ti,_ := strconv.Atoi(t)
    if ti >= ni && ti < min { min = ti }
  }
  fmt.Println(min)
}

Measured memory_bytes: 1024
//============================================================================
// Name        : ATcoder.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {

	int r,g,b;
	int u;
	cin>>r>>g>>b;

	r=r*100;
	g=g*10;

	u=r+g+b;

	if(u%4==0){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}


	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
前半と後半の分かれ目があいまい
123456
2個とる
12
34-56

56
12-34
前半で小さいのを除く
後半の大きいのを除く

DPかな
192837465

max-minが大きいほど効果的？
DP[3]=876-129
min3つ 129
max3つ 876
DP[4] 765-128
8
setなら早いかな
123456789
123 789確定

3
8 2 2 7 4 6 5 3 8
228 358
278
478
678 358

12345678oo
123 78o
234
345
対立箇所が最後だけになっちゃう
Nとおり全探索できる？sort?
set?
setの総和も出しとくとか
63
54
45
36

123456 789
3が境目
12345 6789
除いたのが6>=3 でスタメンなので3が候補入り
2が補欠

456 789
上位N個、下位N個だけおさえられればいい
setにいれて、最下をのぞけばいいとか
入った場合と除いた場合との差分だけとればいいか

*/
int main(){
  ll N,x=0,y=0,ans=-1e16; cin>>N;
  ll N2=N*2,N3=N*3;
  multiset<ll> Z1,Z2;
  vector<ll> A(N3+10,0),X(N3+10,0),Y(N3+10,0);
  for(ll i=0; i<N3; i++) cin>>A[i];
  //初期セット
  for(ll i=0; i<N; i++){
    ll j=N3-1-i;
    x+=A[i];
    y+=A[j];
    Z1.insert(A[i]);
    Z2.insert(A[j]);
    X[i]=x;
    Y[j]=y;
  }
  for(ll i=N; i<N2; i++){
    ll j=N3-1-i;
    x+=A[i];
    y+=A[j];
    Z1.insert(A[i]);
    Z2.insert(A[j]);
    auto IT1=Z1.begin(), IT2=Z2.end();
    IT2--;
    x-=*IT1;//前半は最小を削除
    y-=*IT2;//後半は最大を削除
    X[i]=x;
    Y[j]=y;
    Z1.erase(IT1);
    Z2.erase(IT2);
  }
//ans  
  for(ll i=N-1; i<N2; i++){
    ll tmp=X[i]-Y[i+1];
//cout<<"X["<<i<<"]:"<<X[i]<<" Y["<<i+1<<"]:"<<Y[i+1]<<endl;
    ans=max(ans,tmp);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 16640
from collections import deque


N , M = map(int,input().split())
ikusa_L = []
for i in range(M):
    ikusa_L.append(list(map(int,input().split())))
ikusa_L.sort(key=lambda x: x[1])
q = deque(ikusa_L)
q_1 = deque(q)
count = 0
while len(q_1) > 0:
    q_1 = deque([])
    a = q.popleft()
    cut = a[1]
    #print(cut,'aa')
    count += 1
    pop_count = 0
    for i in q:
        if not(i[0] < cut):
            q_1.append(i)
    q = deque(q_1)
    #print(q_1)

print(count)

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

int main(void)
{
    using namespace std;
    int resident[4][3][10] = {0};

    int n;
    int b, f, r, v;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &b, &f, &r, &v);
        resident[b - 1][f - 1][r - 1] += v;
    }

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 10; k++) {
                printf(" %d", resident[i][j][k]);
            }
            printf("\n");
        }
        if (i < 3) {
            printf("####################\n");
        }
    }
}


Measured memory_bytes: 3208
#include <iostream>
#include <string>

using namespace std;

int main() {
	string s;
	cin >> s;

	int cnt = 0;
	for (int i = 0; i < 4; ++i) {
		for (int j = i + 1; j < 4; ++j) {
			if (s.at(i) == s.at(j)) {
				++cnt;
			}
		}
	}
	if (cnt == 2) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    string S; cin >> S;
    int n = S.size();
    ll base = 0;
    rep(i, n){
        base = base * 10 + (S[i] - '0');
    }
    string T = "0123456789";
    sort(_all(T));
    string resS; ll res = -1, resnum = inf;
    do {
        ll cur = 0;
        rep(i, n){
            cur = cur * 10 + (T[i] - '0');
        }
        string curS = T.substr(0, n);
        ll diff = min(abs(base - cur), (ll)pow(10, n) - abs(base - cur));
        if(diff >= res){
            if(diff > res){
                resS = curS;
                resnum = cur;
            }
            else if(chmin(resnum, cur)){
                resS = curS;
            }
            res = diff;
        }
    } while(next_permutation(_all(T)));

    cout << resS << endl;

    return 0;
}

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

int a[200000];
signed main() {
	int b;
	cin >> b;
	int c = 0;
	for (int d = 0; d < b ; d++) {
		int e; scanf("%lld", &e);
		c += e;
		a[d + 1] = c;
	}
	for (int d = 1; d < b; d++) {
		a[b + d] = a[d] + c;
	}
	int MIN = LLONG_MAX / 3;
	int k = 0;
	for (int d = 0; d < b; d++) {
		int e = d + 1, f = d + b - 1;
		while (f - e >= 1) {
			int g = (e + f) / 2;
			auto h = lower_bound(a + d, a + d + b, a[d]+2*(a[g] - a[d]));
			if (h == a + d + b || a[d + b] - *h < a[g] - a[d]) {
				f = g;
			}
			else { e = g + 1; k = max(k, a[g] - a[d]);  }
		}
	}
	cout << k << endl;
}

Measured memory_bytes: 4732
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n;
string s;

int main(){
    cin >>s >>n;
    for(int i = 0; i < sz(s); i += n) printf("%c", s[i]);
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 256
//
//  main.cpp
//  A
//
//  Created by Hashizo on 2019/11/24.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

int main(int argc, const char * argv[]) {
	ll ans = 0;
	
	string SUN = "SUN";
	string MON = "MON";
	string TUE = "TUE";
	string WED = "WED";
	string THU = "THU";
	string FRI = "FRI";
	string SAT = "SAT";
	
	string s;
	cin >> s;

	if (s == SUN) {
		ans = 7;
	}
	else if (s == MON) {
		ans = 6;
	}
	else if (s == TUE) {
		ans = 5;
	}
	else if (s == WED) {
		ans = 4;
	}
	else if (s == THU) {
		ans = 3;
	}
	else if (s == FRI) {
		ans = 2;
	}
	else if (s == SAT) {
		ans = 1;
	}

	
	cout << ans << endl;
	return 0;
}


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

/* Typedefs */

typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

/* Consts */

const ll INF = 1e18;
const ll MOD = 998244353;
const ll MX = 1000001;

void solve() {
    
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
    // ll T; cin >> T;
    // while (T--) solve();
    int N, M; cin >> N >> M;
    int total = 0, day = 0;
    for(int i = 0; i < M; i++) {
        cin >> day;
        total += day;
    } 
    if (N - total >= 0) cout << N - total;
    else cout << -1;
    return 0;
    // You should actually read the stuff at the bottom
}

/* Stuff to Look For
 * -----------------
 * Int overflow, array bounds
 * Initializing all variables, avoid weird behavior
 * Edge cases(n = 0, n = 1)
 * Just return 0 after result
 */


Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>x;
	ll cnt=0;
	ll res=100;
	while(res<x){
		cnt++;
		res+=res/100;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 3568
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;

const int mod = 1e9 + 7;

int add(int i, int j) {
    if((i += j) >= mod) i -= mod;
    return i;
}

int A[200000];
int B[200001];

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> A[i];
    
    n = unique(A, A + n) - A;
    
    B[A[0]] = 1;
    for(int i = 1; i < n; ++i)
        B[A[i]] = add(B[A[i]], B[A[i - 1]]);
    
    cout << B[A[n - 1]];
    
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main( ){
    int N;
    cin>>N;
    vll X(N);
    int A,B;
    cin>>A>>B;
    rep(i,0,N)cin>>X[i];
    ll res=0;
    rep(i,0,N-1){
        if(A*(X[i+1]-X[i])>B){
            res+=B;
        }
        else{
            res+=A*(X[i+1]-X[i]);
        }
    }
    cout<<res<<endl;
    return 0;
}




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

class Combination {
    /*
        :)
    */
   public :

    const ll mod = 1e9 + 7;

    ll add(ll x, ll y) {
        x += y;
        if (x >= mod) return x - mod;
        return x;
    }
    ll sub(ll x, ll y) {
        x -= y;
        if (x < 0) return x + mod;
        return x;
    }
    ll mult(ll x, ll y) {
        return (x * y) % mod;
    }
    ll bin_pow(ll x, ll p) {
        if (p == 0) return 1;
        if (p & 1) return mult(x, bin_pow(x, p - 1));
        return bin_pow(mult(x, x), p / 2);
    }
    ll rev(ll x) {
        return bin_pow(x, mod - 2);
    }
    ll fact(ll a) {
        ll S = 1;
        for (ll I = 1 ; I <= a; I++)S = mult(S, I);
        return S;
    }
    ll Combin(ll x, ll y) {
        return mult(fact(x), rev(mult(fact(sub(x, y)), fact(y))));
    } 
};
int main () {
    ios_base::sync_with_stdio(false), cin.tie(0);

    ll a;
    cin >> a ;
    Combination cm;
    ll ans = cm.sub(cm.bin_pow(10, a), cm.mult(2, cm.bin_pow(9, a)));
    ans = cm.add(ans, cm.bin_pow(8, a));
    cout << ans << "\n";
}

Measured memory_bytes: 3648
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N int
	var A []int
	var Total [2]int

	fmt.Scan(&N)
	for i := 0; i < N; i++ {
		var a int
		fmt.Scan(&a)
		A = append(A, a)
	}

	sort.Sort(sort.Reverse(sort.IntSlice(A)))

	turn := 0
	for _, v := range A {
		Total[turn] += v
		if turn == 0 {
			turn = 1
		} else {
			turn = 0
		}
	}

	fmt.Println(Total[0] - Total[1])
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
//long long mo = 1e9 + 7;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    double A, B;
    cin >> A >> B;
    ll a = ll(ceil(A/0.08));
    ll b = B*10;
    ll M = max(a,b);
    if(ll(M*0.08) == A && ll(M*0.1) == B){
        cout << M  << endl;
    }else{
        cout << -1 << endl;
    }
}


Measured memory_bytes: 256
#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(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

ll gcd(ll x, ll y) //最大公約数
{
    if (y == 0)
        return x;
    if (y > x)
        return gcd(y, x);
    else
        return gcd(y, x % y);
}

int main()
{
    ll a, b, ans = 0;
    cin >> a >> b;
    ll c = gcd(a, b);
    for (ll i = 2; i <= 1000003; i++)
    {
        if (c % i == 0)
        {
            ans++;
            while (c % i == 0)
            {
                c /= i;
            }
        }
    }
    if (c > 1)
        ans++;
    cout << ++ans << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# Submit as pypy2


from __future__ import print_function, division, unicode_literals

__metaclass__ = type

try:
    input = raw_input
    range = xrange
except NameError:
    pass


import sys


# Test code requires python3
# from hypothesis import given
# from hypothesis import strategies as st
#
#
# def debug(*args, **kwargs):
#     print(*args, *('{}={}'.format(k, v) for k, v in kwargs.items()),


from collections import Counter


def main():
    N, M = map(int, input().split())
    AC = set()
    WA = Counter()
    for i in range(M):
        p, S = input().split()
        p = int(p) - 1
        S = S == 'AC'
        if S:
            AC.add(p)
        elif p not in AC:
            WA[p] += 1
    print(len(AC), sum(v for k, v in WA.items() if k in AC))


if __name__ == "__main__":
    main()


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


int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int N, T; cin >> N >> T;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  B.at(N-1) = A.at(N-1);
  for (int i = N-2; i >= 0; i--) B.at(i) = max(A.at(i), B.at(i+1));
  int vmax = 0;
  int vcnt = 0;
  for (int i = 0; i < N; i++) {
    int v = B.at(i) - A.at(i);
    if (v > vmax) {
      vmax = v;
      vcnt = 1;
    }else if (v == vmax) {
      vcnt++;
    }
  }
  cout << vcnt << endl;

  return 0;
}



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

int calc( int* a, string s )
{
    int sum = 0;
    for( int i = 0; i < s.size(); i++ )
        {
            if( 'a' < s[i] && s[i] < 'z' )
                sum += a[s[i]];
            else
            {
                sum += ( s[i] - '0' ) * a[s[i+1]];
                i++;
            }
        }
    return sum;
}

int main()
{
    int n, a[100];
    string s1, s2;
    char b[4];

    a['m'] = 1000;
    a['c'] = 100;
    a['x'] = 10;
    a['i'] = 1;

    b[0] = 'm';
    b[1] = 'c';
    b[2] = 'x';
    b[3] = 'i';

    cin >> n;

    for( int i = 0; i < n; i++ )
    {
        cin >> s1 >> s2;

        int res = calc( a, s1 ) + calc( a, s2 );

        int d = 1000, j = 0;
        while( res != 0 )
        {
            if( res / d == 0 );
            else if( res / d == 1 )
            {
                cout << b[j];
                res -= ( res / d ) * d;
            }
            else
            {
                cout << res / d << b[j];
                res -= ( res / d ) * d;
            }
            d /= 10;
            j++;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int s[100];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1);
    ll ans=0;
    for(int i=n-k+1;i<=n;i++) ans+=s[i];
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int a,b;
	cin>>a>>b;
	if(a%3==0||b%3==0||(a+b)%3==0)
	{
		cout<<"Possible"<<endl;
	}
	else
	{
		cout<<"Impossible"<<endl;
	}
}


Measured memory_bytes: 256
/**
 *    +--+--+--++--++--In the name of ALLAH--++--++--+--+--+
 *
 *    author:  skmonir
 *    created: 27-Jun-2020 18:03:12
**/

#include <bits/stdc++.h>

using namespace std;

#define endl                '\n'
#define TN                  typename
#define mod                 1000000007LL
#define len(x)              (int) x.size()
#define all(x)              x.begin(), x.end()
#define rall(x)             x.rbegin(), x.rend()
#define mem(x, y)           memset(x, y, sizeof x)
#define FOR(x, l, r)        for (int x = l; x <= r; ++x)
#define ROF(x, l, r)        for (int x = l; x >= r; --x)

template <TN T> inline void Int(T &n) {
    n = 0; int f = 1; int ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
    n = n * f;
}

template <TN T> T gcd(T a, T b) {return !b ? a : gcd(b, a % b);}
template <TN T> inline void umin(T &a, T b) {a = a < b ? a : b;}
template <TN T> inline void umax(T &a, T b) {a = a > b ? a : b;}
template <TN T, TN W> inline void Int(T &x, W &y) {Int(x), Int(y);}
template <TN T, TN W, TN Q> inline void Int(T &x, W &y, Q &z) {Int(x, y), Int(z);}

const int N = 1e5 + 7;
const int inf = 1e9 + 7;


int solve() {
    int res = 0;
    string s, t; cin >> s >> t;
    int n = (int) s.size();
    for (int i = 0; i < n; ++i) {
        if (s[i] != t[i]) {
            ++res;
        }
    }

    cout << res << endl;

    return 0;
}

int main() {
    int tests = 1, CaseNo = 0;
    // Int(tests);
    while (tests--) {
        //printf("Case %d: ", ++CaseNo);
        solve();
    }
    return 0;
}

Measured memory_bytes: 3912
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
#define fast() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

// a -> 0, b -> 1, c -> 2
// dp[i][j] := i日目にjをしたときのmax
int N, a[1 << 17], b[1 << 17], c[1 << 17], dp[1 << 17][3];

int main()
{
    fast();

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

    dp[1][0] = a[1], dp[1][1] = b[1], dp[1][2] = c[1];

    for (int i = 2; i <= N; i++)
    {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
    }

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}

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

long long n,m,a=1,c;
string s;
bool b;

int main(){
    cin>>n;
    vector<int>v;
    for (int i=1; i<=sqrt(n); i++){
        if (n%i==0){
            v.push_back(i);
        }
    }
    cout<<v[v.size()-1]+(n/v[v.size()-1])-2<<endl;
}


Measured memory_bytes: 3668