akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

const (
	initialBufSize = 1024
	maxBufSize     = 1e6
)

var (
	scanner = bufio.NewScanner(os.Stdin)
)

func main() {
	scanner.Split(bufio.ScanWords)
	n := scanInt()
	p, q := scanInts(n), scanInts(n)
	fmt.Println(cal(n, p, q))
}

func cal(n int, p, q []int) int {

	pn := 1
	qn := 1
	for i := 0; i < n; i++ {
		f := fact(n - 1 - i)
		for j := (i + 1); j < n; j++ {
			if p[i] > p[j] {
				pn += f
			}
			if q[i] > q[j] {
				qn += f
			}
		}
	}

	return abs(pn - qn)
}

func fact(n int) int {
	ret := 1
	for i := 1; i <= n; i++ {
		ret *= i
	}
	return ret
}

func scanInt() int {
	i, _ := strconv.Atoi(scanText())
	return i
}

func scanInts(size int) []int {
	ints := make([]int, size)
	for i := 0; i < size; i++ {
		ints[i] = scanInt()
	}
	return ints
}

func scanFloat64() float64 {
	f, _ := strconv.ParseFloat(scanText(), 64)
	return f
}

func scanFloat64s(size int) []float64 {
	f := make([]float64, size)
	for i := 0; i < size; i++ {
		f[i] = scanFloat64()
	}
	return f
}

func scanText() string {
	scanner.Scan()
	return scanner.Text()
}

func scanTexts(size int) []string {
	s := make([]string, size)
	for i := 0; i < size; i++ {
		s[i] = scanText()
	}
	return s
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

// greatest common divisor(最大公約数)
func gcd(a, b int) int {
	for {
		mod := a % b
		if mod == 0 {
			return b
		}
		a, b = b, mod
	}
}

// latest common multiple(最小公倍数)
func lcm(a, b int) int {
	return (a / gcd(a, b)) * b
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    string ans;
    vector<string> tango(n);
    set<string> tango_set;
    rep(i, n){
        string s;
        cin >> s;
        tango[i] = s;
        tango_set.insert(s);
    }
    ans = "Yes";
    for(int i = 1; i < n; i++){
        if(tango[i-1][(int)tango[i-1].size() - 1] != tango[i][0]){
            ans = "No";
            break;
        }
    }
    if(tango_set.size() != n) ans = "No";

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
         
        using namespace std;
         
        int main() {
          int x, y;
          scanf("%d %d", &x, &y);
          if(y&1) {
            printf("No\n");
          } else {
            int b = (y >> 1) - x;
            int a = x - b;
            if(a < 0 || b < 0) {
              printf("No\n");
            } else {
              printf("Yes\n");
            }
          }
          return 0;
        }

Measured memory_bytes: 3764
import sys
import decimal # 10進法に変換，正確な計算

def input():
    return sys.stdin.readline().strip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    keep = n
    sum = 0
    for i in a:
        sum += b[i-1]
        if i == keep + 1:
            sum += c[i-2]
        keep = i
    print(sum)

    
    
main()

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

int main()
{
	int a, b, c, x, ans = 0;
	cin >> a >> b >> c;
	for(int x = a; x <= b; x++){
		if(c % x == 0){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1160
from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    d += 1
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d])
            if ans < d:
                ans = d
            hw[nh][nw] = "#"
print(ans)

Measured memory_bytes: 176092
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

vector<bool> IsPrime;

void sieve(int max) {
  if (max+1 > IsPrime.size()) {
    IsPrime.resize(max+1, true);
  }
  IsPrime[0] = false;
  IsPrime[1] = false;

  for (int i = 2; i*i <= max; i++) {
    if (IsPrime[i]) {
      for (int j = 2; i*j <= max; j++) {
        IsPrime[i*j] = false;
      }
    }
  }
}

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

  sieve(55555);

  for (int i = 11, cnt = 0; cnt < n; i += 10) {
    if (IsPrime[i]) {
      if (cnt) cout << " ";
      cout << i;
      cnt++;
    }
  }
  cout << endl;
  



  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[]) {
  char cn[4];
  string num[4];
  for (size_t i = 0; i < 4; i++) {
    cin >> cn[i];
    num[i] = cn[i];
  }

  if (stoi(num[0])+stoi(num[1])+stoi(num[2])+stoi(num[3])==7) cout << num[0]+"+"+num[1]+"+"+num[2]+"+"+num[3]+"=7" << endl;
  else if (stoi(num[0])+stoi(num[1])+stoi(num[2])-stoi(num[3])==7) cout << num[0]+"+"+num[1]+"+"+num[2]+"-"+num[3]+"=7" << endl;
  else if (stoi(num[0])+stoi(num[1])-stoi(num[2])+stoi(num[3])==7) cout << num[0]+"+"+num[1]+"-"+num[2]+"+"+num[3]+"=7" << endl;
  else if (stoi(num[0])+stoi(num[1])-stoi(num[2])-stoi(num[3])==7) cout << num[0]+"+"+num[1]+"-"+num[2]+"-"+num[3]+"=7" << endl;
  else if (stoi(num[0])-stoi(num[1])+stoi(num[2])+stoi(num[3])==7) cout << num[0]+"-"+num[1]+"+"+num[2]+"+"+num[3]+"=7" << endl;
  else if (stoi(num[0])-stoi(num[1])+stoi(num[2])-stoi(num[3])==7) cout << num[0]+"-"+num[1]+"+"+num[2]+"-"+num[3]+"=7" << endl;
  else if (stoi(num[0])-stoi(num[1])-stoi(num[2])+stoi(num[3])==7) cout << num[0]+"-"+num[1]+"-"+num[2]+"+"+num[3]+"=7" << endl;
  else if (stoi(num[0])-stoi(num[1])-stoi(num[2])-stoi(num[3])==7) cout << num[0]+"-"+num[1]+"-"+num[2]+"-"+num[3]+"=7" << endl;

  return 0;
}


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

int main() {
	char ca[8];
	int a;
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> ca;
		sort(ca, ca + 8);
		string sa = ca;
		reverse(ca,ca+8);
		string sb = ca;
		int p = stoi(sa);
		int q = stoi(sb);
		cout << q - p << endl;
	}
	return 0;
}

Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
  ll N,M;
  while( cin >> N >> M){ 
    if( N == 0 && M == 0){ break;}
  vector<ll> P(N+1);
  ll ans = 0LL;
  for(ll i = 0; i < N; i++){ cin >> P[i];} P[N] = 0;
   // cin all components that is the same with P1~PN+1 in 1-indexed
  
  vector<ll> two;
  for(ll i = 0; i <= N; i++){
   for(ll j = 0; j <= N; j++){
     two.push_back(P[i]+P[j]);}}
    
  sort(two.begin(),two.end());
    
    
    
  for(ll i = 0; i < two.size(); i++){
    ll c = two[i];
  
    if( c > M){ continue;}
    
    auto itr = upper_bound(two.begin(),two.end(),M-c);
    if( itr == two.begin()){ continue;}
    itr--;
    
    if( *itr > M-c){ continue;}
    ans = max(ans, c+*itr);
  }
  
  cout << ans << endl; }return 0;}


