akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ALimitedInsertion solver = new ALimitedInsertion();
        solver.solve(1, in, out);
        out.close();
    }

    static class ALimitedInsertion {

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                a.add(in.nextInt());
            }
            int[] ans = new int[n];
            for (int t = n - 1; t >= 0; t--) {
                boolean found = false;
                for (int i = a.size() - 1; i >= 0; i--) {
                    if (a.get(i) == i + 1) {
                        ans[t] = a.get(i);
                        a.remove(i);
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    out.println(-1);
                    return;
                }
            }
            for (int i = 0; i < n; i++) {
                out.print(ans[i]);
                out.print(' ');
            }
        }
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}



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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll K, A, B;

signed main()
{
    cin >> K >> A >> B;
    if(B - A <= 2) {
        printf("%lld\n", K + 1);
        return 0;
    }
    // とりあえず A まで貯める
    ll remain = K;
    ll cur = 1;
    remain -= (A - cur);
    cur = A;
    if(remain <= 0) {
        printf("%lld\n", K + 1);
        return 0;
    }
    // あとはひたすら変換する
    ll ans = 0;
    if(remain % 2 == 0) {
        ans = (B - A) * (remain /2) + A;
    }
    else {
        ans = (B - A) * (remain / 2) + 1 + A;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define abdelrahman010 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int N = 2e3 + 5;

int main() {
    abdelrahman010
    char c;
    cin >> c;
    if(c >= 'A' && c <= 'Z')
        cout << 'A';
    else
        cout << 'a';
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll n;
  in(n);
  vector<ll> a(n);
  rep(i, n)
    in(a[i]);
  sort(all(a));
  out(a[n - 1] - a[0]);
  memi;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define ll long long
#define SZ(x) ((int)(x).size()) 
#define ALL(v) (v).begin(), (v).end()
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i) 
#define REP(i,a,n) for ( int i=a; i<(n); ++ i )
#define FOR(i,a,n) for ( int i=n-1; i>= int(a);i-- )
#define lson rt<<1, L, m
#define rson rt<<1|1, m, R
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define fi first
#define se second
#define CLR(a, b) memset(a, b, sizeof(a))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

ll n, s;

bool ok(ll b){
    if(b < 2) return false;
    ll x = n;
    ll sum = 0;
    while(x){
        sum += x % b;
        x /= b;
    }
    return sum == s;
}
int main(){
#ifdef ac
	freopen("in.txt","r",stdin);
#endif
	//freopen("out.txt","w",stdout);
    scanf("%lld%lld", &n, &s);
    ll sn = sqrt(n);
    REP(i, 2, sqrt(n) + 1){
        if(ok(i)){
            printf("%d\n", i);
            return 0;
        }
    }
    FOR(q, 1, sqrt(n)){
        if((n - s + q) % q == 0){
            if(ok((n - s + q) / q)){
                printf("%lld\n", (n - s) / q + 1);
                return 0;
            }
        }
    }
    if(n == s){
        printf("%lld\n", n + 1);
        return 0;
    }
    puts("-1");
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] h = new int[n];

        int ans = 1;
        boolean flg = true;

        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) {
            flg = true;
            for (int j = 0; j < i; j++) {
                if (h[i] < h[j]) {
                    flg = false;
                    break;
                }
            }
            if (flg) {
                ans++;
            }
        }

        sc.close();

        System.out.println(ans);
    }

}

Measured memory_bytes: 23252
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
  let x: isize = read();
  let mut ans = (0, 0);
  for a in -1000..=1000 {
    for b in -1000..=1000 {
      if pow(a, 5) - pow(b, 5) == x {
         ans = (a, b);
      }
    } 
  }

  println!("{} {}", ans.0, ans.1);
}


fn pow(x: isize, n: usize) -> isize {
  let mut res = 1;
  for i in 0..n {
    res *= x;
  }
  res
}


Measured memory_bytes: 2148
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_V 100
#define INF 1e9
using namespace std;
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;
void dijkstra(int s)
{
	for (int i = 0; i < MAX_V; i++)

	{
		d[i] = INF;
		used[i] = false;
	}
	d[s] = 0;

	while (true)
	{
		int v = -1;
		for (int u = 0; u < V; u++)
		{
			if (!used[u] && (v == -1 || d[u] < d[v]))
			{
				v = u;
			}
		}
		if (v == -1)
		{
			break;
		}
		used[v] = true;

		for (int u = 0; u < V; u++)
		{
			d[u] = min(d[u], d[v] + cost[v][u]);
		}


	}
}
int main()
{

	for (int i = 0; i < MAX_V; i++)
	{
		for (int j = 0; j < MAX_V; j++)
		{
			cost[i][j] = INF;
		}
	}
	cin >> V;
	for (int i = 0; i < V; i++)
	{
		int u;
		cin >> u;
		int k;
		cin >>  k;
		for (int j = 0; j < k; j++)

		{
			int v;
			cin >> v;
			int c;
			cin >> c;
			cost[u][v] = c;

		}
	}

	dijkstra(0);

	for (int i = 0; i < V; i++)
	{
		cout << i << " " <<d[i]<< endl;
	}
	return 0;

}


