akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	long MODULO = 1_000_000_000 + 7;

	void run() {
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] t = new int[n];
		int[] p = new int[n];
		int[] x = new int[s];
		for (int i = 0; i < s; ++i) {
			x[i] = sc.nextInt();
		}
		for (int i = 0; i < n; ++i) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
			--p[i];
		}
		int[] w = new int[n];
		for (int i = 0; i < n; ++i) {
			w[i] = t[i] - x[p[i]];
		}
		Arrays.sort(w);
		long ans = 0;
		for (long v : w) {
			ans -= v;
		}
		long[][] f = new long[n + 1][m + 1];
		for (int i = 0; i < f.length; ++i) {
			for (int j = 0; j < f[i].length; ++j) {
				f[i][j] = Integer.MAX_VALUE / 16;
			}
		}
		for (int i = 1; i < f.length; ++i) {
			f[i][1] = w[i - 1] * i;
		}

		for (int j = 2; j <= m; ++j) {
			// j is fixed.
			// Attention: h[i][k]:=f[k][j-1]+w[i-1]*(i-k) is of Monge.
			// min(h[i][]) can be enumerated in O(n*log(n))
			// f[i][j]=min(h[i][])
			long[] v = calc(f, w, j);
			for (int i = 1; i <= n; ++i) {
				// for (int k = 1; k <= i - 1; ++k) {
				// f[i][j] = Math.min(f[i][j], h(f, w, i, j, k));
				// }
				f[i][j] = v[i];
			}
		}

		long min = Integer.MAX_VALUE / 16;
		for (int j = 1; j <= m; ++j) {
			min = Math.min(min, f[n][j]);
		}
		ans += min;
		System.out.println(ans);
	}

	long[] calc(long[][] f, int[] w, int j) {
		int n = f.length - 1;
		int m = f[0].length - 1;
		long[] ret = new long[n + 1];
		Arrays.fill(ret, Integer.MAX_VALUE / 16);
		rec(ret, 1, n, 2, n + 1, f, w, j);
		return ret;
	}

	// [low,high)
	// [left,right)
	long rec(long[] ret, int low, int high, int left, int right, long[][] f, int[] w, int j) {
		int mid = (left + right) / 2;// the value of the variable i
		long v = Long.MAX_VALUE / 16;
		int arg = -1;
		for (int k = Math.max(0, low); k <= Math.min(mid - 1, high); ++k) {
			v = Math.min(v, h(f, w, mid, j, k));
			if (v == h(f, w, mid, j, k))
				arg = k;
		}
		if (right - left > 1) {
			rec(ret, low, arg, left, mid, f, w, j);
			rec(ret, arg, high, mid, right, f, w, j);
		}
		ret[mid] = v;
		return v;
	}

	long h(long[][] f, int[] w, int i, int j, int k) {
		return f[k][j - 1] + w[i - 1] * (i - k);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

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

int main() {
    int x,y;
    cin>>x>>y;

    vector<int>a{1,3,1,2,1,2,1,1,2,1,2,1};

    if(a[x-1]==a[y-1]){
        cout<<"Yes"<<endl;
    }
    else {
        cout<<"No"<<endl;
    }

}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int H,i,A[100000];
  scanf("%d",&H);
  for(i=1;i<=H;i++){
    scanf("%d",&A[i]);
  }
  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(i/2>=1){
      printf("parent key = %d, ",A[i/2]);
    }
    if(2*i<=H){
      printf("left key = %d, ",A[i*2]);
    }
    if(2*i+1<=H){
      printf("right key = %d, ",A[i*2+1]);
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2104
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = 205;
int n;
char tmp[maxn];
string s;
long long a[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }
  scanf("%s", tmp);
  s = tmp;
  return true;
}

const int maxb = 60;
long long x[maxb];

void solve() {
  for (int i = 0; i < maxb; i++) {
    x[i] = -1;
  }
  for (int i = n - 1; i >= 0; i--) {
    long long y = a[i];
    for (int j = 0; j < maxb; j++) {
      if ((y & (1ll << j)) && x[j] != -1) {
        y ^= x[j];
      }
    }
    if (s[i] == '0') {
      if (y) {
        int bit = 0;
        while (!(y & (1ll << bit))) {
          bit++;
        }
        for (int j = 0; j < maxb; j++) {
          if (x[j] != -1 && (x[j] & (1ll << bit))) {
            x[j] ^= y;
          }
        }
        x[bit] = y;
      }
    } else {
      if (y) {
        printf("1\n");
        return;
      }
    }
  }
  printf("0\n");
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  int t;
  scanf("%d", &t);
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 3664
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); }

const int MAXN = 5000;
const int MOD = 1000000007;
void inc(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }
void dec(int &a, int b) { if ((a -= b) < 0) a += MOD; }

int n;
vector<int> adj[MAXN];

// sum(e subset of E: (-1)^|e|*(ways to make pairs without crossing any edge in e))
// sum(ei subset of Ei: (-1)^sum(|ei|)*prod(ways to make pairs in part of Ti not reachable without crossing any edge in ei)*(ways to make pairs in reachable parts without crossing any edge in e1))
// dp[i][k]=sum(ei subset of Ei: (-1)^|ei|*(ways to make pairs not reachable without crossing any edge in ei) | #nodes in reachable part = k)

