akhauriyash/Code-Regression huggingface dataset:
fun main(arr:Array<String>) {
    val (n,k) = readLine()!!.split(" ").map { it.toInt() }
    goal = k
    val results = (1..n).map { calc(it) }
    val max = results.maxBy { it.total}!!.total
    var win = 0L
    var total = 0L
    results.forEach {
        win += (it.win * (max/it.total))
        total += max
    }
    println("%.10f".format(win.toDouble()/total.toDouble()))
}

class Result(val win:Long, val total:Long)
var goal = 0

val dic = mutableMapOf<Int, Result>()
fun calc(num:Int):Result {
    if(num >= goal) {
        return Result(1, 1)
    }
    if(num <= 0) {
        return Result(0,1)
    }
    dic[num]?.let { return it }
    val ret = calc(num*2)
    val ans = Result(ret.win, ret.total * 2)
    dic[num] = ans
    return ans
}

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

pair<int, int> x[111111];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        x[i] = {a, b};
    }
    sort(x, x + n, [](auto a, auto b) {
        return a.first + a.second < b.first + b.second;
    });
    int l = -1e9, r = 0;
    for(int i = 0; i < n; i++) {
        if(x[i].first - x[i].second < l)
            continue;
        r++;
        l = max(l, x[i].first + x[i].second);
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 1024
while True:
  y,o = 0,0
  x  = int(input())
  if x == 0:
    break
  else:
    for q in range(12):
      m,n= map(int,raw_input().split())
      y += m-n
      if y >= x:
        o += 1
 
    if y >= x: print 12-o+1
    else:
      print "NA"

Measured memory_bytes: 4224
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2005000000
#define MOD 1000000007
#define N 805
#define M 100000000
#define LOG 22
#define KOK 4000000
using namespace std;

int vis[N][N];
int ans=inf,h,w,k,sx,sy;
vector<ii> v;
char s[N][N];
int wa[4][2]={1,0,0,1,-1,0,0,-1};

void solve(ii p) {

	umin(ans,min((min(p.st-1,h-p.st)+k-1)/k,(min(p.nd-1,w-p.nd)+k-1)/k));

}

void bfs() {

	queue<ii> q;

	q.push({sx,sy});

	vis[sx][sy]=0;

	while(!q.empty()) {

		ii pos=q.front();

		q.pop();

		if(vis[pos.st][pos.nd]>k) continue ;

		v.pb(pos);

		for(int i=0;i<4;i++) {

			int tx=pos.st+wa[i][0];
			int ty=pos.nd+wa[i][1];

			if(tx>h || tx<1 || ty>w || ty<1 || s[tx][ty]=='#') continue ;

			if(vis[tx][ty]<=vis[pos.st][pos.nd]+1) continue ;

			vis[tx][ty]=vis[pos.st][pos.nd]+1;

			q.push({tx,ty});

		}

	}

}

int main() {

	//freopen("input.txt","r",stdin);

	scanf("%d %d %d",&h,&w,&k);

	for(int i=1;i<=h;i++) {

		scanf("%s",s[i]+1);

		for(int j=1;j<=w;j++) {

			if(s[i][j]=='S') {

				sx=i;
				sy=j;

			}

			vis[i][j]=inf;

		}

	}

	bfs();

	for(auto p:v) {

		solve(p);

	}

	printf("%d",ans+1);

}

Measured memory_bytes: 13292
#include <stdio.h>

int main(void){
    int H, W;
    while(1){
    scanf("%d %d", &H, &W);
    if(H ==0&&W==0){
    break;
    }else{
    char S[H][W];
    int i, j;
        for (i = 0; i < H; i++){
            for (j = 0; j < W; j++){
                S[i][j] = '#';
                printf("%c", S[i][j]);
            }
            printf("\n");
        }
    printf("\n");
    }
}
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
//Remove below header file if c++ version greater than 14
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define ll long long int
#define pb push_back
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define deb(x) cout << #x << " "<< x << endl;
#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)

const int inf = -1000;
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a /gcd(a, b) *b;
}
typedef pair<int,int> pii;
const int mod = 1e9+7;
int main() {

   int r,d,x;
   cin>>r>>d>>x;

   int arr[11];
   arr[0] = x;

   Fo(i,1,11){

    arr[i] = r*arr[i-1] -d;
    cout<<arr[i]<<"\n";
   }































    return 0;

      }


Measured memory_bytes: 384
def C_SnukeFestival(N, A, B, C):
    a = sorted(A)
    b = sorted(B)
    c = sorted(C)

    import bisect
    ans = 0
    for j in range(N):
        # b[j]より小さなaの要素の個数
        i = bisect.bisect_left(a, b[j])
        # b[j]より大きなcの要素の個数
        k = N - bisect.bisect_right(c, b[j])
        ans += i * k
    return ans

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
print(C_SnukeFestival(N, A, B, C))

Measured memory_bytes: 23644
#include <iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    int l=s.size();
    int count =0;
    for (int i = 0; i < (l+1)/2; i++){
        if(s[i] != s[l-1-i]) count++;
    }
    cout << count;
}

