akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#define mid ((l+r)>>1)
#define read(n) scanf("%lld",&n)
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
ll a[MAXN] ,  binary[MAXN];
ll pre[MAXN];
ll b[MAXN];
ll ans;
ll n;
void merge(ll *p,int l,int r)
{
	if(l == r)	return ;
	merge(p,l,mid);
	merge(p,mid+1,r);
	int tot = l;
	int pos1 = l , pos2 = mid + 1;
	while(pos1 <= mid && pos2 <= r)
	{
		if(p[pos1] > p[pos2])
		{
			b[tot++] = p[pos2++];
			ans += mid - pos1 + 1;
		}	
		else
			b[tot++] = p[pos1++];
	}
	while(pos1 <= mid)	b[tot++] = p[pos1++];
	while(pos2 <= r)	b[tot++] = p[pos2++];
	for(int i = l ; i <= r ; i++)
		p[i] = b[i];
}
bool check(ll x)
{
	ans = 0;
	pre[0] = 0;
	for(int i = 1 ; i <= n ; i++)
		pre[i] = pre[i-1] + (x >= a[i] ? -1 : 1) , ans += pre[i] < 0 ? 1 : 0;
	merge(pre,1,n);
	return ans <= (long long)(n * (n + 1) / 4);
}
int main()
{
	read(n);
	for(int i = 1 ; i <= n ; i++)
		read(a[i]) , binary[i] = a[i];
	merge(binary,1,n);
	ans = 0;
	int l = 1 , r = n;
	while(l + 1 < r)
	{
		if(check(binary[mid]))
			l = mid;
		else
			r = mid;
	}
	printf("%d\n",binary[r]); 
}

Measured memory_bytes: 3328
#include <iostream>

bool solve(int i, int m, int n, int A[]);

int main(){
    int n,q;
    std::cin >> n;
    int A[n];
    for(int i=0;i<n;i++){
        std::cin >> A[i];
    }
    std::cin >> q;
    int m[q];
    for(int i=0;i<q;i++){
        std::cin >> m[i];
    }
    for(int i=0;i<q;i++){
        if(solve(0, m[i], n, A)){
            std::cout << "yes\n";
        }else{
            std::cout << "no\n";
        }
    }
}

bool solve(int i, int m, int n, int A[]){
    if(m==0){
        return true;
    }
    if(i>=n){
        return false;
    }
    if(solve(i+1, m, n, A) || solve(i+1, m-A[i], n, A)){
        return true;
    }
    return false;
}


Measured memory_bytes: 3028
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1e18+10;

int main(){

	ll n,w;
	cin >> n >> w;
	ll wt[n],val[n];
	for(ll i=0;i<n;i++){
		cin >> wt[i] >> val[i];
	}

	ll y = n*1000;
	ll dp[y+1];
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(ll i=1;i<=n;i++){
		for(ll j=y;j>=val[i-1];j--){
			dp[j] = min(dp[j],dp[j-val[i-1]]+wt[i-1]);
		}
	}
	ll ans=0;
	for(ll i=0;i<=y;i++){
		if(dp[i]<=w){
			ans = i;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
import math

sc = list(map(float, input().split()))
a = sc[0]
b = sc[1]
c = math.pi * sc[2] / 180

s = a * b * math.sin(c) / 2

print('{:.10f}'.format(s))

print('{:.10f}'.format(a + b + math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(c))))

print('{:.10f}'.format(2 * s / a))


Measured memory_bytes: 5696
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
        StringBuilder str = new StringBuilder();
        int i = 1;
        while (true) {
            int data = Integer.parseInt(br.readLine());
            if (data == 0)
                break;
            str.append("Case ").append(Integer.toString(i)).append(": ")
                .append(Integer.toString(data)).append("\n");
            i++;
        }
        System.out.print(str);
    }
}

Measured memory_bytes: 31348
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

// aのn乗を求める。計算量はO(logn)
ll modpow(ll a, ll n) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 1) {
        return (a * modpow(a, n-1))%mod;
    }
    return (modpow(a, n/2) * modpow(a, n/2))%mod;
}
 
int main() {
    ll n;
    cin >> n;

    vl c(n);
    rep(i, n) {
        cin >> c[i];
    }
    sort(rall(c));

    ll ans = 0;
    rep(i, n) {
        ans += (i+2)*c[i];
        ans %= mod;
    }

    ans *= modpow(4, n-1);
    ans %= mod;
    
    out(ans);
    re0;
}

Measured memory_bytes: 1920
s = input()
n = len(s)-1

total = 0
#digit loop
for b in range(2**n):
    nums = []
    index = 0
    #bit loop / looking for plus location until number of digit
    for i in range(n):
        if ( b & (1 << i) ):
            nums.append(int(s[index:i+1]))
            index = i+1
    nums.append(int(s[index:]))
    total = total + sum(nums)
print(total)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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 gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

