akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <cmath>
 
using namespace std;
 
vector<pair<int, int> > lista;
int dp[105][100005];
int n, c;
 
int transforma(int a, int b){
    double v = (a / (double)b) + 1e-9;
    int r = round(v * 100000);
 
    return r;
}
 
int solve(int pos, int total){
    if(pos >= lista.size()) return 0;
 
    int &d = dp[pos][total];
    if(d != -1) return d;
    int res = solve(pos + 1, total);
    if(total + lista[pos].second <= 100000) res = max(res, solve(pos + 1, total + lista[pos].second) + lista[pos].first);
 
    return d = res;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
 
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        int w, v; cin >> w >> v;
        if(w > c) continue;
        lista.push_back({v, transforma(w, c)});
        // cout << lista[i].first << " " << lista[i].second << endl;
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 0) << endl;
    
    return 0;
}

Measured memory_bytes: 41344
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

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

using namespace std;

int main() {
	int n;
	cin >> n;
	n++;
	vector<ll> dp(n+5,0);

	rep(i,n){
		if(i==0)continue;
		rep(j,n){
			if(j==0)continue;
			if(i*j > n)break;
			dp[i*j]++;
		}
	}

	int64_t ans =0;
	rep(i,n){
		if(i==0)continue;
		ans += (ll)i*dp[i];
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 81400
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;
static const ll LOGN=55;


ll dp[MAX][15]={};

int main(void) {
  string s;
  cin >> s;
  ll N=(ll)s.size();
  ll i, j, k;
  
  dp[0][0]=1;
  for(i=0; i<N; i++) {
    for(j=0; j<13; j++) {
      
      if(s[i]=='?')
        for(k=0; k<10; k++)
          moC(dp[i+1][(j*10+k)%13], +, dp[i][j]);
      else
        moC(dp[i+1][(j*10+s[i]-'0')%13], +, dp[i][j]);
      
    }
  }
  
  pt(dp[N][5]);
  
  
}






Measured memory_bytes: 12160
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++){
			a[i] = sc.nextInt();
		}
		
		int sum = 0;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				sum+=a[i]*a[j];
			}
		}
		
		System.out.println(sum);
	}

}