Measured memory_bytes: 256
import fractions
n=int(input())
a=list(map(int,input().split()))
ans=1
l=[0]
r=[0]
for i in range(1,n+1):
    l.append(fractions.gcd(l[i-1],a[i-1]))
    r.append(fractions.gcd(r[i-1],a[n-i]))
r.reverse()
for i in range(n):
    buf=fractions.gcd(l[i],r[i+1])
    ans=max(ans,buf)
print(ans)

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

int main(){
	int n,f=0;
  	cin >> n;
  	for(int i=1;i<=9;i++){
    	for(int j=1;j<=9;j++){
        	if((i*j)==n)f=1;
        }
    }
  if(f==0)cout << "No";
  else cout << "Yes";
  
  return 0;
}

Measured memory_bytes: 256
//! 尺卂乃卂.卂ﾌ乇乇ㄒ
#include<bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
//Using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Ordered_set;

#define ll              long long
#define int             long long
#define ld             long double
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define vii             vector<vi>
#define vip            vector<pii>
#define mii             map<int,int>
#define mip             map<pair<int,int>,int>
#define mic             map<char,int> 
#define all(v)          v.begin(),v.end()  
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define lb(x)           (x&(-x))
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define itr(it,v)          for(auto it:v)
#define show(arr,n)     for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<"\n";
#define fi(i,n)         for(int i=0;i<n;i++)
#define fir(i,k,n)       for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ff               first 
#define ss               second
#define deb(x) cout << #x << "=" << x << endl
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define check(x) (x && cout<<"Yes\n")||(cout<<"No\n");
#define fin(s)          freopen(s,"r",stdin);  
#define fout(s)         freopen(s,"w",stdout);

const ld pi = 3.141592653589793238462643383279502884;
const int xd[]={-1,0,1,0};
const int yd[]={0,-1,0,1};
int XX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int YY[] = { -1, 0,  1, -1, 1, -1, 0, 1 };

int expo(int a,int b,int m);
int mmi(int a,int m);
void ipgraph(int m);

const int N=5*(1e5)+10;
vii adj(N);
int a[N];

void  solve(){

}
int32_t main()
{
    FIO
    char a;
    cin>>a;
    if(isupper(a)) cout<<"A\n";
    else cout<<"a\n";
    return 0;

}

void ipgraph(int m){
    int i, u, v;
    while(m--){
          cin>>u>>v;
         u--, v--;
    adj[u].pb(v);
    adj[v].pb(u);
    }
}
int expo(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return a;
    int val=(expo(a,b/2,m)*expo(a,b/2,m))%m;
    if(b & 1) return (val*a)%m;
    else return val;
}
int mmi(int a,int m){
    return expo(a,m-2,m);
}

Measured memory_bytes: 15016
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


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


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


a = inp()
b = inp()
c = inp()
d = inp()
print(min(a, b) + min(c , d))


Measured memory_bytes: 3572
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>

using namespace std;

struct State
{
    vector<int> to_solve;
    vector<bool> solved;
    int breaks;

    State(int size) : solved(size, false), breaks(0) {}
};

class Event
{
public:
    Event(int id, int time, int priority)
        : id_(id), time_(time), priority_(priority) {}

    virtual ~Event() {}

    virtual void Execute(State &state) const = 0;

    bool operator<(const Event &other) const
    {
        if (time_ != other.time_) {
            return time_ < other.time_;
        }
        return priority_ > other.priority_;
    }

protected:
    int id_;
    int time_;
    int priority_;
};

class BreakStart : public Event
{
public:
    BreakStart(int id, int time) : Event(id, time, 0) {}

    void Execute(State &state) const override
    {
        state.to_solve.push_back(id_);
    }
};

class BreakStop : public Event
{
public:
    BreakStop(int id, int time) : Event(id, time, 1) {}

    void Execute(State &state) const override
    {
        if (state.solved[id_]) {
            return;
        }

        state.breaks += 1;
        while (!state.to_solve.empty()) {
            state.solved[state.to_solve.back()] = true;
            state.to_solve.pop_back();
        }
    }
};

int main()
{
    int nodes, disputes;
    cin >> nodes >> disputes;

    vector<shared_ptr<Event>> events(2 * disputes, nullptr);
    for (int i = 0; i < disputes; i += 1) {
        int left, right;
        cin >> left >> right;
        events[2 * i] = make_shared<BreakStart>(i, left - 1);
        events[2 * i + 1] = make_shared<BreakStop>(i, right - 1);
    }

    sort(events.begin(), events.end(),
        [](const shared_ptr<Event> &a, const shared_ptr<Event> &b) {
            return (*a) < (*b);
        });

    State state(disputes);
    for (const auto &e : events) {
        e->Execute(state);
    }

    cout << state.breaks << "\n";
    return 0;
}


Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  ll n, k;
  cin >> n >> k;

  ll ans;
  if (k % 2 != 0) {
    ll x = n / k;
    ans = x * x * x;
  } else {
    k /= 2;
    ll x = (n + k) / k / 2;
    ll x2 = n / k / 2;
    ans = x * x * x + x2 * x2 * x2;
  }

  cout << ans << endl;

  return 0;
}

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

