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 std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef long double ld;

#define llset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define en '\n'
#define S second
#define F first
#define pll pair<ll,ll>
#define PB push_back

const ll N = 1e6+7;
ll mod = 1e9+7;
#define calncr for(int i=1  ;i<=1e6;i++) fac[i] = (fac[i-1]*i)%mod;
ll fac[N] = {0};

ll gen_base(const ll before, const ll after) {
    auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt_rand(seed);
    int base = std::uniform_int_distribution<ll>(before+1, after)(mt_rand);
    return base % 2 == 0 ? base-1 : base;
}

ll pow(ll a,ll b)
{
    if(!b)
        return 1;
    ll p = pow(a,b/2);
    if(b%2)
        return (a*((p*p)%mod))%mod;
    else
        return (p*p)%mod;
}

ll modInv(ll a)
{
    //cout<<a<<" "<<mod<<en;
    return pow(a%mod,mod-2);
}

ll nCr(ll n,ll r)
{
    return (fac[n]*modInv((fac[r]*fac[n-r])%mod))%mod;
}

ll hashf(ll r,ll x,ll mod)
{
    return (x+r)%mod;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    fac[0] = 1;
    calncr;
    ll n,k;
    cin>>n>>k;
    ll arr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    ll l=1,r=1e9+5, ans=1e9+5;
    while(l<=r){
        ll mid = (l+r)/2;
        ll cnt=0;
        for(ll i=0;i<n;i++){
            cnt+=arr[i]/mid;
            if(arr[i]%mid==0)
                cnt--;
        }
        //cout<<l<<" "<<r<<" "<<mid<<" "<<cnt<<en;
        if(cnt<=k){
            ans = min(ans,mid);
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }
    cout<<ans<<en;
}


Measured memory_bytes: 12980
#include <stdio.h>
#include <stdlib.h>

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

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

    if (abs(x-a) < abs(x-b)) {
	puts("A");
    }
    else {
	puts("B");
    }
    return 0;
}


Measured memory_bytes: 128
//人bが人aに初めて負けたとき、aからbに辺を張ったグラフGを考える.
//a -> {b_1, b_2, …, b_k}と辺が張ってあるとき、b_i(1≦i≦k)についてトーナメントの深さを最小化し、その値をv(b_i)とおく。
//v(b_i)の大きい順にbを並べ、v(b_i + i)のmaxを取ったものがv(a)になりそうだ。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int n;
vector<int> et[100000];
int dp[100000];

int dfs(int v) {
	if (dp[v] != -1) return dp[v];
	
	int ret = 0;
	vector<int> vec;
	for (int i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		int res = dfs(nv);
		vec.push_back(res);
	}
	sort(vec.begin(), vec.end(), greater<int>());
	
	for (int i = 0; i < vec.size(); i++) {
		int res = vec[i] + i + 1;
		ret = max(ret, res);
	}
	return dp[v] = ret;
}

int main() {
	int i;
	
	cin >> n;
	for (i = 1; i < n; i++) {
		int a;
		cin >> a; a--;
		et[a].push_back(i);
	}
	
	for (i = 0; i < n; i++) dp[i] = -1;
	
	int ans = 0;
	for (i = 0; i < n; i++) {
		int res = dfs(i);
		ans = max(ans, res);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }
    constexpr int INF = 1'000'000'000;
    vector<int> dp(N, INF);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        if (i + 1 < N) {
            dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        }
        if (i + 2 < N) {
            dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
        }
    }
    cout << dp[N - 1] << "\n";

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
mt19937 rnd;


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

    ll a, b, n;
    cin >> a >> b >> n;
    ll r = min(b - 1, n);
    cout << a * r / b << "\n";

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


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)
using namespace std;