Measured memory_bytes: 18912
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  as <- VU.fromList . map (pred . unsafeTextToInt) . T.words <$> T.getLine :: IO (VU.Vector Int)
  let
    ls = VU.accumulate (+) (VU.replicate n 0) . VU.map (flip (,) 1) $ as :: VU.Vector Int
    m = VU.sum . VU.map comb $ ls :: Int
  VU.mapM_ print . VU.map ((m -) . pred . (ls VU.!)) $ as

comb :: Int -> Int
comb l = (l * pred l) `div` 2

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint=vector<int>;
using vvint=vector<vint>;
using pint=pair<int, int>;
using vpint=vector<pint>;
template<typename T> using priority_queue_rev=priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T1, typename T2> bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N, L;
signed main() {
    cin >> N >> L;
    int sum = 0, k = LLONG_MAX;
    rep(i, N) {
        sum += L + i;
        if (abs(k) > abs(L + i)) { k = L + i; }
    }
    cout << sum - k << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a.at(i);
    sort(a.begin(), a.end());
    cout << a.at(n - 1) - a.at(0) << endl;
    return 0;
}

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

typedef long long ll;

main()
{
    string s;
    cin >> s;
    int c = 0, m = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'A' || s[i] == 'T' || s[i] =='G' || s[i] == 'C'){
            c++;
        }
        else{
            c = 0;
        }
        m = max(c, m);
    }
    cout << m;



}





///promy_pompom
//hello world


Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

long long A,B;