Measured memory_bytes: 23252
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int q, h, s, d;
int n;
signed main() {
	cin >> q >> h >> s >> d >> n;
	h = min(h, q * 2);
	s = min(s, h * 2);
	d = min(d, s * 2);
	cout << (n / 2) * d + (n % 2) * s << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

#ifdef DEBUG
#else
    #define cerr if (false) cerr
#endif

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    cin >> a;
    vector <int> sorted = a;
    sort(all(sorted));
    map <int, int> where;
    forn (i, 0, n)
        where[sorted[i]] = i;
    int ans = 0;
    forn (i, 0, n) {
        if (where[a[i]] % 2 != i % 2)
            ++ans;
    }
    cerr << ans;
    cout << ans / 2;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

#define MAX_V 100001
struct edge {
	ll to;
	ll cost;
};
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + MAX_V, -1);
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;

		for (int i = 0; i < G[v].size(); ++i) {
			edge e = G[v][i];
			if (d[e.to] == -1 || d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

void solve_abc_d() {
	ll n;
	cin >> n;

	ll a, b, c;
	edge e;
	rep(i, n - 1) {
		cin >> a >> b >> c;
		e.to = b;
		e.cost = c;
		G[a].push_back(e);
		e.to = a;
		e.cost = c;
		G[b].push_back(e);
	};

	ll q, k;
	cin >> q >> k;

	dijkstra(k);

	ll x, y;
	vector<ll> ans;
	rep(i, q) {
		cin >> x >> y;
		ans.push_back(d[x] + d[y]);
	}

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

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

	solve_abc_d();

	return 0;
}


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

string a, b;

bool solve() {
	for (int i = 0; i < a.size() - b.size() + 1; ++i) {
		int j;
		for (j = 0; j < b.size(); j++) {
			if (b[j] != '_' && a[i + j] != b[j]) {
				break;
			}
		}
		if (j == b.size()) return true;
	}
	return false;
}

int main() {
	while (cin >> a >> b) {
		cout << (solve() ? "Yes" : "No") << endl;
	}
	return 0;
}


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

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()

const int mod = 1e9+7;
const int inf = 2e18;



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

	double r;
	cin>>r;

	r = 2*r;
	cout<<(3.141592)*r<<'\n';

	return 0;
}	

Measured memory_bytes: 3800
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')

def solve():
    x1, x2, x3, x4, x5 = it()
    if x1 == 0:
        return 1
    if x2 == 0:
        return 2
    if x3 == 0:
        return 3
    if x4 == 0:
        return 4
    return 5

if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 9460
#import<atcoder/all>
#define f(i)std::cout<<i<<' ';
int n,a;int main(){std::cin>>n>>a;atcoder::scc_graph g(n);for(;std::cin>>n>>a;)g.add_edge(n,a);f(size(g.scc()))for(auto i:g.scc()){f(size(i))for(int j:i)f(j)}}

Measured memory_bytes: 40084
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define cost first
#define from second.first
#define to second.second
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

int main(void){
	ll h,hd,w,wd,i,a,b,c,ans;
	cin >> h >> w;
	if(!(h%3) || !(w%3)){
		cout << 0 << endl;
		return 0;
	}
	ans = min(h,w);
	for(i=1ll; i<h; ++i){
		a = w * i;
		hd = h - i;
		b = hd * (w/2);
		c = hd * (w - (w/2));
		ans = min(ans,max(a,c)-min(a,b));
	}
	for(i=1ll; i<w; ++i){
		a = h * i;
		wd = w - i;
		b = wd * (h/2);
		c = wd * (h - (h/2));
		ans = min(ans,max(a,c)-min(a,b));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		int[] count = new int[11];
		count[sc.nextInt()]++;
		count[sc.nextInt()]++;
		count[sc.nextInt()]++;
		
		if(count[5] == 2 && count[7] == 1){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
 
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

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

typedef long long LL;
const int N = 1e6+7, M = 998244353;

int fr[N];
LL msum[N], msqsum[N];
LL gcdsum[N];

LL power(LL a, LL p) {
    if (p==0)   return 1;
    LL ans = power(a, p/2);
    ans = (ans * ans)%M;
    if (p%2)    ans = (ans * a)%M;
    return ans;
}


LL fac[N], invfac[N], inv[N];

void pre() {
    fac[0] = 1;
    for (int i=1; i<N; i++)
        fac[i] = (fac[i-1]*i)%M;

    invfac[N-1] = power(fac[N-1], M-2);
    for (int i=N-2; i>=0; i--)
        invfac[i] = (invfac[i+1] * (i+1))%M;

    for (int i=1; i<N; i++)
        inv[i] = (fac[i-1]*invfac[i])%M;
}


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

    int n;
    cin>>n;

    for (int i=1; i<=n; i++) {
        int x;
        cin>>x;
        fr[x]++;
    }

    for (int i=1; i<N; i++) {
        for (int j=i; j<N; j+=i) {
            msum[i] += 1LL*j*fr[j];
            msqsum[i] += 1LL*j*j*fr[j];
        }
    }

    for (int i=1; i<N; i++) {
        msum[i] %= M;
        msqsum[i] %= M;
        gcdsum[i] = (msum[i]*msum[i]+M-msqsum[i])%M;
        if (gcdsum[i]%2)    gcdsum[i] += M;
        gcdsum[i]/=2;
    }

    pre();
    long long ans = 0;
    for (int i=N-1; i>0; i--) {
        for (int j=2*i; j<N; j+=i)
            gcdsum[i] = (gcdsum[i] + M - gcdsum[j])%M;

        ans = (ans + gcdsum[i] * inv[i])%M;
    }
    cout<<ans<<endl;
}


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

#define int long long

main() {
	int n, k, m; cin >> n >> k >> m;
	if (k * 2 < n) {
		int ans = 1;
		for (int i = 0; i < n; i++) {
			ans *= k;
			ans %= m;
		}
		cout << ans << endl;
	} else {
		int ans = 0;
		static int dp[1000000];
		for (int i = 0; i < k; i++) {
			dp[0] = 1;
			for (int j = 1; j < (1 << 2 * k - 1); j++) {
				int tmp = 0, sum = 0, bitcnt = 0;
				for (int K = 0; K < 2 * k - 1; K++) {
					if ((j >> K) & 1) tmp += - (k - 1) + K, sum += dp[j - (1 << K)], sum %= m, bitcnt++;
				}
				if (i + tmp >= k || i + tmp < 0) dp[j] = 0;
				else dp[j] = sum;
				if (bitcnt == n - 1) ans += dp[j];
			}
		}
		ans %= m;
		int sum = 1;
		for (int i = 0; i < n; i++) {
			sum *= k;
			sum %= m;
		}
		//for (int i = 0; i < k; i++) {
		//	for (int j = 0; j < (1 << 2 * k - 1); j++) {
		//		cout << dp[i][j] << " ";
		//	} cout << endl;
		//}
		cout << (sum + m - ans) % m << endl;
	}
}


Measured memory_bytes: 7212
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i< (int) n; i++)
 
 
int main() {
    int N;
    int t[110000], x[110000],y[110000];
    cin >> N;
    t[0] =x[0] = y[0] =0;
    rep(i,N)cin >> t[i+1] >> x[i+1] >> y[i+1];

    bool can = 1;
    rep(i,N){
        int dt = t[i+1] -t[i];
        int dist =abs(x[i+1]-x[i]) +abs(y[i+1] - y[i]);
        if (dt < dist)can = 0;
        if (dist%2 != dt%2) can =0;
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;

    }


    


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

int main(){
  int N, K;
  int x, num = 0;
  
  cin >> N >> K;
  
  for(int i = 0;i < N;i ++){
    cin >> x;
    
    if(x < K - x){
      num += 2 * x;
    }
    else{
      num += 2 * (K - x);
    }
  }
  cout << num << endl;
}

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

int main(){
  int n;
  int x[200005], y[200005];
  cin >> n;
  int mx1=0, mx2=0;
  int mn1=1001001001, mn2=1001001001;
  int mx1i,mx2i,mn1i,mn2i;
  rep(i, n){
    cin >> x[i] >> y[i];
    int tmp1=x[i]+y[i];
    int tmp2=x[i]-y[i];
    if(tmp1>mx1){
      mx1=tmp1;mx1i=i;
    }
    if(tmp2>mx2){
      mx2=tmp2;mx2i=i;
    }
    if(tmp1<mn1){
      mn1=tmp1;mn1i=i;
    }
    if(tmp2<mn2){
      mn2=tmp2;mn2i=i;
    }
  }
  int ans = 0;
  ans = max(x[mx1i]-x[mn1i]+y[mx1i]-y[mn1i], x[mx2i]-x[mn2i]+y[mn2i]-y[mx2i]);
  cout << ans;
  return 0;
}


Measured memory_bytes: 5196
#include <iostream>
#include <vector>


int main()
{
	int n, q; std::cin >> n >> q;
	
	std::vector<int>* array = new std::vector<int>[n];
	;
	for (int i=0; i<q; i++) {
		int op, x, t;
		std::cin >> op;
		switch (op) {
		case 0:
			std::cin >> t >> x;
			array[t].push_back(x);
			break;
		case 1:
			std::cin >> t;
			for (std::vector<int>::iterator it = array[t].begin(); it != array[t].end(); ++it) {
				if (it != array[t].begin()) std::cout << " ";
				std::cout << *it;
			}
			std::cout << std::endl;
			break;
		case 2:
			std::cin >> t;
			array[t].clear();
			break;
		}
	}
	
	delete[] array;
	
	return 0;
}
		



Measured memory_bytes: 5868
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=3e3+10;
vector<int> G[maxn];
int vis[maxn],f[maxn],a[maxn],id[maxn];
bool cmp(const int A,const int B){
	return a[A]<a[B];
}
void dfs(int x){
	vis[x]=1;
	f[x]=0;
	for(auto v:G[x]){
		dfs(v);
		f[x]|=(f[v]^1);
	}
}
int main(){
	int n=read();
	REP(i,1,n) a[i]=read();
	REP(i,1,n-1){
		int x=read(),y=read();
		if(a[x]<a[y]) G[y].push_back(x);
		if(a[x]>a[y]) G[x].push_back(y);
	}
	REP(i,1,n) id[i]=i;
	sort(id+1,id+n+1,cmp);
	DREP(i,n,1) if(!vis[id[i]]) dfs(id[i]);
	REP(i,1,n) if(f[i]) printf("%d ",i);
	return 0;
}


Measured memory_bytes: 384
/* kadai4_3
   nabe9393 */

#include<stdio.h>
//プロトタイプ宣言
int snowfall(int height_A, int height_B);

int main(void){
  int tower_west, tower_east;
  scanf("%d %d", &tower_west, &tower_east);
  //関数を呼び出す
  printf("%d\n", snowfall(tower_west, tower_east));
  return 0;
}

//関数の定義
//露出した二つの塔の高さから求める。
int snowfall(int height_A_exposed, int height_B_exposed){
  int tower_diff, height_A, snow;
  //塔の高さの差を求める。
  tower_diff = height_B_exposed - height_A_exposed;
  //西の塔の実際の高さを求める。
  //tower_diff-1番目の塔なので、１からtower_diff-1までを足したものが高さ。
  height_A = tower_diff * (tower_diff - 1)/2;
  //本来の高さから露出分を引くと積雪量が出る。
  snow = height_A - height_A_exposed;
  return(snow);
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 1 << 20;

int n, v, x[200010];

int l[22][200010], r[22][200010];

int val[22], cnt, f[N], g[N];

vector<PII> t;

int main()
{
	gii(n, v);
	for (int i = 1; i <= n; ++i) gi(x[i]);
	for (int i = v; ; i = i >> 1)
	{
		val[++cnt] = i;
		for (int j = 1; j <= n; ++j)
		{
			int k = j;
			while (k < n && x[k + 1] - x[k] <= i) ++k;
			for (int p = j; p <= k; ++p) l[cnt][p] = j, r[cnt][p] = k;
			if (cnt == 1) t.pb(mp(j, k));
			j = k;
		}
		if (!i) break;
	}
	int all = cnt - 1;
	for (int i = 0; i < (1 << all); ++i) g[i] = n + 1;
	for (int i = 1; i < (1 << all); ++i)
	{
		for (int j = 0; j < all; ++j)
			if (i & (1 << j))
			{
				int t = f[i ^ (1 << j)];
				f[i] = max(f[i], r[j + 2][t + 1]);
				t = g[i ^ (1 << j)];
				g[i] = min(g[i], l[j + 2][t - 1]);
			}
	}
	for (auto v : t)
	{
		bool flag = 0;
		int s = (1 << all) - 1;
		for (int i = 0; i < (1 << all); ++i)
		{
			if (f[i] >= v.fi - 1 && v.se + 1 >= g[s ^ i])
				flag = 1;
		}
		for (int i = v.fi; i <= v.se; ++i)
			puts(flag ? "Possible" : "Impossible");
	}
}

Measured memory_bytes: 40576
#include<stdio.h>

int A[1000000], n;

int BinarySearch(int key) {
    int left = 0;
    int right = n;
    int mid;
    while(left < right) {
     mid = (left + right)/2;
     if(key == A[mid]) return 1;
     if(key > A[mid]) left = mid+1;
     else if(key < A[mid]) right = mid;
    }
    return 0;
}

int main() {
    int i, q, k, sum=0;
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d",&A[i]);
    }
    scanf("%d",&q);
    for(i=0; i<q; i++){
        scanf("%d",&k);
        if( BinarySearch( k ) ) sum++;
    }
    printf("%d\n", sum);

    return 0;
}


Measured memory_bytes: 2080
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#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 fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z main.cpp
//.\a.exe

int main(void){ios::sync_with_stdio(false);cin.tie(0);
///////////////////////////////////////////////////////
int a,b,c,sum=0;
cin >> a >> b >> c;
sum = c-(a-b);
if(sum<=0){
  cout << "0" << endl;
}
else{
	cout << sum << endl;
}

///////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
//using Graph = vector<vector<int>>;
typedef long long ll;
using Graph = vector<vector<pair<ll,ll>>>;
const int mod =1e+9+7;

const int dy[4]={0,1,0,-1};
const int dx[4]={1,0,-1,0};
const ll INF=1e10;

ll RepeatSquaring(ll a, ll n, ll p){
    if(n==0) return 1;
    if(n%2==0){
        ll t = RepeatSquaring(a, n/2, p);
        return t*t % p;
    }
    return (a*RepeatSquaring(a, n-1, p))%p;
}

ll nCr(ll n, ll r, ll mod){
    ll mul = 1, div = 1;
    for(ll i = 0; i < r; i++){
        mul *= n - i;
        div *= i + 1;
        mul %= mod;
        div %= mod;
    }   
    return mul * RepeatSquaring(div, mod - 2, mod) % mod;
}
int main(){
    ll n; cin>>n;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    ll sum10=RepeatSquaring(10,n,mod);
    ll sum8=RepeatSquaring(8,n,mod);
    ll sum9=RepeatSquaring(9,n,mod);
    sum9*=2;
    sum9%=mod;
    ll ans=sum10+sum8;
    ans%=mod;
    if(ans>sum9){
        ans-=sum9;
    }
    else{
        ans+=mod;
        ans-=sum9;
    }
    ans%=mod;
    cout<<ans<<endl;



}











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

int main() {
  int n,m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  rep(i,m){
    int x,y;
    cin >> x >> y;
    g[x-1].push_back(y-1);
    g[y-1].push_back(x-1);
  }
  vector<int> dist(n,-1);
  vector<int> ans(n,0);
  queue<int> que;
  dist[0]=0;
  que.push(0);
  while(!que.empty()){
    int x=que.front();que.pop();
    for(int y:g[x]){
      if(dist[y]==-1){
        dist[y]=dist[x]+1;
        ans[y]=x;
        que.push(y);
      }
    }
  }
  cout << "Yes" << endl;
  rep(i,n-1) cout << ans[i+1]+1 << endl;
    
}


Measured memory_bytes: 10636
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    print('2018'+input()[4:])

if __name__ == '__main__':
    main()


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

using namespace std;

#define MAX 2000001
#define VMAX 10000

int main(){
    unsigned short A[MAX], B[MAX]; 
    int C[VMAX + 1];
    int n, i, j;
    cin >> n;

    for(i = 0; i <= VMAX; i++){
        C[i] = 0;
    }

    for ( i = 0; i < n; i++)
    {
        cin >> A[i + 1];
        C[A[i + 1]]++;
    }

    for ( i = 1; i <= VMAX; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    
    for ( j = n; j >= 1; j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]]--;
    }
    
    for( i = 1; i <= n; i++){
        if( i > 1) cout << " ";
        cout << B[i];
    }
    cout << endl;

    return 0;
    
}


Measured memory_bytes: 10936
// Marcin Knapik
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // order_of_key
// #include <ext/pb_ds/tree_policy.hpp> // find by order
// using namespace __gnu_pbds; 
// #define ordered_set tree< int , null_type,less< int >, rb_tree_tag,tree_order_statistics_node_update>  

// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ll>(a, b)(rng)
 
typedef long double             ld;
typedef long long               ll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<vll>             vvll;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vii>             vvii;
#define pll pair<long long, long long>
#define vpll vector<pll> 
#define ull unsigned long long

#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second

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

template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<class T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return abs(a); }

const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll BIG_INF = 1e18 + 7;
const ll N = 1e6+7;
const ll T = 1<<20;
const ld inf = 1e18;

ll n, m, q, k, r;

void solve(){
    cin >> n >> k;
    vi tab(n);
    cin >> tab;
    for(int i = 0; i < n - k; i++)
        cout << (tab[i] < tab[i + k] ? "Yes" : "No") << '\n';
}

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

  q = 1;
  // cin >> q;

  for(int i = 1; i <= q; i++)
    solve();
} 

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define mp make_pair
#define pb push_back
#define EB emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr double eps = 1e-14; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    ll N,x;
    cin >> N >> x;
    vector<ll> a(N);
    rep(i,N) cin>>a[i];

    ll ans=0;
    for(int i=1;i<N;i++){
        ll t = a[i-1] + a[i];
        if(t>x){
            ll d = t-x;
            if(a[i]>=d){
                a[i] -= d;
            }else{
                a[i] = 0;
            }
            ans += d;
        }
    }
    cout << ans << endl;
} 


