akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9


int main(){
	int n;
	cin>>n;
	vector<ll> v(n),c(n);
	ll res = 0;
	for(int i=0;i<n;i++)cin>>v[i];
	for(int i=0;i<n;i++)cin>>c[i];
	for(int i=0;i<n;i++)if(v[i]-c[i]>0)res+=v[i]-c[i];
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def bs(ar,eq,n) en=(eq==1 ? :>= : :>); ar.bsearch_index{|x|x.send(en,n)} end
def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n,k=gsmi
a=gsmi

div=((n-1).to_f/(k-1)).ceil
puts div

Measured memory_bytes: 8716
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();
    set<string> A; 

    for(int i = 1; i <= k; i++) {
        for(int j = 0; j <= n-i; j++) {
            A.insert(s.substr(j, i));
        }
    }

    auto itr = A.begin();

    rep(i, k-1) {
        itr++;
    }

    cout << *itr;

    cout << endl;
    return 0;
}

Measured memory_bytes: 1664
import java.util.Scanner;

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

        String str;
        str = scanner.nextLine();
        char c = str.charAt(0);
        if (c >=65 && c <= 90) {
            System.out.println("A");
        } else {
            System.out.println("a");
        }
    }
}


Measured memory_bytes: 35704
import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class Main {
		
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = new int[N+1];
		int[] sum = new int[N+1];
		
		HashMap<Integer, Long> map = new HashMap<Integer, Long>();
		map.put(0, 1L);
		for(int i = 1; i <= N; i++){
			A[i] = sc.nextInt();
			sum[i] = (sum[i-1] + A[i]) % M;
			int m = sum[i];
			Long count = map.get(m);
			if(count == null) map.put(m, 1L);
			else map.put(m, count+1);
		}
		
		ArrayList<Entry<Integer, Long>> listEntries = new ArrayList<Entry<Integer, Long>>(map.entrySet());
		long ans = 0;
		for(Entry<Integer, Long> e : listEntries){
			long count = e.getValue();
			ans += count * (count - 1) / 2;
		}
		
		System.out.println(ans);
		
	}//end main
	
}//end Main

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}


Measured memory_bytes: 27496
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 #define int long long
#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define endl '\n'
#define fi first
#define se second
 
 
 
using namespace __gnu_pbds;
using namespace std;
 // const int mod=1e9+7;
 const int mod=998244353;
const int INF=4e18+10;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define read(n) int n; cin>>n;
#define readv(x, n) vector<int> x(n); for(auto &i:x) cin>>i; 
 
 
int power(int a, int b, int mod)
{
    int prod=1;
    int mult=a%mod;
    while(b!=0)
    {
        if(b%2)
        {
            prod*=mult;
            prod%=mod;
        }
        mult*=mult;
        mult%=mod;
        b/=2;
    }
    return prod;
}
int mod_inv(int q, int mod)
{
    return power(q, mod-2,mod);
}


signed main()
 
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
       cout.tie(NULL);
     #ifndef ONLINE_JUDGE
        if(fopen("INPUT.txt","r"))
        {
        freopen ("INPUT.txt" , "r" , stdin);
        freopen ("OUTPUT.txt" , "w" , stdout);
        }
     #endif
    auto clk=clock(); 
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // -------------------------------------Code starts here---------------------------------------------------------------------     

    const long double PI= acos(-1);
    int r;
    cin>>r;
    cout<<setprecision(10)<<fixed<<(2*PI*r)<<endl;
    // -------------------------------------Code ends here------------------------------------------------------------------
 
 
    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
    return 0;
 }


Measured memory_bytes: 3804
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>
#include <stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

