akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

int main() {
  int N;
  cin >> N;
  ll A[N];
  ll sum[N];
  for (int i=0;i<N;i++) { cin >> A[i]; sum[i]=A[i]+(i>0?sum[i-1]:0);}
  ll half=0;
  int idx;
  for (int i=0;i<N;i++) {
    half+=A[i];
    if (half > sum[N-1] / 2) {
      idx = i;
      break;
    }
  }
  ll goal = min(abs(sum[N-1]-2*sum[idx]),abs(sum[N-1]-2*sum[max(idx-1,0)]));
  cout << goal << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	int n, k;
	long ans = 1;
	cin >> n >> k;
	for (int i = 0; i < n; i++){
		if (i == 0) {
			ans *= k;
		}
		else{
			ans *= (k - 1);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>pii;
const int maxn=2e5+100;
ll n, arr[maxn];
pii L[maxn], R[maxn];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>arr[i];
    ll l=1, r=2, lsum=0, rsum=arr[1]+arr[2];
    while(r<=n)
    {
        while(abs((lsum+arr[l])-(rsum-arr[l])) < abs(lsum-rsum))
        {
            lsum+=arr[l];
            rsum-=arr[l];
            l++;
        }
        L[r]= {lsum, rsum};
        r++;
        if(r<=n)rsum+=arr[r];
    }
    l=n-1; r=n, rsum=0, lsum=arr[n]+arr[n-1];
    while(l>=1)
    {
        while(abs((rsum+arr[r])-(lsum-arr[r])) < abs(lsum-rsum))
        {
            rsum+=arr[r];
            lsum-=arr[r];
            r--;
        }
        R[l]={lsum, rsum};
        l--;
        if(l>=1)lsum+=arr[l];
    }
    ll ans=LLONG_MAX;
    for(int i=2; i<=n-2; i++)
    {
        ll mn=min({L[i].x, L[i].y, R[i+1].x, R[i+1].y});
        ll mx=max({L[i].x, L[i].y, R[i+1].x, R[i+1].y});
        ans=min(ans, mx-mn);
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
long long nature(long long a){
  if(a>=0){return a;}
  else{return -1*a;}
}
int main(){
  #define int long long
  int T;
  int INF=1000000000000000000;
  cin>>T;
  for(int h=0;h<T;h++){
    int N,A,B,C,D;
    cin>>N>>A>>B>>C>>D;
    unordered_map<int,int> mp;
    queue<int> que;
    que.push(N);
    mp[N]=0;
    while(que.size()>0){
      if(N==1){
        break;
      }
      int x=que.front();
      que.pop();
      /*
      //+1または-1する時
      for(int i=x-1;i<=x+1;i++){
        int cost=0;
        if(i!=x && i>1){
          cost=D+mp[x];
          if(cost<mp[i] || mp[i]==0){
            mp[i]=cost;
            que.push(i);
          }
        }
      }
      */
      //2で割る場合
      for(int i=x-1;i<=x+1;i++){
        int cost=0;
        if(i%2==0 && i>=1){
          cost=min((i/2)*D+nature(i-x)*D+mp[x],nature(i-x)*D+A+mp[x]);
          if((i-i/2)>=(2*INF-mp[x])/D && cost<0){
            cost=nature(i-x)*D+A+mp[x];
          }
          if(cost<mp[i/2] || mp[i/2]==0){
            //if(i/2==10 && cost==3821859794){cout<<2<<endl;}
            mp[i/2]=cost;
            if(i/2>1){
              que.push(i/2);
            }
          }
        }
      }
      //3で割る場合
      for(int i=x-2;i<=x+2;i++){
        int cost=0;
        if(i%3==0 && i>=1){
          cost=min((i-i/3)*D+nature(i-x)*D+mp[x],nature(i-x)*D+B+mp[x]);
          if((i-i/3)>=(2*INF-mp[x])/D && cost<0){
            cost=nature(i-x)*D+B+mp[x];
          }
          if(cost<mp[i/3] || mp[i/3]==0){
            //if(i/3==10 && cost==3821859794){cout<<3<<" "<<x<<" "<<i<<endl;}
            mp[i/3]=cost;
            if(i/3>1){
              que.push(i/3);
            }
          }
        }
      }
      //5で割る場合
      for(int i=x-4;i<=x+4;i++){
        //if(x==5){cout<<x<<endl;}
        int cost=0;
        if(i%5==0 && i>=1){
          cost=min((i-i/5)*D+nature(i-x)*D+mp[x],nature(i-x)*D+C+mp[x]);
          if((i-i/5)>=(2*INF-mp[x])/D || cost<0){
            cost=nature(i-x)*D+C+mp[x];
          }
          if(cost<mp[i/5] || mp[i/5]==0){
            //if(i/5==10 && cost==3821859794){cout<<5<<endl;}
            mp[i/5]=cost;
            if(i/5>1){
              que.push(i/5);
            }
          }
        }
      }
    }
    cout<<mp[1]+D<<endl;
    if(h==0){
      for(int i=1;i<51;i++){
        //cout<<i<<" "<<mp[i]<<endl;
      }
    }
  }
}

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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int n,m;

signed main()
{

    cin >>n>>m;

    vector<int>a(n);
    priority_queue<int> q;
    rep(i,n){
        cin>>a[i];
        q.push(a[i]);
    }

    rep(i,m){
        int temp = q.top();
        temp /=2;
        q.pop();
        q.push(temp);
    }
   
   int ans=0;

    while(!q.empty()){
        ans += q.top();
        q.pop();
    }

   print(ans);

    return 0;
}


Measured memory_bytes: 2168
// vim: shiftwidth=2 expandtab foldmethod=marker

// include {{{
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cmath>
#include <utility>
#include <cstdlib>
#include <random>
#include <chrono>
// }}}

// debug(...) {{{
#ifdef LOCAL_DEBUG
#include "./debug.h"
#else
#define debug(...)
#define debugn(...)
#define debug_reset()
#endif

#include <cstdio>

template<class T>
std::string bin(int bits, const T& x) {
  char buf[bits + 1];
  buf[bits] = '\0';
  for(int i = 0; i < bits; i++) {
    if((x >> i) & 1) {
      buf[bits - i - 1] = '1';
    } else {
      buf[bits - i - 1] = '0';
    }
  }
  return std::string(buf);
}
std::string bin(int x) {
  if(x < 0) return bin(32, x);
  for(int i = 4; i < 31; i++) {
    int y = 1 << i;
    if(x < y) return bin(i, x);
  }
  return bin(32, x);
}
// }}}

// misc {{{
using namespace std;
template<class T, class U>

using umap = unordered_map<T, U>;
template<class T>
using uset = unordered_set<T>;

typedef long long ll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

template<class T>
void sort(T& arr) {
  std::sort(arr.begin(), arr.end());
}
template<class T, class By>
void sort_by(T& arr, By by) {
  std::sort(arr.begin(), arr.end(), [by](auto l, auto r){return  by(l) < by(r); });
}

template<class T>
void reverse(T& arr) {
  std::reverse(arr.begin(), arr.end());
}

class Random {
  public:
  std::uniform_int_distribution<> uniform_int;
  std::mt19937 rnd;
  std::bernoulli_distribution bern_dist;
  int uniform(int l, int r) {
    return uniform_int(rnd, std::uniform_int_distribution<>::param_type(l, r));
  }
  int next(int N) {
    return uniform(0, N - 1);
  }
  int bern(double p) {
    return bern_dist(rnd, std::bernoulli_distribution::param_type(p));
  }
};
// }}}

// main {{{
void solve();
int main() {
  solve();
}
// }}}

void solve() {
  int N;
  cin >> N;
  vector<int> P(N);
  rep(i, N) cin >> P[i];
  vector<int> index(N);
  rep(i, N) index[P[i] - 1] = i;

  ll ans = 0;
  set<int> s;
  rep(i, N) {
    int p = N - i;
    int j = index[p - 1];
    int w = -1, x = -1, y = N, z = N;
    auto it1 = s.upper_bound(j);
    if(it1 != s.begin()) {
      it1--;
      x = *it1;
      if(it1 != s.begin()) {
        it1--;
        w = *it1;
      }
    }
    auto it2 = s.upper_bound(j);
    if(it2 != s.end()) {
      y = *it2;
      it2++;
      if(it2 != s.end()) {
        z = *it2;
      }
    }

    ll c1 = (x - w) * (y - j);
    ll c2 = (j - x) * (z - y);
    debugn(s);
    debugn(p, j, w, x, y, z, c1, c2);
    ans += (c1 + c2) * p;

    s.insert(j);
  }
  cout << ans << endl;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}

typedef pair<int,int> pii;
const double pi=acos(-1);
const int N=200010;
const int MX=1e8+5;
int x1,yy1,x2,yy2,n,tot=0,lis;
int g[N],idx[N],a[N],f[N],gx[N],ax[N];
pii pnt[N];
bool deled[N];

int LIS()
{
    int res=0;
    memset(g,0x7f,sizeof(g));
    for(int i=1;i<=tot;i++)
    {
        auto it=lower_bound(g+1,g+1+n,a[i]);
        if(*it==0x7f7f7f7f) res++;
        *it=a[i];
    }
    return res;
}

int main()
{
    x1=read();yy1=read();x2=read();yy2=read();n=read();
    for(int i=1;i<=n;i++) pnt[i].X=read(),pnt[i].Y=read();
    if(x2<x1||yy2<yy1)
    {
        if(x1<=x2) goto swap2;
        x1=MX-x1;x2=MX-x2;
        for(int i=1;i<=n;i++) pnt[i].X=MX-pnt[i].X;
        if(yy1<=yy2) goto work;
        swap2: yy1=MX-yy1;yy2=MX-yy2;
        for(int i=1;i<=n;i++) pnt[i].Y=MX-pnt[i].Y;
    }
    work: sort(pnt+1,pnt+1+n);
    for(int i=1;i<=n;i++)
        if(pnt[i].X>=x1&&pnt[i].X<=x2&&pnt[i].Y>=yy1&&pnt[i].Y<=yy2) a[++tot]=pnt[i].Y;
    double ans=100.0*(x2-x1+yy2-yy1)+(pi*5-20)*(lis=LIS());
    if(lis==min(x2-x1,yy2-yy1)+1) ans+=pi*5;
    output: printf("%.12lf\n",ans);
    return 0;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
	for(int i=1;i<=5;i++)
	{
		cin>>a[i];
		if(a[i]==0)
		{
			cout<<i;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#define N 10000
using namespace std;

struct Card{char suit;char value;};

void bubble(Card a[],int n)
{
    int flag;
    for(int i=0;i<n-1;i++)
    {
        flag=0;
        for(int j=0;j<n-1-i;j++)
            if(a[j].value>a[j+1].value)
            {
                flag=1;
                Card t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        if(flag==0) break;
    }
}

void selection(Card a[],int n)
{
    for(int i=0;i<n;i++)
    {
        int minj=i;
        for(int j=i;j<n;j++)
            if(a[j].value<a[minj].value)
                minj=j;
        Card t=a[i]; a[i]=a[minj];a[minj]=t;
    }
}

void print(Card a[],int n)
{
    for(int i=0;i<n;i++)
    {
        if(i>0) cout<<" ";
        cout<<a[i].suit<<a[i].value;
    }
    cout<<endl;
}

void isstable(Card a[],Card b[],int n)
{
    for(int i=0;i<n;i++)
        if(a[i].suit!=b[i].suit)
        {
            cout<<"Not stable"<<endl;
            return;
        }
    cout<<"Stable"<<endl;
}

int main()
{
    Card C1[100],C2[100];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>C1[i].suit>>C1[i].value;
        C2[i]=C1[i];
    }

    bubble(C1,n);
    selection(C2,n);

    print(C1,n);
    cout<<"Stable"<<endl;
    print(C2,n);
    isstable(C1,C2,n);
}




Measured memory_bytes: 3108
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;

typedef vector<int> VI;

int size[13] = {1, 2, 4, 2, 1, 4, 4, 4, 1, 2, 4, 2, 1};
int move[13][4] = {
  {2},
  {2, 5},
  {0, 1, 6, 3},
  {2, 7},
  {5},
  {1, 4, 6, 9},
  {2, 5, 7, 10},
  {3, 6, 8, 11},
  {7},
  {5, 10},
  {6, 9, 11, 12},
  {7, 10},
  {10}
};

VI v;
map<VI, int> mp;
map<VI, int> mp2;

void make(){
  VI goal;
  for(int i = 0 ; i < 13 ; i++){
    if(i == 0 || i == 12) goal.push_back(0);
    else goal.push_back(i);    
  }
  
  queue<VI> que;
  que.push(goal);
  mp2[goal] = 0;
  
  while(!que.empty()){
    VI q = que.front(); que.pop();    
    if(mp2[q] > 11) continue;
    for(int i = 0 ; i < 13 ; i++){
      if(q[i] != 0) continue;
      for(int j = 0 ; j < size[i] ; j++){
	VI t = q;
	swap(t[i], t[ move[i][j] ]);
	if(mp2.find(t) != mp2.end()) continue;	
	mp2[t] = mp2[q] + 1;	
	que.push(t);
      }
    }
  }
}
    


int bfs(){
  queue<VI> que;
  que.push(v);
  mp[v] = 0;  
  while(!que.empty()){
    VI q = que.front(); que.pop();    
    if(mp2.find(q) != mp2.end()){
      return mp2[q] + mp[q];
    }
    
    if(mp[q] > 10) continue;
    for(int i = 0 ; i < 13 ; i++){
      if(q[i] != 0) continue;      
      for(int j = 0 ; j < size[i] ; j++){
	VI t = q;
	swap(t[i], t[ move[i][j] ]);
	if(mp.find(t) != mp.end()) continue;
	mp[t] = mp[q] + 1;
	que.push(t);
      }
    }
  }
  return -1;
}

void init(){
  v.clear();
  mp.clear();  
}

int main(){
  make();
  int n;
  while(cin >> n){
    if(n == -1) break;
    
    init();
    
    v.push_back(n);
    for(int i = 0 ; i < 12 ; i++){ cin >> n; v.push_back(n); }
    
    int ans = bfs();
    if(ans == -1 || ans > 20) cout << "NA" << endl;
    else cout << ans << endl;
  }
  

  return 0;
}

Measured memory_bytes: 14572
#include <cstdio>

using namespace std;

typedef long long ll;

static const ll MOD = 1000000007LL;

int main()
{
    ll N;
    ll A, B;
    ll X, prevX;
    ll dist, walk;
    ll tiredness = 0;

    scanf("%lld %lld %lld", &N, &A, &B);

    ll i;

    scanf("%lld", &prevX);

    for (i = 1; i < N; i++) {
        scanf("%lld", &X);

        dist = X - prevX;
        walk = dist * A;

        if (walk < B) tiredness += walk;
        else tiredness += B;

        prevX = X;
    }

    printf("%lld\n", tiredness);

    return 0;
}


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

int main(void) {
    long long w, v;
    cin >> w >> v;

    vector<long long> weight(w);
    vector<long long> value(w);
    for (long long i = 0; i < w; ++i)
        cin >> weight[i] >> value[i];

    vector<vector<long long>> kek(w + 1, vector<long long>(v + 1));
    long long W = 0;

    for (long long i = 1; i <= w; ++i)
    for (long long j = 1; j <= v; ++j) {
        kek[i][j] = kek[i - 1][j];
        if (weight[i - 1] <= j)
            kek[i][j] = max(kek[i][j], value[i - 1] + kek[i - 1][j - weight[i - 1]]);
    }

    cout << kek[w][v] << endl;
}


Measured memory_bytes: 83052
#include<iostream>
#include<vector>
#include<string>
#include<tuple>
#include<algorithm>
#include<iomanip>
#include<math.h>
#include<stdio.h>

using namespace std;

int main(){

    int N;
    cin >> N;

    if(N <= 999)
    {
        cout << "ABC" << endl;
    }
    else
    {
        cout << "ABD" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;

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

	double inf = 1e10;
	class D{
		double l[] = new double[3];
		double r[] = new double[3];
		public D(){
			for(int i=0; i<3; i++) {
				l[i] = inf;
				r[i] = -inf;
			}
		}
		public void add(double x, int v) {
			v++;
			l[v] = Math.min(l[v], x);
			r[v] = Math.max(r[v], x);
		}

		public double get(double t) {
			double minl = inf;
			double maxr = -inf;
			for(int i=0; i<3; i++) {
				minl = Math.min(minl, l[i]+(t*i));
				maxr = Math.max(maxr, r[i]+(t*i));
			}
			return maxr-minl;
		}
		public ArrayList<Double> events() {
			ArrayList<Double> el = new ArrayList<>();
			for(int i=0; i<3; i++) {
				for(int j=0; j<i; j++) {
					double t = (l[j]-l[i])/(i-j);
					if(t>0) el.add(t);
					t = (r[j]-r[i])/(i-j);
					if(t>0) el.add(t);
				}
			}
			return el;
		}
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		D dx = new D();
		D dy = new D();
		for(int i=0; i<n; i++) {
			double x = sc.nextInt();
			double y = sc.nextInt();
			char d = sc.next().charAt(0);
			if(d=='R') {dx.add(x, 1); dy.add(y, 0);}
			if(d=='L') {dx.add(x, -1); dy.add(y, 0);}
			if(d=='U') {dx.add(x, 0); dy.add(y, 1);}
			if(d=='D') {dx.add(x, 0); dy.add(y, -1);}
		}
		ArrayList<Double> nsl = new ArrayList<>();
		nsl.add(0.0);
		nsl.add(inf);
		nsl.addAll(dx.events());
		nsl.addAll(dy.events());
		Collections.sort(nsl);
		double min = 1e18;
		for(double t : nsl) {
			min = Math.min(min, dx.get(t) * dy.get(t));
		}
		System.out.println(String.format("%.10f", min));
		sc.close();
	}
}


Measured memory_bytes: 60664
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
#include <functional>
using i64 = long long;
using P = std::pair<i64, int>;

int main() {
    constexpr i64 inf = std::numeric_limits<i64>::max();
    int n, m;
    i64 s;
    std::cin >> n >> m >> s;

    std::vector<std::vector<std::pair<int, i64>>> g(2501 * n);
    auto get = [=](int i, int c) { return i * 2501 + c; };
    for (int i = 0; i < m; i++) {
        int u, v;
        i64 a, b;
        std::cin >> u >> v >> a >> b;
        --u; --v;
        for (int j = a; j <= 2500; j++) {
            g[get(u, j)].emplace_back(get(v, j - a), b);
            g[get(v, j)].emplace_back(get(u, j - a), b);
        }
    }

    if (s > 2500) {
        std::vector<i64> dist(g.size(), inf);
        std::priority_queue<P, std::vector<P>, std::greater<>> q;
        dist[2500] = 0; // get(0, s)
        q.emplace(0, 2500);
        while (!q.empty()) {
            const auto [c, j] = q.top();
            q.pop();
            if (dist[j] < c) continue;
            for (const auto [to, cc] : g[j]) {
                const auto nc = c + cc;
                if (dist[to] <= nc) continue;
                dist[to] = nc;
                q.emplace(nc, to);
            }
        }

        for (int i = 1; i < n; i++) {
            i64 ret = inf;
            for (int j = 0; j <= 2500; j++) ret = std::min(ret, dist[get(i, j)]);
            std::cout << ret << std::endl;
        }
    }

    for (int i = 0; i < n; i++) {
        i64 c, d;
        std::cin >> c >> d;
        for (int j = 0; j + c <= 2500; j++) {
            g[get(i, j)].emplace_back(get(i, j + c), d);
        }
    }

    if (s > 2500) return 0;

    std::vector<i64> dist(g.size(), inf);
    std::priority_queue<P, std::vector<P>, std::greater<>> q;
    dist[s] = 0; // get(0, s)
    q.emplace(0, s);
    while (!q.empty()) {
        const auto [c, j] = q.top();
        q.pop();
        if (dist[j] < c) continue;
        for (const auto [to, cc] : g[j]) {
            const auto nc = c + cc;
            if (dist[to] <= nc) continue;
            dist[to] = nc;
            q.emplace(nc, to);
        }
    }

    for (int i = 1; i < n; i++) {
        i64 ret = inf;
        for (int j = 0; j <= 2500; j++) ret = std::min(ret, dist[get(i, j)]);
        std::cout << ret << std::endl;
    }

    return 0;
}


Measured memory_bytes: 23736
#include<bits/stdc++.h>
using namespace std;
int main(){
 int h,n;
  cin>>h>>n;
  int a[n];
  int s=0;
  for(int i=0;i<n;i++){
  cin>>a[i];
  s=s+a[i];
  }
  
  if(s>=h)
    cout<<"Yes";
  else
    cout<<"No";
  
return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main() {

	int s[4], t[4], ss ,st;

	ss=st=0;
	for(int i=0; i<4; i++) {
		cin >> s[i];
	}
	for(int i=0; i<4; i++) {
		cin >> t[i];
	}
	for(int i=0; i<4; i++) {
		ss+=s[i];
		st+=t[i];
	}
	cout << (ss>=st ? ss : st) << endl;

	return 0;

}

Measured memory_bytes: 0
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstring>
#include<deque>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << endl

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int dp[101][1 << 15];

template<typename T>
bool chmin(T &_a, T _b){
    if(_a > _b){
        _a = _b;
        return true;
    }else{
        return false;
    }
}

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

    int n, m;
    while(cin >> n >> m, n){
        vector<int> s(n);
        rep(i, n){
            cin >> s[i];
        }

        vector<int> d(m);
        rep(i, m){
            cin >> d[i];
        }

        SORT(d);

        vector<int> sum(1 << n);
        rep(i, 1 << n){
            int t = 0;
            rep(j, n){
                if(i >> j & 1){
                    t += s[j];
                }
            }
            sum[i] = t;
        }

        fill(dp[0], dp[m + 1], IINF);
        dp[0][0] = 0;

        rep(i, m){
            rep(j, 1 << n){
                chmin(dp[i + 1][j], dp[i][j] + abs(sum[j] - d[i]));
                rep(k, n){
                    chmin(dp[i][j | (1 << k)], dp[i][j]);
                }
            }
        }

        int ans = IINF;
        rep(j, 1 << n){
            chmin(ans, dp[m][j]);
        }

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 16216
#include<iostream>
using namespace std;
int main(){
	int N;
	long long L[87];
	long long c1=L[0]=2;
	long long c2=L[1]=1;
	cin>>N;
	for(int i=2;i<=N;i++){
		L[i]=c1+c2;
		c1=c2;
		c2=L[i];
	}
	cout<<L[N];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll A, B, N;
    cin >> A >> B >> N;
    ll ans = 0;
        if (N <= 10000){
    for(int i = 1; i <= N; i++) {
        if (floor(A*i/B) - A * floor(i/B) > ans) {
            ans = floor(A*i/B) - A * floor(i/B);
            }
    }
    }
    else {
        if (min({A, B, N}) == N || B > N) ans = floor(A*N/B) - N * floor(N/B);
        else if (min({A, B, N}) == A) ans = A-1;
        else ans = floor(A*(B-1)/B) - N * floor((B-1)/B);
    }
    cout << ans;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<string> svec;

#define IN_LL(in) ll in; cin >> in
#define IN_STR(in) string in; cin >> in
#define IN_VEC(in, size) vec in; for(int i = 0; i < (size); ++i){int ____cur; cin >> ____cur; in.push_back(____cur); } 0
#define IN_SVEC(in, size) svec in; for(int i = 0; i < (size); ++i){int ____cur; cin >> ____cur; in.push_back(____cur); } 0

#define OUT(out) cout << (out)
#define OUT_VEC(out) for(ll i = 0; i < (out).size(); ++i) cout << (out)[i] << endl

vec func(vec s){
	vec res(s.size() + 1);
	for(ll ss : s){
		++(res[ss - 1]);
	}
	return res;
}

int main(void){
	IN_LL(n);
	vec a;
	for(int i = 0; i < n - 1; ++i){
		int cur;
		cin >> cur;
		a.push_back(cur);
	}
	
	vec res = func(a);
	
	OUT_VEC(res);
	return 0;
}

Measured memory_bytes: 7992
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <limits>
#include <queue>
using namespace std;

#define rep(i,N) for(int i=0; i<N; i++)

typedef long long ll;

int main(void)
{
    int N;
    cin >> N;
    priority_queue<int> A;

    rep(i,N){
        int a;
        cin >> a;
        A.push(a);
    }

    int max = 0;
    while(true){
        max = A.top();A.pop();

        if (A.empty()) break;
        int sec_max = A.top();
        if (max % sec_max > 0) A.push(max % sec_max);

        //auto B = A;
        //while(!B.empty()){
        //    cout << B.top() << ",";
        //    B.pop();
        //}
        //cout << endl;
    }


    cout << max << endl;
}


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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, W;
  cin >> N >> W;
  vector<vector<ll>> WV(N + 1, vector<ll>(2));
  for (int i = 1; i <= N; i++)
    cin >> WV[i][0] >> WV[i][1];
  vector<vector<ll>> dp(N + 1, vector<ll>(W + 1, 0));
  for (int i = 1; i <= N; i++) {
    for (int w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      if (w - WV[i][0] < 0) continue;
      dp[i][w] = max(dp[i][w], dp[i - 1][w - WV[i][0]] + WV[i][1]);
    }
  }
  cout << dp[N][W] << '\n';
  return 0;
}


Measured memory_bytes: 80256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

for A in range(-int(X**(1/3))-1, int(X**(1/3))+1):
	for B in range(-int(X**(1/3)), A):
		if B**5 == A**5-X:
			print(A, B)
			exit()


Measured memory_bytes: 10308
#include <stdio.h>

int main(void)
{
	int h, m, s;
	int t;
	int H, M, S;
	int H3, M3, S3;
	for(; ; ) {
		scanf("%d%d%d", &h, &m, &s);
		if(h==-1 && m==-1 && s==-1) break;
		t=7200-h*3600-m*60-s;
		H=t/3600;
		M=(t-H*3600)/60;
		S=t-H*3600-M*60;
		t*=3;
		H3=t/3600;
		M3=(t-H3*3600)/60;
		S3=t-H3*3600-M3*60;
		printf("%02d:%02d:%02d\n", H, M, S);
		printf("%02d:%02d:%02d\n", H3, M3, S3);
	}
	
	return 0;
}


Measured memory_bytes: 612
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B; cin >> A >> B;
  if(A >= 13) {
      cout << B << endl; return 0;
  }
  else if(A <= 12 && A >= 6) {
      cout << B / 2 << endl; return 0;
  }
  else {
      cout << 0 << endl; 
  }
  return 0;
}

Measured memory_bytes: 256
N, M = gets.split(' ').map(&:to_i)
p = gets.split(' ').map(&:to_i)

@par = (0..N).to_a

def root(i)
	return i if @par[i] == i
	@par[i] = root(@par[i])
end

def same(i, j)
	if root(i) == root(j)
      return true
    else
      return false
    end
end

def unite(i, j)
	i = root(i)
	j = root(j)
	if !same(i, j)
		@par[j] = i
	end
end

M.times do
	x, y = gets.split(' ').map(&:to_i)
	x, y = y, x if x > y
	unite(x, y)
end

cnt = 0
1.upto(N) do |i|
	cnt += 1 if same(i, p[(i - 1)])
end

puts cnt

Measured memory_bytes: 11404
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e9
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<int, int> P;

struct SegTree{
	int size;
	vector<llint> seg;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++) seg[i] = -inf;
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = max(seg[i*2], seg[i*2+1]);
		}
	}

	llint query(int a, int b, int k, int l, int r)
	{
		if(b < l || r < a) return -inf;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return max(lval, rval);
	}
	llint query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

int h, w, m;
vector<llint> vec[300005];
llint a[300005];
SegTree seg(19);

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> h >> w >> m;
	llint y, x;
	for(int i = 1; i <= m; i++){
		cin >> y >> x;
		vec[y].push_back(x);
		a[x]++;
	}
	
	seg.init();
	for(int i = 1; i <= w; i++) seg.update(i, a[i]);
	
	llint ans = 0;
	for(int i = 1; i <= h; i++){
		llint tmp = 0;
		for(int j = 0; j < vec[i].size(); j++){
			tmp++;
			llint x = vec[i][j];
			seg.update(x, seg.query(x, x) - 1);
		}
		ans = max(ans, tmp + seg.query(1, w));
		for(int j = 0; j < vec[i].size(); j++){
			llint x = vec[i][j];
			seg.update(x, seg.query(x, x) + 1);
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 30092
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf = 1e9;

string s[101];
int N,L;
int main(){
    cin>>N>>L;
    REP(i,0,N){
        cin>>s[i];
    }
    sort(s,s+N);
    REP(i,0,N){
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;

#define rep(i,x,y) for(int i=(x); i<(y); ++i)
const int INF = (1<<30);
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;

template <typename T>
void vec_print(vector<T> VEC){
  rep(i, 0, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  rep(i, 0, MAT.size()){
    rep(j, 0, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << endl;
  }
};

class HOGE{
  public:
    ll index;
    ll value;
    HOGE(ll index, ll value){
      this->index = index;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "index : " << index << ", value : " << value << endl;
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

int main(){
  ll A, B, X;
  cin >> A >> B >> X;
  if(X < A || A+B < X){
    cout << "NO" << endl;
  }else{
    cout << "YES" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
/*
 *  author: chw0501
 *  reference: https://jinpyo.kim/EducationalDP-solution
 *  created: 26.04.2020 04:56:41(UTC)
*/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define MOD 1000000007 
#define INF 987654321 

int h,w,n;
vector<P> v;
ll fac[200010];
ll inv[200010];
ll invfac[200010];
//dp[i]: i번째 벽에 최단 거리로 도착하는 가짓수(그 전에 벽을 만나지 않아야 함)
ll dp[3010];

int main(){
	cin>>h>>w>>n;
	fac[0]=1;
	for(ll i=1;i<200010;i++){
		fac[i]=(fac[i-1]*i)%MOD;
	}
	inv[0]=1;
	inv[1]=1;
	for(ll i=2;i<200010;i++){
		inv[i]=(MOD-((MOD/i)*inv[MOD%i])%MOD)%MOD;
	}
	invfac[0]=1;
	for(ll i=1;i<200010;i++){
		invfac[i]=(invfac[i-1]*inv[i])%MOD;
	}
	for(int i=0;i<n;i++){
		int r,c;
		scanf("%d %d",&r,&c);
		r--; c--;
		v.emplace_back(r,c);
	}
	v.emplace_back(h-1,w-1);
	sort(v.begin(),v.end());
	//i번째 벽에 도착하는 가짓수(dp[i]계산)
	for(int i=0;i<=n;i++){
		//i번째 벽에 도착하기 전에 j번째 벽에 도착하는 경우를 빼줘야 함
		int ri=v[i].first;
		int ci=v[i].second;
		//일단 default값은 (ri+ci) C ri
		dp[i]=(((fac[ri+ci]*invfac[ri])%MOD)*invfac[ci])%MOD;
		for(int j=0;j<n;j++){
			int rj=v[j].first;
			int cj=v[j].second;
			if(ri<rj || ci<cj) continue;
			if(ri==rj && ci==cj) continue;
			int x=ri-rj;
			int y=ci-cj;
			ll val=(((fac[x+y]*invfac[x])%MOD)*invfac[y])%MOD;
			dp[i]=(dp[i]+MOD-(dp[j]*val)%MOD)%MOD;
		}
	}
	cout<<dp[n];
	return 0;
}

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

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == 5) {
        if ((b == 5 && c == 7) || (b == 7 && c == 5)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else {
        if (b == 5 && c == 5) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
S = list(input())
N = len(S)
S = S[::-1]

cur_pos = 0
tmp_str = ''
str_list = ['maerd', 'remaerd', 'esare', 'resare']

while (cur_pos < N):
    tmp_str += S[cur_pos]

    if (tmp_str in str_list):
        tmp_str = ''
    
    cur_pos += 1

if (tmp_str == ''):
    print('YES')
else:
    print('NO')


Measured memory_bytes: 4768
from collections import defaultdict as dd
from functools import reduce

if __name__ == "__main__":
    N = int(input())
    arr = map(int, input().split())

    dic = dd(int)

    for el in arr:
        dic[el] += 1

    count = len(dic) - len(list(filter(lambda x: x %
                                       2 == 0, dic.values()))) % 2
    print(count)


Measured memory_bytes: 22756
#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)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1 ; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1 ; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const bool debug = 0;
/***************************************/

int N;
int a[300];
int dp1[300][301]; // [l, r)
int dp2[301];

int main() {
	while (cin >> N, N) {
		REP(i, N) scanf("%d", a + i);
		
		memset(dp1, 0, sizeof(dp1));
		REP(i, N - 1) if (abs(a[i] - a[i + 1]) <= 1) dp1[i][i + 2] = 2;
		FOR(w, 4, N + 1) {
			REP(i, N - w + 1) {
				int l = i, r = i + w; // [l, r)
				FOR(k, l + 1, r) { // [l, k), [k, r)
					if (dp1[l][k] && dp1[k][r]) dp1[l][r] = w;
				}
				if (abs(a[l] - a[r - 1]) <= 1 && dp1[l+1][r-1]) dp1[l][r] = w;
			}
		}
		
		memset(dp2, 0, sizeof(dp2));
		REP(i, N) {
			FOR(j, i + 1, N + 1) chmax(dp2[j], dp2[i] + dp1[i][j]);
			chmax(dp2[i + 1], dp2[i]);
		}
		
		if (debug) printf("@ ");
		cout << dp2[N] << endl;
	}
	return 0;
}



Measured memory_bytes: 3500
n = int(input())
a = [int(s) for s in input().split()]

count = 0
same_color = 1
for i in range(1, n):
    if a[i] == a[i - 1]:
        same_color += 1
    else:
        count += same_color // 2
        same_color = 1
if same_color > 1:
    count += same_color // 2
print(count)

Measured memory_bytes: 9184
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nm = InputNumList();
            var n = nm[0];
            var m = nm[1];
            var a = InputNumList();

            a.Sort();

            var listDis = new List<int>();
            if (m == 1) listDis.Add(0);
            else
            {
                for (int i = 0; i < m - 1; i++)
                {
                    listDis.Add(a[i + 1] - a[i]);
                }
            }

            listDis.Sort();
            listDis.Reverse();

            for (int i = 0; i < n - 1; i++)
            {
                if (listDis.Count != 0)
                {
                    listDis.RemoveAt(0);
                }
                else
                {
                    break;
                }
            }

            WriteLine(listDis.Sum());
        }

        static int InputNum()
        {
            return int.Parse(ReadLine());
        }
        static List<int> InputNumList()
        {
            return ReadLine().Split(' ').Select(int.Parse).ToList();
        }
    }
}

Measured memory_bytes: 20960
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

/*
 *変数
 */
int n;

/*
 *解 
 */
void solve(){
    if(n%2==0)printf("%d",n);
    else printf("%d",n*2);
}

/*
 *入力 
 */
int main(){
       std::cin.tie(0);
       std::ios::sync_with_stdio(false);
       std::cin>>n;
       solve();
       return 0;
}

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

namespace AtCoder.Abc
{
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列の入力
            // string s = Console.ReadLine();

            // 整数の入力
            // long n = long.Parse(Console.ReadLine());

            // 文字列配列の入力
            // string[] inputStrArray = Console.ReadLine().Split(' ');

            // 整数配列の入力
            var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            var A = inputLongArray[0];
            var B = inputLongArray[1];
            var H = inputLongArray[2];
            var M = inputLongArray[3];

            double H_deg = (H * (double)30) + ((M / (double)60) * (double)30);
            double M_deg = (double)360 * (M / (double)60);

            double HM_diff = (H_deg - M_deg) * (Math.PI / (float)180);

            double cosC = Math.Cos(HM_diff);

            double c = Math.Sqrt(Math.Pow(A, 2) + Math.Pow(B, 2) - 2 * A * B * cosC);

            Console.WriteLine(c);
            Console.Out.Flush();
        }
    }
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

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

void solve() {

}

int main() {
  int n;
  cin >> n;
  vector<ll> vec(n);
  rep(i,n) cin >> vec[i];
  ll sum = 0;
  REP(i,1,n) {
    if( vec[i-1] > vec[i] ) {
      sum += ( vec[i-1] - vec[i] );
      vec[i] = vec[i-1];
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 4836
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

int main(){
    int N,A[200001],m=0,m1=0,m2=0;
    cin>>N;
    for(int k=0;k<N;k++){
        cin>>A[k];
        if(m<A[k]){
            m2=m;
            m=A[k];
            }
            else{
        if(m2<A[k]){
            m2=A[k];
        }
            }
    }
    for(int i=0;i<N;i++){
        if(A[i]==m)cout<<m2<<endl;
        else cout<<m<<endl;
    }
    return 0;
}

Measured memory_bytes: 2432
class Array
  def swap(x, y)
    self[x], self[y] = self[y], self[x]
  end
end

def bubbleSort(n, a)
  bs = a.clone
  n.times{|i|
    (n-1).downto(i+1){|j|
      bs[j][1]<bs[j-1][1]&&bs.swap(j,j-1)
    }
  }
  return bs
end

def selectionSort(n, a)
  ss = a.clone
  stability = 1
  n.times{|i|
    min = i
    dup = nil
    (i+1..n-1).each{|j|
      ss[j][1]<ss[min][1]&&min=j
      ss[j][1]==ss[i][1]&&dup=j
    }
    (dup!=nil)&&(dup<min)&&(stability=0)
    i!=min&&ss.swap(i,min)
  }
  return ss, stability
end

n = gets.to_i
a = gets.split
bs = bubbleSort(n, a)
puts bs.join(" ")
puts "Stable"
ss, stability = selectionSort(n, a)
puts ss.join(" ")
puts (stability == 1) ? "Stable" : "Not stable"

Measured memory_bytes: 8812
# -*- coding: utf-8 -*-
"""
Set Operation - Set Intersection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_9_B&lang=jp

"""
_ = input()
A = set([int(a) for a in input().split()])
_ = input()
B = set([int(b) for b in input().split()])
ans = sorted(A & B)
if ans:
    print(*ans, sep='\n')



Measured memory_bytes: 44904
A,B = input().split()

A = int(A)
B = float(B)

#B_by100 = int(B*100)
#ans_by100 = A*B_by100
#ans=ans_by100//100

B_by1000 = int(B*1000)
ans_by1000 = A*B_by1000
ans=ans_by1000//1000

#ans = math.floor(ans_by100/100)

#A_hund = int(A//100)
#A_res = int(A-A_hund*100) 
#
#ans1 = int(A_hund * B * 100)
#ans2 = int(A_res * B) 

#ans = A*B
#ans = ans1+ans2
#ans = int(ans)
print(str(ans))

Measured memory_bytes: 61808
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int a,b;
  cin >> a >> b;
  cout << max(0,a - 2*b) << endl;
}



Measured memory_bytes: 256
# ABC137D - Summer Vacation
import sys
input = sys.stdin.readline

from heapq import heappush, heappushpop


def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    T = [[] for _ in range(M + 1)]
    for a, b in A:
        if a <= M:
            T[M - a] += [b]
    q = []
    for i in range(M + 1):
        for v in T[i]:
            if len(q) <= i:
                heappush(q, v)
            else:
                heappushpop(q, v)
    print(sum(q))


if __name__ == "__main__":
    main()

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

int main(){
    cin.sync_with_stdio(false);
    
    int n; cin >> n;
    vector<long long> v(n);
    for(int i = 0; i < n; i++){
        cin>>v[i];
    }

    vector<vector<long long>>dp(n, vector<long long>(n));

    for(int i = 0; i < n; i++){
        dp[i][i] = v[i];
    }

    for(int i = 2; i <=n; i++){
        for(int j = n-i; j >= 0; j--){
            dp[j][j+i-1] = max(v[j]-dp[j+1][j+i-1], v[j+i-1]-dp[j][j+i-2]);
        }
    }

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


Measured memory_bytes: 73620
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    int N;
    cin>>N;
    vector<int> A(N),B(N);
    REP(i,N){
      cin>>A[i]>>B[i];
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    if(N%2==0){
      cout<<(((B[N/2-1]+B[N/2])-(A[N/2-1]+A[N/2]))+1)<<endl;
    }else{
      cout<<B[N/2]-A[N/2]+1<<endl;
    }

    
}

Measured memory_bytes: 4804
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

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

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

type point struct {
	y, x, d int
}

func main() {
	sc.Split(bufio.ScanWords)

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

	h, w := scanInt(), scanInt()
	maze := make([]string, h)
	for i := 0; i < h; i++ {
		maze[i] = scanText()
	}

	sum := 0
	dd := make([][]int, h)
	for i := 0; i < h; i++ {
		dd[i] = make([]int, w)
		for j := 0; j < w; j++ {
			if maze[i][j] == '#' {
				sum++
			}
		}
	}

	queue := make([]point, 0)
	queue = append(queue, point{y: 0, x: 0, d: 0})

	for len(queue) > 0 {
		now := queue[0]
		queue = queue[1:]

		for i := 0; i < 4; i++ {
			nextY, nextX := now.y+dy[i], now.x+dx[i]
			if nextY < 0 || nextY >= h || nextX < 0 || nextX >= w || maze[nextY][nextX] == '#' || dd[nextY][nextX] != 0 {
				continue
			}
			if nextY == 0 && nextX == 0 {
				continue
			}

			dd[nextY][nextX] = now.d + 1
			queue = append(queue, point{y: nextY, x: nextX, d: now.d + 1})
		}
	}

	if dd[h-1][w-1] == 0 {
		fmt.Println(-1)
	} else {
		fmt.Println(h*w - (dd[h-1][w-1] + sum + 1))
	}

}


Measured memory_bytes: 896
#include <stdio.h>
#define MAX 100000
#define INFTY 114514810

typedef struct {
  char d;
  int f;
}CARD;

CARD A[MAX],B[MAX],L[MAX],R[MAX];

void quicksort(int,int);
int partition(int,int);
//void bubblesort(int);
void mergeSort(int,int);
void merge(int,int,int);

int main() {

  int n,i,flag=0;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++) {
    scanf(" %c %d",&A[i].d,&A[i].f);
    B[i] = A[i];  
  }

  
  quicksort(0,n-1);
  //bubblesort(n);
  mergeSort(0,n);


  for(i = 0; i < n; i++) {
    if(A[i].d != B[i].d)
      flag = 1;
  }

  if(flag) printf("Not stable\n");
  else printf("Stable\n");
  
  for(i = 0; i < n; i++) {
    printf("%c %d\n",A[i].d,A[i].f);
  }

  /* for(i = 0; i < n; i++) {
     printf("%c %d\n",B[i].d,N[i].f);
     }
  
  */

  return 0;
}

void quicksort(int p,int r)
{
  int q;
  if(p < r) {
    q = partition(p,r);
    quicksort(p,q-1);
    quicksort(q+1,r);
  }
}

int partition(int p,int r)
{
  int x,i,j;
  CARD temp;
  x = A[r].f;
  i = p-1;
  for(j = p; j < r; j++) {
    if(A[j].f <= x) {
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;
  return i+1;
}

/*void bubblesort(int N)
{
  int i,j,flag;
  CARD temp;
  flag = 1;
  while(flag) {
    flag = 0;
    for(j = N-1; j > 0; j--) {
      if(B[j].f < B[j-1].f) {
	temp = B[j];
	B[j] = B[j-1];
	B[j-1] = temp;
	flag = 1;
      }      
    }
  }
}
*/

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

void merge(int left,int mid,int right)
{
  int n1,n2,i,j,k;
  n1 = mid - left;
  n2 = right - mid;

  for(i = 0; i < n1; i++) {
    L[i] = B[left + i];
  }
  for(i = 0; i < n2; i++) {
    R[i] = B[mid + i];
  }
  L[n1].f = INFTY;
  R[n2].f = INFTY;
  i = 0;
  j = 0;
  
  for(k = left; k < right; k++) {
    if(L[i].f <= R[j].f) {
      B[k] = L[i];
      i = i + 1;
    }
    else {
      B[k] = R[j];
      j = j + 1;
    }
}
}



Measured memory_bytes: 4076
i,n;main(c,v){for(;;){for(v=c=i=0;i-5;n?:exit(0),v|=n<<i++*2,c|=1<<n)scanf("%d",&n);for(n=11328>>c&3,i=0;i-5;++i){printf("%d\n",(v>>i*2&3)-n?n?2:3:1);}}}

Measured memory_bytes: 600
#include <stdio.h>
void fibonacci(int n);
int main(){
  int n;
   
 
  scanf("%d",&n);
  fibonacci(n);

  
  return 0;
}


void fibonacci(int n){
  
  int F[n];
  int i;


  
  F[0]=1;
  F[1]=1;
  for(i=2;i<=n;i++){
    
    F[i]=F[i-1]+F[i-2];
    
  }

  
  printf("%d\n",F[n]);
}

Measured memory_bytes: 596