using i64 = int64_t;

constexpr int INF = 1e9;

int degree[805]={0};
bool visited[805]={0};

void init(){
    for(int i=0;i<=800;++i)degree[i] = 0;
}

pair<int, int> dfs(int n, int i, const vector<vector<int>> &graph){
    auto res = make_pair(i, 0);
    visited[i] = true;
    for(int j=1;j<=n;++j){
        if(graph[i][j] == 0)continue;
        if(visited[j])continue;
        auto tmp = dfs(n, j, graph);
        tmp.second += graph[i][j];
        if(tmp.second > res.second)res = tmp;
    }
    return res;
}

int compute_radius(int n, const vector<vector<int>> &graph){
    int s = 1;
    for(int i=1;i<=n;++i){
        visited[i] = false;
        if(degree[i] > 0)s = i;
    }
    auto tmp = dfs(n, s, graph);
    for(int i=1;i<=n;++i)visited[i] = false;
    tmp = dfs(n, tmp.first, graph);
    return tmp.second;
}

int main(){
    int n;
    while(cin >> n, n != 0){
        init();
        vector<vector<int>> graph(n+1, vector<int>(n+1));
        vector<int> v(n+1);
        for(int i=2;i<=n;++i){
            int p;
            cin >> p;
            v[i] = p;
            degree[i]++;
            degree[p]++;
        }
        int sum = 0;
        for(int i=2;i<=n;++i){
            int d;
            cin >> d;
            graph[i][v[i]] = d;
            graph[v[i]][i] = d;
            sum += d;
        }
        int tmp = 0;
        vector<pair<int, int>> vp;
        for(int i=1;i<=n;++i){
            if(degree[i] == 1){
                for(int j=1;j<=n;++j){
                    if(graph[i][j] == 0)continue;
                    tmp += graph[i][j];
                    graph[i][j] = 0;
                    graph[j][i] = 0;
                    vp.emplace_back(i,j);
                }
            }
        }
        for(auto e:vp){
            degree[e.first]--;
            degree[e.second]--;
        }
        int ans = tmp;
        sum -= tmp;
        ans += sum*3;
        ans -= compute_radius(n, graph);
        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 5600
#define ll long long
#define ldd long double
#define mpp make_pair
#define pb push_back
#define ff first
#define ss second
#include<bits/stdc++.h>
using namespace std;
int main(){
    ll n,m,y,x,z,h,t,i,j,k;
    ll cnt=0,cnt1=0,sum=0,sum1=0,flag=0,flag1=0,maxi=LLONG_MIN,mini=LLONG_MAX,temp=0,ans=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    ll a[n+1];
    for(i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=i){
            cnt++;
        }
    }
    if(cnt>2){
        cout<<"NO";
    }
    else{
        cout<<"YES";
    }


return 0;
}


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

using namespace std;

#define endl '\n'

string a, b;

vector<char> lcs(string a, string b)
{
    int n = a.size(), m = b.size();

    vector< vector<int> > X(n + 1, vector<int>(m + 1));
    vector< vector<int> > Y(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
          if (a[i] == b[j])
          {
              X[i + 1][j + 1] = X[i][j] + 1;
              Y[i + 1][j + 1] = 0;
          }
          else if (X[i + 1][j] < X[i][j + 1])
          {
              X[i + 1][j + 1] = X[i][j + 1];
              Y[i + 1][j + 1] = +1;
          }
          else
          {
              X[i + 1][j + 1] = X[i + 1][j];
              Y[i + 1][j + 1] = -1;
          }
        }
    }

    vector<char> c;
    for (int i = n, j = m; i > 0 && j > 0; )
    {
        if(Y[i][j] > 0)
           --i;
        else if (Y[i][j] < 0)
           --j;
        else
        {
            c.push_back(a[i - 1]);
            --i; --j;
        }
    }

    reverse(c.begin(), c.end());

    return c;
}

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

    cin >> a >> b;

    vector<char> lista(lcs(a, b));

    for(int i = 0; i < lista.size(); i++)
    {
        cout << lista[i];
    }
    cout << endl;
}


Measured memory_bytes: 70912
#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 IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define ll long long
#define endl "\n"
#define ar array
#define deb(x) cout << #x << " = " << x << endl
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const ll MAX = 2e5 + 1;

template <class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
inline ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
inline ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
inline ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
struct comp
{
    bool operator()(const pair<ll, ll> &x, const pair<ll, ll> &y) const
    {
        return x.first < y.first;
    }
};
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll pwr(ll x, ll n)
{
    if (n == 0)
        return 1;
    if (n & 1)
        return mul(x, pwr(mul(x, x), (n - 1) / 2));
    else
        return pwr(mul(x, x), n / 2);
}
ll modInv(ll n)
{
    return pwr(n, mod - 2);
}
ll modInverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}
ll a[4000];
int main()
{
    int t = 1;
    //cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll a[n + 1];
        vector<ll> pref(n + 1, 0);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (i == 0)
                pref[i] = a[i];
            else
                pref[i] = pref[i - 1] + a[i];
        }
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            ll diff = pref[n - 1] - pref[i];
            ans = add(ans, mul(a[i], diff));
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 6424
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
ll n,a[200001],p[200001],h[200001];
map<ll,ll> mp;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n){
		cin>>a[i];
		p[i]=a[i]+i;
		h[i]=a[i]-i;
		mp[h[i]]++;
	}
	ll ans=0;
	rep(i,n){
		p[i]=-p[i];
		ans+=mp[p[i]];
	}
	cout<<ans;
	re 0;
}