#define int ll
void solve()
{
	ll d;
	cin>>d;
	vector<ll>c(26);
	rep(i,26)cin>>c[i];
	vector<vector<ll>>s(d,vector<ll>(26));
	rep(i,d)rep(j,26)cin>>s[i][j];
	vector<ll>t(d);
	rep(i,d)cin>>t[i];
	vector<ll>last(26);
	ll res=0;
	rep(i,d){
		ll maxv=0;
		t[i]--;
		// rep(j,26){
		// 	if(chmax(maxv,s[i][j]))day=j;
		// }
		maxv=s[i][t[i]];
		res+=maxv;
	}
	ll m;
	cin>>m;
	vector<ll>dd(m),q(m);
	rep(i,m){
		cin>>dd[i]>>q[i];
		dd[i]--;q[i]--;
		res-=s[dd[i]][t[dd[i]]];
		res+=s[dd[i]][q[i]];
		ll pre=res;
		// if(res<pre){
		// 	res=pre;
		// }
		t[dd[i]]=q[i];
		rep(k,d){
			last[t[k]]=k+1;
			rep(j,26){
				res-=c[j]*(k+1-last[j]);
			}
		}
		cout<<res<<"\n";
		rep(j,26)last[j]=0;
		res=pre;
	}
}
#undef int
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


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

struct Problem {
    vector<UL> E[100000];
    UL P[100000];
    bool F[100000] = {};
    vector<pair<UL, UL>> ans;
    UL D[100000];

    UL DFS(UL p) {
        F[p] = true;
        UL tmp = D[p];
        for (UL e : E[p]) {
            if (P[p] == e) continue;
            if (F[e]) {
                tmp = min(tmp, D[e]);
            }
            else {
                P[e] = p;
                D[e] = D[p] + 1;
                UL res = DFS(e);
                if (res > D[p]) ans.push_back({ min(p, e), max(p, e) });
                tmp = min(tmp, res);
            }
        }
        return tmp;
    }

    void Solve() {
        UL N, M; scanf("%d%d", &N, &M);
        rep(i, M) {
            UL u, v; scanf("%d%d", &u, &v);
            if (u > v)swap(u, v);
            E[u].push_back(v);
            E[v].push_back(u);
        }
        D[0] = 0;
        DFS(0);
        sort(ans.begin(), ans.end());
        for (auto& a : ans) printf("%d %d\n", a.first, a.second);
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    //cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}




Measured memory_bytes: 7396
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rem(i, s, n) for (int i = (s); i >= (n); --i)
using ll = long long;
const int MOD = 1e9+7;

int main(){
    ll n, k; cin >> n >> k;
    vector<ll> p(n); rep(i, 0, n) cin >> p[i];

    vector<double> x(n);
  	rep(i, 0, n) x[i] = ((double) p[i] + 1.0) / 2.0;
    vector<double> s(n+1, 0.0);
    rep(i, 0, n) s[i+1] = s[i] + x[i];
    int L = 0, R = k, l = 0, r = k;
    rep(i, 0, n - k) {
        l++; r++;
        if(s[r] - s[l] > s[R] - s[L]){
            L = l; R = r;
        }
    }
    cout << fixed << setprecision(12) << s[R] - s[L] << endl;

    return 0;
}

Measured memory_bytes: 4992
import numpy as np
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
a=np.array(a)

a2=[]
a3=[]
for i in range(h):
  if "#" in a[i]:
    a2.append(a[i])
a2=np.array(a2)
a2=a2.T

for i in range(len(a2)):
  if "#" in a2[i]:
    a3.append(a2[i])
a3=np.array(a3)
a3=a3.T
for i in range(len(a3)):
  print("".join(a3[i]))

Measured memory_bytes: 27368
import collections
# import math


def resolve():
    N = int(input())
    S = []
    for i in range(N):
        ss = input()
        S.append(ss)

    counter = collections.Counter(S)
    _, max_count = counter.most_common()[0]

    ans = []

    for key in counter:
        if (counter[key] == max_count):
            ans.append(key)

    ans.sort()

    for a in ans:
        print(a)


resolve()


Measured memory_bytes: 45036
require 'set'

def calc_cost(s, g, n, edges)
  q = Set.new (0...n)
  max_cost = 1000 * n
  costs = (0...n).map{max_cost}
  costs[s] = 0

  while ! q.empty?
    u = q.to_a.min{|a, b| costs[a] <=> costs[b]}
    q.delete(u)

    for v in (0...n)
      e = edges[u][v]
      next if e.nil?

      c = costs[u] + e
      costs[v] = c if costs[v] > c
    end
  end

  return costs[g]
end

n = gets.chomp.to_i
m = gets.chomp.to_i

edges = (0...n).map{[]}

m.times.each do
  n0, n1, c1, c2 = gets.chomp.split(",").map{|s| s.to_i}
  n0 -= 1
  n1 -= 1
  edges[n0][n1] = c1
  edges[n1][n0] = c2
end

st, gl, rev, pr = gets.chomp.split(",").map{|s| s.to_i}
st -= 1
gl -= 1

c0 = calc_cost(st, gl, n, edges)
c1 = calc_cost(gl, st, n, edges)
puts rev - (pr + c0 + c1)

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

int main(){
    int X, A, B;
    cin >> X >> A >> B;

    if(B - A > X){
        cout << "dangerous" << endl;
    }else if(B - A <= 0){
        cout << "delicious" << endl;
    } else{
        cout << "safe" << endl;
    }
}


Measured memory_bytes: 3620
#include <stdio.h>
#include <string.h>
#define N 2000
int main(void){
	int n,m,i=0,A[N][2]={0};
	char str[N];

	for( ;fgets(str,sizeof(str),stdin)!=NULL; ){
		if(str[0]=='\n'){
			i++;
			if(i>1)	break;
		}
		else{
			sscanf(str,"%d,%d",&n,&m);
			A[n][i]+=1;
		}
	}
	for(i=1;i<N;i++)
		if(A[i][0] && A[i][1]) printf("%d %d\n",i,A[i][0]+A[i][1]);
	return 0;
}

Measured memory_bytes: 628
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))