int main() {
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    rep(i, 0, N) {
        cin >> X[i];
        Y[i] = X[i];
    }
    sort(Y.begin(), Y.end());
    int index = N / 2;
    int median = Y[index];

    rep(i, 0, N) {
        if (X[i] < median) {
            cout << median << endl;
        }
        else {
            cout << Y[index - 1] << endl;
        }
    }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    bool ok=true;
    int h,w;
    cin >> h >> w;
    vector<vector<int>> paint(h,vi(w,0));
    rp(i,h){
        rp(j,w){
            char ch;
            cin >> ch;
            if(ch=='#') {
                paint[i][j]=1;
            }
        }
    }
    rp(i,h){
        rp(j,w){
            if(paint[i][j]==1){
                bool next=false;
                if(i>0){
                    if(paint[i-1][j]==1) next=true;
                }
                if(i<h-1){
                    if(paint[i+1][j]==1) next=true;
                }
                if(j>0){
                    if(paint[i][j-1]==1) next=true;
                }
                if(j<w-1){
                    if(paint[i][j+1]==1) next=true;
                }
                if(!next) ok=false;
            }
        }
    }
    Yes(ok);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) { 
		Scanner sc = new Scanner(System.in);
		int n[]=new int[10];
		int a=0;int b=0;int c=0;
		for(int i=0;i<10;i++){
			n[i] = sc.nextInt();
			if(a<=n[i]){
				c=b;
				b=a;
				a=n[i];
			}else if(b<=n[i]){
				c=b;
				b=n[i];
			}else if(c<=n[i]){
				c=n[i];
			}
		}
		System.out.println(a);
		System.out.println(b);
		System.out.println(c);
	}
}

Measured memory_bytes: 17168
package main

import (
    "fmt"
    "os"
    "bufio"
    "strconv"
    // "sort"
)
var sc = bufio.NewScanner(os.Stdin)


func main() {
    sc.Split(bufio.ScanWords)
    // code goes here
    h, w := nextInt(), nextInt()
    i, j := nextInt(), nextInt()
    fmt.Println((h-i)*(w-j));
}



func nextInt() int {
    sc.Scan()
    v, e := strconv.Atoi(sc.Text())
    if e != nil { panic(e) }
    return v
}
func nextInt64() int64 {
    sc.Scan()
    v, e := strconv.ParseInt(sc.Text(), 10, 64)
    if e != nil { panic(e) }
    return v
}
func nextString() string {
    sc.Scan()
    return sc.Text()
}
func nextFloat() float64 {
    sc.Scan()
    v, e := strconv.ParseFloat(sc.Text(), 64)
    if e != nil { panic(e) }
    return v
}
func Max(x, y int) int { if x > y { return x }; return y }
func Min(x, y int) int { if x < y { return x }; return y }
func Abs(x int) int { if x > 0 { return x }; return -x }



Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
  int N;
  cin>>N;
  char S[N];
  int LW=0,LB=0,RW=0,RB=0;
  for(int i=0;i<N;i++){
    cin>>S[i];
    S[i]=='#' ? RB++:RW++;
  }
  
  vector<int> count;
  
  
  for(int i=0;i<N;i++){
    if(S[i]=='#'){
      count.push_back(LB+RW);
    }
    if(S[i]=='#'){
      RB--;
      LB++;
    }
    if(S[i]=='.'){
      RW--;
      LW++;
    }
    if(i==N-1){
      count.push_back(LB+RW);
    }
  }
  if(count.size()==0){
    cout<<0;
  }
  else{
    cout<<*min_element(count.begin(),count.end());
  }
}

Measured memory_bytes: 1656
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <bool> vb;
typedef vector <long long> vll;
typedef vector <vi> vvi;
typedef vector <vll> vvll;
 
#define all(v) v.begin(),v.end()
#define nl endl
#define bs(v,n) binary_search(v.begin(),v.end(),n)
#define sz() size()
#define pb push_back
 
ll mod=1000000007;

int main(){
  	int n, q;
  	string s;
  	vi rep(n,0);
  	cin>>n>>q>>s;
    for(int i=0; i<n-1; i++){
    	if(s[i]=='A' and s[i+1]=='C'){
        	rep[i+1]=1;
        }
    }
  	for(int i=0; i<n-1; i++){
    	rep[i+1]+=rep[i];
    }
  	for(int i=0; i<q; i++){
    	int l1, r1;
      	cin>>l1>>r1;
      	cout<<rep[r1-1]-rep[l1-1]<<nl;
    }
	return 0;
}

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

