akhauriyash/Code-Regression huggingface dataset:
n = int(input())
s = input()

v1 = [100]*10
v2 = [0]*10
v3 = [0]*10

out = 0

for i in range(len(s)):
  idx = int(s[i])
  if v3[idx] > 0:
    out += v3[idx]
    v3[idx] = 0
  if v2[idx] > 0:
    for j in range(len(v2)):
      v3[j] += v2[idx]//10
    v2[idx] = 0
  if v1[idx] > 0:
    for j in range(len(v2)):
      v2[j] += v1[idx]//10
    v1[idx] = 0

print(out)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
int main()
{
	int n;
	cin>>n;
	int arr[n];
	map<int,int> m;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
		m[arr[i]]++;
	}
	int cnt=n;
	for(int i=0;i<n;i++)
	{
		if(m[1]>0 && arr[i]!=1)
		{
			cnt--;
		}
		else if(m[arr[i]]>1)
		{
			cnt--;
		}
		else
		{
			for(int j=2;j<=sqrt(arr[i]);j++)
			{
				if(arr[i]%j==0)
				{
					if(arr[i]/j == j)
					{
						if(m[j]>0)
						{
							cnt--;
							break;
						}
					}
					else
					{
						if(m[j]>0)
						{
							cnt--;
							break;
						}
						if(m[arr[i]/j]>0)
						{
							cnt--;
							break;
						}
					}
				}
			}
		}
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 33096
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define mod 1000000007
using ll = long long;
using namespace std;
int modPow(ll a, ll n, ll p) { //繰り返し二乗法 a**n % p
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  ll t = modPow(a, n / 2, p);
  return (t * t) % p;
}
ll choose(ll n, ll k){
  ll num = 1;
  ll waru = 1;
  for(ll i = 0; i < k; i++){
    num *= n - i;
    waru *= i + 1;
    num %= mod;
    waru %= mod;
  }
  waru = modPow(waru, mod - 2, mod);
  return num * waru % mod;
}

int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll ans = modPow(2, n, mod) - 1;
  ans -= choose(n, a);
  ans -= choose(n, b);
  while(ans < 0) ans += mod;
  cout << ans % mod << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 200010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

//------------------------------------------------------

int f(int a) {
    if (a % 2 == 0) return a / 2;
    else return 3 * a + 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s;
    cin >> s;
    int ans = 1;
    int used[10000] = {};
    while (!used[s]) {
        used[s] = true;
        s = f(s);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

void __print(int x) {cerr << x;}; void __print(long x) {cerr << x;}; void __print(long long x) {cerr << x;}; void __print(unsigned x) {cerr << x;}; void __print(unsigned long x) {cerr << x;}; void __print(unsigned long long x) {cerr << x;}; void __print(float x) {cerr << x;}; void __print(double x) {cerr << x;}; void __print(long double x) {cerr << x;}; void __print(char x) {cerr << '\'' << x << '\'';}; void __print(const char *x) {cerr << '\"' << x << '\"';}; void __print(const string &x) {cerr << '\"' << x << '\"';}; void __print(bool x) {cerr << (x ? "true" : "false");}

#define int             long long
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define endl            '\n'
#define pb              push_back
#define all(x)          x.begin(),x.end()
#define ff              first
#define ss              second
#define in(arr)         for(int i=0;i<(int)(sizeof(arr)/sizeof(int));i++) cin >> arr[i];
#define out(arr)        for(int i=0;i<(int)(sizeof(arr)/sizeof(int));i++) cout << arr[i];

//Some Helpful Function
int powmod(int a, int b) {int res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;}
int string_to_int(string s) {int ans = 0; int p = 1; for (int i = s.size() - 1; i >= 0; i--) {ans += (s[i] - '0') * p; p *= 10;} return ans;}
int fast_pow(int a, int b) {if (b == 1) return a; if (b == 0) return 1; int x = fast_pow(a, b / 2); x *= x; if (b & 1) x *= a; return x;}

//DEBUGGING-LINES
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

void t_c_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("inp.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif*/
	int n, d; cin >> n >> d;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		if ((x * x + y * y) <= d * d) {
			ans++;
		}
	}
	cout << ans << endl;

}

int32_t main()
{
	t_c_c();
	return 0;
}


Measured memory_bytes: 3644
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    static long[] lc;
    static long[] rc;
    static long[] lcMax;
    static long[] rcMax;
    static long[] x;
    static long[] v;
    static int n;
    static long c;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        c = sc.nextLong();
        x = new long[n];
        v = new long[n];
        lc = new long[n + 1];
        rc = new long[n + 1];
        lcMax = new long[n + 1];
        rcMax = new long[n + 1];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextLong();
            v[i] = sc.nextLong();
        }
        for (int i = 0; i < n; i++) {
            lc[i + 1] = lc[i] + v[i];
        }
        for (int i = 0; i < n; i++) {
            lc[i + 1] -= x[i];
        }
        for (int i = 0; i < n; i++) {
            rc[i + 1] = rc[i] + v[n-1-i];
        }
        for (int i = 0; i < n; i++) {
            rc[i + 1] -= rX(n-1-i);
        }
        for (int i = 0; i < n; i++) {
            lcMax[i + 1] = Math.max(lcMax[i], lc[i + 1] - x[i]);
        }
        for (int i = 0; i < n; i++) {
            rcMax[i + 1] = Math.max(rcMax[i], rc[i + 1] - rX(n-1-i));
        }

        List<Long> ret = new ArrayList<>();
        ret.add(0l);
        for (int i = 0; i < n; i++) {
            long score = lc[i + 1];
            ret.add(score);
//            ret = Math.max(ret, score);
            score += rcMax[n - i - 1];
            ret.add(score);
//            ret = Math.max(ret, score);
        }
        for (int i = 0; i < n; i++) {
            long score = rc[i + 1];
            ret.add(score);
//            ret = Math.max(ret, score);
            score += lcMax[n - i - 1];
            ret.add(score);
//            ret = Math.max(ret, score);
        }
    System.out.println(ret.stream().mapToLong(Long::longValue).max().getAsLong());
    }

    public static long rX(int i) {
        return c - x[i];
    }
}


