akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN = 100050;
int A[MAXN];

int main() {
	int N, T;
	scanf("%d%d", &N, &T);
	for(int i=0;i<N;i++)
		scanf("%d", &A[i]);
	int big=A[N-1];
	int bst=0, cnt=0;
	for(int i=N-2;i>=0;i--) {
		if(big-A[i]>bst)
			bst=big-A[i], cnt=1;
		else if(big-A[i]==bst)
			cnt++;
		big=max(big, A[i]);
	}
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 768
/*
 * Pawan Harendra Mishra
 */

/*
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
*/

/*
 * Windows Powershell
 * Get-Content input.txt | ./a.exe > output.txt
 */

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mod 1000000007
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll a, p;

int main(int argc, char const *argv[])
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);

    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // //freopen("output.txt", "w", stdout);
    // #else
    // // online submission
    // #endif
    
    cin >> a >> p;
    cout << (3*a + p)/2 << endl;
    return 0;
}

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 1e9+7
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<pint>>;

int main(){
    int N,M; cin>>N>>M;
    vector<vector<ll>> dist(N,vector<ll>(N,INF));
    rep(i,N){
        rep(j,N){
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }
    
    vector<ll> a(M),b(M),c(M);
    rep(i,M){
        cin>>a[i]>>b[i]>>c[i];
        --a[i]; --b[i];
        dist[a[i]][b[i]] = c[i];
        dist[b[i]][a[i]] = c[i];
    }

    rep(k,N){
        rep(i,N){
            rep(j,N){
                dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
            }
        }
    }

    int res = 0;
    rep(i,M){
        if(c[i]>dist[a[i]][b[i]])++res;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3636
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

dp = [0] * (n+1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i - 2]
    dp[i] %= 1000000007

print(dp[n])




Measured memory_bytes: 56664
def main():
    high, width = map(int, input().split())
    ans = [''.join(['#' for i in range(width + 2)])]
    ans = ans + ['#' + input() + '#' for i in range(high)] + ans


    for i in range(high + 2):
        print(ans[i])

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
N = int(input())
A = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, f, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = f(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, e, n, dat = self.f, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(res, dat[r])
            l >>= 1
            r >>= 1
        return res


gcd = lambda x, y: gcd(y, x) if x < y else gcd(y, x % y) if y else x
e = 0
size = N
ST = SegmentTree(A, f=gcd, e=e, size=size)
ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)


Measured memory_bytes: 128732
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pll pair<ll,ll>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vll vector<ll>
#define vbl vector<bool>
#define vvll vector<vll>
#define vld vector<ld>
#define vb vector<bool>
#define vc vector<char>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()

template<class T> ostream& operator<<(ostream &os, vector<T> V){
	os << "[ ";
	for(auto v  : V) os << v << " ";
	return os << " ]";
}
template<class T> ostream& operator<<(ostream &os, set<T> V){
	os << "[ ";
	for(auto v  : V) os << v << " ";
	return os << " ]";
}
template<class T , class R > ostream& operator<<(ostream &os, map<T , R> V){
	os << "[ ";
	for(auto v  : V) os << "(" << v.first << ":" << v.second << ")";
	return os << " ]";
}
template<class T , class R > ostream& operator<<(ostream &os, pair<T , R> V){
	return os << "(" << V.first << "," << V.second << ")";
}

#define cerr cout
#define TRACE
#ifdef TRACE
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');
        cerr.write(names, comma - names) << " : " << arg1<<" | ";
        __f(comma+1, args...);
    }
    clock_t clk=clock();
    #define checktime() cout<<"\nTime Elapsed : "<<float(clock()-clk)/CLOCKS_PER_SEC<<endl
#else
    #define trace(...);
    #define checktime();
#endif

const ll Mod = 1e9 + 7;
// const ll Mod = 998244353;
const ll MAXN = 1e6;

void solve(){
    ll n,m,x;cin>>n>>m>>x;
    vll c(n);
    vvll a(n,vll(m));
    for(ll i=0;i<n;i++){
        cin>>c[i];
        for(ll j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ll ans=1ll<<60;
    for(ll i=0;i<(1<<n);i++){
        vll val(m,0);
        ll cost=0;
        for(ll k=0;k<n;k++){
            if(1<<k & i){
                cost+=c[k];
                for(ll j=0;j<m;j++) val[j]+=a[k][j];
            }
        }
        bool f=1;
        for(ll pp:val){
            if(pp<x){
                f=0;break;
            }
        }
        if(f) ans=min(ans,cost);
    }
    if(ans==1ll<<60) cout<<"-1\n";
    else cout<<ans<<"\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout<<fixed<<setprecision(25);

    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3688
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
int n,a;
int x[55];

ll dp[55][55][55*55];
ll solve(int k,int c,int s){
  if(k == n){
    return (c*a==s?1:0);
  }
  if(dp[k][c][s] >= 0) return dp[k][c][s];
  return dp[k][c][s] = solve(k+1,c+1,s+x[k]) + solve(k+1,c,s);
}

int main(void){
  cin >> n >> a;
  for(int i = 0; i < n; i++){
    cin >> x[i];
  }
  memset(dp,-1,sizeof(dp));
  cout << solve(0,0,0)-1 << endl;
}


Measured memory_bytes: 71808
#include <iostream>
using namespace std;
int k[11];
int s[11][11];
int p[11];
int main() {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  for (int i=0; i<M; i++) {
    cin >> k[i];
    for (int j=0; j<k[i]; j++) {
      cin >> s[i][j];
      s[i][j]--;
    }
  }
  for (int i=0; i<M; i++) {
    cin >> p[i];
  }
  int ret = 0;
  for (int i=0; i<(1<<N); i++) {
    int t[11] = {0};
    int ii = i;
    for (int j=0; j<N; j++) {
      t[j] = ii & 1;
      ii = ii >> 1;
    }
    int r = 1;
    for (int j=0; j<M; j++) {
      int d = 0;
      for (int a=0; a<k[j]; a++) {
        d += t[s[j][a]];
      }
      if (d % 2 != p[j]) {
        r = 0;
        break;
      }
    }
    ret += r;
  }
  cout << ret << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>

#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	int X;
	cin >> X;

	for (int i = X; true; i++) {
		bool flag = true;
		for (int j = 2; j <= sqrt(i); j++) {
			if (i % j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			COUT(i);
			return 0;
		}
	}



	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, c;

    cin >> a >> b >> c;

    if (a - b == b - c) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int Q,H,S,D,N;cin>>Q>>H>>S>>D>>N;
    if(H>Q*2)H=Q*2;
    if(S>H*2)S=H*2;
    if(D>S*2)D=S*2;
    cout<<N/2*D+(N%2)*S<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<bool> ok(100100,true);
    ok[1]=false;
    for(int i=2; i*i<=100000; i++){
        if(ok[i]==true){
            for(int j=2*i; j<=100000; j+=i){
                ok[j]=false;
            }
        }
    }
    vector<int> cnt(100100,0);
    for(int i=3; i<=100000; i++){
        if(ok[i]&&ok[(i+1)/2]){
            cnt[i]=cnt[i-1]+1;
        }
        else cnt[i]=cnt[i-1];
    }
    int Q;cin >> Q;
    vector<int> l(Q),r(Q);
    for(int i=0; i<Q; i++){
        cin >> l[i] >> r[i];
    }
    for(int i=0; i<Q; i++){
        cout << cnt[r[i]]-cnt[l[i]-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

int main(){
int a,b;cin>>a>>b;
if(a%3==0||b%3==0||(a+b)%3==0)cout<<"Possible";
else cout<<"Impossible";
}

Measured memory_bytes: 256
N = input()

try:
  if 0 <= int(N) <= 999:
    if N[-1] == '2' or N[-1] == '4' or N[-1] == '5' or N[-1] == '7' or N[-1] == '9':
      print('hon')
    elif N[-1] == '0' or N[-1] =='1' or N[-1] =='6' or N[-1] =='8':
      print('pon')
    elif N[-1] == '3':
      print('bon')
except ValueError:
  exit()

Measured memory_bytes: 9180
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

int main(){
    string s,t;
    cin >> s >> t;
    
    string s2 = s+s;
    
    bool ans = 0;
    rep(i,s.size()){
        string s3;
        rep(j,s.size()){
            s3 += s2[i+j];
        }
        if(s3 == t) ans = true;
    }
    
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}







Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,k,i;
	long s;
	scanf("%d %d",&n,&k);
	s=k;
	for(i=1;i<=n-1;i++)
	{
s=s*(k-1);
}
 printf("%ld\n",s);
 return 0;
 } 

Measured memory_bytes: 128
n,m  = map(int, input().split())
ten = list(map(int, input().split()))
arr = [list(map(int,input().split())) for i in range(m)]
hikui = []
for i in arr:
    if ten[i[0]-1]<ten[i[1]-1]:
        hikui.append(i[0])
    elif ten[i[1]-1]<ten[i[0]-1]:
        hikui.append(i[1])
    else:
        hikui.append(i[0])
        hikui.append(i[1])
ans = n-len(set(hikui))

print(ans)

Measured memory_bytes: 34664
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[[]for _ in[0]*n]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i,ai in enumerate(a):
  x=lastAppeared[ai-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[ai-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)


Measured memory_bytes: 194660
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int main(){
	int N, K;
	cin >> N >> K;
	ll S;
	cin >> S;

	vector<ll> ans;
	if(S > N){
		for(int i=0; i<K; i++) ans.push_back(S);
		for(int i=K; i<N; i++) ans.push_back(1);
	} else {
		for(int i=0; i<K; i++) ans.push_back(S);
		for(int i=K; i<N; i++) ans.push_back(1e9);
	}

	pr(ans);

	return 0;
}


Measured memory_bytes: 2292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

map<string, ll> m;

int main(void)
{
    ios_base::sync_with_stdio(0);   cin.tie(0);
    ll n, ans = 0;
    cin >> n;
    for(ll i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        if(m.find(s) == m.end()) m[s] = 0;
        ans += m[s];
        ++m[s];
    }
    cout << ans;
    return 0;
}


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


int main()
{
    vector<int> data(4);
    string S;
    cin >> S;
    for(int i=0;i<4;++i)  data.at(i) = S[i] -'0';

    int N = 3;
    for (int bit = 0; bit < (1<<N); ++bit){
        int sum = data.at(0);
        vector<char> s;
        for (int i = 0; i < N; ++i) {
            if (bit & (1 << i)) {
                sum += data[i+1];
                s.push_back('+');
            }
            else {
                sum -=data[i+1];
                s.push_back('-');
            }
        }
        if (sum == 7){
            cout << data[0] << s[0] <<data[1]<< s[1] <<data[2]<< s[2] <<data[3] << "=7" << endl;
        	return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextV  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextV.append(b)
    
q = deque([1]) # 頂点1から幅優先探索
color = [0]*(N+1)
while q:
  v = q.popleft()
  parentC = color[v]
  c = 1
  for child in graph[v]:
    if c == parentC: # 親と同じ色だったら次の色へスキップ
      c += 1
    color[child] = c # 使用した色を保持
    c += 1 # 次の色へスキップ
    q.append(child)
    
print(max(color))    
for b in nextV:
  print(color[b])
  

  

Measured memory_bytes: 18548
n = int(input())
a = list(map(int,input().split()))
asum = abs(a[0])
for i in range(1,len(a)):
    asum += abs(a[i] - a[i - 1])
asum += abs(a[-1])
a.insert(0,0)
a.append(0)
for i in range(1,len(a) - 1):
    ans = asum - abs(a[i] - a[i-1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1])
    print(ans)

Measured memory_bytes: 14176
import sys
A, B, C, D = map(int, input().split())
s, g = 0, 0
if A <= C:
    s = C
    if B < s:
        print(0)
        sys.exit()
else:
    s = A
    if D < s:
        print(0)
        sys.exit()

if B <= D:
    g = B
else:
    g = D

print(g - s)

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


def main():
    s_list = list(map(int, input()))
    for i in range(0, len(s_list) - 1):
        if s_list[i] == s_list[i + 1]:
            print('Bad')
            return
    print('Good')


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define mem0(s) memset(s,0,sizeof(s))
#define meminf(s) memset(s,0x3f,sizeof(s))
#define mp_insert(a,b,c) mp.insert(map<pair<int,int>,int>::value_type(make_pair(a,b),c))
double pi=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
inline ll lowbit(ll x){return x&(-x);}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}
const int INF=0x3f3f3f3f,max_n=100005,mod=1e9+7;
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll pow(ll a,ll b,ll mod){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int a[max_n];
string s;
int x,ans1,ans2;
int vis[max_n];
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x;
		cin>>s;
		if(vis[x])
		{
			continue;
		}
		if(s=="WA")
		{
			a[x]++;
		}
		else if(s=="AC")
		{
			ans1++;
			vis[x]=1;
			ans2+=a[x];
		}
	}
	cout<<ans1<<' '<<ans2;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>                                                               #include <vector>
#include <utility>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
  int N;
  cin >> N;
  cout << ((N % 10 == 9 or N >= 90) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  while(true){
  	int v = n;
    set<int> t;
    while(v) t.insert(v%10), v /= 10;
    if(t.size() == 1){
      cout << n << endl;
      return 0;
    }
    n++;
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    double X;
    double a=100;
    int count=0;
    scanf("%lf",&X);
    while(a<X){
        a=a*1.01;
        long long int b=a;
        a=b;
        count=count+1;
    }
    printf("%d\n",count);
}

Measured memory_bytes: 1752
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <map>
#include <numeric>
#include <cassert>
#include <iomanip>

using namespace std;
#define int long long
#define uint unsigned long long
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr int INF = 1145141919810893;

//
struct Edge {
	int next;
	int w = 1;
};
template<class T>
struct Vertex {
	std::vector<Edge>edges;
	T val = {};
};
template<class T>
struct Graph {
	std::vector<Vertex<T>> vertex;
public:
	Graph(size_t n = 0) :vertex(n) {
	}
	void setArray(int u, int v, int w = 1) {
		vertex[u].edges.push_back(Edge{ v ,w });
	}
	void setConnect(int u, int v, int w = 1) {
		setArray(u, v, w);
		setArray(v, u, w);
	}
	T& val(int u) {
		return vertex[u].val;
	}
	void dfsImpl(int pos, int prev, std::function<void(Vertex<int>& now, Vertex<int>& next, int w)>func) {
		for (auto& e : vertex[pos].edges) {
			if (e.next == prev) continue;
			func(vertex[pos], vertex[e.next], e.w);
			dfsImpl(e.next, pos, func);
		}
	}
	void dfs(int pos, std::function<void(Vertex<int> & now, Vertex<int> & next, int w)>func) {
		dfsImpl(pos, -1, func);
	}
};




#define LOADVEC(type,name,N) std::vector<type>name(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOADVEC2(type,name0,name1,N) std::vector<type>name0(N),name1(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn]; \
}

#define LOADVEC3(type,name0,name1,name2,N) std::vector<type>name0(N),name1(N),name2(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn];cin >> name2[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;


void proc();

signed main() {
	ios::sync_with_stdio(false);
	proc();
	return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/


void proc() {
	LOAD(int, N);
	Graph<int> graph(N);
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		graph.setConnect(u - 1, v - 1, w);
		graph.val(u - 1) = -1;
	}
	graph.val(0) = 0;
	graph.dfs(0, [](Vertex<int> & now, Vertex<int> & next, int w) {
		if (w % 2 == 0) {
			next.val = now.val;
		}
		else {
			next.val = 1 - now.val;
		}
		});
	for (int i = 0; i < N; ++i) {
		cout << graph.val(i) << endl;
	}

}


#endif



Measured memory_bytes: 14720
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
    while(1){
        int n,x;
        int i,j;
        int tarou[300] = {0},hanako[300] = {0};
        int field = 0;
        int flg1 = 0,flg2 = 0;
        scanf("%d",&n);
        if(n == 0) break;
        for(i = 0; i < n; i++){
            scanf("%d",&x);
            tarou[x-1] = x;
        }
        for(i = 0; i < n * 2; i++){
            if(tarou[i] == 0) hanako[i] = i+1;
        }

        sort(tarou,tarou+n*2,greater<int>());
        sort(hanako,hanako+n*2,greater<int>());
        sort(tarou,tarou+n);
        sort(hanako,hanako+n);

        while(1){
            //太郎の番
            for(j = 0; j < n; j++){
                if(field < tarou[j]){
                    field = tarou[j];
                    tarou[j] = -1;
                    flg1++;
                    goto next;
                }
            }
            field = 0;
            next :
            if(flg1 == n || flg2 == n) break;
            for(j = 0; j < n; j++){
                if(field < hanako[j]){
                    field = hanako[j];
                    hanako[j] = -1;
                    flg2++;
                    goto next2 ;
                }
            }
            field = 0;
            next2 :
            if(flg1 == n || flg2 == n) break;
        }
        printf("%d\n%d\n",n-flg2,n-flg1);
    }

    return 0;
}

Measured memory_bytes: 1048
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
//orz jzm
#define ll long long
#define ull unsigned ll
const ll PR=19260817;
int n;
ll a[100005], b[100005];
int main() {
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		scanf("%lld%lld", &a[i], &b[i]);
	}
	ll ans=0ll;
	for (int i=n-1; i>=0; i--) {
		a[i]+=ans;
		if (a[i]%b[i]!=0) {
			ll val=((a[i]/b[i])+1)*b[i]-a[i];
			a[i]+=val;ans+=val;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1792
N = int(input())
*A, = map(int,input().split())

S = sum(A)

Sb = 0
for i,a in enumerate(A):
    Sb += a
    if Sb>=S/2:
        break

ans = abs(S-Sb*2)
Sb -= A[i]
ans = min(ans,abs(S-Sb*2))
print(ans)

Measured memory_bytes: 26056
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n;
    cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];
    sort(rall(a));

    queue<int> q;
    rep(i, n-1) {
        q.push(a[i]);
        q.push(a[i]);
    }
    q.pop();
    ll ans = 0;
    rep(i, n-1) {
        ans += q.front();
        q.pop();
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5628
import java.io.*;
import java.util.*;


class Main {
    public static void main(String[] args) {
        Scanner scr = new Scanner(System.in);
//        int t = scr.nextInt();
//        while (t-- > 0)
        solve(scr);
    }


//    static void solve(Scanner scr) {
//        int n = scr.nextInt();
//        int[] a = new int[n];
//        int[] b = new int[n + 1];
//
//        for (int i = 0; i < n; i++) {
//            a[i] = scr.nextInt();
//            b[a[i]]++;
//        }
//        int s = 0;
//        for (int i = 0; i < n; i++) {
//            s += b[i] * (b[i] - 1) / 2;
//        }
//
//        for (int i = 0; i < n; i++) {
//            int c = (b[a[i]] - 1) * (b[a[i]] - 2) / 2 > 0 ? (b[a[i]] - 1) * (b[a[i]] - 2) / 2 : 0;
//            int d = (b[a[i]]) * (b[a[i]] - 1) / 2;
//            System.out.println(s - d + c);
//        }
//
//
//    }


    static void solve(Scanner scr) {
        int L = scr.nextInt();
        double a = L / 3.0;
        double d = Math.pow(a, 3);
        System.out.printf("%f", d);

    }

}





Measured memory_bytes: 20052
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

int main(){
    int n;
    cin>>n;
    if(n>88 or n%10==9)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

vector<long long>adj[100002];
long long ara[100004],vis[100002],mod=1000000007,ans,k;

long long bigmod(long long n,long long p)
{
     if(p==0)return 1;
     if(p%2==0)
     {
         long long ret=bigmod(n,p/2);
         return ((ret%mod)*(ret%mod))%mod;
     }
     else
        return ((n%mod)*(bigmod(n,p-1)%mod))%mod;
}

void bfs(long long src)
{

    vis[src]=1; long long sz=adj[src].size(); long long lp,v,u,x,y,z,p,q;
    queue<long long>qu; qu.push(src);

    while(!qu.empty())
    {
        v=qu.front(); qu.pop();

        sz=adj[v].size();

        if(v==1){  x=sz; y=k-1;  }
        else{  x=sz-1; y=k-2;  }

        if(x>0)
        {
            if(y<x){  ans=0; break; }
            else
            {
                p=ara[y-x]; q=bigmod(p,mod-2); z=(ara[y]*q)%mod; ans=(ans*z)%mod;
                //cout<<v<<"     "<<x<<" "<<y<<"      "<<p<<" "<<q<<" "<<z<<endl;
            }
        }

        if(ans==0)break;

        for(lp=0;lp<sz;lp++)
        {
            u=adj[v][lp]; if(vis[u]==0){   qu.push(u); vis[u]=1;  }
        }
    }


}

int main()
{



    long long n,m,i,j,a,b;
    scanf("%lld %lld",&n,&k);

    for(i=1;i<=n-1;i++)
    {
        scanf("%lld %lld",&a,&b);  adj[a].push_back(b);  adj[b].push_back(a);
    }

    ara[0]=1; for(i=1;i<=100001;i++){  ara[i]=(ara[i-1]*i)%mod;   }

    ans=k; bfs(1);
    printf("%lld\n",ans);


    return 0;
}





Measured memory_bytes: 11912
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	long long res = 0;
	for(auto i = 1; i <= n; ++ i){
		if(i % 3 && i % 5){
			res += i;
		}
	}
	cout << res;
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 3608
// practice with kaiboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	static final int INF = 0x3f3f3f3f;
	int[] oo, oj; int __ = 1;
	int link(int o, int j) {
		oo[__] = o; oj[__] = j;
		return __++;
	}
	int[] ii, jj, ww;
	int[] af; boolean[] used;
	void init(int n, int m) {
		oo = new int[1 + m]; oj = new int[1 + m];
		ii = new int[m]; jj = new int[m]; ww = new int[m];
		af = new int[n]; used = new boolean[n];
	}
	void dfs(int i) {
		if (used[i])
			return;
		used[i] = true;
		for (int o = af[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			dfs(j);
		}
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int p = sc.nextInt();
		init(n, m);
		for (int h = 0; h < m; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			int w = sc.nextInt();
			ii[h] = i;
			jj[h] = j;
			ww[h] = w - p;
			af[j] = link(af[j], i);
		}
		dfs(n - 1);
		int[] dd = new int[n]; Arrays.fill(dd, -INF); dd[0] = 0;
		for (int k = 1; k <= n; k++)
			for (int h = 0; h < m; h++) {
				int i = ii[h], j = jj[h];
				if (dd[i] != -INF && used[j]) {
					int d = dd[i] + ww[h];
					if (d >= INF) {
						println(-1);
						return;
					}
					if (dd[j] < d) {
						dd[j] = d;
						if (k == n) {
							println(-1);
							return;
						}
					}
				}
			}
		println(Math.max(dd[n - 1], 0));
	}
}


Measured memory_bytes: 52568
import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc  = new Scanner(System.in);
      int n = sc.nextInt();
        Integer[] a = new Integer[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        Integer[] dp = new Integer[n];
        dp[0] = 0;
        for(int i=1;i<n;i++){
            dp[i] = Math.min((dp[Math.max(i-1,0)]+(Math.abs(a[i]-a[Math.max(i-1,0)]))),(dp[Math.max(i-2,0)]+(Math.abs(a[i]-a[Math.max(i-2,0)]))));
        }
        System.out.print(dp[n-1]);
    }
}

Measured memory_bytes: 60320
#include<cstdio>
#include<vector>
#include<algorithm>
#define MAXN 100006
using namespace std;
int fa[MAXN],re[MAXN],n,b,a,d,m;
int root(int x)
{
	if(fa[x]==x) return x;
	int lastfa=fa[x];
	int haha=root(fa[x]);
	re[x]=re[x]+re[lastfa];
	fa[x]=haha;
	return haha;
}
bool work()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&d);
		int roota=root(a);
		int rootb=root(b);
		if(roota==rootb)
		{
			if(re[a]!=re[b]+d) return 0;
		}
		else
		{
			fa[roota]=rootb;
			re[roota]=d+re[b]-re[a];
		}
	}
	return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(work()) printf("Yes");
	else printf("No");
}

Measured memory_bytes: 896
/*
cat <<EOF >mistaken-paste
*/

#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define BIG 2000000007
#define VERYBIG 200000000000007LL

#define MOD 1000000007
typedef uint64_t ull;
typedef  int64_t sll;

#define N_MAX 200000
#define M_MAX 200000

#ifdef __cplusplus
#include <queue>
#include <stack>
// #include <tuple>
#include <set>
#include <map>

// using namespace std; // HELL
using std::queue;
using std::priority_queue;
using std::stack;
// using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;

#endif

typedef struct {
	int32_t a;
	int32_t b;
} hw;

typedef struct {
	sll a;
	sll b;
} hwll;

typedef struct {
	hwll a;
	hwll b;
} linell;


typedef struct {
	ull s;
	ull t;
	int32_t c;
} struct_a;

typedef struct {
	int32_t from;
	int32_t to;
	sll cost;
} struct_b;



const hw vector8[8] = {
	{-1, -1},
	{-1,  0},
	{-1, +1},
	{ 0, -1},
	{ 0, +1},
	{+1, -1},
	{+1,  0},
	{+1, +1}
};

ull n, m;
ull h, w;
ull k;
ull q;
ull vua, vub, vuc, vud, vue, vuf;
sll vsa, vsb, vsc, vsd, vse, vsf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
size_t slen;
size_t tlen;
char ch, dh;

ull gcd (ull x, ull y) {
	if (x < y) {
		return gcd(y, x);
	} else if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}

sll a[N_MAX];

ull solve () {
	sll i, j, ki;
	// ull result = 0;
	sll result = 0;
	// double result = 0;
	ull maybe = 0;
	// sll maybe = 0;
	// ull sum = 0;
	sll sum = 0;
	ull item;
	ull *dpcell;

	ull evens = 0;

	bool takaflag = true;
	bool winflag;

	while (true) {
		evens = 0;

		ull ones = 0;
		ull finalodd = BIG;
		for (i = 0; i < n; i++) {
			if (a[i] == 1) ones++;
			if (a[i] % 2 == 0) {
				evens++;
			} else {
				finalodd = i;
			}
		}
		if (ones) {
			winflag = (evens % 2 == 1);
			break;
		}

		if (evens % 2 == 1) {
			winflag = true;
			break;
		}
		if (evens < n - 1) {
			winflag = false;
			break;
		}

		if (finalodd == BIG) {
			winflag = false;
			break;
		}
		a[finalodd]--;

		ull allgcd = a[0];
		for (i = 0; i < n; i++) {
			allgcd = gcd(allgcd, a[i]);
		}
		for (i = 0; i < n; i++) {
			a[i] /= allgcd;
		}

		takaflag = !takaflag;
	}

	if ((winflag ? 1 : 0) == (takaflag ? 1 : 0)) {
		goto success;
	} else {
		goto fail;
	}

	return 0;

	success:
	puts("First");
	return 0;

	fail:
	puts("Second");
	return 1;
}

int32_t main (void) {
	int32_t i, j;
	int32_t x, y;

	scanf("%llu", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%llu", &a[i]);
	}

	solve();

	return 0;
}


Measured memory_bytes: 896
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
int n, w[61][61];
long long Mod = 1000000007, res[61][61], K, D[61][61], TP[61][61];
int main(){
	int i, j, k;
	scanf("%d%lld", &n, &K);
	for (i = 1; i <= n; i++) {
		res[i][i] = 1;
		for (j = 1; j <= n; j++) {
			scanf("%lld", &D[i][j]);
		}
	}
	while (K) {
		if (K & 1) {
			for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)TP[i][j] = 0;
			for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)for (k = 1; k <= n; k++)TP[i][k] = (TP[i][k] + res[i][j] * D[j][k]) % Mod;
			for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)res[i][j] = TP[i][j];
		}
		for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)TP[i][j] = 0;
		for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)for (k = 1; k <= n; k++)TP[i][k] = (TP[i][k] + D[i][j] * D[j][k]) % Mod;
		for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)D[i][j] = TP[i][j];
		K >>= 1;
	}
	long long s = 0;
	for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)s = (s + res[i][j]) % Mod;
	printf("%lld\n", s);
}

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

using namespace std;

typedef long long ll;

#define endl '\n';

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);

    int x,ans=0;

    cin>>x;

    ans=x/500*1000;
    x=x%500;
    ans+=x/5*5;

    cout<<ans;


    return 0;
}







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