int main() {
  int n, prev, now, flag = 0;
  cin >> n;
  prev = n % 10;
  n /= 10;
  rep(i, 3) {
    now = n % 10;
    n /= 10;
    if (prev == now) flag = 1;
    prev = now;
  }
  if (flag == 1) cout << "Bad" << endl;
  else cout << "Good" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int a, b, c;
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a >> b >> c;
    a = a * a;
    b = b * b;
    c = c * c;
    if ((a == b + c) || (b == a + c) || (c == a + b)) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define llong long long
#define INF (__INT32_MAX__ / 2)

using namespace std;

int main(int argc, char **argv) {
    int n;
    scanf("%d", &n);

    int res = 0;
    int highest = -INF;
    for(int i = 0; i < n; ++i) {
        int h;
        scanf("%d", &h);
        if(h >= highest) ++res;
        highest = max(highest, h);
    }

    printf("%d\n", res);
}

Measured memory_bytes: 128
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String s = sc.next();

        boolean isCorrect = true;
        if (s.charAt(a) != '-') isCorrect = false;

        for (int i = 0; i < a + b; i++) {
            if (!isCorrect) break;
            if (i == a) continue;
            if (s.charAt(i) == '-') isCorrect = false;
        }

        if (isCorrect) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define inf 100000000000000000
#define mod 1000000007
#define MAX 200005
#define pb push_back
#define vit vector<int>::iterator
typedef pair<lint,lint> pii;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    lint n,sum=0,ans=0;
    cin>>n;
    for(lint i=1;i<=n;i++){
        lint a;
        cin>>a;
        ans=(ans+(sum*a)%mod)%mod;
        sum=(sum+a)%mod;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <bitset>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll n;
  cin>>n;

  bitset<61> bit(n);
  ll dp[62][3];
  for(int i=0;i<=61;i++) for(int j=0;j<3;j++) dp[i][j]=0;
  dp[61][0]=1;

  for(int i=60;i>=0;i--){
    if(bit[i]){
      dp[i][0]=dp[i+1][0];
      dp[i][1]=(dp[i+1][0]+dp[i+1][1])%MOD;
      dp[i][2]=(2*dp[i+1][1]+3*dp[i+1][2])%MOD;
    }else{
      dp[i][0]=(dp[i+1][0]+dp[i+1][1])%MOD;
      dp[i][1]=dp[i+1][1];
      dp[i][2]=(dp[i+1][1]+3*dp[i+1][2])%MOD;
    }
  }

  cout<<((dp[0][0]+dp[0][1])%MOD+dp[0][2])%MOD<<endl;
  return 0;
}


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

int main()
{
    int n = 0,l = 0;
    cin >> n >> l;
    int t = 0,c = 0;
    bool judge = false;
    int anw_t = l,anw_c = 1002;
    for(int i = 0;i < n;i++)
    {
        cin >> c >> t;
        if(t <= l)
        {
            judge = true;
            if(anw_c > c)
            {
                anw_c = c;
            }
        }
    }
    if(!judge)
    {
        cout << "TLE";
        return 0;
    }
    cout << anw_c;
    return 0;
}


Measured memory_bytes: 256
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define ifYN(x) cout<<(x?"Yes":"No")<<"\n" 
#define dcml(n) fixed<<setprecision(n)

 
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; } 
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; } 
ll modPow(ll x,ll n,ll mod=MOD){ 
    return (!n?1:!n%2?modPow(x*x,n/2,mod)%mod:x%mod*modPow(x,n-1,mod)%mod); 
} 
using namespace std;
//-------------------------------------------
typedef pair<ll,ll> P;
int main(void){
    ll N;cin>>N;
    ll H[N];REP(i,N)cin>>H[i];

    ll cnt=0,ans=0;
    REP(i,N-1){
        if(H[i]>=H[i+1]){
            cnt++;
        }
        else{
            ans=max(cnt,ans);
            cnt=0;
        }
        if(i==N-2)ans=max(cnt,ans);
    }
    cout<<ans<<"\n";
}




Measured memory_bytes: 1024
#include<iostream>

using namespace std;



