akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		string s;
		cin>>s;
		if(s=="#") break;
		int h=1,w;
		for(auto c:s) if(c=='/') h++;
		vvi a(h,vi(11));
		s+='/';
		int id=0;
		string t;
		for(auto c:s){
			if(c=='/'){
				int x=0;
				for(auto c1:t){
					if(c1=='b') a[id][x++]++;
					else x+=c1-'0';
				}
				w=x;
				t="";
				id++;
			}
			else t+=c;
		}
		int x,y,X,Y;
		cin>>x>>y>>X>>Y;
		a[x-1][y-1]--;
		a[X-1][Y-1]++;
		t="";
		for(int i=0;i<h;i++){
			if(i) t+='/';
			int cnt=0;
			for(int j=0;j<w;j++){
				if(a[i][j]){
					if(cnt) t+=(char)('0'+cnt);
					t+='b',cnt=0;
				}
				else cnt++;
			}
			if(cnt) t+=(char)('0'+cnt);
		}
		cout<<t<<endl;
	}
}


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

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

if(a<40)
  a=40;
if(b<40)
  b=40;
if(c<40)
  c=40;
if(d<40)
  d=40;
if(e<40)
  e=40;

cout<<(a+b+c+d+e)/5<<'\n';

return 0;
}

Measured memory_bytes: 1160
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << x << "\n"
#define int long long
using namespace std;
using point = pair< int,int >;

signed main() {
    int cnt = 0;
    int in;
    REP(i, 10) {
        cin >> in;
        cnt += in;
    }
    OUT(cnt);

    return 0;
}




Measured memory_bytes: 3084
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
int main(){
    int n; cin >> n;
    int h[n]; for(int i=0; i<n; i++) cin >> h[i];
    int dp[n+2]; for(int i=0; i<n; i++) dp[i] = 1e9;
    dp[0] = 0;
    for(int i=0; i<n; i++){
        dp[i+1] = min(dp[i]+abs(h[i]-h[i+1]),dp[i+1]);
        dp[i+2] = min(dp[i]+abs(h[i]-h[i+2]),dp[i+2]);
    }
    cout << dp[n-1] << endl; 
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdint>
#include<string>

int64_t const MOD = 1e9+7;
std::string s;

int main() {
  std::cin >> s;
  int64_t a = 0, b = 0, c = 0;
  int l = s.size();
  int64_t nq = 1;
  for(int i = 0; i < l; ++i) {
    int64_t na = a, nb = b, nc = c;
    switch(s[i]) {
      case 'A': na += nq; break;
      case 'B': nb += a; break;
      case 'C': nc += b; break;
      default:
        na = a*3+nq;
        nb = b*3+a;
        nc = c*3+b;
        (nq *= 3) %= MOD;
    }
    a = na%MOD; b = nb%MOD; c = nc%MOD;
  }
  std::cout << c << std::endl;
  return 0;
}


Measured memory_bytes: 512
n = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i).sort.reverse
gochi, usa = 0, 0

skip = false
(0..(n - 2)).each do |i|
  if skip
    skip = false
    next
  end
  if a[i] == a[i + 1]
    if gochi.zero?
      gochi = a[i]
      skip = true
    else
      usa = a[i]
      break
    end
  end
end
puts gochi * usa


Measured memory_bytes: 11016
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	long long a,b,c;
	cin>>a>>b>>c;
    if(a%2 && b%2 && c%2)//全为奇数 
    {
    	long long min=1;
        if(a<b)
        {
        	min*=a;
        	if(c<b) min*=c;
        	else min*=b;
		}
		else
		{
			min*=b;
			if(c<a) min*=c;
			else min*=a;
		}
		cout<<min<<endl;
	}
	else cout<<0<<endl;
	return 0;
} 

Measured memory_bytes: 256
// by adiforluls
#pragma GCC optimize ("-O2")
#include<bits/stdc++.h>
using namespace std;
#define fastestiointhewest   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll          long long
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define mii         map<int,int>
#define vi          vector<int>
#define vll         vector<long long>
#define all(a)      (a).begin(),(a).end()
#define clz(a)      __builtin_clz(a) // count leading zeroes
#define ctz(a)      __builtin_ctz(a) // count trailing zeroes
#define popc(a)     __builtin_popcount(a) // count set bits (for ints only diff for ll)
#define lul         1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define SIZE        1000005
#define F           first
#define S           second
#define debug(x)    cerr << #x << " = " << x << endl;
#define mod         998244353

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " = " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " = " << arg1<<" |";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define endl        '\n'
const ld PI = acos(-1.0);
const int INF = 0x3f3f3f3f;

void solve()
{
   int n,k; cin>>n>>k;
   string s; cin>>s;
   vi v;
   int flag=1,cur1=0,cur2=0,ans=-1;
   rep(i,0,n)
   {
      if(s[i]=='1')
      {
        if(!flag)
        {
          v.pb(i);
          flag=1;
        }
        cur1++;
        ans=max(cur1-cur2,ans);
      }
      else{
        flag=0;
        if((int)v.size()==k)
        {
          cur2=*v.begin();
          v.erase(v.begin());
        }
        cur1++;
        ans=max(ans,cur1-cur2);
      }
   }
   cout<<ans;
} 
int main()
{   
    fastestiointhewest;
   //  #ifndef ONLINE_JUDGE
     // freopen("input.txt", "r", stdin);
     // freopen("output.txt", "w", stdout);
   //  #endif
    int t; t=1;
    while(t--){
       solve();
    }
    return 0;
}

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