const int N = 1e5 + 1000;
bool vis[N+100];
int prim[N+100];
int main(){
	vis[1] = 1;
	int idx = 0;
	for(int i = 2;i <= sqrt(N);++i){
		for(int j = i*i;j <= N;j += i){
			vis[j] = 1;
		}
	}
	for(int i = 1;i <= N;++i){
		if(!vis[i]) prim[++idx] = i;
	}
	int n;
	cin>>n;
	int x = lower_bound(prim+1,prim+idx+1,n) - prim;
	cout<<prim[x];
}

Measured memory_bytes: 384
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node
{
    int c, a[20];
} p[20];
int ans[15], v[20];
ll ANS = 1e10, sum;
int n, m, u, x;
void dfs(int cnt, int pre)
{
    if (cnt == u)
    {
        sum = 0;
        fill(v, v + 20, 0);  //记录总的学习程度
        for (int j = 0; j < cnt; j++)
        {
            for (int k = 0; k < m; k++)
                v[k] += p[ans[j]].a[k];
            sum += p[ans[j]].c;
        }
        int flag = 1;
        for (int j = 0; j < m; j++)
            if (v[j] < x)
            {
                flag = 0;
                break;
            }
        if (flag)
            ANS = min(ANS, sum);
        return;
    }
    for (int j = 0; j <= n; j++)
    {
        if (j > pre)
        {
            pre = j;
            ans[cnt] = pre;
            dfs(cnt + 1, pre);
        }
    }
}