int f[MAXN + 1];
vector<int> dp[MAXN];
void dfs(int at, int par) {
	dp[at] = vector<int>(2); dp[at][0] = 0, dp[at][1] = 1;
	REPSZ(i, adj[at]) {
		int to = adj[at][i]; if (to == par) continue;
		dfs(to, at);
		vector<int> ndp = vector<int>(SZ(dp[at]) + SZ(dp[to]) - 1);
		REPSZ(j, dp[at]) REPSZ(k, dp[to]) {
			int ways = (ll)dp[at][j] * dp[to][k] % MOD;
			// include edge
			inc(ndp[j + k], ways);
			// exclude edge
			dec(ndp[j], (ll)ways*f[k] % MOD);
		}
		dp[at] = ndp;
	}
	FORSZ(j, 1, dp[at]) dec(dp[at][0], (ll)dp[at][j] * f[j] % MOD);
}

void run() {
	scanf("%d", &n);
	REP(i, n - 1) { int a, b; scanf("%d%d", &a, &b); --a, --b; adj[a].PB(b), adj[b].PB(a); }

	f[0] = 1; FORE(i, 1, n) f[i] = i % 2 == 1 ? 0 : (ll)(i - 1) * f[i - 2] % MOD;
	dfs(0, -1);
	int ret = 0; FORSZ(j, 1, dp[0]) inc(ret, (ll)dp[0][j] * f[j] % MOD); printf("%d\n", ret);
}

int main() {
	run();
	return 0;
}


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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) std::cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << '\n';
}

void solve() {
    Int n;
    cin >> n;
    vector<Int> a(2 * n);
    for (Int i = 0; i < 2 * n; i++) {
        cin >> a[i];
    }
    sort(all(a));
    Int res = 0;
    for (Int i = 0; i < 2 * n; i += 2) {
        res += a[i];
    }
    print(res);
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3604
N,M=map(int,input().split())
list1=[]
for i in range (M):
    a=list(map(int,input().split()))
    list1.append(a)
P=list(map(int,input().split()))
switch=[0]*N
count=0
for i in range (2**N):
    switch=[0]*N
    ans=0
    for j in range (N):
        if ((i>>j)&1):
            switch[N-1-j]=1
    for l in range(1,M+1):
        con=0
        for k in range(1,len(list1[l-1])):
            con+=switch[list1[l-1][k]-1]
        if con%2!=P[l-1]:
            ans=1
    if ans==0:
        count+=1

print(count)
        

Measured memory_bytes: 9172
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <cmath>
#include <math.h>

using namespace std;

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

	vector<int> as(n);
	int sum = 0;
	for(int i = 0; i < n; i++) {
		cin >> as[i];
		sum += as[i];
	}
	double avg = double(sum) / double(as.size());
	int rounded_avg = round(avg);

	int cost = 0;
	for(int i = 0; i < n; i++) {
		cost += pow((as[i] - rounded_avg), 2);
	}

	cout << cost << endl;
}

Measured memory_bytes: 384
# -*- coding:utf-8 -*-

def solve():
    class UnionFindVerSize():
        def __init__(self, N):
            """ N個のノードのUnion-Find木を作成する """
            # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
            self._parent = [n for n in range(0, N)]
            # グループのサイズ（個数）
            self._size = [1] * N

        def find_root(self, x):
            """ xの木の根(xがどのグループか)を求める """
            if self._parent[x] == x: return x
            self._parent[x] = self.find_root(self._parent[x]) # 縮約
            return self._parent[x]

        def unite(self, x, y):
            """ xとyの属するグループを併合する """
            gx = self.find_root(x)
            gy = self.find_root(y)
            if gx == gy: return

            # 小さい方を大きい方に併合させる（木の偏りが減るので）
            if self._size[gx] < self._size[gy]:
                self._parent[gx] = gy
                self._size[gy] += self._size[gx]
            else:
                self._parent[gy] = gx
                self._size[gx] += self._size[gy]

        def get_size(self, x):
            """ xが属するグループのサイズ（個数）を返す """
            return self._size[self.find_root(x)]

        def is_same_group(self, x, y):
            """ xとyが同じ集合に属するか否か """
            return self.find_root(x) == self.find_root(y)

        def calc_group_num(self):
            """ グループ数を計算して返す """
            N = len(self._parent)
            ans = 0
            for i in range(N):
                if self.find_root(i) == i:
                    ans += 1
            return ans

    N, M = list(map(int, input().split()))
    uf = UnionFindVerSize(N)
    for _ in range(M):
        a, b = list(map(int, input().split()))
        uf.unite(a-1, b-1)

    # 求める答えは、最大グループ数の人数に等しい。
    ans = 0
    for i in range(N):
        ans = max(ans, uf.get_size(i))

    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 18616
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
using namespace std;
#define REP(i,n) for(int i = 0;i < (int)(n);i++)

