akhauriyash/Code-Regression huggingface dataset:
#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;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#define mp make_pair

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename A,typename B> istream& operator>>(istream&,pair<A,B>&);
template<typename A> istream& operator>>(istream&,vector<A>&);
void add(int&,int);
int mul(int,int);
int powz(int,int);
int sub(int,int);
template<typename A> ostream& operator<<(ostream&,vector<A>&);

const int N=500001;
	
void solve(){
	int n,d;
	cin>>n>>d;
	vector<vector<int>>v(n,vector<int>(d));
	cin>>v;
	//~ for(auto &i:v)cin>>i;
	//~ for(int 
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int vl=0;
			for(int k=0;k<d;k++){
				vl+=(v[j][k]-v[i][k])*(v[j][k]-v[i][k]);
			}
			int x=sqrt(vl);
			if(x*x==vl){
				ans++;
			}
		}
	}
	cout<<ans;
	
}
	
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc=1;
	//~ cin>>tc;
	for(int _=0;_<tc;_++){
		//~ cout<<"Case #"<<_+1<<": ";
		solve();
		if(_!=tc-1)
		cout<<"\n";
	}
}
 
int mul(int a,int b)
{
	return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b)
{
	a+=b;
	if(a>=mod)a-=mod;
}

int sub(int a,int b){
	a-=b;
	if(a<0){
		a+=mod;
	}
	return a;
}
 
int powz(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=mul(res,a);
		b/=2;
		a=mul(a,a);
	}
	return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
	input>>x.F>>x.S;
	return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
	for(auto& i:x)
		input>>i;
	return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
	for(auto& i:x)
	    output<<i<<' ';
	return output;	
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	
	static boolean[] primes;
	
	static void primeSet(final int MAX){
		primes = new boolean[MAX+1];
		primes[2] = true;
		for(int i=3;i<=MAX;i+=2){
			primes[i] = true;
		}
		int rt = (int) Math.sqrt(MAX);
		for(int i=3;i<=rt;i+=2){
			if(primes[i]){
				for(int j=i*2;j<=MAX;j+=i){
					primes[j] = false;
				}
			}
		}
	}

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

		int call = 0;
		while(true){
			int n = stdIn.nextInt();
			if(n==0)
				return;
			if(call<n){
				primeSet(n*2);
				call=n;
			}
			
			int cnt = 0;
			for(int i=n+1;i<=2*n;i++){
				if(primes[i]){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
	}
}

Measured memory_bytes: 13000
#include<iostream>
using namespace std;
int main(){
  	cin.tie(0);
  	ios::sync_with_stdio(false);
  	int a[3];
  	for (int i = 0; i < 3; i++) cin >> a[i];
  	int five = 0;
  	int seven = 0;
  	for (int i = 0; i < 3; i++) {
      	if (a[i] == 5)
          	five++;
      	if (a[i] == 7)
          	seven++;
    }
  	if (five == 2 && seven == 1)
      	cout << "YES" << endl;
  	else
      	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

int N;
vector<int> xlist;

int func(int mid)
{
    int ret = 0;
    for (int i = 0; i < N; i++)
    {
        ret += pow(mid - xlist[i], 2);
    }

    return ret;
}

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

    cin >> N;

    xlist.assign(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> xlist[i];
    }

    int lo = 1;
    int hi = 100;
    while (hi - lo >= 3)
    {
        int mid1 = (lo * 2 + hi) / 3;
        int mid2 = (lo + hi * 2) / 3;

        if (func(mid1) > func(mid2))
        {
            lo = mid1;
        }
        else
        {
            hi = mid2;
        }
    }

    int result = func(lo);
    for (int x = lo + 1; x <= hi; x++)
    {
        result = min(result, func(x));
    }

    cout << result;

    return 0;
}

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

using namespace std;

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

	int a = int(sqrt(N*2));

	if (N*2 == a*(a+1)){
		cout << "Yes" << endl;
		int A = a + 1; //部分集合の数
		cout << A << endl;
		vector<vector<int>> S(A, vector<int>(0, 0));

		int n = 0;

		for (int a=0; a<A; a++){
			for (int b=a+1; b<A; b++){
				n += 1;
				S[a].push_back(n);
				S[b].push_back(n);
			}
		}

		for (int i=0; i<A; i++){
			cout << A - 1;
			for (int j=0; j<A-1; j++){
				cout << " " << S[i][j];
			}
			cout << endl;
		}

	}
	else{
		cout << "No" << endl;
	}

}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
#define ll long long int
#define l(i,a,b) for(ll i=a;i<b;i++)
using namespace std;
int main(){
	ll n,tle=0,wa=0,re=0,ac=0;
	cin>>n;
	string s[n];
	l(i,0,n){
		cin>>s[i];
		if(s[i]=="TLE") tle++;
		else if(s[i]=="WA") wa++;
		else if(s[i]=="AC") ac++;
		else if(s[i]=="RE") re++;
	}
	cout<<"AC x "<<ac<<"\n";
	cout<<"WA x "<<wa<<"\n";
	cout<<"TLE x "<<tle<<"\n";
	cout<<"RE x "<<re<<"\n";
}