long long f(long long x) {
    if (x % 4 == 0) return x;
    if (x % 4 == 1) return 1;
    if (x % 4 == 2) return x + 1;
    return 0;
}
int main() {
    cin >> A >> B;
    cout << (f(B) ^ f(A - 1)) << endl;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
suma = sum(A)
u = 10**12
d = 0
for i in range(50):
    x = (u + d)//2
    s = 0
    for i in range(N):
        f = F[i]
        j = -(i+1)
        a = A[j]
        b = x // f
        s += max(0,a-b)
    if s <= K:
        u = x
    else:
        d = x
print(u)

Measured memory_bytes: 119628
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using P = pair<int,int>;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(n-1));
    rep(i,n) {
        rep(j,n-1) {
            cin >> a[i][j];
            --a[i][j];
        }
        reverse(all(a[i]));
    }
    vector<P> q;
    auto check = [&](int i) {
        if (a[i].size()==0) return;
        int j = a[i].back();
        if (a[j].size()==0) return;
        if (a[j].back()==i) {
            P p(i,j);
            if (p.se > p.fi) swap(p.se, p.fi);
            q.pb(p);
        }
    };

    rep(i,n) check(i);

    int day = 0;
    while (q.size() > 0) {
        ++day;
        sort(all(q));
        q.erase(unique(all(q)), q.end());
        vector<P> prevq;
        swap(q,prevq);

        for (auto p: prevq) {
            int i = p.fi, j = p.se;
            a[i].pop_back();
            a[j].pop_back();
        }
        for (auto p: prevq) {
            int i = p.fi, j = p.se;
            check(i);
            check(j);
        }
    }
    rep(i,n) {
        if (a[i].size()!=0) {
            puts("-1");
            return 0;
        }
    }
    cout << day << endl;
    return 0;
}






Measured memory_bytes: 4224
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m, k;
	cin >> n >> m >> k;
	
	int ret[n][m];
	char f[n][m];
	for(int i = 0, li = 0; i < n; i++){
		vector<pi> cur;
		for(int j = 0, lj = 0; j < m; j++){
			cin >> f[i][j];
			if(f[i][j] == '#'){
				cur.push_back({lj, j});
				lj = j + 1;
			}
		}
		if(cur.empty()) continue;
		
		int X = (cur.size() < k ? i : n - 1);
		cur.back().second = m - 1;
		for(pi p : cur){
			for(int x = li; x <= X; x++){
				for(int y = p.first; y <= p.second; y++){
					ret[x][y] = k;	
				}
			}
			k--;
		}
		li = i + 1;
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) cout << ret[i][j] << " ";
		cout << endl;
	}
	
	return 0;
}

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

template <class _T> inline bool chmax (_T& a,_T b){if(a<b){a=b;return true;}return false;}
template <class _T> inline bool chmin (_T& a,_T b){if(a>b){a=b;return true;}return false;}

const long long INF = 1LL << 60;
const long long mod = 1000000007;


int main(void){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int i=0;
    while(1){
	if(i%2==0){
	    c -= b;
	}else{
	    a -= d;
	}
	if(a<=0){
	    cout << "No" << endl;
	    break;
	}
	if(c<=0){
	    cout << "Yes" << endl;
	    break;
	}
	i++;
    }
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iomanip>
#include<limits>
#include<queue>
#include<set>
#include<cstdio>
#include<climits>
#include<cstring>

using namespace std;


int main(){

    set<int>right;
    set<int>left;

    int N,M;

    cin >> N >> M;

    for(int i = 0;i < M;i++){
    	int a;
    	int b;
    	cin >> a >> b;
    	if(a == 1){
    		right.insert(b);
    	}
    	if(b == N){
    	    left.insert(a);
    	}
    }

    for(auto r:right){
    	if(left.count(r) !=0){
    		cout << "POSSIBLE" << endl;
    		return 0;
    	}
    }

    cout << "IMPOSSIBLE" << endl;

	return 0;

}


Measured memory_bytes: 9600
//Don't have to see. start------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin, output: process.stdout
});
var obj; var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error('\n↑入力 ↓出力');
  Main();
});
function makeClone(obj){return (obj instanceof Set) ? new Set(Array.from(obj)) : JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  return {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(this.hasNext()){return this.list[this.index++];}else{throw 'ArrayIndexOutOfBoundsException ‚There is no more input';}}
  };
}
function myout(s){console.log(s);}
function myerr(s){console.error('debug:' + require('util').inspect(s,false,null));}
//param "no" is
//unknown or outlier : return i. 1: parseInt.
//2: split space. 4: split space and parseInt.
//6: split 1 character. 7: split 1 character and parseInt.
//8: join space. 9: join nextline. 0: join no character.
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(' ');case 4:return i.split(' ').map(Number);case 6:return i.split('');case 7:return i.split('').map(Number);case 8:return i.join(' ');case 9:return i.join('\n');case 0:return i.join('');default:return i;}}catch(e){return i;}}