int main(){
  string n;
  cin >> n;
  for(int i = 0;i < 3 ;i++){
    if(n[i] == '1') cout << "9";
    else{
      cout << "1";
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 入力
term = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

i = int(input())
print(term[i-1])

Measured memory_bytes: 38384
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp>0:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k):
    a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2:
    a=lp.pop()
  p=[]
  while len(lp)>1:
    p+=[lp.pop()*lp.pop()]
  while len(lm)>1:
    p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2):
    a=a*p[i]%M
print(a)

Measured memory_bytes: 31756
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
ll inv(ll a, ll b){ return a<2 ? a : ((a-inv(b%a,a))*b+1)/a%b; }
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}

ll N,a[100010];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	
	int i;
	for (i=1; i<=N; i++)
		cin >> a[i];
		
	if (a[N]!=2){
		cout << -1 << "\n";
		return 0;
	}
	
	ll l=1,r=1;
	for (i=N-1; i>0; i--){
		ll nl=(a[i+1]*l+a[i]-1)/a[i];
		ll nr=((r+1)*a[i+1]-1)/a[i];
		
		if (nl>nr){
			cout << -1 << "\n";
			return 0;
		}
		
		l=nl,r=nr;
	}
	
	cout << l*a[1] << " " << (r+1)*a[1]-1;
	
	return 0;
}



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

using namespace std;

int main()
{
    int r, g, b, n, ans = 0, tmp;
    cin >> r >> g >> b >> n;

    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            tmp = n - (i*r + j*g);
            if(tmp >= 0 && tmp % b == 0) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    dsu U(N);
    for(int i = 0; i < Q; i++){
        int t, u, v;
        cin >> t >> u >> v;
        if(t == 0) U.merge(u, v);
        else{
            cout << (int)U.same(u, v) << endl;
        }
    }
}


Measured memory_bytes: 4028
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String temp = String.valueOf(n/100);
		int tem = Integer.parseInt(temp+temp+temp);
		if (n <= tem) {
			System.out.println(tem);
		} else {
			System.out.println(tem+111);
		}
	}
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define PB push_back
using namespace std;
typedef vector<int>V;
int main(void){
	int n;
	int a[4],b[4],ans[4];
	V v[4];
	int i,j,k;
	int sum;
	while(1){
		cin>>n;
		if(n==0)	break;
		for(k=0;k<n;k++){
			for(i=0;i<4;i++)	cin>>a[i];
			for(i=0;i<4;i++)	cin>>b[i];
			for(i=0;i<4;i++)	v[i].clear();
			for(i=0;i<4;i++){
				for(j=0;j<4;j++){
					if(i==0)			v[j].PB(a[i]*b[j]);
					if(i==1){
						if(j==0)		v[1].PB(a[i]*b[j]);
						if(j==1)		v[0].PB(a[i]*b[j]*-1);
						if(j==2)		v[3].PB(a[i]*b[j]);
						if(j==3)		v[2].PB(a[i]*b[j]*-1);
					}
					if(i==2){
						if(j==0)		v[2].PB(a[i]*b[j]);
						if(j==1)		v[3].PB(a[i]*b[j]*-1);
						if(j==2)		v[0].PB(a[i]*b[j]*-1);
						if(j==3)		v[1].PB(a[i]*b[j]);
					}
					if(i==3){
						if(j==0)		v[3].PB(a[i]*b[j]);
						if(j==1)		v[2].PB(a[i]*b[j]);
						if(j==2)		v[1].PB(a[i]*b[j]*-1);
						if(j==3)		v[0].PB(a[i]*b[j]*-1);
					}
				}
			}
			for(i=0;i<4;i++){
				ans[i]=0;
				for(j=0;j<(int)v[i].size();j++)		ans[i]+=v[i][j];
			}
			for(i=0;i<4;i++){
				if(i)	cout<<" ";
				cout<<ans[i];
			}
			cout<<endl;
		}
	}
	return 0;
}
					


Measured memory_bytes: 3152
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "cmath"
#include "random"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	cin >> N;
	cout << 48 - N << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
	int i,j,n,x,b;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]%2==1)
		{
			printf("first");
			return 0;
		}
	}
	printf("second");
	return 0;
}

