akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>
#include<cmath>





using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
//const ll mod = 1000 * 1000 * 1000 + 7;




void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int res = n / 2;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'p')
            --res;
    }
    cout << res << endl;

}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
const int xp=1e9+7;
long long d[2][3002][3002],n,v[3002];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=n;i>=1;i--)
    for(int j=i;j<=n;j++)
    {
        d[1][i][j]=min(d[0][i+1][j]-v[i],d[0][i][j-1]-v[j]);
        d[0][i][j]=max(d[1][i+1][j]+v[i],d[1][i][j-1]+v[j]);
    }
    cout<<d[0][1][n];
}


Measured memory_bytes: 139776
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define debugvec(v)   rep(i, v.size()) cerr << "L" << __LINE__ << ": " << #v << "[" << i << "] = " << v[i] << endl;
#define debugvec2(v)  cerr << "L" << __LINE__ << ": " << #v << " = { "; rep(i, v.size()) cerr << v[i] << (i + 1 == v.size() ? "" : ", "); cerr << " }" << endl;
typedef long long ll;  /* 10^18 くらいまでいける */

int main(){
  int n;

  cin >> n;

  cout << pow(n, 3) << endl;

  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;
// ())((
int main() {
    int n;
    string s;
    cin >> n >> s;
    int p = 0;
    int l = 0;
    rep(i,s.size()) {
        if(s[i]=='(') p++;
        else {
            if(!p) l++;
            else --p;
        }
    }
    int r = p;
    string ans = "";
    rep(i,l) ans+='(';
    ans+=s;
    rep(i,r) ans+=')';
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3544
n,m= map(int,input().split())
info = [list(map(int,input().split())) for i in range(n)]

info = sorted(info)

ans = 0
for i in range(n):
  if info[i][1] < m:
    ans += info[i][0]*info[i][1]
    m -= info[i][1]
  else:
    ans += m*info[i][0]
    break
print(ans)

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


int main() {
	string inStr;
	cin >>inStr;
	int length = inStr.size();
	int ans = 0;
	int tmpAns = 0;
	for(int i=0;i<length;i++){
		if(inStr[i] == 'A' || inStr[i] == 'C'
			||inStr[i]=='G' || inStr[i] == 'T') {
			tmpAns ++;
		} else if(tmpAns > 0) {
			if(ans < tmpAns) {
				ans = tmpAns;
			}
			tmpAns = 0;
		}
	}
	if (ans<tmpAns) {
		ans = tmpAns;
	}
	cout <<ans <<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  char c[999][999];
  int h,w,a[999][999]={0},i,j,k;
  cin>>h>>w;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin>>c[i][j];
    }
  }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
        for(k=j;k>=0;k--){
          if(c[i][k]=='c'){
            a[i][j]=j-k;
            break;
          }
          if(k==0) a[i][j]=-1;
        }
      }
    }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(j!=w-1) cout<<a[i][j]<<" ";
      else cout<<a[i][j];
    }
    cout<<"\n";
  }
  return 0;
}

Measured memory_bytes: 7080
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <stdarg.h>
#include <algorithm>
#include <iostream>

using namespace std;

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

  if (a<1 || a>9 || b<1 || b>9)
    cout<<-1<<endl;
  else
    cout<<a*b<<endl;

  return 0;
}
 


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

string T;
int dp[200005][2];
int prv[200005][2];

int main() {
    cin >> T;
    int N = T.size();

    INIT(dp, -1);
    dp[0][0] = 0;

    for_(i,0,N) for_(j,0,2) {
        if (dp[i][j] == -1) continue;
        if (T[i] == 'P' or T[i] == '?') {
            if (dp[i + 1][1] < dp[i][j]) {
                dp[i + 1][1] = dp[i][j];
                prv[i + 1][1] = j;
            }
        }
        if (T[i] == 'D' or T[i] == '?') {
            if (j == 1) {
                if (dp[i + 1][0] < dp[i][j] + 2) {
                    dp[i + 1][0] = dp[i][j] + 2;
                    prv[i + 1][0] = j;
                }
            }
            else {
                if (dp[i + 1][0] < dp[i][j] + 1) {
                    dp[i + 1][0] = dp[i][j] + 1;
                    prv[i + 1][0] = j;
                }
            }
        }
    }

    int k = (dp[N][0] < dp[N][1] ? 1 : 0);
    int i = N;
    string ans = "";
    while (i) {
        if (k == 1) ans += 'P';
        else ans += 'D';
        k = prv[i][k];
        --i;
    }
    reverse(ALL(ans));
    cout << ans << endl;
}