Measured memory_bytes: 30932
N, A, B, C, D = map(int, input().split())
S = input()
S = '#' + S
sunuke = A
funuke = B

while funuke < D:
    if S[funuke + 1] == '.':
        funuke += 1
    else:
        if S[funuke + 2] == '.':
            funuke += 2
        else:
            print('No')
            exit()
while sunuke < C:
    if S[sunuke + 1] == '.':
        sunuke += 1
    else:
        if S[sunuke + 2] == '.':
            sunuke += 2
        else:
            print('No')
            exit()

if C < D:
    print('Yes')
else:
    for i in range(B - 1, D):
        if S[i:i + 3] == '...':
            print('Yes')
            exit()
    else:
        print('No')

Measured memory_bytes: 3636
#![allow(unused_imports)]
#![allow(dead_code)]
use std::io::prelude::*;
use std::cmp::{max, min};
use std::collections::HashMap;

const MOD: i64 = 1e9 as i64 + 7; 

fn main(){
    let n: usize = read();
    let mut mp: HashMap<String, u64> = HashMap::new();
    for _ in 0..n{
        let mut s: Vec<char> = read::<String>().chars().collect();
        s.sort();
        let key: String = s.into_iter().collect();
        *mp.entry(key).or_insert(0) += 1;
    }
    let mut ans: u64 = 0;
    for (_, i) in mp{
        ans += i * (i - 1) / 2;
    }
    println!("{}", ans);
}

fn read<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define	IOS ios_base::sync_with_stdio(0);
#define en "\n"
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>


using namespace std;
const ll maxn=5e5+100,inf=1e18,LOG=23,mod=1e9 + 7;
int block = 300, timer = 0;
const ld EPS = 1e-7;

#define bt(i) (1 << (i))
#define int ll

int a[maxn], n,dp[maxn], mx, ans;

main()
{
	cin >> n;
	forn(1, i, n - 1)
	{
		ans += i;
	}
	cout << ans;
}