int main()
{
	int N;
	int *a;
	int counter = 0;
	bool end = false;
	cin >> N;

	a = new int[N];

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

	while(true)
	{
		for(int i=0;i<N;i++)
		{
			if(a[i]%2==1)
			{
				end = true;
			}
			else
			{
				a[i] = a[i]/2;
			}
		}

		if(end)break;

		counter++;
	}

	cout << counter << endl;

	delete(a);

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>

using namespace std;

int main() {
string a;
cin >> a;
for(int i=0;i<5;i++){
  cout << a[i];
}
cout << " ";
for(int i=0;i<7;i++){
  cout << a[6+i];
}
cout << " ";
for(int i=0;i<5;i++){
cout << a[14+i];
}
cout << endl;


  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
    int n,m,k,i,sum=0;
    scanf("%d%d%d",&n,&m,&k);
    for(i=n;i>=1;i=i-1)
    {
        if(n%i==0&&m%i==0) sum++;
        if(sum==k) break;
    }
    printf("%d\n",i);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int main()
{
    string S; cin >> S;
    ll K; cin >> K;
    int N = S.size();
    int l, n = 1, m = 1;
    ll ans = 0;
    int i = 0;
    bool flag = false;
    while (i + 1 <= N - 1 && S[i] == S[i + 1])
    {
        n++;
        i++;
        if (i == N - 1) flag = true;
    }   

    int j = N - 1;
    while (j - 1 >= 0 && S[j] == S[j - 1])
    {
        m++;
        j--;
    }

    if (flag || N == 1) cout << N * K / 2 << endl;
    else
    {
        if (S[0] == S[N - 1]) ans += (n + m) / 2 * (K - 1) + n / 2 + m / 2;
        else ans += n / 2 * K + m / 2 * K;
        int k = i;
        while (k + 1 <= j)
        {
            l = 1;
            while (S[k] == S[k + 1])
            {
                l++;
                k++;
                if (k + 1 >= j) break;
            }
            ans += l / 2 * K;
            k++;
        }
        
        cout << ans << endl;
        
    }
}

Measured memory_bytes: 256
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, K = ZZ()
    C = [input() for _ in range(H)]
    atode = collections.deque()
    last = -1
    cakeId = 0
    output = [[0] * W for _ in range(H)]

    for i in range(H):
        if not '#' in C[i]:
            atode.append(i)
            continue
        ichigo = []
        last = i
        for j in range(W):
            if C[i][j] == '#': ichigo.append(j)
        itr = 0
        for j in ichigo:
            cakeId += 1
            while itr <= j:
                output[i][itr] = cakeId
                itr += 1
        while itr < W:
            output[i][itr] = cakeId
            itr += 1
        while atode:
            j = atode.popleft()
            for k in range(W): output[j][k] = output[i][k]
    while atode:
        j = atode.popleft()
        for k in range(W): output[j][k] = output[last][k]

    for i in range(H): print(*output[i])

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 7880
#include <iostream>
#define int long long
using namespace std;

int N, T, Q;
int A[100001], D[100001];
int X[1001];
int P[100001];	//P[i] = ???i???????????????

signed main()
{
	int i, j;
	
	cin >> N >> T >> Q;
	for( i = 1; i <= N; i++ ){
		cin >> A[i] >> D[i];
	}
	for( i = 1; i <= Q; i++ ){
		cin >> X[i];
	}
	
	for( i = N; i >= 1; i-- ){
		if( D[i] == 2 )
			continue;
		//????????????????????????????????????
		if( i == N )
			P[i] = A[i] + T;
		else if( D[i + 1] == 2 )
			P[i] = min(A[i] + T, (A[i] + A[i + 1]) / 2);
		else
			P[i] = min(A[i] + T, P[i + 1]);
	}
	for( i = 1; i <= N; i++ ){
		if( D[i] == 1 )
			continue;
		//????????????????????????????????????
		if( i == 1 )
			P[i] = A[i] - T;
		else if( D[i - 1] == 1 )
			P[i] = max(A[i] - T, (A[i - 1] + A[i]) / 2);
		else
			P[i] = max(A[i] - T, P[i - 1]);
	}
	
	for( i = 1; i <= Q; i++ ){
		cout << P[X[i]] << endl;
	}
	return 0;
}

Measured memory_bytes: 3508
#include<iostream>
using namespace std;
#define lli long long 
int main(){
  lli h,n;
  cin>>h>>n;
  lli a[n],sum=0;
  for(lli i=0;i<n;i++){
    cin>>a[i];
    sum+=a[i];
  }
  if(sum>=h)
    cout<<"Yes";
  else
    cout<<"No";
  return 0;
}

Measured memory_bytes: 1024
# https://atcoder.jp/contests/abc090/tasks/abc090_b
a, b = map(int, input().split())

ans = 0
for i in range(a, b + 1):
    num = str(i)
    h = 0
    t = len(num) - 1
    while h <= t:
        if num[h] == num[t]:
            h += 1
            t -= 1
        else:
            break
    else:
        ans += 1
print(ans)

Measured memory_bytes: 39536
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))

#  めぐる式二分探索で実装

def calc(x):
    count = 0
    for a in A:
        count += (a - 1) // x

    return count <= K

ok = 10 ** 9
ng = 0

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    
    if calc(mid):
        ok = mid
    else:
        ng = mid

print(ok)


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

evi=[[] for _ in range(N)]

for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        x-=1
        evi[i].append((x,y))

ans=0