//Don't have to see. end------------------------------------------
function Main(){
  var one = nextIntArray();
  var H = one[0];
  var N = one[1];
  var list = nextIntArray();
  var sum = 0;
  for(var i = 0; i < N; i++){
    sum += list[i];
  }
  myout((sum < H) ? "No" : "Yes");

}


Measured memory_bytes: 40548
#include <iostream>
#include<math.h>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {

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


    int resultA = A * 10 + B + C;
    int resultB = A + B * 10 + C;
    int resultC= A + B + C * 10;

    vector<int> answer(3);
    answer.push_back(resultA);
    answer.push_back(resultB);
    answer.push_back(resultC);

    int max = *max_element(answer.begin(), answer.end());

    cout << max << endl;
}

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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

template<typename T1,typename T2>ostream& operator<<(ostream& os,const pair<T1,T2>& a) {os << "(" << a.first << ", " << a.second << ")";return os;}

const char newl = '\n';

int const MAX_N = 100000;
vector<ll> prime;
vector<bool> is_prime(MAX_N,true);
void Eratosthenes() {
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2;i*i < MAX_N;++i) if (is_prime[i]) for (ll j = 2*i;j < MAX_N;j += i) is_prime[j] = false;
    for (ll i = 0;i < MAX_N;++i) if (is_prime[i]) prime.push_back(i);
}

vector<pair<ll,int>> prime_factorization(ll a) {
    vector<pair<ll,int>> prime_factor;
    if (is_prime[0]) Eratosthenes();
    for (ll& i : prime) {
        if (i*i > a) break;
        if (a%i == 0) {
            P p = P(i,0);
            while (a%i == 0) {
                a /= i;
                p.second++;
            }
            prime_factor.push_back(p);
        }
    }
    if (a != 1) prime_factor.push_back(P(a,1));
    return prime_factor;
}

void rec(vector<ll>& div,vector<pair<ll,int>>& fact,int i,ll d) {
    if (i == fact.size()) {
        div.push_back(d);
        return;
    }
    for (int j = 0;j <= fact[i].second;++j) {
        rec(div,fact,i+1,d);
        d *= fact[i].first;
    }
}

vector<ll> divisor(ll a) {
    vector<ll> div;
    vector<pair<ll,int>> prime_factor = prime_factorization(a);
    rec(div,prime_factor,0,1);
    return div;
}

int main() {
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0;i < n;++i) cin >> a[i];
    ll sum = 0;
    for (int i = 0;i < n;++i) sum += a[i];
    vector<ll> div = divisor(sum);
    int ans = 1;
    for (int d : div) {
        vector<int> x,y;
        for (int i = 0;i < n;++i) if (a[i]%d) {
            x.push_back(a[i]%d);
            y.push_back(d-a[i]%d);
        }
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        int s1 = 0,s2 = 0,m = x.size();
        for (int i = 0;i < m;++i) s2 += y[i];
        for (int i = 0;i < m;++i) {
            s1 += x[i];
            s2 -= y[m-1-i];
            if (s1 == s2) {
                if (s1 <= k) ans = max(ans,d);
                break;
            }
        }
    }
    cout << ans << endl;
}

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

#define llong long long 
#define ii pair<int, int>
#define fir first
#define sec second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++i < (n);)
#define rep1(i,n) for (int i = 0; i++ < (n); )

template<typename t>/*{{{*/
ostream& operator<<(ostream& cout, const vector<t>& a) {
  cout << "[";
  rep(i, len(a)) cout << a[i] << ", ";
  return cout << "]";
}

template<typename u, typename v>
ostream& operator<<(ostream& cout, const pair<u, v>& t) {
  return cout << "(" << t.fir << ", " << t.sec << ")";
}/*}}}*/

#define maxg 600000
#define maxd 20
#define inf 10101010
int d, g;
int dp[maxd][maxg] = {0};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> d >> g;
  g /= 100;
  rep(i, d + 1) rep(f, g + 1) dp[i][f] = inf;
  dp[0][0] = 0;
  rep1(i, d) {
    int u, v; cin >> u >> v;
    v /= 100;
    rep(f, 1 + u) {
      int ad = i * f + (f == u ? v : 0);
      rep(h, g + 1)
        dp[i][min(h + ad, g)] = min(dp[i][min(h + ad, g)], dp[i - 1][h] + f);
    }
  }
  cout << dp[d][g];

  return 0;
}