Measured memory_bytes: 2304
/*
    author:@bhaskar_8998
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace __gnu_pbds; 
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;  
typedef long long i64;
typedef vector<int> vi;
typedef vector<long> vl;
typedef pair<int,int>pii;
#define all(A) (A).begin(),(A).end()
#define pb push_back
#define MOD 1000000007
#define fastio() {ios_base::sync_with_stdio(false);cin.tie(NULL);}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    fastio();
    i64 ss[31];
    for(int i=1,ts=2;i<=30;i++){
        ss[i]=ts;
        ts*=2;
    }
    clock_t beg=clock();
    int t=1;
    // cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        unordered_map<int,int> m;
        m.clear();
        for(int i=0,l;i<k;i++){
            cin>>l;
            for(int j=0,ct;j<l;j++){
                cin>>ct;
                m[ct]+=1;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(m[i]==0)ans+=1;
        }
        cout<<ans;
    }

    clock_t end=clock(); 
    fprintf(stderr, "\n%lf sec\n", (double)(end-beg)/(CLOCKS_PER_SEC));
    return 0;
}


    

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

template <typename T, T (*op)(T, T), T id>
struct SegmentTree {
    int size;
    vector<T> node;

    SegmentTree(int n) : SegmentTree(vector<T>(n, id)) {}
    SegmentTree(const vector<T>& v) {
        size = 1;
        while (size < v.size()) size <<= 1;
        node.resize(2 * size, id);
        for (int i = 0; i < v.size(); i++) node[i + size] = v[i];
        for (int i = size - 1; i > 0; i--) node[i] = op(node[2 * i], node[2 * i + 1]);
    }

    T operator[](int k) const {
        return node[k + size];
    }

    void update(int k, const T& x) {
        k += size;
        node[k] = x;
        while (k >>= 1) node[k] = op(node[2 * k], node[2 * k + 1]);
    }

    T query(int l, int r) {
        T vl = id, vr = id;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = op(vl, node[l++]);
            if (r & 1) vr = op(node[--r], vr);
        }
        return op(vl, vr);
    }

    int find_first(int l, const function<bool(T)>& cond) {
        T vl = id;
        int r = 2 * size;
        for (l += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                T nxt = op(vl, node[l]);
                if (cond(nxt)) {
                    while (l < size) {
                        nxt = op(vl, node[2 * l]);
                        if (cond(nxt)) l = 2 * l;
                        else vl = nxt, l = 2 * l + 1;
                    }
                    return l - size;
                }
                vl = nxt;
                l++;
            }
        }
        return -1;
    }

    int find_last(int r, const function<bool(T)>& cond) {
        T vr = id;
        int l = size;
        for (r += size; l < r; l >>= 1, r >>= 1) {
            if (r & 1) {
                r--;
                T nxt = op(node[r], vr);
                if (cond(nxt)) {
                    while (r < size) {
                        nxt = op(node[2 * r + 1], vr);
                        if (cond(nxt)) r = 2 * r + 1;
                        else vr = nxt, r = 2 * r;
                    }
                    return r - size;
                }
                vr = nxt;
            }
        }
        return -1;
    }
};

int op(int a, int b) {
    return max(a, b);
}

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    SegmentTree<int, op, 0> st(A);
    for (int i = 0; i < Q; i++) {
        int T;
        cin >> T;
        if (T == 1) {
            int X, V;
            cin >> X >> V;
            st.update(X - 1, V);
        } else if (T == 2) {
            int L, R;
            cin >> L >> R;
            cout << st.query(L - 1, R) << "\n";
        } else {
            int X, V;
            cin >> X >> V;
            int j = st.find_first(X - 1, [&](int v) { return v >= V; });
            cout << (j == -1 ? N + 1 : j + 1) << "\n";
        }
    }
}

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

#define debug(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 << "]"<< endl;
    err(++it, args...);
}
using ll = long long;


int main() {
    int N, W;
    scanf("%d%d", &N, &W);
    vector<int> w (N+1), v (N+1);
    
    for (int i = 1; i<= N; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    vector<vector<ll>> dp(N+1, vector<ll> (W+1));

    for (int i = 1; i<= N; i++) {
        for (int j = 0; j<w[i]; j++) {
            dp[i][j] = dp[i-1][j];
        }
        for (int j = w[i]; j<= W; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
    printf("%lld\n", dp[N][W]);
    return 0;
}


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

// Remove GCC optimizer for codechef
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define endl "\n"
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 1e18 + 8;
const double PI = acos(-1);
const int N = 1e6 + 7;
int mod = 998244353;


int32_t main()
{
    IOS;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n;
    cin >> n;
    int ok = 1;
    vector<int> v(n+1);
    for(int i = 0; i <= n; i++)
        cin >> v[i];
    int l = v[n], r = v[n];
    stack<pair<int, int>> ranges;
    ranges.push({l, r});
    for(int i = n-1; i >= 0; i--)
    {
        l = (l + 1) / 2 + v[i];
        r = r + v[i];
        ranges.push({l, r});
    }
    int bound = 1;
    int i = 0, ans = 0;
    while(!ranges.empty())
    {
        auto p = ranges.top();
        ranges.pop();
        bound = min(bound, p.second);
        if(p.first <= bound && bound <= p.second)
        {
            ans += bound;
            bound -= v[i];
            bound *= 2;
        }
        else
            ok = 0;
        i++;
    }
    if(!ok)
        cout << -1;
    else
        cout << ans;
    return 0;
}

Measured memory_bytes: 5636
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N,K;cin>>N>>K;
  long ans=(N/K)*(N/K)*(N/K);
  if(K%2==0){
    long x=(N+K/2)/K;ans+=x*x*x;
  } 
  cout<<ans;
}



Measured memory_bytes: 256
N = int(input())
T = list(map(int, input().split()))
M = int(input())
P = [None] * M
X = [None] * M

for i in range(M):
    P[i], X[i] = map(int, input().split())

for i in range(M):
    S = T.copy()
    S[P[i] - 1] = X[i]
    print(sum(S))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
const ll mod=998244353;
ll n,ri,le,s0,f[1000005];
struct node{
	int x,y;
	bool operator<(node b)const{
		return x-y>b.x-b.y;
	}
}a[1000005];
char s[1000005];
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		ll l=0,r=0;
		scanf("%s",s+1);
		for(int j=1;s[j];j++)
			if(s[j]=='(')l++;
			else{
				if(l)l--;
				else r++;
			}
		if(!l and r)ri+=r;
		else if(l and !r)le+=l;
		else a[i]=(node){l,r};	
		s0+=l-r;
	}
	if(s0!=0)return puts("No"),0;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(le<a[i].y)
			return puts("No"),0;
		le-=a[i].y-a[i].x;
	}
	if(le!=ri)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int main(){
  int n,m;
  cin >> n >> m;
  Graph G(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int>dist(n,-1);
  dist[0] = 0;
  queue<int>q;
  q.push(0);
  while(!(q.empty())){
    int now = q.front();
    q.pop();
    for(auto i : G[now]){
      if(dist[i] != -1)continue;
      dist[i] = now;
      q.push(i);
    }
  }
  cout << "Yes" << endl;
  REP(i,1,n)cout << dist[i] + 1 << endl;
}


Measured memory_bytes: 10332
def fun(n, m):
        n_total = 0
        N = []
        for _ in range(n):
                s = int(input())
                N.append(s)
                n_total += s
        m_total = 0
        M = []
        for _ in range(m):
                s = int(input())
                M.append(s)
                m_total += s
        flag = False
        for i in N:
                for j in M:
                        if n_total -i+j==m_total+i-j:
                                print(i,j)
                                flag = True
                                break
                if flag:
                        break
        if not flag:
                print(-1)
n, m = map(int, input().split())
while n != 0:
        fun(n, m)
        n, m = map(int, input().split())


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

map<pair<int, int>, int> cnt;
void init(){
    for (int i = 1; i < 10; i++)
    {
        for (int j = 1; j < 10; j++)
        {
            cnt[make_pair(i, j)] = 0;
        }
        
    }
        
}
int main(){
    long long ans = 0;
    init();
    int n; cin >> n;
    int place = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i == place*10)
        {
            place*=10;
        }
        cnt[make_pair(i/place, i%10)]++;
    }
    for (int i = 1; i < 10; i++)
    {
        for (int j = 1; j < 10; j++)
        {
            ans += cnt[make_pair(i, j)] * cnt[make_pair(j, i)];   
        }
        
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque
import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,d = IL()
    d = d*d
    c = 0
    for _ in range(n):
        x,y = IL()
        if x*x + y*y <= d:
            c += 1

    print(c)
    exit()

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

vector<vector<int>> g;

using P = pair<int,int>; // <端点からの頂点の個数, 端点>
P dfs(int pre, int cur){
    P ans = {0, cur};
    for(int to : g[cur]) if(to != pre) {
        ans = max(ans, dfs(cur, to));
    }
    ans.first++;
    return ans;
}

int main(void){
    int n;
    cin >> n;
    g.resize(n);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int diameter = dfs(-1, dfs(-1, 0).second).first;
    cout << ((diameter % 3 != 2) ? "First" : "Second") << endl;

    return 0;
}


Measured memory_bytes: 26752
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,M = map(int,input().split())

edge = []
pass_edge = []
for i in range(M):
    a,b = map(int,input().split())
    if a < b:
        a,b = b,a#つねaの方が大きい
    if a==b:
        pass_edge.append([a,b])
    else:
        edge.append([a,b])

sorted_edge = sorted(edge)

bridge = {}
for i in range(1,N+1):
    bridge[i] = []

latest_bridge = [0,0]
for edge_i in sorted_edge:
    #edge = [a,b]
    if latest_bridge == edge_i:
        pass_edge.append(edge)
        pass
    else:
        latest_bridge = edge_i
        for port in range(2):
            bridge[edge_i[port]] = bridge[edge_i[port]]+[edge_i[port-1]]

# print(bridge)

def check(ie):
    a,b = ie
    used.append(a)
    copy_bridge = copy.deepcopy(bridge)
    copy_bridge[a] = list(set(copy_bridge[a])-set([b]))
    move = copy_bridge[a]
    isolate = 1
    while len(move)>0:
        pos = move.pop()
        if pos in used:
            pass
        elif pos == b:
            isolate = 0
        else:
            move = move+list(set(copy_bridge[pos]+used)-set(used))
            used.append(pos)
    return isolate

ans = 0

for ie in edge:
    # print("bi",ie)
    if ie in pass_edge:
        pass
    else:
        used = []

        ans += check(ie)
        # print(ans)

print(ans)


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

int main(){
    int S,h,m,s;
    int t1,t2;
    cin >> S;
    t1 = S%3600;
    t2 = t1%60;
    h= (S - t1)/3600;
    m=(t1 - t2)/60;
    s = t2;
    cout << h << ':' << m << ':' << s << endl;
    return 0;
}

Measured memory_bytes: 3080
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
#define ll long long

int main(){
    ll N;
    cin >> N;
    ll A[N];
    ll i;
    for(i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A,A+N);
    ll a=0,b=0;
    for(i=N-1;i>0;i--){
        if(A[i]==A[i-1]){
            if(a==0)a=A[i];else if(b==0)b=A[i];
            i--;
        }
    }
    cout << a*b;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		char x=s.charAt(0);
		s=scan.next();
		char y=s.charAt(0);
		scan.close();
		if(x>y)System.out.println(">");
		else if(x<y)System.out.println("<");
		else System.out.println("=");

	}

}


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



int main() {
  int a,b;
  cin >> a >> b;
  if (a>=13)
    cout << b << endl;
  if (a<=12 && 6<=a)
    cout << b/2 << endl;
  if (a<=5)
    cout << 0 << endl;
 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;



int main(){ 
    int H, W;
    cin >> H >> W;

    vector<vector<char>> s(H, vector<char>(W));

    rep(i,H) rep(j,W) {
        cin >> s[i][j];
    }

    vector<vector<int>> dp(H, vector<int>(W));

    if (s[0][0] == '#') dp[0][0] = 1;
    else dp[0][0] = 0;

    rep(i,H) rep(j,W) {
        if (i > 0 && j > 0) {
            int u, v;
            u = dp[i-1][j];
            v = dp[i][j-1];
            if (s[i-1][j] == '.' && s[i][j] == '#') u++;
            if (s[i][j-1] == '.' && s[i][j] == '#') v++;
            dp[i][j] = min(u,v);
        }
        if (i == 0 && j > 0) {
            dp[i][j] = dp[i][j-1];
            if (s[i][j-1] == '.' && s[i][j] == '#') dp[i][j]++;
        }
        if (i > 0 && j == 0) {
            dp[i][j] = dp[i-1][j];
            if (s[i-1][j] == '.' && s[i][j] == '#') dp[i][j]++;
        }
    }

    cout << dp[H-1][W-1] << endl;
   
    
}


Measured memory_bytes: 256
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  char a, b;
  cin >> a >> b;
  string sa, sb;
  for (char i = '1'; i <= b; i++) {
    sa += a;
  }
  for (char i = '1'; i <= a; i++) {
    sb += b;
  }
  if (sa <= sb) cout << sa << '\n';
  else cout << sb << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


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

const int MAX = 100010;
const int INF = 1e9;

struct State{
  int pos, c;
  State(int pos, int c) : pos(pos), c(c){}
};

int n;
int dp[MAX], cost[MAX];

int solve(){
  fill(dp, dp+MAX, INF);

  queue<State> que;
  que.push(State(0, 0));
  
  while(!que.empty()){
    State q = que.front(); que.pop();
    
    q.pos = min(n-1, q.pos);
    
    if(dp[q.pos] <= q.c || q.pos >= n) continue;
    dp[q.pos] = q.c;
    
    if(cost[q.pos] != 0){
      que.push(State(q.pos + cost[q.pos], q.c));
      continue;
    }
    
    for(int i = 1 ; i <= 6 ; i++){
      que.push(State(q.pos + i, q.c + 1));
    }
  }
  return dp[n-1];
}

int main(){
  while(cin >> n){
    for(int i = 0 ; i < n ; i++) cin >> cost[i];
    cout << solve() << endl;
  }
  return 0;
}

Measured memory_bytes: 2132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); i++)
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; }

vector<long long> compress(vector<long long> v) {
    vector<long long> val;
    for (long long i = 0; i < v.size(); i++) val.push_back(v[i]);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    vector<long long> res;
    for (long long i = 0; i < v.size(); i++) {
        long long id = lower_bound(val.begin(), val.end(), v[i]) - val.begin();
        res.push_back(id);
    }
    return res;
}

string id(ll x){
    string res = to_string(x);
    while(res.size()<6) res = '0' + res;
    return res;
}

int main(){
    ll n,m; cin>>n>>m;
    vector<vector<ll>> pref(n+1);
    vector<ll> cnt(n+1);
    vector<ll> p(m), y(m);
    rep(i,m){
        cin>>p[i]>>y[i];
        pref[p[i]].push_back(y[i]);
    }
    rep(i,n){
        pref[i+1] = compress(pref[i+1]);
    }
    rep(i,m){
        cout<<id(p[i])<<id(pref[p[i]][cnt[p[i]]] + 1)<<endl;
        cnt[p[i]]++;
    }
    return 0;
}

Measured memory_bytes: 9344
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

/*
全部偶奇が一致
二を足してていけばいい
いっこ仲間はずれ
仲間はずれ出ない方に1ずつたす
全部同じと同じ
最大値は一足しても変わんない
*/

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