Measured memory_bytes: 1024
import java.io.*;
// import java.math.*;
// import java.util.*;
// import java.util.Map.*;
// import java.util.stream.*;

public class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader reader =
            new BufferedReader (new InputStreamReader (System.in));
        String S = reader.readLine();
        String O = "RUD";
        String E = "LUD";
        boolean flg = true;
        for (int i = 0; i < S.length(); i++) {
            if (1 == (i + 1) % 2 && !O.contains (S.substring (i, i + 1))) {
                flg = false;
                break;
            }
            if (1 == i % 2 && !E.contains (S.substring (i, i + 1))) {
                flg = false;
                break;
            }
        }
        System.out.println (flg ? "Yes" : "No");
        return;
    }
}

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

namespace Structured_Programming
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            List<int> temp = new List<int>();


            for (int i = 1; i <= num; i++)
            {
                if (i % 3 == 0 )
                {
                    temp.Add(i);
                }
                else
                {
                    for (int j = i; j > 0; j /= 10)
                    {
                        if (j % 10 == 3)
                        {
                            temp.Add(i);
                            break;
                        }
                    }
                }
            }

            foreach (int item in temp)
            {
                Console.Write(" " + item);
            }

            Console.WriteLine();
        }
    }
}



Measured memory_bytes: 19980
#include <iostream>
#include <vector>
using namespace std;
int main(void){
   int x,y;
   cin >> x >> y;
   for(int i = 0;i <= x;i++){
         if(2 * i + 4 * (x - i) == y){
               cout << "Yes" << endl;
               return 0;
         }
   }
   cout << "No" << endl;
}


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