int main() {
	int n;
	bool flag = false;
	vector<char> s;
	cin >> n;
	s.resize(n);
	REP(i, n) {
		cin >> s[i];
		if (s[i] == 'Y')flag = true;
	}
	if (flag)cout << "Four";
	else cout << "Three";
	return(0);
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>   
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <random>
#include <ctime>
#include <iomanip>
#include <deque>
#include <queue> 
#include <cmath>
#include <cstring>
#include <cassert>
#include <bitset>
#include <unordered_set>
typedef long long ll;
typedef long double ld;
 
using namespace std;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
    int n, ans;
    scanf("%d", &n);
    ans = n;
    vector<int> a(n), l(n + 1);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        l[a[i]] = l[a[i] - 1] + 1;
        ans = min(ans, n - l[a[i]]);
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

vector<ll> fact(1999);

ll fastpow(ll base, ll index)
{
	ll ret = 1;
	while(index)
	{
		if(index & 1) ret = (ret * base) % MOD;
		base = (base * base) % MOD;
		index /= 2;
	}
	return ret;
}

ll ncr(ll n, ll r)
{
	ll ret = fact[n] * fastpow(fact[n - r], MOD - 2) % MOD;
	return ret * fastpow(fact[r], MOD - 2) % MOD;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen(".in.txt", "r", stdin);
	freopen(".out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	fact[0] = 1;
	for(int i = 1; i <= 1998; i++) fact[i] = (i * fact[i - 1]) % MOD;
	ll s, ans = 0; cin >> s;
	for(int i = 0; s - 2 * (i + 1) - 1 >= i; i++)
		ans = (ans + ncr(s - 2 * (i + 1) - 1, i)) % MOD;
	cout << ans;

	return 0;
}

Measured memory_bytes: 3656
a = list(input())
a = [int(i) for i in a]
for bit in range(1<<3):
    ans = a[0]
    ans1 = []
    for i in  range(3):
        mask = 1<<i
        if mask&bit:
            ans = (ans+a[i+1])
            ans1.append('+')
        else:
            ans = (ans-a[i+1])
            ans1.append('-')
    
    if ans==7:
        ans2 = ans1
ans3 = []
for i in range(3):
    ans3.append(str(a[i]))
    ans3.append(ans2[i])
ans3.append(str(a[3]))
ans3.append('=7')
ans4 =''.join(ans3)
print(ans4)

Measured memory_bytes: 38384
N = int(input())
p = list(map(int, input().split()))

M = [i for i in range(1, N+1, 1)]

count = 0
for i in range(N):
  if p[i] != M[i]:
    count += 1
if count == 2 or count == 0:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 9060
#include "bits/stdc++.h"
using namespace std;

int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	long long ans = max({1LL * b * d, 1LL * a * d, 1LL * c * b, 1LL * a * c});
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main() {

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


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define SORT(c) sort((c).begin(),(c).end())
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define reprs(i, m, n) for(int i = n; i >= m; i--)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;

int main(){

  int N;
  cin >> N;

  multiset<ll> se;
  int ct=0;
  ll a;
  rep(i,N){
    cin>>a;
    if(se.lower_bound(a)!=se.begin()){
      se.erase(prev(se.lower_bound(a)));
    }
    se.insert(a);
  }

  cout << se.size() <<endl;
  return 0;
}


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

using namespace std;

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

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	// ｶｲｾﾂﾁｮｯﾄﾐﾀ

	int d, g;
	cin >> d >> g;

	vector<int> p(d), c(d);
	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
	}

	int pSum = accumulate(begin(p), end(p), 0);

	// dp[i番目][問題数]
	vector<vector<int>> dp(d + 1, vector<int>(pSum + 1));

	for (int i = 1; i <= d; i++) {
		for (int j = 1; j <= pSum; j++) {
			int ma = dp[i - 1][j];
			for (int k = j - 1; k >= 0; k--) {
				if (k < j - p[i - 1]) {
					break;
				}

				if (k == j - p[i - 1]) {
					// コンプリート
					ma = max(ma, dp[i - 1][k] + (j - k) * 100 * i + c[i - 1]);
				} else {
					// 通常得点
					ma = max(ma, dp[i - 1][k] + (j - k) * 100 * i);
				}
			}
			dp[i][j] = ma;
		}
	}

	for (int i = 0; i <= pSum; i++) {
		if (dp[d][i] >= g) {
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
'use strict'
function main(input) {
  input = Number(input.trim())
  let ans = ''
  while (Math.abs(input) > 0) {
    if (Math.abs(input % 2)){
      if (ans.length % 2 === 1) {
        input++
      } else {
        input--
      }
      ans = '1' + ans
    } else {
      ans = '0' + ans
    }
    input = input / 2
  }
  console.log(ans || '0')
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<ll> A(n), B(n);
  vector<int> id(n);
  rep(i, n) {
    cin >> A[i] >> B[i];
    id[i] = i;
  }
  sort(all(id), [&](int i, int j) {
      return A[i]+B[i] > A[j]+B[j];
    });
  ll ans = -accumulate(all(B), 0LL);
  rep(i, n) if(i%2==0) ans += A[id[i]]+B[id[i]];
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 5288
// By Mohit Gupta
#include <bits/stdc++.h>
using namespace std;
//DEBUG 
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define printint(v) copy(begin(v), end(v), ostream_iterator<int>(cout," "))
#define printintv(s,e) copy(s,e, ostream_iterator<int>(cout," "))
#define forstl(i,v) for(auto &i: v)
#define all(v) (v).begin(), (v).end()
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for ll)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define pb push_back
#define fi first
#define se second
#define int long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
#pragma GCC optimize ("-O2")
const int LIM = 5e5+5, MOD = 998244353;
int t,n,m,k,x,y;
 
 
int32_t main()
{
    IOS;
    cin>>n;
    v32 h(n+1);
    map<int,vector<int> > right;
    forsn(i,1,n+1){
      cin>>h[i];
      if(right.find(i-h[i])==right.end()) right[i-h[i]]=v32();
      right[i-h[i]].pb(i);
    }
    int ans=0;
    forsn(i,1,n+1){
      int val=i+h[i];
      if(right.find(val)!=right.end()){
        v32 &v= right[val];
        ans+=v.end()-lower_bound(v.begin(),v.end(),val);
      }
    }
    cout<<ans<<ln;
}


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

public class Main{
	public static void main(String[]args)throws IOException{
	
		BufferedReader br=
				new BufferedReader(new InputStreamReader(System.in));
		String str1=br.readLine();
		String[] str2 = str1.split(" ");
		int time=Integer.parseInt(str2[0])+Integer.parseInt(str2[1]);
		if(time>=24){
		  time=time-24;
		}
		System.out.println(time);
	}
}	



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

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
#define REP(i, n)  for(int i = 0; i < n; ++i)
#define FOR(i, t, n)  for(ll i = t; i <= (ll)n; ++i)
struct edge {
    int from, to;
    ll cost;
};


class Eratosthenes {
public:
    vector<bool> prime;

    Eratosthenes(ll size) {
        size = max((int) sqrt(size) + 1, 101010);
        prime.resize(size, 1);
        prime[0] = 0;
        prime[1] = 0;
        for (size_t i = 2; i * i <= size; ++i)
            if (prime[i]) {
                for (size_t j = 2; i * j <= size; ++j)prime[i * j] = false;
            }
    }
};


class Combination {
    vector<ll> fac; //n!(mod M)
    vector<ll> ifac; //k!^{M-2} (mod M)
public:
    Combination(ll size) {
        fac.resize(size);
        ifac.resize(size);
        fac[0] = 1;
        ifac[0] = 1;
        for (ll i = 0; i < size; i++) {
            fac[i + 1] = fac[i] * (i + 1) % MOD;
            ifac[i + 1] = ifac[i] * mpow(i + 1, MOD - 2) % MOD;
        }
    }

    ll mpow(ll x, ll n) {
        ll ans = 1;
        while (n != 0) {
            if (n & 1) ans = ans * x % MOD;
            x = x * x % MOD;
            n = n >> 1;
        }
        return ans;
    }

    ll comb(ll a, ll b) {
        if (a == 0 && b == 0)return 1;
        if (a < b || a < 0)return 0;
        ll tmp = ifac[a - b] * ifac[b] % MOD;
        return tmp * fac[a] % MOD;
    }
};


ll GCD(ll a, ll b) {
    if (b == 0)return a;
    return GCD(b, a % b);
}

ll LCM(ll a, ll b) {
    ll gcd = GCD(a, b);
    return a / gcd * b;
}

ll N;

int func(string s) {
    int cnt = 0;
    REP(i, s.size()) {
        int t = i;
        while (i < s.size() && s[i] == s[t])t++;
        cnt += (t - i) / 2;
        i = t - 1;
    }
    return cnt;
}

int main() {
    string s;
    cin >> s;
    cin >> N;
    char b = s[0];
    bool f = 1;
    REP(i, s.size())if (b != s[i])f = 0;
    if (f) {
        cout << s.size() * N / 2 << endl;
        return 0;
    }
    ll cnt1 = func(s), cnt2 = func(s + s);
    cout << cnt1 + (N - 1) * (cnt2 - cnt1) << endl;
    return 0;
}

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

int main() {
  int H , W;
  cin >> H >> W;
  vector<string> v(H);
  for (int i = 0; i < H; i++){
    cin >> v.at(i);
  }
  for (int i = 0; i < W + 2; i++){
    cout <<"#";
  }
  cout << endl;
  for (int i = 0; i < H; i++){
    cout << "#" << v.at(i)<< "#" ; 
    cout << endl;
  }
  for (int i = 0; i < W + 2; i++){
    cout <<"#";
  }
}


Measured memory_bytes: 256
string = input()
if string[0] == string[1] and string[2] == string[3]\
and string[0] != string[2]:
  print("Yes")
elif string[0] == string[2] and string[1] == string[3]\
and string[0] != string[1]:
  print("Yes")
elif string[0] == string[3] and string[1] == string[2]\
and string[0] != string[1]:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
n, l = map(int, input().split())
a = list(map(int, input().split()))

if n == 2:
	if a[0] + a[1] < l:
		print("Impossible")
	else:
		print("Possible")
		print(1)

else:
	nagai = 0
	for i in range(n - 1):
		if a[i] + a[i + 1] > nagai:
			nagai = a[i] + a[i + 1]
			nagai_index = i + 1

	if nagai < l:
		print("Impossible")
	else:
		print("Possible")
		for i in range(1, nagai_index):
			print(i)
		for i in range(n - 1, nagai_index, -1):
			print(i)
		print(nagai_index)

Measured memory_bytes: 14432
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);
    vector<ll> a(n + 1);
    int i;
    for (i = 0; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    vector<ll> b0(n + 1), b1(n + 1);
    for (i = n; i >= 0; i--) {
        if (i == n) {
            b0[i] = b1[i] = a[i];
        }
        else {
            b0[i] = (b0[i + 1] + 1) / 2 + a[i];
            b1[i] = b1[i + 1] + a[i];
        }
    }
    if (b0[0] != 1) {
        printf("-1\n"); return;
    }

    ll ans = 1;
    ll curr = 1;
    for (i = 1; i <= n; i++) {
        curr *= 2;
        curr = MIN(curr, b1[i]);
        ans += curr;
        curr -= a[i];
    }
    printf("%lld\n", ans);
    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 5144
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a > b)
            System.out.println("a > b");
        else if (a < b)
            System.out.println("a < b");
        else if (a == b)
            System.out.println("a == b");
    }
}



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

class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		int[][] A = new int[n][m];
		int[] B = new int[m];
		int[] C = new int[n];

		for(int i=0; i<n; i++){
			str = br.readLine().split(" ");
			for(int j=0; j<m; j++){
				A[i][j] = Integer.parseInt(str[j]);
			}
		}
		for(int i=0; i<m; i++){
			B[i] = Integer.parseInt(br.readLine());
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				C[i] += A[i][j]*B[j];
				//System.out.print(A[i][j]);
			}
		}
		for(int i=0; i<n; i++){
			System.out.println(C[i]);
		}
	}
}