for i in range(2**N):
    cnt=0
    f=True
    for j in range(N):
        if (i>>j)&1:
            cnt+=1
            for x,y in evi[j]:
                if (i>>x)&1 and y==0:
                    f=False
                    break
                elif (not (i>>x)&1) and y==1:
                    f=False
                    break
        if not f:
            break
    if f:
        ans=max(ans,cnt)

print(ans) 



Measured memory_bytes: 3064
#include<iostream>
using namespace std;
#include<string>
#define REP(i,a,b) \
for(int i=a; i<b; i++)
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long int
typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end();i++)
 
int main()
{
	int n;
	cin >> n;
	int count = 0;
	int num = n;
	if(num == 0){cout << "Yes"; return 0;}
	while(num != 0)
	{
		count = count + num%10;
		num = num/10;
	}
	if(n%count == 0)cout << "Yes";
	else cout << "No";
}


Measured memory_bytes: 256
#include<cstdio>

int n,m,ans;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=n;i<=m;i++)
	{
		if((i/10000==i%10)&&((i/1000%10)==i%100/10))ans++;
	}
	printf("%d",ans);
	return 0;
}

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

int main() {
  int N,x,sum;
  cin>>N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  
  for(int j=0;j<N;j++){
    for (int i = 1+x; i < N; i++) {
      sum+=d.at(x)*d.at(i);
    }
    x++;
  }
  
  cout<<sum<<endl;

  

}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N;

int main() {
    //cout.precision(10);
    cin >> N;
    if(N == 0) {
        cout << 0 << endl;
        return 0;
    }
    ll val = 1;
    vector<int> ans;
    while(N != 0) {
        //cerr << N << " " << val << endl;
        if((abs(N) % ((2 * abs(val))) != 0)) {
            ans.push_back(1);
            N -= val;
        } else {
            ans.push_back(0);
        }
        val *= -2;
    }
    for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
dp=[0]*(n+1)
for i in range(n+1):
  t=i
  count=0
  while t>0:
    count+=t%6
    t//=6
  t=n-i
  while t>0:
    count+=t%9
    t//=9
  dp[i]=count
print(min(dp))

Measured memory_bytes: 68172
#include<stdio.h>
#include <string.h>

int main(void)
{
  char s[100000];
  int n, i;
  scanf("%d", &n);
  scanf("%s", s);
  i = 0;
  while(s[i] != '\0'){
    s[i] += n;
    if(s[i] > 'Z'){
      s[i] -= 26;
    }
    i++;
  }
      
  printf("%s\n", s );

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
using namespace std;
ll dp[3005][3005];
int v[3005][3005];
int a[3005];
int n;
ll rec(int l , int r){
    if(v[l][r] == 1)return dp[l][r];
    v[l][r] = 1;
    if(l == r){dp[l][r] = a[l];}
    else{dp[l][r] = max(a[l] - rec(l+1,r) , a[r] - rec(l,r-1));}
    return dp[l][r];
}
int main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    for(int i = 1 ; i <=n; i++){
        cin >> a[i];
    }
    cout << rec(1,n) << endl;

}


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

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

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

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

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

#define lf double

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M,D; cin>>N>>M>>D;
    lf ans = (lf)(N-D)*(M-1)/(N*N);
    if (D>0) ans*=2;
    cout<<setp(12);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3732
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#define DEBUG(x) std::cout << '>' << #x << ':' << x << '\n';
#define PRINTVEC(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i] << ' '; std::cout << '\n';
#define PRINTP(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i].first << ' ' << x[i].second << '\n'; std::cout << '\n';
#define io std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);   
const int INF = 1<<29;
typedef long long ll;



int main()
{
	io;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout);  
    #endif

    int k,n;
    std::cin >> k >> n;
    std::vector<int> v(n);
    for (int &it : v) std::cin >> it;
    int ans = v[n-1] - v[0];
    for (int i = 1; i < n; i++) {
        ans = std::min(ans, k - v[i] + v[i-1]);
    }
    std::cout << ans;


    #ifndef ONLINE_JUDGE   
    //std::cout << '\n' << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
    #endif
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
using namespace std;
int main(){
        int a[4];
        int x,y,z;
        cin >>x;
        a[0]=(x/1000);
        x=x%1000;
        a[1]=(x/100);
        x=x%100;
        a[2]=(x/10);
        x=x%10;
        a[3]=x;
        if(a[0]+a[1]+a[2]+a[3]==7) {
                cout << a[0] << "+" << a[1] <<"+" << a[2] << "+" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]+a[1]-a[2]+a[3]==7) {
                cout << a[0] << "+" << a[1] <<"-" << a[2] << "+" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]+a[1]+a[2]-a[3]==7) {
                cout << a[0] << "+" << a[1] <<"+" << a[2] << "-" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]-a[1]+a[2]+a[3]==7) {
                cout << a[0] << "-" << a[1] <<"+" << a[2] << "+" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]-a[1]-a[2]+a[3]==7) {
                cout << a[0] << "-" << a[1] <<"-" << a[2] << "+" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]+a[1]-a[2]-a[3]==7) {
                cout << a[0] << "+" << a[1] <<"-" << a[2] << "-" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]-a[1]+a[2]-a[3]==7) {
                cout << a[0] << "-" << a[1] <<"+" << a[2] << "-" <<a[3] <<"=7"<< endl;
        }
        else if(a[0]-a[1]-a[2]-a[3]==7) {
                cout << a[0] << "-" << a[1] <<"-" << a[2] << "-" <<a[3] <<"=7"<< endl;
        }
}