int main() {
  int A,B,C; 
  cin >>A>>B>>C;
  if(A%B==C||A==1){
    cout<<"YES"<<endl;
    return 0;
  }
  bool hantei=false;
  for(int i=0;i<B;i++){
    if(A*i%B==C){
      //cout<<i<<" ";
      hantei=true;
      break;
    }
  }
  if(hantei){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
  return 0;
}

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

using namespace std;

int n;
int id[15];
int dist[15];
int w[15];
double dp[15][1<<15][15];
vector<int> path[15][1<<15];

const double INF = 100000000.0;

main(){
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> id[i] >> dist[i] >> w[i];
  }
  fill(dp[0][0], dp[15][0], INF);
  for(int i=0;i<n;i++){
    dp[0][1<<i][i] = 0.0;
    path[i][1<<i].push_back(i);
  }
  for(int i=0;i<15;i++){
    for(int j=0;j<(1<<n);j++){
      for(int k=0;k<n;k++){
	if(dp[i][j][k] == INF) continue;
	int sumW = 0;
	for(int l=0;l<n;l++){
	  if((1<<l) & j) sumW += w[l];
	}
	sumW *= 2;
	for(int l=0;l<n;l++){
	  if((1<<l) & j) continue;
	  double val = dp[i][j][k] + (abs(dist[l] - dist[k]) * (7.0 + sumW)) / 200.0;
	  if(val < dp[i+1][j|(1<<l)][l]){
	    dp[i+1][j|(1<<l)][l] = val;
	    path[l][j|(1<<l)] = path[k][j];
	    path[l][j|(1<<l)].push_back(l);
	  }
	}
      }
    }
  }
  double valm = INF;
  int idx;
  int state = (1<<n)-1;
  int maxW = 0;
  vector<int> ans;
  for(int i=0;i<n;i++){
    maxW += w[i];
  }
  for(int i=0;i<n;i++){
    double val = dp[n-1][state][i];
    /*cout << id[path[i][state][0]];
    for(int j=1;j<path[i][state].size();j++){
      cout << ' ' << id[path[i][state][j]];
    }
    cout << "   ";
    cout << val << endl;*/
    if(val < valm){
      valm = val;
      idx = i;
    }
  }
  cout << id[path[idx][state][0]];
  for(int i=1;i<path[idx][state].size();i++){
    cout << ' ' << id[path[idx][state][i]];
  }
  cout << endl;
  return 0;
}

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

