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

#define MOD 1000000007
#define lli long long int
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = n - 1; ~i; i--)
#define pb push_back
#define mkp make_pair
#define endl "\n"

using namespace std;

bool enable_test_case = false;
bool enable_google = false;

void solve()
{
    lli n, k;
    cin >> n >> k;
    lli h[n];
    lli dp[n];
    rep(i, n)
    {
        cin >> h[i];
        dp[i] = INT64_MAX;
    }
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    if (k != 1)
    {
        dp[2] = min(abs(h[0] - h[2]), abs(h[0] - h[1]) + abs(h[1] - h[2]));
    }
    else
    {
        dp[2] = dp[1] + abs(h[1] - h[2]);
    }

    for (int i = 3; i < n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if ((i - j) >= 0)
                dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]));
        }
    }
    cout << dp[n - 1] << endl;
}

void google_contests(int t)
{
    cout << "Case #" << t + 1 << ": ";
}

void test_case()
{
    if (enable_test_case)
    {
        lli t;
        cin >> t;
        rep(i, t)
        {
            if (enable_google)
                google_contests(i);
            solve();
        }
    }
    else
    {
        solve();
    }
}

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

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    test_case();

    return 0;
}


Measured memory_bytes: 5164
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;



int cost(vector<int> &a, int mid){
  int ans = 0;
  for (int i = 0; i < a.size(); ++i) {
    ans += pow(abs(a[i]-mid), 2);
  }
  return ans;
}


int main() {
  //
//  cout << INF << endl;

  long long INF = (1 << 30);
  int N;
  cin >> N;
  vector<int> a(N, 0);
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }

  //
  int c0 = cost(a, 0), cl = cost(a, -1), cr = cost(a, 1);
  if(c0 < cl && c0 < cr){
    cout << c0 << endl;
    return 0;
  }

  int left, right;
  if(cl < cr){
    c0 = cl;
    left = -100;
    right = -1;
  }else{
    c0 = cr;
    left = 1;
    right = 100;
  }

  for (int i = left; i <= right; ++i) {
    c0 = min(c0, cost(a, i));
  }
  cout << c0 << endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<double> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<double>> dp(n + 5, vector<double>(n + 5, 0));
  dp[0][0] = 1;
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++){
      dp[i + 1][j + 1] += dp[i][j] * a[i];
      dp[i + 1][j] += dp[i][j] * (1 - a[i]);
    }
  }
  double ans = 0;
  for(int i = n / 2 + 1; i <= n; i++) {
    ans += dp[n][i];
  }

  printf("%.10f\n", ans);

  return 0;
}

Measured memory_bytes: 70912
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=3000;

int n;
int a[MAXN];

ll dp[MAXN][MAXN];

ll solve() {
	REP(i,n) dp[i][i]=a[i];
	FORE(len,2,n) REPE(i,n-len) {
		int j=i+len-1;
		dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);
	}
	return dp[0][n-1];
}

void run() {
	scanf("%d",&n);
	REP(i,n) scanf("%d",&a[i]);
	printf("%lld\n",solve());
}

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