int main()
{
  const int INF = 1e+9;
  int h, w;
  string s[50];
  int white = 0;

  cin >> h >> w;
  for(int i = 0; i < h; i++){
    cin >> s[i];
    for(int j = 0; j < w; j++){
      if(s[i][j] == '.') white++;
    }
  }

  int d[50][50];
  for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++) d[i][j] = INF;
  d[0][0] = 1;

  int dx[] = { 0, 1, 0, -1 };
  int dy[] = { 1, 0, -1, 0 };
  queue<pair<int, int> > q;
  q.push(make_pair(0, 0));

  while(!q.empty()){
    pair<int, int> p = q.front();
    q.pop();

    for(int i = 0; i < 4; i++){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];

      if(0 <= nx && nx < w && 0 <= ny && ny < h){
        if(s[ny][nx] == '.' && d[ny][nx] > d[p.second][p.first] + 1){
          d[ny][nx] = d[p.second][p.first] + 1;
          q.push(make_pair(nx, ny));
        }
      }
    }
  }

  if(d[h-1][w-1] == INF) cout << -1 << endl;
  else cout << white - d[h-1][w-1] << endl;

  return 0;
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int  main(){
  int n, m, c;
  cin >> n >> m >> c;

  int b[m];
  
  for(int i=0; i<m; ++i) cin >> b[i];

  int a[n][m];
  for(int i=0; i<n; ++i){
    for(int j=0; j<m; ++j){
      cin >> a[i][j];
    }
  }


  int cnt = 0;
  for(int i=0; i<n; ++i){
    int sum = 0;
    for(int j=0; j<m; ++j){
      sum += (a[i][j]*b[j]);
    }
    if(sum + c > 0) ++cnt;
  }
  
  cout << cnt;
  return 0;
}

Measured memory_bytes: 256
// aribon3-3_g
// Range Query - RMQ and RUQ
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_F&lang=jp
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1ll << 31)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


// 区間update, 区間min
template<typename T>
struct LazySegmentTree{
    int n;
    vector<T> val;
    vector<T> lazy;

    explicit LazySegmentTree(int n_){
        n = 1;
        while (n < n_) n <<= 1;

        val = vector<T>(n<<1, INF);
        lazy = vector<T>(n<<1, -1);
    }
    void lazy_propagate(int k) {
        if (lazy[k] == -1) return;

        val[k] = lazy[k];
        if (k < n-1) {
            lazy[k*2+1] = lazy[k];
            lazy[k*2+2] = lazy[k];
        }
        lazy[k] = -1;
    }
    void update(int a, int b, int k, int l, int r, int x) {
        lazy_propagate(k);

        if (b <= l || r <= a) {
            return;
        }
        if (a <= l && r <= b) {
            lazy[k] = x;
            lazy_propagate(k);
            return;
        }
        int mid = (l+r)/2;
        update(a, b, k*2+1, l, mid, x);
        update(a, b, k*2+2, mid, r, x);
        val[k] = min(val[k*2+1], val[k*2+2]);
    }

    void update(int a, int b, int x) {
        update(a, b, 0, 0, n, x);
    }

    T get_min(int a, int b, int k, int l, int r) {
        lazy_propagate(k);

        if (b <= l || r <= a) {
            return INF;
        }
        if (a <= l && r <= b) {
            return val[k];
        }
        int mid = (l+r)/2;
        T sl = get_min(a, b, k*2+1, l, mid);
        T sr = get_min(a, b, k*2+2, mid, r);
        return min(sl, sr);
    }

    T get_min(int a, int b) {
        return get_min(a, b, 0, 0, n);
    }
};

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, Q;
    cin >> N >> Q;

    LazySegmentTree<ll> sst(N);

    REP(i, Q){
        int q;
        cin >> q;
        if (q == 0){
            int s, t, x;
            cin >> s >> t >> x;
            sst.update(s, t+1, x);

        } else {
            int s, t;
            cin >> s >> t;
            ll ans = sst.get_min(s, t+1);
            print(ans);
        }

    }

    return 0;
}



Measured memory_bytes: 7076
import math
n=int(input())


maxa=math.floor((n-1)**0.5)
#print(maxa)

PossibleB=0

#a>=b を仮定
for a in range(1,maxa+1):
  #print(a)
  #print(math.floor((n-1)/a)-(a-1))
  PossibleB += math.floor((n-1)/a)-(a-1)

#a==b　の重複は削除
print(2*PossibleB-maxa)

Measured memory_bytes: 62524
#include <stdio.h>
#include <string.h>