Measured memory_bytes: 27716
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <list>
#include <stack>

using namespace std;

/* constant */

const int INF = 1 << 30;
const int mod = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

/* function */

/* main */
int main() {

    int a, b, c; cin >> a >> b >> c;
    
    if (a > b) {
        swap(a, b);
    }
    if (b > c) {
        swap(b, c);
    }
    if (a > b) {
        swap(a, b);
    }
    cout << a << ' ' << b << ' ' << c << '\n';
}



Measured memory_bytes: 3120
def root(x):
    if x == parent[x]:
        return x
    y = root(parent[x])
    dist[x] += dist[parent[x]]
    parent[x] = y
    return y
def unite(x, y, d):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
        dist[py] = dist[x] - dist[y] - d
    else:
        parent[px] = py
        dist[px] = dist[y] - dist[x] + d

n, m = map(int, input().split())
*parent, = range(n)
dist = [0]*n
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1; r -= 1
    if root(l) == root(r):
        if dist[l] - dist[r] != d:
            print("No")
            exit(0)
    else:
        unite(l, r, d)
print("Yes")


Measured memory_bytes: 9324
def getprimes(n):
  primes = []
  for i in xrange(2, n+1):
    isprime = True
    for j in xrange(len(primes)):
      if i % primes[j] == 0:
        isprime = False
        break
    if isprime:
      primes.append(i)
  return primes