Measured memory_bytes: 640
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    VII arr(n);
    for(auto &x:arr)cin>>x;
    bool win=true;
    for(int i=0;i<n && win;++i)
    {
        if(arr[i]%2==0 && (arr[i]%3!=0 && arr[i]%5!=0 ))
        win=false;
    }
    if(win)
    cout<<"APPROVED";
    else
    cout<<"DENIED";
    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;
using tTree=__gnu_pbds::tree< ll , __gnu_pbds::null_type, less< ll >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){

  ll a,b,c;
  cin>>a>>b>>c;

  cout << max(0LL,c-(a-b)) << endl;

  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
int f[3][105];
int a[3][105],n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
	f[1][1]=a[1][1];
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
		f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
	printf("%d",f[2][n]);
}

Measured memory_bytes: 256
// D - Banned K
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int N;
vl A;

vl solve(){
	map<int,int> m;//<ai,count>
	rp(i,0,N) m[A[i]]++;

	vl csum(N+1), del(N+1);
	for(auto x:m){
		ll a,c; tie(a,c) = x;
		if(c>=2) csum[a] = c*(c-1)/2;//組み合わせ
		c--;
		if(c>=2) del[a] = c*(c-1)/2;//１減の組み合わせ
	}

	rp(i, 1, N+1) csum[i] += csum[i-1];//Cumulative sum: 累積和

	vl ans(N+1, 0);
	rp(k, 1, N+1){
		int ak = A[k-1];
		ll m = del[ak];// k の組み合わせ
		ll f = csum[ak-1];// k より前の組み合わせの和
		ll b = csum[N] - csum[ak];// k より後の組み合わせの和
		ans[k] = f + m + b;
	}

	return ans;
}

int main(){
	cin>>N;
	A.resize(N);
	rp(i, 0, N) cin>>A[i];
	vl ans = solve();
	rp(i, 1, N+1) cout<< ans[i] <<endl;
}

Measured memory_bytes: 12416
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define E endl
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
const int N = 2e6+5;
const int INF = 1e18L;
#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...);
}
int ar[N];
vector<int>v;
int dp[102][4][2]; // dp[pos][k][flag];
int solve(int pos, int cnt , int f , int k ,int n){
	if(pos==n){
		return cnt == k;
	}
	if(cnt > k)return 0;
	if(dp[pos][cnt][f]!=-1)return dp[pos][cnt][f];
	int limit = (f==0 ? v[pos] : 9);
	int ans =0 ;
	for(int i =0 ;i<=limit;i++){
		int curCnt =cnt;
		if(i!=0)curCnt++;
		int nf = f;
		if(i < limit && f==0)nf =1;
		ans+=solve(pos+1,curCnt,nf,k,n);
	}
	return dp[pos][cnt][f]=ans;
}
signed main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS;
	int T=1;
	// cin >> T;
	while(T--){
		int k;
		string s;
		cin>>s>>k;
		memset(dp,-1,sizeof(dp));
		for(char x : s)v.pb(x-'0');
		int n = s.size();
		int ans = solve(0,0,0,k,n);
		cout << ans<<endl;
	
	}
	cerr << "Time Taken : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