static const int N = 100;

int main() {
	int n, p[N + 1], m[N + 1][N + 1];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i - 1] >> p[i];
	}
	for (int i = 1; i <= n; i++) m[i][i] = 0;
	for (int l = 2; l <= n; l++) {
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			m[i][j] = (1 << 21);
			for (int k = i; k <= j - 1; k++) {
				m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
			}
		}
	}
	cout << m[1][n] << endl;

	return 0;
}

Measured memory_bytes: 3108
#include <stdio.h>
#define N 100001

typedef struct{

  int par;
  int left;
  int right;

}node;

node T[N];

int dep(int);
int hei(int);

int main(){

  int n,i,j,a;

  scanf("%d",&n);

  for(i=0; i<n; i++) T[i].par = T[i].left = T[i].right =-1;

  for(i=0; i<n; i++){

    scanf("%d",&a);
    scanf("%d %d", &T[a].right, &T[a].left);

    if(T[a].left != -1) T[T[a].left].par = a;
    if(T[a].right != -1) T[T[a].right].par = a;

  }

  for(i=0; i<n; i++){

    printf("node %d: parent = %d, sibling = ", i ,T[i].par);

    if(T[i].par == -1){

      printf("-1, ");

    }else{

      if(T[T[i].par].left == i){

	printf("%d, ",T[T[i].par].right);

      }
      else{

	printf("%d, ",T[T[i].par].left);

      }

    }


    printf("degree = ");

    if(T[i].left == -1 && T[i].right == -1){

      printf("0, ");

    }
    else{

      if(T[i].left != -1 && T[i].right != -1){

	printf("2, ");

      }
      else{

	printf("1, ");

      }
    }

    printf("depth = %d, height = %d, ", dep(i), hei(i));

    if(T[i].par == -1){

      printf("root");


    }
    else{

      if(T[i].left ==-1 && T[i].right == -1){

	printf("leaf");
    
  }
      else{

	printf("internal node");
      }
    }
    printf("\n");
  }

  return 0;
}