Measured memory_bytes: 23168
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 1000000007
#define N 100005
#define PI 3.14159265
bool compare(pair<ll,char> i, pair<ll,char> j) 
{
  return i.S < j.S;
}
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
}
int main()
{
	ios
	string s;
	cin>>s;
	ll l=s.length()/2;
	string str1,str2;
	str1=s.substr(0,l);
	str2=s.substr(l+1,l);
	if (str1 == string(str1.rbegin(), str1.rend())&& (str2 == string(str2.rbegin(), str2.rend()))&&(s == string(s.rbegin(), s.rend())))
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	String r=scan.next(),g=scan.next(),b=scan.next();
	String s=r+g+b;
	int i=Integer.parseInt(s);
	if((i)%4==0) {
		System.out.println("YES");
	}
	else {
		System.out.println("NO");
	}

	}

}

Measured memory_bytes: 39132
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In,' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var A = cin.ReadIntArray(N);
          	var i = 1;
          var ans = 0;
          	Array.Sort(A);
            Array.Reverse(A);
            foreach(var x in A){
              ans += (x * i);
              i *= (-1);
            }

            WriteLine(ans);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream,char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0;i < tmp.Length;i++)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }

        
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }

}

Measured memory_bytes: 13268
function main(input) {
  input = input.trim().split("\n");
  const [n, q] = input[0].split(" ").map(n => Number(n));
  const s = input[1];
  const lr = input.slice(2).map(n => n.split(" ").map(m => Number(m));
  const arr = [s[0] === "A" && s[1] === "C" ? 1 : 0];
  for (let i = 1; i < s.length; i++) {
    const char = s[i];
    if (char === "A" && s[i+1] === "C") {
      arr.push(arr[i-1] + 1);
    } else {
      arr.push(arr[i-1]);
    }
  }
  const result = [];
  for (let i = 0; i < q; i++) {
    const [l, r] = lr[i];
    if (l === 1) {
      result.push(arr[r-2]);
    } else {
      result.push(arr[r-2]-arr[l-2]);
    }
  }
  console.log(result.join("\n"));
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 55756
#include<bits/stdc++.h>
#define hell 1000000007
#define int long int
#define inf (int)(100000000)

using namespace std;

void solve(){
    int n;
    cin>>n;
    map <int,int> mp;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n/=i;
        }
    }
    if(n!=1)
        mp[n]++;
    int ans=0;
    for(auto x:mp){
        int y=x.second;
        for(int i=1;i<=y;i++){
            y-=i;
            ans++;
        }
    }
    cout<<ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 3656
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#include<climits>
#include<set>
#define ll long long
using namespace std;
int main() {
	ll n;
	cin >> n;
	vector<ll>p(n);
	for (ll i = 0; i < n; i++) {
		cin >> p[i];
	}
	ll a, b,soejia=0,soejib=0;
	bool flag = false;
	for (ll i = 0; i < n-1; i++) {
		if (p[i] > p[i + 1]) {
			if(!flag){
				//a = p[i];
				soejia = i;
				flag = true;
			}
			else {
				//b = p[i + 1];
				soejib = i + 1;
				break;
			}
		}
	}
	swap(p[soejia], p[soejib]);
	for (ll i = 0; i < n-1; i++) {
		if (p[i] > p[i + 1]) {
			cout << "NO" << endl;
			exit(0);
		}
	}
	cout << "YES" << endl;
	


}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String[] a = new String[n];
		String[] b = new String[m];
		for(int i = 0; i < n; i++) {
			a[i] = sc.next();
		}
		for(int i =0; i < m; i++) {
			b[i] = sc.next();
		}
		String result = "初期化";
		int idx = 0;
out:		for(int i = 0;i <= n-m; i++) {
			//System.out.println("テスト" + i + " idx:" + idx + " → " + a[i].indexOf(b[0], idx) );
			idx = a[i].indexOf(b[0], idx);
			if(idx == -1) {
				//System.out.println("test");
				idx = 0;
			}else{
				//System.out.println(n + " " + m);
				if(n == m) {
					result = "Yes";
					break out;
				}
				for(int j = 1; j <= m-1; j++) {
					//System.out.println("i-:" + i + " idx:" + idx + " 比較" + a[i + j].indexOf(b[j], idx) );
					if(a[i + j].indexOf(b[j], idx) == idx);
					else if(a[i + j].indexOf(b[j], idx) == -1) {
						idx = 0;
						break;
					}else{
						i--;
						idx++;
						break;
					}
					if(j == m-1) {
						result = "Yes";
						break out;
					}
				}
				
			}
			if(i == n-m) {
				result = "No";
			}
		}
		System.out.println(result);
	}
}