Measured memory_bytes: 3136
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <tuple>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define repi(m, itr) for (auto itr = m.begin();itr != m.end();++itr)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// D - 2017-like Number
int Q;
vector<int> primes;


std::vector<int> MakePrime(int n) {
  std::vector<int> prime;
  prime.emplace_back(2);
  for (int i = 3; i <= n; i += 2) {
    bool a = false;
    for (int j = 3; j <= std::sqrt(i); j += 2) {
      if (i%j == 0) {
        a = true;
      }
    }
    if (a == false) {
      prime.emplace_back(i);
    }
  }
  return prime;
}

int main(){
    cin >> Q;

    primes = MakePrime(100000);

    vector<int> oknum;
    rep(i, 3, 100000){
        if(i%2 == 0) continue;
        if(binary_search(primes.begin(), primes.end(), i) && binary_search(primes.begin(), primes.end(), (i+1)/2)){
            oknum.push_back(i);
        }
    }

    rep(i, 0, Q){
        int ans=0;
        int l, r;
        cin >> l >> r;
        vector<int>::iterator lx, rx;
        lx = lower_bound(oknum.begin(), oknum.end(), l);
        rx = upper_bound(oknum.begin(), oknum.end(), r);
        ans = rx - lx;

        cout << ans << endl;
    }

    return 0;
}




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

using namespace std;

long long n,m,ps[3][2069][2069];
bool a[3][2069][2069];

long long pf(long long it,long long y1,long long x1,long long y2,long long x2)
{
	return ps[it][y2][x2]-ps[it][y1-1][x2]-ps[it][y2][x1-1]+ps[it][y1-1][x1-1];
}

int main()
{
	long long i,j,t,rr,it,y1,x1,y2,x2;
	string s;
	
	scanf("%lld%lld%lld",&n,&m,&t);
	for(i=1;i<=n;i++)
	{
		cin>>s;
		for(j=1;j<=m;j++)
		{
			a[0][i][j]=s[j-1]-'0';
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[0][i][j])
			{
				if(a[0][i-1][j])
				{
					a[1][i][j]=1;
				}
				if(a[0][i][j-1])
				{
					a[2][i][j]=1;
				}
			}
			for(it=0;it<3;it++)
			{
				ps[it][i][j]=ps[it][i-1][j]+ps[it][i][j-1]-ps[it][i-1][j-1]+a[it][i][j];
			}
		}
	}
	for(rr=0;rr<t;rr++)
	{
		scanf("%lld%lld%lld%lld",&y1,&x1,&y2,&x2);
		printf("%lld\n",pf(0,y1,x1,y2,x2)-pf(1,y1+1,x1,y2,x2)-pf(2,y1,x1+1,y2,x2));
	}
}

Measured memory_bytes: 114304
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

using namespace std;
using P = pair<int, int>;
using T = tuple<int, int, int>;

long long MOD = 1000000007;
long long dp[100005][4];

P channel[30];

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {

	int A, B;
	cin >> A >> B;

	int tap = 1;
	int count = 0;
	while (tap < B) {
		tap--;
		tap += A;
		count++;
	}

	cout << count << endl;
}


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

int main() {
	
	int H, W;

	for (int k = 0;; k++) {

		cin >> H >> W;

		if (H == 0 || W == 0)break;

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (i == 0 || i == H - 1 || j == 0 || j == W - 1) {
					cout << "#";
				}
				else {
					cout << ".";
				}
			}
			cout << "\n";
		}
		cout << "\n";
	}

	return 0;

}

Measured memory_bytes: 1124
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<cmath>

using namespace std;

typedef long long ll;
#define INF 1000000007

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

    vector<int> dp(100100, INF);
    dp[0] = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }
    cout << dp[n - 1] << "\n";    
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
using namespace std;
int main()
{
    int n,m,A,B;
    cin>>n>>m>>A>>B;
    if(A*2>m||B*2>n)return puts("-1"),0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(i<=B&&j<=A)putchar('1');
        else if(i>B&&j>A)putchar('1');
        else putchar('0');
        if(j==m)puts("");
    }

    return 0;
}