int dep(int n){

  if(T[n].par == -1) return 0;


  return dep(T[n].par)+1;

}


int hei(int n){

  int right=0,left=0;
  if(T[n].right == -1 && T[n].left == -1) return 0;

  if(T[n].right != -1) right = hei(T[n].right)+1;
  if(T[n].left != -1) left = hei(T[n].left)+1;

  if(left > right) return left;

  else return right;

}

Measured memory_bytes: 604
//vinay
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const ll mod = 1e9+7;
#define flash ios_base::sync_with_stdio(false);cin.tie(0);
// C++ program to print all 
// permutations with duplicates allowed 
typedef pair<int, int > pii;
const int INF = 1e9+5;

int main(){
  int n;
  cin >> n;
  ll a[n];
  for(ll i = 0; i < n; i++){
      cin >> a[i];
  }
  ll sum = 0, mx = 0;
  for(ll i = 1; i < n; i++){
       
       if(a[i] < a[i-1]){
           sum += a[i-1]-a[i];
           a[i] = a[i-1];
       }
    }
    cout << sum << endl;
     

}

Measured memory_bytes: 5020
N=input()
K=int(input())
m=len(N)
a=0
if K==3:
    for i in range(1,m-2):
        a+=i*(i+1)
    a//=2
    a*=729
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                for b in range(m-2):
                    for c in range(m-2-b):
                        if N>=str(i)+"0"*b+str(j)+"0"*c+str(k)+"0"*(m-3-b-c):
                            a+=1
elif K==1:
    if int(N)<10:
        a=int(N)
    else:
        a=9
        for i in range(2,m):
            a+=9
        for i in range(1,10):
            if N>=str(i)+"0"*(m-1):
                a+=1
