akhauriyash/Code-Regression huggingface dataset:
#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 PB push_back
#define MP make_pair
#define SZ size()
#define Fr first
#define Sc second
#define si(a) scanf("%d", &a)
#define sl(a) scanf("%I64d", &a)
#define sd(a) scanf("%lf", &a)
#define ss(a) scanf("%s", a)
#define debug(x) cout << #x << ": " << x << endl
#define Fast_IO ios_base::sync_with_stdio(0);cin.tie(0)

typedef long long Long;
typedef pair <int, int> Pii;
///<-------------------------------------------------END OF TEMPLATE-------------------------------------------------->

#define MAX 505
int H, W, h, w, grid[MAX][MAX];

int main() {
   si(H); si(W); si(h); si(w);
   Long sum = 0;
   for(int i = 0; i < H; i++)
      for(int j = 0; j < W; j++) {
         if((i+1) % h == 0 && (j+1) % w == 0) grid[i][j] = -500 * w * h + 499;
         else grid[i][j] = 500;
         sum += grid[i][j];
      }

   if(sum <= 0) {
      puts("No");
   } else {
      puts("Yes");
      for(int i = 0; i < H; i++) {
         for(int j = 0; j < W; j++) {
            if(j) printf(" ");
            printf("%d", grid[i][j]);
         }
         puts("");
      }
   }
}


Measured memory_bytes: 2304
#include<iostream>
using namespace std;
int main() {
    int a, b, c, d;
    cin >> a >> b;
    d = a * b;
    if (b > 0) {
        c = a + b;
    } else {
        c = a - b;
    }
    cout << (c >= d ? c : d) << endl;
    return 0;
}


Measured memory_bytes: 256
dic = {}
max = 0
maxword = 0
word = input().strip().split(" ")
i = 1
while i <= len(word):
    if word[i-1] in dic:
        dic[word[i-1]] += 1
    else:
        dic[word[i-1]] = 1
    i += 1
for k,v in sorted(dic.items()):
    if v > max:
        max = v
        words = k
for k in dic:
    if len(k) > maxword:
        maxword = len(k)
        maxwords = k
print(words + " " + maxwords)