Measured memory_bytes: 22612
import sys
import math

a, b, c = map(int, sys.stdin.readline().split())

# if math.sqrt(a) + math.sqrt(b) < math.sqrt(c):
if c - b - a > 0 and  a**2 + b**2 + c**2 - 2 * (a*b + b*c + c*a) > 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    edge_from[B-1].append(A-1)
    edge_to[A-1].append(B-1)

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_

for x in result:
    print(x + 1)

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

int main(){
  int N;
  cin >> N;
  vector<int> p(N);
  rep(i,N){
    cin >> p.at(i);
  }
  sort(p.begin(),p.end());
  int m = 0;
  rep(i,N){
    if(i==N-1){
      m += p.at(i)/2;
    }else{
      m += p.at(i);
    }
  }
  cout << m <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<cstdlib>
#include<deque>
#include<queue>
#include<bitset>
#include<functional>
#include<utility>
#include<list>
#include<iomanip>
#include<ctime>
#include<cassert>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
const int INF=1e9+1;
long long ans[55],n,p,yu;
int main()
{
	long long k;
	cin>>k;
	n=50;
	for(int i=1;i<=n;i++) ans[i]=49;
	p=k/n;
	yu=k%n;
	for(int i=1;i<=50;i++) ans[i]+=p;
	if(yu!=0)
	{
		for(int i=1;i<=yu;i++) ans[i]+=n-yu+1;
		for(int i=yu+1;i<=n;i++) ans[i]-=yu;
	}
	cout<<n<<endl;
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long a,b,c,x;
    cin>>a>>b>>c;
    if(b-1<c) c=b-1;
    x=floor(a*c/b)-a*floor(c/b);
    cout<<x<<endl;
    return 0;
 }

Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
int main(){
  int x[101],i=1;
  char s[100];
   
  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      x[i-2]=x[i-2]+ x[i-1];
      i=i-2;
    } else if ( s[0] == '-' ){
      x[i-2]=x[i-2]- x[i-1];
      i=i-2;
    } else if ( s[0] == '*' ){
      x[i-2]=x[i-2]* x[i-1];
      i=i-2;
    } else {
      x[i] = atoi(s);
    }
    i++;
  }
  printf("%d\n", x[1]);
   
  return 0;
}

Measured memory_bytes: 548
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int num, i, j, cnt=0, ans=0;
    cin >> num;
    for(i=1; i<=num; i++){
        for(j=1; j<=i; j++){
            if(i % j == 0 && i&1){
                cnt++;
            }
        }
        if(cnt == 8){
            ans++;
        }
        cnt=0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import defaultdict

N ,K,S = list(map(int,input().split(" ")))

ans = []
for _ in range(K):
    ans.append(S)
if S == 1:
    hoge = 2
else:
    hoge = S//2 + 1
for _ in range(N - K):
    ans.append(hoge)
print(*ans)

Measured memory_bytes: 6900
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=10010;
int n,a[25],cnt;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=2;i<n;i++)
  {
    int p=min(a[i-1],min(a[i],a[i+1]));
    int b=max(a[i-1],max(a[i],a[i+1]));
    if(a[i]!=p && a[i]!=b) cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}


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

int main()
{
int n;
  cin>>n;
  int arr[n];
  unordered_map<int,int>m;
  for(int i=1;i<=n-1;i++)
  {
     cin>>arr[i];
    m[arr[i]]++;
  }
  sort(arr,arr+n);
  for(int i=1;i<=n;i++)
  {
    if(m[i])
    {
      cout<<m.find(i)->second<<endl;
    }
    else
      cout<<0<<endl;
     
    
  }
 
}


Measured memory_bytes: 12156
import sys
input=sys.stdin.readline

a,b,k = map(int,input().split())

a_a =  0 if(a <= k) else a - k
if(a_a > 0):
	b_a = b
else:
	if(k-a>=b):
		b_a = 0
	else:
		b_a = b+a-k
print(a_a, b_a)


Measured memory_bytes: 38384
n = int(input())
 
adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)
 
isSearched = [None] + [False] * n
 
distance = [None] + [-1] * n
 