else:
    for i in range(1,m-1):
        a+=i
    a*=81
    for i in range(1,10):
        for j in range(1,10):
            for k in range(m-1):
                if N>=str(i)+"0"*k+str(j)+"0"*(m-2-k):
                    a+=1
print(a)

Measured memory_bytes: 45916
usrInput = int(input())
kosuu = []

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

for n in range(usrInput):
    counting = n + 1
    divisors = make_divisors(counting)
    if len(divisors) == 8 and counting % 2 == 1:
        kosuu.append(counting)

print(len(kosuu))

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

int main() {
  int N, A, num, min = 32;
  cin >> N;
  
  for (int i = 0; i < N; i++){
    cin >> A;
    num = 0;
    while (A % 2 == 0){
      A = A / 2;
      num += 1;
    }
    if (min < num)
      continue;
    else
      min = num;
  }
  cout << min << endl;
}


Measured memory_bytes: 3652
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include <algorithm>
#include<initializer_list>
using namespace std;
#define ul unsigned long long

#define rup(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define rdn(i, a, b) for(int (i) = (a); (i) > (b); (i)--)

int main() {
	vector<char> bucket = vector<char>(5000, 0);
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		bucket[s[i]]++;
	}
	for (char i = 'a'; i <= 'z'; i++) {
		if (bucket[i] == 0) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}





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

int main(){
   int n,m;
   cin>>n>>m;
   vi s(m);
   vector<char> c(m);
   rep(i,m){
     cin>>s.at(i)>>c.at(i);
   }
   int a,b;
   if(n==1){
     a=0;
     b=10;
   }else{
    a=1;
    rep(i,n-1){
      a*=10;
    }
    b=a*10;
   }
   if(m==0){
     cout<<a<<endl;
     return 0;
     }
   for(int i=a;i<b;i++){
     string S=to_string(i);
     int j=0;
     while(true){
       if(S.at(s.at(j)-1)!=c.at(j)){
         break;
       }
       else if(j==m-1){
         cout<<S<<endl;
         return 0; 
       }
       j++;
     }
   }
   cout<<-1<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n;
    cin >> n;
    vector<vi> a(n,vi(n));
    rep(i,n)rep(j,n)cin >> a[i][j];

    vector<vi> tate,yoko;
    tate = yoko = a;
    rep(i,n)rep(j,n-1){
        tate[j+1][i] += tate[j][i];
        yoko[i][j+1] += yoko[i][j];
    }

    int ans = -INF;
    rep(i,n)loop(j,i,n){

        /*
            左端が l のとき
            + (tate[j-1][l] - tate[i][l]) - yoko[i][l-1] - yoko[j][l-1]
            右端が r のとき
            + (tate[j-1][r] - tate[i][r]) - (yoko[i][n-1] - yoko[i][r]) - (yoko[j][n-1] - yoko[j][r])
        */

        // l = r のとき
        rep(l,n){
            int tmp = yoko[i][l] + yoko[j][l];
            if(l)tmp -= yoko[i][l-1] + yoko[j][l-1];
            if(i < j)tmp += tate[j-1][l] - tate[i][l];
            if(i == j)tmp /= 2;
            ans = max(ans, tmp);
        }

        // l < r のとき
        int geta = yoko[i][n-1] + yoko[j][n-1];// i 行目と j 行目を選択
        vi ma(n,0);// ma[r] := 右端が r 列目以降であるときの最大値
        if(i < j)ma[n-1] = tate[j-1][n-1] - tate[i][n-1]; // r = n-1 のとき
        for(int r = n-2; r >= 0; r--){
            int tmp = 0;
            if(i < j)tmp = (tate[j-1][r] - tate[i][r]);
            tmp -= (yoko[i][n-1] - yoko[i][r]) + (yoko[j][n-1] - yoko[j][r]);
            ma[r] = max(ma[r+1], tmp);
        }

        int sum = -INF;
        rep(l,n){ // 左端を l にしたときの最大値
            int tmp = 0;
            if(i < j)tmp = (tate[j-1][l] - tate[i][l]);
            if(l)tmp -= yoko[i][l-1] + yoko[j][l-1];
            if(l < n-1)tmp += ma[l+1];
            sum = max(sum, tmp);
        }

        int tmp = geta + sum;
        if(i == j)tmp /= 2;
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}



Measured memory_bytes: 5000
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        int N = Integer.parseInt(lines[0]);
        lines = br.readLine().split(" ");
        ArrayList<Integer> ppl = new ArrayList<Integer>();
        for(String line:lines){
            ppl.add(Integer.parseInt(line));
        }
        Collections.sort(ppl);
        
        int min = 0;
        int max = N-1;
        int ans = 0;
        while(min<=max){
            int ave = (min+max)/2;
            if(check(ppl,ave)){
                max = ave-1;
                ans = ave;
            }else{
                min = ave+1;
            }
        }
        System.out.println(N-ans);
    }
    private static boolean check(ArrayList<Integer> ppl,int idx){
        int base = ppl.get(idx);
        int max = ppl.get(ppl.size()-1);
        int n=0;
        while(base*2 >= ppl.get(n)){
            if(n!=idx)
                base += ppl.get(n);
            ++n;
            if(base*2 >= max){
                return true;
            }
        }
        return false;
    }
    
}

