akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = [int(input()) for _ in range(n)]
max_v = max(a)
a_copy = a[:]
a_copy.remove(max_v)
max_v2 = max(a_copy)
for i in a:
  if i != max_v:
    print(max_v)
  else:
    print(max_v2)

Measured memory_bytes: 14068
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],ans;
map<int,int> mp;
int main(){
	scanf("%d", &n);
	while( n-- ){
		int x;
		scanf("%d", &x);
		if( mp[x] == 0 ) ans++, mp[x] = 1;
		else mp[x] = 0, ans--;
	}
	printf("%d\n", ans);
	
} 

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n,m;cin>>n>>m;
	ll a[n];For(i,0,n) cin>>a[i];
	priority_queue<ll> p;
	ll ans = 0;
	For(i,0,n){
		p.push(a[i]);
		ans += a[i];
	}

	while(m>0){
		ll c = p.top();p.pop();
		if(c%2==0) ans -= c/2;
		else ans -= (c+1)/2;
		p.push(c/2);
		m--;
	}
	cout<<ans<<endl;































	
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    ll cnt[9][9];
    rep(i,9)rep(j,9) cnt[i][j]=0ll;

    FOR(i,1,n){
        if (i%10==0) continue;
        string s; s = to_string(i);
        cnt[s.front()-'1'][s.back()-'1']++;
    }
    ll ans=0;
    rep(i,9)rep(j,9){
        ans += cnt[i][j]*cnt[j][i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll; 
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int n, m; cin >> n >> m;
    int a[1000];
    int sum = 0;
    rep(i, 0, n) { cin >> a[i]; sum += a[i]; }
    int cnt = 0;
    rep(i, 0, n) {
        if (a[i] >= (sum+4*m-1) / (4 * m)) cnt++;
        //if (a[i] >= (sum + 3) / (4 * m)) cnt++;
    }
    if (cnt >= m) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int N, A[100005], ans;

int main() {
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", A+i);
    for(int i=1; i<=N+1; i++) ans += abs(A[i] - A[i-1]);
    for(int i=1; i<=N; i++) printf("%d\n", ans - abs(A[i] - A[i-1]) - abs(A[i+1] - A[i]) + abs(A[i+1] - A[i-1]));
}


Measured memory_bytes: 1664
<?php
fscanf(STDIN, '%d', $n);
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));
$ans = 'APPROVED';
for ($i = 0; $i < $n; $i++) {
    if ($a[$i] % 2 == 0 && $a[$i] % 3 != 0 && $a[$i] % 5 != 0) {
        $ans = 'DENIED';
        break;
    }
}
echo $ans . PHP_EOL;

Measured memory_bytes: 4856
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

/* --------------------------------------- */

vector<vector<ll>> g;
map<ll, ll> cnt;
constexpr ll p = 10007, M = 1000000007;
ll hassh(ll pos, ll par) {
	ll ret = 0;
	REP(i, g[pos].size()) {
		ll child = g[pos][i];
		if(child == par) continue;
		ret += hassh(child, pos) * p;
		ret %= M;
	}
	ret++; ret %= M;
	cnt[ret]++;
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	g.resize(n);
	REP(i, n - 1) {
		ll a, b;
		cin >> a >> b;
		a--; b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	hassh(0, -1);
	ll ans = 0;
	for(auto x: cnt) {
		ans += x.second * (x.second - 1) / 2;
	}
	cout << ans << endl;
 	return 0;
}

/* --------------------------------------- */




Measured memory_bytes: 22400
import java.util.HashMap;
import java.util.Scanner;


public class Main {
	
       public static void main(String[] args) {
    	  Scanner input=new Scanner( System.in);
    	  
    	  long ans=0;
    	  int n=input.nextInt();
    	  
    	  long m=input.nextLong();
    	  long []a=new long[100005];
  
    	  for(int i=1;i<=n;i++)
    	  {
    		  a[i]=input.nextLong();
    		  if(i>1)
    		  {
    			  if(a[i]+a[i-1]>m)
    			  {
    				  ans+=(a[i]+a[i-1]-m);
    				   if(a[i]>=(a[i]+a[i-1]-m))
    				   {
    					   a[i]-=(a[i]+a[i-1]-m);
    				   }
    				   else a[i]=0;
    			  }
    		  }
    	  }
    	 
    	  System.out.println(ans);
          
	}
}


Measured memory_bytes: 50892
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let n = it.next().unwrap().parse::<usize>().unwrap();
    let a = (0..n).map(|_| it.next().unwrap().parse::<usize>().unwrap()).collect::<Vec<_>>();
    let mut b = vec![0; n];
    for i in 0..n {
        b[a[i]-1] = i;
    }
    let mut res = 0;
    let mut cnt = 0;
    let mut pos = 0;
    for &t in &b {
        cnt = if t >= pos { cnt + 1} else { 1 };
        res = std::cmp::max(res, cnt);
        pos = t;
    }
    println!("{}", n - res);
}