Measured memory_bytes: 6924
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main() {
    //input
    string S;
    cin >> S;
    int res = 0;
    rep(i,S.length()/2){
        if(S[i] != S[S.length()-1-i])res++;
    }
    cout << res << endl;

    return 0;
}

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

using namespace std;
#define int long long

int32_t main() {
    int a, b;
    cin >> a >> b;
    ++b;

    for (int i = 61; i >= 0; --i) {
        int bit1 = (a & (1LL << i));
        int bit2 = (b & (1LL << i));

        if (bit1 && bit2) {
            a ^= (1LL << i);
            b ^= (1LL << i);
        }

        if (bit1 != bit2) {
            assert(bit1 == 0);

            cerr << a << " " << b << endl;

            int pw = (1LL << i);
            int ans = pw - a;

            int min1 = a, max1 = pw;
            int min2 = 0, max2 = 1;

            b ^= pw; b -= 1;
            if (b == -1) {
                cout << ans << endl;
                return 0;
            }
            while (b) {max2 = max2 * 2; b /= 2;}

            cerr << min1 << " " << max1 << " " << min2 << " " << max2 << endl;
            ans += max1 - min1;
            ans += max2 - min2;
            ans -= max(0LL, max2 - min1);

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

    assert(false);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main(){
    int H, W, h, w; cin >> H >> W >> h >> w;
    vector<vector<long long>> a(H, vector<long long>(W, 0));
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(i%h == h-1 && j%w == w-1){
                a[i][j] = -1000000000;
            } else if(i%h == 0 && j%w == 0){
                a[i][j] = 999999999 - h * w + 2;
            } else {
                a[i][j] = 1;
            }
        }
    }
    long long sum = 0;
    for(auto& v : a) sum = accumulate(v.begin(), v.end(), sum);
    if(sum > 0){
        cout << "Yes" << endl;
        for(auto& v : a){
            for(auto& t : v) cout << t << " ";
            cout << endl;
        }
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 4864
#include <stdio.h>
	int main(void){
		int W,H,i,j;
		while(1){
			scanf("%d %d",&H,&W);
			if(W==0 && H==0){
				break;
			}
			for(i=0;i<H;i++){
				for(j=0;j<W;j++){
					if(i==0 || i==H-1 ||j==0 || j==W-1){
						printf("#");
					}else{
						printf(".");
					}
				}
				printf("\n");
			}
			printf("\n");
		}
	return 0;
}

Measured memory_bytes: 572
#include <stdio.h>
#include <math.h>
#define N 10000

int isPrime(int);

int main(){
  int i,count=0,n,A[N];

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

  for(i=0;i<n;i++){
    if(isPrime(A[i]) == 1)
       count++;
  }
  printf("%d\n",count);

  return 0;
}

int isPrime(int x){
  int i=3;

  if(x == 2) return 1;
  if(x < 2 || x%2 == 0) return 0;

  while(i <= sqrt(x)){
    if(x%i == 0) return 0;
    i = i+2;
  }
    
  return 1;
}


Measured memory_bytes: 2084
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello{
    public static void Main(){
        var input = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var N = input[0];
        var M = input[1];
        var foods = new List<long>();
        for(var i = 0;i < M;i++){
            foods.Add(0);
        }
        
        for(var i = 0;i < N;i++){
            var K = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            for(long j = 1;j <= K[0];j++){
                foods[K[j] - 1]++;
            }
        }
        
        var ans = foods.Count(x => x == N);
        Console.WriteLine(ans);
    }
}


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

int main(){
int x; cin >> x;
if(x>=400 && x < 600) cout << 8 << endl;
if(x>=600 && x < 800) cout << 7 << endl;
if(x>=800 && x < 1000) cout << 6 << endl;
if(x>=1000 && x < 1200) cout << 5 << endl;
if(x>=1200 && x < 1400) cout << 4 << endl;
if(x>=1400 && x < 1600) cout << 3 << endl;
if(x>=1600 && x < 1800) cout << 2 << endl;
if(x>=1800 && x < 2000) cout << 1 << endl;

return 0;
}

Measured memory_bytes: 3632
#include<iostream>
using namespace std;int h,w,m,D[1401][1401]={m=0},f,i=0;main(){cin>>h>>w;for(;i<h*w;i++)cin>>f,m=max(m,D[i/w+1][i%w+1]=(min(D[i/w][i%w],min(D[i/w+1][i%w],D[i/w][i%w+1]))+1)*(!f));cout<<m*m<<endl;}


Measured memory_bytes: 10700
open System
let R T = stdin.ReadLine()|> T
let RS T = stdin.ReadLine().Split()|>Array.map T
let Mod = (1e9|>int64)+7L
[<EntryPoint>]
let main argv =
    let a,b = RS int |>fun c -> (min c.[0] c.[1]),(max c.[0] c.[1])
    for i in [0..b-1] do
        stdout.Write a
    stdout.WriteLine ""
    0


Measured memory_bytes: 11348
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
#define LL long long
using namespace std;
LL a,b,c;
inline LL read(){
	char ch=getchar(); LL x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	a=read(); b=read(); c=read();
	for(LL i=1;i<=c;i++)
	{
		if(i&1)
		{
			if(a&1) a--;
			int tt=a/2;
			a=tt; b+=tt;
		}
		else {
			if(b&1) b--;
			int tt=b/2;
			a+=tt; b=tt;
		}
	}
	printf("%lld %lld\n",a,b);
//	fclose(stdin); fclose(stdout);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int d = Integer.parseInt(sc.next());
        int t = Integer.parseInt(sc.next());
        int s = Integer.parseInt(sc.next());
        if (d <= t * s) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35580
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
		double speed = scanner.nextDouble();
		double time = speed / 9.8;
		double height = 4.9 * Math.pow(time, 2);
		int floor = (int)((height+5)/5)+1;
		System.out.println(floor);
		}
	}
}

Measured memory_bytes: 18592
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
    IOS;
    int n;
    cin >> n;
    int d,x;
    cin >> d >> x;
    vector<int> vec;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    int ans = x;
    for(int i=0; i<n; i++){
        int temp = (d-1)/vec[i]+1;
        ans+=temp;
    }
    cout << ans <<endl;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 

 
int main() {
    int n, k, x, counter = 0;
    cin >> n >> k;
    int ppl[n];
    int d[k];
    vector<int> a;

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

    for (int i = 0; i < k; i++)
    {
        cin >> d[i];
        for (int j = 0; j < d[i]; j++)
        {
            cin >> x;
            a.push_back(x);
            ppl[x-1]++;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (ppl[i] == 0)
        {
            counter++;
        }
    }

    cout << counter;
    
    return 0;
}

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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll n; cin >> n;
    vector<ll> c;
    vector<vector<ll>> place(200005, vector<ll>());
    rep(i, n) {
        ll tmp; cin >> tmp;
        if(i>0) if(c[c.size()-1] == tmp) continue;
        c.push_back(tmp);
    }
    
    rep(i, c.size()) {
        place[c[i]].push_back(i);
    }

    vector<ll> dp(c.size()+1, 0);
    dp[0] = 1;

    frep(i, 1, c.size()) {
        dp[i] = madd(dp[i], dp[i-1], 0);
        ll color = c[i-1];

        auto iter = lower_bound(ALL(place[color]), i-1) - place[color].begin();
        if(iter > 0 && place[color][iter-1]+1 != i-1) {
            dp[i] = madd(dp[i], dp[place[color][iter-1]+1], 0);
        }
    }

    cout << dp[c.size()] << endl;


    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

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

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 17236
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    if S[-1] == 's':
        S += 'es'
    else:
        S += 's'
    print(S)
resolve()

Measured memory_bytes: 61712
#include <iostream>
#include <math.h>
#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 W,H,N;
  cin>>W>>H>>N;
  int w0,w1,h0,h1;
  w0=0;
  w1=W;
  h0=0;
  h1=H;

  REP(i,N){
    int x,y,a;
    cin>>x>>y>>a;
    if(a==1)w0=max(x,w0);
    else if(a==2)w1=min(x,w1);
    else if(a==3)h0=max(y,h0);
    else h1=min(y,h1);
  }
  // cout<<w0<<w1<<h0<<h1<<endl;
  cout<<max(0,(w1-w0))*max(0,(h1-h0))<<endl;
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

int main(){
	ll N,K; cin>>N>>K;
	vector<ll> A(N);
	ll ans=10000000000;
	rep(i,N) cin>>A[i];
	rep(i,N-K+1){
		ll l=i,r=i+K-1;
		ans=min(ans,min(abs(A[l])+abs(A[l]-A[r]),abs(A[r])+abs(A[l]-A[r])));
	}
	cout<<ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;

class UnionFind {
  vector<int> par;
  vector<int> sizes;
  public:
  UnionFind(int n) : par(n), sizes(n, 1) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
    }
  }
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sizes[x] < sizes[y]) swap(x, y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  int size(int x) {
    return sizes[find(x)];
  }
};

void solve(long long N, std::vector<long long> x, std::vector<long long> y){
  map<long long, int> xmap;
  map<long long, int> ymap;
  UnionFind uf(N);

  for (int i = 0; i < N; i++) {
    if (!xmap.count(x[i])) {
      xmap[x[i]] = i;
    } else {
      uf.unite(i, xmap[x[i]]);
    }
    if (!ymap.count(y[i])) {
      ymap[y[i]] = i;
    } else {
      uf.unite(i, ymap[y[i]]);
    }
  }

  vector<set<int>> xlines(N);
  vector<set<int>> ylines(N);
  vector<int> usize(N, 0);

  for (int i = 0; i < N; i++) {
    xlines[uf.find(i)].insert(x[i]);
    ylines[uf.find(i)].insert(y[i]);
    usize[uf.find(i)]++;
  }

  long long ans = 0;

  for (int i = 0; i < N; i++) {
    ans += xlines[i].size() * ylines[i].size() - usize[i];
  }

  std::cout << ans << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  std::vector<long long> x(N);
  std::vector<long long> y(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&x[i]);
    scanf("%lld",&y[i]);
  }
  solve(N, std::move(x), std::move(y));
  return 0;
}