n = int(raw_input())
primes = getprimes(10000)
count = 0
for _ in xrange(n):
  x = int(raw_input())
  isprime = True
  for i in xrange(len(primes)):
    if primes[i] >= x:
      break
    if x % primes[i] == 0:
      isprime = False
      break
  if isprime:
    count += 1
print count

Measured memory_bytes: 6392
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		int[] data = new int[5];
		for (int i=0; i < 5; i++) {
			data[i] = sc.nextInt();
		}

		mergeSort(data, 0, 5);

		System.out.print(data[0]);
		for (int i=1; i < 5; i++) {
			System.out.print(" " + data[i]);
		}
		System.out.println();
	}

	public static void mergeSort(int[] array, int l, int r) {
		if (l+1 == r) return;

		int m = (l+r) / 2;
		mergeSort(array, l, m);
		mergeSort(array, m, r);
		merge(array, l, m, r);
	}

	private static void merge(int[] array, int l, int m, int r) {
		int[] sorted = new int[r-l];
		int i = l;
		int j = m;
		int k = 0;
		while ( k < r-l) {
			if (i == m) {
				sorted[k] = array[j];
				j++;
			} else if (j == r) {
				sorted[k] = array[i];
				i++;
			} else if (array[i] < array[j]) {
				sorted[k] = array[j];
				j++;
			} else {
				sorted[k] = array[i];
				i++;
			}
			k++;
		}

		for (int index=0; index < r-l; index++) {
			array[l+index] = sorted[index];
		}
	}
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, p;
  cin >> n >> p;
  int f = 0;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if(a % 2) f = 1;
  }
  ll k = 1;
  rep(i, 0, n) k *= 2;
  if(f) {
    cout << k / 2 << endl;
  }else {
    if(p) cout << 0 << endl;
    else cout << k << endl;
  }
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

Ld = []
Rd = []

for i in range(M):
	Ld.append(LR[i][0])
	Rd.append(LR[i][1])

if max(Ld) <= min(Rd):
	print(min(Rd) - max(Ld) + 1)
else:
	print(0)

Measured memory_bytes: 29092
n=int(input())
cost=list(map(int, input().split()))
dp=[0]*n
dp[0]=0
dp[1]=abs(cost[1]-cost[0])
for i in range(2,n):
	dp[i]=min(abs(cost[i]-cost[i-1]) + dp[i-1], abs(cost[i]-cost[i-2])+dp[i-2])
print(dp[n-1])

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

int main(){
  int n;
  cin >> n;
  string str;
  cin >> str;
  vector<vector<int>> dp(5005, vector<int>(5005, 0));
  for(int i=n-1; i>=0; --i){
    for(int j=n-1; j>=0; --j){
      if(str[i] == str[j]) dp[i][j] = dp[i+1][j+1] + 1;
      else dp[i][j] = 0;
    }
  }
  int res = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i<j){
        int check = min(dp[i][j], j-i);
      	res = max(res, check);
      }
    }
  }
  cout << res << endl;
  return 0;
}
  
  
  

Measured memory_bytes: 98432
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};