long long gcd(long long a, long long b) {
    for(;;) {
        if(a == 0)
            return b;
        b %= a;
        if(b == 0)
            return a;
        a %= b;
    }
}
void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int N;
    cin>>N;
    vector<long long> A(N);
    REP(i,N){
        cin>>A[i];
    }
    long long result = A[0];
    REP(i,N){
        result = gcd(result,A[i]);
    }
    long long cnt = 0;
    while(result%2==0){
        result/=2;
        cnt ++;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#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 RFOR(i,b,a) for(int i = (b) - 1; i>= (a); i--)
                            #define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
                            #define FILL(a, value) memset(a, value, sizeof(a)

                            #define SZ(a) (int)a.size()
                            #define ALL(a) a.begin(), a.end()
                            #define PB push_back
                            #define MP make_pair
                            #define er erase
                            #define in insert
                            #define f first
//                            #define s second



                            typedef  long long LL;
                            typedef vector<int> VI;
                            typedef vector<LL > VL;
                            typedef vector<vector<int > > VVI;
                            typedef vector<vector<LL>> VVL;
                            typedef vector <vector<pair<int, int >> >VVPI;
                            typedef vector<vector<pair<LL, LL >> >VVPL;
                            typedef vector<pair<LL, LL >> PL;
                            typedef vector<PL> VPL;
                            typedef pair<int, int> PII;
                            typedef vector<PII> VPI;

                            const double PI = acos(-1.0);
                            const int INF = 1e9;
                            const LL LINF = (LL)1e18;

                            const double EPS = 1e-7;
                            const int MAS =  3 *1e5 + 10;
                            const int mod = 998244353;
                            const int MOD =1e9+7;
                            const int LOG= 19;
                            const int ar = 1e5 +100;
                            const int MAX = 1e6 + 1e2;
                         bool dp[ar];
                        int main() {
                            ios_base::sync_with_stdio(false);
                            cin.tie(NULL);
                            int n,k;
                            cin >> n >> k ;
                            VI a(n);
                            rep(i,n)cin >> a[i];
                            rep(i,k + 1)
                            {
                                for(auto x : a)
                                {
                                    if(i >=x && !dp[i - x])
                                    {
                                        dp[i] = true;
                                    }
                                }
                            }
                            cout << (dp[k]?"First":"Second");


                        }

















































Measured memory_bytes: 384
#pragma GCC optimize("Ofast",3,"inline")
#include <bits/stdc++.h>
using namespace std;
int n;
int a[150];
long long ans;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++) cin>>a[i];
	a[0]=0x7f7f7f7f;
	a[n]=0x7f7f7f7f;
	for(int i=0;i<n;i++) ans+=min(a[i],a[i+1]);
	cout<<ans;
	return 0;
}


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

using namespace std;

int ans(int n)
{
  if ( n < 10 ) {
    return n;
  }
  else if( n < 100 ) {
    return ans(9);
  }
  else if( n < 1000 ) {
    return n - 90;
  }
  else if( n < 10000 ) {
    return ans(999);
  }
  else if( n < 100000 ) {
    return n- 9090;
  }
  else if( n < 1000000 ) {
    return ans(99999);
  }
  
  return -1;
}

int main(void)
{
  int n;
  
  cin >> n;
  
  cout << ans(n) << endl;
  
  return 0;
}


Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define v vector
#define ALL(x) x.begin(),x.end()
#define rALL(x) x.rbegin(),x.rend()
#define endl '\n'
#define F first
#define S second
#define DEBUG

template<typename T> void DBG(const char* name, T&& H) {
	cerr << name << " = " << H << ')' << endl;
}

template<typename T, typename... Args> void DBG(const char* names, T&& H, Args&&... args) {
	const char* NEXT = strchr(names+1, ',');
	cerr.write(names, NEXT-names) << " = " << H << " |";
	DBG(NEXT+1, args...);
}

#ifdef DEBUG
	#define dbg(...) cerr << __FUNCTION__ << ' ' <<__LINE__ << " : (", DBG(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
#endif

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

const long long mod = 998244353;
const long double PI = acos(-1.0);
const long long INF = 1e18;
const int maxN = 2e5+1;

void Solve() {
	int N;
	cin >> N;
	vector<int> a(N);
	for(int i = 0; i < N; i ++) {
		cin >> a[i];
	}
	int ans = 2e9;
	for(int i = -100; i <= 100; i ++) {
		int val = 0;
		for(auto j : a) {
			val += ((j-i)*(j-i));
		}
		ans = min(ans, val);
	}
	cout << ans << endl;
}

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

	int tt = 1;
	while(tt --) {
		Solve();
	}
	
	return 0;
}

Measured memory_bytes: 3632
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    X = I()
    a = X // 500
    b = (X % 500) // 5

    print(a * 1000 + b * 5)


if __name__ == '__main__':
    main()


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

int func(int x){
    if (x<10) return x;
    return func(x/10)+x%10;
}
int main() {
    int N;
    cin >> N;
    if (N%func(N)==0) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

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

using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}

typedef pair<int,int> P;

bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int factorial(int a){
  int res = 1;
  while(a){
    res *= a;
    a--;
  }
  return res;
}