Measured memory_bytes: 6648
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
    int n;string s;cin>>n>>s;
    vector<set<int>> k(26);
    rep(i,n){
        k[s[i]-'a'].insert(i);
    }
    int q;cin>>q;
    rep(_,q){
        int a;cin>>a;
        if(a==1){
            int i;char c;
            cin>>i>>c;
            i--;
            k[s[i]-'a'].erase(i);
            s[i]=c;
            k[s[i]-'a'].insert(i);
        }
        else{
            int l,r;
            cin>>l>>r;
            l--;r--;
            int ans =0;
            rep(i,26){
                auto it = k[i].lower_bound(l);
                if(it!=k[i].end()&&*it<=r)ans++;
            }
            cout<<ans<<endl;
        }
    }

}


Measured memory_bytes: 24196
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
MP={}
res = 0
for i, A in reversed(list(enumerate(LI(), start=1))):
    if (-A-i) in MP: res += MP[-A-i]
    if not A-i in MP:
        MP[A-i] = 0
    MP[A-i] += 1

# print(MP)

print(res)


Measured memory_bytes: 58840
#include <iostream>
#include <algorithm>


using namespace std;

typedef long long ll;
const int MAX = 2e5;
int a[MAX + 1];
ll n, k;

bool lessThanK(ll x, ll k) {
    ll skip = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] < 0) {
            int l = 0, h = n;
            while (l < h) {
                int m = l + (h - l) / 2;
                if (1ll * a[i] * a[m] < x) {
                    h = m;
                } else {
                    l = m + 1;
                }
            }
            skip += n - h;
        } else {
            int l = 0, h = n;
            while (l < h) {
                int m = l + (h - l) / 2;
                if (1ll * a[i] * a[m] < x) {
                    l = m + 1;
                } else {
                    h = m;
                }
            }
            skip += h;
        }

        if (1ll * a[i] * a[i] < x) skip--;
    }

    skip /= 2;
    return skip < k;
}

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

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a, a + n);

    ll lo = (ll)-1e18;
    ll hi = (ll)1e18 + 1;
    while (lo + 1 < hi) {
        ll x = lo + (hi - lo) / 2;
        if (lessThanK(x, k)) {
            lo = x;
        } else {
            hi = x;
        }
    }

    cout << lo;

    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>

int main() {
  int num;
  std::cin >> num;
  std::vector<int> a(num);
  for (int i = 0; i < num; ++i) std::cin >> a.at(i);

  int ans = 0;
  for (int i = 0; i < num; ++i) {
    for (int j = 0; j < num; ++j) {
      ans = std::max(ans, std::abs(a.at(i) - a.at(j)));
    }
  }
  std::cout << ans << std::endl;
}


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