Measured memory_bytes: 256
#include <cstdio>

int x, y;

int abs2(int v)
{
	if(v >= 0)
		return v;
	else
		return -v;
}

int main()
{
	scanf("%d%d", &x, &y);
	int res = 0;
	if(abs2(x) == abs2(y) )
		res = 1;
	else if(abs2(x) < abs2(y) ){
		if(x<0){
			res ++;
		}
		res += abs2(y) - abs2(x);
		if(y < 0)
			res ++;
	}
	else{
		if(x > 0)
			res ++;
		res += abs2(x) - abs2(y);
		if(y > 0)
			res ++;
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
 
int main(){
  int h,w;
  cin >> h >> w;
  char c[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout << c[i][j];
      if(j==w-1)
        cout << endl; 
    }
    for(int j=0;j<w;j++){
      cout << c[i][j];
      if(j==w-1)
        cout << endl; 
    }
  }
}

Measured memory_bytes: 256
s = input()
list_s = list(s)
len_s = len(list_s)
check = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(26):
    if check[i] not in list_s:
        print(s + check[i])
        exit()
for i in range(1, len_s + 1):
    memo = list_s.pop(len_s - i)
    for j in range(check.index(memo) + 1, 26):
        if check[j] not in list_s:
            print(s[:26 - i] + check[j])
            exit()
print(-1)


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

int main(){
  	string s,t;
	cin >> s >> t;
    int ans = 0;
  	for(int i=0; i < s.size(); i++){
    	if (s.at(i) == t.at(i)){
        	ans++;
        }
    }
        
    cout << ans << endl;
}


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

typedef unsigned long long ull;
typedef long long ll;

const int INF = 1001001001;
const ll MOD = 1e9 + 7;

using namespace std;
using P = pair<int,int>;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

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

  int a[n];
  rep(i, n) {
      cin >> a[i];
  }
  
  bool colors[8] = {false};
  int count = 0; int count_min = 0; int count_max = 0;
  rep(i, n) {
      if (1<=a[i] && a[i]<=399) colors[0] = true;
      else if (400<=a[i] && a[i]<=799) colors[1] = true;
      else if (800<=a[i] && a[i]<=1199) colors[2] = true;
      else if (1200<=a[i] && a[i]<=1599) colors[3] = true;
      else if (1600<=a[i] && a[i]<=1999) colors[4] = true;
      else if (2000<=a[i] && a[i]<=2399) colors[5] = true;
      else if (2400<=a[i] && a[i]<=2799) colors[6] = true;
      else if (2800<=a[i] && a[i]<=3199) colors[7] = true;
      else { count_max++; }
  }

  rep(i, 8) {
      if (colors[i]) count++;
  }
  if (count == 0) count_min = 1;
  cout << count+count_min << " " << count+count_max << endl;
  
  return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
lr_lst = [list(map(int,input().split())) for _ in range(m)]

min_number = 1
max_number = n
for i in range(m):
    low = lr_lst[i][0]
    upper = lr_lst[i][1]

    min_number = max(min_number, low)
    max_number = min(max_number, upper)

answer = max_number - min_number + 1

if answer < 0:
    answer = 0

print(answer)

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

n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))

temp = [0]*n

for i in range(n):
    temp[i] = t - h[i] * 0.006

minlen = 10000
minnum = -1

for i in range(n):
    len = abs(a - temp[i])
    if minlen > len:
        minlen = len
        minnum = i + 1