Measured memory_bytes: 3636
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
Ans = 10**10
A = [[10**10 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    A[a-1][b-1] = c
    A[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k]+A[k][j])
P = list(permutations(r))
for p in P:
    d = 0
    for i in range(R-1):
        d += A[p[i]-1][p[i+1]-1]
    Ans = min(Ans,d)
print(Ans)

Measured memory_bytes: 55128
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
typedef long long ll;
using namespace std;
//#define int long long

//素数判定
inline bool IsPrime(int p) {
	if (p == 1) return false;
	for (int i = 2; i <= sqrt(p); i++) {
		if (p%i == 0) return false;
	}
	return true;
}

//10進数の自然数の桁数を返す
inline int GetDigit(int num) {
	return (int)log10(num) + 1;
}

//各位の和を返す
int GetDigitsSum(int num) {
	int N = 0;
	while (num > 0) {
		N += num % 10;
		num /= 10;
	}
	return N;
}

//互除法
ll gcd(ll a, ll b) {
	if (a < b) {
		return gcd(b, a);
	}
	else if (a%b) {
		return gcd(b, a%b);
	}
	else {
		return b;
	}
}

//異なるn個からr個の整数を取り出す組合せの数を求める
int combination(int n, int r) {
	if (r == 0 || n == r) {
		return 1;
	}
	else if (r == 1) {
		return n;
	}
	else {
		return combination(n - 1, r - 1) + combination(n - 1, r);
	}

}

//Ｏ(√n)
//素因数分解
map<int, int> prime_factor(int n) {
	map<int, int> res; // map[i]:=ｎを素因数分解したときiは何乗か。
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0) {
				res[i]++;
				n /= i;
			}
		}
	}
	if (n != 1)
		res[n] = 1;
	return res;
}


int N;
int miny = 10000000;
void Yen(int now, int cnt) {
	if (now == N) {
		//cout << cnt << endl;
		if (miny > cnt) {
			miny = cnt;
		}
	}
	if (now > N) {
		return;
	}
	if (N - now < 6) {
		Yen(now + 1, cnt + 1);
	}
	else {
		for (int i = 1; i <= 7; i++)
		{
			int tmp = pow(6, i);
			if (N - (tmp + now) < 0) {
				Yen(now + pow(6, i-1), cnt + 1);
				break;
			}
		}
		for (int i = 1; i <= 6; i++)
		{
			int tmp = pow(9, i);
			if (N - (tmp + now) < 0) {
				Yen(now + pow(9, i - 1), cnt + 1);
				break;
			}
		}
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	Yen(0, 0);
	cout << miny << endl;

	return 0;
}

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

const string YES = "Yes";
const string NO = "No";

bool contains(long long x,vector<long long>&b)
{
    return find(b.begin(),b.end(),x)!=b.end();
}
void solve(std::vector<std::vector<long long>> a, long long N, std::vector<long long> b){
    for(int i=0;i<3;++i)
    {
        if(contains(a[i][0],b)&&contains(a[i][1],b)&&contains(a[i][2],b)){
            cout<<YES<<endl;
            return;
        }
        if(contains(a[0][i],b)&&contains(a[1][i],b)&&contains(a[2][i],b)){
            cout<<YES<<endl;
            return;
        }
    }
    if(contains(a[0][0],b)&&contains(a[1][1],b)&&contains(a[2][2],b))
    {
        cout<<YES<<endl;
        return;
    }
    if(contains(a[2][0],b)&&contains(a[1][1],b)&&contains(a[0][2],b))
    {
        cout<<YES<<endl;
        return;
    }
    cout<<NO<<endl;
}

int main(){
    std::vector<std::vector<long long>> A(3, std::vector<long long>(3));
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    long long N;
    scanf("%lld",&N);
    std::vector<long long> b(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&b[i]);
    }
    solve(std::move(A), N, std::move(b));
    return 0;
}


Measured memory_bytes: 256
n=int(input())

d=[]
for _ in range(n):
    x,y=map(int,input().split())

    d.append((x,y))

cnt=0
for (x,y) in d:
    if x==y:
        cnt+=1
    else:
        cnt=0
    
    if cnt==3:
        print("Yes")
        exit()
print("No")


Measured memory_bytes: 62384
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1e9
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
#define FOR(i,k,n) for(int i=k;i<n+k;i++)
#define ALL(x) x.begin(),x.end()