Measured memory_bytes: 70016
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//ここまでテンプレ
int main(){
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	cout<<min(A,B)+min(C,D)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;

int n,q;
int S[4*maxn],lazy[4*maxn];

void upd(int id,int l,int r,int ql,int qr,int v) {
    if (ql==l && qr==r) {
        lazy[id]=v;
        return;
    }
    if (lazy[id]!=-1005) {
        S[id]=lazy[id]*(r-l+1);
        if (l!=r) {
            lazy[id<<1]=lazy[id];
            lazy[id<<1|1]=lazy[id];
        }
        lazy[id]=-1005;
    }
    int m=l+r>>1;
    if (qr<=m) upd(id<<1,l,m,ql,qr,v);
    else if (ql>m) upd(id<<1|1,m+1,r,ql,qr,v);
    else upd(id<<1,l,m,ql,m,v),
         upd(id<<1|1,m+1,r,m+1,qr,v);
    S[id]=(lazy[id<<1]!=-1005?lazy[id<<1]*(m-l+1):S[id<<1])+
          (lazy[id<<1|1]!=-1005?lazy[id<<1|1]*(r-m):S[id<<1|1]);
}

int query(int id,int l,int r,int ql,int qr) {
    if (lazy[id]!=-1005) {
        S[id]=lazy[id]*(r-l+1);
        if (l!=r) {
            lazy[id<<1]=lazy[id];
            lazy[id<<1|1]=lazy[id];
        }
        lazy[id]=-1005;
    }
    if (ql==l && qr==r) return S[id];
    int m=l+r>>1;
    if (qr<=m) return query(id<<1,l,m,ql,qr);
    else if (ql>m) return query(id<<1|1,m+1,r,ql,qr);
    else return query(id<<1,l,m,ql,m)+query(id<<1|1,m+1,r,m+1,qr);
}

int main() {
    cin>>n>>q;
    for (int i=0;i<q;i++) {
        int f,s,t,x; cin>>f>>s>>t;
        if (f) cout<<query(1,0,n-1,s,t)<<'\n';
        else {
            cin>>x;
            upd(1,0,n-1,s,t,x);
        }
    }
}


Measured memory_bytes: 5124
n,m,q = map(int,input().split())

abcd_list = []
for i in range(q):
    abcd_list.append(list(map(int,input().split())))

a = [1]*n
def next_a(a):
    if a[-1] != m:
        a[-1] += 1
    else:
        d = n-1
        while d > 0 and a[d] == m:
            d-=1
        if d < 0:
            return a
        a[d] += 1
        next = a[d]
        for i in range(d,n):
            a[i] = next
max = -1
a[-1] = 0
while sum(a) != n*m:
    next_a(a)
    test = 0
    for i in range(q):
        if a[abcd_list[i][1]-1] - a[abcd_list[i][0]-1] == abcd_list[i][2]:
            test += abcd_list[i][3] 
    if test > max:
        max = test

print(max)

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

int main() {
  int n;
  int sum = 0;
  cin >> n;
  vector<int> b(n);
  
  for(int i=0;i<n-1;i++){
    cin >> b.at(i);
  }
  
  sum += b.at(0);
  
  for(int i=0;i<n-2;i++){
    if(b.at(i) <= b.at(i+1)) sum += b.at(i);
    else sum += b.at(i+1);
  }
  
  sum += b.at(n-2);
  
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define boost ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define M 1000000007
#define eb emplace_back
#define watch(x) cout << (#x) <<" is "<< x <<"\n";


using namespace std;
//const int N = 1e6;

int32_t main(){
  boost;
  int tc = 1; //cin >> tc;
  while(tc--)
  {
    int n; cin >> n;
    int ans = 0;
    for(int i=1; i<n; i++)
    {
      ans += n/i;
      if(n%i == 0)
        ans--;
    }
    cout << ans <<"\n";
  }
}



Measured memory_bytes: 3644
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
uf=UnionFind(n)
ans=[n*(n-1)//2for i in range(m)]
cnt=0
a=[];b=[]
for i in range(m):
  A,B=map(int,input().split())
  A-=1;B-=1
  a.append(A);b.append(B)
a.reverse(); b.reverse()
for i in range(m):
  ans[i]-=cnt
  if not uf.same(a[i],b[i]):
    cnt+=uf.size(a[i])*uf.size(b[i])
    uf.union(a[i],b[i])

for x in reversed(ans):
  print(x)

Measured memory_bytes: 17132
import heapq


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    # print(n, m)
    # print(ab)
    index = 0
    ans = []
    money = 0
    for day in range(1, m+1):
        # print(day)
        while index < n and ab[index][0] <= day:
            heapq.heappush(ans, -ab[index][1])
            index += 1
            # print(ans)
        if ans:
            money -= heapq.heappop(ans)

    print(money)


if __name__ == "__main__":
    main()


Measured memory_bytes: 31952
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

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

using namespace std;
typedef long long int ll;
const ll INF = 1e18;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll ans = -INF;
    ans = max(ans, a * c);
    ans = max(ans, a * d);
    ans = max(ans, b * c);
    ans = max(ans, b * d);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int main(){
    int m,f,r;
    while(true){
        cin >> m >> f >> r;
        if(m==-1 && f==-1 && r==-1){
            break;
        }
        if(m==-1 || f==-1){
            cout << "F" << endl;
            continue;
        }else if(80<=m+f){
            cout << "A" << endl;
            continue;
        }else if(65<=m+f && m+f<80){
            cout << "B" << endl;
            continue;
        }else if(50<=m+f && m+f<65){
            cout << "C" << endl;
            continue;
        }else if(30<=m+f && m+f<50 && 50 <= r){
            cout << "C" << endl;
            continue;
        }else if(30<=m+f && m+f<50 && r<50){
            cout << "D" << endl;
            continue;
        }else if(m+f<30){
            cout << "F" << endl;
            continue;
        }



    }


    return 0;
}



Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;int main(){int n,k;cin>>n>>k;vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];sort(a.begin(),a.end());if(k>n)k=n;cout<<accumulate(a.begin(),a.end()-k,(long long)0)<<endl;}

Measured memory_bytes: 1024
#include <iostream>
#include <queue>
#include <set>
#include <cstring>
#include <cstdio>

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

template<class T> T getAs(){ T v; std::cin >> v; return v; }
int getInt(){ return getAs<int>(); }

using namespace std;

#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

using namespace std;

const int _dx[] = { 0, 1, 0,-1};
const int _dy[] = {-1, 0, 1, 0};

enum DIR{
  NORTH = 0,
  EAST  = 1,
  SOUTH = 2,
  WEST  = 3
};

string s;
string g[1000];
int memo[1000][1000][4];
int nextdir[1000010][4];
int w, h, n;

bool cango(int x, int y, int d){
  int xx = x + _dx[d];
  int yy = y + _dy[d];

  return ISIN(xx, yy, w, h) && g[yy][xx] == '.';
}

struct data{
  int x;
  int y;
  int d;
  int cnt;

  data(int a, int b, int c, int e) : x(a), y(b), d(c), cnt(e) {}
};

bool operator < (const data &lhs, const data &rhs){
  return lhs.cnt > rhs.cnt;
}

int main(){
  while(true){
    h = getInt();
    w = getInt();
    n = getInt();

    int sx, sy, sd = NORTH;
    int gx, gy;

    if(h + w + n == 0) break;

    cin >> s;

    REP(i,h){
      cin >> g[i];

      REP(j,w){
        if(g[i][j] == 'S'){
          sx = j; sy = i; g[i][j] = '.';
        }else if(g[i][j] == 'G'){
          gx = j; gy = i; g[i][j] = '.';
        }
      }
    }

    memset(memo, -1, sizeof(memo));

    for(int i = n - 1; i >= 0; i--){
      REP(j,4) nextdir[i][j] = n + 2;

      nextdir[i][s[i] == 'L' ? 3 : 1] = i + 1;
      nextdir[i][0] = i;
      if(i != n - 1){
        REP(j,4){
          int k = (j + (s[i] == 'L' ? 3 : 1)) % 4;
          nextdir[i][k] = min(nextdir[i][k], nextdir[i + 1][j]);
        }
      }
    }

    /*
    REP(j,n) printf("  %c", s[j]); puts("");
    REP(i,4){
      REP(j,n){
        printf("%2d ", nextdir[j][i]);
      }
      puts("");
    }
    REP(i,h) cout << g[i] << endl;
    */

    bool ans = false;
    priority_queue<data> pq;
    pq.push(data(sx, sy, sd, 0));

    while(pq.size()){
      data dt = pq.top(); pq.pop();
      int x = dt.x;
      int y = dt.y;
      int d = dt.d;
      int cnt = dt.cnt;

      if(memo[y][x][d] != -1) continue;
      memo[y][x][d] = cnt;
      //printf("%d %d %d %d\n", x, y, d, cnt);

      if(cnt != n){
        REP(i,4) if(nextdir[cnt][i] != n + 2){
          int dd = (d + i) % 4;
          if(memo[y][x][dd] == -1) pq.push(data(x, y, dd, nextdir[cnt][i]));
        }
      }

      while(cango(x, y, d)){
        x += _dx[d]; y += _dy[d];
        if(gx == x && gy == y){ ans = true; goto end; }
        if(cnt != n){
          int nextd = (d + (s[cnt] == 'L' ? 3 : 1)) % 4;
          if(memo[y][x][nextd] == -1){
            pq.push(data(x, y, nextd, cnt + 1));
          }
        }
      }
    }

  end:;
    puts(ans ? "Yes" : "No");
  }

  return 0;
}

Measured memory_bytes: 0
// (c) 2020, redotter

// Roses are red
// The Tardis is blue
// The Doctor once said
// Rose Tyler...

#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#pragma comment(linker, "/stack:500000000")
#endif

#define pb push_back
#define the(a) (a).begin(), (a).end()
#define ft first
#define sd second
#define endl "\n"
#define forn(i, n) for (int i = 0; i < (n); i++)
#define forr(i, s, n) for (int i = (s); i < (n); i++)

using i64 = long long;
using i32 = int;
using f64 = long double;

template <class T> using vec = vector<T>;
using str = string; using p64 = pair<i64, i64>;
using v64 = vec<i64>; using vv64 = vec<v64>;
using s64 = set<i64>; using m64 = map<i64, i64>;
template <size_t Size1> using a64 = array<i64, Size1>;
template <size_t Size1, size_t Size2> using aa64 = array<a64<Size2>, Size1>;
template <class T> using hash_set = unordered_set<T>;
template <class T, class U> using hash_map = unordered_map<T, U>;

mt19937 gen(998244353);
const i64 inf = numeric_limits<i64>::max() / 2;

template <class T> inline i64 len(const T& a) { return (i64)(a.size()); }
inline void fast() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
template <class T, class S>
inline bool check_min(T& a, S b) { if (a > b) return a = b, 1; return 0; }
template <class T, class S>
inline bool check_max(T& a, S b) { if (a < b) return a = b, 1; return 0; }

void read() {}
template<class T, class ...U>
void read(T& a, U& ...b) { cin >> a; read(b...); }
void print() {}
template<class T, class ...U>
void print(const T& a, const U& ...b) { cout << a << " "; print(b...); }
void println() { cout << "\n"; }
template<class T, class ...U>
void println(const T& a, const U& ...b) { cout << a << " "; println(b...); }

struct Problem {
	void files(str in, str out) {
#ifdef ONLINE_JUDGE
		freopen(in.c_str(), "r", stdin), freopen(out.c_str(), "w", stdout);
#endif
	}
	void solve(), input();
	void many() { i32 t; cin >> t; while (t--) input(), solve(); }
	void make(bool mt = 0) { if (mt) many(); else input(), solve(); }
} problem;

signed main() {
	fast();
	problem.make();
#ifdef _DEBUG
	println(); println("[finished]"); system("pause > nul");
#endif
	return 0;
}

struct Graph {
	i64 n;
	vv64 adj;
	Graph() {}
	Graph(i64 n_) {
		n = n_;
		adj.resize(n);
	}
	void add(i64 v, i64 u) {
		adj[v].pb(u);
	}
};

i64 n, m;
Graph g;

v64 used;
v64 order;
void topsort(i64 v) {
	used[v] = 1;
	for (i64 u : g.adj[v]) {
		if (used[u]) continue;
		topsort(u);
	}
	order.pb(v);
}

void Problem::solve() {
	used.assign(n, 0);
	forn(v, n) {
		if (!used[v]) {
			topsort(v);
		}
	}
	reverse(the(order));
	v64 dp(n, 0);
	for (i64 v : order) {
		for (i64 u : g.adj[v]) {
			check_max(dp[u], dp[v] + 1);
		}
	}
	i64 ans = *max_element(the(dp));
	println(ans);
}

void Problem::input() {
	read(n, m);
	g = Graph(n);
	forn(i, m) {
		i64 v, u;
		read(v, u);
		--v, --u;
		g.add(v, u);
	}
}


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

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


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

using namespace std;

#define INF 210000000
#define int long long

signed main() {
	string s;
	cin >> s;
	int n = s.length() / 2;
	int ans = 0;
	for (int i=0;i<n;i++){
		if(s[i] != s[s.length()-1-i]) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define INF (1<<20)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

map<char, int> m;

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

	rep(i, s.size()) m[s[i]] = 1;
	
	for (int i = 'a'; i <= 'z'; i++) {
		if (m[i] != 1) {
			printf("%c\n",i);
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
#define SKILLER ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N=1e4;
string s, t;
int n, m, totW;
//int w[105], v[105];
int cache[N][N];
 
int dp(int i, int j)
{
  if(i == n)return 0;
  if(j == m)return 0;
  if(cache[i][j] != -1)return cache[i][j];
  if(s[i] == t[j]){
    cache[i][j] = dp(i+1, j+1) + 1 ;
    return cache[i][j];
  }
  cache[i][j] = max(dp(i+1, j), dp(i, j+1));
  return cache[i][j] ;
}
void path(int i, int j){
    if(i == n)return;
    if(j == m)return;
    if(s[i] == t[j]){
        cout<<s[i];
        return path(i+1, j+1);
    }
    if(cache[i][j] == cache[i+1][j])
         return path(i+1, j);
    else return path(i , j+1);
}
int32_t main()
{
    SKILLER

    memset(cache, -1, sizeof(cache));
    cin >> s >>  t;
    n = s.length();
    m = t.length();
    int ans = dp(0,0);
   // cout<<ans<<"\n";
    path(0, 0);
    return 0;
}

Measured memory_bytes: 781824
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = map(int, input().split())
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)


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

#define maxn 200005
typedef long long ll;
typedef double db;

int n, k;
int a[maxn];
int b[maxn];

typedef pair<int, int> pii;
vector<pii> ans;
multiset<pii> s;
multiset<pii> aux;

int printAns(int i, int p) {

	//cout << i << ' ' << aux.size() << endl;

	//cout << ans.size() << ' ' << p << endl;
	if(ans.size() + n - 2 + p > 2 * n)
		return 0;

	for (int j = i - 1; j > 0; j--)
		ans.push_back(make_pair(j, j - 1));
	for (int j = i; j < n - 1; ++j)
		ans.push_back(make_pair(j, j + 1));

	//cout << i << endl;

	cout << ans.size() << endl;
	for (unsigned int i = 0; i < ans.size(); ++i)
		cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << endl;
	return 1;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s.insert(make_pair(a[i], i));
	}

	multiset<pii>::iterator iter;
	iter = s.end();
	iter--;
	if ((*s.begin()).first >= 0) {
		cout << n - 1 << endl;
		for (int i = 0; i < n - 1; ++i)
			cout << i + 1 << ' ' << i + 2 << endl;
	} else if ((*iter).first <= 0) {
		cout << n - 1 << endl;
		for (int i = n - 1; i > 0; i--)
			cout << i + 1 << ' ' << i << endl;
	} else {
		for (int i = 0; i < n; ++i) {
			//cout << "i "<< i << endl;
			ans.clear();
			aux.clear();
			copy(a, a + n, b);
			for (multiset<pii>::iterator iter = s.begin(); iter != s.end();
					iter++) {
				//cout << (*iter).first << ' ' << (*iter).second << endl;
				aux.insert(make_pair((*iter).first, (*iter).second));
			}
			for (int j = 0; j < n; ++j) {
				//cout << "j " << j << endl;
				if (j < i && b[j] > 0) {
					//cout << "entro 1" << endl;
					multiset<pii>::iterator iter = aux.begin();
					int	mini = (*iter).first;
					int posMini = (*iter).second;
					int tmp = ceil(-b[j] / db(mini));
					//cout << "tmp " << tmp << endl;
					if (ans.size() + tmp > 2 * n)
						break;
					//cout << "tmp " << tmp << endl;
					int ol = b[j];
					int ne = b[j] + tmp * mini;
					b[j] = ne;
					aux.erase(make_pair(ol, j));
					aux.insert(make_pair(ne, j));
					for (int k = 0; k < tmp; ++k)
						ans.push_back(make_pair(posMini, j));
				} else if (j >= i && b[j] < 0) {
					//cout << "entro 2" << endl;
					multiset<pii>::iterator iter = aux.end();
					iter--;
					int	maxi = (*iter).first;
					int posMaxi = (*iter).second;
					//cout << i << ' ' << j << ' ' << maxi << ' ' << posMaxi << endl;
					int tmp = ceil(-b[j] / db(maxi));
					//cout << tmp << endl;
					if (ans.size() + tmp > 2 * n)
						break;
					int ol = b[j];
					int ne = b[j] + tmp * maxi;
					b[j] = ne;
					aux.erase(make_pair(ol, j));
					aux.insert(make_pair(ne, j));

					for (int k = 0; k < tmp; ++k)
						ans.push_back(make_pair(posMaxi, j));
				}
				multiset<pii>::iterator iter2 = aux.end();
				iter2--;
				//cout << (*iter2).first << endl;
				if((*iter2).first <= 0)
				{
					if(printAns(n, 1))
						return 0;
				}
				else if((*aux.begin()).first >= 0)
				{
					if(printAns(0, 1))
						return 0;
				}
				else if (j == n - 1 && printAns(i, 0))
					return 0;
			}
		}
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdio.h>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <utility>
#include <string>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <functional>

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define SORT(v) sort(ALL(v))
//#define scanf scanf_s

int main()
{
	int n, p;
	while (cin >> n >> p, n)
	{
		int m[55] = {};
		int wan = p;
		int i, j;
		j = 0;
		for (i = 1; i < 1000005; i++)
		{
			if (wan>0)
			{
				wan--;
				m[j]++;
				if (m[j] == p)
				{
					cout << j << endl;
					break;
				}
			}
			else
			{
				wan += m[j];
				m[j] = 0;
			}

			j++;
			if (j >= n) j = 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T>
void inputVector(vector<T> &v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

bool F[100][10];
int P[100][11];

signed main() {
    int N;
    cin >> N;

    rep(i, N) {
        rep(j, 10) {
            cin >> F[i][j];
        }
    }
    rep(i, N) {
        rep(j, 11) {
            cin >> P[i][j];
        }
    }

    int ret = LLONG_MIN;
    rep(i, 1 << 10) {
        if (i == 0) continue;
        int tmp = 0;
        rep(j, N) {
            int cnt = 0;
            rep(k, 10) {
                if ((i & (1 << k)) == 0) continue;
                cnt += F[j][k];
            }
            tmp += P[j][cnt];
        }
        ret = max(ret, tmp);
    }

    cout << ret << endl;
}


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

int main(){
  int n;
  cin >> n;
  
  vector<int> p(n), q(n);
  rep(i, n) cin >> p[i];
  rep(i, n) cin >> q[i];
  
  vector<int> o(n);
  rep(i, n) o[i] = i+1;
  
  bool flga, flgb;
  int cnt=0;
  int a, b;
  do
  {
    flga = flgb = true;
    rep(i, n){
      if (p[i]!=o[i]) flga=false;
      if (q[i]!=o[i]) flgb=false;
    }
    
    if (flga) a = cnt;
    if (flgb) b = cnt;
    
    cnt++;
  } while (next_permutation(o.begin(), o.end()));
  
  cout << abs(a-b) << endl;
  return 0;
}


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

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 998244353
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define mii unordered_map<int,int>
#define mll unordered_map<ll,ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi  first

#define se second
#define pb push_back
#define mp make_pair
#define pp pop_back
#define vii vector<int>
#define vll vector<ll>
#define vpp vector<pii>
#define all(c) c.begin(),c.end()
#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}

int main(){
	boost;
	// #ifndef ONLINE_JUDGE
	// 	freopen("D:/Disk D/Work/c++ workspace/input.txt","r",stdin);
	// 	freopen("D:/Disk D/Work/c++ workspace/output.txt","w",stdout);
	// #endif
	int n;
	cin>>n;
	int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    sort(arr,arr+n);

    ll sum = 0;
    for(int i =0;i<n;i++){
        sum = sum + arr[i];
    }
    sum = sum/n;
    sum = sum + 1;
    ll ans = 0,ans2 = 0;
    for(int i =0;i<n;i++){
        ans = ans + power(sum - arr[i],2);
        ans2 = ans2 + power(sum - 1 - arr[i],2);
    }

    cout<<min(ans,ans2);
	return 0;
}


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

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


using namespace std;

int dp[105][10010];
int main()
{
	int N,W;
	cin>>N>>W;
  
	int v[N+100];
	int w[N+100];
 
	REP(i,N){
		cin>>v[i+1]>>w[i+1];
	}
 
	REP(i,N+1){
		dp[0][i]=0;
	}
	
	for(int i=1;i<N+1;++i){
		
		REP(j,W+1){
			
			if(j<w[i]){
				dp[i][j]=dp[i-1][j];
			}
			else{
				dp[i][j]=max({dp[i-1][j-w[i]]+v[i],dp[i-1][j]});
			}
		}
	}
	
	cout<<dp[N][W]<<endl;
	
	
}


Measured memory_bytes: 7036
#include <stdio.h>

int main(void) {
    int n;
    int p[200000];
    int i;
    int ans = 0;
    int min;

    scanf("%d", &n);

    scanf("%d", &p[0]);
    min = p[i];
    ans++;

    for(i = 1; i < n; i++) {
        scanf("%d", &p[i]);

        if( min > p[i] ) {
            min = p[i];
            ans++;
            continue;
        }
    }

    printf("%d", ans);

    return 0;
}

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

int main()
{
    int x[5];
    rep(i, 5) cin >> x[i];

    rep(i,5)
    {
        if(x[i]!=i+1)
            cout << i + 1 << endl;
    }
}

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

int main()
{
    int n, d;
    cin >> n >> d;
    vector<vector<int>> x(n, vector<int>(d));
    rep(i, n) rep(j, d) cin >> x[i][j];
    int ans = 0;
    rep(i, n - 1)
    {
        for (int j = i + 1; j < n; j++)
        {
            int norm = 0;
            for (int k = 0; k < d; k++)
            {
                int dif = abs(x[i][k] - x[j][k]);
                norm += dif * dif;
            }
            double check = sqrt(norm);
            if (check == (int)check)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << '\n'

typedef int64_t Int;
const double pi = M_PI;

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int s[m];
    char c[m];
    for (int i = 0; i < m; i++) {
        cin >> s[i] >> c[i];
    }

    int ans = INT32_MAX;

    for (int i = (int)pow(10, n - 1); i < (int)pow(10, n); i++) {
        bool ok = true;
        string ss = to_string(i);
        for (int k = 0; k < m; k++) {
            if (ss[s[k] - 1] != c[k]) {
                ok = false;
            }
        }

        if (ok) {
            ans = i;
            break;
        }
    }

    if (m == 0 && n == 1 || n == 1 && m == 1 && s[0] == 1 && c[0] == '0')
        ans = 0;

    if (ans == INT32_MAX) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}


Measured memory_bytes: 256
/*
ID: alec3
LANG: C++14
PROG:
*/

#include <bits/stdc++.h>

#define check(x) cout<<(#x)<<": "<<x<<" ";
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ss second
#define ff first
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ld long double
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = a; i < b; i++)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

int pct(int x) { return __builtin_popcount(x); }
bool absComp (int i, int j) { return (abs(i) < abs(j)); }


int main()
{
    io;
    int n;
    cin >>n;
    string s = to_string(n);
    char digit = s[s.size() -1];

    if (digit == '2' || digit == '4' || digit == '5' || digit == '7' || digit == '9')
        cout << "hon" << endl;
    else if (digit == '3')
        cout << "bon" << endl;
    else
        cout << "pon" << endl;


    return 0;
}


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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N;
  cin>>N;
  ll dig;
  ll flag=0;

  dig=(N/10)%10;
  if(dig!=(N/100)%10) flag--;
  FOR(i,0,4){
    if(N%10==dig)flag++;
    N/=10;
  }
  if(flag>=3)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

const int N = 3e5 + 7;
const int MOD = 998244353;
int fact[N], inv[N];

ll bpow(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = 1LL * res * a % MOD;
		a = 1LL * a * a % MOD;
		b >>= 1;
	}
	return res;
}

ll c(ll a, ll b)
{
	return 1LL * fact[a] * inv[b] % MOD * inv[a - b] % MOD;
}

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

	fact[0] = 1;
	for (int i=1; i<N; i++)
		fact[i] = 1LL * fact[i-1] * i % MOD;
	inv[N-1] = bpow(fact[N-1], MOD - 2);
	for (int i=N-1; i>0; i--)
		inv[i-1] = 1LL * inv[i] * i % MOD;
	ll n, A, B, K;
	cin >> n >> A >> B >> K;
	ll res = 0;
	for (int i=0; i<=n; i++)
	{
		ll sum = A * i;
		ll need = K - sum;
		if (need < 0 || need % B != 0 || need / B > n)
			continue;
		ll cnt = need / B;
		res = (res + 1LL * c(n, i) * c(n, cnt) % MOD) % MOD;
	}
	cout << res << "\n";

	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> P;


int main(){
	int n; cin >> n;
	while (n--) {
		string a, b; cin >> a >> b;
		reverse(all(a));
		reverse(all(b));
		if (a.size() < b.size() ) swap(a, b);
		int u = 0;
		string s;
		rep(i, b.size()) {
			int d = a[i] - '0' + b[i] - '0' + u;
			u = d / 10;
			s += d % 10 + '0';
		}
		REP(i, b.size(), a.size() - 1) {
			int d = a[i] - '0' + u;
			u = d / 10;
			s += d % 10 + '0';
		}
		if(u) s += '1';
		reverse(all(s));
		if(s.size() > 80) cout << "overflow" << endl;
		else cout << s << endl;
		
	}
	return 0;
}

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

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

  int a, b;
  for (a = 0;; ++a)
    for (b = -a; b < a; ++b)
      if (pow(a, 5) - pow(b, 5) == x)
        goto fin;

fin:
  cout << a << " " << b << endl;
}


Measured memory_bytes: 4076
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r,s;};
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX],H[MAX];

void print(int u){
 int i, c,child=0;
 if(T[u].l!=NIL)child++;
 if(T[u].r!=NIL)child++;

 printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", u, T[u].p, T[u].s, child,D[u],H[u]);

 if(T[u].p==NIL) printf("root");
 else if(T[u].l==NIL&&T[u].r==NIL) printf("leaf");
 else printf("internal node");

 printf("\n");

}

void calcDepth(int u, int p){
 D[u] = p;
 if(T[u].l!=NIL) calcDepth(T[u].l,p+1);
 if(T[u].r!=NIL) calcDepth(T[u].r,p+1);
}

int calcHeight(int u){
    if(u==NIL)return -1;
    int left=calcHeight(T[u].l);
    int right=calcHeight(T[u].r);
    if(left>right)return H[u]=left+1;
    else return H[u]=right+1;
}

void Postorder(int n){
    if(n==NIL)return;

    Postorder(T[n].l);
    Postorder(T[n].r);
    cout<<" "<<n;

}
void Inorder(int n){
    if(n==NIL)return;

    Inorder(T[n].l);
    cout<<" "<<n;
    Inorder(T[n].r);
}
void Preorder(int n){
    if(n==NIL)return;
    cout<<" "<<n;
    Preorder(T[n].l);
    Preorder(T[n].r);
}

int main(){
 int i, left,right;
 int n;
 int id;
 int root = NIL;
 scanf("%d", &n);
 for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r =T[i].s= NIL;

 for(i=0; i<n; i++){
   scanf("%d %d %d", &id, &left,&right);
    if(left!=NIL){
        T[left].p = id;
        T[left].s=right;
        }
    if(right!=NIL){
        T[right].p = id;
        T[right].s=left;
        }
    T[id].l = left;
    T[id].r = right;

 }

 //根を求める (find the root)
 for(i=0; i<n; i++){
   if(T[i].p == -1) root = i;
 }

//  //それぞれのノードの深さを求める (find depth of each node)
//  calcDepth(root, 0);
//  calcHeight(root);


 //出力 (output)
 cout<<"Preorder"<<endl;
 Preorder(root);
 cout<<endl<<"Inorder"<<endl;
 Inorder(root);
 cout<<endl<<"Postorder"<<endl;
 Postorder(root);
 cout<<endl;
 return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <cstring>

using namespace std;

#define ll long long
#define pb push_back
#define st first
#define N 200005
#define nd second
#define INF (ll)1e18+7
#define ii pair<int,int>
#define fr freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
ll dp[1005][5000];
ll n,m;
ll ar[N];
ll ma[N];
ll f(ll cur,ll mask){
	ll &ret=dp[cur][mask];
	if(ret!=-1){
		return ret;
	}
	if(cur==m+1){
		if(mask==(1<<n)-1){
			return 0;
		}
		return INF;
	}
	ret=INF;
	ret=min(ret,f(cur+1,mask));
	ret=min(ret,ar[cur]+f(cur+1,mask|ma[cur]));
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//fr
	cin>>n>>m;
	memset(dp,-1,sizeof(dp));
	for(int i=1,k;i<=m;i++){
		cin>>ar[i]>>k;
		ll mask=0;
		for(int j=0;j<k;j++){
			int a;
			cin>>a;
			a--;
			mask=mask|(1<<a);
		}
		ma[i]=mask;
	}
	ll ans=f(1,0);
	if(ans>=(INF/2))cout<<-1;
	else cout<<ans;
}


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

int main()
{
    int a,b;
    cin>>a>>b;
    
    if(a<b){
        cout<<"a < b"<<endl;
    }
     else if(a>b){
        cout<<"a > b"<<endl;
        }
     else{
        cout<<"a == b"<<endl;
        }
            return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int n;
int a[300000];

class UnionFind {
public:
	vector<int>par, sz;
public:
	UnionFind() {}
	UnionFind(int n) {
		par = sz = vector<int>(n);
		for (int i = 0; i < n; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		par[x]=y;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return sz[find(x)];
	}
};
bool C(int t){
	unordered_map<int,int>mp,id,id_rev;
	set<int>se;
	UnionFind uf(n*3);
	int cnt=0;
	for(int i=1;i<n;i++){
		if(a[i]>a[i-1])continue;
		if(!id.count(a[i])){
			id[a[i]]=cnt++;
			id_rev[id[a[i]]]=a[i];
		}
		int d=id_rev[uf.find(id[a[i]])];
		if(d==0||++mp[d]>t)return false;
		if(mp[d]==t){
			if(!id.count(d-1)){
				id[d-1]=cnt++;
				id_rev[id[d-1]]=d-1;
			}
			uf.unite(id[d],id[d-1]);
		}
		se.insert(d);
		auto it=se.lower_bound(d+1);
		while(it!=se.end()){
			mp[*it]=0;
			uf.par[id[*it]]=id[*it];
			it=se.erase(it);
		}
	}
	return true;
}
int main(){
	scanf("%d",&n);
	bool flag=false;
	rep(i,n){
		scanf("%d",&a[i]);
		if(i&&a[i-1]>=a[i])flag=true;
	}
	if(!flag){
		puts("1");return 0;
	}
	int ok=n*2,ng=0;
	while(ok-ng>1){
		int t=(ok+ng)/2;
		if(C(t))ok=t;
		else ng=t;
	}
	cout<<ok+1<<endl;
}


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


int main(){
  stack<int> S1;
  stack<pair<int,int>> S2;
  char ch;
  int sum = 0;

  for(int i = 0;cin >> ch;++i){
    if(ch == '\\') S1.push(i);
    else if(ch == '/' && S1.size() > 0){
      int j = S1.top(); S1.pop();
      sum += i - j;
      int a = i - j;
      while(S2.size() > 0 && S2.top().first > j){
        a += S2.top().second; S2.pop();
      }
      S2.push(make_pair(j,a));
    }
  }
  vector<int> ans;
  while(S2.size() > 0){ ans.push_back(S2.top().second); S2.pop();}
  reverse(ans.begin(),ans.end());
  cout << sum << endl;
  cout << ans.size();
  for(int i = 0;i < ans.size(); ++i){
    cout << " ";
    cout << ans.at(i);
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3168
"use strict";
main(require("fs").readFileSync("/dev/stdin", "UTF-8"));

function main(input) {
  input = input
    .split("\n")
    .shift()
    .split("");
  let isEasy = true;
  for (let i = 0; i < input.length; i++) {
    if (i % 2 === 0 && input[i] === "L") {
      isEasy = false;
      break;
    } else if (i % 2 === 1 && input[i] === "R") {
      isEasy = false;
      break;
    }
  }
  console.log(isEasy ? "Yes" : "No");
}


Measured memory_bytes: 11468
import numpy as np
from functools import reduce
from operator import add,sub,mul,truediv
from fractions import gcd
import itertools 

n,k = map(int,input().split())


num = [0]*k

for i in range(1,n+1):
    num[i%k] = num[i%k]+1

ans = 0

for a in range(k):
    b = (k-a)%k
    c = (k-a)%k
    if (b+c)%k != 0:
        continue
    ans = ans + num[a]*num[b]*num[c]


print(ans)

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();

            var total = 0;

            for (var i = 0; i < 2; i++)
            {
                if (line[0] > line[1])
                {
                    total += line[0];
                    line[0] -= 1;
                } else
                {
                    total += line[1];
                    line[1] -= 1;
                }
            }

            Console.WriteLine(total);
        }

    }
}


Measured memory_bytes: 13268
n, c = map(int, input().split())
clock = []
counter_clock = []
for i in range(n):
    x, v = map(int, input().split())
    clock.append([x, v])
    counter_clock.append([c - x, v])
clock.sort()
counter_clock.sort()
clock_ac = [0]
counter_clock_ac = [0]
for i in range(n):
    v = clock[i][1]
    clock_ac.append(clock_ac[-1] + v)
    v2 = counter_clock[i][1]
    counter_clock_ac.append(counter_clock_ac[-1] + v2)
for i in range(n):
    x = clock[i][0]
    clock_ac[i + 1] -= x
    x2 = counter_clock[i][0]
    counter_clock_ac[i + 1] -= x2
max_clock_ac = [0]
max_counter_clock_ac = [0]
for i in range(n):
    max_clock_ac.append(max(max_clock_ac[-1], clock_ac[i + 1]))
    max_counter_clock_ac.append(max(max_counter_clock_ac[-1], counter_clock_ac[i + 1]))
ans = max(max_clock_ac[n], max_counter_clock_ac[n])
for i in range(n):
    ans = max(ans, clock_ac[i + 1] - clock[i][0] + max_counter_clock_ac[n - i - 1])
    ans = max(ans, counter_clock_ac[i + 1] - counter_clock[i][0] + max_clock_ac[n - i - 1])
print(ans)

Measured memory_bytes: 48784
/*
Author: QAQAutomaton
Lang: C++
Code: D.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef complex<double> cp;
typedef pair<int,int> pii;
int inf;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T,class T2>int chkmin(T &a,T2 b){return a>b?a=b,1:0;}
template<class T,class T2>int chkmax(T &a,T2 b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T,class T2>T mmin(T a,T2 b){return a<b?a:b;}
template<class T,class T2>T mmax(T a,T2 b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
struct __INIT__{
	__INIT__(){
		memset(&inf,0x3f,sizeof(inf));
	}
}__INIT___;
char alpha[]="qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890";
int w[62];
char s[205];
int query(char *s){
	printf("? %s\n",s);
	fflush(stdout);
	int ans;
	scanf("%d",&ans);
	return ans;
}
char cur[199][205];
int t=0;
int l;
void merge(int x,int y){
	char *sol=cur[++t];
	int i=0,j=0;
	int m=0;
	int l1=strlen(cur[x]),l2=strlen(cur[y]);
	for(;i<l1;++i){
		while(j<l2){
			for(int k=0;k<m;++k)s[k]=sol[k];
			s[m]=cur[y][j];
			int n=m;
			for(int k=i;k<l1;++k)s[++n]=cur[x][k];
			s[++n]=0;
			if(query(s)==l-n){
				sol[m]=cur[y][j];
				++j;
				++m;
			}
			else break;
		}
		sol[m]=cur[x][i];
		++m;
		sol[m]=0;
	}
	while(j<l2){sol[m]=cur[y][j];++m;++j;}
	sol[m]=0;
}
priority_queue<pii,vector<pii>,greater<pii> >pq;
signed main(){
	int sum=0;
	for(int i=0;i<62;++i){
		for(int j=0;j<128;++j)s[j]=alpha[i];	
		s[128]=0;
		w[i]=128-query(s);
		l+=w[i];
		sum+=w[i];
	}
	for(int i=0;i<62;++i)if(w[i]){
		++t;
		for(int j=0;j<w[i];++j)cur[t][j]=alpha[i];
		cur[t][w[i]]=0;
		pq.push(make_pair(w[i],t));
	}
	while(pq.size()>1){
		int x=pq.top().y;
		pq.pop();
		int y=pq.top().y;
		pq.pop();
		merge(x,y);
		pq.push(make_pair(strlen(cur[t]),t));
	}
	printf("! %s\n",cur[pq.top().y]);
	fflush(stdout);
	return 0;
}



Measured memory_bytes: 3872
sum = gets.split(' ').map(&:to_i)
a = sum[0]
b = sum[1]
c = sum[2]
if a >= b && a >= c then
	puts (b + c)
elsif b >= c && b >= a then
	puts (a + c)
elsif c >= b && c >= a then
	puts (a + b)
end

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

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

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

//constexpr ll mod = 998244353;
constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

struct {
    int N;
    vector<long long> dat;

    void init(int n) {
      N = 1;
      while(N < n) N *= 2;
      dat.resize(2*N-1, 0);
    }

    // add [a, b) by x
    void add(int a, int b, long long x) {
      return add(a, b, x, 0, 0, N);
    }
    void add(int a, int b, ll x, int k, int l, int r) {
      if (r <= a || b <= l) return;
      if (a <= l && r <= b) {
        dat[k] += x;
        return;
      }
      int m = (l+r)/2;
      add(a, b, x, k*2+1, l, m);
      add(a, b, x, k*2+2, m, r);
    }

    // return k
    long long query(int k) {
      k += N-1;
      ll ret = dat[k];
      while(k > 0) {
        k = (k-1)/2;
        ret += dat[k];
      }
      return ret;
    }
} S;

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

  int n, m; cin >> n >> m;
  S.init(m+1);
  vector<P> vec;
  rep(i, n) {
    ll l, r; cin >> l >> r;
    vec.emplace_back(r-l, l*mod+r);
  }

  sort(vec.begin(), vec.end());
  int now = 1;
  rep(i, n) {
    //debugln(i);
    P p = vec[i];
    ll l = vec[i].second/mod;
    ll r = vec[i].second%mod;
    ll range = vec[i].first+1;
    while(now <= range && now <= m) {
      //debugln(now);
      ll ans = n-i;
      for(int j=now; j<=m; j+=now) {
        ans += S.query(j);
      }
      cout << ans << '\n';
      now++;
    }
    //debug(l); debugln(r+1);
    S.add(l, r+1, 1);
  }

  while(now <= m) {
    ll ans = 0;
    for(int j=now; j<=m; j+=now) {
      ans += S.query(j);
    }
    cout << ans << '\n';
    now++;
  }

}

Measured memory_bytes: 12652