int main(void){
    int A,B,C,M;
    scanf("%d %d %d",&A,&B,&C);
    int out,counter = 0,val = 0;
    M = max(max(A,B),C);
    if(A%2 == B%2&&B%2 == C%2){
        val = 3*M-(A+B+C);
        printf("%d\n",val/2);
    }
    else{
        if(A%2 == B%2){
            out = C;
        }
        else if(A%2 == C%2){
            out = B;
        }
        else{
            out = A;
        }
        if(M == out){
            val = 3*M-(A+B+C+2);
            val = val/2 + 1;
            printf("%d\n",val);
        }
        else{
            val = (M+1)*3-(A+B+C+2);
            val = val/2+1;
            printf("%d\n",val);
        }
    }

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define maxn 100005

using namespace std;

typedef  long long ll;
typedef pair <int,int> par;
typedef pair <int ,par> tri;

int N, C, K, T[maxn];
bool mark[maxn];

int main() {

    #ifdef acm
    freopen ("x.in", "r", stdin );
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> C >> K;
    for ( int i = 1; i <= N; i ++ ) cin >> T[i];
    sort ( T+1, T+1+N );

    int sol = 0;
    for ( int i = 1; i <= N; i++ ) {
        if ( mark[i] ) continue;
        mark[i] = true;
        for ( int j = i+1; j <= N && j <= i+C-1; j ++ ) {
            if ( T[j] > T[i]+K ) break;
            mark[j] = true;
        }
        sol ++;
    }

    cout << sol;
    return 0;
}


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

const int N = 2e5 + 5;

int nxt[N][26];

int go[26], n;

string s;

int dp[N];

int solve(int idx){

  if(idx == n + 1)return dp[idx] = 0;

  int &ret = dp[idx];

  if(~ret)return ret;

  ret = INT_MAX;

  for(int j = 0; j < 26; j++)
    ret = min(ret, 1 + solve(nxt[idx][j]));


  return ret;
}

void build(int idx){

  if(idx == n + 1)exit(0);

  for(int j = 0; j < 26; j++){
    if(dp[idx] == 1 + dp[nxt[idx][j]]){
      putchar('a' + j);
      build(nxt[idx][j]);
    }

  }

}

int main(){

  memset(dp, -1, sizeof dp);

  cin >> s;

  n = s.size();

  for(int i = 0; i < 26; i++)go[i] = n + 1;

  for(int i = n - 1; i >= -1; i--){

    for(int j = 0; j < 26; j++)
      nxt[i + 1][j] = go[j];

    if(i == -1)break;;

    go[s[i]-'a'] = i + 1;

  }

  solve(0);
  build(0);





  return 0;
}


Measured memory_bytes: 22020
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {

    int n, q;

    cin >> n >> q;
    vector<vector<int>> tree(n);

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

        int from, to;
        cin >> from >> to;

        from--;
        to--;

        tree[from].push_back(to);
        tree[to].push_back(from);
    }

    vector<int> values(n, 0);

    for(int i = 0; i < q; ++i) {
        int node, value;
        cin >> node >> value;

        values[node - 1] += value;
    }

    stack<pair<int, int>> s;
    vector<int> answers(n);
    vector<bool> visited(n, false);

    s.push(make_pair(0, 0));


    while(!s.empty()) {

        auto node = s.top(); s.pop();
        int index = node.first;

        if(visited[index])
            continue;
        visited[index] = true;

        int sum = node.second + values[index];
        answers[index] = sum;

        for(int i = 0; i < tree[index].size(); ++i) {

            s.push(make_pair(tree[index][i], sum));

        }

    }

    for(int i = 0; i < n; ++i) {
        if(i)
            cout << " ";
        cout << answers[i];
    }

    cout << endl;

    return 0;

}

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