ans = 0

while(1):
    for i in range(n):
        if (a[i] % 2 == 0):
            a[i] /= 2
        else:
            print(ans)
            exit()
    ans += 1


print(ans)

Measured memory_bytes: 12396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = b - 1; i >= a; i--)
#define int ll
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

signed main() {
    int x;
    cin >> x;
    if (x >= 30) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

Measured memory_bytes: 3620
//
// author  : Abhishek
//
#include <bits/stdc++.h>

#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)

using namespace std;

const ll mod = 1000000007;
const ll N = 200005;  // array size
const ll inf = 10000000000000000;


void print(vector<ll> v) {
    ll i;
    fo(i, v.size())cout << v[i] << " ";
    cout << "\n";
}

vector<ll> read(ll n) {
    ll i;
    vector<ll> arr(n, 0);
    fo(i, n)cin >> arr[i];
    return arr;
}

vector<ll> read(ll n, ll k) {
    ll i;
    vector<ll> arr(n + k, 0);
    Fo(i, k, n + k)cin >> arr[i];
    return arr;
}

bool isEven(ll n) {
    return n % 2 == 0;
}

bool isOdd(ll n) {
    return n % 2 == 1;
}


void solve() {
    ll t;
    cin >> (t);
    while (t--) {

        ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    }
}

int main() {


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll i, j, k, n, m, q, x, y, a, b, l, r;

    cin >> n >> m;
    vector<ll> adj[m];

    fo(i, m) {
        cin >> k;
        fo(j, k) {
            cin >> x;
            x--;
            adj[i].push_back(x);
        }
    }

    vector<ll> p;
    p = read(m);

    ll mask = 0;

    ll ans = 0;
    for (mask = 0; mask < (1 << n); mask++) {
        bool ok = 1;

        for (i = 0; i < m; i++) {
            ll ct = 0;
            for (auto on : adj[i]) {
//                deb(on);
                if (mask & (1 << on)) {
                    ct++;
                }
            }
            if (ct % 2 != p[i] % 2 ) {
                ok = 0;
            }
        }
        if(ok)
            ans++;
    }
    cout << ans;


    return 0;
}




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

int N;

// bool is_prime(int n) {
//     for (int i = 2; i * i <= n; i++) {
//         if (n % i == 0) return false;
//     }
//     return n != 1;
// }

bool calc(int n) {
    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            num++;
        }
    }

    // printf("n: %d num: %d\n", n, num);

    return num == 8;
}

int main() {
    cin >> N;

    int ans = 0;
    for (int i = 1; i <= N; i += 2) {
        bool tmp = calc(i);
        if (tmp) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

ll a[500500+1];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	int n=s.size();
	ll p=0;
	ll mi=0;
	a[0]=0;
	for(int i=0;i<n;i++){
		if(s[i]=='>'){
			ll cnt=0;
			int cp=i;
			while(i<n&&s[i]=='>'){
				i++;
				cnt++;
			}
			a[cp]=max(a[cp],cnt);
			for(int j=cp+1;j<=i;j++){
				if(j==cp+1){
					a[j]=min(a[j-1]-1,cnt-1);
				}
				else{
					a[j]=a[j-1]-1;
				}
			}
			i--;
		}
		else{
			a[i+1]=a[i]+1;
		}
	}
	ll sum=0;
	for(int i=0;i<=n;i++){
		sum+=a[i];
	}
	cout << sum << endl;
}

Measured memory_bytes: 4764
#include <iostream>
#include <cstdio>
using namespace std;
int main(void) {
  double a[11], s;
  
  while(cin >> a[1]) {
    s = 0;
    for(int i = 2 ; i < 11 ; i++) {
      a[i] = 0;
    }
    for(int i = 2 ; i < 11 ; i++) {
      if(i % 2 == 1) {
	a[i] = a[i-1] / 3;
      }
      else if(i % 2 == 0) {
	a[i] = 2 * a[i-1];
      }
    }
    for(int i = 1 ; i < 11 ; i++) {
      s += a[i];
    }
    printf("%.8f\n", s);
  }
  return 0;
}

Measured memory_bytes: 0
open System

let input1 = stdin.ReadLine().Split(' ')
let input2 = stdin.ReadLine().Split(' ')
//

//------------------------------------------------
let N = input1.[0] |> int
let M = input1.[1] |> int64
let V = input1.[2] |> int
let P = input1.[3] |> int
let A = input2 |> Array.map (fun x -> x |> int64) |> Array.take N


// ２分岐探査によりＯＫの最大インデックスを返す.
let rec searchB ok ng i (a:int64 array) =
    //printfn "ok=%d ng=%d i=%d b=%d, [i]=%d" ok ng i a.[P] a.[i]
    let mid a b = (a+b)/2
    let next o n t =
        let j = mid o n
        //printfn "%s o=%d n=%d j=%d" t o n j
        if (o+1) >= n then o
        else searchB o n j a
    let calc m =
        let r = M*((V-(P-1)-(N-i+1))|>int64)
        let u = [P..(i-1)] |> List.map (fun j -> M-(a.[j]-a.[i])) |> List.sum
        //printfn "m=%d r=%d u=%d" m r u
        if (r <= u) then next i ng "A" else next ok i "B"
    if a.[i] >= a.[P] then next i ng "C"
    else
        let m = a.[i] + M
        if m < a.[P] then next ok i "D" else calc m

let solve =
    let a = Array.concat [ [|-1L|]; (A |> Array.sort |> Array.rev) ]
    let s = searchB 1 (N+1) (N/2) a
    //printfn "s=%d" s
    s

solve |> printfn "%d"

Measured memory_bytes: 88368
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
 
ll mod = 1000000007;
ll modpow(ll a, ll n) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
 
	int N;
	string S;
	cin >> N >> S;
	map<int, int>mp;
	for (int i = 0; i < N; i++)mp[S[i] - 'a']++;
 
	ll ans = 1;
	fore(x,mp) {
		ans *= (x.second+1);
		ans %= mod;
	}
	ans += mod - 1;
	ans %= mod;
	puts(ans);
 
	return 0;
}

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