int main(){
	int n,m;cin>>n>>m;
	if(n==m) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll mod = 1e9 + 7;

const int maxn = 1e5;

int main() {
  int n;
  cin >> n;
  ll sum = 0;
  for (int i = 1; i <= (int)maxn; i++) {
    sum += i;
    if (sum >= n) {
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3584
#include<map>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a,b,len;
int main(){
	cin>>a>>b;
	int x=b;
	while(x){
		len++;
		x/=10;
	}
	a=a*pow(10,len)+b;
	if(sqrt(a)==(int)sqrt(a))puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    while(1){
        int n;
        cin >> n;
        if(n == 0)break;
        vector<pair<int,char>> c(26);
        vector<char> IN(n);
        rep(i,n)cin >> IN[i];
        rep(i,26)c[i] = MP(0,i+'A');
        int flag = 0;

        rep(j,n){
            char in = IN[j];
            rep(i,26)if(c[i].se == in)c[i].fi++;
            sort(c.begin(),c.end());
            //cerr << j << ": (" << c[25].se << "," << c[25].fi << ") (" << c[24].se << "," << c[24].fi << ")" << endl;
            if(c[25].fi > c[24].fi + n-j-1){
                char ans_c = c[25].se;
                cout << ans_c << " " << j+1 << endl;
                flag = 1;
                break;
            }
        }
    
        if(flag == 0)cout << "TIE" << endl;
    }
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc133.contest.atcoder.jp/tasks/abc133_b


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

ll dp[3005][3005];

ll solve(ll a[], int start, int end, bool isfirst){
	if(start > end)
		return 0;
		
	if(start==end)
		return a[start];
	
	if(start+1 == end) {
		if(isfirst || true)
			return max(a[start], a[end]);
		else
			return min(a[start], a[end]);
	}
	
	if(dp[start][end] != -1)
		return dp[start][end];
	
	ll ans=0;	
	
	ans=max( a[start] + min( solve(a, start+2, end, false), solve(a, start+1, end-1, false) ) , a[end] + min( solve(a, start+1, end-1, false), solve(a, start, end-2, false) ) );
	
	return dp[start][end] = ans;
}

void solve(){
	int n;
	cin >> n;
	
	ll a[n]={};
	long long int tot=0;
	
	for(int i=0; i<n; i++) {
		cin >> a[i];
		tot+=a[i];
	}
		
	
	memset(dp, -1, sizeof dp);
			
	// [X-Y] maximize means max X, minimize means min X
	
	ll x = solve(a, 0, n-1, true);
	ll y = tot-x;
	
	cout << x-y << "\n";
}

int main(){
	solve();
}


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

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

template <typename T, const T& merge(const T&, const T&)>
class SegmentTree {
  const int n;
  const T id;
  vector<T> data;
  T sub(int l, int r, int node, int lb, int ub) {
    if (ub <= l || r <= lb) return id;
    if (l <= lb && ub <= r) return data[node];
    T vl = sub(l, r, node * 2 + 0, lb, (lb + ub) / 2);
    T vr = sub(l, r, node * 2 + 1, (lb + ub) / 2, ub);
    return merge(vl, vr);
  }
  int size(int n) {
    return n == 1 ? n : size((n + 1) / 2) * 2;
  }
public:
  SegmentTree(int m, T id) : n(size(m)), id(id), data(n * 2, id) {}
  void update(int p, T val) {
    assert (0 <= p && p < n);
    p += n;
    data[p] = val;
    while (p /= 2) {
      int l = p * 2, r = p * 2 + 1;
      data[p] = merge(data[l], data[r]);
    }
  }
  T find(int l, int r) {
    return sub(l, r, 1, 0, n);
  }
};

int N;
int a[256000];

template<typename T>
ll dfs(T &seg, int l, int r) {
  if (l == r) return 0;
  int p, val;
  tie(val, p) = seg.find(l, r);
  ll lp = p - l + 1, rp = r - p;
  if (rp < lp) swap(lp, rp);
  ll res = lp * (lp - 1) + (rp - lp + 1) * lp;
  res *= val;
  // cout << l << " " << r << " " << lp << " " << res << endl;
  res += dfs(seg, l, p);
  res += dfs(seg, p + 1, r);
  return res;
}

int main() {
  int N;
  scanf("%d", &N);
  SegmentTree<pair<int,int>,min> seg(N, make_pair(N, N));
  REP(i,N) scanf("%d", a + i);
  REP(i,N) seg.update(i, make_pair(a[i], i));
  cout << dfs(seg, 0, N) << endl;
  return 0;
}


Measured memory_bytes: 86400
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;

int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	int n, k;
	string s;
	cin >> n >> k >> s;
	int cnt = 1;
	for(int i=1; i<n; i++)
		if(s[i-1]!=s[i]) cnt++;
	cnt = max(1, cnt-2*k);
	cout << n - cnt << '\n';
	return 0;
}


Measured memory_bytes: 512
#define MOD_TYPE 1

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
/*
#include <boost/multiprecision/cpp_int.hpp>
using multiInt = boost::multiprecision::cpp_int;
*/
/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
*/
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

inline void init_main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
}
template <typename T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}
#pragma endregion

int main()
{
  init_main();

  int n;
  cin >> n;
  int k = -1;
  rep(i, 1010)
  {
    if (i * (i - 1) == 2 * n)
    {
      k = i;
      break;
    }
  }
  if (k == -1)
  {
    Yes(0);
    return 0;
  }
  Yes(1);
  vector<int> v[100010];
  int num = 1;
  rep(i, k) REP(j, i + 1, k)
  {
    v[i].push_back(num);
    v[j].push_back(num);
    num++;
  }
  cout << k << endl;
  rep(i, k)
  {
    cout << v[i].size() << " ";
    rep(j, v[i].size()) cout << v[i][j] << (j == (int)v[i].size() - 1 ? "\n" : " ");
  }

  return 0;
}


Measured memory_bytes: 4736
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
ll A,B,C,D;
ll n;
int t;
map<ll,ll> mp,vis;
ll getans(ll x)
{
	if(mp.count(x)) return mp[x];
	if(vis.count(x)) return 1e18;
	vis[x]=1;
	if(!x) return 0;
	ll ans=(1.0*x*D<=1e18?x*D:1e18);
	//printf("x=%lld,ans=%lld\n",x,ans);
	for(ll i=x;;i--)
		if(i%2==0)
		{
			ans=min(ans,(x-i)*D+A+getans(i/2));
			break;
		}
	for(ll i=x;;i++)
		if(i%2==0)
		{
			ans=min(ans,(i-x)*D+A+getans(i/2));
			break;
		}
	for(ll i=x;;i--)
		if(i%3==0)
		{
			ans=min(ans,(x-i)*D+B+getans(i/3));
			break;
		}
	for(ll i=x;;i++)
		if(i%3==0)
		{
			ans=min(ans,(i-x)*D+B+getans(i/3));
			break;
		}
	for(ll i=x;;i--)
		if(i%5==0)
		{
			ans=min(ans,(x-i)*D+C+getans(i/5));
			break;
		}
	for(ll i=x;;i++)
		if(i%5==0)
		{
			ans=min(ans,(i-x)*D+C+getans(i/5));
			break;
		}
	vis.erase(x);
	return mp[x]=ans;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		mp.clear();
		scanf("%lld%lld%lld%lld%lld",&n,&A,&B,&C,&D);
		printf("%lld\n",getans(n));
	}
	return 0;
} 

Measured memory_bytes: 4032
#include<iostream>
using namespace std;
int main(){
  int n,min=-1;
  cin >> n;
  int s[n];
  for(int i=0;i<n;i++){
    cin >> s[i];
    if(min<0||min>s[i]) min = s[i];
  }
  for(int i=1;i<=min;i++){
    if(n==2&&s[0]%i==0&&s[1]%i==0) cout << i << endl;
    else if(n==3&&s[0]%i==0&&s[1]%i==0&&s[2]%i==0) cout << i << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    string A;
    cin >> A;

    int n = A.size();

    vector<int> next(26, 0);
    vector<vector<int>> np(n + 2, vector<int>(26, 0));
    REP(i, 26) np[n][i] = next[i] = n + 1;

    vector<int> dp(n + 2);
    REV(i, n, 0) {
        int tmp = INF;
        REP(j, 26) {
            np[i][j] = next[j];
            int pos = next[j];
            int v = dp[pos];
            if (v < tmp) {
                tmp = v;
            }
        }
        dp[i] = tmp + 1;
        if (i > 0) next[A[i - 1] - 'a'] = i;
    }

    int cur = 0;
    string ans;
    while (cur < n + 1) {
        REP(j, 26) {
            int pos = np[cur][j];
            if (dp[cur] - 1 == dp[pos]) {
                ans += ('a' + j);
                cur = pos;
                break;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 50452
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

vector<long long> A;
int N;
int main()
{

	while (cin >> N) {
		A.resize(N);
		for (int i = 0; i < N; ++i) cin >> A[i];

		/*******************************/
		long long all = 0;
		map<long long, long long> mp;
		mp[all]++;
		for (int i = 0; i < N; i++)
		{
			all += A[i];
			mp[all]++;
		}
		/*****************************/
		long long res = 0;
		map<long long, long long>::iterator it;
		for (it = mp.begin(); it != mp.end(); it++)
		{
			res += (it->second - 1) * it->second / 2;
		}
		/*********************************/
		//printf("%lld\n", res);
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 14336
class Integer
  def combination(k)
    return 1 if k.zero?

    (self - k + 1..self).inject(:*) / k.factorial
  end

  def permutation(k)
    return 1 if k.zero?

    (self - k + 1..self).inject(:*)
  end

  def factorial
    return 1 if self.zero?

    (1..self).inject(:*)
  end
end

N, M = gets.split.map &:to_i
p N.combination(2)+M.combination(2)

Measured memory_bytes: 1788
#include <bits/stdc++.h> 
#include <bits/types/stack_t.h>
using namespace std; 
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI1 3.14159265358979311599796346854418516159057617187500

typedef long long int ll;  

int main() 
{ 
    FIO
    ll t;
    //cin >> t;
    t=1;
    while(t--)
    {
        string s;
        cin >> s;

        if(s=="ARC")
            cout << "ABC" << endl;
        else
            cout << "ARC" << endl;
    }
    return 0; 
} 


Measured memory_bytes: 3652
import Data.Bits
import Data.List
import Control.Monad
import qualified Data.Vector.Unboxed as V
import Control.Monad.ST
import Data.Maybe (fromMaybe)
import qualified Data.ByteString.Lazy.Char8 as B
--import Debug.Trace

main :: IO ()
main = do
  n <- readLn :: IO Int
  as <- replicateM n $ readLn :: IO [Int]
  let ls = V.fromList $ scanl1 max as
      rs = V.fromList $  scanr1 max as

  print $ (rs V.! 1)
  forM_ [2..n-1] $ \i -> do
    print $ max (ls V.! (i-2)) (rs V.! i)
  print $ (ls V.! (n-2))


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

int main(void){
    int a,b,c;
    cin >> a >> b >> c;
    string ans = (a<=c && c<=b)?"Yes":"No";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
let is_prime = Array.make 55556 true
let primes = begin
  is_prime.(0) <- false; is_prime.(1) <- false;
  for i = 2 to 55555 do
    if is_prime.(i) then begin
      for j = i to 55555 / i do
        is_prime.(i*j) <- false;
      done
    end
  done;

  Array.mapi (fun i b -> i, b) is_prime
  |> Array.fold_left (fun stk (i, b) -> if b then i::stk else stk) []
  |> List.rev
end

let rec take n xs = if n <= 0 then [] else
  match xs with [] -> [] | x::xs' -> x :: take (n-1) xs'

let () =
  Scanf.scanf "%d" @@ fun g ->
  List.filter (fun x -> x mod 5 = 1) primes
  |> take g |> List.iter (Printf.printf "%d ");
  print_newline ()



Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int BIG = 2e9 + 55;

int n;
string s;
map<pair<string, string>, ll> cnt;

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

    cin >> n;

    cin >> s;

    for(int bitmask0 = 0; bitmask0 < (1 << n); bitmask0++){
        string a = "", b = "";
        for(int i = 0; i < n; i++){
            if(bitmask0 & (1 << i)){
                a.push_back(s[i]);
            } else {
                b.push_back(s[i]);
            }
        }

        cnt[make_pair(a, b)]++;
    }

    ll fRes = 0;
    for(int bitmask = 0; bitmask < (1 << n); bitmask++){
        string a = "", b = "";
        for(int i = n - 1; i >= 0; i--){
            if(bitmask & (1 << i)){
                a.push_back(s[n + i]);
            } else {
                b.push_back(s[n + i]);
            }
        }

        fRes += cnt[make_pair(a, b)];
    }

    cout << fRes << '\n';

    return 0;
}

Measured memory_bytes: 91904
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i)
            arr[i] = in.nextInt();

        int lo = -(int)1e9;
        int hi = (int)1e9;

        while (Math.abs(hi - lo) > 1) {
            int mid1 = lo + (hi - lo + 1) / 3;
            int mid2 = hi - (hi - lo + 1) / 3;

            long sum1 = computeSadness(arr, mid1);
            long sum2 = computeSadness(arr, mid2);

            // System.err.println(lo + " " + mid1 + " " + mid2 + " "+ hi);

            if (sum1 < sum2) hi = mid2;
            else lo = mid1;
        }

        System.out.println(Math.min(computeSadness(arr, lo), computeSadness(arr, hi)));
    }

    private static long computeSadness(int[] arr, int b) {
        long s = 0;
        for (int i = 0; i < arr.length; ++i) {
            s += Math.abs(arr[i] - (b + i + 1));
        }
        return s;
    }
}

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

int main() {
  string  c;
	cin >> c;
  for (int i = 0; i < 3; i++) {
  	if (c[i] == '7')
  		return cout << "Yes" << '\n', 0;
  }
  	cout << "No" << '\n';
 	return 0; 
}


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

using ll = long long int;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

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

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	os << "{";
	rep(i, (int)v.size()) {
		if (i)
			os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
	for (auto val : array)
		std::cout << val << ", ";
	std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

	ll n, k; std::cin >> n >> k;
	vector<ll> a(n); rep(i, n) std::cin >> a[i];
	vector<ll> f(n); rep(i, n) std::cin >> f[i];
	sort(rng(a)), sort(rng(f), greater<ll>());
	ll l = -1, r = 1e12; 
	while(l + 1 < r) {
		ll c = (l + r) / 2;
		ll sum = 0;
		rep(i, n) {
			sum += max(a[i] - c / f[i], 0ll);
		}
		if (sum > k)
			l = c;
		else
			r = c;
	} 
	std::cout << r << "\n";
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n,m; cin>>n>>m;
    vector<ll> a(n), b(n);
    map<ll, vector<ll>> mp;
    rep(i,n) {
        cin>>a[i]>>b[i];
        mp[a[i]].push_back(b[i]);
    }

    priority_queue<ll> pq;
    ll ans = 0;
    for (int i = m-1; i >= 0; --i) {
        int day = m-i;
        for (auto &&e: mp[day]) {
            pq.push(e);
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 12416
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    h, w = LI()
    s = SR(h)
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                q = deque()
                q.append((i, j))
                dist = defaultdict(int)
                dist[q[0]] = 1
                while q:
                    p = q.popleft()
                    dp = dist[p]
                    for mx, my in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        my += p[0]
                        mx += p[1]
                        if 0 <= mx < w and 0 <= my < h:
                            if dist[(my, mx)] or s[my][mx] == "#":
                                continue
                            dist[(my, mx)] = dp + 1
                            q.append((my,mx))
                ans = max(ans, max(dist.values()))
    print(ans-1)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 47068
LIMIT = 2 * 10 ** 5
fac = [0] * (LIMIT + 10)
fac[0] = 1
inv = [0] * (LIMIT + 10)
MOD = 1_000_000_007
n = 1
for i in range(1, LIMIT + 1):
    n *= i
    n %= MOD
    fac[i] = n
inv[LIMIT] = pow(fac[LIMIT], MOD - 2, MOD)
for i in range(LIMIT, -1, -1):
    inv[i - 1] = (inv[i] * i) % MOD
def C(n, r):
    return (fac[n] * inv[n-r] * inv[r]) % MOD

H, W, A, B = map(int, input().split())
ans = 0
B1 = B - 1
WB1 = W - B - 1
for i in range(H - A):
    ans += C(i + B1, B1) * C(H - i - 1 + WB1, WB1)
    ans %= MOD
print(ans)


Measured memory_bytes: 24552
#include <stdio.h>

int main(int argc, char *argv[])
{
    int W, H, x, y, r;

    scanf("%d%d%d%d%d", &W, &H, &x, &y, &r);
    if ((x - r < 0) || (y + r > H) || (y - r < 0) || (x + r > W))
        puts("No");
    else
        puts("Yes");

    return 0;
}


Measured memory_bytes: 2144
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

int N;
ll K, A[200000], F[200000];

const ll INF = 1e+18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> K;
    ll sum = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        sum += A[i];
    }
    for(int i = 0; i < N; i++){
        cin >> F[i];
    }
    sort(A, A+N);
    sort(F, F+N, greater<ll>());
    if(sum <= K){
        cout << 0 << endl;
        return 0;
    }
    ll l = 0;
    ll r = INF;
    while(r-l > 1){
        ll c = (l+r)/2;
        ll cnt = 0;
        for(int i = 0; i < N; i++){
            ll m = c/F[i];
            if(A[i] > m) cnt += A[i]-m; 
        }
        if(cnt > K) l = c;
        else r = c;
    }
    cout << r << endl;
}

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

int main(void){
  int H,A,ans;
  if(scanf("%d %d",&H,&A)>2){
    printf("error");
   exit(0);
  }
  ans=H/A;
  if(H%A>0.5)ans++;
  printf("%d",ans);
  return 0;
}


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

int main() {
  int N,K;
  cin >> N>>K;
  vector<int>A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  sort(A.begin(),A.end());
  vector<int>B(0);
 
 
 
  int a=1;
  for(int i=0;i<N-1;i++){  
       
    if(A.at(i)==A.at(i+1)){
      a++;
    }
    else{     
      B.push_back(a);
      a=1; 
    }    
  }
  B.push_back(a);
  sort(B.begin(),B.end());
  
  if(B.size()<=K){
    cout<<0<<endl;
  }
  else{
    int ans=0;
    for(int i=0;i<B.size()-K;i++){
      ans+=B.at(i);
    }  
    cout <<  ans<< endl;
  }
}



Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define IOS  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mp    make_pair
#define pb    push_back
#define F     first
#define pi 	  3.14159265358979323846
#define S     second
#define ll    long long
#define ld    long double
#define sz(s) (ll)s.size() 
#define vl    vector < ll >
#define pll   pair < ll, ll >
#define ml    map < ll, ll >
#define mod   1000000007
#define MAXN  50005 
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define inv(i,a,b)  for(ll i=a;i>=b;i--)
#define all(a)  (a).begin(),(a).end()
using namespace std;
int main(){
	IOS;
	ll n,i,ans;
	n=5;
  	ll a[n];
  	rep(i,0,n){cin>>a[i];if(a[i]==0)ans=i+1;}
  	cout<<ans;
}

Measured memory_bytes: 3636
#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    string ans = ":(";

    for(int i = 1; i <= 50000; i++){
        if((int) (i  * 1.08) == n){
            ans = to_string(i);
            break;
        }
    }

    cout << ans << endl;

}       

Measured memory_bytes: 3648
#include <bits/stdc++.h> 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vll>;
using vb = vector<bool>;
 
const int INF = 2e9+5;
const ll LLINF = (1LL << 60) + 5;
 
/*
  filippos
  Contest : AtCoder DP contest
  Task : J - Sushi
*/
 
ll pack(int a, int b, int c){
  return a + b*301 + c*301*301;
}

array<int, 3> unpack(int x){
  return array<int, 3>{x % 301, x / 301 % 301, x / (301 * 301)};
}

int main(){
  cin.tie(0), cin.sync_with_stdio(0), cout.tie(0), cout.sync_with_stdio(0);

  int n; cin >> n;

  vi v(4);
  for(int i = 0; i < n; i++){
    int x; cin >> x;
    v[x]++;
  }

  unordered_map<int, double> memo;
  function<double(int)> dp = [&](int status){
    // base case
    if(!status) return 0.0;
    // memoization
    if(memo.count(status)) return memo[status];
    double &ans = memo[status];

    // to be used as {3s, 2s, 1s}
    auto vals = unpack(status);
    // cout << status << ' ' << vals[0] << ' ' << vals[1] << ' ' << vals[2] << '\n';

    int empty = n - vals[0] - vals[1] - vals[2];

    // compute value excluding recurrency
    ans = 1.0;
    if(vals[0]) ans += (vals[0] * 1.0 / n) * dp(pack(vals[0] -1, vals[1] + 1, vals[2]));
    if(vals[1]) ans += (vals[1] * 1.0 / n) * dp(pack(vals[0], vals[1] - 1, vals[2] + 1));
    if(vals[2]) ans += (vals[2] * 1.0 / n) * dp(pack(vals[0], vals[1], vals[2] - 1));
    // derived from some equation, it should make sense
    if(empty) ans *= n * 1.0 / (n - empty);
    return ans;
  };

  cout << fixed << setprecision(15);
  cout << dp(pack(v[3], v[2], v[1]));

  return cout << endl, 0;
}

Measured memory_bytes: 239704
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
def inpl(): return list(map(int, input().split()))

#### START
S = input()
K = int(input())

f = False
for s in S[:K]:
  if s != "1":
    print(s)
    f = True
    break

if not f:
  print(1)




Measured memory_bytes: 3316
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const ll inf = (ll)(1e18);

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, t;
  cin >> n >> t;
  vector <int> a(n), b(n);
  vector <int> ord;
  vector <pair <int, int> > ot;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    b[i] += a[i];
    a[i]++, b[i]++;
    if (a[i] == 1) {
      ord.push_back(b[i]);
    } else {
      ot.push_back({a[i], b[i]});
    }
  }
  sort(ord.begin(), ord.end());
  sort(ot.begin(), ot.end(), [&] (pair <int, int> a, pair <int, int> b) {
    return b.first * (ll) a.second + b.second < a.first * (ll) b.second + a.second;
  });
  vector <ll> dp(51, inf);
  dp[0] = 0;
  auto f = [&] (ll t, ll a, ll b) {
    return a * t + b;
  };
  for (int i= 0; i < (int) ot.size(); i++) {
    for (int j = min(i, 49); j >= 0; j--) {
      if (dp[j] <= t)
        dp[j + 1] = min(dp[j + 1], f(dp[j], ot[i].first, ot[i].second));
    }
  }
  int ok = 0;
  for (int x = 0; x <= 50; x++) {
    ll ans = dp[x];
    if (ans > t) continue;
    int ret = x;
    for (int j = 0; j < (int) ord.size(); j++) {
      if (ans + ord[j] <= t) {
        ans += ord[j];
        ret++;
      }
    }
    ok = max(ok ,ret);
  }
  cout << ok << endl;
}


Measured memory_bytes: 3956