signed main() {
  int H,W,N;cin>>H>>W>>N;
  std::vector<int> a(N),b(N);
  for(int i=0;i<N;i++)cin>>a[i]>>b[i];
  std::vector<int> v(10);
  typedef pair<int,int> P;
  v[0]=(H-2)*(W-2);
  map<P,int> m;
  set<P> s;
  for(int i=0;i<N;i++){
    for(int j=max(2LL,a[i]-1);j<min(H,a[i]+2);j++){
      for(int k=max(2LL,b[i]-1);k<min(W,b[i]+2);k++){
        m[P(j,k)]++;
        s.insert(P(j,k));
      }
    }
  }
  for(auto p:s){
    v[m[p]]++;
    v[0]--;
    //cout<<p.first<<" "<<p.second<<" "<<m[p]<<endl;
  }
  for(int i=0;i<10;i++)cout<<v[i]<<endl;
}


Measured memory_bytes: 114304
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Program{
  static void Main(){
	var order = ReadLine().Split(' ').Select(int.Parse).ToArray();
    var dices = ReadLine().Split(' ').Select(int.Parse).ToArray();
    var num = 0;
    var total = 0;
    decimal evalue = 0;
    
    for(var i = 0;i < order[1];i++){
      num += dices[i];
    }
    total = num;
    
    for(var i = 0;i < order[0]-order[1];i++){
      num = num-dices[i]+dices[order[1]+i];
      if(num>total){
        total = num;
      }
    }
    evalue = decimal.Divide(total + order[1],2);
    Write(evalue);
  }
}