int main() {
    int n, ans;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h.at(i);
    ans = h.at(0);
    rep(i, n - 1) ans += max(0, h.at(i + 1) - h.at(i));
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;
using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef vector<pii> vii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OrderedSet;

const int MOD	= 1e9 + 7;
const double PI = acos(-1.0);

#define fastio			ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto &i : c)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define fill(a)  memset(a, 0, sizeof (a))
#define error(x) cerr << #x << " = " << (x) << endl
#define errorp(p) cerr << #p << " = " << (p.first) << ", " << (p.second) << endl

template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }
int mul(int a, int b, int c){lli res=(lli)a*b;return (int)(res>=c?res%c:res);}
template<typename T>T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
int mod_neg(int a, int b, int c){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}


int main(){
    
    fastio;
    int N;
    double M;
    cin >> N >> M; 
    vector<double> arr(N);

    double sum = 0;
    rep(i, N){
        cin >> arr[i];
        sum += arr[i];
    }

    sum /= 4 * M;

    int x = 0;
    tr(arr, y){
        if(y >= sum){
            x++;
        }
    }

    if(x >= M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
flg = 0
a[0] -= 1
for i in range(1,n):
  if a[i] >= a[i-1] + 1:
    a[i] -= 1
  elif a[i] < a[i-1]:
    flg = 1
if flg == 1:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 14396
/// Updated! https://www.youtube.com/watch?v=U07_n9xGIlM
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define dbug printf("I am here\n");
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int maxn = 2e5+100;

const ll inf = 1e18;

string s;
int k;
ll dp[200][20][2][2];

ll solve(int i , int p , bool boro, bool st){
    if(i == s.size() and p==0)return 1ll;
    if(i == s.size())return 0;
    if( p < 0 )return 0;
    ll &ret = dp[i][p][boro][st];
    if(ret != -1)return ret;
    ll mx = s[i]-'0';
    if(boro == false)mx = 9;
    ret = 0;
    for(int d = 0; d<=mx; d++){
        ret += solve(i+1,p-(d!=0), boro&(d==mx) , st|d>0);
    }
    return ret;
}

int main()
{
    fast;
    cin >> s >> k;
    memset(dp,-1,sizeof dp);
    cout << solve(0,k,true,false) << endl;
    return 0;
}
/*



*/



Measured memory_bytes: 384
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	string s;
	cin>>s;
	ll n = s.size();
	ll res = n/2;
	rep(i, n) if(s[i]=='p') res--;
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
// #include <string>
// #include <vector>
// #include <map>
// #include <algorithm>

using namespace std;
// typedef unsigned long long ull;


int main(int argc, char const *argv[]) {
    int a, b, c;
    cin >> a;
    cin >> b;
    cin >> c;

    int num;
    if (a == b && b == c && c == a) {
        num = 1;
    } else if ((a == b) || (b == c) || (c == a)) {
        num = 2;
    } else {
        num = 3;
    }
    cout << num << endl;

    return 0;
}


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

int main()
{
	int n, c;
	scanf("%d %d", &n, &c);
	vector<vector<int>> events;
	for (int i = 0; i < n; i++)
	{
		vector<int> t(3);
		for (int j = 0; j < 3; j++)
			scanf("%d", &t[j]);
		events.push_back(t);
	}
	sort(events.begin(), events.end());

	size_t ans = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>> , greater<pair<int, int>>> pq;
	for (int i = 0; i < n; i++)
	{
		while (!pq.empty() && pq.top().first < events[i][0])
			pq.pop();
		vector<pair<int, int>> t;
		while (!pq.empty() && pq.top().first == events[i][0])
		{
			t.push_back(pq.top());
			pq.pop();
			if (t.back().second == events[i][2])
				t.pop_back();
		}
		for (int j = 0; j < t.size(); j++)
			pq.push(t[j]);
		pq.push({events[i][1], events[i][2]});
		ans = max(ans, pq.size());
	}
	printf("%ld\n", ans);

	return 0;
}

Measured memory_bytes: 6708
#include<iostream>
#include<string>
using namespace std;
int n,l=0,r=0,ans;
string s;
int main(void){
	cin>>n>>s;
	for(int i=1;i<n;i++)if(s[i]=='E')r++;
	ans=r;
	for(int i=1;i<n;i++){
		if(s[i-1]=='W')l++;
		if(s[i]=='E')r--;
		ans=min(ans,r+l);
	}
	cout<<ans;
	return 0;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

vector<string> ans;

void rec(int idx, int n, int d, string s) {
  if (idx == n) {
    ans.eb(s);
    return;
  }

  rep(i, d) { rec(idx + 1, n, d + (i + 1 == d), s + char('a' + i)); }
}

int main() {
  int n;
  cin >> n;
  rec(0, n, 1, "");

  sort(all(ans));

  rep(i, ans.size()) cout << ans[i] << "\n";
}


Measured memory_bytes: 7796
#include<stdio.h>
int main()
{
	int n,m,i;
	scanf("%d %d",&n,&m);
	if(n>m)
	{
		for(i=1;i<=n;i++)
			printf("%d",m);
	}
	if(n<m)
	{
		for(i=1;i<=m;i++)
			printf("%d",n);
	}
	if(n==m)
	{
		for(i=1;i<=n;i++)
			printf("%d",m);
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main()
{
  int n;
  int temp;
  int d[100][6];
  int count = 0;
  int p = 0;
  int m;
  int h;
  scanf("%d", &n);
  
  for(int i  = 0 ; i < n; i++)
    {
      for(int j = 0 ; j < 6; j++)
	{
	  scanf("%d", &d[i][j]);
	}
    }
  
  for(int i = 0; i < n-1; i++)
    {
      for(int j = 0; j < 6; j++)
	{
	  for(int k = 0; k < 6; k++)
	    {
	      if(d[i][j] == d[i+1][k])
		{
		  count++;
		  break;

		}
	    }
	}
      if(count != 6)
	{
	  count = 0;
	  continue;
	}
      count = 0;
      for(int p = i+1; p < n; p++)
	{
	  for(int j = 0; j < 6; j++)
	    {
	      for(int k = 0; k < 6; k++)
		{
		  if(d[i][j] == d[p][k])
		    {
		      count++;
		      break;
		      
		    }
		}
	    }
	  if(count != 6)
	    {
	      count = 0;
	      continue;
	    }
	  count = 0;
	  while(1)
	    {
	      if(d[i][0] == d[p][0])
		{
		  break;
		}
	      for(int j = 0; j < 6; j++)
		{
		  if(d[p][j] == d[i][0])
		    {
		      m = j;
		      break;
		    }
		}
	      temp = d[p][0];
	      if(m == 3)
		{
		  d[p][0] = d[p][3];
		  d[p][3] = d[p][5];
		  d[p][5] = d[p][2];
		  d[p][2] = temp;
		}
	      if(m == 2)
		{
		  d[p][0] = d[p][2];
		  d[p][2] = d[p][5];
		  d[p][5] = d[p][3];
		  d[p][3] = temp;
		}
	      if(m == 4 || m == 0)
		{ 
		  d[p][0] = d[p][4];
		  d[p][4] = d[p][5];
		  d[p][5] = d[p][1];
		  d[p][1] = temp;
		}
	      if(m == 1 || m == 5)
		{
		  d[p][0] = d[p][1];
		  d[p][1] = d[p][5];
		  d[p][5] = d[p][4];
		  d[p][4] = temp;
		}
	    }
	  while(1)
	    {
	      for(int j = 0; j < 6; j++)
		{
		  if(d[p][j] == d[i][1])
		    {
		      m = j;
		    }
		}
	      if(d[i][5] == d[p][5] && d[i][2] == d[p][2] && d[i][4] == d[p][4] && d[i][3] == d[p][3])
		{
		  printf("No\n");
		  return 0;
		}
	      if(d[i][1] == d[p][1] || m == 5)
		{
		  break;
		}
	      temp = d[p][1];
	      if(m == 2)
		{
		  d[p][1] = d[p][2];
		  d[p][2] = d[p][4];
		  d[p][4] = d[p][3];
		  d[p][3] = temp;
		}
	      if(m == 3)
		{
		  d[p][1] = d[p][3];
		  d[p][3] = d[p][4];
		  d[p][4] = d[p][2];
		  d[p][2] = temp;
		}
	      if(m == 4)
		{
		  d[p][1] = d[p][4];
		  d[p][4] = temp;
		  temp = d[p][2];
		  d[p][2] = d[p][3];
		  d[p][3] = temp;
		}
	      if(d[i][5] == d[p][5] && d[i][2] == d[p][2] && d[i][4] == d[p][4] && d[i][3] == d[p][3])
		{
		  printf("No\n");
		  return 0;
		}
	    }
	}
    }
  printf("Yes\n");
}



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

long long gcd(long long a, long long b){
  if (b==0) return a;
  else return gcd(b,a%b);
}

int main() {
  int n;
  cin >> n;
  if(n%10==3) cout << "bon" << endl;
  else if (n%10==0||n%10==1||n%10==6||n%10==8) cout << "pon" << endl;
  else cout << "hon" << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define REP(i,n) for(int i = 0; i < n; i++)
using namespace std;

int FindSumofdigit(int n){
    int sum = 0;
    while(n > 0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(){
    int n,a,b, sum = 0;
    cin >> n >> a >> b;
    FOR(i, 1, n){
        if(FindSumofdigit(i) >= a && FindSumofdigit(i) <= b){
            sum += i;
        }
    }
    cout << sum << endl;
}   

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>

using std::ios_base;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::fixed;

using std::vector;
using std::string;
using std::stack;
using std::queue;
using std::deque;
using std::map;
using std::set;
using std::unordered_map;
using std::unordered_set;
using std::bitset;

using std::tuple;
using std::make_tuple;
using std::pair;
using std::make_pair;

using std::sort;
using std::reverse;
using std::nth_element;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

const int MAXN = 100000;
const int INF = 1e9;
const int MOD = 1e9+7;
const int64_t L_INF = 4e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;

    int n, a, b;
    cin >> n >> a >> b;
    cout << std::min(a, b) << ' ' << std::max(0, a + b - n) << '\n';

    #ifdef LOCAL
        cerr << "\n== " << 1.0 * clock() / CLOCKS_PER_SEC << " sec.\n";
    #endif
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define infty 1000000001
using namespace std;
int c=0;
void merge(int *a,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    int l[n1+1];
    int r[n2+1];
    for(int i=0;i<n1;i++){
        l[i]=a[left+i];
    }
    for(int i=0;i<n2;i++){
        r[i]=a[mid+i];
    }
    l[n1]=infty;
    r[n2]=infty;
    int i=0;
    int j=0;
    for(int k=left;k<right;k++){
        c++;
        if(l[i]<=r[j]){
            a[k]=l[i];
            i++;
        }
        else{
            a[k]=r[j];
            j++;
        }
    }
}
void mergesort(int *a,int left,int right){
    if(left+1<right){
        int mid=(right+left)/2;
        mergesort(a,left,mid);
        mergesort(a,mid,right);
        merge(a,left,mid,right);
    }
}
int main(){
    int n;
    cin>>n;
    int b[n];
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    mergesort(b,0,n);
    for(int i=0;i<n-1;i++){
        cout<<b[i]<<" ";
    }
    cout<<b[n-1]<<endl;
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 6988
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp make_pair
#define sz(x) ((int)(x).size())
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(),x.end()
#define y1 omg
#define INF 1000000010
#define FOR(x, n) for(int x=0; x<n; x++)
#define ini(x, n) memset(x, n, sizeof(x));
#define MOD ((int)1e9 + 7)
#define atoi(x) ((x)-'0')
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

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

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

const int MAX = 1e6;
int n, t, flag, arr[MAX], fact[MAX];

signed main() {
	cin >> n;
	FOR(i, n) cin >> arr[i];
	FOR(i, n) {
		t = arr[i];
		for (int i = 2; i * i <= t; i++) {
			if (t % i == 0) {
				if(fact[i])	flag = 1;
				fact[i] = 1;
			}
			while (t % i == 0) t /= i;
		}
		if (t > 1) {
			if (fact[t]) flag = 1;
			fact[t] = 1;
		}
	}
	if (!flag) {
		cout << "pairwise coprime";
		return 0;
	}
	int tmp = arr[0];
	for (int i = 1; i < n; i++) {
		tmp = gcd(tmp, arr[i]);
	}
	if (tmp == 1) cout << "setwise coprime";
	else cout << "not coprime";
}

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

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

LL f(LL b, LL n){
    if(n < b) return n;
    else return f(b, n / b) + (n % b);
}

int main(){
    LL n, s;
    cin >> n >> s;
    if(n == s){
        cout << n + 1 << endl;
        return 0;
    }else if(s > n){
        cout << -1 << endl;
        return 0;
    }

    for(LL i = 2LL; i*i <= n; i++){
        if(f(i, n) == s){
            cout << i << endl;
            return 0;
        }
    }

    for(LL i = (LL)sqrt(n); i >= 1; i--){
        LL b = (n - s) / i + 1LL;
        if(b == 1) continue;
        if(f(b, n) == s){
            cout << b << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}


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

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

	int n;
	cin >> n;
	if(n%10 == 3){
		cout << "bon";
	}
	else if(n%10 == 0 || n%10 == 1 || n%10 == 6 || n%10 == 8) cout << "pon";
	else cout << "hon";

	return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#ifndef _USEFUL_MACROS_
#define _USEFUL_MACROS_
#define INF INT_MAX/3
#define N_PRIME 1000000007
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define OUTPUT_DEBUG
#ifdef OUTPUT_DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x) do{}while(false)
#endif
#endif 

using namespace std;

int64_t nmax = 100008;              // 0!??????nmax!?????§?????¨?????????
int64_t prime = N_PRIME;            // ?????°???????????????????????????????????§n????????§?????????????????????
bool isCombPreProcess = false;      // ????????????????????£?????????????????????
vector<int64_t> fact(nmax+1);       // fact[i] = i????????? mod prime
vector<int64_t> fact_inv(nmax+1);   // fact_inv[i] = fact[i]^(-1) mod prime

// x^n ( mod p )
int64_t power(int64_t x,int64_t n,int64_t p){
    int64_t ret = 1;
    
    while(n){
        if(n%2)ret=(ret*x)%p;
        x = (x * x) % p;
        n/=2;
    }
    
    return ret;
}

void CombPreProcess(){
    fact[0] = 1;
    FOR(i,1,nmax+1)
        fact[i] = (i*fact[i-1])%prime;
    
    // ?????§?????????????°??????????
    // a^(p-1) = (mod p)
    // a_inv = a^(p-2) (mod p) ??¨????????¨???
    // a * a_inv = a^(p-1) = 1 (mod p)
    // ???????????£??? a_inv ??? a ?????????
    
    // fact[n]^(p-2) = fact[n]_inv (mod p)
    // ????????? fact[n] ???p????´???°????????£??????????????????
    fact_inv[nmax] = power(fact[nmax],prime-2,prime);
    RFOR(i,0,nmax)
        fact_inv[i] = ((i+1)*fact_inv[i+1])%prime;
    isCombPreProcess = true;
}

// a C b
int64_t Combination(int64_t a,int64_t b){
    if( isCombPreProcess ){
        return ((((fact[a]*fact_inv[b]) % prime)*fact_inv[a-b]) % prime);
    }else{
        CombPreProcess();
        return Combination(a,b);
    }
}

void test(){
    // ?´??????¢??°?????????
    debug(power(2,10,prime));
    debug(power(2,9,prime));
    
    // ????????????????????§????????????
    debug(Combination(5,3));
    debug(Combination(5,2));
    debug(Combination(5,1));
    debug(Combination(5,0));
    debug(Combination(5,5));
}
 
int main(void){
int m,n;cin >> m >> n;
cout << power(m,n,N_PRIME) << endl;
    return 0;
}

Measured memory_bytes: 4248
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

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

    string str;
    cin >> str;

    int indexA, indexZ;
    indexA = str.find('A');
    indexZ = str.rfind('Z');

    cout << indexZ - indexA + 1 << '\n';
    return 0;
}

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

int main() {
  int n;
  cin>>n;
  vector<string> s(n);
  for(int i=0;i<n;i++){
    cin>>s.at(i);
  }
  
  bool result=true;
  
  for(int i=1;i<n;i++){
    if(s.at(i-1).at(s.at(i-1).size()-1)!=s.at(i).at(0)){
      result=false;
      goto OUT;
    }
    
    for(int j=0;j<i;j++){
      if(s.at(i)==s.at(j)){
        result=false;
        goto OUT;
      }
    }
  }
  
  OUT:
  if(result)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
int main(){
    long long W,H,x,y;
    std::cin >> W >> H >> x >> y;
    std::cout << std::fixed << std::setprecision(10) << (long double)(W*H / 2.00000) << " ";
    std::cout <<( W == 2 * x and H == 2 * y)  << std::endl;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int i,j,n;
    cin>> n;
    for(i=3;i<=n;i++){
        if(i%3==0){
            cout<< " "<< i;
        }else{  
            for(j=10;j<i;j*=10){
                if((i%j)==3||(i/j)%10==3){
                    cout<< " "<< i;
                    break;
                }
            }
        }
    }
    cout<< endl;
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll table[5002][5002];
ll hirou[5002];
ll intable[5002][202];
int N,M;


void solve(int l, int r,int i){
  ll most = 0;
   int opt = 0;
  if(l == r)return;
  
  for(int j = l; j < r; j++){
    if(most < intable[j][i]){
      opt = j;
      most = intable[j][i];
    }
  }
 
  table[l][opt] = table[l][opt] + most;
  table[l][r] = table[l][r] - most;
  table[opt+1][opt] = table[opt+1][opt] - most;
  table[opt+1][r] = table[opt+1][r] + most;
  solve(l,opt,i);
  solve(opt+1,r,i);
  return;
}

int main(){
  ll mmax = 0;
  cin>>N>>M;
  for(int i = 1; i < N; i++)cin>>hirou[i];
  for(int i = 2; i < N; i++)hirou[i] += hirou[i-1];

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


  for(int i = 0; i < M; i++){
    solve(0,N,i);
  }

  for(int i = 0; i < N; i++){
    for(int j = 1; j < N; j++){
      table[i][j] += table[i][j-1];
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 1; j < N; j++){
      table[j][i] += table[j-1][i];
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(mmax < table[i][j]-(hirou[j]-hirou[i]) && i <= j){
	mmax = table[i][j]-(hirou[j]-hirou[i]);
      }
    }
  }

  cout<<mmax<<endl;
}

Measured memory_bytes: 203648
S = list(input())

res = True

n = S.count("N")
s = S.count("S")
w = S.count("W")
e = S.count("E")

if (n > 0) ^ (s > 0):
    res = False

if (w > 0) ^ (e > 0):
    res = False

if res:
    print("Yes")
else:
    print("No")



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

int main() {
	string n;
	cin >> n;
	for (int i = 0; i < n.size(); i++) {
		if (n[i] == '1') n[i] = '9';
		else n[i] = '1';
	}
	cout << n << endl;
}


Measured memory_bytes: 256
import numpy as np

L,R  = list(map(lambda x: int(x),input().split()))
ans=2019
for i in range(2019):
    for j in range(2019):
        l = L+i
        r = R-j
        if l>=r :
            continue
        candidate = (l*r)%2019
        if ans>candidate:
            ans=candidate
print(ans)
        
        



Measured memory_bytes: 23436
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <algorithm>
#include <limits.h>
#include <bits/stdc++.h>
#define fw(x) freopen("x.txt","w",stdout)
#define For(i,a,b,c) for(int i = a;i < b;i+=c)
#define REP(i,n) for(int i = 0;i < n;++i)
#define REP1(i,n) for(int i = 1; i<=n;i++)
#define mem(a,s) memset(a,s,sizeof a)
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
#define pf printf
#define sc scanf
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define vii vector<int>
#define vll vector<ll>
#define vss vector<string>
#define debug(x)  cout<<#x"="<<(x)<<endl
#define pb push_back


using namespace std;


// moves

//int dx[]= {0,0,1,-1};/*4 side move*/
//int dy[]= {-1,1,0,0};/*4 side move*/
//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/
//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/


//big_mod

//ll bigmod(ll a,ll b,ll m)
//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}
//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M

//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}
//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}
//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}

const int mod = 1000000007;
ll qpow(ll n,ll k)
{
    ll ans=1;
    assert(k>=0);
    n%=mod;
    while(k>0)
    {
        if(k&1)
            ans=(ans*n)%mod;
        n=(n*n)%mod;
        k>>=1;
    }
    return ans%mod;
}
int ar[100009];
int cost[100009];
void run(int i, int n){
    if(i>=n) return;
    if(cost[i]== -1 ){
        run(i+1, n);
        run(i+2, n);
    }
    if(i< n-1){
        int c1 = cost[i+1] + abs(ar[i]-ar[i+1]);
        int c2 = cost[i+2] + abs(ar[i]-ar[i+2]);
        cost[i] = min(c1, c2) ;
    }
    else cost[i] = cost[i+1] + abs(ar[i] - ar[i+1]);
}
int main()
{
    fast;
    int n, v;
    cin>>n;
    REP1(i, n){
        cin>>v;
        cost[i]= -1;
        ar[i] = v;
    }
    cost[n]=0;
    run(1, n);
    cout<<cost[1]<<'\n';
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define vec vector
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/

    int n;cin >> n;
    vec<int> a(n);
    rep(i,n)cin >> a[i];
    /*
    差が例えば3ならば
    a+b=n
    a-b=3
    のどちらか
    場所は二通り
    ほぼexpするだけで解けるな
    */
    map<int,int> m;
    rep(i,n){
        m[a[i]]++;
    }
    for(auto v:m){
        if(v.second!=2&&(!(n%2==1&&v.first==0))){
            cout << 0 << endl;return 0;
        }if(v.first==0&&v.second!=1){
            cout << 0 << endl;
            return 0;
        }
    }

    cout << expm(2,n/2) << endl;
}

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

//#define int long long
typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W, D;
    cin >> H >> W >> D;
    vector<pair<int,int>> p(H*W);
    for (int h=0;h<H;h++){
        for (int w=0;w<W;w++){
            int a;
            cin >> a;
            a--;
            p[a] = make_pair(h,w);
        }
    }
    vector<int> step(H*W);
    for (int i=H*W-1;i>=0;i--){
        if (i+D >= H*W) step[i] = 0;
        else step[i] = step[i+D] + abs(p[i+D].first - p[i].first) + abs(p[i+D].second - p[i].second);
    }
    int Q;
    cin >> Q;
    for (int i=0;i<Q;i++){
        int L, R;
        cin >> L >> R;
        L--;R--;
        cout << step[L] - step[R] << "\n";
    }
}

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


ll fact[NMAX+1];
ll invfact[NMAX+1];

ll pow(ll a, ll b) {
  if (b == 0) {
    return 1;
  } else if (b % 2 == 0) {
    ll d = pow(a, b / 2);
    return (d * d) % MOD;
  } else {
    ll d = pow(a, b - 1);
    return (a * d) % MOD;
  }
}

int main(){
    int n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    
    fact[0] = 1;
    for(int i = 1; i <= NMAX+1; i++){
        fact[i] = fact[i-1]*i%MOD;
    }
    invfact[NMAX+1] = pow(fact[NMAX+1], MOD-2);
    invfact[0] = 1;
    for(int i = NMAX; i > 0; i--){
        invfact[i] = invfact[i+1]*(i+1)%MOD;
    }

    ll ans = 0;
    
    for(int i = 0; i < n; i++){
        // min
        if((n-i-1)-(k-1) >= 0){
            ll cnt = fact[(n-i-1)]*invfact[k-1] %MOD;
            cnt = cnt*invfact[(n-i-1)-(k-1)] %MOD;
            ll tmp = a[i]*cnt %MOD;
            ans -= tmp;
            if(ans < 0) ans += MOD;
        }

        // max
        if(i-(k-1) >= 0){
            ll cnt = fact[i]*invfact[k-1] %MOD;
            cnt = cnt*invfact[i-(k-1)] %MOD;
            ll tmp = a[i]*cnt %MOD;
            ans += tmp;
            ans %= MOD;
        }
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 5604
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		new Main().run();
	}
	public void run(){
		Scanner sc = new Scanner(System.in);
		int[] a = new int[5];
		for(int i=0; i < 5; i++){
			a[i]=sc.nextInt();
		}
		Arrays.sort(a);
		System.out.println(a[4]+" "+a[3]+" "+a[2]+" "+a[1]+" "+a[0]);
	}
}

Measured memory_bytes: 17180
using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;

// 満点解答
// 解説の満点解法１をそのまま実装

class Program
{
    static void Main()
    {
        string[] cin = Console.ReadLine().Split();
        int n = int.Parse(cin[0]);
        int a = int.Parse(cin[1]);
        cin = Console.ReadLine().Split();
        int[] x = new int[n + 1];
        for (int i = 1; i <= n; i++)
        {
            x[i] = int.Parse(cin[i - 1]);
        }

        long[,,] dp = new long[n + 1, n + 1, n * a + 1];

        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= n; k++)
            {
                for (int s = 0; s <= n * a; s++)
                {
                    if (j == 0 && k == 0 && s == 0) dp[j, k, s] = 1;
                    else if (j >= 1 && s < x[j]) dp[j, k, s] = dp[j - 1, k, s];
                    else if (j >= 1 && k >= 1 && s >= x[j])
                        dp[j, k, s] = dp[j - 1, k, s] + dp[j - 1, k - 1, s - x[j]];
                    else dp[j, k, s] = 0;
                }
            }
        }

        long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans += dp[n, i, i * a];
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 61664