def bfs(u):
    d = 0
    isSearched[u] = True
    distance[u] = d
    edge = [u]
    while edge:
        q = list(edge)
        edge = []
        d += 1
        for c_e in q:
            for n_e in adj[c_e]:
                if not isSearched[n_e]:
                    isSearched[n_e] = True
                    edge.append(n_e)
                    distance[n_e] = d
 
 
bfs(1)
 
for i, x in enumerate(distance[1:], start=1):
    print(i, x)

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n; cin >>n;
	VL a(n);
	rep(i, n) cin >>a[i];

	VL sm(62);
	rep2(i, 0, 62) rep(j, n) if(a[j]>>i &1) sm[i]++;

	ll ans = 0;
	rep(i, 62){
		(ans += (1LL<<i) %MD * sm[i] %MD * (n-sm[i])) %=MD;
	}
	
	cout <<ans <<"\n";
	return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
int main(void){
	int n, i, j, v, a[100];
	
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		if(i != n-1){
			printf("%d ", a[i]);
		}else{
			printf("%d\n", a[i]);
		}
	}
	
	for(i=1; i<n; i++){
		v = a[i];
		j = i-1;
		while(j>=0 && a[j]>v){
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = v;
		
		for(j=0; j<n; j++){
			if(j != n-1){
				printf("%d ", a[j]);
			}else{
				printf("%d\n", a[j]);
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 600
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

typedef long long ll;

const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

typedef vector<int> vi;
typedef pair<int, int> pi;

#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define ALL(v) (v).begin(), (v).end()

long long int facctorial(long long int k){
    long long int sum = 1;
    for (long long int i = 1; i <= k; ++i)
    {
        sum *= i;
        if(sum > 1000000007){
          sum = sum % 1000000007;
        }
    }
    return sum;
}

int main(){
  long long int n,m;
  scanf("%lld %lld", &n, &m);
  long long int t = n>m ? n-m : m-n ;
  if(t>1){
    printf("0\n");
  }else if(t==1) {
    long long int a = (facctorial(n) * facctorial(m)) % (1000000007);
    printf("%lld\n",a);
  }else {
    long long int a = facctorial(n);
    a = (2 * a * a) % (1000000007);
    printf("%lld\n",a);
  }

  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, c = mi()
    B = lmi()
    cnt = 0
    for _ in range(n):
        A = lmi()
        if sum([A[i] * B[i] for i in range(m)]) + c > 0:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
    string S, T;
    cin >> S >> T;
    bool flag = false;
    int slen = S.length();
    int tlen = T.length();
    for (int i=slen-1; i>=tlen-1; i--) {
        for (int j=0; j<tlen; j++) {
            if (!(S[i-j] == '?' || S[i-j] == T[tlen - j -1])) {
                break;
            }
            if (j == (tlen-1)) {
                flag = true;
            }
        }
        if (flag) {
            for (int j=0; j<tlen; j++) {
                S[i-tlen+j+1] = T[j];
            }
            break;
        }
    }
    if (flag) {
        for (int i=0; i<slen; i++) {
            if (S[i] == '?') S[i] = 'a';
        }
    } else {
        S = "UNRESTORABLE";
    }
    cout << S << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define MAXN ((ll)4e2+5)
#define MOD ((ll)1e9 + 7) 
#define ll long long
#define _ << " " <<
#define TRACE(x) cerr << #x << " = " << x << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"

ll n,m,t,k;
ll d[MAXN];
ll dp[MAXN][MAXN];
ll pre[MAXN];

ll range(ll L,ll R)
{
	if(L)
		return pre[R] - pre[L-1];
	return pre[R];
}

ll f(ll L,ll R)
{	
	if(L == R)
		return 0;
	if(L+1 == R)
		return (d[L] + d[R]); 
	if(dp[L][R]) return dp[L][R];

	ll ans = LLONG_MAX;
	for (ll i = L; i < R; ++i)
		ans = min(ans, f(L,i) + f(i+1,R) + range(L,R));

	return dp[L][R] = ans;
}

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

	cin >> n;
	for (ll i = 0; i < n; ++i)
	{
		cin >> d[i];
		if(i)
			pre[i] = pre[i-1] + d[i];
		else
			pre[0] = d[0];
	}

	cout << f(0,n-1) << endl;


	return 0;
}


Measured memory_bytes: 1664
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

typedef pair< pair<int,int> , pair<int,int> > DATA;
DATA in[10000];

bool cmp1( const DATA &a , const DATA &b ){
	return a.first < b.first;
}
bool cmp2( const DATA &a , const DATA &b ){
	return a.second < b.second;
}

int main(){
	int n,q;
	while(cin >> n >> q && n){
		vector< pair<int,int> > tr[10001] , tc[10001];
		for(int i = 0 ; i < n ; i++){
			int x1 , y1 , x2 , y2;
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			in[i].first.first   = x1;
			in[i].first.second  = x2;
			in[i].second.first  = y1;
			in[i].second.second = y2;
		}
		sort(in,in+n,cmp1);
		for(int i = 0 ; i < n ; i++){
			int x1 , y1 , x2 , y2;
			x1 = in[i].first.first;
			x2 = in[i].first.second;
			y1 = in[i].second.first;
			y2 = in[i].second.second;
			for(int i = y1 ; i < y2 ; i++) tr[i].push_back(make_pair(x1,x2));
		}
		if(q == 2){
			sort(in,in+n,cmp2);
			for(int i = 0 ; i < n ; i++){
				int x1 , y1 , x2 , y2;
				x1 = in[i].first.first;
				x2 = in[i].first.second;
				y1 = in[i].second.first;
				y2 = in[i].second.second;
				if(q==2) for(int i = x1 ; i < x2 ; i++) tc[i].push_back(make_pair(y1,y2));
			}
		}
		int area = 0 , perimeter = 0;
		// merge
		for(int i = 0 ; i < 10001 ; i++){
			if(tr[i].size() == 0) continue;
	
			int s = tr[i][0].first , e = tr[i][0].second;
			for(int j = 1 ; j < tr[i].size() ; j++){
				int S = tr[i][j].first , E = tr[i][j].second;
				if(S <= e){
					e = max(E,e);
				}else{
					area += e-s;
					perimeter += 2;
					s = S;
					e = E;
				}
			}
			perimeter += 2;
			area += e-s;
		}
		
		if(q == 2){
			for(int i = 0 ; i < 10001 ; i++){
				if(tc[i].size() == 0) continue;
				
				int s = tc[i][0].first , e = tc[i][0].second;
				for(int j = 1 ; j < tc[i].size() ; j++){
					int S = tc[i][j].first , E = tc[i][j].second;
					if(S <= e){
						e = max(E,e);
					}else{
						perimeter += 2;
						s = S;
						e = E;
					}
				}
				perimeter += 2;
			}
		}
		if(q == 1){
			cout << area << endl;
		}else{
			cout << area << endl;
			cout << perimeter << endl;
		}
	}
	
}

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

int main(void)
{
	int n, m;
	vector <int> a(100001);
	
	cin >> n >> m;
	for (int i = 1; i < n; i++)	cin >> a[i];
	for (int i = 0; i <= n; i++) a[i+1] += a[i];
	
	int res = 0, move, now = 1;
	for (int i = 0; i < m; i++){
		cin >> move;
		res += abs(a[now+move-1] - a[now-1]);
		//cout << now+move << "*" << a[now+move-1] << " -- " << a[now-1];
		//cout << now+move << 
		res %= 100000;
		now += move;
	}
	
	cout << res << endl;
	
	return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)

string s1 = "qwertasdfgzxcvb";
string s2 = "yuiophjklnm";

void solve(string s){
    int cur = 0;
    if(s2.find(s[0]) != string::npos) cur = 1;

    int ans = 0;
    for(int i = 1; i < (int)s.size(); i++) {
        if(cur == 0) {
            if(s2.find(s[i]) == string::npos) continue;
            ans++;
            cur = 1;
        } else {
            if(s1.find(s[i]) == string::npos) continue;
            ans++;
            cur = 0;
        }
    }

    cout << ans << endl;
}

int main() {
    while(1){
        string s;
        cin >> s;
        if(s == "#") break;
        solve(s);
    }

    return 0;
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;

typedef unsigned long long ll;

const long long MOD = 1000000000 + 7;

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

int main(){
    string f,s,e;
    cin >> f >> s >> e;
    cout << "A" << s[0] << "C" << endl;
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
A = []
B = []
clear = 0
same = 0
for i in range(N):
    A.append(str(input()))
for i in range(M):
    B.append(str(input()))

for i in range(N - M + 1):
    for j in range(N - M + 1):
        same = 0
        for k in range(M):
            if A[i + k][j: j + M] == B[k]:
                same += 1
            else:
                break
        if same == M:
            clear = 1
            break

if clear == 1:
    print('Yes')
else:
    print('No')

        
            

Measured memory_bytes: 9144