Measured memory_bytes: 23296
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<utility>
#include<queue>
#include<stdbool.h>
#include<math.h>
#include<sstream>
typedef long long ll;
#define N (1000000000+7)
using namespace std;
typedef pair<int, int> P;

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

int main(void) {
	int n, ma = -10000000, mi = 10000000, minindex = 0, maxindex = 0;
	cin >> n;
	vector<int>a(n + 1);
	vector<stringstream>s(2 * n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
		if (a[i] > ma) {
			ma = a[i];
			maxindex = i;
		}
		if (a[i] < mi) {
			mi = a[i];
			minindex = i;
		}
	}
	//最小値と最大値が同じ、つまり全部同じ
	if (ma == mi) {
		cout << 0 << endl;
		return 0;
	}
	//全て正の時,最大値を一番初めに足せばあとは順にやればいい
	if (mi >= 0) {
		int count = 0;
		int index = 0;
		while (true) {
			if (index == n)break;
			while (a[index] > a[index + 1]) {
				a[index + 1] += ma;
				count++;
				s[count] << maxindex << " " << index + 1;
			}
			index++;
			if (ma < a[index]) {
				ma = a[index];
				maxindex = index;
			}
		}
		cout << count << endl;
		for (int i = 1;i <= count;i++)cout << s[i].str() << endl;
		return 0;
	}

	if (ma <= 0) {
		int count = 0;
		int index = n;
		while (true) {
			if (index == 1)break;
			while (a[index] < a[index - 1]) {
				a[index - 1] += mi;
				count++;
				s[count] << minindex << " " << index - 1;
			}
			index--;
			if (mi > a[index]) {
				mi = a[index];
				minindex = index;
			}
		}
		cout << count << endl;
		for (int i = 1;i <= count;i++)cout << s[i].str() << endl;
		return 0;
	}
	
	if (ma < abs(mi)) {
		int index = 1, count = 0;
		while (true) {
			if (index == n + 1)break;
			while (a[index] >= 0) {
				a[index] += mi;
				count++;
				s[count] << minindex << " " << index;
			}
			index++;
		}
		index = n;
		while (true) {
			if (index == 1)break;
			while (a[index] < a[index - 1]) {
				a[index - 1] += mi;
				count++;
				s[count] << minindex << " " << index - 1;
			}
			index--;
			if (mi > a[index]) {
				mi = a[index];
				minindex = index;
			}
		}
		cout << count << endl;
		for (int i = 1;i <= count;i++)cout << s[i].str() << endl;
		return 0;
	}
	int index = 1, count = 0;
	while (true) {
		if (index == n + 1)break;
		while (a[index] <= 0) {
			a[index] += ma;
			count++;
			s[count] << maxindex << " " << index;
		}
		index++;
	}
	index = 1;
	while (true) {
		if (index == n)break;
		while (a[index] > a[index + 1]) {
			a[index + 1] += ma;
			count++;
			s[count] << maxindex << " " << index + 1;
		}
		index++;
		if (a[index] > ma) {
			ma = a[index];
			maxindex = index;
		}
	}
	cout << count << endl;
	for (int i = 1;i <= count;i++)cout << s[i].str() << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main() {
  int n,x,cnt;
  while(cin >> n >> x&&n||x) {
    cnt=0;
    for(int i=1;i<=n-2;i++){
      for(int j=i+1;j<=n-1;j++){
        for(int k=j+1;k<=n;k++){
          if(i+j+k==x) cnt++;
        }
      }
    }
    cout << cnt << endl;
  }
  return 0;
}


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

int main(){
    ll n;
    cin>>n;
    ll ans;
    ans=n*n/2-n/2;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int main()
{	
	fast
	int n,k,i;
	cin>>n>>k;
	double a[200005];
	a[0]=0;
	for(i=1;i<=n;i++)
	{	cin>>a[i];
		a[i]=(a[i]+1)/2;
		a[i]+=a[i-1];
	}
	double mx=0;
	for(i=k;i<=n;i++)
		mx=max(mx,a[i]-a[i-k]);
	printf("%0.12lf\n",mx);
	
	
}

Measured memory_bytes: 1792
import java.util.Scanner;

class Main
{
    public static void main(String args[])
    {
        Scanner s = new Scanner(System.in);
        int h = s.nextInt();
        int a = s.nextInt();
        if(h%a==0)
        {
            System.out.println(h/a);
        }
        else
        {
            int k = h/a;
            k++;
            System.out.println((k)++);
        }
    }
}

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

int main()
{
    int N;
    long int a,count=0;

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> a;
        while(a%2==0){
            count++;
            a /= 2;
        }
    }

    cout << count << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int ans = 0;
  int i;
  for(i=0;i<s.length();i++){
    if(i%2==0){
      if(s[i] == 'p')ans--;
    }else{
      if(s[i] == 'g')ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
using namespace std;
int main(void) {
	string S, T;
	cin >> S >> T;
	int count = size(T);
	int s = size(S);
	int t = size(T);
	int min = 0;
	for (int i = 0; i <= s-t; i++) {
		for (int j = 0; j < t; j++) {
			if (S[i + j] != T[j])
				min++;
		}
		if (count > min)
			count = min;
		min = 0;
	}

	cout << count << endl;

}


Measured memory_bytes: 3652
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<=ll(b);++i)
#define ALL(f,x,...) ([&](decltype((x)) xxxx) { return (f)(begin(xxxx), end(xxxx), ## __VA_ARGS__); })(x)
#define lim 1000000007ll
#define Yes(flag) cout<<((flag)? "Yes":"No");
#define YES(flag) cout<<((flag)? "YES":"NO");
#define which(flag,msg1,msg2) cout<<((flag)? msg1:msg2);

#include<bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T 
chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>T 
chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template <class T> T 
gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T 
lcm(T a, T b){return a * b / gcd(a, b);}
vector<char> 
string_to_vector_char(const string& input){vector<char> out(input.length());rep(i,input.length()){out[i]=input[i];}return out;}
map<char,int> 
count_same_elements(const vector<char>& v){map<char,int>cmap; for_each(v.begin(),v.end(),[&cmap](int x){cmap[x]++;}); return cmap; }
template<class A,class B> vector<B> 
mapf(const vector<A>& v,const function<B(A)>& func){vector<B> v_(v.size());rep(i,v.size()){ v_[i]=func(v[i]); }return v_;}
template<class A,class B> vector<B> 
adjacent_map(const vector<A>& v,const function<B(A,A)>& func){vector<B> v_(v.size()-1);rep(i,v.size()-1){ v_[i]=func(v[i+1],v[i]); }return v_;}
template<class A> bool
all_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]<1){flag=false;}; }return flag;}
template<class A> bool
any_of(const vector<A>& v){bool flag=false;rep(i,v.size()){ if(v[i]>0){flag=true; break;}; }return flag;}
template<class A> bool
none_of(const vector<A>& v){bool flag=true;rep(i,v.size()){ if(v[i]>0){flag=false;}; }return flag;}
template<class T>
void scan_vector(long long size,vector<T>& vector){
    vector.resize(size);
    for(long long i=0;i<size;++i){
        cin>>vector[i];
    }
}
// 約数列挙
template <class T>
vector< T > divisor(T n) {
    vector< T > ret;
    for(T i = 1; i * i <= n; i++) {
        if(n % i == 0) {
        ret.push_back(i);
        if(i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

int xo;
int xt;
int yo;
int yt;
void input(){
    cin>>xo>>yo>>xt>>yt;
}
void src(){
    cout<<(xt-(yt-yo))<<" ";
    cout<<(yt+(xt-xo))<<" ";
    cout<<(xo-(yt-yo))<<" ";
    cout<<(yo+(xt-xo))<<" ";
}   

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
 //   ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	ll lon, squ, tri, lle, lri, zri, zle;
	cin >> lon >> squ >> tri >> lle >> lri >> zri >> zle;
	ll tot1 = squ * 2;
	int sm = (lon & 1) + (lle & 1) + (lri & 1);
	if(lon && lle && lri && sm >= 2) tot1 += 6, lon--, lle--, lri--;
	tot1 += 4 * (lle / 2);
	tot1 += 4 * (lri / 2);
	tot1 += (lon / 2) * 4;
	cout << tot1 / 2 << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

using namespace std;

typedef long long ll;
using pii = pair<int, int>;

static const int INTINF = (2147483647);
static const ll LLINF = (9223372036854775807);
static const int MAX = 100001;
static const ll MOD = 1000000007;


//--global--//



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

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//
    
    int dp[MAX];
    dp[0] = 1;
    int a[6] = {100, 101, 102, 103, 104, 105};
    rep(i, 6){
        rep2(k, 1, 1001){
            for(int j=MAX-1; j>=0; j--){
                if(dp[j] && j + a[i]*k <= MAX){
                    dp[j+a[i]*k] = 1;
                }
            }
        }
    }

    int x;
    cin >> x;
    if(dp[x]){
        cout << "1" <<endl;
    }
    else{
        cout << "0" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 640
from collections import deque
H,W = map(int, input().split())
S = [list(input()) for _ in range(H)] # S[H][W]なのに注意
# 黒を白に変えられないので最短経路算出後に差っ引けばOK
# 早い話が迷路なので幅優先探索
whites = sum([i.count('#') for i in S])
S[0][0] = 0
goal = [H-1, W-1]
move = ((-1,0), (1,0), (0,-1), (0,1))
queue = deque()
queue.append((0,0))

while queue:
    now = queue.popleft()
    cnt = S[now[0]][now[1]] + 1
    for h,w in move:
        x,y = now[0]+h,now[1]+w
        if x < 0 or x >= H or y < 0 or y >= W:
            continue
        if S[x][y] == '.':
            S[x][y] = cnt
            queue.append((x,y))
if S[H-1][W-1] == '.':
    print(-1)
else:
    print(W*H - 1 - S[H-1][W-1] - whites)
exit(0)


Measured memory_bytes: 3316
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

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


	int N = getint();

	int A[1000001] = {};
	rep(i, N) A[getint()]++;

	if (A[1]) {
		if (A[1] == 1) co(1);
		else co(0);
		return 0;
	}
	if (A[2]) {
		int kotae = (A[2] == 1);
		for (int i = 3; i <= 500000; i += 2) {
			if (A[i]) {
				kotae += (A[i] == 1);
				for (int j = i + i; j <= 1000000; j += i) {
					A[j] = 0;
				}
			}
		}
		for (int i = 500001; i <= 1000000; i += 2) kotae += (A[i] == 1);
		co(kotae);
		return 0;
	}

	int kotae = 0;
	for (int i = 2; i <= 500000; i++) {
		if (A[i]) {
			kotae += (A[i] == 1);
			for (int j = i + i; j <= 1000000; j += i) {
				A[j] = 0;
			}
		}
	}
	for (int i = 500001; i <= 1000000; i++) kotae += (A[i] == 1);
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 7704
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int MOD = 0;

vector<vector<int> > mulMatMod(const vector<vector<int> > &A, const vector<vector<int> > &B) {
    auto n = (int)A.size(), m = (int)A[0].size(), p = (int)B[0].size();
    vector<vector<int> > res(n, vector<int>(p));
    for (int i = 0; i < n; ++i)for (int j = 0; j < p; ++j) for (int k = 0; k < m; ++k)
        res[i][j] = (int)((res[i][j] + (long long)A[i][k] * B[k][j]) % MOD);
    return res;
}

vector<vector<int> > powMatMod(vector<vector<int> > A, long long k) {
    auto n = (int)A.size();
    vector<vector<int> > res(n, vector<int>(n));
    for (int i = 0; i < n; ++i)res[i][i] = 1;
    while (k) {
        if (k % 2)res = mulMatMod(res, A);
        k /= 2;
        A = mulMatMod(A, A);
    }
    return res;
}

int digit(ll x) {
    int res = 0;
    while (x > 0) {
        res++;
        x /= 10;
    }
    return res;
}

void solve() {
    ll L, A, B;
    int M;
    cin >> L >> A >> B >> M;
    MOD = M;

    ll ans = 0;
    for (ll i = 0; i < L;) {
        int d = digit(A + B * i);
        ll pw = 1;
        rep(j, d)pw *= 10;
        ll j = (pw - A + B - 1) / B;
        smin(j, L);
        assert(j > i);
        vector<vi> C(3, vi(3));
        C[0][0] = C[0][2] = C[1][0] = C[2][2] = 1;
        C[1][1] = (int)(pw%M);
        auto D = powMatMod(C, j - i);
        ll x = (A + B * i) % MOD;
        ans = D[1][0] * x+ D[1][1] * ans + D[1][2] * (B%M);
        ans %= MOD;
        i = j;
    }
    cout << ans << endl;
}

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

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

int main() {
    int n;
    cin >> n;
    vector<int> dp(50);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n] << endl;
}



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

using namespace std;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, k;
int a[N];
bool No = 0;
int ans = 0;
map < pair < ll, int > , int > was;

int f[N];
void upd (int p, int x) {
	for (; p < N; p |= (p + 1))
		f[p] += x;
}

int get (int r) {
	int res = 0;
	while (r > 0) {
		res += f[r];
		r = (r & (r + 1)) - 1;
	}
	return res;
}

int main () {
   SpeedForce;
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	ll res = 0;
	int last = 0;
	for (int i = 1, j = 1; j <= n; i ++) {
		while (j - i < k && j <= n) {
			int add = j - i - get(a[j]);
			res += add;
			if (add > 0)
				last = j;

			upd(a[j], 1);
			j++;
		}
		if (res > 0) {
		//	cout << i << ' ' << j << " :range" << ' ' << res << ' ' << last << '\n';
			was[mp(res, last)] = 1;
		}
		if (res == 0) No = 1;

		upd(a[i], -1);
		int add = get(a[i]);
		res -= add;
		 
	}
	cout << sz(was) + No;
   return Accepted;
}

// B...a

Measured memory_bytes: 15616
#include<bits/stdc++.h>
using namespace std;
int main(){
  long n,a,b,head=0,tail=1e+10;
  cin>>n>>a>>b;
  vector<long> h(n);
  for(long i=0;i<n;++i)cin>>h[i];
  
  long t,sum;
  while(tail-head>1){
    cerr<<"["<<head<<" - "<<tail<<"]\n";
    sum=0;
    t=(head+tail)/2;
    for(long i=0;i<n;++i){
      if(h[i]>b*t){
        long damt=(h[i]-b*t)/(a-b);
        if((h[i]-b*t)>damt*(a-b))damt++;
        sum+=damt;
      }
    }
    if(sum>t)head=t;
    else tail=t;
  }
  cerr<<"["<<head<<" - "<<tail<<"]\n";
  sum=0;
  t=head;
  for(long i=0;i<n;++i){
    if(h[i]>b*t){
      long damt=(h[i]-b*t)/(a-b);
      if((h[i]-b*t)>damt*(a-b))damt++;
      sum+=damt;
    }
  }
  if(sum>t)t=tail;
  else t=head;
  cout<<t;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<62;


int main(){
    int n,k;
    cin >> n >> k;
    if(n%k==0) puts("0");
    else puts("1");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <tuple>

using namespace std;

#define INF 100000000;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
#define eps 1.0e-14;

int main(){
    long double A,B;
    cin >> A >> B;
    ll ans = floor( A * B );
    cout << ans << endl;
}

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

using namespace std;

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

int main() {
  int N;
  cin >> N;
  int r = 1000;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int s;
    cin >> s;
    ans += s;
    if (s % 10 != 0) chmin(r, s);
  }
  if (ans % 10 == 0) {
    if (r == 1000) {
      ans = 0;
    } else {
      ans -= r;
    }
  }
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


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

int main()
{
    int x;
    cin >> x;
    if (x == 0)
    {
        cout << 1 << endl;
    }
    if (x == 1)
    {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
N = int(input())


def f(L, m):
    l = len(L)
    if l == N:
        print(''.join(list(map(lambda i: chr(i + 96), L))))
        return
    for d in range(1, min(l + 1, m + 1) + 1):
        f(L + [d], max(m, d))


f([1], 1)


Measured memory_bytes: 4412
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("fma,avx,avx2")

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
const int maxs = 1e6 + 10;
const unsigned int q1 = 179;
const unsigned int q2 = 239;

int last = 0;
map<long long, int> hh;
map<long long, int> mp;
vector<char> a;
long long res[2 * maxs][26];
int cnt[26];
long long h[maxn];

int get_id(long long hsh) {
    if (hh.find(hsh) != hh.end()) {
        return hh[hsh];
    }
    hh[hsh] = ++last;
    return last;
}

long long get_hash(unsigned int h1, unsigned int h2) {
    return (h1 * 1ll << 32) | h2;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        a[i] = s[0];
        memset(cnt, 0, sizeof cnt);
        for (int j = 0; j < sz(s); j++) {
            cnt[s[j] - 'a']++;
        }
        unsigned int h1 = 0, h2 = 0;
        for (int j = sz(s); j >= 0; j--) {
            if (j == sz(s)) {
                int id = get_id(get_hash(h1, h2));
                for (int k = 0; k < 26; k++) {
                    if (cnt[k]) {
                        res[id][k]++;
                    }
                }
            } else {
                long long tmp = get_hash(h1, h2);
                cnt[s[j] - 'a']--;
                h1 = h1 * q1 + s[j];
                h2 = h2 * q2 + s[j];
                int id = get_id(get_hash(h1, h2));
                if (j == 0) {
                    mp[get_hash(h1, h2)]++;
                    h[i] = tmp;
                }
                for (int k = 0; k < 26; k++) {
                    if (cnt[k]) {
                        res[id][k]++;
                    }
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int id = get_id(h[i]);
        ans += res[id][a[i] - 'a'];
    }
    for (auto &el : mp) {
        ans -= el.y * (el.y + 1) / 2;
    }
    cout << ans << "\n";


    return 0;
}


Measured memory_bytes: 268928
import numpy as np

n = int(input())
arr = []

for i in range(n):
    arr.append(list(map(int, input().split(' '))))

arr = np.array(arr)
arr = arr[np.argsort(np.sum(arr, axis=1))[::-1]]
takahashi = np.sum(arr[::2, 0], axis=0)
aoki = np.sum(arr[1::2, 1], axis=0)

print(takahashi - aoki)


Measured memory_bytes: 37844
import java.util.Scanner;

public class Main {

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

		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    long ans = a;
		    int cnt = 1;
		    while(b-ans>0) {
		    	cnt += 1;
		    	ans += a-1;
		    }
		    if(b==1) {
		    	cnt = 0;
		    }
		    System.out.println(cnt);


		    sc.close();
	}
}


Measured memory_bytes: 23892
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#define pb push_back
#define mod 1000000007
using namespace std;
typedef long long int ll;

int main(void){
  string s;
  cin>>s;
  cout<<s.substr(0,s.size()-8)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
typedef pair<int,int> pii;
#define mp make_pair
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=100010;
int n,a[N],o[N],v[N],c[N<<1],s[N];
ll all;
int lowbit(int x){return x&(-x);}
void Add(int x,int d){while(x<=(n<<1)){c[x]+=d;x+=lowbit(x);}}
int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
bool check(int mid)
{
	for(int i=1;i<=n;i++)v[i]=(a[i]>=o[mid])?1:-1;
	ll ret=0;
	for(int i=1;i<=n;i++)s[i]=s[i-1]+v[i],ret+=(s[i]<0);
	memset(c,0,sizeof(c));
	for(int i=n;i;i--)
	{
		ret+=query(s[i]+n-1);
		Add(s[i]+n,1);
	}
	return ret*2<=all;
}
int main()
{
	n=gi();all=1ll*n*(n+1)/2;
	for(int i=1;i<=n;i++)a[i]=o[i]=gi();sort(o+1,o+n+1);int tot=unique(o+1,o+n+1)-o-1;
	int l=1,r=tot,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)){ans=mid;l=mid+1;}
		else r=mid-1;
	}
	printf("%d\n",o[ans]);
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  ll ans = 0;
  vl d(n, 0);
  rep(i, n - 1) rep2(j, i + 1, n) {
    ll now = min(j - i, abs(x - i) + abs(y - j) + 1);
    d[now]++;
  }
  rep2(i, 1, n) cout << d[i] << '\n';
}

Measured memory_bytes: 256
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

int main()
{
    ll N;
    cin >> N;
    set<ll> s;
    rep(i, N) {
        ll a;
        cin >> a;
        s.insert(a);
    }
    vector<ll> v;
    std::copy(s.begin(), s.end(), std::back_inserter(v));
    sort(all(v));
    ll sum = 0;
    rep(i, v.size()-1) sum += v[i+1] - v[i]; 
    print(sum);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){
  int k;
  string s;

  cin >> k;
  cin >> s;

  int size = s.size();

  if(size <= k) cout << s << endl;
  else {
    for(int i = 0; i < k; i++){
      cout << s[i];
    }
    cout << "..." << endl;
  }


  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
#define acc(v) accumulate(v.begin(), v.end(), 0)
#define cinv(n,v) rep(i,n) cin >> v[i]
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
int x_pos[4] = {1,0,-1,0}, y_pos[4] = {0,1,0,-1};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

char upper(char c){
	return c-0x20;
}

char lower(char c){
	return c+0x20;
}

void unique_vector(vector<int>& v){
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//ユークリッドの互除法
//最大公約数
ll gcd(ll x, ll y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

//最小公倍数
ll lcm(ll x, ll y){
	ll g = gcd(x,y);
	return x/g*y;
}

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}
int main() {
    ll n;cin>>n;
    rep(i,3501){
        rep(j,3501){
            ll a = i*j*n;
            ll b = 4*i*j - n*i - n*j;
            if(a>0 && b > 0 && a%b==0){
                int c = a / b;
                cout << i << ' ' << j << ' ' << c << endl;
                return 0;
            }
        }
    }
}



Measured memory_bytes: 256