print(minnum)


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//typedef
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//conversion
inline LL toLong(string s) {LL v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//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) LL((a).size())
#define EACH(i,c) for(auto 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(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

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

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

#define PUTS(x) cout << (x) << endl;

LL gcd(LL m,LL n){
    if(m<n) swap(m,n);
    while(true){
        if(n==0) break;
        LL t = n;
        n = m%n;
        m = t;
    }
    return m;
}

bool used[1000005] = {0};

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL n;
    cin>>n;
    VL a(n);
    REP(i,n)cin>>a[i];

    LL x = a[0];
    REP(i,n-1){
        x = gcd(x, a[i+1]);
    }
    bool isSetwise = x == 1;

    bool isPairwise = true;
    REP(i,n){
        LL x = a[i];
        LL div = 2;
        while(div * div <= x){
            if(x % div == 0){
                do{
                    x /= div;
                }while(x % div == 0);
                if(used[div]){
                    isPairwise = false;
                    goto END;
                }
                else{
                    used[div] = true;
                }
            }
            div++;
        }

        if(x == 1)continue;
        if(used[x]){
            isPairwise = false;
            goto END;
        }
        else{
            used[x] = true;
        }
    }

END:
    if(isPairwise){
        PUTS("pairwise coprime");
    }
    else if(isSetwise){
        PUTS("setwise coprime");
    }
    else{
        PUTS("not coprime");
    }

}

Measured memory_bytes: 11064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
//#pragma GCC optimize("Ofast")  //デバッグ時にoptimized-outされて邪魔だった
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  invar(ll, H); invar(ll, W);
  
  if(H == 1 || W == 1) {
    fin(1);
  } else {
    //WAが2つ．なぜ？
    //本番でWAになると，終わる．．ペナルティも怖い
    ll p1w = (W + 1) / 2;
    
    ll res = ((H + 1) / 2) * p1w + (H / 2) * (W / 2);
    fin(res);
  }
}


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

#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif

//{{{
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
vector<string> split(const string& s, char c) {vector<string> v; stringstream ss(s); string x; while
(getline(ss, x, c)) v.push_back(x); return v;} void err(vector<string>::iterator) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n, k;
LL a[N];
LL dp[111][N];
LL s[N];

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif

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

        dp[0][0] = 1;
        for (int i = 0; i <= k; i++) s[i] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= k; j++)
            {
                dp[i][j] = s[j];
                if (j - a[i] > 0) dp[i][j] -= s[j - a[i] - 1];
                dp[i][j] = (dp[i][j] + mod) % mod;
            }

            s[0] = dp[i][0];
            for (int j = 1; j <= k; j++) s[j] = (s[j - 1] + dp[i][j]) % mod;
        }

        cout << dp[n][k] << endl;
    }

    return 0;
}


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

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

  int d;
  cin >> d;
  cout << "Christmas";
  rep(i, 25 - d) {
    cout << " Eve";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
// #include<bits/stdc++.h>
// using namespace std;
 
// const int N = 100, MAXI = 5000, D = 9;
 
// int main() {
//     freopen("output.txt", "r", stdin);
//     freopen("input.txt", "w", stdout);
//     srand(time(nullptr));
//     int tc = 10, flag = 1;
//     cout << tc << "\n";
//     int n = 1;
//     while (tc--)
//     {
//     	int n = rand()%N + 1;
//     	int k = rand()%MAXI + 1;

//     	cout << n << " " << k << "\n";

//     	for(int i=0;i<n;i++)
//     	{
//     		for(int j=0;j<n;j++)
//     		{
//     			cout << rand()%2 << " ";
//     		}
//     		cout << "\n";
//     	}
    	
//     	cout << "~\n";
//     }
 
//     return 0;
// }
 
 
 
 
 
 
 
 
//---------------------------------------------//
 
 
 
/*
#define int long long 
#define mod (int)(1e9+9)
#define endl '\n'
#define MAXI (int)(3e17+10)
#define N 200005
 */ 
 
 
 
 

//  /* while(!cin.eof()) */
 
#include<bits/stdc++.h>
using namespace std; 
//#define int long long
#define ll long long
#define mod (int)(1e9+7)
#define N 105
#define M 100005

int n, k;
int a[N], dp[N][M] = {0};


// Driver code to test above functions
int32_t main()
{
   
     
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
	cout.tie(NULL);

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

	for(int i=0;i<=n;i++)
		dp[i][0] = 1;

	for(int i=1;i<=k;i++)
		dp[0][i] = 0;

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			dp[i][j] = dp[i][j-1];

			dp[i][j] += dp[i-1][j];

			if(dp[i][j]>=mod)
				dp[i][j] %= mod;

			if(j-1-a[i-1]>=0)
				dp[i][j] = (dp[i][j] - dp[i-1][j-1-a[i-1]] + mod)%mod;
		}
	}
	
	cout << dp[n][k];
 
    return 0;
 
} 