int main(){
  string S;
  cin >> S;
  bool flagA = false;
  bool flagB = false;
  rep(i,3){
    if(S[i] == 'A') flagA = true;//Aがある
    if(S[i] == 'B') flagB = true;//Bがある
  }
  if(flagA && flagB) cout << "Yes" << endl;
  else cout << "No" <<endl;
 }

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 200003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
	rint s=0;
	rgt char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
	return s;
}
int n;
LL K,a[N],b[N],sum[N],ans,l,r,mid;
inline bool check(rll k) {
	rint i;rll res=0;
	for(i=1;i<=n;i++)
		if(sum[i]>k)
			res+=(sum[i]-k+b[i]-1)/b[i];
	return res<=K;
}
int main() {
	rint i;
	scanf("%lld%lld",&n,&K);
	for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=n;i++) b[i]=read();
	sort(a+1,a+n+1),sort(b+1,b+n+1,greater<int>());
	for(i=1;i<=n;i++) sum[i]=a[i]*b[i];
	r=2e18;
	while(l<=r) {
		mid=(l+r)>>1;
//		printf("l=%lld r=%lld mid=%lld\n",l,r,mid);
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0 ;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		//String s = sc.next();
		//long n = sc.nextLong();
		//double n = sc.nextDouble();
		
		//for(int i = 0; i < ; i++)

		System.out.println((int)(n+Math.pow(n, 2)+Math.pow(n, 3)));
		//System.out.println("No");
		

	}
}


Measured memory_bytes: 35724
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,A,B,C,ans=1e7,l[10];
void dfs(int i,int a,int b,int c,int m){
    if(i==n)if(a==A||b==B||c==C)return;
    else{
        ans=min(ans,abs(a)+abs(b)+abs(c)+m);
        return;
	}
    dfs(i+1,a-l[i],b,c,m+(a==A?0:10));
    dfs(i+1,a,b-l[i],c,m+(b==B?0:10));
    dfs(i+1,a,b,c-l[i],m+(c==C?0:10));
    dfs(i+1,a,b,c,m);
}
int main(){
    cin>>n>>A>>B>>C;
    for(int i=0;i<n;i++)cin>>l[i];
    dfs(0,A,B,C,0);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3540
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int d[20];

int n,x[20][20],y[20][20],a[20];

int ch()
{
    int i,j;

    for(i=0;i<n;i++)
    {
        if(d[i] == 1)
        {
            for(j=0;j<a[i];j++)
                if(d[x[i][j]-1] != y[i][j])
                    return -1;
        }
    }

    int ans = 0;
    for(i=0;i<n;i++)
        ans += d[i];

    return ans;
}

int sub(int k)
{

    if(k < n)
    {
        d[k] = 1;
        int n1 = sub(k+1);

        d[k] = 0;
        int n0 = sub(k+1);
        
        if(n0 > n1)
            return n0;
        else
            return n1;
    }
    else 
    {
        return ch();
    }
}

int main()
{
    int i,j;

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        
        for(j=0;j<a[i];j++)
            scanf("%d %d",&x[i][j],&y[i][j]);
    }


    int ans = sub(0);
    

    if(ans < 0)
        ans = 0;

    printf("%d\n",ans);
    return 0;
}

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