int main()
{
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].c;
        for (int j = 0; j < m; j++)
            cin >> p[i].a[j];
    }
    for (u = 1; u <= n; u++)
    {
        dfs(0, 0);
    }
    if (ANS == 1e10)
        puts("-1");
    else
        cout << ANS;
    return 0;
}


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

#define ll long long
#define ld long double
#define pb push_back
#define pr pair<ll, ll>
#define vct vector<ll>
#define vpt vector<pr>
#define st set<ll>
#define pq priority_queue<ll>
#define mat vector<vector<ll> >
#define all(x) x.begin(),x.end()
#define F(i, n) for(i = 0; i < (1LL*n); i++)
#define Fr(i, n) for(i = n - 1; i >= 0; i--)

struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umap unordered_map<long long, long long, custom_hash>

void prv(vct v){for (ll i=0;i<v.size();i++)cout<<v[i]<<" ";cout << "\n";}
void prn(ll n){cout<<n<<"\n";}
void prs(string n){cout<<n<<"\n";}
void deb(string s, ll n){cout<<s<<" : "<<n<<"\n";}
void prmt(mat m){for(ll i=0;i<(1LL*m.size());i++)prv(m[i]);}

mat getRzMat(mat mt, ll m,ll n, ll ini=0){mt.assign(m,vector<ll>(n,ini));return mt;}