int main() {
    char O[51];
    char E[51];
    scanf("%s\n%s", O, E);
    int len1 = strlen(O);
    int len2 = strlen(E);
    for (int i = 0; i < len2; i ++) {
        printf("%c", O[i]);
        printf("%c", E[i]);
    }
    if (len2 < len1) {
        printf("%c", O[len2]);
    }
    puts("");
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;//nÍ¢ÁØñÉA^CÌBkÍÍªê½
int a,b;

int main(void){

	scanf("%d\n",&n);
	scanf("%d\n",&k);
	for (int j=0;j<k;j++){
		scanf("%d",&a);
		scanf("%d",&b);
	  int x = a-1;
      int y = b-1;
      int z = n-x-1;
      int w = n-y-1;
      int m = min(min(x,y),min(z,w));
	  printf("%d\n",m%3+1);
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main()
{
  string s, t;
  cin >> s >> t;

  int a, b;
  cin >> a >> b;

  string u;
  cin >> u;

  if(u.compare(s) == 0){
    a-- ;
  } else {
    b--;
  }
  
  cout << a << " " << b << endl;
    
  return 0;
}

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

using namespace std;

const int md = 1e9 + 7;
const int mxn = 3e5;

long long a[mxn + 11];
int main(){
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%lld", a + i);
	}
	long long cur = 1;
	long long ans = 0;
	for (int i = 1; i <= 61; i++){
		int cnt = 0;
		for (int j = 0; j < n; j++){
			if (a[j] & cur)
				cnt++;
		}
		long long now = cnt * 1LL * (n - cnt) % md;
		now = now * 1LL * (cur % md) % md;
		ans = (ans + now) % md;
		cur <<= 1;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 2560
program abc116c
  integer :: n
  integer,allocatable :: a(:), d(:)
  read *, n
  allocate(a(0:n))
  a(0) = 0
  read *, a(1:n)
  d = a(1:n) - a(0:n-1)
  print *, sum(d,d>0)
end program abc116c


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int ls[N], s[N], pos[N], num[N], n, a[N];
int sum[N * 4];
void add(int now, int l, int r, int pos) {
    sum[now]++;
    if(l == r) return;
    int mid = l + r >> 1;
    if(pos <= mid) add(now * 2, l, mid, pos);
    else add(now * 2 + 1, mid + 1, r, pos);
}
bool ask(int now, int l, int r, int L, int R) {
    if(l > R || L > r) return false;
    if(L <= l && r <= R) return (sum[now] != 0);
    int mid = l + r >> 1;
    return ask(now * 2, l, mid, L, R) | ask(now * 2 + 1, mid + 1, r, L, R);
}
bool ask(int pos) {
   return ask(1, 1, n, 1, pos);
}
void add(int pos) {
   add(1, 1, n, pos);
}
bool find(int x, int right) {
    int l = 1, r = n;
    for(int mid = l + r >> 1; l < r; mid = l + r >> 1) {
        if(ls[mid] < x) l = mid + 1;
        else r = mid;
    }
    while(ls[l] > x && l > 0) l--;
    if(l == 0) return false;
   // printf("ask = %d %d %d %d\n", l, ask(l), x, ls[l]);
    return ask(l);
}
bool check(int x) {
   // printf("test = %d\n", x);
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++) {
        if(find(a[i] - x, i)) return true;
        add(num[i]);
        //printf("num = %d\n", num[i]);
        //rem[num[a[i]]] ++; 
    }    
    return false;
}
int main()
{
    int minn = 0, maxn = 0, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ls[i] = a[i];
        maxn = max(maxn, a[i]);
    }
    sort(ls + 1, ls + n + 1);
    for (int i = 1; i <= n; i++) {  
        num[i] = lower_bound(ls + 1, ls + n + 1, a[i]) - ls;
        pos[num[i]] = i;
        //cerr << num[i] << " "; 
        //
    }
    //cerr << "\n"; 
    //
    int l = minn, r = maxn;
    for (int mid = (l + r) >> 1; l < r; mid = (l + r) >>  1) {
    //printf("%d %d\n", l, r);
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    if(!check(l)) l--;
    memset(sum, 0, sizeof(sum));
    //printf("%d\n", l);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if(find(a[i] - l, i)) ans++;
        add(num[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3328
#include<math.h>
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ll long long int
#define ull unsigned long long
#define py printf("Yes\n")
#define pn printf("No\n")
#define in cin>>
using namespace std;
int INF = 1001001001;
const int MOD=1e9+7;

int main()
{
  string a,ans="";
  in a;
  if(a=="A")ans='A';
  else if(a=="B")ans='A';
  else if(a=="C")ans='A';
  else if(a=="D")ans='A';
  else if(a=="E")ans='A';
  else if(a=="F")ans='A';
  else if(a=="G")ans='A';
  else if(a=="H")ans='A';
  else if(a=="J")ans='A';
  else if(a=="K")ans='A';
  else if(a=="L")ans='A';
  else if(a=="M")ans='A';
  else if(a=="N")ans='A';
  else if(a=="O")ans='A';
  else if(a=="P")ans='A';
  else if(a=="Q")ans='A';
  else if(a=="R")ans='A';
  else if(a=="S")ans='A';
  else if(a=="T")ans='A';
  else if(a=="U")ans='A';
  else if(a=="V")ans='A';
  else if(a=="W")ans='A';
  else if(a=="X")ans='A';
  else if(a=="Y")ans='A';
  else if(a=="Z")ans='A';
  else if(a=="a")ans='a';
  else if(a=="b")ans='a';
  else if(a=="c")ans='a';
  else if(a=="d")ans='a';
  else if(a=="e")ans='a';
  else if(a=="f")ans='a';
  else if(a=="g")ans='a';
  else if(a=="h")ans='a';
  else if(a=="i")ans='a';
  else if(a=="j")ans='a';
  else if(a=="k")ans='a';
  else if(a=="l")ans='a';
  else if(a=="m")ans='a';
  else if(a=="n")ans='a';
  else if(a=="o")ans='a';
  else if(a=="p")ans='a';
  else if(a=="q")ans='a';
  else if(a=="r")ans='a';
  else if(a=="s")ans='a';
  else if(a=="t")ans='a';
  else if(a=="u")ans='a';
  else if(a=="v")ans='a';
  else if(a=="w")ans='a';
  else if(a=="x")ans='a';
  else if(a=="y")ans='a';
  else if(a=="z")ans='a';
  cout<<ans<<endl;
}


Measured memory_bytes: 3624
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    x = I()
    a = x//500
    x -= a*500
    b = x//5
    print(a*1000+b*5)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 38384
import java.util.Scanner;

/**
 * 冒泡排序
 * @author MZ21G
 *
 */
public class Main {

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt();
		
		int arr[] = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = scanner.nextInt();
		}
		
		int flag = 0;
		for (int k = 1; k <= N; k++) {
			for (int i = arr.length - 1; i > 0; i--) {
				int j = i - 1;
				if (arr[j] > arr[i]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
					flag++;
				}
			}
		}
	
		
		for (int i = 0; i < arr.length - 1; i++) {
			System.out.printf("%d ", arr[i]);
		}
		System.out.println(arr[arr.length - 1]);
		System.out.println(flag);
		
		
	}
}



Measured memory_bytes: 26464
h,w=gets.split.map(&:to_i)
n=gets.to_i
a=gets.split.map(&:to_i)

puts a.flat_map.with_index(1){|c,i|[i]*c}.each_slice(w).map.with_index{|c,i|(i%2<1?c:c.reverse)*" "}

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

int main(){
    int N;
    string A,B,C;
    
    cin>>N;
    cin>>A;
    cin>>B;
    cin>>C;
    
    int i;
    int count=0;
    
    for(i=0;i<N;i++){
        if(A[i]!=B[i]&&B[i]!=C[i]&&A[i]!=C[i]){
            count+=2;
        }else if(A[i]==B[i]&&B[i]==C[i]){
            continue;
        }else{
            count++;
        }
    }
    
    cout<<count<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N (1<<18)
#define INF (1e9)
using namespace std;
struct po{
  int l,r,x;
  po(){};
  po(int l,int r,int x):l(l),r(r),x(x){}
};
const int base=1e5+2;
int segMin[2][2*N-1], segAdd[2][2*N-1];
int w,h,m,x[N],y[N];
vector <po> mp[2][N];
po LR[N];

//starry sky tree
void add(int a,int b,int x,int k,int l,int r,int idx){
  if(r<=a||b<=l) return;
  if(a<=l&&r<=b){segAdd[idx][k]+=x;return;} 
  add(a,b,x,2*k+1,l,(l+r)/2,idx);
  add(a,b,x,2*k+2,(l+r)/2,r,idx);
  int L=segMin[idx][2*k+1]+segAdd[idx][2*k+1];
  int R=segMin[idx][2*k+2]+segAdd[idx][2*k+2];
  segMin[idx][k]=min(L,R);
}

int getMin(int a,int b,int k,int l,int r,int idx){
  if (r<=a||b<=l) return INF;
  if (a<=l&&r<=b) return segMin[idx][k]+segAdd[idx][k];
  int L=getMin(a,b,2*k+1,l,(l+r)/2,idx);
  int R=getMin(a,b,2*k+2,(l+r)/2,r,idx);
  return min(L,R)+segAdd[idx][k];
}

void mk_LR(){
  
  for(int i=0;i<h&&w==1;i++)LR[i+base]=po(base+i,base+i,i%2);
  if(w==1)return;
  LR[base]=po(base,base,0);
  LR[base+1]=po(base,base+1,1);
  int mn=min(w,h),S,cnt=0;
  for(int i=1;i<mn;i++) cnt+=2*i;
  S=(w*h-cnt)/mn;
  if(w==2)S--;
  for(int i=base+2;;i++){
    int l=LR[i-2].l-1,r=LR[i-2].r+1,x=LR[i-2].x;

    if(S==0&&!x)l=LR[i-1].l,r=l+mn-2,S--;
    else if(S==0&&x)l=LR[i-1].l+1,r=LR[i-1].r,S--;
    else if(S<0) l+=2,r-=2;
    if(l>r)break;
    if(r-l+1>mn) l=LR[i-2].l,r=l+mn-1;
    if(S>0&&LR[i-2].r-LR[i-2].l+1==mn)l=LR[i-2].l+1,r=l+mn-1;
    if(r-l+1==mn)S--;
    LR[i]=po(l,r,x);
  }
}

void mk_mp(int d){
  for(int i=0;i<N;i++) mp[0][i].clear();
  for(int i=0;i<N;i++) mp[1][i].clear();
  
  for(int i=0;i<m;i++){
    int idx=y[i]+(w-x[i]-1)+base;
    int c=LR[idx].l+min(y[i],x[i]);
    int a=idx%2,b=(idx+d)%2;
    int D=d/2;
    if(d%2==0){
      mp[b][idx-d].push_back(po(c-D,c+D,1));
      mp[b][idx+d+1].push_back(po(c-D,c+D,-1));

      mp[!b][idx-d+1].push_back(po(c-D+!a,c+D-a,1));
      mp[!b][idx+d].push_back(po(c-D+!a,c+D-a,-1));
    }
    else {
      mp[b][idx-d].push_back(po(c-D-a,c+D+!a,1));
      mp[b][idx+d+1].push_back(po(c-D-a,c+D+!a,-1));
      
      mp[!b][idx-d+1].push_back(po(c-D,c+D,1));
      mp[!b][idx+d].push_back(po(c-D,c+D,-1));
    }
  }
}


bool check(int d){
  mk_mp(d);
  memset(segMin,0,sizeof(segMin));
  memset(segAdd,0,sizeof(segAdd));
  for(int i=0;i<N;i++){
    int bit=i%2;
    for(int k=0;k<2;k++)
      for(int j=0;j<(int)mp[k][i].size();j++)add(mp[k][i][j].l,mp[k][i][j].r+1,mp[k][i][j].x,0,0,N,k);


    if(LR[i].l&&!getMin(LR[i].l,LR[i].r+1,0,0,N,bit))return 1;
  }
  return 0; 
}

int search(){
  if(w==1){
    sort(y,y+m);
    int res=max(y[0],h-y[m-1]-1);    
    for(int i=1;i<m;i++) res=max(res,(y[i]-y[i-1]-1)/2+(y[i]-y[i-1]-1)%2);
    return res;
  }
 
  int L=0,M,R=100001;
  while(L<R){
    M=(L+R)/2;
    if(!check(M)) R=M;
    else L=M+1;
  }
  return L;
}
int main(){
  cin>>w>>h>>m;
  for(int i=0;i<m;i++)cin>>x[i]>>y[i];
  if(w>h){
    swap(w,h);
    for(int i=0;i<m;i++)swap(x[i],y[i]); 
  }
  mk_LR();
  cout <<search()<<endl;
  return 0;
}

Measured memory_bytes: 72152
#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	int n, h, w;
	cin >> n >> h >> w;
	cout << (n - h + 1) * (n - w + 1) << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define PB(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007

using namespace std;


int main() {
	int n, x;
	long long cnt = 0;
	cin >> n >> x;
	vector<int> v(n);
	REP(i, n) {
		cin >> v[i];
	}
	vector<int> w(n - 1);
	REP(i, n-1) {
		w[i] = v[i] + v[i + 1];
	}
	FOR(i, 0, n - 2) {
		if (w[i] > x) {
			int c = min(v[i + 1], w[i] - x);
			cnt += c;
			w[i] -= c;
			w[i + 1] -= c;
			v[i + 1] -= c;
		}
	}
	if (w[0] > x) {
		cnt += w[0] - x; w[0] = x;
	}
	if (w[n - 2] > x) cnt += w[n - 2] - x;
	cout << cnt << endl;
	return 0;
}


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

class Dice {
public:
	int u, f, r, l, b, d;

	Dice(int uu, int ff, int rr, int ll, int bb, int dd) {
		u = uu;
		f = ff;
		r = rr;
		l = ll;
		b = bb;
		d = dd;
	}

	void move(char dir) {
		int tmp;

		if (dir == 'N') {
			tmp = u;
			u = f;
			f = d;
			d = b;
			b = tmp;
		}
		else if (dir == 'E') {
			tmp = u;
			u = l;
			l = d;
			d = r;
			r = tmp;
		}
		else if (dir == 'S') {
			tmp = u;
			u = b;
			b = d;
			d = f;
			f = tmp;
		}
		else if (dir == 'W') {
			tmp = u;
			u = r;
			r = d;
			d = l;
			l = tmp;
		}
	}
};


int main()
{
	int a, b, c, d, e, f;
	string order;
	cin >> a >> b >> c >> d >> e >> f >> order;

	Dice dice(a, b, c, d, e, f);

	for (int i = 0;i < order.size();i++) {
		dice.move(order[i]);
	}

	cout << dice.u << endl;

    return 0;
}



Measured memory_bytes: 3172
#include <stdio.h>
#include <math.h>

int main(void) {
  int N, D;
  scanf("%d %d", &N, &D);

  int X[10][10];
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < D; j++) {
      scanf("%d", &X[i][j]);
    }
  }
  int ans = 0;
  for(int i = 0; i < (N-1); i++) {
    for(int j = i+1; j < N; j++) {
      int sum = 0;
      for(int k = 0; k < D; k++) {
	int tmp = (X[j][k] - X[i][k]);
	sum += (tmp * tmp);
      }
      int int_sqrt = (int)sqrt((double)sum);
      int int_sum = int_sqrt * int_sqrt;
      if(int_sum == sum)
	ans++;
    }
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int i = 0; i < 1 << (a + b); i++) {
        int x = 0, y = 0;
        bool ok = true;
        for (int j = a + b - 1; j >= 0; j--) {
            if (i & (1 << j))x++;
            else y++;
            if (j != 0 && max(x, y) > 4 && min(x, y) < 4)ok = false;
        }

        if (ok && b == x) {
            if (a > 4 && b > 4) {
                int tmp = 0;
                for (int j = a + b - 1; j >= a + b - 8; j--) {
                    if (i & (1 << j))tmp++;
                }
                if (tmp != 4)continue;
            }

            for (int j = a + b - 1; j >= 0; j--) {
                if (i & (1 << j))cout << 'B';
                else cout << 'A';
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3084
#include<stdio.h>

int main(){
  int n;
  int i;
  scanf("%d",&n);
  int Fib[50];
  Fib[0]=1;
  Fib[1]=1;
  for(i=2;i<=n;i++)Fib[i]=Fib[i-1]+Fib[i-2];
  printf("%d\n",Fib[n]);
  return 0;
}
		  

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

using namespace std;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

template <unsigned long long mod> class modint {
public:
	unsigned long long v;
	modint(const long long x = 0) : v(x % mod) {}
	modint operator+(const modint rhs) { return modint(*this) += rhs; }
	modint operator-(const modint rhs) { return modint(*this) -= rhs; }
	modint operator*(const modint rhs) { return modint(*this) *= rhs; }
	modint operator/(const modint rhs) { return modint(*this) /= rhs; }
	modint operator-() { return modint(mod - this->v); }
	modint& operator+=(const modint rhs) {
		v += rhs.v;
		if (v >= mod) v -= mod;
		return *this;
	}
	modint& operator-=(const modint rhs) {
		if (v < rhs.v) v += mod;
		v -= rhs.v;
		return *this;
	}
	modint& operator*=(const modint rhs) {
		v = v * rhs.v % mod;
		return *this;
	}
	modint inverse(modint a) {
		unsigned long long exp = mod - 2;
		modint ret(1ULL);
		while (exp) {
			if (exp % 2) { ret *= a; }
			a *= a;
			exp >>= 1;
		}
		return ret;
	}
	modint& operator/=(modint rhs) {
		(*this) *= inverse(rhs);
		return *this;
	}
	friend ostream& operator<<(ostream& os, modint& u) {
		os << u.v;
		return (os);
	}
	friend istream& operator>>(istream& is, modint& u) {
		is >> u.v;
		return (is);
	}
};
const int MOD = 1000000007;
using mint = modint<MOD>;

const int MAX = 1000005;
mint fact[MAX], invfact[MAX], inv[MAX];

void facinit() {
	fact[0] = fact[1] = 1;	
	invfact[0] = invfact[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++){
		fact[i] = fact[i - 1] * i;
		inv[i] = - inv[MOD%i] * (MOD / i);
		invfact[i] = invfact[i - 1] * inv[i];
	}
}

mint nCr(int n, int r){
	if(n < 0|| r < 0 || n < r)return mint{0};
	return fact[n]*invfact[r]*invfact[n-r];
}

class Solution {
public:
	void solve() {
		int n, k;
		cin >> n >> k;
		vector<int> a(n, 0);
		facinit();
		for(int i=0; i<n; i++)cin >> a[i];
		sort(a.begin(), a.end());
		for(int i=0; i < n; i++)if(a[i] < 0)a[i] += MOD;
		mint ans = 0;
		for(int i = k-1; i < n; i++){
			ans += mint(a[i])*nCr(i,k-1);
		}
		for(int i= k-1; i < n; i++){
			ans -= mint(a[n-1-i])*nCr(i, k-1);
		}
		cout << ans << "\n";
		
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 24064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  int l = S.length();
  int min = INT_MAX;
  for ( int i = 0; i < l-2; i++ ) {
    int x = abs( 753 - atoi(S.substr(i,3).c_str()) );
    if ( x < min ) min = x;
  }

  cout << min << endl;
}

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

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v(0) {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<TEN(9) + 7>;

using D = array<Mint, 2>;
VV<int> g;
D dfs(int p, int b) {
    D dp = {Mint(1), Mint(1)};
    for (int d: g[p]) {
        if (d == b) continue;
        D x = dfs(d, p);
        dp[0] = dp[0] * (x[0] + x[1]);
        dp[1] = dp[1] * x[0];
    }
    return dp;
}

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

    int n;
    cin >> n;
    g = VV<int>(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y; x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    auto d = dfs(0, -1);
    cout << d[0] + d[1] << endl;
    return 0;
}


Measured memory_bytes: 12672
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<iomanip>
using namespace std;
int main(){
double a,b,c;
double S,L,h;
cin>>a>>b>>c;
S=1/2.0*a*b*sin(c/180.0f*M_PI);
L=a+b+sqrt(a*a+b*b-2.0*a*b*cos(c/360.0*2.0*M_PI));
h=2.0*S/a;
cout<<fixed << setprecision(10)<<S<<endl;
cout<<fixed << setprecision(10)<<L<<endl;
cout<<fixed << setprecision(10)<<h<<endl;
}

Measured memory_bytes: 1332
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main(void){
    // Your code here!
    int n,k;
    cin >> n >> k;
    double p=0;
    for(int i=0; i < n;i++){
        double t=log((double)k/(i+1))/log(2);
        if(t>0)p+=pow(0.5,ceil(t))/n;
        else p+=(double)1/n;
    }
    printf("%.10lf\n", p);
    
    return 0;
}


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    ll N, K; cin >> N >> K;
    vector<ll> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    vector<ll> F(N);
    for(int i=0; i<N; i++) cin >> F[i];

    sort(A.begin(), A.end());
    sort(F.rbegin(), F.rend());

    ll ub = LONGINF, lb = -1;
    while(ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        ll sum = 0;
        for(int i=0; i<N; i++) {
            ll max_val = mid / F[i];
            sum += max(0LL, A[i] - max_val);
        }
        if(sum <= K) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define F first
#define S second
#define int long long
#define mod 1000000007
using namespace std;
int mypow(int a, int b, int c) {
	if (b == 0)return 1;
	if (b % 2)return mypow(a, b - 1, c)*a%c;
	int z = mypow(a, b / 2, c);
	return z * z%c;
}
int x[3][3];
bool b[3][3];
signed main() {
	int n;
	f(i, 3) {
		f(j, 3) {
			cin >> x[i][j];
		}
	}
	cin >> n;
	f(i, n) {
		int a;
		cin >> a;
		f(j, 3) {
			f(k, 3) {
				if (x[j][k] == a)b[j][k] = 1;
			}
		}
	}
	f(i, 3) {
		bool bo = true;
		f(k, 3) {
			if (!b[i][k])bo = false;
		}
		if (bo) {
			puts("Yes");
			return 0;
		}
	}
	f(j, 3) {
		bool bo = true;
		f(i, 3) {
			if (!b[i][j])bo = false;
		}
		if (bo) {
			puts("Yes");
			return 0;
		}
	}
	bool bo = true;
	f(i, 3) {
		if (!b[i][i])bo = false;
	}
	if (bo) {
		puts("Yes");
		return 0;
	}
	bo = true;
	f(i, 3) {
		if (!b[2 - i][i])bo = false;
	}
	if (bo)puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N,K,R,S,P; cin>>N>>K>>R>>S>>P;
    ll ans=0;
    string s; cin>>s;
    //MOD iについて
    rep(i,K){
        ll tmp=0;
        
        if(sz(s)%K==0) tmp=sz(s)/K;
        else{
            if(i<sz(s)%K) tmp=(sz(s)+K-1)/K;
            else tmp=(sz(s)+K-1)/K-1;
        }
        
        //dp[j][k]:j番目にkを出したときの最高点数
        vector<vector<ll> > dp(tmp+1,vector<ll>(3,0));
        
        rep1(j,tmp){
            if(s[K*(j-1)+i]=='r'){
                chmax(dp[j][2],dp[j-1][0]+P);
                chmax(dp[j][2],dp[j-1][1]+P);
                dp[j][0]=max(dp[j-1][1],dp[j-1][2]);
                dp[j][1]=max(dp[j-1][0],dp[j-1][2]);
            }
            else if(s[K*(j-1)+i]=='s'){
                chmax(dp[j][0],dp[j-1][2]+R);
                chmax(dp[j][0],dp[j-1][1]+R);
                dp[j][1]=max(dp[j-1][0],dp[j-1][2]);
                dp[j][2]=max(dp[j-1][1],dp[j-1][0]);
            }
            else{
                chmax(dp[j][1],dp[j-1][2]+S);
                chmax(dp[j][1],dp[j-1][0]+S);
                dp[j][0]=max(dp[j-1][1],dp[j-1][2]);
                dp[j][2]=max(dp[j-1][1],dp[j-1][0]);
            }
            
        }
        ans+=maxx(dp[tmp][0],dp[tmp][1],dp[tmp][2]);
    }
    cout<<ans<<endl;
}



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

int main(void)
{
    int K;
    char S[105];
    int c;
    scanf("%d", &K);
    scanf("%s", S);
    if (strlen(S) <= K)
    {
        printf("%s", S);
        return 0;
    }
    c = K + 3;
    S[K] = '.';
    S[K + 1] = '.';
    S[K + 2] = '.';
    while (S[c] != '\0')
    {
        S[c] = '\0';
        ++c;
    }
    printf("%s", S);
    return 0;
}

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

int main(){
    ll k;
    cin >> k;
    vector <ll> a(k);
    rep(i,k){
        cin >> a[k-1-i];
    }
    vector <ll> ma(k),mi(k);
    ma[0]=3;
    mi[0]=2;
    int ans=0;

    if(k==1 and a[0]!=2){
        ans=-1;
    }
    if(a[0]!=2){
        ans=-1;
    }
    else{

    rep(i,k-1){
        if((ma[i]/a[i+1])==0){
            ans=-1;
            break;
        }
        if(((ma[i]/a[i+1])*a[i+1])<mi[i]){
            ans=-1;
            break;
        }
        ma[i+1]=(ma[i]/a[i+1])*a[i+1]+a[i+1]-1;
        if((mi[i]%a[i+1])==0){
            mi[i+1]=mi[i];
            if(mi[i+1]>ma[i+1]){
                ans=-1;
                break;
            }
            if(((ma[i]/a[i+1])*a[i+1])<((mi[i]/a[i+1])*a[i+1])){
            ans=-1;
            break;
        }
        }
        else{
            mi[i+1]=(mi[i]/a[i+1])*a[i+1]+a[i+1];
            if(mi[i+1]>ma[i+1]){
                ans=-1;
                break;
            }
            if(((ma[i]/a[i+1])*a[i+1])<((mi[i]/a[i+1])*a[i+1]+a[i+1])){
            ans=-1;
            break;
        }
    }
    }
    

    }

    if(ans==-1){
        cout << ans << endl;
    }
    else{
        //cout << mi[k-1] << " " << ma[k-1] << endl;
        cout << mi[k-1] << endl;
        cout << ma[k-1] << endl;
        

    }
    

    return 0;
}

Measured memory_bytes: 5632
#include<stdio.h>
long long limit=1000000;
int main(){
  int n, k;

  scanf("%d %d", &n, &k);
  long long result = 0;
  if( k==0 ){
    long tmp=n;
    result = tmp*tmp;
    printf("%lld\n", result);
    return 0;
  }
  for(int b=k+1; b<=n; b++){
    int tmp1 = n/b;
    result += tmp1*(b-k);
    int tmp2 = n - tmp1*b;
    if( tmp2 >= k ) result+= tmp2-(k-1);
  }
  
  printf("%lld\n", result);
  return 0;
	 
}


Measured memory_bytes: 128
N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
 
dp = [INF]*N
dp[0] = 0
 
for i,hi in enumerate(h):
    if i == 0:
        continue
    s = i-K if i-K >= 0 else 0
    dp[i] = min([dpk + abs(hi-hk) for dpk,hk in zip(dp[s:i],h[s:i])])
 
print(dp[-1])

Measured memory_bytes: 13980
n=int(input())
a=list(map(int,input().split()))
b=len(a)
result=1
i=0
j=0
while True:
    if a[i]==result:
        result+=1
    i+=1
    if i>=b:
        break
if result==1:
    print(-1)
else:
    print(b-result+1)

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

const int MOD = 1000000007;
struct modint {
  long long val;
  modint(long long val=0) : val((val % MOD + MOD) % MOD){}
  modint operator-() const { return modint(-val); }
  modint& operator+=(const modint a) { if ((val += a.val)     >= MOD) val -= MOD; return *this; }
  modint& operator-=(const modint a) { if ((val += MOD-a.val) >= MOD) val -= MOD; return *this; }
  modint& operator*=(const modint a) { (val *= a.val) %= MOD; return *this; }
  modint operator+(const modint a) const { return (modint)*this += a; }
  modint operator-(const modint a) const { return (modint)*this -= a; }
  modint operator*(const modint a) const { return (modint)*this *= a; }
  modint pow(long long n) const { modint r(1), m(val); while (n > 0) { if (n & 1) {r *= m;} m *= m; n >>= 1; } return r; }
  modint inv() const { return pow(MOD-2); }
  modint& operator/=(const modint a) { return (*this) *= a.inv(); }
  modint operator/(const modint a) const { return (modint)*this /= a; }
  bool operator==(const modint &p) const { return val == p.val; }
  bool operator!=(const modint &p) const { return val != p.val; }
  friend ostream &operator<<(ostream &os, const modint &p) { return os << p.val; }
  friend istream &operator>>(istream &is, modint &a) { long long t; is >> t; a = modint(t); return (is); }
};

int N,K;
int a[100];
modint dp[101][100001];
modint csum[100001];

signed main() {
  cin >> N >> K;
  for(int i=0; i<N; i++) cin >> a[i];

  for(int n=0; n<=N; n++) dp[n][0] = 1;

  //for(int n=1; n<=N; n++)
  //  for(int k=1; k<=K; k++)
  //    for(int c=max(k-a[n-1], 0); c<=k; c++)
  //      dp[n][k] += dp[n-1][c];

  for(int n=1; n<=N; n++) {
    csum[0] = 0;
    for(int k=1; k<=K+1; k++) csum[k] = csum[k-1] + dp[n-1][k-1];
    for(int k=1; k<=K; k++) dp[n][k] = csum[k+1] - csum[max(k-a[n-1],0)];
  }
  cout << dp[N][K] << endl;
}

Measured memory_bytes: 80000
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int N;
int L[1 << 18], R[1 << 18];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int p1, p2; cin >> p1 >> p2;
		L[i] = p1 - p2;
		R[i] = p1 + p2;
		Q.push(make_pair(R[i], i));
	}

	int cx = -(1 << 30), ans = 0;
	while (!Q.empty()) {
		cx = Q.top().first; ans++;
		Q.pop();
		while (!Q.empty()) {
			pair<int, int> v1 = Q.top();
			if (L[v1.second] < cx) Q.pop();
			else break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1912
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

using static Input;
using static Util;
class Program
{
    static int N;
    static int[] A;
    static void INPUT()
    {
        N = NextInt();
        A = LineInt();
    }

    static void OUT()
    {
        var al = new long[N + 1];
        var ar = new long[N + 1];
        for (var n = 0; n < N; n++)
        {
            var l = n - A[n];
            var r = n + A[n];
            if (l >= 0 && l < N)
                al[l]++;
            if (r >= 0 && r < N)
                ar[r]++;
        }

        var count = 0L;
        for (var n = 0; n < N; n++)
        {
            count += al[n] * ar[n];
        }

        Console.WriteLine(count);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{

}




Measured memory_bytes: 44368
from math import sqrt,floor
N,M =map(int,input().split())
ans = 1
for g in range(1,floor(sqrt(M))+1):
    if M%g == 0:
        x = M//g
        if x > floor(sqrt(M)) and g >= N:
            ans = x
            break
        if x >= N:
            ans = g
print(ans)

Measured memory_bytes: 9104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e9+7;
int main(){
	ll n,k;
	cin >> n >> k;
	ll m=(((k+1)*k)/2)%N;
	ll p =((k*(k-1))/2)%N;
	ll a[n];
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	ll cnt = 0;
	for(int i=0;i<n;i++){
		ll sum=0;
		ll ans=0;
		for(int j=i+1;j<n;j++){
			if(a[i]>a[j])sum++;
		} 
		sum%=N;
		cnt+=(sum*(m%N))%N;
		for(int j=i-1;j>=0;j--){
			if(a[i]>a[j])ans++;
		}
		ans%=N;
		cnt+=(ans*(p%N))%N;
	}
	cout << cnt%N << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;}
#define all(x) (x).begin(),(x).end()
#define debug(x)  cerr << #x << " = " << (x) << endl;

template<typename Monoid,typename F>
class SegmentTree{
private:
    int sz;
    vector<Monoid> seg;
    const F op;
    const Monoid e;
public:
    SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){
        sz = 1;
        while(sz<=n) sz <<= 1;
        seg.assign(2*sz,e);
    }
    void set(int k, const Monoid &x){
        seg[k+sz] = x;
    }
    void build(){
        for(int i=sz-1;i>0;i--){
            seg[i] = op(seg[2*i],seg[2*i+1]);
        }
    }
    void update(int k,const Monoid &x){
        k += sz;
        seg[k] = max(seg[k],x);
        while(k>>=1){
            seg[k] = op(seg[2*k],seg[2*k+1]);
        }
    }
    Monoid query(int l,int r){
        Monoid L = e,R = e;
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1) L = op(L,seg[l++]);
            if(r&1) R = op(seg[--r],R);
        }
        return op(L,R);
    }
    Monoid operator[](const int &k)const{
        return seg[k+sz];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    int M = 300001;
    SegmentTree seg(M,[](int a,int b){return max(a,b);},0);
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        int l = max(0,a-K),r = min(M-1,a+K);
        seg.update(a,seg.query(l,r+1)+1);
    }
    cout << seg.query(0,M) << "\n";
}

Measured memory_bytes: 7420