int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll n;cin>>n;
  vl a(n);
  rep(i,n)cin>>a[i];
  ll q;cin>>q;
  vl b(q),c(q);
  rep(i,q)cin>>b[i]>>c[i];
  ll sum=0;
  map<ll,ll>M;
  rep(i,n){
    sum+=a[i];
    M[a[i]]++;

  }
  rep(i,q){
    sum-=M[b[i]]*b[i];
    sum+=M[b[i]]*c[i];
    //M[b[i]]=0;
    M[c[i]]+=M[b[i]];
    M[b[i]]=0;
    cout<<sum<<endl;
  }
}

Measured memory_bytes: 11676
#include <sys/time.h>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <cctype>

using namespace std;

using ll = long long;
using i_i = pair<int, int>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
const ll mod = 1000000007LL;


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

	ll dp[n + 1][2][2];

	rep(i, n + 1) rep(j, 2) rep(k, 2) {
		dp[i][j][k] = 0;
	}


	dp[0][0][0] = 1;

	rep(i, n) {

		dp[i + 1][0][0] = (dp[i][0][0] * 8) % mod;
		dp[i + 1][0][1] = (dp[i][0][0] + dp[i][0][1] * 9) % mod;
		dp[i + 1][1][0] = (dp[i][0][0] + dp[i][1][0] * 9) % mod;
		dp[i + 1][1][1] = (dp[i][1][0] + dp[i][0][1] + dp[i][1][1] * 10) % mod;
	}



	cout << dp[n][1][1] << endl;


	return 0;
}


Measured memory_bytes: 34268
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R PI = acos(-1.0);


int main(void){
	int n;
	cin >> n;
	vector<ll> x(n), y(n);
	rep(i, n) cin >> x[i] >> y[i];

	using state = tuple<R, int>;
	vector<state> ary;

	rep(i, n) {
		if(x[i] == 0 and y[i] == 0) continue;
		ary.push_back(state(atan2(y[i], x[i]), i));
	}

	const int m = ary.size();
	sort(begin(ary), end(ary));

	rep(i, m) {
		state entry = ary[i];
		get<0>(entry) += 2.0L * PI;
		ary.push_back(entry);
	}

	ll cx = 0LL, cy = 0LL;
	R ans = 0.0;
	int pos = 0;

	rep(is, m) {
		const int i = get<1>(ary[is]);
		
		{
			const R tmp = sqrt(cx * cx + cy * cy);
			chmax(ans, tmp);
		}
			
		while(pos < is + m) {
			const int j = get<1>(ary[pos]);
			const ll dot = x[i] * x[j] + y[i] * y[j];
			const ll det = x[i] * y[j] - y[i] * x[j];
			
			if(det < 0 or (det == 0 and dot < 0)) break;
			cx += x[j], cy += y[j];
			const R tmp = sqrt(cx * cx + cy * cy);
			chmax(ans, tmp);
			
			pos++; 
		}		
		
		cx -= x[i], cy-= y[i];
	}

	cout.precision(20);
	cout << fixed << ans << endl;

	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cmath>
typedef long long llong;
using namespace std;
const int mod = 1000000007;
llong pow(llong x, llong n)
{
	if (n == 0)
		return 1;
	else if (n % 2 == 0)
		return pow(x*x%mod, n / 2);
	else
		return pow(x*x%mod, n / 2)*x%mod;

}
int main()
{
	llong x, n;
	cin >> x >> n;
	cout << pow(x,n) << endl;
}


Measured memory_bytes: 3072
import java.util.*;

public class Main {

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

    int n = stdIn.nextInt();
    int [] s = new int [n];

    s[2] = n % 10; n /= 10;
    s[1] = n % 10; n /= 10;
    s[0] = n % 10;

    for(int i = 0; i < 3; i ++){
      if (s[i] == 1){
        s[i] = 9;
      } else {
        s[i] = 1;
      }
    }
    int goal = 100 * s[0] + 10 * s[1] + s[2];



    System.out.println(goal);

  }
}


Measured memory_bytes: 22996
#include<iostream>
#include<math.h> 
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long int lli;
lli mod=1000000007;
vector < lli> primes;