ll poww(ll x, ll y, ll m){
    ll res = 1;
    while (y){
        if (y%2 == 0){x = (x * x) % m;y = y / 2;}
        else{res = (res * x) % m;y--;}
    }
    return res;
}

vct divsors(ll n){
    vct ans;//ans.push_back(1);
    for(ll i=1;i<=sqrt(n);i++){if(n%i==0){ans.push_back(i);if(i!=(n/i))ans.push_back(n/i);}}
    sort(ans.begin(),ans.end());
    return ans;
}
vct sieve(ll n){
    vct ans(n+1,-1);
    for(ll i=2;i<=n;i++){
        if(ans[i]==-1){
            for(ll j=i;j<=n;j+=i)if(ans[j]==-1)ans[j]=i;
        }
    }
    return ans;
}
mat mt;
ll n, k, m, l, r, x, y, z, ans=0;
ll t, t1, t2;
ll q;
ll i, j;
ll a, b, c, d, w;
ll mod = 1000000007;
ll cas=0;

void solve(){
    cin>>n;
    ll mx=-1;
    ans=0;
    F(i,n){
        cin>>t1;
        if(t1<mx)ans+=(mx-t1);
        mx=max(mx,t1);
    }
    prn(ans);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout);
    ll t = 1;
    // cin >> t;
    cas=1;
    while (t--){
        solve();
        cas++;
    }
    return 0;
}



Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())

N = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0
for i in range(0, N*2, 2) :
  ans += L[i]
  
print (ans)



Measured memory_bytes: 3572
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1010,oo=9999999;
int f[maxn],w[maxn],n;
vector <int> son[maxn];
int dp[2][5050];
void dfs(int v){
	for(int i=0;i<son[v].size();i++)
		dfs(son[v][i]);
	for(int i=0;i<=w[v];i++)
		dp[0][i]=dp[1][i]=oo;
	int x=1;dp[x][0]=0;
	for(int i=0;i<son[v].size();i++){
		x^=1;int y=x^1,u=son[v][i];
		for(int j=0;j<=w[v];j++)
			dp[x][j]=oo;
		for(int j=0;j<=w[v];j++){
			if(j>=w[u])dp[x][j]=min(dp[x][j],dp[y][j-w[u]]+f[u]);
			if(j>=f[u]){
				//if(v==5)cout<<x<<" "<<u<<" "<<j<<" "<<dp[x][j]<<" "<<dp[y][j-f[u]]+w[u]<<endl;
				dp[x][j]=min(dp[x][j],dp[y][j-f[u]]+w[u]);
			}
		}
	}
	f[v]=oo;
	//cout<<"print"<<v<<":";
	for(int i=0;i<=w[v];i++){
		//cout<<dp[x][i]<<" ";
		f[v]=min(f[v],dp[x][i]);
	}
	//cout<<endl;
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		son[x].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	dfs(1);
	//for(int i=1;i<=n;i++)
	//	cout<<f[i]<<" ";
	if(f[1]<oo)cout<<"POSSIBLE";
	else cout<<"IMPOSSIBLE";
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
#define gcd(x,y) __gcd(x,y)
#define fi first
#define se second
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline ll abs(A &a) { return (a < 0 ? -a : a); }
using namespace std;
const ll inf=(1LL<<62);
const ll MOD=(1e9)+7;
const ll mod=998244353;
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  ll a, b, c = 0;
  cin >> n;
  bool flag = true;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    if (a == b) {
      c++;
    }else {
      if (c < 3) {
        c = 0;
      }
    }
  }
  if (c >= 3) {
    cout << "Yes\n";
  }else {
    cout << "No\n";
  }
  return 0;
}
 