int main(){
    string box, tes, tes2, rev1, rev2;
    bool flag;
    flag = false;
    cin >> box;
    for(int i = 0; i < box.size()/2; i++){
        tes.push_back(box.at(i));
    }
    for(int i = 0; i < box.size()/2; i++){
        tes2.push_back(box.at(i + (box.size()+1)/2));
    }

    rev1 = tes;
    rev2 = tes2;
    reverse(rev1.begin(), rev1.end());
    reverse(rev2.begin(), rev2.end());
    if(rev1 == tes && rev2 == tes2 && tes == tes2){
        flag = true;
    }

    if(flag){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N,M; cin >> N >> M;
    VI L(M), R(M); REP(i,M) cin >> L[i] >> R[i];
    pair<int,int> ans(1,N);
    REP(i,M){
        ans.first = max(ans.first, L[i]);
        ans.second = min(ans.second, R[i]);
    }
    cout << max(0, ans.second-ans.first+1) << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rt return 0
#define endln "\n"
#define all(v) v.begin(), v.end()
#define for1(i, a, b) for (long long int i = a; i < b; i++)
#define for2(i, a, b) for (long long int i = a; i > b; i--)
//  cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;typedef long long int i;
typedef long long int lli;
typedef pair<lli, lli> pll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.length(); i++)
    {
        int c = 0;
        if (s[i] == 'R')
        {
            // c += 1;
            while (s[i] == 'R' && i < s.length())
            {
                i++;
                c++;
            }

            i -= 1;
        }
        ans = max(ans, c);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define FOR(i,n,m) for(int i=n; i<(int)m; i++)
#define ROF(i,n,m) for(int i=n; i>(int)m; i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define ri(a) scanf("%d",&a)
#define rii(a,b) ri(a),ri(b)
#define riii(a,b,c) rii(a,b),ri(c)
#define lri(a) scanf("%lld",&a)
#define lrii(a,b) lri(a),lri(b)
#define ms(obj,val) memset(obj,val,sizeof(obj))
#define all(x) x.begin(),x.end()
#define debug true
#define dprintf debug && printf

const int INF = 0x3f3f3f3f;
const ll INFLL = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e3+5;

set <int> G[MAXN];
int color[MAXN];
int cnt[2];
int a[MAXN];
int dp[MAXN][MAXN];
int n, m, cmp;

bool dfs(int v, int col){
    if(color[v] != -1) return color[v] == col;
    color[v] = col;
    cnt[col]++;
    bool ret = 1;
    for(auto u : G[v]) ret = ret && dfs(u, col^1);
    return ret;
}

bool solve(){
    FOR(i,0,n) if(color[i] == -1){
        cnt[0] = cnt[1] = 0;
        if(!dfs(i, 0)) return false;
        a[cmp++] = abs(cnt[0] - cnt[1]);
    }
    return true;
}

int f(int i, int dif){
    if(dp[i][dif+n] != -1) return dp[i][dif+n];
    if(i == cmp) return abs(dif);
    dp[i][dif+n] = min(f(i+1, dif + a[i]), f(i+1, dif - a[i]));
    return dp[i][dif+n];
}

ll sum(ll x){
    return (x*(x-1))/2;
}

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

    ms(color, -1);
    ms(dp, -1);
    rii(n,m);
    FOR(i,0,n) FOR(j,0,n) if(i != j) G[i].insert(j);
    FOR(i,0,m){
        int u, v;
        rii(u, v); u--; v--;
        G[u].erase(v);
        G[v].erase(u);
    }

    if(!solve()) printf("-1\n");
    else{
        int dif = f(0,0);
        int x = (n-dif)/2;
        printf("%lld\n", sum(x) + sum(x + dif));
    }

    return 0;
}


Measured memory_bytes: 39040
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> triple;
 
#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define fuv(i,a)    for(ll i=0;i<a.size();i++)
#define fdv(i,a)    for(ll i=(ll)a.size()-1;i>=0;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a
#define pr2(a,b)    cout<<a<<" "<<b
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(all(a),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()		
#define ast(x,a,b)  assert(x>=a and x<=b)				
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define se          second
#define fi          first 
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline ll minize(ll& a,ll b){return a=(a>b?b:a);}
inline ll maxize(ll& a,ll b){return a=(a<b?b:a);}
inline string toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e6;
 
 
ll A[MAXN+5];
map<ll,pll> mymap;
ll Solves(){
	
	ll n,m,k,cnt=0,ans=0,y,q,c,sum=0,v,t;
	// PROCESS IN HERE
	sc(n);
	fu(i,1,n)sc(A[i]);
	if(A[1]!=0)re cout<<-1,0;
for(int i=2;i<=n;i++){if(A[i]>A[i-1]+1)re cout<<-1,0;}
	mymap[0]=mp(1,0);
	pll x;
	cnt=1;
	fu(i,2,n){
		mymap[-cnt]=mp(i,0);
		x=mymap[A[i]-cnt];
		if(!x.fi)re cout<<-1,0;
		ans+=i-x.fi-x.se;
		mymap[A[i]-cnt]=mp(x.fi,i-x.fi);
		cnt++;		
//		debug(x.fi); debug(x.se);
//		debug(ans);
	}
	cout<<ans;
 
	re 0;
	// Hack it if you can :)
}
 
int main(){
//	INPUT;
	ll JUDGE_ONLINE = 1;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	ll test;
//	sc(test);
//	fu(T,1,test)
	Solves();
	if (!JUDGE_ONLINE) cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";  
		
}

Measured memory_bytes: 14336
/*
@author: sharrad99
*/
#include<bits/stdc++.h>
using namespace std;
int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<vector<int>> h(n, vector<int>(3));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 3; j++) {
			cin >> h[i][j];
		}
	}

	int ba = 0, bb = 0, bc = 0;
	ba = h[0][0], bb = h[0][1], bc = h[0][2];

	for(int i = 1; i < n; i++) {
		int cba = max(bb, bc) + h[i][0];
		int cbb = max(ba, bc) + h[i][1];
		int cbc = max(ba, bb) + h[i][2];
		ba = cba, bb = cbb, bc = cbc;
	}

	cout << max(ba, max(bb, bc));
}