void Sieve(lli n) 
{ 
    bool prime[n+1];
	for(lli i=0;i<n+1;++i)
		prime[i]=true;
    for (lli p=2;p*p<=n;++p) 
    {
        if (prime[p] == true) 
        {  
            for (lli i=2*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    }  
    for(lli p=2; p<=n; p++) 
       if (prime[p]) 
		primes.push_back(p);  
}
lli gcd(lli a,lli b)  
 {
    if(b>a)
        swap(a,b);
    if (a%b==0)  
        return b;  
    else 
        return gcd(a%b,b);  
 }
lli power(lli x,lli y,lli m)   
{ 
    lli res = 1; 
    x=x%m;   
    while (y > 0) 
    {  
        if (y%2==1) 
            res =(res*x)%m;  
        y=y/2; 
        x=(x*x)%m; 
    } 
    return res; 
}

int main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
	lli n;
	cin>>n;
	lli a[n],b[n],c[n-1];
	lli last=-1;
	for(lli i=0;i<n;++i)
	{
		cin>>a[i];
	}
	for(lli i=0;i<n;++i)
	{
		cin>>b[i];
	}
	for(lli i=0;i<n-1;++i)
	{
		cin>>c[i];
	}
	lli ans=0;
	for(lli i=0;i<n;++i)
	{
		ans+=b[a[i]-1];
		if(last==a[i]-1)
			ans+=c[last-1];
		last=a[i];
	}
	cout<<ans<<endl;
}

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

int main() {
    string s;
    cin >> s;
    int counter = 0;
    if (s[0] == 'o') ++counter;
    if (s[1] == 'o') ++counter;
    if (s[2] == 'o') ++counter;
    cout << 700+100*counter << endl;
}

Measured memory_bytes: 256
import numpy as np

n = int(input())
x = list(map(int, input().split()))
x = sorted(x)
min = np.inf

for i in range(1, x[-1]+1):
    total = 0
    for j in x:
        total += (j-i)**2
    if total < min:
        min = total

print(min)

Measured memory_bytes: 21216
#include<bits/stdc++.h>
#define int long long int
#define pll pair<int,int>
#define dbl long double
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define eps 0.00000001
#define inf 10000000000001
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define popb() pop_back()
#define popf() pop_front()
#define mp(x,y) make_pair((x),(y))
#define vv(dt) vector<vector<dt>>
#define fastio(x) ios_base::sync_with_stdio(x); cin.tie(NULL)
#define init(v,s) memset(v,s,sizeof(v)) 
#define bug(x) cerr<<"LINE: "<<__LINE__<<" || "<<#x<<" = "<<x<<endl
#define loop(i,s,n) for(auto i=s;i<n;i++)
#define rloop(i,n,b) for(auto i=n-1;i>=b;i--)
using namespace std;
	
signed main()
{
	fastio(0);
	int n;
	cin>>n;
	int a[n];
	loop(i,0,n) cin>>a[i];
	
	int dp[n][n],prefix[n+1];
	init(dp,0);
	init(prefix,0);
	prefix[1] = a[0];
	loop(i,2,n+1) prefix[i] = prefix[i-1] + a[i-1]; 
	// dp[i][j] = min cost for piling up slimes of range [i,j] = min m (dp[i][m] + dp[m+1][j] + prefix[i][j]) , m E [i,j-1].
	for(int j=0;j<n;j++)
	{
		for(int i=j-1;i>=0;i--)
		{
			int mn = inf;
			for(int m=i;m<j;m++)
				mn = min(mn, dp[i][m] + dp[m+1][j]);
			dp[i][j] = mn + prefix[j+1] - prefix[i];
		}
	}

	cout<<dp[0][n-1]<<endl;
	return 0;		
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()

int main() {
  ll x;
  cin>>x;
  if(x>=2000) cout<<1<<endl;
 else{
  rep(a,20){
    rep(b,20){
      rep(c,20){
        rep(d,20){
          rep(e,20){
            if((x-100*a-101*b-102*c-103*d-104*e)%105==0&&(x-100*a-101*b-102*c-103*d-104*e)>=0){
              cout<<1<<endl;
              return 0;
            }
          }
        }
      }
    }
  }
 cout<<0<<endl;
 }
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned int uint;

int main() {
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n, n) {
        uint num = n, sum = 0, p;
        for (int i=0; i<n; ++i) {
            cin >> p;
            sum += p;
        }
        vector<uint> joint;
        uint j;
        for (int i=0; i<n-1; ++i) {
            cin >> j;
            joint.push_back(j);
        }
        sort(joint.begin(), joint.end(), greater<uint>());
        uint res = sum * n;
        for (int i=0; i<n-1; ++i) {
            sum += joint[i];
            num -= 1;
            if (res < sum * num) {
                res = sum * num;
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1612
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include <map>
using namespace std;

int main(){
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());

  int N;
  cin>>N;

  //vector< pair<string,int> > S(N);
  map<string,int> m;

  int MAX=0;

  for(int i=0;i<N;i++){
    string X;
    cin>>X;
    //S.at(i).first = X;
    //S.at(i).second++;
    m[X]++;
      if(MAX<=m[X]){
        MAX = m[X];
      }
  }
  
  //cout<<MAX<<endl;

  for(auto itr = m.begin(); itr != m.end(); ++itr) {
    if(itr->second==MAX) cout << itr->first<<endl;
  }
 
}

Measured memory_bytes: 25216
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args) {
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		
		if(C >= A && C <= B) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

	static class FastScanner {
	    private final InputStream in = System.in;
	    private final byte[] buffer = new byte[1024];
	    private int ptr = 0;
	    private int buflen = 0;
	    private boolean hasNextByte() {
	        if (ptr < buflen) {
	            return true;
	        }else{
	            ptr = 0;
	            try {
	                buflen = in.read(buffer);
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	            if (buflen <= 0) {
	                return false;
	            }
	        }
	        return true;
	    }
	    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
	    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
	    public String next() {
	        if (!hasNext()) throw new NoSuchElementException();
	        StringBuilder sb = new StringBuilder();
	        int b = readByte();
	        while(isPrintableChar(b)) {
	            sb.appendCodePoint(b);
	            b = readByte();
	        }
	        return sb.toString();
	    }
	    public long nextLong() {
	        return Long.parseLong(next());
	    }
	    public int nextInt(){
	    	return Integer.parseInt(next());
	    }
	}
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
#define forloop(n) for(int i = 0; i < n; i++)
#define ll long long
 
#define mod 1000000007
long long exp(long long taban, long long us) {
    long long carpan = taban;
    long long temp = us;
    long long res = 1;
    for(int i = 0;;i++){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
        if(temp == 0) break;
    }
    return res;
}
ll ebob(ll a, ll b){
	if(!a)return b;
	return ebob(b%a, a);
}
ll ekok(ll a, ll b){
	return (((a*b)%mod)*(exp(ebob(a,b), (ll)mod-2))) % mod;
}

void fonk(vector<vector<int>>& vec, ll dp[][2], int r, int dont){
	ll topb = 1, top = 1;
	for(auto x: vec[r]){
		if(x != dont){
			fonk(vec, dp, x, r);
			topb = (topb * dp[x][0]) % mod;
			top = (top * ((dp[x][0] + dp[x][1]) % mod)) % mod;
		}
	}
	if(!(dp[r][0] = top)) dp[r][0]++;
	if(!(dp[r][1] = topb)) dp[r][1]++;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	vector<vector<int>> vec(n+1);
	ll dp[n+1][2] = {};
	
	for(int i = 0; i < n-1; i++){
		int a, b; cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	fonk(vec, dp, 1, -1);
	cout<<(dp[1][0] + dp[1][1])%mod;
	return 0;
}


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

int main(void){
    int n, oldt = 0, oldx = 0, oldy = 0;
    int t[100001], x[100001], y[100001];
    bool can = true;
    string ans;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> t[i] >> x[i] >> y[i];
    for(int i = 0; i < n; i++){
        int dt = t[i] - oldt;
        int dist = abs(x[i] - oldx) + abs(y[i] - oldy);
        if(dist > dt){
            can = false;
            break;
        }
        if(dist % 2 == dt % 2){
            oldt = t[i]; oldx = x[i]; oldy = y[i];
        } else {
            can = false;
            break;
        }
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 4744
#include <iostream>
#include <algorithm>
using namespace std;
int sx,sy,gx,gy;
int field[22][22];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void watch(void){
	for(int y=0;y<22;y++){
		for(int x=0;x<22;x++){
			cout << field[x][y] <<' ';
		}
		cout << endl;
	}
	return ;
}

int move( int nfield[22][22],int n,int x,int y){
	int num=11,tem;
	int mfield[22][22];
	if(n > 10)
		return n;
	if(x==gx&&y==gy)
		return n;

	for(int i=0;i<22;i++)
		for(int j=0;j<22;j++)
			mfield[i][j]=nfield[i][j];

/*	for(int b=0;b<8;b++){
		for(int a=0;a<8;a++){
			cout << mfield[a][b] <<' ';
		}
		cout << endl;
	}*/

	for(int i=0;i<4;i++){
		if(mfield[x+dx[i]][y+dy[i]]==0||mfield[x+dx[i]][y+dy[i]]==3){
			int j=x,k=y;
			while(mfield[j+dx[i]][k+dy[i]]==0)
					j+=dx[i],k+=dy[i];
		//	cout << j << " "  << k << endl;
			if(mfield[j+dx[i]][k+dy[i]]==3)
				num=min(move( mfield,n+1,j+dx[i],k+dy[i]),num);
			else if(mfield[j+dx[i]][k+dy[i]]==1){
				mfield[j+dx[i]][k+dy[i]]=0;
				num=min(move( mfield,n+1,j,k),num);
				mfield[j+dx[i]][k+dy[i]]=1;
			}
		}
	}
	// cout << num << endl;
	return num;
}

int main(void){
	int w,h;
	int result;
	while(cin >> w >> h,w|h){
		for(int y=0;y<=h+1;y++){
			for(int x=0;x<=w+1;x++){
				if(x==0||x==w+1||y==0||y==h+1)
					field[x][y]=4;
				else
					cin >> field[x][y];
			}
		}
	//	watch();
		for(int y=0;y<=h;y++){
			for(int x=1;x<=w;x++){
				if(field[x][y]==2)
					sx=x,sy=y,field[x][y]=0;
				if(field[x][y]==3)
					gx=x,gy=y;
			}
		}
	//	cout << sx <<' '<< sy << ' '<< gx <<' '<< gy << ' '<<endl;
		result=move(field,0,sx,sy);
		if(result==11)
			result=-1;
		cout << result << endl;
	}
	return 0;
}

Measured memory_bytes: 1180
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v[2][100000];
int n, w, h, x, y, p[40000], r[40000], f, ans;

int find(int x){
  if(p[x] == x) return x;
  else return p[x] = find(p[x]);
}

bool unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return false;
  if(r[x] < r[y]) p[x] = y;
  else{
    p[y] = x;
    if(r[x] == r[y]) r[x]++;
  }
  return true;
}

main(){
  cin >> n >> w >> h;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    x--; y--;
    if(min(x, y) == 0 || x == w - 1 || y == h - 1) f = 1;
    v[0][y].push_back(i);
    v[1][x].push_back(i);
  }
  for(int i=0;i<n;i++){
    p[i] = i;
    r[i] = 0;
  }
  for(int i=0;i<h;i++) for(int j=1;j<v[0][i].size();j++) if(unite(v[0][i][j-1], v[0][i][j])) ans++;
  for(int i=0;i<w;i++) for(int j=1;j<v[1][i].size();j++) if(unite(v[1][i][j-1], v[1][i][j])) ans++;
  if(n - ans != 1) ans += (n - ans) * 2 - 1 - f;
  cout << ans << endl;
}

Measured memory_bytes: 8272
n = int(input())
S = [int(i) for i in input().split()]
q = int(input())
T = [int(i) for i in input().split()]

count = 0

S.append(None)

def lenearSearch(s, t):
    i = 0
    while S[i] != t:
        i += 1
    return i != (len(s)-1)

for t in T:
    S[-1] = t
    if lenearSearch(S, t):
        count+=1

print(count)

    


Measured memory_bytes: 6556