Measured memory_bytes: 98852
import itertools
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
ans=[0]*(n+1)

for i in range(len(s)-1):
  if s[i]+s[i+1]=="AC":
    ans[i+1]=1
ansr=list(itertools.accumulate(ans))

for i in range(q):
  if ans[lr[i][1]]==1:
    print(ansr[lr[i][1]]-ansr[lr[i][0]-1]-1)
  else:
    print(ansr[lr[i][1]]-ansr[lr[i][0]-1])


Measured memory_bytes: 33040
def countryRoad
  n, k = gets.split.map(&:to_i)
  house = gets.split.map(&:to_i)

  # 発電機の数が家の数以上なら電線は必要ない.
  if k >= n
    p 0
    return
  end

  # 隣り合う家の距離を計算する.
  # その後、発電機の個数kだけ電線を分割できるので、距離の長い場所から
  # k-1個除外していって和を求める.
  p house[0,n-1].zip(house.rotate(1)[0,n-1]).map!{|a| a[1]-a[0]}.sort![0,(n-k)].inject(:+)
end

if __FILE__ == $0
  gets.to_i.times do
    countryRoad
  end
end

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

using namespace std;

int n,m,res,mm;

int main() {
	cin >> n >> m;
	mm = min(m/n,(int)sqrt(m)+1);
	for(int i = 1;i <= mm;i++) {
		if(m % i == 0) {
			res = max(res,i);
			if(m/i <= m/n) {
				res = max(res,m/i);
			}
		}
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n,a[100010];
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	ll cnt=0;
	for(ll i=0;i<n;i++){
		cnt*=-1;
		cnt+=a[i];
	}
	ll ans=cnt/2;
	cout << ans*2<<" ";
	for(ll i=0;i<n-1;i++){
		ans*=-1;
		ans+=a[i];
		cout << 2*ans<<" ";
	}
	// your code goes here
	return 0;
}

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

int main() {
    int n;
    while (cin >> n) {
        int prev_max[100][100] = {{0}};
        int ans = -100000;
        for (int i = 0; i < n; i++) {
            int sum[101] = {0};
            for (int j = 0; j < n; j++) {
                int x;
                cin >> x;
                sum[j + 1] = sum[j] + x;
            }
            for (int j = 0; j < n; j++) {
                for (int k = j; k < n; k++) {
                    // j列からk列までを考える
                    // sum[k + 1] - sum[j] == (i行目のj列からk列までの和)
                    // 0 => 前までの行は使わない場合
                    // prev_max[j][k] => 前までの行の最大値を使った場合
                    prev_max[j][k] = max(0, prev_max[j][k]) + sum[k + 1] - sum[j];
                    ans = max(ans, prev_max[j][k]);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1208
n=int(input())
A=list(map(int,input().split()))

dp=[0]*n
dp[0]=1000

for i in range(1,n):
    dp[i]=dp[i-1]
    for j in range(i):
        add=(dp[j]//A[j])*(A[i]-A[j])
        dp[i]=max(dp[i],dp[j]+add)

print(dp[n-1])



Measured memory_bytes: 9072
input_line = input()
abk = input_line.split(" ") 
ABK = [int(n) for n in abk]



if ABK[0] + ABK[1] <= ABK[2]:
    A = 0
    B = 0

elif ABK[0] <= ABK[2] and ABK[1] > ABK[2] - ABK[0]:
    A = 0
    B = ABK[1] -  (ABK[2] - ABK[0])

elif ABK[0] > ABK[2]:
    A = ABK[0] - ABK[2]
    B = ABK[1]

    
print(A," ",B)



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
map<pair<ll,ll>,ll> mp;
ll f(ll i,ll x) {
  if(x==0) return 0;
  if(i==0) return 1;
  if(mp.count({i,x})) return mp[{i,x}];
  ll a=(1LL<<i+1)-3;
  ll res;
  if(x==1) res=0;
  else if(x<a+2) res=f(i-1,x-1);
  else res=f(i-1,a)+f(i-1,x-a-2)+1;
  mp[{i,x}]=res;
  return res;
}
int main(){
  ll n,x;
  cin>>n>>x;
  cout<<f(n,x)<<endl;
}


Measured memory_bytes: 3676
#102_D
N=int(input())
A=list(map(int,input().split()))
s=0
AS=[]
for i in range(N):
    s+=A[i]
    AS.append(s)
#尺取り法
Ans=AS[N-1]+1
L=0
R=2
for Mid in range(1,N-2):
    Sum_L=AS[Mid]
    Sum_R=AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L])>abs(Sum_L-2*AS[L+1]):
        L+=1
    
    while R<=N-3 and abs(AS[N-1]-2*AS[R]+AS[Mid])>abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R+=1
    P=AS[L]
    Q=AS[Mid]-AS[L]
    S=AS[R]-AS[Mid]
    T=AS[N-1]-AS[R]
    #print(Mid,L,R,abs(max(P,Q,S,T)-min(P,Q,S,T)))
    Ans=min(Ans,abs(max(P,Q,S,T)-min(P,Q,S,T)))
print(Ans)

Measured memory_bytes: 25068
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int k, x;
  cin >> k >> x;
  cout << (500 * k >= x ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < n; i++)
#define forr(i,a,n) for(int i = a; i<= n; i++)
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define all(u) u.begin(),u.end()
#define lli long long int
#define ld long double

using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<vi> vvi;

lli n;
lli act = 100;
int days = 0;
int main(){__
	cin >> n;
	while(act < n){
		act += act/100;
		days++;
	}
	cout << days << '\n';
	return 0;
}



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


int main() {
    int N;
    cin>>N;
    map<string,int>mp;
    vector<string>data(N);
    rep(i,N){
        cin>>data[i];
        mp[data[i]]++;
    }
    int mx=0;
    for(auto p:mp){
        mx =max(mx,p.second);
    }
    for(auto p:mp){
        if(p.second!=mx)continue;
        cout<<p.first<<endl;
    }
}

Measured memory_bytes: 26752
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

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

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M, L;
	cin >> N >> M >> L;

	vector<vector<int>> dist(N, vector<int>(N, INF));
	vector<vector<int>> cost(N, vector<int>(N, INF));

	for (int i = 0; i < N; i++) dist[i][i] = 0;
	for (int i = 0; i < N; i++) cost[i][i] = 0;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		dist[a][b] = c;
		dist[b][a] = c;
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				chmin(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			if (dist[i][j] <= L) cost[i][j] = 1;
		}
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				chmin(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}

	DMP(cost);

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int s, t;
		cin >> s >> t;
		s--, t--;
		auto tmp = cost[s][t];
		if (tmp != INF) cout << tmp - 1 << "\n";
		else cout << -1 << "\n";
	}

	return 0;
}

Measured memory_bytes: 1280
import java.io.*;
import java.util.*;
public class Main
{
	final int inf=(int)(1e9+1);
	private void solve()throws IOException
	{
		int A=nextInt();
		int B=nextInt();
		int M=nextInt();
		int a[]=new int[A+1];
		int b[]=new int[B+1];
		int mina=inf,minb=inf;
		for(int i=1;i<=A;i++)
		{
			a[i]=nextInt();
			mina=Math.min(mina,a[i]);
		}
		for(int i=1;i<=B;i++)
		{
			b[i]=nextInt();
			minb=Math.min(minb,b[i]);
		}
		long ans=mina+minb;
		for(int i=1;i<=M;i++)
		{
			int x=nextInt();
			int y=nextInt();
			int c=nextInt();
			ans=Math.min(ans,a[x]+b[y]-c);
		}
		out.println(ans);
	}

	 
	///////////////////////////////////////////////////////////

	public void run()throws IOException
	{
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		solve();

		br.close();
		out.close();
	}
	public static void main(String args[])throws IOException{
		new Main().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws IOException{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws IOException{
		return br.readLine();
	}
	int nextInt()throws IOException{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws IOException{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws IOException{
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 52448
//abc076_b.cpp
//Sat Jun  9 11:17:36 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;

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

	int num = 0;
	int board = 1;

	while (num<n){
		int x = board * 2;
		int y = board + k;
		if (x < y){
			board = x;
		}else {
			board = y;
		}
		num++;
	}

	cout << board << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    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] = R[n2] = SENTINEL;
    int i = 0, j = 0;
    for(int k = left; k < right; k++){
        cnt++;
        if(L[i] <= R[j]){
            A[k] = L[i++];
        } else {
        A[k] = R[j++];    
        
        }
    }
}

void mergeSort(int A[], int n, int left, int right){
    if(left+1 < right){
        int mid = (left + right)/2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

int main() {
    int A[MAX], n, i;
    cnt = 0;
    cin >> n;
    for(i = 0; i<n; i++) cin >> A[i];
    mergeSort(A, n, 0, n);
    for(i = 0; i<n; i++){
        if(i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << cnt << endl;
    
    return 0;
}



Measured memory_bytes: 7008
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class B {
    static StreamWriter Out = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static void Main(string[] args) {
        string S;
        Input(out S);
        if (IsP(S) && IsP(S.Substring(0, S.Length / 2)) && IsP(S.Substring((S.Length + 3) / 2 - 1, S.Length / 2))){
            Print("Yes");
        } else {
            Print("No");
        }
        Out.Flush();
    }
    static bool IsP(string s) {
        bool b = true;
        for (int i = 0; i < s.Length / 2; i++) {
            if (s[i] != s[s.Length - 1 - i]) {
                b = false;
            }
        }
        return b;
    }
    static T ChangeT<T>(string s) => (T)Convert.ChangeType(s, typeof(T));
    static void Input<A>(out A a) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
    }
    static void Input<A, B>(out A a, out B b) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
    }
    static void Input<A, B, C>(out A a, out B b, out C c) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
    }
    static void Input<A, B, C, D>(out A a, out B b, out C c, out D d) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
    }
    static void Input<A, B, C, D, E>(out A a, out B b, out C c, out D d, out E e) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
    }
    static void Input<A, B, C, D, E, F>(out A a, out B b, out C c, out D d, out E e, out F f) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
        f = ChangeT<F>(words[5]);
    }
    static void Inputs<T>(out T[] array) {
        array = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries).Select(s => ChangeT<T>(s)).ToArray();
    }
    static void Print<T>(T s) => Out.WriteLine(s);
    static void Print<T>(params T[] s) => Out.WriteLine(string.Join(" ", s));
    static void Print<T>(IEnumerable<T> e) => Out.WriteLine(string.Join(" ", e));
}

Measured memory_bytes: 11220
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>

typedef long long ll;
using std::vector;
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) {
    vec.resize(len);
    for (auto &v : vec) ndarray(v, args...);
}

int main() {
    //std::ifstream in("0_normal_2");
    //std::cin.rdbuf(in.rdbuf());
    
    ll N, K, Q;
    std::cin >> N >> K >> Q;
    
    vector<ll> score(N, K-Q);
    for (int i = 0; i < Q; i++) {
        int a;
        std::cin >> a;
        score[a-1] += 1;
    }
    
    for (int i = 0; i < N; i++) {
        if (score[i] > 0) {
            std::cout << "Yes" << std::endl;
        } else {
            std::cout << "No" << std::endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 1408
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
bool chmax(T & a, const T & b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T & a, const T & b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

using namespace std;
int main(){
	int K, A, B;
	int sum = 0;
	cin >> K >> A >> B;
	int mk = A / K;
	for (int i = 0; i <= 1000; i++) {
		sum += K;
		if (A <= sum) {
			if (A <= sum && sum <= B) {
				cout << "OK" << endl;
				break;
			}
			else {
				cout << "NG" << endl;
				break;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3624
def print_chessboard(h,w)
  line_odd = "#."*(w/2)
  line_odd += "#" if w % 2 == 1
  line_even = line_odd.gsub("#",",").gsub(".","#").gsub(",",".")

  h.times do |i|
    next puts line_odd if i % 2 == 0
    puts line_even
  end
  puts ""
end

loop do
  h,w = gets.split.map(&:to_i)
  break if h == 0 && w == 0
  print_chessboard(h,w)
end


Measured memory_bytes: 6876
#include <bits/stdc++.h>
#define modp 1000000007
#define Maxn 2000007
using namespace std;
int pre[Maxn],inv[Maxn];
int n;
int power(int a,int b)
{
	int res=1,now=a,left=b;
	while (left>0)
	{
		if (left%2==1) res=(1LL*res*now)%modp;
		left/=2;
		now=(1LL*now*now)%modp;
	}
	return res;
}
int calc(int x,int y)
{
	if (y<0||y>x) return 0;
	if (y==0||y==x) return 1;
	int res=(1LL*pre[x]*inv[y])%modp;
	return (1LL*res*inv[x-y])%modp;
}
int main()
{
	scanf("%d",&n);
	pre[0]=1;
	for (int i=1;i<=2000000;i++)
		pre[i]=(1LL*i*pre[i-1])%modp;
	inv[2000000]=power(pre[2000000],modp-2);
	for (int i=2000000;i;i--)
		inv[i-1]=(1LL*i*inv[i])%modp;
	int ans=0;
	for (int i=1;i<n;i++)
	{
		int del=(1LL*pre[i]*pre[n-1-i])%modp;
		del=(1LL*del*calc(i-1,n-1-i))%modp;
		ans=(ans+del)%modp;
	}
	ans=(pre[n]-ans+modp)%modp;
	printf("%d\n",ans);
	return 0;
}


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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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


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

    if( A==B ) cout << C << endl;
    else if( A==C) cout << B<< endl;
    else cout << A << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n';

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

	ll temp = 0, flag = 0;
	while(n--){
		ll t1, t2;
		cin >> t1 >> t2;
		if(t1 == t2){
			temp++;
		}else{
			temp = 0;
		}

		if(temp == 3){
			flag = 1;
		}
	}

	if(flag == 1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

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

int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    long long m = *min_element(a, a+n), s = accumulate(a, a+n, 0LL) - m;
    if (n % 2) cout << ((m + s) % 2 ? "First\n" : "Second\n");
    else cout << (m % 2 || s % 2 ? "First\n" : "Second\n");
}



Measured memory_bytes: 3852
n, m = [int(x) for x in input().split()]
a = [[int(x) for x in input().split()] for y in range(n)]
b = [int(input()) for x in range(m)]
c = [0 for i in range(n)]

for i in range(n):
    c[i] = sum([a[i][x] * b[x] for x in range(m)])

for i in c:
    print(i)

Measured memory_bytes: 8084
use std::io::*;//Not mine.
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main(){
    let a:i32 = read();
    let b:i32 = read();
    let c:i32 = read();
    let x:i32 = read();
    let mut cnt = 0;
    for i in 0..a + 1{
        for j in 0..b + 1{
            for k in 0..c + 1{
                if(i * 500 + j * 100 + 50 * k == x){
                    cnt += 1;
                }
            }
        }
    }
    println!("{}", cnt);
}

Measured memory_bytes: 4352
#include<cstdio>
int main(void)
{
  char A[101],B[101],C[101];
  scanf("%s",A);
  scanf("%s",B);
  scanf("%s",C);
  
  int ai = 0;
  int bi = 0;
  int ci = 0;
  
  char x;	
  x=A[0];
  
  while(1){
    if(x=='a'){
      if(A[ai]=='\0'){
        printf("A");
        break;
      }
      else{
        x=A[ai];
		ai++;
      }
    }
		
    else if(x=='b'){
      if(B[bi]=='\0'){
        printf("B");
		break;
      }
      else{
        x=B[bi];
		bi++;
      }
    }
    
    else if(x=='c'){
      if(C[ci]=='\0'){
        printf("C");
		break;
      }
      else{
		x=C[ci];
		ci++;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
    vector<int> t;
    int a;
    while (cin >> a)
    {
        if (a != 0)
        {
            t.push_back(a);
        }
        else if (a == 0)
        {
            cout << t.back() << endl;
            t.pop_back();
        }
    }
}



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

using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

template<typename T> ostream& operator << (ostream& os, vector<T> v) {
  for (auto& i : v) os << i << " "; return os; 
}
template<typename T> istream& operator >> (istream& is, vector<T>& v) {
  for (auto& i : v) is >> i; return is;
}
template<typename K, typename V> ostream& operator << (ostream& os, unordered_map<K, V> m) {
  for (auto& i : m) os << i.first << ":" << i.second << endl; return os;
}
template<typename T> inline bool chmin(T& x, T y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
template<typename T> inline bool chmax(T& x, T y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  sort(a.begin(), a.end());
  int mid = n / 2;
  cout << a[mid] - a[mid-1] << endl;
  return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
		sc.close();
		String ans[] = { "Yes", "No"};
		int an = 0;
		if(a + b < c)an = 1;
		System.out.println(ans[an]);
	}

}


Measured memory_bytes: 22996
from collections import defaultdict, deque

N, K = map(int, input().split())

neighbor = defaultdict(list)

for i in range(N-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

d = deque([(0, -1)])

ans = K
mod = 10**9 + 7
while d:
    cur, par = d.pop()

    i = 1 if par == -1 else 2
    for n in neighbor[cur]:
        if n != par:
            d.append((n, cur))
            ans *= (K-i)
            ans %= mod
            i += 1

print(ans)

Measured memory_bytes: 102120
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
aint = lambda: int(input())
ints = lambda: list(map(int, input().split()))

n = aint()
a = ints()
c = [0]*n
for i in range(n-1):
    c[a[i]-1]+=1
d = deque(c)
for i in range(n):
    print(d.popleft())

Measured memory_bytes: 33848
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class SWAG(object):
    def __init__(self,dot):
        self.__front=[]; self.__back=[]; self.__dot=dot

    def __bool__(self):
        return bool(self.__front or self.__back)

    def __len__(self):
        return len(self.__front)+len(self.__back)

    def append(self,x):
        back=self.__back
        if(not back): back.append((x,x))
        else: back.append((x,self.__dot(back[-1][1],x)))

    def popleft(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front):
            front.append((back[-1][0],back[-1][0]))
            back.pop()
            while(back):
                front.append((back[-1][0],self.__dot(back[-1][0],front[-1][1])))
                back.pop()
        return front.pop()[0]

    def sum(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front): return back[-1][1]
        elif(not back): return front[-1][1]
        else: return self.__dot(front[-1][1],back[-1][1])

def resolve():
    n,m=map(int,input().split())
    S=list(map(int,input()))
    dp=[INF]*(n+1) # dp[i] : i から何手でゴールできるか
    dp[-1]=0

    swag=SWAG(min)
    for i in range(n-1,-1,-1):
        swag.append(dp[i+1])
        if(len(swag)>m): swag.popleft()
        if(S[i]==1): continue
        dp[i]=swag.sum()+1

    if(dp[0]==INF):
        print(-1)
        return

    ans=[]
    now=0
    turn=dp[0]
    for i in range(1,n+1):
        if(dp[i]==INF): continue
        if(turn>dp[i]):
            ans.append(i-now)
            now=i
            turn=dp[i]

    print(*ans)
resolve()

Measured memory_bytes: 80092
b,c,d,r,y;main(q){for(;scanf("%d%d%d%d%d",&q,&b,&c,&d,&r),q;puts("NA"))for(;r;r--)for(y=b/d;~y;y--)r*c+y*d>b|r+y<q||main(printf("%d %d\n",r,y));exit(0);}

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

#define int long long
#define MAXN 200000

int a[MAXN];
int n;
std::vector<int> Adj[MAXN];

int dfs(int u, int p = -1) {
  int ret = a[u];

  if(Adj[u].size() == 1 && p != -1)
    return ret;

  int sum = 0;
  int max = 0;
  for(int j : Adj[u]) {
    if(j == p)
      continue;

    int next = dfs(j, u);

    if(next == -1)
      return -1;

    sum += next;
    max = std::max(max, next);
  }

  ret = 2*a[u] - sum;

  if(ret < std::max(2*max - sum, (int)0) || a[u] > sum)
    return -1;

  return ret;
}

signed main() {
  std::cin >> n;

  for(int i = 0; i < n; i++) 
    std::cin >> a[i];

  int root = 0;
  for(int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    u--; v--;
    Adj[u].push_back(v);
    Adj[v].push_back(u);

    if(Adj[u].size() > 1)
      root = u;
    if(Adj[v].size() > 1)
      root = v;
  }

  if((dfs(root) == 0 && n > 2) || (n == 2 && a[0] == a[1]))
    std::cout << "YES";
  else
    std::cout << "NO";

  std::cout << std::endl;

  return 0;
}


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);
void prime_map(map<ll, ll> &, ll);

int main() {
    int n;
    cin >> n;
    int x[n], y[n];
    rep(i, n) { cin >> x[i] >> y[i]; }

    map<pair<int, int>, int> m;
    rep(i, n) {
        rep(j, n) {
            if (i == j) {
                continue;
            }
            int dif_x = x[i] - x[j];
            int dif_y = y[i] - y[j];
            auto p = make_pair(dif_x, dif_y);
            if (m[p] == 0) {
                m[p] = 1;
            } else {
                m[p] += 1;
            }
        }
    }

    int temp = 0;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        temp = max(temp, iter->second);
    }

    int ans = n - temp;
    cout << ans << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
 
#define mo 1000000007
#define inf 1e18
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rrep(i,s,n) for(ll i=s;i>=n;i--)
#define adiii \                               
  ios_base::sync_with_stdio(false); \                                      
  cin.tie(NULL);  \
  cout.tie(NULL);									
 
ll mod(ll n) { return (n % (ll)mo + (ll)mo)%(ll)mo;}
ll gcd(ll a,ll b) {if (b == 0) return a;return gcd(b, a % b);}

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}



int main(){
	adiii
	ll n;cin>>n;
	vector <ll> a(n+1);
	map <ll,ll> m;
	rep(i,0,n) cin>>a[i];
	vector<ll> temp;
	ll ans=0;
	rep(i,0,n){

			ans += m[i-a[i]];
					//cout<<i<<" "<<" "<<a[i]<<" "<<a[idx]<<" "<<ans<<endl;

		

		m[a[i]+i]++;
	}


	cout<<ans<<endl;
	
}


Measured memory_bytes: 27348
#!/usr/bin/perl

use strict;
use warnings;

my ($n, $k);
{
    my $in = <STDIN>;
    ($n, $k) = split(" ", $in);
}
my @p;
{
    my $in = <STDIN>;
    @p = split(" ", $in);
}
my $max = 0;
my $sum = 0;
for (my $j=0; $j<$k; $j++)
{
    $sum += $p[$j];
}
if ($n>$k)
{
    for (my $i=0; $i<$n-$k+1; $i++)
    {
        $sum = $sum - $p[$i] + $p[$i+$k];
        if ($max<$sum)
        {
            $max = $sum;
        }    
    }
}
else
{
    $max = $sum;
}
$max = ($max+$k)/2;
print "$max\n";

Measured memory_bytes: 33060
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = s.length();
    if (s[0] == '0' || s[n - 1] == '1') {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 0, j = n - 2; i < j; ++i, --j) {
        if (s[i] != s[j]) {
            cout << -1 << '\n';
            return 0;
        }
    }

    vector<pair<int,int>> res;
    vector<int> pars(n, -1);
    {
        int u = n;
        int p = n - 1;
        res.emplace_back(u, p);
        u = p;
        for (int i = 2; i < n; ++i) {
            if (s[i - 1] == '1') {
                --p;
                res.emplace_back(u, p);
                u = p;
            } else {
                --p;
                res.emplace_back(u, p);
            }
        }
    }
    for (auto& e : res) {
        cout << e.first << ' ' << e.second << '\n';
    }


    return 0;
}

Measured memory_bytes: 2884
N,K,Q = map(int,input().split())
A = [0] * Q
for i in range(Q):
    A[i] = int(input())
    
judge = [K-Q] * N
for j in A:
    judge[j-1] += 1

for k in judge:
    if k > 0:
        print("Yes")
    else:
        print("No")


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

int main(){
  while(true){
    int x,y,s;
    int mx = 0;
    cin>>x>>y>>s;
    if(x==0&&y==0&&s==0) break;
    for(int t=1;t<s;t++){
      for(int u=1;u<s;u++){
        if((t*(100+x)/100+u*(100+x)/100)==s){
          mx = max(mx,(t*(100+y)/100+u*(100+y)/100));
        }
      }
    }
    cout<<mx<<endl;
  }
  return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int n,a[N],f[N];
LL dp[N][N];
bool vis[N][N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i],f[i]=i;
	sort(f+1,f+1+n,[](int x,int y){
		return a[x]>a[y];
	});
	vis[0][0]=1;
	LL ans=0;
	for(int i=1;i<=n;i++){
		int x=f[i];
		for(int j=0;j<i;j++){
			int l=j,r=i-1-j;
			if(vis[l][r]){
				dp[l+1][r]=max(dp[l+1][r],dp[l][r]+1ll*abs(l+1-x)*a[x]);
				dp[l][r+1]=max(dp[l][r+1],dp[l][r]+1ll*abs(x-(n-r))*a[x]);
				vis[l+1][r]=vis[l][r+1]=1;
				// cout<<"------------"<<i<<' '<<x<<' '<<a[x]<<' '<<abs(x-(n-r))*a[x]<<' ';
				// cout<<l<<  ' '<<r<<' '<<dp[l+1][r]<<' '<<dp[l][r+1]<<endl;
			}
		}		
	}
	for(int i=0;i<=n;i++){
		ans=max(ans,dp[i][n-i]);
	}
	cout<<ans<<'\n';
 	return 0;
}

Measured memory_bytes: 30244
// D - Dice in Line
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N,K; scanf("%d%d",&N,&K);
	int P[N+K] = {}; rp(i,0,N) scanf("%d",P+i+K);
	int ans = 0, sum = 0;
	rp(i,0,N) ans = max(ans, sum += P[i+K] - P[i]);
	printf("%.12f\n",(ans+K)/2.0);
}

Measured memory_bytes: 1792
//Created by Aminul on 7/5/2020.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();
        long sum = 0, min = Long.MAX_VALUE;
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        shuffle(arr);
        Arrays.sort(arr);

        sum += arr[n - 1];
        for (int i = n - 2, j = 1; i >= 0 && j < n - 1; i--) {
            sum += arr[i];
            j++;
            if (j < n - 1) {
                sum += arr[i];
                j++;
            }
        }

        pw.println(sum);
        pw.close();
    }

    public static void shuffle(int[] a) {
        Random rnd = new Random();
        for (int i = a.length - 1; i >= 1; i--) {
            int j = rnd.nextInt(i + 1);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}

Measured memory_bytes: 50696
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  string s;
  cin>>s;
  Int n=s.size();
  Int ans=0;
  for(Int i=0;i<n-i-1;i++)
    ans+=s[i]!=s[n-i-1];
  cout<<ans<<endl;
  return 0;
}


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

typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int l,r;
int p[124];

int32_t main()
{
    IOS
    cin>>l>>r;
    p[0]=1;
    for (int i=1;i<=120;i++) p[i]=p[i-1]*3%mod;
    for (int i=62;i>=0;i--)
    {
        if ((((1ll<<i)&l)^((1ll<<i)&r))!=0) break;
        if (l&(1ll<<i)) l^=(1ll<<i),r^=(1ll<<i);
    }
    int ans=0;
    int high,low;
    for (int i=62;i>=0;i--)
    {
        if ((1ll<<i)&r)
        {
            high=i;
            break;
        }
    }
    for (int i=62;i>=0;i--)
    {
        if ((1ll<<i)&l)
        {
            low=i;
            break;
        }
    }

    if (l==r&&l==0) return cout<<1<<endl,0;
    else if (l==0)
    {
        int now=1;
        for (int i=high;i>=0;i--)
        {
            if ((1ll<<i)&r) ans=(ans+p[i]*now)%mod,now=(now*2)%mod;
        }
        ans=(ans+now)%mod;
        cout<<ans<<endl;
    }
    else
    {
        int now=1;
        for (int i=high-1;i>=0;i--)
        {
            if ((1ll<<i)&r) ans=(ans+p[i]*now)%mod,now=(now*2)%mod;
        }
        ans=(ans+now)%mod;
        now=1;
        for (int i=low-1;i>=0;i--)
        {
            if (!((1ll<<i)&l)) ans=(ans+p[i]*now)%mod,now=(now*2)%mod;
        }
        ans=(ans+now)%mod;
        for (int i=low+1;i<=high-1;i++) ans=(ans+p[i])%mod;
        cout<<ans<<endl;
    }

}



Measured memory_bytes: 256
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static final int unvisited = 0;
	public static final int visiting = 1;
	public static final int visited = 2;

	public static boolean dfs(int node, boolean[][] adj, int[] state, LinkedList<Integer> list){
	    state[node] = visiting;
	    
	    for(int i = 0; i < adj.length; i++){
	        if(!adj[node][i]){ continue; }
	        else if(state[i] == unvisited){
	            if(!dfs(i, adj, state, list)){ //
	                state[node] = visited; return false;
	            }
	        }else if(state[i] == visiting){ //cycle!
	            return false;
	        }
	    }
	    
	    state[node] = visited;
	    list.addFirst(node);
	    return true;
	}

	public static boolean topological_sort(boolean[][] adj, LinkedList<Integer> list){
	    int[] state = new int[adj.length];
	    for(int i = 0; i < adj.length; i++){
	        state[i] = unvisited;
	    }
	    for(int i = 0; i < adj.length; i++){
	        if(state[i] == unvisited){
	            if(!dfs(i, adj, state, list)){
	                return false;
	            }
	        }
	    }
	    return true;
	}
	
	
	public static class UnionFind{
	    int[] par; // 
	    
	    public UnionFind(int n){
	        par = new int[n];
	        for(int i = 0; i < n; i++){ par[i] = -1; }
	    }
	    
	    public int find(int x){
	        if(par[x] < 0){
	            return x;
	        }else{
	            return par[x] = find(par[x]);
	        }
	    }
	    
	    public boolean union(int x, int y){
	        x = find(x);
	        y = find(y);
	        
	        if(x != y){
	            if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
	                int tmp = x; x = y; y = tmp;
	            }
	            par[x] += par[y];
	            par[y] = x;
	            return true;
	        }else{
	            return false;
	        }
	    }
	    
	    public boolean same(int x, int y){
	        return find(x) == find(y);
	    }
	    
	    public int size(int x){
	        return -par[find(x)];
	    }
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		final int m = sc.nextInt();
		
		boolean[][] adj = new boolean[n][n];
		
		for(int i = 0; i < m; i++){
			final int win  = sc.nextInt() - 1;
			final int lose = sc.nextInt() - 1;
			
			adj[win][lose] = true;
		}
		
		LinkedList<Integer> result = new LinkedList<Integer>();
		final boolean is_valid = topological_sort(adj, result);
		
		boolean order = true;
		int pre = -1;
		for(int ret : result){
			if(pre != -1 && !adj[pre][ret]){
				order = false;
				break;
			}
			pre = ret;
		}
		
		for(int ret : result){
			System.out.println(ret + 1);
		}
		System.out.println(order ? 0 : 1);
	}

}

Measured memory_bytes: 122224