Measured memory_bytes: 10492
#include<iostream>
#include<numeric>
using namespace std;
int main(){
    int h,w,a=0;
    cin>>h>>w;
    char s[h][w];
    int d[h][w]={};
    for(int i=0;i<h*w;i++)cin>>s[i/w][i%w];
    for(int i=0;i<h;i++){
        for(int j=0,k=0;j<w;k=0,j++){
            if(s[i][j]=='.'){
                while(j+k<w&&s[i][j+k]=='.')k++;
                for(int l=0;l<k;l++)d[i][j+l]=k;
            }
            j+=k;
        }
    }
    for(int i=0;i<w;i++){
        for(int j=0,k=0;j<h;k=0,j++){
            if(s[j][i]=='.'){
                while(j+k<h&&s[j+k][i]=='.')k++;
                for(int l=0;l<k;l++)d[j+l][i]+=k;
            }
            j+=k;
        }
    }
    for(int i=0;i<h*w;i++)a=max(a,d[i/w][i%w]);
    cout<<a-1<<endl;
    return 0;
}


Measured memory_bytes: 19840
#include <iostream>

using namespace std;

char toMark(int x){
  switch(x){
    case 0:
    return 'S';
    case 1:
    return 'H';
    case 2:
    return 'C';
    case 3:
    default:
    return 'D';
  }
}

int toNum(char x){
  if(x == 'S') return 0;
  if(x == 'H') return 1;
  if(x == 'C') return 2;
  if(x == 'D') return 3;
}