Measured memory_bytes: 7384
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R, K,X;
ll A;
ll B;
ll ans;
string S;
ll searchflg[100001];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
list<pair<ll,ll> > l[100001];
bool func(ll nowpos,ll nownum) {
	if (searchflg[nowpos] == nownum) {
		return true;
	}
	else if (searchflg[nowpos] != 10000000000) {
		return false;
	}
	else{
		searchflg[nowpos] = nownum;
		for(auto itr =l[nowpos].begin();itr!=l[nowpos].end();itr++) {
			if (!func(itr->first, itr->second + nownum)) {
				return false;
			}
		}
	}
	return true;
}
int main() {
	cin >> N >> M;
	rep(i, 0, M) {
		cin >> L >> R >> D;
		l[L].push_back(make_pair(R, D));
		l[R].push_back(make_pair(L, -1*D));
	}
	rep(i, 1, N + 1) {
		searchflg[i] = 10000000000;
	}
	rep(i, 1, N+1) {
		if (searchflg[i]== 10000000000) {
			if (!func(i,0)) {
				cout << "No" << endl;
				cin >> ans;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	cin >> ans;
	return 0;
}

Measured memory_bytes: 23168
#include<bits/stdc++.h>
#include<vector>
#include<cstring>
#include<iostream>
#include<cstdio>
#define ull unsigned long long
#define ll long long
const ll mod=998244353;
using namespace std;
//priority_queue
inline ll in()
{
    ll res=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-48,c=getchar();
    return res;
}
 ll gcd(ll a,ll b)
 {
     return b==0?a:gcd(b,a%b);
 }
 ll kk(ll a,ll b)
{
    ll c=0;
    while(b)
    {
        if(b&1)c=(c+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return c;
}
 ll kc(ll a,ll b)
 {
     ll c=1;
     while(b)
     {
         if(b&1)c=c*a%mod;
         a=a*a%mod;
         b>>=1;
     }
     return c;
 }
 char s[200006];
int main()
{  //ios::sync_with_stdio(false);
  int n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;
   scanf("%s",s+1);
  if(c==d)cout<<"No\n";
  else if(c<d)
  {
       int i=b;
       int q=0;
       while(i<=n&&i!=d)
       {
           if(i+1<=n&&s[i+1]=='.')i++;
           else if(i+2<=n&&s[i+2]=='.')i+=2;
           else {q=1;break;}
       }
       int qq=0;i=a;
       while(i<=n&&i!=c)
       {
           if(i+1<=n&&s[i+1]=='.')i++;
           else if(i+2<=n&&s[i+2]=='.')i+=2;
           else {qq=1;break;}
       }
       if(!q&&!qq)cout<<"Yes\n";
       else cout<<"No\n";
  }
  else {
     int q=0;
      while(b<=n&&b!=d)
      {   if(b-1>0&&b+1<=n&&s[b-1]=='.'&&s[b+1]=='.'){s[b]=='#';break;}
          if(b+1<=n&&s[b+1]=='.')b++;
           else if(b+2<=n&&s[b+2]=='.')b+=2;
           else {q=1;break;}
      }
      if(b==d)s[b]='#';
      int qq=0,i=a;
        while(i<=n&&i!=c)
       {
           if(i+1<=n&&s[i+1]=='.')i++;
           else if(i+2<=n&&s[i+2]=='.')i+=2;
           else {qq=1;break;}
       }
      if(i==c)s[c]='#';
       while(b<=n&&b!=d)
      {  // if(i-1>=0&&i+1<n&&s[i-1]=='.'&&s[i+1]=='.')break;
          if(b+1<=n&&s[b+1]=='.')b++;
           else if(b+2<=n&&s[b+2]=='.')b+=2;
           else {q=1;break;}
      }
      if(!q&&!qq)cout<<"Yes\n";
      else cout<<"No\n";
  }
}


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

int main(){
int n,  k;
cin >> n >> k;
vector<ll> a(n);
for(int i = 0; i < n ; i++)cin >> a[i];

int cnt = 0;
for(int i = 1; i<= n-k; i++){
  if(a[k+i-1] > a[i-1])cout << "Yes" << endl;
  else cout << "No" << endl;
} 
return 0;
}

Measured memory_bytes: 4836
import java.util.Scanner;

public class Main {
	
	static  Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		
		int a, b;
        a = in.nextInt();
        b = in.nextInt();
        int ans = 0;
        ans = a - b * 2;
        if(ans < 0) ans = 0;
        System.out.println(ans);
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define mod 1000000007
#define int long long

int path(int src, vector<int> &dp, vector<vector<int>> &a) {
	if (dp[src] != -1)return dp[src];
	int ans = 0;
	for (auto x : a[src]) {
		ans = max(ans, path(x, dp, a));
	}

	return dp[src] = 1 + ans;
}

void solve() {
	int n, m;
	cin >> n >> m;
	int i;
	vector<vector<int>> a(n);
	for (i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		a[u].push_back(v);
	}

	vector<int> dp(n);
	fill(dp.begin(), dp.end(), -1);

	int ans = 0;

	for (i = 0; i < n; i++) {
		ans = max(ans, path(i, dp, a));
	}

	cout << ans - 1 << endl;

	return;
}

int32_t main() {

	std::ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	while (t--)solve();
	return 0;
}

Measured memory_bytes: 12168
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (auto &e: h) cin >> e;

    int ans = 1;
    int m = h[0];
    for (int i = 1; i < n; ++i) {
        if (m <= h[i]) {
            ++ans;
            m = h[i];
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define MAX 200010

using namespace std;

int n,a,ms,msmax;
int p[MAX];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a,p[a]=i;
    ms=1;
    for(int i=2;i<=n;i++)
      if(p[i]>p[i-1])ms++;
      else msmax=max(msmax,ms),ms=1;
    msmax=max(msmax,ms);
    cout<<n-msmax;
    return 0;
}


Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
def main():
    D = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(D):
        si = list(map(int, input().split()))
        s.append(si)
    for i in range(D):
        best_idx = -1
        best_val = 0
        for j in range(26):
            val = s[i][j] + (20000 - c[j] * 200)
            if val > best_val:
                best_idx = j
                best_val = val
        print(best_idx+1)
if __name__ == "__main__":
    main()

Measured memory_bytes: 68784
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define call(var) cout<<#var<<"="<<var<<endl;
#define dup(x,y) (((x)+(y)-1)/(y))
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
const int INTMAX = 2147483647;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
    int n;cin >> n;
    vi p(n);
    rep(i,n) cin >> p[i];

    int ans = 0;
    rep(i,n-3+1){
        if(p[i]<p[i+1] && p[i+1]<p[i+2]) ++ans;
        else if(p[i]>p[i+1] && p[i+1]>p[i+2]) ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;

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

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

ll INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    ll ans = 0;
    if(a<b && n>1){
        ans = (n-1)*b + a - b - (n-1)*a + 1;
    }
    else if(a==b){
        ans = 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 764
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    int z = sc.nextInt();
    int k = sc.nextInt();
    long[] a = new long[x];
    long[] b = new long[y];
    long[] c = new long[z];
    long[] ab = new long[x * y];
    for(int i = 0; i < x; i++){
      a[i] = sc.nextLong();
    }
    for(int i = 0; i < y; i++){
      b[i] = sc.nextLong();
    }
    for(int i = 0; i < z; i++){
      c[i] = sc.nextLong();
    }
    Arrays.sort(a);
    Arrays.sort(b);
    Arrays.sort(c);
    int index = 0;
    for(int i = 0; i < x; i++){
      for(int j = 0; j < y; j++){
        ab[index] = a[i] + b[j];
        index++;
      }
    }
    Arrays.sort(ab);
    long[] abc = new long[Math.min(x*y, 3000) * z];
    index = 0;
    for(int i = 0; i < Math.min(x*y, 3000); i++){
      for(int j = 0; j < z; j++){
        abc[index] = ab[x*y-1-i] + c[z-1-j];
        index++;
      }
    }
    Arrays.sort(abc);
    for(int i = 0; i < k; i++){
      System.out.println(abc[abc.length-1-i]);
    }
  }
}

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

int main() {
    int n, k; cin >> n >> k;
    vector<int> v(n, 0);

    for(int i = 0; i < n; i += 1) {
        cin >> v[i];
    }
    
    vector<int64_t> sums;

    for(int i = 0; i < n; i += 1) {
        int64_t sum = 0;
        for(int j = i; j < n; j += 1) {
            sum += v[j];
            sums.push_back(sum);
        }
    }
    
    int64_t ans = 0;

    for(int bit = 40; bit >= 0; bit -= 1) {
        vector<int64_t> new_sums;
        for(auto val : sums) {
            if(val & (1LL << bit)) {
                new_sums.push_back(val);
            }
        }

        if(int(new_sums.size()) >= k) {
            ans += (1LL << bit);
            sums = new_sums;
        }
    }

    cout << ans << "\n";
}

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

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

    if (n == 100000) {
        cout << 9 + (999 - 99) + (99999 - 9999) << endl;
    } else if (n >= 10000) {
        cout << 9 + (999 - 99) + (n - 9999) << endl;
    } else if (n >= 1000) {
        cout << 9 + (999 - 99) << endl;
    } else if (n >= 100) {
        cout << 9 + (n - 99) << endl;
    } else if (n >= 10) {
        cout << 9 << endl;
    } else {
        cout << n << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#import numpy as np
N = int(input())
#a = np.array(list(map(int,input().split()))).astype(np.int64)
a = list(map(int,input().split()))
a.sort(reverse=True)

ans = 0

while True:
    f = True
    for i in range(N):
        if a[i] >= N:
            f = False
    if f:
        break
    for i in range(N):
        if a[i] >= N:
            t = a[i]//N
            ans += t
            a[i] -= t*(N+1)
            for j in range(N):
                a[j] += t
print(ans)



Measured memory_bytes: 42076
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
map<int,int>vis;
void dfs(int s)
{
vis[s]=1;
for(auto i:adj[s])
{
if(!vis[i])
dfs(i);
}
}
int main()
{
int n,m;
cin>>n>>m;
adj.assign(n+1,vector<int>());
for(int i=0; i<m; ++i)
{
int a,b;
cin>>a>>b;
--a;
--b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int cm(0);
for(int i=0; i<n; ++i)
{
if(!vis[i])
{
dfs(i);
++cm;
}
}
cout<<cm-1;
}


Measured memory_bytes: 15672
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    long long x, k, d, quot, k_temp;
    cin >> x >> k >> d;
    x = abs(x);
  
    if (k > 3){
        quot = x / d;
        if (k > quot){
            k = (k - quot) & 1?3:2;
            x = x % d;
        } else {
            k_temp = k;
            k = (quot - k) & 1?3:2;
            x = x - d * (k_temp - k);
        }
    }
    

    while(k > 0){
        if(d > x)
            x = abs(x - d);
        else{
            if (k > 1 && x < abs(x - 2 *d))
                x = x + d;
            else
                x = abs(x - d);
        }
        k--;
    }

    cout << x << endl;
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,Q;
int state[100];

signed main(){
    while(cin>>N>>Q,N||Q){
        memset(state,-1,sizeof(state));
        rep(i,Q){
            char c;
            int a,b;
            cin>>c>>a;
            if(c=='s'){
                cin>>b;
                int pos=-1;
                rep(j,N-b+1){
                    bool f=true;
                    rep(k,b)if(state[j+k]!=-1)f=false;
                    if(f){
                        pos=j;
                        rep(k,b)state[j+k]=a;
                        break;
                    }
                }
                if(pos>=0)cout<<pos<<endl;
                else cout<<"impossible"<<endl;
            }
            else{
                rep(j,N)if(state[j]==a)state[j]=-1;
            }
        }
        cout<<"END"<<endl;
    }
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    int a[n];
    int tmp;
    rep(i, n){
        cin >> a[i];
        if(i==0){
            tmp = a[0];
        }

        tmp = __gcd(tmp, a[i]);

    }
    cout << tmp << endl;
    return 0;
}

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

void dfs(int n, string s, char c) {
  if (n == 0) {
    cout << s << "\n";
  } else {
    for (char next = 'a'; next <= c; next++) {
      dfs(n - 1, s + next, max(c, (char) (next + 1)));
    }
  }
}

int main() {
  int n;
  cin >> n;
  dfs(n, "", 'a');
}


Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second


signed main(){
	ll a[4] = {1,4,7,9};
	ll b[4];
	
	rep(i,0,4) cin >> b[i];
	
	sort(b,b+4);
	
	rep(i,0,4){
		if(a[i] != b[i]){
			cout << "NO" << endl;
			break;
		}
		else if(i == 3){
			cout << "YES" << endl;
		}
	}
	return 0;

}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

std::string S;

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

    for(int i=0;i<3;++i){
        std::cin >> S;

        for(int j=0;j<3;++j){
            if(j == i){
                std::cout << S[j];
            }
        }
    }

    std::cout << std::endl;
}


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

int main()
{
	int a,b;
	char op;
	while(1){
	    cin >> a >> op >> b;
		if(op == '+') cout << a + b << endl;
		if(op == '-') cout << a - b << endl;
		if(op == '*')	cout << a * b << endl;
		if(op == '/') cout << a / b << endl;
		if(op == '?') break;
	}
	return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstdio>
#include <cmath>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
	int N,total=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		total += y - x + 1;
	}
	cout << total << endl;
	return 0;
}


Measured memory_bytes: 256
#c+c->S
#Scc

A=gets.chomp
N=A.split(" ")[0].to_i
M=A.split(" ")[1].to_i

if N>M/2 then #too many S's
	print M/2.floor
else 
	a=N
	M-=N*2 #make Scc with original S's
	b=M/4.floor #make Scc all from c's
	print a+b
end

Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {
	private static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		long ret = 1;
		for (int i = 1;i <= n;i++) {
			ret = (ret*i)%1000000007;
		}
		System.out.println(ret);
	}
}


Measured memory_bytes: 21844
#[allow(unused_imports)]
use {
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::ops::*,
};

#[allow(unused_macros)]
macro_rules !max {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::max ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *) =>{{std ::cmp ::max ($a ,max !($($rest ) ,+) ) } } ;}
#[allow(unused_macros)]
macro_rules !chmax {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_max =max !($($cmps ) ,+) ;if $base <cmp_max {$base =cmp_max ;true } else {false } } } ;}

#[fastout]
fn main() {
    input! {
        h: usize,
        w: usize,
        ab: [(Usize1, usize); h]
    }

    let mut s = (0..w).map(|i| (i, i)).collect::<BTreeSet<(usize, usize)>>();
    let mut v = (0..w).map(|i| (0, i)).collect::<BTreeSet<(usize, usize)>>();

    for (i, &(a, b)) in ab.iter().enumerate() {
        let update = s
            .range((a, 0)..(b, w))
            .map(|&(i, j)| (i, j))
            .collect::<Vec<(usize, usize)>>(); // total: O(w)log w
        if !update.is_empty() {
            let mut x = 0;
            for (end, start) in update {
                chmax!(x, start);
                s.remove(&(end, start));
                v.remove(&(end - start, start));
            }
            if b != w {
                s.insert((b, x));
                v.insert((b - x, x));
            }
        }
        if let Some((m, _)) = v.iter().next() {
            println!("{}", m + i + 1);
        } else {
            println!("-1");
        }
    }
}


Measured memory_bytes: 22192
#include <iostream>

int main(void){
    int N;
    std::cin >> N;
    int min = 0;
    std::cin >> min;
    int count = 1;
    int temp;
    for(int i = 1; i < N; ++i){
        std::cin >> temp;
        if(temp <= min){
            min = temp;
            ++count;
        }
    }

    std::cout << count << "\n";

    return 0;
}

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

#define pb push_back
#define mp make_pair
#define ft first
#define sd second
#define snd sd.ft
#define td sd.sd
#define debug(x) cout<<"### x is: "<<x<<"###"<<endl
#define all(a) a.begin(),a.end()

#define ninf -1000000000
#define pinf 1000000000

typedef long long int ll;
const ll MOD= 1e9+7;
typedef vector<pair<ll,ll> > vecpair;
typedef vector<pair<ll, pair<ll,ll> > > vecpair3;
typedef pair<ll, ll> pi;

//double mei ye line cout << fixed << setprecision(10); kam mei le

ll power(ll a, ll b) {ll ret=1;while(b) {if(b&1) ret*=a;a*=a;if(ret>=MOD) ret%=MOD;if(a>=MOD) a%=MOD;b>>=1;}return ret;}

struct subset // disjoint set use subsets.claer and subsets.resize............
{
	int parent,sz;
};
vector< subset> subsets;
int find( int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets[i].parent);

    return subsets[i].parent;
}
void uniona(int x, int y){
	if( x == y)
	return ;
    int xroot = find( x);
    int yroot = find( y);
    if (subsets[xroot].sz < subsets[yroot].sz){
        subsets[xroot].parent = yroot;
        subsets[yroot].sz += subsets[xroot].sz;
    }
    else{
        subsets[yroot].parent = xroot;
        subsets[xroot].sz += subsets[yroot].sz;
    }
}
//........................................................

int n;
double p[3000],dp[3000][3000];

double solve(int i,int k)
{
	if(i==n+1)
	{
		if(k>n/2)
			return 1;
		else
			return 0;
	}
	if(dp[i][k]!=-1)
	return dp[i][k];
	dp[i][k]=1;
	dp[i][k]=p[i]*solve(i+1,k+1)+(1-p[i])*solve(i+1,k);
	return dp[i][k];
}

int main()
{
	std:ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> p[i];
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
			dp[i][j]=-1;
	}
	cout << fixed << setprecision(10);
	cout << solve(1,0);

	return 0;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    int k;
    cin >> k;
    //kが7より小さい時のために7%kにする
    int x = 7%k;
    set<int> s;
    int i=1; //カウンタ
    while(s.count(x)==0){
        //xが0になったらその時点で終了
        if(x==0){
            cout << i << endl;
            return 0;
        }
        //一回訪れたところはsetに挿入する
        s.insert(x);
        x=(x*10+7)%k;
        ++i;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 50428
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>//////////////////////////////////////////
#define deb(...)/////////////////////////////////////////////////
#define DBP(...)/////////////////////////////////////////////////
#ifdef LOC///////////////////////////////////////////////////////
#include"debuglib.h"/////////////////////////////////////////////
#endif///////////////////////////////////////////////////////////
#define x first//////////////////////////////////////////////////
#define y second/////////////////////////////////////////////////
#define pb push_back/////////////////////////////////////////////
#define sz(x)int((x).size())/////////////////////////////////////
#define each(a,x)for(auto&a:(x))/////////////////////////////////
#define all(x)(x).begin(),(x).end()//////////////////////////////
#define rep(i,b,e)for(int i=(b);i<(e);i++)///////////////////////
using namespace std;using ll=long long;using Pii=pair<int,int>;//
using Vi=vector<int>;void run();int main(){cin.sync_with_stdio///
(0);cin.tie(0);cout<<fixed<<setprecision(18);run();return 0;}////
//-------------------------------------------------------------//

void run() {
	string s; cin >> s;
	int k; cin >> k;

	int naive = min(k, 20);
	string t = s;
	rep(i, 1, naive) t += s;

	ll ans = 0;
	vector<ll> thr = {0};

	rep(i, 1, sz(t)) {
		if (t[i] == t[i-1]) {
			t[i] = '.';
			ans++;
		}
		if (i%sz(s) == 0) thr.pb(ans);
	}

	if (naive < k) {
		int rest = k-naive;
		ans += ll(rest/2) * (thr.back() - thr.rbegin()[2]);
		if (rest%2) ans += thr.rbegin()[1] - thr.rbegin()[2];
	}

	cout << ans << '\n';
}


Measured memory_bytes: 256
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        s: chars,
    }
    let mut s = s;
    let n = s.len();
    let mut ans = vec![0; s.len()];
    for _ in 0..2 {
        { // solve
            let mut cnt = 0;
            for i in 0..n {
                if s[i] == 'R' {cnt+=1}
                else {
                    ans[i] += cnt/2;
                    ans[i-1] += (cnt+1)/2;
                    cnt = 0;
                }
            }
        }
        ans.reverse();
        s.reverse();
        for i in 0..n {
            if s[i] == 'L' {s[i] = 'R'}
            else {s[i] = 'L'}
        }
    }
    for i in 0..n {
        println!("{}", ans[i]);
    }
}

Measured memory_bytes: 4476
#include<iostream>
using namespace std;
string a1,a2;
long long a=0,b=0;
int main(){
	cin>>a1;
	if(a1[0]!='A'){
		cout<<"WA"<<endl;
		return 0;
	}
	for(long long i=2;i<=a1.length()-2;i++){
		if(a1[i]=='C'){
			a++;
		}
	}
	if(a!=1){
		cout<<"WA"<<endl;
		return 0;
	}
	a=0;
	for(long long i=1;i<a1.length();i++){
		if(a1[i]>='A'&&a1[i]<='Z'&&a1[i]!='C'){
			b=1;
		}
		if(a1[i]=='C'){
			a++;
		}		
	}
	if(b==1||a!=1){
		cout<<"WA"<<endl;
		return 0;
	}
	cout<<"AC"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main( void )
{
	int n,x;
	int number;
	
	scanf( "%d", &n );
	
	for( number = 1; number <= n; number++ )
	{
		x = number;
		
		if( x % 3 == 0 )
		{
			printf( " %d", number );
		}else
		{
			while( x != 0 )
			{
				if( x % 10 == 3 )
				{
					printf( " %d", number );
					break;
				}
				x = x / 10;
			}
		}
	}
	
	printf( "\n" );
	
	return 0;
}

Measured memory_bytes: 600
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc074/tasks/arc083_a
# 要復習
A, B, C, D, E, F = read_ints()


# Aを何回を行うか Bを何回行うかは全探索できる #30通り*30通り(たかだか)
satou_candi = set()
for c, d in product(range(3001), repeat=2):
    if c * C + d * D > F:
        continue
    satou_candi.add(c * C + d * D)

water_candi = set()
for a, b in product(range(31), repeat=2):
    if 100 * (A * a + B * b) > F:
        continue
    water_candi.add((A * a + B * b) * 100)

satou_candi = sorted(satou_candi)  # この時点で最大3000通りしか無い
water_candi = sorted(water_candi)
# print(satou_candi)
# print(water_candi)

ans_satou = 0
ans_total = A * 100
for water in water_candi[1:]:
    for satou in satou_candi:
        if satou + water > F:
            continue
        max_satou = E * water // 100  # 100lあたり
        if satou > max_satou:
            continue
        if ans_satou / ans_total < satou / (satou + water):
            ans_satou = satou
            ans_total = water + satou

# for water in water_candi[1:]:
#     max_satou = E * water // 100  # 100lあたり
#     idx = bisect_right(satou_candi, max_satou) - 1  # -1にはならないはず [0]→0なので
#     satou = satou_candi[idx]
#     # print(water, satou, max_satou)
#     if satou + water > F:
#         continue
#     if ans_satou / ans_total < satou / (satou + water):
#         ans_satou = satou
#         ans_total = water + satou

print(ans_total, ans_satou)


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

#define abs (x)(x>0?x:-x)


int main() 
{
	int A, B;

	scanf("%d%d", &A, &B);

	if ((A + B) % 2 == 0)
		printf("%d", (B + A) / 2);
	else
		printf("IMPOSSIBLE\n");

	
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef map<int,int> mint;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int inf=1e9+100;
ll infi =1e18+100;

int N,K;
ll x[60],y[60];

int main() {
	cin>>N>>K;
	Rep(i,N) cin>>x[i]>>y[i];
	ll ans=4*infi;
	Rep(i,N){
		Rep(j,N){
			Rep(k,N){
				Rep(l,N){
					int cnt=0;
					Rep(m,N){
						if(x[m]>=x[i]&&x[m]<=x[j]&&y[m]>=y[k]&&y[m]<=y[l]){
							cnt++;
						}
					}
					if(cnt>=K){
						ll S=(x[i]-x[j])*(y[k]-y[l]);
						if(S<ans) ans=S;
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(void)
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a<b&&b<c)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }


    printf("\n");
    return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define puts(i) cout<<i<<endl
#define pi 3.14159265358979323846264338
#define pb push_back
#define mp make_pair
#define inf 10000
using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;

ll divisor=1000000007;

int main(){
	char s;
	cin>>s;
	
	if(s-'A'>=0&&s-'A'<26){
		puts("A");
	}else{
		puts("a");
	}
}


Measured memory_bytes: 3596
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int N = 0;
int K = 0;
int a = 0;



int main() {
	cin >> N;
	cin >> K;
	for (int i = 0; i < N; i++) {
		int h = 0;
		cin >> h;
		if (h >= K) {
			a++;
		}
	}
	cout << a;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define rep(i, n) for(int i = 0;i < n;i++)
#define reprb(i, n) for(int i = n;i >= 0;i--)
#define reps(i, m, n) for(int i = m;i < n;i++)
#define repsb(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
vector<int> a;

int main(int argc,char * argv[])
{
	int n,in,mi=0;
	while(true)
	{
		cin>>n;

		if(n==0)	break;
		rep(i,n){
			cin>>in;
			a.pb(in);
			mi=max(mi,in);
		}
		rep(i,n){
			rep(j,n){
				if(i!=j)	mi=min(mi,abs(a[i]-a[j]));
			}
		}
		cout<<mi<<endl;
		a.clear();
	}
	return 0;
}


Measured memory_bytes: 3080
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int K,len;
set<string> s;
string S;

int main(){
    cin>>S>>K;
    len=S.length();
    rep(i,S.length()){
        rep(j,K){
            s.insert(S.substr(i,j+1));
        }
    }
    for(auto x : s){
        K--;
        if(!K){
            out(x);
            break;
        }
    }
}


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

int main(){
  int d;
  long long n;
  cin>>d >>n;
  if(n == 100) n++;
  if(d == 0){
    cout<<n<<endl;
  }else if(d == 1){
    cout<<100*n<<endl;
  }else if(d == 2){
    cout<<10000*n<<endl;
  }
}

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

int main(){
    int A, B;
    char S[20];
    cin >> A >> B >> S;
    for(int i = 0; i < A; i++) if(!('0' <= S[i] && S[i] <= '9')){
        cout << "No" << endl;
        return 0;
    }
    if(S[A] != '-'){
        cout << "No" << endl;
        return 0;
    }
    for(int i = A + 1; i < A + B + 1; i++) if(!('0' <= S[i] && S[i] <= '9')){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int A,B;

  cin >> A >> B;

  if(A==1&&B!=1){
    cout << "Alice" << endl;
  }

  else if(A!=1&&B==1){
    cout << "Bob" << endl;
  }

  else if(A==B){
    cout << "Draw" << endl;
  }

  else if(A>B){
    cout << "Alice" << endl;
  }

  else if(A<B){
    cout << "Bob" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>

using namespace std;

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;

constexpr ll MOD = 1000000007;
constexpr ll INF = 1050000000;



/*for文でx,yを上下左右確認するやつだよ。正直使いづらいよ。

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


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}

*/

/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}

*/

/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; ++i) {
	for (int j = 0; j < w; ++j) {

	}
}

*/

struct node {
	int value;
	node* next;
	node(int value, node* next) : value(value), next(next) { }
};

#define index_of(as, x) distance(as.begin(), lower_bound(as.begin(), as.end(), x))

vector<int> lcs_hs(const vector<int>& a, const vector<int>& b) {
	const int n = a.size(), m = b.size();
	map< int, vector<int> > M;
	for (int j = m - 1; j >= 0; --j)
		M[b[j]].push_back(j);
	vector<int> xs(n + 1, INF); xs[0] = -INF;
	vector< node* > link(n + 1);
	for (int i = 0; i < n; ++i) {
		if (M.count(a[i])) {
			vector<int> ys = M[a[i]];
			for (int j = 0; j < ys.size(); ++j) {
				int k = index_of(xs, ys[j]);
				xs[k] = ys[j];
				link[k] = new node(b[ys[j]], link[k - 1]);
			}
		}
	}
	int l = index_of(xs, INF - 1) - 1;
	vector<int> c;
	for (node* p = link[l]; p; p = p->next)
		c.push_back(p->value);
	reverse(c.begin(), c.end());
	return c;
}


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

	for (int i = 0; i < n; i++) {
		vector<int> a, b;
		string s; cin >> s;
		for (int j = 0; j<s.size(); j++) {
			char x = s[j];
			a.push_back((int)x);
		}
		string t; cin >> t;
		for (int j = 0; j<t.size(); j++) {
			char y = t[j];
			b.push_back((int)y);
		}
		vector<int> c = lcs_hs(a, b);
		cout << c.size() << endl;
	}


	return 0;
}


Measured memory_bytes: 51300
#include<iostream>
#include<algorithm>
#include<vector>
#include <map>
#include<queue>
#include<bits/stdc++.h>
#include<climits>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef queue<int> IntQueue;
//typedef std::pair<int, int> pair;

int weight[110];
int value[110];
  
void solve(){
  int N,W;
  cin>>N>>W;
  int weight[N];
  int value[N];
  int dp[N+1][W+1];
  rep(i,N)cin>>value[i]>>weight[i];
  rep(i,W+1)dp[0][i]=0;
  rep(i,N){
    rep(j,W+1){
      if (j>=weight[i]){
        dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j]);
      }else{
        dp[i+1][j]=dp[i][j];
      }
    }
  }
  cout<<dp[N][W]<<endl;
  return;
}

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



Measured memory_bytes: 7060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    ll n,a,b;cin>>n>>a>>b;
    ll v[n+1];rep(i,1,n)cin>>v[i];
    l_l dp[n+1][n+1];
    rep(i,0,n)rep(j,0,n)dp[i][j]=l_l(-1,0);
    dp[0][0]=l_l(0,1);
    rep(i,1,n){
        rep(j,0,n){
            if(j==0){
                dp[i][j]=l_l(0,1);
            }else{
                if(dp[i-1][j].first==-1){
                    if(dp[i-1][j-1].first==-1){
                        dp[i][j]=l_l(-1,0);
                    }else{
                        dp[i][j]=l_l(dp[i-1][j-1].first+v[i],dp[i-1][j-1].second);
                    }
                }else{
                    if(dp[i-1][j-1].first==-1){
                        dp[i][j]=l_l(dp[i-1][j].first,dp[i-1][j].second);
                    }else{
                        if(dp[i-1][j].first==dp[i-1][j-1].first+v[i]){
                            dp[i][j]=l_l(dp[i-1][j].first,dp[i-1][j].second+dp[i-1][j-1].second);
                        }else if(dp[i-1][j].first>dp[i-1][j-1].first+v[i]){
                            dp[i][j]=l_l(dp[i-1][j].first,dp[i-1][j].second);
                        }else{
                            dp[i][j]=l_l(dp[i-1][j-1].first+v[i],dp[i-1][j-1].second);
                        }
                    }
                }
            }
        }
    }
    dd maxi=0;
    vector<ll> flag;
    rep(i,a,b){
        dd hoge=(dd)dp[n][i].first/(dd)i;
        if(fabs(maxi-hoge)<EPS){
            flag.pb(i);
        }else if(maxi<hoge){
            flag.clear();
            flag.pb(i);
            maxi=hoge;
        }
    }
    ll sum=0;
    rep(i,0,flag.size()-1){
        sum+=dp[n][flag[i]].second;
    }
    cout<<setprecision(20)<<maxi<<endl;
    cout<<sum<<endl;
    return 0;
}





Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
string s[8];
int cnt[8][8];

bool in(int y, int x) {
    return y >= 0 && x >= 0 && y < 8 && x < 8;
}

int count(int sy, int sx, char c, char d) {
    int res = 0;
    for (int i = 0; i < 8; ++i) {
        int y = sy + dy[i], x = sx + dx[i], num = 0;
        while (in(y, x) && s[y][x] == d) {
            y += dy[i];
            x += dx[i];
            num++;
        }
        if (!in(y, x) || s[y][x] != c) continue;
        res += num;
    }
    return res;
}

void simu(int sy, int sx, char c, char d) {
    for (int i = 0; i < 8; ++i) {
        int y = sy + dy[i], x = sx + dx[i];
        while (in(y, x) && s[y][x] == d) {
            y += dy[i];
            x += dx[i];
        }
        if (!in(y, x) || s[y][x] != c) continue;
        s[sy][sx] = c;
        y = sy + dy[i], x = sx + dx[i];
        while (in(y, x) && s[y][x] == d) {
            s[y][x] = c;
            y += dy[i];
            x += dx[i];
        }
    }
}

int mami() {
    memset(cnt, 0, sizeof(cnt));
    int mx = 0, y = -1, x = -1;
    for (int i = 0; i < 8; ++i) for (int j = 0; j < 8; ++j) if (s[i][j] == '.') {
        cnt[i][j] = count(i, j, 'o', 'x');
        if (cnt[i][j] > mx) {
            mx = cnt[i][j];
            y = i;
            x = j;
        }
    }
    if (y < 0) return -1;
    simu(y, x, 'o', 'x');
    return 0;
}

int majo() {
    memset(cnt, 0, sizeof(cnt));
    int mx = 0, y = -1, x = -1;
    for (int i = 7; i > -1; --i) for (int j = 7; j > -1; --j) if (s[i][j] == '.') {
        cnt[i][j] = count(i, j, 'x', 'o');
        if (cnt[i][j] > mx) {
            mx = cnt[i][j];
            y = i;
            x = j;
        }
    }
    if (y < 0) return -1;
    simu(y, x, 'x', 'o');
    return 0;
}

void _main() {
    REP (i, 8) cin >> s[i];
    int pass = 0;
    while (true) {
        if (mami() < 0) pass++;
        else pass = 0;
        if (pass == 2) break;
        if (majo() < 0) pass++;
        else pass = 0;
        if (pass == 2) break;
    }
    REP (i, 8) cout << s[i] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}


Measured memory_bytes: 3252
#include <iostream>
#include<string>
#include<algorithm>
#include<functional>

using namespace std;


int main() {

	int N,K,L[50];
	cin >> N >>K;

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

	sort(L, L + N, greater<int>());
	int Y = 0;

	for (int m = 0; m < K; m++) {
		Y += L[m];
	}

	cout << Y << endl;

	return 0;
}

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

int main(){
    ll n;
    cin>>n;
    vector<ll> p(n);
    for(ll i=0;i<n;++i){
        cin>>p[i];
    }
    sort(p.begin(), p.end());
    ll ans=0;
    for(ll i=0;i<n;++i){
        ans+=p[i];
    }
    ans-=p[n-1]/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


V<string> split(const string& s, char c) {
  V<string> res;
  stringstream ss(s);
  string t;
  while (getline(ss, t, c)) res.push_back(t);
  return res;
}

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  string s;
  while (getline(cin, s)) {
    auto ss = split(s, ' ');
    V<> a(4);
    for (int i = 0; i < 4; ++i) a[i] = stoi(ss[i]);
    getline(cin, s);
    ss = split(s, ' ');
    V<> b(4);
    for (int i = 0; i < 4; ++i) b[i] = stoi(ss[i]);
    int h = 0;
    for (int i = 0; i < 4; ++i) h += a[i] == b[i];
    int bl = 0;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) if (i != j) {
        if (b[i] != a[j]) continue;
        ++bl;
        break;
      }
    }
    cout << h << ' ' << bl << '\n';
  }
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
 
// a,b,cの最大値、最小値をそれぞれminimumの参照先、maximumの参照先に代入する

int main() {
    string n ;
    cin >>n;
    bool a=false,b=false;
    for(int i=0;i<3;i++){
        if(n.at(i)=='A'){
            a=true;
        }
        if(n.at(i)=='B'){
            b=true;
        }
    }
    if(a&&b)
    {cout << "Yes"<<endl;}
    else {
        cout << "No"<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e2 + 10 ;
int a[maxn] ;
int n , x ;
int main()
{	
	cin >> n >> x ;
	for ( int i = 0 ; i< n ; i++)
		cin >> a[i] ;
	sort ( a , a+n ) ;
	for ( int i = 0 ; i< n ; i++)
	{	
		if ( i == n-1 ) 
		{
			if ( x == a[i] )
			       cout << n << endl;
			else
				cout << i << endl;	
			//cout << " I " << i << " x " << x << " a[i] " << a[i] << endl ;
			return 0 ;
		}
		else if ( x >= a[i] ) 
			x-=a[i] ;
		else if ( x < a[i] ) 
		{
			//cout << " i " << i << " x " << x << " a[i] " << a[i] << endl;
			cout << i << endl;
			return 0 ;
		}
		
	}
}

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

int main(){
	int n, k;

	cin >> n >> k;
    
    int a[n];

	loop(i,n){
		cin >> a[i];
	}
 

    int mini = 1e9;

	loop(i, n - k + 1){
		int temp;
		temp = a[i + k - 1] - a[i] + min(abs(a[i]), abs(a[i+k-1]));
		mini = min(mini, temp);
	}

	cout << mini;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }

//long longのシフト演算には気をつけよう

int main(){
    int mod = 1000000007;
    int N,M; cin >> N >> M;

    if(abs(N-M) > 1) cout << 0 << endl;
    else if(abs(N-M) == 1){
        ll ans = 1;
        for(int i=1; i<=N; i++) ans = (ans*i)%mod;
        for(int i=1; i<=M; i++) ans = (ans*i)%mod;
        cout << ans << endl;
    }
    else{
        ll ans = 1;
        for(int i=1; i<=N; i++) ans = (ans*i)%mod;
        for(int i=1; i<=M; i++) ans = (ans*i)%mod;
        ans = (ans*2)%mod;
        cout << ans << endl;
    }
}

Measured memory_bytes: 256