Measured memory_bytes: 31068
def main():
    from builtins import int, map, list, print
    import sys, math
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input_number()
    print(N * 2 * math.pi)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9136
//here H and W is less so no need of recursion style dp...do the dp tabulation
#include<bits/stdc++.h>
#define N 1000000007
using namespace std;

int dp[10001][10001];  //global has default zero
int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>>v;
    v.assign(h,vector<char>(w,'0'));
    for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)cin>>v[i][j];
                             //here dp is for number of ways so no ways means dp is 0
    //these extra row and column used in states of first row and column
                                        //or use condition if we dont want to use these extra row and column
     dp[1][1]=1;
     for(int i=1;i<=h;i++){
         for(int j=1;j<=w;j++){
             if(i==1&&j==1)continue;
             if(v[i-1][j-1]=='#')dp[i][j]=0;        //it makes our condition satisy as we make reaching ways to # 0 s further ways from here also 0
             else
             dp[i][j]=(dp[i-1][j]%N+dp[i][j-1]%N)%N;
         }
     }
     cout<<dp[h][w]<<endl;
     return 0;                               
}


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

void solve(){
    int a,b;
    cin >> a >> b;
    cout << max(a+b, max(a-b, a*b)) << endl;
}


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

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include<bits/stdc++.h>

#define KhaledAshraf ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define modulo lln(1e9+7)
#define PI acos(-1.0)
#define setzero(a) memset(a,0,sizeof(a))
#define setdp(a) memset(a,-1,sizeof(a))
typedef int lln;

namespace patch
{
template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}
}
using namespace std;

int main(){
    KhaledAshraf
    lln N;
    string S,T;
    cin>>N>>S>>T;
    for(int i=0;i<N;i++){
        bool ok=true;
        for(int j=i;j<N;j++){
            if(S[j]!=T[j-i]){
                ok=false;
                break;
            }
        }
        if(ok){
            cout<<N+i;
            return 0;
        }
    }
    cout<<N*2;


	return 0;
}


Measured memory_bytes: 256