Measured memory_bytes: 41216
#include<iostream>
#include<climits>
using namespace std;
#define MAX 20

int T[MAX], n, sum, minv;

void rec( int cur, int v ){
    if ( cur == n ){
	int d = max(v, sum-v) - min(v, sum-v);
	minv = min(minv, d);
	return;
    }
    rec( cur+1, v);
    rec( cur+1, v+T[cur]);
}

void compute(){
    minv = INT_MAX;
    rec(0, 0);
    cout << minv << endl;
}

main(){
    while( cin >>n && n ) {
	sum = 0;
	for ( int i = 0; i < n; i++ ){
	    cin >> T[i]; sum += T[i];
	}
	compute();
    }
}

Measured memory_bytes: 868
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define F first
#define S second
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
using ll = long long;
using pi = pair<int,int>;
int main()
{
  int n; cin >> n;
  int k; cin >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  for (int i = k; i < n; ++i) {
    if(a[i-k] < a[i]) cout << "Yes" << "\n";
    else cout << "No" << "\n";
  }

  
  return 0;
}


Measured memory_bytes: 3964
n = int(input())
A = []
for i in range(n):
    A.append(int(input()))

b = [True]*n
btn = 1
ans = 0
while b[btn - 1]:
    ans += 1
    b[btn - 1] = False
    btn = A[btn - 1]
    if btn == 2:
        b[1] = False
        print(ans)
        break
if b[1]:
    print(-1)