int main() {
  int n;
  int number;
  char mark;
  bool cards[4][13] = {false};
  cin >> n;
  for(int i=0; i < n; ++i){
    cin >> mark >> number;
    cards[toNum(mark)][number-1] = true;
  }
  for(int i=0; i < 4; ++i){
    for(int j=0; j < 13; ++j){
      if(cards[i][j] == false) cout << toMark(i) << " " << j+1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3104
N,K=map(int,input().split())
h = input().split()
H=[int(i) for i in h]

if __name__=='__main__':
    if (K>=N):
        print(0)
    elif K==0:
        print(sum(H))
    else:
        H=sorted(H,reverse=True)
        print(sum(H[K:N]))

Measured memory_bytes: 27556
from sys import exit
from collections import deque
N = int(input())
D = deque(map(int, input().split()))
if N == 0:
  d = D.pop()
  if d == 1:
    print(1)
  else:
    print(-1)
  exit()
R = [[] for i in range(N + 1)]
leaf = D.pop()
R[-1].append(leaf)
R[-1].append(leaf)
for i in range(N - 1, -1, -1):
  leaf = D.pop()
  R[i].append(R[i + 1][0]//2 + R[i + 1][0] % 2 + leaf)
  R[i].append(R[i + 1][1] + leaf)
  R[i].append(leaf)
if not(R[0][0] <= 1 <= R[0][1]):
  print(-1)
  exit()
node = 1
ans = 1
for i in range(1, N + 1):
  node = min(R[i][1], 2 * (node - R[i-1][2]))
  ans += node
print(ans)

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


int main() {
    int N;
    ll ans = 0;
    cin >> N;
    unordered_map<string, int> m(N);
    string s;
    for(int i=0;i<N;i++) {
        cin >> s;
        sort(s.begin(), s.end());
        ans += m[s];
        m[s]++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 10496
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;
bool overflow(ll a,ll b){
    if (a <= (inf+b-1)/b) return false;
    return true;
}
int main(){
FASTIO;
int n;
cin>>n;
string s,t;
cin>>s>>t;
for(int i=0;i<n;i++)
    cout<<s[i]<<t[i];
cout<<endl;
}


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

using namespace std;
vector<long long> factors;
#define ll long long

#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000'000'007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

template<class T>
istream &operator>>(istream &ist, vector<T> &vec)
{
	for (auto i = vec.begin(); i != vec.end(); ++i)
	{ ist >> vec[i]; }
	return ist;
}

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }

//****************************don't use int!!!!!!!****************************//
//***************************code starts here!!!!!****************************//

bool check(char ch)
{
	if (ch == 'A' || ch == 'C' || ch == 'G' || ch == 'T')
	{
		return true;
	}
	return false;
}

int main()
{
	IOS

	int n;
	int q;
	cin >> n;
	cin >> q;
	string st;
	cin >> st;
	vector<ll> pref(n + 1);
	pref[0] = 0;
	pref[1] = 0;
	for (int i = 2; i <= n; ++i)
	{
		pref[i] = pref[i - 1] + (st[i - 2] == 'A' && st[i - 1] == 'C');
	}

	for(int i = 0;i < q; ++i){
		int l,r;
		cin >> l >> r;
		cout << pref[r] - pref[l];
		cout << '\n';
	}


	return 0;
}

Measured memory_bytes: 1872
import scala.io.StdIn._
import scala.annotation.tailrec

object Main {
    def main(args: Array[String]): Unit = { 
        digit(readLine().split(" ").map(_.toDouble))
    }   

    @tailrec
    def digit(n: Seq[Double]): Unit = {
       val d: Double = n(1) * n(3) - n(0) * n(4)
       val x: Double = zero((n(1) * n(5) - n(4) * n(2)) / d)
       val y: Double = zero((n(2) * n(3) - n(0) * n(5)) / d)
       println(f"$x%.3f $y%.3f")
       val next: String = readLine()
       if(next == null) Unit else digit(next.split(" ").map(_.toDouble))
    }

    def zero(n: Double): Double = if(n == -0) 0 else n
}

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

int main() {
    int h,w;
    cin>>h>>w;
    vector<vector<char>> s(h,vector<char>(w));
    rep(i,h) {
        rep(j,w) cin>>s[i][j];
    }
    vector<vector<char>> ans(h+2,vector<char>(w+2));
    rep(i,h+2) {
        rep(j,w+2) {
            if (i==0||i==h+1||j==0||j==w+1) {
                ans[i][j]='#';
            } else {
                ans[i][j]=s[i-1][j-1];
            }
        }
    }
    rep(i,h+2) {
        rep(j,w+2) {
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}


Measured memory_bytes: 256
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 702;
const int INF = 1e9;

int n, m, cnt[2], side[MAX_N], f[MAX_N][MAX_N];
bool a[MAX_N][MAX_N];
vector<pair<int, int> > p;
set<pair<int, int> > visited[MAX_N];

void enter() {
	cin >> n >> m;
	for (int i=1; i<=m; ++i) {
		int u, v; cin >> u >> v;
		a[u][v] = a[v][u] = 1;
	}
}

bool visit(int u, int x) {
	++cnt[x];
	side[u] = x;
	for (int v=1; v<=n; ++v) {
		if (u!=v && a[u][v]==0) {
			if (side[v]!=-1 && side[v]!=x^1)
				return false;
			if (side[v]==-1) {
				if (!visit(v, x^1))
					return false;
			}
		}
	}
	return true;
}

void dfs(int pos, int x, int y) {
	if (visited[pos].count(make_pair(x, y)))
		return;
	visited[pos].insert(make_pair(x, y));
	if (pos==p.size())
		return;
	dfs(pos+1, x+p[pos].first, y+p[pos].second);
	dfs(pos+1, x+p[pos].second, y+p[pos].first);
}

int solve() {
	int res = INF;
	dfs(0, 0, 0);
	for (int x=0; x<=n; ++x) {
		for (int y=0; y<=n; ++y) {
			if (visited[p.size()].count(make_pair(x, y))) {
				res = min(res, x*(x-1)/2 + y*(y-1)/2);
			}
		}
	}
	return res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	memset(side, -1, sizeof(side));
	//debug(visit(1, 0))
	for (int i=1; i<=n; ++i) {
		if (side[i]==-1) {
			cnt[0] = cnt[1] = 0;
			if (!visit(i, 0)) {
				cout << -1;
				return 0;
			}
			p.push_back(make_pair(cnt[0], cnt[1]));
		}
	}
	//PR(side, n);
	cout << solve();
}

Measured memory_bytes: 12288
#include<bits/stdc++.h>
#define reg(i,a,b) for(int i=a;i<=b;i++)
#define reh(i,a,b) for(int i=b;i>=a;i--)
#define in(x) scanf("%d",&x)
#define fro freopen("D:\\testdata.in", "r", stdin)
#define il inline
#define lson(q) q<<1
#define rson(q) q<<1|1
using namespace std;
typedef long long ll;
const int mx=1e5+10;
int main() {
	int a,b;
	cin>>a>>b;
	reg(i,b-a+1,b+a-1){
		printf("%d%c",i,i==(b+a-1)?'\n':' ');
	}
	return 0;
}




Measured memory_bytes: 256
n = input()
nl = int(n[-1:])

if nl == 2 or nl == 4 or nl == 5 or nl == 7 or nl == 9:
  print('hon')
elif nl == 0 or nl == 1 or nl == 6 or nl == 8:
  print('pon')
else:
  print('bon')

Measured memory_bytes: 9172
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using pii = pair<Int,Int>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

Int LCM(Int a, Int b){
    return a*b/GCD(a,b);
}


int main() {
    Int P, Q, R;
    cin >> P >> Q >> R;
    Int ans = 0;

    ans = min(P+Q,Q+R);
    ans = min(ans,R+P);


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

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
import java.util.List;

public class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();
		for (int i = 0; i < S.length(); i++)
		{
			if ('a' <= (int)S.charAt(i) && (int)S.charAt(i) <= 'z')
			{
				System.out.print((char)((int)S.charAt(i) - 'a' + 'A'));
			}
			else if ('A' <= (int)S.charAt(i) && (int)S.charAt(i) <= 'Z')
			{
				System.out.print((char)((int)S.charAt(i) - 'A' + 'a'));
			}
			else
			{
				System.out.print(S.charAt(i));
			}
		}
		System.out.println();
		sc.close();
	}
}


Measured memory_bytes: 26576
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define endl "\n"

#define ll long long
bool Q;
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const {
		return Q ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
		return l.k * x + l.m;
	}
};
#undef ll

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    LineContainer lc;
    int c;
    cin >> c;
    int h, mincost;
    cin >> h;
    lc.add(2*h, -1*h*h);
    for(int i = 0; i < n-2; i++)
    {
        cin >> h;
        mincost = -1*lc.query(h) + h*h + c;
        lc.add(2*h, -1*h*h - mincost);
    }
    cin >> h;
    mincost = -1*lc.query(h) + h*h + c;
    cout << mincost;
}

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

N, M = MAP()
AB = [LIST() for _ in range(N-1+M)]
graph = [[] for _ in range(N)]
d_in = [0]*N
for a, b in AB:
	a, b = a-1, b-1
	graph[a].append(b)
	d_in[b] += 1

for i in range(N):
	if d_in[i] == 0:
		root = i
		break

ans = [None]*N
ans[root] = 0
q = deque([root])
while q:
	n = q.popleft()
	for node in graph[n]:
		d_in[node] -= 1
		if d_in[node] == 0:
			ans[node] = n+1
			q.append(node)

print(*ans, sep="\n")


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

using namespace std;
using ll=long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, a, n) for(int i = (a); i < (n); i++)

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  long long N;
  cin >> N;
  // (a, b) = (1, N)
  long long res = N + 1 - 2;
  for (long long a = 1; a * a <= N; ++a) {
    if (N % a == 0) res = min(res, a + N/a - 2);
  }
  cout << res << endl;
}


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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0) 

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }
    
    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
	int n = ri();
	int a[n]; INPUT(a);
	map<s64,int> ma;
	ma[0] = 1;
	s64 sum = 0;
	FOR(i,n) {
		sum += a[i];
		ma[sum]++;
	}
	s64 res = 0;
	for (auto &i : ma) {
		if (i.se >= 2) {
			res += (i.se-1)*((s64)i.se)/2;
		}
	}
	cout << res << endl;
    return 0;
}


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