Measured memory_bytes: 3648
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
#a=input_list()
#a=input().split()
#n=int(a[0])
#m=float(a[1])
#print(math.floor(n*m))
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
div=make_divisors(n)
#print(div)
ind=0
ans=0
while(n!=1 and n>=div[ind]):
    ind+=1
    check=Counter(prime_factorize(div[ind]))
    if (len(check.keys()))>1:
        continue
    #print("pass")    
    if n%div[ind]==0:
        ans+=1
        n=n//div[ind]

print(ans)


Measured memory_bytes: 27212
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1100000;
bool nov[maxn+1];
vector<long long> prim;
int main()
{
	prim.clear();
	for(int i=1;i<=maxn;i++)
	nov[i]=true;
	
	for(int i=2;i<=maxn;i++)
	if(nov[i])
	{
		prim.push_back(i);
		for(long long j=(1LL*i)*i;j<maxn;j+=i)
			nov[j]=false;	
	}
	
	long long l;
	while(scanf("%lld",&l)!=EOF&&l)
	{
		long long tmp=l,ans=1;
		for(int i=0;prim[i]*prim[i]<=l;i++)
		{
			int num=0;
			while(tmp%prim[i]==0)
			{
				tmp/=prim[i];
				num++;
			}
			//if(num!=0)printf("%d\n",num);
			ans=ans*(2*num+1);
		}
		//printf("%lld\n",ans);
		if(tmp!=1)ans=ans*3;		
		ans=(ans-1)/2+1;
		printf("%lld\n",ans);
	}
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using llint = long long;
using vint = vector<int>;
using vvint = vector<vector <int>>;

int main () {
    int n, d; cin >> n >> d;
    vvint x(n, vint(d));
    rep(i, n) {
        rep(j, d) {
            cin >> x[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n ; i++) {
        for (int j = i + 1; j < n; j++) {
            int norm = 0;
            for (int k = 0; k < d; k++) {
                int diff = abs(x[i][k] - x[j][k]);
                norm += diff * diff;
            }
            bool flag = false;
            for (int k = 0; k <= norm; k++) {
                if (k * k == norm) flag = true;
            }
            if (flag) ans++;
        }

    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C;
    cin >> A >> B >> C;
    if(A == B && A != C)cout << "Yes" << endl;
    else if(A == C && A != B)cout << "Yes" << endl;
    else if(B == C && B != A)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256