Measured memory_bytes: 13596
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  string s;
  cin>>s;
  ll ans=0;
  for(int i=0;i<s.size();i++){
    int a=s[i]-'0';
    ans+=a;
  }
  if(ans%9==0){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
}


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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long i = 2; i*i <= N; i++) {
        if (N%i != 0) continue;
        long long ex = 0;

        while (N%i == 0) {
            ex++;
            N /= i;
        }
        res.push_back({i, ex});
    }

    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(int argc, char const *argv[]) {
    long long n;
    cin >> n;
    vector<pair<long long, long long> > res = prime_factorize(n);

    long long ans = 0;
    for (auto p : res) {
        long long ex = p.second;
        for (long long i = 1; i <= ex; i++) {
            ans++;
            ex -= i;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
/*
 *Author : zsenshi
 DP Knapsack  
 *
 */
#include <bits/stdc++.h> //Only for gcc compilers
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define dg(x) cout << #x << ":"<<x<<endl
#define dg2(x,y) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<endl
#define dg3(x,y,z) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<endl
#define dg4(x,y,z,zz) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<' '<<#zz<<':'<<zz<<endl
#define rep(i,begin,end) for(__typeof(end) i = (begin)-((begin) > (end)); i != (end) - ((begin) > (end)); i += 1-2*((begin) > (end)))
#define ll long long 
using namespace std;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vector<pii>> vvpi;
const ll INF = 1e18L+5;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,m;
  cin >> n >> m;
  vector<int> d(n,0);
  vector<vector<int>> g(n);
  vector<int> in_degree(n,0);
  int x,y;
  for(int i = 0; i < m; i++){
    cin >> x >> y;
    x--,y--;
    g[x].push_back(y); // x-->y, 
    in_degree[y]++; // -->y
  }
  vector<int> v(n,0);
  function<int(int)> dfs = [&g,&v,&d,&in_degree,&dfs](int vx)->int{
    v[vx] = 1;
    for(auto x : g[vx]){
      if(!v[x]){
        d[x] = max(d[x],d[vx]+1);
        in_degree[x]--;
        if(in_degree[x] == 0){
          dfs(x);
        }
      }
  }};
  for(int i = 0; i < n; i++){
    if(!v[i] && in_degree[i] == 0){
      dfs(i);
    }
  }
  int answer = 0;
  for(auto i : d){
    answer = max(answer,i);
  }
  cout << answer << "\n";
}


Measured memory_bytes: 13184
import bisect
m = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a)
cc = [0] * n
ca = [0] * n
for i in range(n):
  c = 0
  for j in range(i+1,n):
    if a[i] > a[j]:
      c += 1
  cc[i] = c
  ca[i] = bisect.bisect_left(b,a[i])
s = 0
for i in range(n):
  s = ((cc[i]*k)%m + ((k-1)*k*ca[i]//2)%m + s)%m
print(s)

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

using namespace std;

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

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

#endif

void solve() {
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a << '\n';

}

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


Measured memory_bytes: 3608
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
long long x, y;

int main(){
	scanf("%lld", &x);
	long long n = 2 * x; 
	for(int i = 1; i <= 1e5; i++){
		long long k = i * (i + 1); 
		if(k >= n){
			y = i;
			break;
		}
	}
	printf("%lld", y);
}

		

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;
const int maxn = 1e5+7;
int near_pos[maxn][128];
void get_near_pos(string s)
{
    for(char a = 'a';a<='z';++a)
    {
        if(s.back() == a)
        {
            near_pos[s.size()-1][a] = s.size()-1;
        }else
        {
            near_pos[s.size()-1][a] = -1;
        }
        for(int i=s.size()-2;i>=0;--i)
        {
            if(s[i] == a)
            {
                near_pos[i][a] = i;
            }else
            {
                near_pos[i][a] = near_pos[i+1][a];
            }
        }
    }
}
int main()
{
    string s,t;
    cin>>s>>t;
    get_near_pos(s);
    long long ans = 0;
    long long pos = 0;
    for(int p=0;p<t.size();++p)
    {
        char ch = t[p];
        if(near_pos[pos][ch] != -1)
        {
            ans += near_pos[pos][ch] - pos + 1;
            pos = near_pos[pos][ch] + 1;
            if(pos == s.size())pos=0;
        }else
        {
            if(pos == 0)
            {
                ans = -1;
                break;
            }
            ans += s.size() - pos;
            pos = 0;
            p--;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 50560
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238;
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

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

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 3100;

int a[N];
ll dp[N][N][2];

ll calc(int l, int r, int turn) {
    if (dp[l][r][turn] != LINF) {
        return dp[l][r][turn];
    }

    if (l == r) {
        if (turn == 0) {
            return dp[l][r][turn] = a[l];
        } else {
            return dp[l][r][turn] = -a[l];
        }
    }

    if (turn == 0) {
        dp[l][r][turn] = std::max(calc(l + 1, r, turn ^ 1) + a[l], calc(l, r - 1, turn ^ 1) + a[r]);
    } else {
        dp[l][r][turn] = std::min(calc(l + 1, r, turn ^ 1) - a[l], calc(l, r - 1, turn ^ 1) - a[r]);
    }

    return dp[l][r][turn];
}

void run() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j][0] = LINF;
            dp[i][j][1] = LINF;
        }
    }

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

    printf("%lld\n", calc(0, n - 1, 0));
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    auto start = std::chrono::high_resolution_clock::now();
    run();
    auto end = std::chrono::high_resolution_clock::now();

    #ifdef PERVEEVM_LOCAL
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}


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

using namespace std;

int main(){

	string s;

	cin>> s;

	if (s.size() % 2 == 1) {
		cout << "No" << endl;
		return 0;
	}

	for (int i = 0;i < s.size();i+=2) {
		if (s[i] != 'h' || s[i + 1] != 'i') {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

}


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

int main() {
	int H,W;cin>>H>>W;
	vector<string> a(H);
	for (int i = 0; i < H; i++) cin >> a[i];

	vector<bool> row(H, false);
	vector<bool> col(W, false);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (a[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}

	for (int i = 0; i < H; i++) {
		if (row[i]) {
			for (int j = 0; j < W; j++) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}


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

int main(void)
{
    long long K;
    cin >> K;
    if( K %2 == 0 || K % 5 == 0){
        cout << -1 << endl;
    }else{
        long long n = 0;
        long long count=0;
        bool ans = false;
        while(1000000 > count){
            n = n * 10;
            n = n + 7;
            n = n % K;
            ++count;
            if( n == 0){
                ans = true;
                break;
            }
        }

        if(ans == true){
            cout << count << endl;
        }else{
            cout << -1 << endl;
        }
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    string s;
    cin >> s;
    rep(i,s.size() - 1){
        if(s[i] == 'A' && s[i + 1] == 'C'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main(){
  int N; cin >> N;
  vector<int> L(N);
  int m = 0;
  int sum = 0;
  for(int i = 0; i < N; i++){
    cin >> L[i];
    m = max(m, L[i]);
    sum += L[i];
  }
  sum -= m;
  
  if(sum > m) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256