int main()
{
  int n;
  std::cin >> n;
  n %= 1000;
  if (n == 0)
  {
    std::cout << 0 << std::endl;
  }
  else
  {
    std::cout << 1000 - n << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn];

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        scanf("%d",a + i);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        if(a[i] == i){
            ans++;
            if(i + 1 <= n && a[i + 1] == i + 1){
                swap(a[i],a[i + 1]);
            }else{
                if(i > 1){
                    swap(a[i],a[i - 1]);
                    continue;
                }
                if(i < n){
                    swap(a[i],a[i + 1]);
                    continue;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
bitset<maxn> pr; 
int n;
void sieve(){
	pr.set();
	pr[0] = pr[1] = 0;
	for(int i = 2; i*i <= n; ++i){
		if(pr[i])
			for(int j = i*i; j <= n; j+=i) 
				pr[j] = 0;
	}
}
int main() {
	n = maxn - 5;
	sieve();
	cin >> n;
	for(int i = 2, cn = 0; cn < n; i++){
		if(pr[i] and i%5 == 1){
			cout << i << ' ';
			cn++;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime> 
#include <memory.h>
#include <assert.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;

int main(){
    int N;
    cin >> N;
    map<int, vector<int>> m;
    set<int> s;
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        m[b].push_back(a);
        s.insert(b);
    }

    ll sum = 0;
    string ans = "Yes";
    for(auto b : s) {
        for(auto a : m[b]) {
            sum += a;
        }
        if(sum > b) ans = "No";
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 31488
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define fr(i,n) for(int i=0;i<(n);i++)
#define Fr(i,n) for(int i=0;i++<(n);)
#define ifr(i,n) for(int i=(n)-1;i>=0;i--)
#define iFr(i,n) for(int i=(n);i>0;i--)

int main() {
    int n,a,m=1e6,M=-1e6,mi,Mi;
    cin>>n;
    Fr(i,n){
        cin>>a;
        m=min(m,a);
        if(a==m) mi=i;
        M=max(M,a);
        if(a==M) Mi=i;
    }
    if(m>=0){
        cout<<n-1<<endl;
        Fr(i,n-1) cout<<i<<" "<<i+1<<endl;
        return 0;
    }
    if(M<=0){
        cout<<n-1<<endl;
        iFr(i,n-1) cout<<i+1<<" "<<i<<endl;
        return 0;
    }
    if(M+m>0){
        cout<<2*n-2<<endl;
        Fr(i,n) if(i!=Mi) cout<<Mi<<" "<<i<<endl;
        Fr(i,n-1) cout<<i<<" "<<i+1<<endl;
    }
    else{
        cout<<2*n-2<<endl;
        Fr(i,n) if(i!=mi) cout<<mi<<" "<<i<<endl;
        iFr(i,n-1) cout<<i+1<<" "<<i<<endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int i,j,H,W;
    scanf("%d %d",&H,&W);
    while(H!=0||W!=0){
    for(i=1;i<=H;i++){
        for(j=1;j<=W;j++){
            if(i==1||i==H||j==1||j==W){
                printf("#");
            }else{
                printf(".");
            }
        }printf("\n");
    }scanf("%d %d",&H,&W);
    printf("\n");
    }return 0;
}


Measured memory_bytes: 2104
//greedy is not applicable here as even if select min "diff" at each step then
//also final ans will not be optimal min possible of all answers
//eg: 30 20 50 10 50 70
//greedy: 60
//bruteforce (mainly dp): 40
import java.io.*;
import java.util.*;
public class Main{
  	/*public int minRec(int a[],int dp[],int i,int j)
    {
      if(i==n && j==n)
        	return dp[n][n];
      if(
        return Math.min( Math.abs(a[]
    }*/
	public static void main(String args[]) throws IOException{
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      int n=Integer.parseInt(br.readLine().trim());
      String s[]=br.readLine().trim().split("\\s+");
      int size=s.length;
      int arr[]=new int[size];
      for(int i=0;i<size;i++)
        arr[i]=Integer.parseInt(s[i]);
      int ans=0;
      //int dp[][]=new int[][];
      //ans=minRec(a,dp,0,0);
      long dp[]=new long[size];
      dp[n-1]=0;
      dp[n-2]=(long)Math.abs((long)arr[n-1]-(long)arr[n-2]);
      for(int i=n-3;i>=0;i--)
        dp[i]=(long)Math.min( dp[i+1]+Math.abs((long)arr[i]-(long)arr[i+1]), dp[i+2]+Math.abs((long)arr[i]-(long)arr[i+2]) );
      	//imp to add dp[i+1] when this index element is selected same for dp[i+2] 
      System.out.println(dp[0]);
    }
}

Measured memory_bytes: 39072
defmodule Main do
  def main do
    IO.gets("")
    list = IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    list |> multiplication() |> IO.puts()
  end

  @doc """
  Multiplication

  ## Examples

      iex> Multiplication2.multiplication([1000000000, 1000000000])
      1000000000000000000
      iex> Multiplication2.multiplication([101, 9901, 999999000001])
      -1
      iex> Multiplication2.multiplication([4, 1, 5, 0])
      0

  """

  def multiplication(list) do
    if 0 in list do
      0
    else
      list
      |> Enum.reduce_while(1, fn n, acc ->
        result = value(acc * n)
        if result > 0, do: {:cont, result}, else: {:halt, result}
      end)
    end
  end

  defp value(n) when n > 1_000_000_000_000_000_000, do: -1
  defp value(n), do: n
end

Measured memory_bytes: 57092
#include <cstdlib>
#include <iostream>

using namespace std;

//マクロ
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define INF 999999999

/*
 * 
 */


//ABC085
int main() {
    int N, Y;
    cin >> N >> Y;
    bool flag = 0;
    REP(x,N+1){
        if(flag == 1){
            break;
        }
        REP(y,N+1-x){
            int z = N - x - y;
            if(10000*x + 5000*y + 1000*z == Y){
                cout << x << " " << y << " " << z << endl;
                flag = 1;
                break;
            }
        }
    }
    if (!flag){
        cout << "-1 -1 -1" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while(true){
			int n = sc.nextInt();
			int x = sc.nextInt();
			if(x == 0 && n == 0){
				break;
			}
			int ans = 0;

			for(int i=1;i<=n;i++){
				for(int j=i+1;j<=n;j++){
					for(int s=j+1;s<=n;s++){
					if(i + j + s == x){
						ans++;
					 }					
					}
				}
			}
			System.out.println(ans);
		}
	}
  }


Measured memory_bytes: 26356
#include <bits/stdc++.h>
#define forn(i,a,b) for(int i=a; i<=b; i++)
#define MOD 1000000007
using namespace std;
int main(){
	int n,k,h[200000];
	cin>>n>>k;
	forn(i,1,n) cin>>h[i];
	int cost[200000]={0};
	forn(i,2,n){
		cost[i]=INT_MAX;
		forn(j,1,k){
			if(i>j) cost[i]=min(cost[i],cost[i-j]+abs(h[i]-h[i-j]));
		}		
	}
	cout<<cost[n]<<"\n";
}

Measured memory_bytes: 1408
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<math.h>
#include<unordered_map>
#include<map>

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using lst = list<ll>;


ll MOD = 1000000007;


int main()
{
	string S;
	cin >> S;
	vec ans(S.length());

	pair<int, int> p;

	for (int i=0;i<S.length();++i)
	{
		if (S[i] == 'R')
		{
			p.first += 1;
			swap(p.first, p.second);
		}
		if (S[i] == 'L')
		{
			ans[i] += p.first;
			ans[i - 1] += p.second;
			p.first = p.second = 0;
		}
	}

	for (int i = S.length()-1; i>=0; --i)
	{
		if (S[i] == 'L')
		{
			p.first += 1;
			swap(p.first, p.second);
		}
		if (S[i] == 'R')
		{
			ans[i] += p.first;
			ans[i + 1] += p.second;
			p.first = p.second = 0;
		}
	}

	for (int i = 0; i < S.length(); ++i)
	{
		cout << ans[i] << " ";
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int INF = 1000000007;

int cnt=0;
vector<int> A(600000);

void merge(int left,int mid,int right){
    int n1 = mid - left;
    int n2 = right - mid;
    vector<int> L(n1+1),R(n2+1);

    for(int i=0;i<n1;i++) L[i] = A[left+i];
    for(int i=0;i<n2;i++) R[i] = A[mid+i];
    L[n1] = INF;
    R[n2] = INF;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        if(L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }
        else{
            A[k] = R[j];
            j++;
        }
        cnt++;
    }
}

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

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> A[i];

    mergesort(0,n);
    cout << A[0];
    for(int i=1;i<n;i++) cout << ' ' << A[i];
    cout << endl;
    cout << cnt << endl;
}


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

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;

    if ((abs(c-a) <= d) || ((abs(b-a)<=d && abs(c-b)<=d))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cmath>

#define REP(i,n) for(int (i) = 0;(i) < (n);(i)++)
using namespace std;

class node{
public:
	int id;
	int parent,child1,child2,sibling;
	int degree,depth,height;
	node():id(-1),parent(-1),child1(-1),child2(-1),sibling(-1),degree(0),depth(0),height(0){};
	
	friend ostream& operator<<(ostream& os,const node& N){
		cout << "node " 		<< N.id ;
		cout << ": parent = "	<< N.parent;
		cout << ", sibling = " 	<< N.sibling;
		cout << ", degree = " 	<< N.degree;
		cout << ", depth = " 	<< N.depth;
		cout << ", height = "	<< N.height;
		cout << ", ";
		if(N.parent==-1) cout << "root";
		else if(N.child1==-1 && N.child2==-1) cout << "leaf";
		else cout << "internal node";
		cout << endl;
	}
};

void Pre(int n,vector<node> N){
	int c1=N[n].child1,c2=N[n].child2;
	cout << " " << n;
	if(c1 != -1) Pre(c1,N);
	if(c2 != -1) Pre(c2,N);
}

void Ino(int n,vector<node> N){
	int c1=N[n].child1,c2=N[n].child2;
	if(c1 != -1) Ino(c1,N);
	cout << " " << n;
	if(c2 != -1) Ino(c2,N);
}

void Pos(int n,vector<node> N){
	int c1=N[n].child1,c2=N[n].child2;
	if(c1 != -1) Pos(c1,N);
	if(c2 != -1) Pos(c2,N);
	cout << " " << n;
}

int main(){
	int n,m;
	cin >> n;
	vector<node> N(n);
	REP(i,n){
		N[i].id=i;
	}
	REP(i,n){
		int id,c1,c2;
		cin >> id >> c1 >> c2;
		N[id].child1 = c1;
		N[id].child2 = c2;
		N[id].degree = ((c1!=-1)?1:0)+((c2!=-1)?1:0);
		if(c1 != -1) N[c1].sibling = c2,N[c1].parent = id;
		if(c2 != -1) N[c2].sibling = c1,N[c2].parent = id;
	}
	int i;
	while(N[i].parent!=-1)i++;
	cout << "Preorder" << endl;Pre(i,N);
	cout << endl << "Inorder" << endl;Ino(i,N);
	cout << endl << "Postorder" << endl;Pos(i,N);
	cout << endl;
	return 0;
}

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

int main()
{   
	int k,s,ans=0;
	cin>>k>>s;
	for(int x=0;x<=k;x++)
	{
		for(int y=0;y<=k;y++)
		{
			int z=s-x-y;
			if(z>=0 && z<=k)
			{
				ans++;
			}
		}
	}
	cout<<ans;
return 0;
}

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

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
int main()
{
    int n; cin >> n;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0; i < n; i++)cin >> b[i];
    ll res = a.back() == b.front();

    for(int i = 1; i < n - 1; i++) {
        pair<int,int> as, bs;
        if(a[i - 1] != a[i])as = {a[i], a[i] + 1};
        else as = {1, a[i] + 1};
        if(b[i + 1] != b[i])bs = {b[i], b[i] + 1};
        else bs = {1, b[i] + 1};
        res *= max(0, min(as.second, bs.second) - max(as.first, bs.first));
        res %= mod;
    }
    cout << res << endl;

}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    cout << ((abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)) ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<memory.h>
#include<ctime>
#include<cstdio>

using namespace std;

int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	cout<<(a-c)/(b+c)<<endl; 
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N;
  cin>>N;
  int ans=0;
  FOR(A,1,N){
    ans+=N/A;
    if(N%A==0)ans--;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int n;
char ss[200005],so[200005];
int tot;
int cc[200005];
int main() {
	scanf("%s",&ss[1]);
	n = strlen(ss+1);
	long long ans = 0;
	for(int i=1;i<=n;i++) cc[i] = (ss[i]=='A');
	for(int i=1;i+2<=n;i++) {
		if(ss[i]=='A'&&ss[i-1]=='A') cc[i] += cc[i-1];
		if(ss[i]=='A'&&ss[i+1]=='B'&&ss[i+2]=='C') {
			ans += cc[i];
			ss[i+2]='A'; ss[i] = 'B'; ss[i+1] = 'C';
			cc[i+2] = cc[i]; cc[i] = 0;
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
const ll N = 200030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;

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





int n,m;
cin>>n>>m;
if(n>m)
swap(n,m);
for(int i=0;i<m;i++)
cout<<n;

}

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

using namespace std;
int n,i,a,b,c,nr,ok,v[100005];
long long sum;
int main()
{
    cin>>n;
   for (i=1;i<=n;i++)
   {
       cin>>v[i];
   }
   v[1]--;
   ok=1;
   for (i=2;i<=n;i++)
   {
       if (v[i]<v[i-1])
       {
           ok=0;
           break;
       }
       else
       if (v[i]>v[i-1])
       {
           v[i]--;
       }
   }
   if (ok==1)
   {
       cout<<"Yes";
   }
   else
   {
       cout<<"No";
   }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    int res = 0;
    rep(i, 1000){
        char one = '0' + (i/100);
        char two = '0' + (i%100/10);
        char three = '0' + (i%10);

        bool flg1 = false;
        bool flg2 = false;
        bool flg3 = false;

        int ptr = 0;
        for(int j = ptr; j < n-2; ++j){
            if(s[j] == one){
                flg1 = true;
                ptr = j+1;
                break;
            }
        }

        for(int j = ptr; j < n-1; ++j){
            if(s[j] == two){
                flg2 = true;
                ptr = j+1;
                break;
            }
        }

        for(int j = ptr; j < n; ++j){
            if(s[j] == three) {
                flg3 = true;
                break;
            }
        }

        if(flg1 && flg2 && flg3) ++res;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;



int main(){
  set<string> s;
  int n;
  cin >> n;
  string x;
  for(int i=0; i<n; i++){
    cin >> x;
    s.insert(x);
  }
  cout << s.size() << endl;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

class mint {
public:
    long long x;

    constexpr mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}

    constexpr mint operator-() const {
        return mint(-x);
    }

    constexpr mint &operator+=(const mint &rhs) {
        if ((x += rhs.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator-=(const mint &rhs) {
        if ((x += MOD - rhs.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator*=(const mint &rhs) {
        (x *= rhs.x) %= MOD;
        return *this;
    }

    constexpr mint operator+(const mint &rhs) const {
        mint res(*this);
        return res += rhs;
    }

    constexpr mint operator-(const mint &rhs) const {
        mint res(*this);
        return res -= rhs;
    }

    constexpr mint operator*(const mint &rhs) const {
        mint res(*this);
        return res *= rhs;
    }

    [[nodiscard]] constexpr mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    [[nodiscard]] constexpr mint inv() const {
        return pow(MOD - 2);
    }

    mint &operator/=(mint rhs) {
        return *this *= rhs.inv();
    }

    mint operator/(const mint rhs) const {
        return mint(*this) /= rhs;
    }

    constexpr bool operator==(const mint &rhs) const noexcept {
        return this->x == rhs.x;
    }

    constexpr bool operator!=(const mint &rhs) const noexcept {
        return this->x != rhs.x;
    }

    bool operator<(const mint &rhs) const noexcept {
        return this->x < rhs.x;
    }

    bool operator>(const mint &rhs) const noexcept {
        return this->x > rhs.x;
    }

    bool operator<=(const mint &rhs) const noexcept {
        return this->x <= rhs.x;
    }

    bool operator>=(const mint &rhs) const noexcept {
        return this->x >= rhs.x;
    }

    friend istream &operator>>(istream &is, mint &a) {
        long long t;
        is >> t;
        a = mint(t);
        return is;
    }

    friend ostream &operator<<(ostream &os, const mint &a) {
        return os << a.x;
    }
};


void solve() {
    ll N;
    cin >> N;
    mint ans = mint(10).pow(N) - mint(9).pow(N) - mint(9).pow(N) + mint(8).pow(N);
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

using namespace std;

#define pb push_back
#define fi first
#define se second
#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);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

const double eps = 1e-10;
const int MOD = 1000000007;

void printv(vector<auto> const& s) {
  REP(i, s.size()) {
    cout << s[i] << endl;
  }
}

void print(auto const s) {
  cout << s << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n, m; cin >> n >> m;
  const int NMAX = 1000;
  const int MMAX = 2000;
  const ll INF = 1ll << 50;
  vi a(MMAX), b(MMAX);
  vector<ll> c(MMAX);

  REP(i, m) {
    cin >> a[i] >> b[i] >> c[i];
    c[i] = -c[i];
  }

  vector<ll> dist(NMAX, INF);
  vector<bool> negative(NMAX, false);
  dist[0] = 0;

  REP(loop, n) {
    REP(i, m) {
      if(dist[a[i] - 1] == INF) continue;

      if(dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
        dist[b[i] - 1] = dist[a[i] - 1] + c[i];
      }
    }
  }

  ll ans = dist[n-1];

  REP(loop, n) {
    REP(i, m) {
      if(dist[a[i] - 1] == INF) continue;

      if(dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
        dist[b[i] - 1] = dist[a[i] - 1] + c[i];
        negative[b[i] - 1] = true;
      }

      if(negative[a[i] - 1] == true) {
        negative[b[i] - 1] = true;
      }
    }
  }


  if(negative[n-1]) {
    cout << "inf" << endl;
  } else {
    cout << -ans << endl;
  }




}


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

using namespace std;

typedef long long ll;

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

	int N, M;
	cin >> N >> M;

	int maxL = 0;
	int minR = N+1;

	rep(i, M){
		int l, r;
		cin >> l >> r;

		maxL = max(maxL, l);
		minR = min(minR, r);
	}

	cout << max(minR - maxL + 1, 0) << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
    int to,next;
}q[maxn];
int head[maxn],cnt=0,dis[maxn][10];
int n,m;
void add_edge(int from,int to){
    q[cnt].to=to;
    q[cnt].next=head[from];
    head[from]=cnt++;
}
typedef pair<int,int>pll;
void bfs(int x){
    queue<pll>que;
    que.push(pll(x,0));
    memset(dis,-1,sizeof(dis) );
    dis[x][0]=0;
    while(!que.empty()){
        x=que.front().first;
        int y=que.front().second;
        que.pop();
        for(int i=head[x];i!=-1;i=q[i].next){
            int to=q[i].to;
            int cost=(y+1)%3;
            if(dis[to][cost]>=0) continue;
            dis[to][cost]=dis[x][y]+1;
            que.push(pll(to,cost));
        }
    }
}
int main()
{
    memset(head,-1, sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int from,to;
        scanf("%d%d",&from,&to);
        add_edge(from,to);
    }
    int s,t;
    scanf("%d%d",&s,&t);
    bfs(s);
    if(dis[t][0]>=0) dis[t][0]/=3;
    printf("%d\n",dis[t][0]);
    return 0;
}

Measured memory_bytes: 5760
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 200000;
priority_queue<pair<ll, int> >que;
ll A[MAXN + 5], B[MAXN + 5]; int n;
int lst(int x) {return x == 1 ? n : x - 1;}
int nxt(int x) {return x == n ? 1 : x + 1;}
int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%lld", &A[i]);
	for(int i=1;i<=n;i++) {
		scanf("%lld", &B[i]);
		que.push(make_pair(B[i], i));
	}
	ll ans = 0;
	while( !que.empty() ) {
		pair<ll, int>t = que.top(); que.pop();
		int x = t.second;
		if( B[x] == A[x] ) continue;
		ll p = B[lst(x)] + B[nxt(x)];
		if( B[x] - p < A[x] ) {
			puts("-1");
			return 0;
		}
		else {
			ll del = (B[x] - A[x]) / p;
			ans += del, B[x] -= del * p;
			que.push(make_pair(B[x], x));
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 8816