Measured memory_bytes: 5760
n, d = map(int, input().split())
XY = []
for i in range(n):
    XY.append(list(map(int, input().split())))

d2 = d**2
ans = 0
for xy in XY:
    distance2 = xy[0]**2 + xy[1]**2
    if distance2 <= d2:
        ans += 1

print(ans)

Measured memory_bytes: 45456
#include <cstdio>
#include <iostream>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)

int main(void) {
  int x, a;
  cin >> x >> a;
  cout << (x < a ? 0 : 10) << endl;
  return 0;
}


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

using namespace std;
int ans=0;
long long sum[50];
int main(){
	long long h;
	cin>>h;
	sum[0]=1;
	for(int i=1;i<=45;i++)sum[i]=sum[i-1]*2;
	long long k=1;
	int cnt=0;
	while(k<=h){
		k*=2;
		cnt++;
	}
	cout<<sum[cnt]-1<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[300000],f[2000001];
bool factors(long long n)
{
	if(f[n]>1)
		return false;

	for (long long i = 2; i <= sqrt(n); ++i)
	{

		if(n%i==0 && n!=i)
		{
			// printf("n is %lld i %lld\n",n,i );
			if(f[i]>0 || f[n/i]>0)
			{
				// printf("--> n is %lld i %lld\n",n,i );
				return false;
			}
		}
	}
	return true;
}
int main()
{
	long long n;
	cin>>n;
	for (long long i = 0; i < n; ++i)
	{
		cin>>a[i];
		f[a[i]]++;
	}
	if(f[1] == 1)
	{
		printf("1\n");
		return 0;
	}
	if(f[1] > 1)
	{
		printf("0\n");
		return 0;
	}
	// sort(a,a+n);
	long long ans = 0;
	for (long long i = 0; i < n; ++i)
	{
		if(factors(a[i]))
		{
			// cout<<a[i]<<endl;
			ans++;
		}
	}
	cout<<ans<<endl;

	
	return 0;
}

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

int main(){
	int n,a;
	set<int> s;
	vector<int> v;

	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a;
		s.insert(a);
		v.push_back(a);
	}
	
	int len = v.size() - s.size();
	if(len%2) cout << v.size()-len-1;
	else cout << v.size()-len;
}

Measured memory_bytes: 5368
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  [n,k] <- getl $ wrds toInt
  unless (n == 0 && k == 0) $ do
    solve <$> getl (wrds toInt) <*> replicateM n (getl $ wrds toInt) >>= putStrLn
    main

solve :: [Int] -> [[Int]] -> String
solve ss bs
  | and (zipWith (>=) ss (map sum . transpose $ bs)) = "Yes"
  | otherwise = "No"

toInt :: String -> Int
toInt = read

wrds :: (String -> a) -> String -> [a]
wrds f = map f . words

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 8208
n,m,x=map(int,input().split())
a=list(map(int,input().split()))

N=[]
for i in range(n+1):
    N.append(i*0)

for i in range(len(a)):
    N[a[i]]=1

print(min(sum(N[0:x+1]),sum(N[x+1:-1])))

Measured memory_bytes: 3064