n,m,k = map(int,input().split())
graph = {i+1:[] for i in range(n)}
block = {i+1:[] for i in range(n)}
ans = [-1 for _ in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
for _ in range(k):
  c,d = map(int,input().split())
  block[c].append(d)
  block[d].append(c)
  
  
from collections import deque

for i in range(1,n+1):
  if ans[i-1] != -1:
    continue
  queue = deque([i])
  friends = set([i])
  while queue:
    node = queue.popleft()
    for n in graph[node]:
      block[node].append(n)
      if n in friends:
        continue
      friends.add(n)
      queue.append(n)
  for n in friends:
    ans[n-1] = len(friends)-1 #remove self
    for b in set(block[n]):
      if b in friends:
        ans[n-1] -= 1
    
    
print(*ans)
      
  
  




Measured memory_bytes: 99428
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ld long double
const int M = 1e9+7;

vector<int> a,b;
vector<int> ord;
vector<int> lf,ri;
stack<int> s;

int32_t main(){
	int a,b;
	cin>>a>>b;
	if(a!=1 && b!=1){
		cout << "1\n";
	}else if(a!=2 && b!=2){
		cout << "2\n";
	}else{
		cout << "3\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(x) memset(x,0,sizeof(x));
#define forn(i,a,b) for(int i=(a);i<=(b);++i)
#define rev(i,a,b) for(int i=(a);i>=(b);--i)
#define sc(x) scanf("%d",&x)
#define bug(x) cerr<<#x<<":"<<(x)<<endl
using namespace std;
typedef long long ll;
const int M = 1000000;
int main(){
    int l,r;
    cin>>l>>r;
    if(r-l>=2019) cout<<0<<endl;
    else{
        ll ans=100000;
        int md=2019;
        forn(i,l,r-1)
            forn(j,i+1,r){
                ans=min(ans,1ll*i*j%md);
            }
        cout<<ans<<endl;
    }
    return 0;
}

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

#define dlog(str) cout << "====" << str << endl;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s; i <= e; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    LLI N;
    cin >> N;
    vector<LLI> v(N);
    vector<LLI> l(N + 1);
    vector<LLI> r(N + 1, 0);
    REP(i, N) { cin >> v[i]; }
    l[0] = 0;
    r[0] = v[N - 1];
    REP(i, N - 1) { l[i + 1] = l[i] + v[i] * (i % 2 == 0 ? 1 : -1); }
    REP(i, N - 1) { r[i + 1] = r[i] + v[N - i - 2] * (i % 2 == 1 ? 1 : -1); }
    REP(i, N) { cout << (r[N - i - 1] - l[i]) * (i % 2 == 0 ? 1 : -1) << " "; }

    return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int A = 0;
  int B = 0;
  
  cin >> N ;
  
  vector<int> card(N);
  for(int i=0;i<N;i++){
    cin>> card.at(i);
  }
  
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  
  for(int i=0;i<N;i++){
    
    if(i%2==0){
      A += card.at(i);
    }else{
      B += card.at(i);
    }
    
  }
  cout << A - B << endl;
}

Measured memory_bytes: 3576
#include "bits/stdc++.h"
#define rep(i,n)for(int i=0;i<(int)(n);i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
int l[105];
signed main(){
	int n;cin>>n;
	rep(i,n)cin>>l[i];
	int ans=0;
	rep(i,n){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				if(l[i]!=l[j]&&l[j]!=l[k]&&l[k]!=l[i]&&abs(l[i]-l[j])<l[k]&&l[k]<l[i]+l[j])ans++;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;

int main() {
    long long n; cin >> n;
    int max = sqrt(n);
    int i = max;
    for (; 0 < i; --i) {
        if (n % i == 0) break;
    }
    long long d = i + (n / i) - 2;
    cout << d << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n;cin>>n;
    n *= 100;
    if(n%108 == 0){cout<<n/100/1.08<<endl; return 0;}
    
    n /=100;
    int ex = n/1.08;
    for(int d = -1; d<=3; ++d){
        int tmp = (ex+d)*1.08;
        if(tmp == n){cout<<ex+d<<endl; return 0;}
    }
    cout<<":("<<endl; return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int main(){
  int N;
  cin>>N;
  vector<string> S(N);
  rep(i,N) cin>>S[i];

  int ans=0;
  for(int i=0;i<N;i++){
    if(S[i]=="E869120") ans++;
  }
  cout<<ans<<endl;

  return 0;
}



Measured memory_bytes: 3340
#include <iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
typedef long long int ll;
using namespace std;

int main(){
    int64_t N;
    int64_t T[1000],A[1000];
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> T[i] >> A[i];
    }
    int64_t taka=T[0];
    int64_t aoi=A[0];
    for(int i=1;i<N;i++){
        int64_t tmp_taka=taka/T[i];
        int64_t tmp_aoi=aoi/A[i];
        if(taka%T[i]!=0){
            tmp_taka++;
        }
        if(aoi%A[i]!=0){
            tmp_aoi++;
        }
        int64_t tmp=max(tmp_taka,tmp_aoi);
        taka=tmp*T[i];
        aoi=tmp*A[i];
    }
    cout << taka+aoi << endl;
    
    
    
    return 0;
}

Measured memory_bytes: 256
H,W=map(int,input().split())
import heapq
w=[[0 for i in range(W)]for j in range(H)]
for i in range(H):
  S=input()
  for j in range(W):
    w[i][j]=S[j]
    
L=[[0 for i in range(W)] for j in range(H)]
R=[[0 for i in range(W)] for j in range(H)]
U=[[0 for i in range(W)] for j in range(H)]
D=[[0 for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      L[i][j]=0
    elif j==0:
      L[i][j]=1
    else:
      L[i][j]=L[i][j-1]+1
for i in range(H):
  for j in range(W-1,-1,-1):
    if w[i][j]=='#':
      R[i][j]=0
    elif j==W-1:
      R[i][j]=1
    else:
      R[i][j]=R[i][j+1]+1
for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      D[i][j]=0
    elif i==0:
      D[i][j]=1
    else:
      D[i][j]=D[i-1][j]+1  
for i in range(H-1,-1,-1):
  for j in range(W):
    if w[i][j]=='#':
      U[i][j]=0
    elif i==H-1:
      U[i][j]=1
    else:
      U[i][j]=U[i+1][j]+1
m=0

for i in range(H):
  for j in range(W):
    x=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    m=max(x,m)
print(m)
    

Measured memory_bytes: 490568
#include <bits/stdc++.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    unordered_map<string, int> mp;
    long long cnt = 0;
    cin >> n;
    string str[n];
    for(int i = 0; i < n; i++) {
      cin >> str[i];
    }
    for(int i = 0; i < n; i++) {
      sort(str[i].begin(), str[i].end());
      if(mp.count(str[i])){
        mp[str[i]] += 1;
      }else {
        mp[str[i]] = 1;
      }
    }
    for(auto& i : mp) {
        long long s = i.second;
        if(s > 1) {
          cnt += s*(s-1) / 2;
        }
    }
    cout << cnt;

    return 0;
}


Measured memory_bytes: 17572
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  while(true){
	int N, A, B, C, X; cin >> N >> A >> B >> C >> X; if(!N) break;
	VI Y(N);
	REP(i,N) cin >> Y[i];
	vector<bool> used(C);
	int cnt = 0;
	REP(i,N){
	  fill(ALL(used), false);
	  if(i > 0){
		X = (A*X + B) % C;
		++cnt;
	  }
	  while(true){
		if(X == Y[i]) break;
		if(used[X]){
		  cnt = -1;
		  break;
		}
		used[X] = true;
		X = (A*X + B) % C;
		++cnt;
	  }
	  if(cnt < 0 || cnt > 10000){
		cnt = -1;
		break;
	  }
	}
	cout << cnt << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void){
    int x;
    cin >> x;
    if(x < 100){
      cout << 0 << endl;
      return 0;
    }
 
    int leave = x % 100;
    int cnt = x / 100;
    int nokori = leave;
    
    for(int i = 1; i <= cnt; i++){
      leave = min({abs(leave - 0), abs(leave - 1), abs(leave - 2), abs(leave - 3), abs(leave - 4), abs(leave - 5)});
 
    }
    if(leave == 0){
      cout << 1 << endl;
    }else {
      cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
n,x=map(int,input().split())
A=list(map(int,input().split()))
if n==2:
  print(max(0,sum(A)-x))
  exit()
if n==3:
  if A[0]+A[1]<=x:
    print(max(0,A[1]+A[2]-x))
  elif A[0]<=x:
    ans=A[1]-x+A[0]
    A[1]=x-A[0]
    print(ans+max(0,A[1]+A[2]-x))
  else:
    ans=A[0]+A[1]-x
    A[1]=0
    A[0]=x
    print(ans+max(0,A[1]+A[2]-x))
  exit()
ans=0
for i in range(n-1):
  if A[i]+A[i+1]<=x:
    pass
  elif A[i]<=x:
    ans=ans+A[i]-x+A[i+1]
    A[i+1]=x-A[i]
  else:
    ans=ans+A[i]+A[i+1]-x
    A[i+1]=0
    A[i]=x
print(ans)

Measured memory_bytes: 14252
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int n, k, a;
    scanf("%d%d", &n, &k);
    vector<int> d(n + 1);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        ++d.at(a);
    }
    sort(d.begin(), d.end(), greater<int>());
    printf("%d\n", n - accumulate(d.begin(), d.begin() + k, 0));
    return 0;
}


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

int main(){
	vector<string> s(3);
	cin >> s[0] >> s[1] >> s[2];
	int i[3];
	i[0] = i[1] = i[2] = 0;
	int now = 0;
	while(true) {
		if((s[now].size() == i[now])) {
			break;
		}
		char tmp = (s[now])[ i[now] ];
		i[now]++;
		if(tmp == 'a') {
			now = 0;
		}
		if(tmp == 'b') {
			now = 1;
		}
		if(tmp == 'c') {
			now = 2;
		}
	}
	switch(now) {
	case 0:
		cout << "A" << endl;
		break;
	case 1:
		cout << "B" << endl;
		break;
	case 2:
		cout << "C" << endl;
		break;
	}
	
}


Measured memory_bytes: 256
fn main() {
    let nm = read_vec::<usize>();
    let a = read_vec::<usize>();
    let sum: usize = a.iter().sum();

    if nm[0] < sum {
        println!("-1");
    } else {
        println!("{}", nm[0] - sum);
    }
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 2208
#include <iostream>
#include <iomanip>
#include <cmath>
struct {double x, y;} p[3];
using namespace std;
int main()
{
	int t, i, j;
	double r, a, b, c, d, e, f, l, m, n;
	cin >> t;
	for (i = 0; i < t; i++)
	{
		for (j = 0; j < 3; j++)
			cin >> p[j].x >> p[j].y;
		a = p[0].x-p[1].x;
		b = p[0].y-p[1].y;
		c = -(p[0].x*p[0].x)-(p[0].y*p[0].y)+(p[1].x*p[1].x)+(p[1].y*p[1].y);
		d = p[1].x-p[2].x;
		e = p[1].y-p[2].y;
		f = -(p[1].x*p[1].x)-(p[1].y*p[1].y)+(p[2].x*p[2].x)+(p[2].y*p[2].y);
		m = (c*d-a*f)/(b*d-a*e);
		l = (c*e-b*f)/(e*a-b*d);
		n = -((p[0].x*p[0].x)+(p[0].y*p[0].y)+p[0].x*l+p[0].y*m);
		cout << setprecision(3) << setiosflags(ios::fixed);
		cout << -l/2 << " " << -m/2 << " " << sqrt(l*l+m*m-4*n)/2 << endl;
	}
}

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

int main() {
  int a,b,c,d;
  
  cin >> a >> b >> c >> d;
  
  int left(a+b), right(c+d);
  if(right < left)
  {
    cout << "Left" <<endl;
  }
  else if(right > left)
  {
    cout << "Right" <<endl;
  }
  else
  {
    cout << "Balanced" <<endl;
  }
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(scan.next());
        }
        scan.close();

        boolean isPairwise = true;
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++) {
            int curA = a[i];
            for (int j = 2; j <= Math.sqrt(curA); j++) {
                if (curA % j == 0) {
                    if (set.contains(j)) {
                        isPairwise = false;
                        break;
                    }

                    set.add(j);
                    while (curA % j == 0) {
                        curA /= j;
                    }
                }
            }

            if (curA >= 2) {
                if (set.contains(curA)) {
                    isPairwise = false;
                } else {
                    set.add(curA);
                }
            }

            if (!isPairwise) {
                break;
            }
        }

        if (isPairwise) {
            System.out.println("pairwise coprime");
            return;
        }

        int gcd = a[0];
        for (int i = 1; i < n; i++) {
            gcd = calcGcd(gcd, a[i]);
        }

        if (gcd == 1) {
            System.out.println("setwise coprime");
        } else {
            System.out.println("not coprime");
        }

    }

    private static int calcGcd(int a, int b) {
        if (a % b == 0) {
            return b;
        } else {
            return calcGcd(b, a % b);
        }
    }
}


Measured memory_bytes: 62956
#include <stdio.h>

int main(void)
{
    int trump[4][13], No;
    int n, i, j;
    char suit;    

    for(i=0;i<4;i++){
        for(j=0;j<13;j++){
            trump[i][j] = 0;
        }
    }

    scanf("%d", &n);

    for(i=0;i<n;i++){
        scanf("%s %d", &suit, &No);
        
        if(suit == 'S'){
            trump[0][No-1] = 1;
        }
        if(suit == 'H'){
            trump[1][No-1] = 1;
        }
        if(suit == 'C'){
            trump[2][No-1] = 1;
        }
        if(suit == 'D'){
            trump[3][No-1] = 1;
        }        
    }

    for(i=0;i<4;i++){
        for(j=0;j<13;j++){
            if(trump[i][j] == 0){
                if(i == 0){
                    printf("S %d\n", j+1);
                }     
                if(i == 1){
                    printf("H %d\n", j+1);
                }     
                if(i == 2){
                    printf("C %d\n", j+1);
                }     
                if(i == 3){
                    printf("D %d\n", j+1);
                }     
            }
        }
    }   
    return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <algorithm>
#define llint long long

using namespace std;

int n;
string s;
int a[5000005];

llint adjust(llint p, llint x)
{
  if(x == 0 || x < a[p]) return -1;
  x = (x-a[p])/10*10 + a[p];
  if(n-p < 9){
    llint sum = 0, mul = 1;
    for(int i = p; i < n; i++){
      sum += mul * a[i];
      mul *= 10;
    }
    x = min(x, sum);
  }
  return x;
}

bool sub(llint p, llint x)
{
  //cout << "-" << x << endl;
  for(;x;x/=10){
    a[p] -= x % 10;
    llint t = p;
    while(a[t] < 0){
      a[t] += 10, a[t+1]--;
      t++;
    }
    p++;
  }
  return a[n-1] == 0;
}

bool check(llint x)
{
  //cout << "! " << x << endl;
  for(int i = 0; i < n; i++) a[i] = s[i]-'0';
  x *= 9;
  for(int i = 0; i < n; i++){
    x = adjust(i, x);
    if(x == -1) return false;
    if(sub(i, x)) break;
    //cout << "="; for(int i = n-1; i >= 0; i--) cout << a[i]; cout << endl;
  }
  return true;
}

int main(void)
{
  cin >> s;
  n = s.size();
  reverse(s.begin(), s.end());

  llint ub = n*2, lb = 0, mid;
  while(ub-lb>1){
    mid = (ub+lb)/2;
    if(check(mid)) ub = mid;
    else lb = mid;
  }
  cout << ub << endl;

  return 0;
}


Measured memory_bytes: 2820
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

int mem[2000010];
set<pair<int, int>> que;
int ans = 987654321;

int sum(int x) {
  int s = 0;
  while (x) {
    s += x % 10;
    x /= 10;
  }
  return s;
}

void push(int x, int d) {
  if (mem[x] != -1 && mem[x] <= d) return;
  mem[x] = d;
  que.insert(make_pair(x, d));
  ans = min(ans, d + sum(x));
}

int main() {
  int K;
  scanf("%d", &K);

  memset(mem, -1, sizeof(mem));
  for (int m = 1; m <= 9; ++m) push(K * m, 0);

  while (!que.empty()) {
    int x = que.begin()->first;
    int d = que.begin()->second;
    que.erase(que.begin());

    for (int m = 0; m <= 9; ++m) {
      int t = x + K * m;
      push(t / 10, t % 10 + d);
    }
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 10752
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<sstream>
#include<cstdlib>
using namespace std;
int flag,a,b;
void run()
{
	cin>>flag;
	if(flag==1) { cout<<"Hello World"; exit(0);}
	cin>>a>>b;
	cout<<a+b;
}
int main()
{
	run();
	return 0;
}

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

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

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;

#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)

int main()
{
  ll N;
  cin >> N;
  ll a[N];
  ll ans = 0;
  rep(i,0,N){
    cin >> a[i];
    ans += a[i] - 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import os

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, C = list(map(int, sys.stdin.readline().split()))

    ret = 'NO'
    for n in range(100):
        if (A * n) % B == C:
            ret = 'YES'

    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int dp[20][10];     // (何桁目, 1~9のどの数字か)

int main(){
    ll N;
    cin >> N;
    
    vector<int> digit;
    while(N > 0){
        digit.push_back(N % 10);
        N /= 10;
    }
    reverse(digit.begin(), digit.end());
    
    bool flag = true;
    for(int i = 1; i < digit.size(); i++){
        if(digit[i] != 9){
            flag = false;
            break;
        }
    }
    
    int ans;
    if(flag){
        ans = digit[0] + 9 * (digit.size() - 1);
    }
    else{
        ans = digit[0] - 1 + 9 * (digit.size() - 1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
fn main() {
    use std::io::Read;
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    
    let n: usize = iter.next().unwrap().parse().unwrap();

    let mut graph = vec![vec![];n];
    for _ in 0..n-1 {
        let a: usize = iter.next().unwrap().parse::<usize>().unwrap() - 1;
        let b: usize = iter.next().unwrap().parse::<usize>().unwrap() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }

    let diameter = get_diameter(&graph);
    println!("{}", if diameter % 3 == 1 {"Second"} else {"First"});
}

#[allow(dead_code)]
fn far_vertex(graph: &[Vec<usize>], pre: Option<usize>, cur: usize) -> (usize, usize) {
    let mut ret = (cur, 0);
    for &v in &graph[cur] {
        match pre {
            Some(p) if v == p => continue,
            _ => (),
        };
        let mut tmp = far_vertex(graph, Some(cur), v);
        tmp.1 += 1;
        if tmp.1 > ret.1 {
            ret = tmp;
        }
    }
    ret
}
#[allow(dead_code)]
pub fn get_diameter(graph: &[Vec<usize>]) -> usize {
    let leaf = far_vertex(graph, None, 0);
    let far = far_vertex(graph, None, leaf.0);
    far.1
}

Measured memory_bytes: 45684
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
using namespace std;

struct edge{long long int from,to,cost;};

edge ed[200001];

int v,E,cou=0;
long long int d[200001],n;

void Bellmanford(int s){
    for(int i=0;i<=v;i++){
        d[i]=1145141919810931;
    }
    d[s]=0;
    while(true){
        bool update=false;
        bool nupdate=false;
        for(int i=1;i<=E;i++){
            edge e=ed[i];
            if(d[e.from]!=1145141919810931&&d[e.to]>d[e.from]+e.cost){
                d[e.to]=d[e.from]+e.cost;
                update=true;
                if(e.to==n){
                    nupdate=true;
                }
            }
        }
        cou++;
        
        if(!update||cou>=v&&!nupdate)break;
        if(cou>=v){
            cout<<"inf"<<endl;
            return ;
        }
    }
    cout<<-d[n]<<endl;
    return ;
}

int main() {
	//cout << fixed << setprecision(10);
	long long int m,a[200001],b[200001],c[200001];
	cin>>n>>m;
	v=n;
	E=m;
	for(int i=1;i<=m;i++){
	    cin>>a[i]>>b[i]>>c[i];
	    ed[i].from=a[i];
	    ed[i].to=b[i];
	    ed[i].cost=-c[i];
	}
	Bellmanford(1);
}

Measured memory_bytes: 4480
gets
a = gets.split.map(&:to_i)

table = Hash.new(0)

a.each do |n|
  table[n] += 1
end

nums = table.keys.sort
last_index = nums.length - 1
nums_count = nums.map.with_index do |n, i|
  count = table[n]

  unless i.zero?
    count += table[n - 1] if (n - nums[i - 1]) == 1
  end

  unless i == last_index
    count += table[n + 1] if (nums[i + 1] - n) == 1
  end

  count
end

puts nums_count.max

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

int main() {
    int  n;
    cin>>n;
    long long arr[n];
    set<long long>s;
    map<long long,long long>mp;
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        mp[arr[i]]++;
        sum+=arr[i];
        s.insert(arr[i]);
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(s.find(a)!=s.end()){
            sum-=mp[a]*(a-b);
            mp[b]+=mp[a];
            mp.erase(a);
            s.erase(s.find(a));
            s.insert(b);
        }
        //for(auto j=mp.begin();j!=mp.end();j++)cout<<j->first<<" "<<j->second<<endl;
        //for(auto j=s.begin();j!=s.end();j++)cout<<*j<<endl;
        cout<<sum<<endl;
    }
}



Measured memory_bytes: 11240
#include <stdio.h>
int main(){
int a,b,c;
int yakusuu=0;
int i;

scanf("%d%d%d",&a,&b,&c);

for(i=b;i>=a;i--){
if(c%i==0) yakusuu++;
}

printf("%d\n",yakusuu);

return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;

lli a[3];
int main(){
  scanf("%lld%lld%lld",&a[0],&a[1],&a[2]);
  lli res=1;
  int flg=1;
  rep(i,3){
    if(a[i]%2==0){flg=0; res=0;}
  }

  if(flg){
    int max=0;
    rep(i,3) if(a[max]<a[i]) max=i;
    rep(i,3){
      if(max!=i) res*=a[i];
    }
  }
  printf("%lld\n",res);


  return 0;

}


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

using namespace std;

using int64 = long long;

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

  int n;
  string a, b;
  cin >> n >> a >> b;
  int ans = 2 * n;
  for (int k = 0; k < n; k++) {
    bool valid = true;
    for (int i = 0; i < n; i++) {
      if (i + k < n && a[i + k] != b[i]) {
        valid = false;
      }
    }
    if (valid) {
      ans = n + k;
      break;
    }
  }
  cout << ans << endl;
}


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

using namespace std;
const int maxn=100;
int N;
int arr[maxn];
vector<pair<int,int>> out;
#define mp(a,b) make_pair(a,b)
int main(){
  scanf("%d",&N);
  for(int i=1;i<=N;i++){
    scanf("%d",arr+i);
  }
HERE:
  int m=max_element(arr+1,arr+1+N)-arr;
  int n=min_element(arr+1,arr+1+N)-arr;
  if(arr[m]==arr[n]){
    puts("0");return 0;
  }
  if(arr[m]<=0){
    for(int i=N-1;i>=1;i--){
      if(1){
        arr[i]+=arr[i+1];
        out.push_back(mp(i+1,i));
      }
    }
  }
  else if(arr[n]>=0){
    for(int i=2;i<=N;i++){
      if(1){
        arr[i]+=arr[i-1];
        out.push_back(mp(i-1,i));
      }
    }
  }
  else {
    int f=arr[m]>-arr[n]?m:n;
    for(int i=1;i<=N;i++){
      arr[i]+=arr[f];
      out.push_back(mp(f,i));
    }
    goto HERE;
  }
  printf("%d\n",int(out.size()));
  for(int i=0;i<out.size();i++){
    printf("%d %d\n",out[i].first,out[i].second);
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e12);
const ll mod = ll(1e9) + 7;
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll t = 1;
    rep1(i, n){
        t *= i;
        t %= mod;
    }
    return t;
}

ll power(ll a, ll b){
    a %= mod;
    if(b == 0){
        return 1;
    }
    ll ans = power(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}

ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    ll ans = 1;
    for(ll i = 0; i < b; i++) {
        ans *= (a - i);
        ans /= (i + 1);
        ans %= mod;
    }
    return ans;
}

int main(){
    char a;
    cin >> a;
    if(a == 'A')pf('T');
    else if(a == 'T')pf('A');
    else if(a == 'C')pf('G');
    else pf('C');
    return 0;
}



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

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int res = 0;
  for (int a = 0; a <= A; ++a) {
    for (int b = 0; b <= B; ++b) {
      for (int c = 0; c <= C; ++c) {
        int total = 500*a + 100*b + 50*c;
        if (total == X) ++res; 
      }
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  int r = 0;
  cin >> r;
  if(r < 1200)cout << "ABC" << endl;
  else cout << "ARC" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

#define INF 1000000009

using namespace std;

void dfs( const vector<vector<int>>& table, const vector<int>& values, vector<bool>& checked, int node, vector<int>& dp,
          vector<int>& ans )
{
    checked[node] = true;

    int old_value;

    auto it = lower_bound(dp.begin(), dp.end(), values[node] );
    old_value = *it;
    *it = values[node];

    for(auto new_node:table[node]){
        if(not checked[new_node]) dfs( table, values, checked, new_node, dp, ans);
    }

    ans[node] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();

    *it = old_value;

    return;
}


int main()
{
    int N,u,v;
    cin >> N;

    vector<int> values(N, 0);
    vector<vector<int>> table(N, vector<int>());

    vector<bool> checked(N, false);
    vector<int> dp(N, INF);
    vector<int> ans(N, 0);

    for(int i=0;i<N;++i){
        cin >> values[i];
    }
    
    for(int i=1;i<N;++i){
        cin >> u >> v;
        table[u-1].push_back(v-1);
        table[v-1].push_back(u-1);
     }

    dfs( table, values, checked, 0, dp, ans);

    for(int i=0;i<N;++i){
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 36648
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int a = n / 100; // 前两位
    int b = n % 100; // 后两位

    if (a >= 1 && a <= 12)
        if (b >= 1 && b <= 12) printf("AMBIGUOUS\n");
        else printf("MMYY\n");
    else 
        if (b >= 1 && b <= 12) printf("YYMM\n");
        else printf("NA\n");
    

    return 0;
}

Measured memory_bytes: 256
let conv x = 
    if x == 1 
    then 
        13
    else 
        x-1;;


let a,b = Scanf.scanf "%d %d" (fun a b -> (conv a),(conv b))
in
    Printf.printf "%s\n"
        (if a > b then "Alice" 
        else if a < b then "Bob"
        else "Draw");;

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

int main() {
    long H, N;
    cin >> H >> N;
    long sum = 0;
    for(long i = 0; i < N; i++){
        long tmp;
        cin >> tmp;
        sum += tmp;
    }
    if(sum >= H) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

const int MOD=1000000007;

ll gcd(ll x, ll y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}

ll lcm(ll x, ll y) {
    return x * y / gcd(x, y);
}


void solve(long long a, std::string s){
    if (a>=3200) {
        cout << s<< endl;
    } else {
        cout << "red" << endl;
    }
}

int main(){
    long long a;
    scanf("%lld",&a);
    std::string s;
    std::cin >> s;
    solve(a, s);
    return 0;
}


Measured memory_bytes: 256
#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 sint int32_t
#define int long long int
#define all(v) v.begin() , v.end()
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



int32_t main()
{   fastio;

    int n;
    cin>>n;

    int arr[n];
    for(int i=0; i<n; i++)
        cin>>arr[i];

    sort(arr , arr+n);

    int cnt = 0;
    //cout<<"HELP\n";
    for(int i=0; i<n-1; i++) {
        for(int j=i+1; j<n-1; j++) {
            auto p = lower_bound(arr+j+1 , arr+n , arr[i]+arr[j]);

            //if(*p == arr[i]+arr[j])
            p--;
            int d = p - arr - j;


            cnt += d;
        }
    }

    cout<<cnt<<endl;

}


Measured memory_bytes: 3640
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define ff first
#define pii pair<int, int>
#define vii vector< pair<int,int> >
#define vi vector<int>
#define vvi vector< vector< int> >
#define ss second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define ull unsigned long long
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace4(x, y, z, d)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#d<<": "<<d<<endl

#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1, 0};int dy[]={0,1,0, -1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
bool compare(const pair<int,int> &a,
             const pair<int,int> &b)
{
    if(a.ff == b.ff) {
        return (b.ss < a.ss);
    }
    return (a.ff<b.ff);
}
bool prime[1000001];
void SieveOfEratosthenes(int n) 
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.

    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}

int stones[100001];
int32_t main()
{
    IOS;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    /********************* From here ***********************/
    int n;
    cin >> n;

    rep(i, 0, n){
        cin >> stones[i+1];   
    }

    int dp[n+1];
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = dp[1] + abs(stones[2]-stones[1]);
    rep(i, 3, n+1){
        dp[i] = min(dp[i-2]+abs(stones[i]-stones[i-2]),dp[i-1]+abs(stones[i]-stones[i-1]) ); 
        //cout << i << '-' << dp[i] << endl; 
    }

    cout << dp[n];
}



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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 200010;
int N,K;
int A[MC];
vector<int> V;

int main(){
	cin >> N >> K;
	repp(i,0,N) cin >> A[i];
	sort(A,A+N);
	int z = 1;
	repp(i,1,N){
		if(A[i-1] == A[i]) ++z;
		else {
			V.PB(z);
			z = 1;
		}
	}
	V.PB(z);
	sort(V.begin(),V.end());
	int ans = 0;
	repp(i,0,V.size()-K){
		ans += V[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,i,j;string s;cin >> n >> s;
  bool S[n],ans[n];
  for(i=0;i<n;i++) S[i] = s[i] == 'o';
  for(i=0;i<4;i++){
    ans[0] = i%2;ans[1] = i>=2;
    for(j=2;j<n-1;j++) ans[j] = !(ans[j-1] == S[j-1])^ans[j-2];
    if((!(ans[n-2] == S[n-2])^ans[n-3]) == (!(ans[0] == S[0])^ans[1])){
      ans[n-1] = !(ans[n-2] == S[n-2])^ans[n-3];
      if((ans[n-2] == ans[0]) == (S[n-1] == ans[n-1])){
        for(j=0;j<n;j++) printf(((ans[j]) ? "S":"W"));
        printf("\n");return 0;
      }
    }
  }
  printf("-1\n");
  return 0;
}

Measured memory_bytes: 768
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void input()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main()
{
	  fastio();
	  int n,k,i,j,t;
	  cin>>n>>k;
	  string s;
	  cin>>s;
 	j = 0;

	int p = 0;

	int ans = 0;

	for (int i = 0; i < n; i++) {
		char ch = s[i];

		if (ch == '0' && (i == 0 || (i > 0 && s[i - 1] == '1'))) {
		    p++;
		}

		while (p > k && j < i) {
		    j++;
		    if (j > 0 && s[j] == '1' && s[j - 1] == '0') {
		        p--;
		    }
		}

		ans = max(ans, i - j + 1);
	}
	cout<<ans;
  	return 0;
}

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

using namespace std;

#define print(s) cout << (s) << endl;
#define sp(x) cout<<setprecision(x);
#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()
#define inf 10000000
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    int ans = 0;
    while(3*ans<=n){
        ans++;
    }
        cout<<ans-1<<endl;
    
return 0;
}

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

int main(){
  string a;
  cin >> a;
  if(a=="SUN") cout << 7 << endl;
  if(a=="MON") cout << 6 << endl;
  if(a=="TUE") cout << 5 << endl;
  if(a=="WED") cout << 4 << endl;
  if(a=="THU") cout << 3 << endl;
  if(a=="FRI") cout << 2 << endl;
  if(a=="SAT") cout << 1 << endl;
  return 0;
}

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

int main() {
    int N, K; cin >> N >> K;
    vector<int> A(N);
    for(auto &e : A) cin >> e;
    vector<int64_t> S(N + 1);
    for(int i = 0; i < N; ++i) S[i + 1] = S[i] + A[i];
    for(int i = 1; i <= N; ++i) S[i] = (S[i] - i) % K;
    map<int, int> ma;
    int64_t ans = 0;
    for(int i = 0; i <= N; ++i) {
        ans += ma[S[i]];
        ma[S[i]]++;
        if(i - K + 1 >= 0) ma[S[i - K + 1]]--;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 12032