Measured memory_bytes: 48300
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.solve();
	}

	void solve() throws Exception {
		try (Scanner cin = new Scanner(System.in)) {
			String str = cin.next();

			System.out.println(test(str.substring(0, str.length() - 1)));
		} finally {
		}
	}

	int test(String str) {
		int ans;

		if (str.length() % 2 != 0) {
			ans = test(str.substring(0, str.length() - 1));
		} else {
			if (str.substring(0, str.length() / 2).equals(str.substring(str.length() / 2))) {
				ans = str.length();
			} else {
				ans = test(str.substring(0, str.length() - 2));
			}
		}

		return ans;
	}

}


Measured memory_bytes: 20948
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n);
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

int
main(void){
  ll a, b, h;
  cin >> a >> b >> h;
    
  cout << (a+b)*h/2 << endl;

  
  return 0;
}


Measured memory_bytes: 256
x, k, d = gets.split.map(&:to_i)
x = x.abs
n = x / d

if k < n
  puts x - k * d
  exit
end

x = (x - n * d).abs

if (k - n) % 2 == 0
  puts x
else
  x = (x - d).abs
  puts x
end


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

int N, K;

int main(){
	cin >> N >> K;
	int h[N + 1000], dp[N + 1000];
	for (int i = 1; i <= N; i++){
		cin >> h[i];
		dp[i] = 1e9 + 7;
	}
	dp[1] = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= K; j++){
			dp[i + j] = min(abs(h[i] - h[i + j]) + dp[i], dp[i + j]); 
		}
	}
	cout << dp[N] << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;
typedef long long ll;

struct Bug{
	int out,in;
	bool operator <(const Bug &a)const{
		return in>a.in;
	}
};

int N;
Bug b[300000];

bool isTokyo(int k){
	multiset<int> latte;
	ll sum = 0;
	for(int i=0;i<N;i++){
		if(latte.size()<k-1){
			sum += b[i].out; latte.insert(b[i].out); continue;
		}
		if((double)(sum+b[i].out)/(double)k<=(double)b[i].in) return true;
		if(latte.size()==0) continue;
		multiset<int>::iterator max_ = latte.end(); max_--;
		if(*max_>b[i].out){
			sum -= *max_;
			latte.erase(max_);
			sum += b[i].out;
			latte.insert(b[i].out);
		}
	}
	return false;
}

signed main(){
	cin>>N;
	for(int i=0;i<N;i++) cin>>b[i].out>>b[i].in;
	sort(b,b+N);
	int l=0, r=N+1;
	while(l+1 != r){
		int piv = (l+r)/2;
		if(isTokyo(piv)) l = piv;
		else r = piv;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 17468
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>
#include <new>

using namespace std;

#define EPS (1e-9)
#define INF (1e9)
#define MOD (ll)(1e9 + 7)
#define PI (acos(-1))
#define REP(i,a,n) for(int i=a;i<n;i++)
#define rep(i, n) REP(i,0,n)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" ; "IMPOSSIBLE")

using ll = long long int;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll beki(ll a, ll b) {
    ll tmp = 1;
    rep(i, b) tmp *= a;
    return tmp;
}

ll modPow(ll x, ll a) {
    if (a == 1) return x;
    if (a % 2) return (x * modPow(x, a - 1)) % MOD;
    ll t = modPow(x, a / 2);
    return ((t % MOD) * (t % MOD)) % MOD;
}

ll modInv(ll x) {
    return modPow(x, MOD - 2);
}

ll K, N;
vector<ll> A(200010);

int main() {
    cin >> K >> N;
    rep(i, N) cin >> A[i];

    ll tmp = K - A[N - 1];
    ll ans = tmp + A[0];
    rep(i, N - 1) {
        ans = max(ans, A[i + 1] - A[i]);
    }

    cout << K - ans << endl;
}

Measured memory_bytes: 4612
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#define endl '\n'
#define ll long long

using namespace std;

int main(void)
{
        cin.tie(NULL); ios_base::sync_with_stdio(false);
        int N, K; cin >> N >> K; vector<int> vec(N, 0);
        for(int i = 0; i < N; i++) cin >> vec[i];

        int ret = 1;
        N = max(0, N - K);

        ret += N / (K-1);
        if(N % (K-1)) ret += 1;
        cout << ret << endl;

        return 0;
}


Measured memory_bytes: 640