akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>

int main(void){
  char s[110];
  long long k;
  scanf("%s%lld", s, &k);

  long long N = strlen(s);
  long long right = 0, left = 0, i = 0;
  while(s[0] == s[i]){
    i++;
    right++;
  }
  i = N-1;
  while(s[N-1] == s[i]){
    i--;
    left++;
  }

  long long ans1 = 0;
  if(right == N){
    printf("%lld\n", N*k/2);
    return 0;
  }else if(s[N-1] == s[0]){
    ans1 = (right+left)/2*(k-1)+right/2+left/2;
  }else{
    ans1 += (right/2+left/2)*k;
  }

  long long ans2 = 0, cnt = 1;
  for (int i = right+1; i < N-left+1; i++) {
    if(s[i] != s[i-1] || i == N-left){
      ans2 += cnt/2*k;
      cnt = 1;
    }else{
      cnt++;
    }
  }

  printf("%lld\n", ans1+ans2);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <memory.h>
using namespace std;

const int source=201,sink=202;

typedef pair<int,int> pi;

int n;
vector<int> b[2];
int c[105][105];
int capa[205][205];
vector<int> adj[205];
bool used[205];



bool prime(int n){
	n=abs(n);
	if(n==1) return false;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0) return false;
	}
return true;
}

int dfs(int v,int t){
	if(v==t) return 1;
	for(int i=0;i<adj[v].size();i++){
		if(capa[v][adj[v][i]]==1&&!used[adj[v][i]]){
			used[adj[v][i]]=true;
			int d=dfs(adj[v][i],t);
			if(d>0){
				capa[v][adj[v][i]]-=d;
				capa[adj[v][i]][v]+=d;
				return d;
			}
		}
	}
return 0;
} 

int main(){
	scanf("%d",&n);
	int last=-1;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x>last+1&&last!=-1) {
			b[(last+1)%2].push_back(last+1);
			b[x%2].push_back(x);
		}
		else if(x>last+1) b[x%2].push_back(x);
		last=x;
	}
	b[(last+1)%2].push_back(last+1);
	for(int i=0;i<b[0].size();i++){
		for(int j=0;j<b[1].size();j++){
			int x=b[0][i]-b[1][j];
			if(x%2){
				if(prime(x)) c[i][j]=1;
				else c[i][j]=3;
			}
			else c[i][j]=2;
		}
	}
	for(int i=0;i<b[0].size();i++){
		adj[source].push_back(i);
		adj[i].push_back(source);
		capa[source][i]=1;
	}
	for(int i=0;i<b[1].size();i++){
		adj[100+i].push_back(sink);
		adj[sink].push_back(100+i);
		capa[100+i][sink]=1;
	}
	for(int i=0;i<b[0].size();i++){
		for(int j=0;j<b[1].size();j++){
			if(c[i][j]==1){
				adj[i].push_back(100+j);
				adj[100+j].push_back(i);
				capa[i][100+j]=1;
			}
		}
	}
	int pairnum=0;
	while(dfs(source,sink)){
		pairnum++;
		memset(used,false,sizeof used);
	}
	int ans=0;
	ans+=pairnum;
	int x=b[0].size()-pairnum,y=b[1].size()-pairnum;
	if(x%2&&y%2) ans+=x+y+1;
	else ans+=x+y;
	printf("%d\n",ans);
return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;

int main() {
  string N;
  cin >> N;
  long long n = 0;

  for (int i = 0; i < N.size(); i++) {
    n += N[i] - '0';
  }

  cout << ((n % 9 == 0) ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 3416
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();
        long[] aSum = new long[n+1];
        long[] bSum = new long[m+1];

        aSum[0] = 0;
        bSum[0] = 0;
        for (int i = 1; i <= n;++i) aSum[i] = aSum[i-1] + sc.nextLong();
        for (int i = 1; i <= m;++i) bSum[i] = bSum[i-1] + sc.nextLong();

        int maxBooks = 0;
        int bBestInd = bSum.length-1;
        for (int i = 0;i<=n;++i)
        {
            long remaining = k - aSum[i];
            //System.err.println(i+":"+remaining+"(bBestInd = "+bBestInd+")");
            if (remaining < 0) break;
            int books = i;

            for (int j = bBestInd;j >= 0;--j)
            {
                if (remaining-bSum[bBestInd] >= 0)
                {
                    bBestInd = j;
                    books += j;
                    System.err.println(i+":"+j+"(time = "+(remaining+aSum[i])+")");
                    break;
                }else
                {
                    --bBestInd;
                }
            }

            if (maxBooks < books) maxBooks = books;
        }
        System.out.println(maxBooks);
        sc.close();
    }
}

Measured memory_bytes: 64316
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LLINF = 1LL << 60;

signed main()
{
  int N;
  int A[100005], sum, minv = LLINF;
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int p = 0; p < 2; p++) {
    int ans = 0;
    sum = 0;
    for(int i = 0; i < N; i++) {
      sum += A[i];
      if((i + p) % 2) {
	ans += max(0LL, -sum + 1);
	if(sum <= 0) sum = 1;
      } else {
	ans += max(0LL, sum + 1);
	if(sum >= 0) sum = -1;
      }
    }
    minv = min(ans, minv);
  }
  cout << minv << endl;
  
  return 0;
}


Measured memory_bytes: 1024
n,x=map(int,input().split())
l=list(map(int,input().split()))
d=[0]

for i in range(1,n+1):
    temp=d[i-1]+l[i-1]
    if temp>x:
        ans=i
        break
    d.append(temp)

else:
    ans=n+1

print(ans)

Measured memory_bytes: 9188
import sys
input = sys.stdin.readline
mod = 10**9 + 7

def main():
    n = int(input())
    A = list(map(int, input().split()))
    candidates = [0] * (n+1)
    candidates[0] = 3
    ans = 1

    for a in A:
        ans *= candidates[a]
        ans %= mod
        candidates[a] -= 1
        candidates[a+1] += 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 20488
#include <stdio.h>
typedef long long ll;
ll maxi(ll a, ll b)
{
    if(a>=b)return a;
    return b;
}
int a[105],b[105];
ll dp[105][100005];
int main(void) {
	int n,w;
	scanf("%d%d",&n,&w);
	int i;
	for(i=1; i<=n; i++)
	scanf("%d%d",&a[i],&b[i]);
	int j;
	ll ans = 0;
	for(i=1; i<=n; i++)
	{
	    for(j=0;j<=w;j++)
	    {
	        // if not  then 
	        dp[i][j] = dp[i-1][j];
	        // if take then 
	        if(j >= a[i])
	        dp[i][j] = maxi(dp[i][j], dp[i-1][j-a[i]] + b[i]);
	       // printf("%d %d is %lld\n",i,j,dp[i][j]);
	        ans = maxi(ans,dp[i][j]);
	    }
	}
	printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 79232
n, q = [int(i) for i in input().split()]
ab_pairs = []
for _ in range(n-1):
    ab_pairs.append([int(i) - 1 for i in input().split()])

qx_pairs = []
for _ in range(q):
    qx_pairs.append([int(i) for i in input().split()])

ab_pairs_sorted = sorted(ab_pairs, key= lambda ab_pair: ab_pair[1])

point_list = [0] * n
for qx_pair in qx_pairs:
    index = qx_pair[0] - 1
    x = qx_pair[1]
    point_list[index] += x

for ab_pair in ab_pairs_sorted:
    a = ab_pair[0]
    b = ab_pair[1]
    point_list[b] += point_list[a]


print(' '.join(map(str, point_list)))


Measured memory_bytes: 102088
#include <stdio.h>
int main(){
	/*???????¨????*/
	int x[3000],y[3000],s;
	for(s=0;s<3000;s++){
		x[s]=-1;
		y[s]=-1;
	}
	int i,t,temp;
	
	
	/*??\???*/
//	printf("??\???\n");
	for(i=0;i<3000;i++){
		do{
			scanf("%d %d",&x[i],&y[i]);
			printf("");
		}while(!(x[i]>=0 && x[i]<=10000 && y[i]>=0 && y[i]<=10000));
		if(x[i]==0 && y[i]==0)break;
	}
	
	
	/*??????*/
	for(t=0;t<=i;t++){
		if(x[t]>y[t]){
			temp=x[t];
			x[t]=y[t];
			y[t]=temp;
		}
	}
	
	
	/*??????*/
//	printf("??????\n");
	for(t=0;t<i;t++){
		printf("%d %d\n",x[t],y[t]);
	}
	

	return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long> VLL;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
/*--------------------------------------------*/
int main(){
    int n;cin>>n;
    vector<double> x(n);
    vector<string> u(n);
    double ans=0;
    rep(i,n){
        cin>>x[i]>>u[i];
        if(u[i]=="JPY")ans+=x[i];
        if(u[i]=="BTC")ans+=x[i]*380000.0;
    }
    cout<<ans<<endl;
}


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

/* 繰り返し自乗法. */
int modPow(long long a, long long n, long long p) {
	if (n == 0) return 1; // 0乗にも対応する場合.
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}

signed main() {
    int N, M;
    cin >> N >> M;

    if (N == M) cout << "Yes" << endl;
    else        cout << "No"  << endl;

}


Measured memory_bytes: 3624
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

int A[110];
int N, K; 
int dp[100010][2];
//残り石がiで手番がjの時に勝つ人

int f(int K, int a) {

	//cout << K << " " << a << endl;
	
	if (dp[K][a] != -1)return dp[K][a];

	if (K == 0) {
		return dp[K][a] = a ^ 1;
		cout << "K" << endl;
	}

	REP(i, N) {
		if (K - A[i] < 0)break;
		if (f(K - A[i], a ^ 1) == a)return dp[K][a] = a;
	}
	return dp[K][a] = a ^ 1;
}

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

	cin >> N >> K;
	eREP(i, K)dp[i][0] = dp[i][1] = -1;
	REP(i, N)cin >> A[i];
	if (f(K, 0) == 0)cout << "First" << endl;
	else cout << "Second" << endl;

	//cout << endl;
	//eREP(i, K)cout << dp[i][0] << " " << dp[i][1] << endl;

	return 0;
}



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

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

typedef long long ll;
using namespace std;

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

  int a, b, c;
  cin >> a >> b >> c;
  cout << a * b / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  ABC105
//
//  Created by hiroaki on 2019/03/18.
//  Copyright © 2019年 hiroaki. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//~~A~~
int main() {
    int n,k;
    cin >>n>>k;
    if (n%k==0) {
        cout<<0<<endl;
    }else{
        cout<<1<<endl;
    }
    return 0;
}


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

using namespace std;

int main(){
  int K;
  cin >> K;
  
  string str;
  cin >> str;
  
  int x = str.size();
  
  if(x <= K ){
    cout << str << endl;
  }
  
  if(x > K){
    for(int i=0; i<x - K; i++){
      str.pop_back();
    }
    
    cout << str << "..." << endl;
    
  }
   

  
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
const int N = 5000;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	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 n, k;
vector<int> a;
bitset<N> t, t2;

int main()
{
	n = read();
	k = read();
	int ans = n;
	LL suma = 0;
	for (int i = 0; i < n; i ++)
	{
		int x;
		x = read();
		suma += x;
		if (x >= k) ans --;
		else a.pb(x);
	}

	if (suma < k)
	{
		cout << n << endl;
		return 0;
	}
	else if (suma == k)
	{
		cout << 0 << endl;
		return 0;
	}
	n = (int)a.size();

	t.set(0);
	for (int i = 0; i < n; i ++)
	{
		if (i) t = (t << a[i - 1]) | t;
		t2 = t;
		bool f = 0;
		for (int j = i + 1; j < n; j ++)
		{
			t2 = (t2 << a[j]) | t2;
			if (~j & 31)
            {
				for (register int l = k - a[i]; l < k; l ++)
					if (t2.test(l))
					{
						f = 1;
						break;
					}

				if (f) break;
			}
		}
		for (register int j = k - a[i]; j < k; j ++)
			if (t2.test(j))
			{
				f = 1;
				break;
			}

		ans -= f;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<iostream>
#include<algorithm>
#include <string>
#include <stdexcept>
using namespace std; 
int main(){
  char t[4];
 long long int a,b[120],c=0,d,e; 
 	cin >>t;
  for(int i=0;i<4;i++){
   if(t[i]=='-')c-=1;
    else c+=1;
  }
  cout <<c;
}

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


Measured memory_bytes: 2072
#include<bits/stdc++.h>
    using namespace std;
    int main(){
      int ks = 0;
      int a,b,k; cin >> a >> b >> k;
      for(int i = min(a,b);;i--){
        if(a%i == 0 && b%i == 0) ks++;
        if(ks == k) return cout << i << endl, 0;
      }
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define ifaxb(a, x, b) if (a < x && x < b)
#define toInt(x) (x - '0')
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define vvs vector<vs>
#define all(x) x.begin(), x.end()
#define INF 2147483647
#define _INF -2147483647
#define pi 3.1415926536
#define MAXN 100004
using namespace std;
typedef long long ll;

int main() {
  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;
  int ans = max({a1, a2, a3}) - min({a1, a2, a3});
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		int n=s.nextInt(),m=s.nextInt();
		int[][] graph    = new int[n][n];
		int[][] graphini = new int[n][n];
		{
			for(int i=0;i<n;i++) {
				Arrays.fill(graph   [i], 114514);
				Arrays.fill(graphini[i], 114514);
				graph   [i][i]=0;
				graphini[i][i]=0;
			}
		}
		{
			int x,y,w;
			for(int i=0;i<m;i++) {
				x=s.nextInt()-1;y=s.nextInt()-1;w=s.nextInt();
				graph   [x][y]=w;
				graph   [y][x]=w;
				graphini[x][y]=w;
			}
		}
		for(int d=0;d<n;d++)
			for(int x=0;x<n;x++)
				for(int y=0;y<n;y++)
					graph[x][y]=Math.min(graph[x][y], graph[x][d]+graph[d][y]);

		int r=0;
		for(int x=0;x<n;x++)
			for(int y=0;y<n;y++)
				if(graphini[x][y]!=114514&&graphini[x][y]>graph[x][y])
					r++;
		System.out.println(r);
	}
}

Measured memory_bytes: 14516
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>

#define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())

#define eb emplace_back
#define ef emplace_front
#define dbg(x) cout<<#x" = "<<((x))<<endl
#define fs first
#define sc second
     
using namespace std;
     
     
typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];
 
inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}
 
inline ll add(ll a, ll b){
    return take_mod(a+b);
}
 
inline ll sub(ll a, ll b){
    return take_mod(a-b);
}
 
 
inline ll mul(ll a, ll b){
    return take_mod(a * b);
}
 
inline ll pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}
 
ll mod_inv(ll x){
    return pow(x, mod-2);
}
 
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}
 
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}
 
ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}
 
ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}

int mypow(int x, int n){
  int ret = 1;
  for(int i = 0; i < n; ++i){
    ret *= x;
  }

  return ret;
}

int main(){
  string str;

  cin >> str;

#ifdef DEBUG
  cout << "str=" << str << endl;
#endif

  int N = str.length();


  ll dp[N+1][13];

  for(int i = 0; i <= N; ++i){
    for(int j = 0; j < 13; ++j){
      dp[i][j] = 0;
    }
  }

  dp[0][0] = 1;


  int mul = 1;
  for(int i = 1; i <= N; ++i){
    // cout << "stri" << str[i-1] << endl;
    if(str[N-i] == '?'){
      for(int k = 0; k <= 12; ++k){
	//cout << "k=" << k << " " << endl;
	for(int l = 0; l <= 9; ++l){
	  dp[i][(k + l*mul)%13] += dp[i-1][k];
	  dp[i][(k + l*mul)%13] = take_mod(dp[i][(k + l*mul)%13]);
	} // l
      } // k
    } else {
      for(int k = 0; k <= 12; ++k){
	int strd = str[N-i] - '0';
	dp[i][(k + strd*mul)%13] = dp[i-1][k];
	dp[i][(k + strd*mul)%13] = take_mod(dp[i][(k + strd*mul)%13]);
      } // k	      
    }
    mul *= 10;
    mul %= 13;
    // // ---
    // cout << endl;
    // for(int i = 0; i <= N; ++i){
    //   for(int j = 0; j < 13; ++j){
    // 	cout << dp[i][j] << " ";
    //   }
    //   cout << endl;
    // }
    // // ---
  }

  cout << dp[N][5] << endl;
  
  return 0;
}


Measured memory_bytes: 10624
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define mp make_pair
#define enld endl

int main() {
	lint N, K;
	cin >> N >> K;
	vector<lint>P(N);
	rep(i, N) {
		cin >> P[i];
	}
	lint ans = 0;
	sort(P);
	rep(i, K) {
		ans += P[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define SZ(v) int((v).size())
#define ALL(vec) begin(vec), end(vec)
using namespace std;
typedef long long i64;
template <typename T>
inline bool uax(T &x, T y) { return (y > x) ? x = y, true : false; }
template <typename T>
inline bool uin(T &x, T y) { return (y < x) ? x = y, true : false; }
#define error(args...)                       \
  {                                          \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
  }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
template <typename A>
string to_string(A);
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool f = false;
  string r = "{";
  for (auto x : v) {
    if (f)
      r += ", ";
    r += to_string(x);
    f = true;
  }
  return r += "}";
}
template <typename A>
string to_string(vector<vector<A>> v) {
  string r;
  for (auto x : v) r += "\n" + to_string(x);
  return r;
}
void err(istream_iterator<string>) { cerr << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << to_string(a) << "; ";
  err(++it, args...);
}
template <typename T>
void kek(T ans) {
  cout << ans << endl;
  exit(0);
}
int const MOD = 1e9 + 7;
long long const INF = 1e18 + 42;
/*************************************/

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  i64 n, x, d;
  cin >> n >> x >> d;
  if (d == 0) {
    if (x == 0)
      kek(1);
    kek(n + 1);
  }
  if (x == 0)
    kek(1LL + n * (n - 1) / 2);
  map<i64, vector<pair<i64, i64>>> m;
  for (i64 take = 0; take <= n; ++take) {
    i64 b = take * x;
    i64 sum = take * (take - 1) / 2LL;
    i64 rsum = (n - take) * take + sum;
    i64 c = b / d;
    m[b % d].emplace_back(c + sum, c + rsum);
  }
  i64 ans = 0LL;
  for (auto &pr : m) {
    auto &v = pr.second;
    sort(ALL(v));
    i64 l, r;
    int f = 0;
    for (auto &p : v) {
      if (!f) {
        f = 1;
        l = p.first;
        r = p.second;
      } else {
        if (p.first <= r) {
          uax(r, p.second);
        } else {
          ans += r - l + 1;
          l = p.first;
          r = p.second;
        }
      }
    }
    ans += r - l + 1;
  }
  kek(ans);

  return 0;
}


Measured memory_bytes: 22144
program go_to_school
  implicit none
  integer :: n, i
  integer, dimension(100000) :: a, b
  read(*,*) n
  read(*,*) a(1:n)
  do i = 1, n
    b(a(i)) = i
  end do
  write(*,*) b(1:n)
end program go_to_school

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

#define ll              long long int
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define fast_io         ios_base::sync_with_stdio(false); cin.tie(NULL);

int main(){
	fast_io;    
    // bottom up approach
    string s,t;
    string ans = "";
    cin >> s >> t;

    if(s.size() == 0 or t.size() == 0){
        cout<<ans<<"\n";
        return 0;
    }

    int n = s.size(), m = t.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1,0));
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){

            if(s[i-1] == t[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    int i=n, j=m;
    while(i>0 and j>0){
        if(dp[i][j] != max(dp[i-1][j], dp[i][j-1])){
            ans = s[i-1]+ans;
            i--;
            j--;
        }
        else{
            if(dp[i-1][j] > dp[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }
    }

    cout<<ans<<"\n";
    
    return 0;
}


Measured memory_bytes: 35584
#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define int long long
const int mod = 1e9 + 7;
inline int ksm(int a, int b)
{
	int ans = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1)
			ans = ans * a % mod;
	return ans;
}
struct nd{
	int l,r;
	int d;
	int v;
};
int fac[3000000],inv[3000000];
int C(int n,int m){
	if(n<0 || m>n)return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
nd cal(nd t,int d,int l,int r){
	//nd res = t;
	if(r-l+1<=4){
		rep(i,t.l,t.r)t.v =(t.v-C(t.d,i))%mod;
		t.d=d;
		t.l=l;t.r=r;
		rep(i,l,r)t.v =(t.v+ C(t.d,i))%mod;
	}
	else {
		t.v=(2*t.v%mod-C(t.d,t.l)-C(t.d,t.r))%mod;
		t.v=(t.v+C(d,t.l))%mod;
		if(t.l<l)t.v=(t.v-C(d,t.l))%mod;
		if(t.r<r)t.v=(t.v+C(d,r))%mod;
		t.d=d;t.l=l;t.r=r;
	}
	return t;
}


int gao(int n,int m){
	if(n>m)swap(n,m);
	//cout<<n<<" "<<m<<endl;
	int ans=0;
	nd t;t.d=t.l=t.r=0;t.v=1;
	rep(i,0,m+n){
		int l=max(i-m,0ll),r=min(i,n);
		t = cal(t,i,l,r);
		ans =(ans+t.v)%mod;
	//	cout<<t.d<<" "<<t.v<<" "<<t.l<<" "<<t.r<<endl;
	}
	return ans;
}
signed main()
{
	fac[0]=inv[0]=1;
	rep(i,1,3e6-1){
		fac[i]=fac[i-1]*i%mod;
		inv[i] = ksm(fac[i],mod-2);
	}
	//cout<<C(0,0);
	/*
{	nd t;
	t.d = t.l = t.r = 0;
	t.v = 1;
	rep(i,1,20){
		t=cal(t,i,0,i);
		cout<<t.v<<endl;
	}
}
*/
	int r1,r2,c1,c2;
	cin>>r1>>c1>>r2>>c2;
	int t=gao(r2,c2) - gao(r1-1,c2) - gao(r2,c1-1) + gao(c1-1,r1-1);
	t=(t%mod+mod)%mod;
	cout<<t<<endl;
	getchar();getchar();
}


Measured memory_bytes: 47104
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <bitset>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void){
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int64_t n,k;
  cin>>n>>k;
  std::bitset<32> k_bit(k);
  int64_t result=0;

  std::vector<std::bitset<32>> a(n);
  std::vector<int64_t> b(n);
  for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    std::bitset<32> tmp(x);
    a[i]=tmp;
    b[i]=y;
  }

  // init result

  for(int j=0;j<n;j++){
    const std::bitset<32>& tgt=a[j];
    const int64_t& value=b[j];

    bool can_use=true;
    for(int l=31;l>=0;l--){
      if(!k_bit[l]&&tgt[l]){
        can_use=false;
        break;
      }
    }
    if(can_use){
      result+=value;
    }
  }


  for(int i=1;std::pow(2,i)<=k;i++){
    if(!k_bit[i]) continue;
    int64_t tmp_result=0;

    for(int j=0;j<n;j++){
      const std::bitset<32>& tgt=a[j];
      const int64_t& value=b[j];

      if(tgt[i]) continue;
      bool can_use=true;
      for(int l=31;l>=i+1;l--){
        if(!k_bit[l]&&tgt[l]){
          can_use=false;
          break;
        }
      }
      if(can_use){
        tmp_result+=value;
      }
    }


    result=std::max(result,tmp_result);
  }
  cout<<result<<endl;
  
  return 0;
}


Measured memory_bytes: 1792
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQUE(c)   sort(ALL((c)));(c).erase(unique(ALL((c))),(c).end())
# define LOWER(s)    transform(ALL((s)),(s).begin(),TL<char>)
# define UPPER(s)    transform(ALL((s)),(s).begin(),TU<char>)
# define FOR(i,a,b)  for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int N;
char C[4020];
int A[4020];
int smB[2020][4020];
int smW[2020][4020];
int idxB[2020];
int idxW[2020];

int memo[2020][2020];
int f(int b, int w) {
	if (b == N && w == N) return 0;
	if (0 <= memo[b][w]) return memo[b][w];

	int res = INF;

	if (b != N) {
		int cnt = 0;
		if (0 <= idxB[b + 1] - 1) cnt += smB[b + 1][idxB[b + 1] - 1];
		if (0 <= idxB[b + 1] - 1) cnt += smW[w + 1][idxB[b + 1] - 1];

		res = min(res, f(b + 1, w) + cnt);
	}

	if (w != N) {
		int cnt = 0;
		if (0 <= idxW[w + 1] - 1) cnt += smB[b + 1][idxW[w + 1] - 1];
		if (0 <= idxW[w + 1] - 1) cnt += smW[w + 1][idxW[w + 1] - 1];
		res = min(res, f(b, w + 1) + cnt);
	}

	return memo[b][w] = res;
}

int main() {
	cin >> N;
	REP(i, 2 * N) cin >> C[i] >> A[i];

	REP(i, 2 * N) {
		if (C[i] == 'B') smB[A[i]][i]++;
		else smW[A[i]][i]++;
	}
	REP(i, N + 5) {
		FOR(j, 1, 2 * N) smB[i][j] += smB[i][j - 1];
		FOR(j, 1, 2 * N) smW[i][j] += smW[i][j - 1];
	}
	REP(j, 2 * N) {
		for (int i = N + 4; i >= 0; i--) smB[i][j] += smB[i + 1][j];
		for (int i = N + 4; i >= 0; i--) smW[i][j] += smW[i + 1][j];
	}

	REP(i, 2 * N) {
		if (C[i] == 'B') idxB[A[i]] = i;
		if (C[i] == 'W') idxW[A[i]] = i;
	}

	REP(i, N + 1) REP(j, N + 1) memo[i][j] = -1;
	cout << f(0, 0) << endl;
}

Measured memory_bytes: 79744
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	m := getNextInt(scanner)

	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, 0)
	}
	for i := 0; i < m; i++ {
		s := getNextInt(scanner) - 1
		t := getNextInt(scanner) - 1
		g[s] = append(g[s], t)
	}

	ysp48 := make([]float64, n)
	rng58 := make([]float64, n)
	rng58[0] = 1
	for i := 0; i < n-1; i++ {
		for _, to := range g[i] {
			rng58[to] += rng58[i] / float64(len(g[i]))
		}
	}

	for i := n - 2; i >= 0; i-- {
		for _, to := range g[i] {
			ysp48[i] += ysp48[to] + 1
		}
		ysp48[i] /= float64(len(g[i]))
	}
	horobiyo := 0.0

	for i := 0; i < n-1; i++ {
		l := len(g[i])
		if l < 2 {
			continue
		}
		for _, to := range g[i] {
			oni := rng58[i] * (ysp48[i] - (ysp48[i]*float64(l)-(ysp48[to]+1))/float64(l-1))
			if horobiyo < oni {
				horobiyo = oni
			}
		}
	}

	fmt.Fprintln(writer, ysp48[0]-horobiyo)
	writer.Flush()
}


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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> s(m);
	for (int i = 0; i < m; i++) {
		int k;
		cin >> k;
		vector<int> v(k);
		for (int j = 0; j < k; j++) cin >> v[j];
		s[i] = v;
	}
	vector<int> p(m);
	for (int i = 0; i < m; i++) cin >> p[i];

	int ans = 0;
	for (int bit = 0; bit < 1 << n; bit++) {
		int wholeCount = 0;
		vector<int> sw(n + 1);
		for (int i = 0; i < n; i++) {
			if (bit&(1 << i)) sw[i] = 1;
		}
		for (int i = 0; i < m; i++) {
			int count = 0;
			for (int j = 0; j < s[i].size(); j++) {
				if (sw[s[i][j] - 1]) count++;
			}
			if (count % 2 == p[i]) wholeCount++;
		}
		if (wholeCount == m) ans++;
	}
	cout << ans << endl;
}


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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

ll bpow(ll x,ll n,ll m=MD,ll r=1LL){for(;n>0;n>>=1,x=x*x%m) if(n&1) r=r*x%m; return r;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	VL c(n);
	rep(i,n) cin >>c[i];
	sort(all(c));
	ll ans = 0;
	rep(l, n){
		int r = n-1-l;
		//(2^r + r * 2^(r-1)) * 2^l * a[i];
		ll tmp = (bpow(2, r) + (r>0? r * bpow(2, r-1): 0)) %MD;
		(tmp *= (bpow(2, l) * c[l]) %MD) %=MD; 
		(ans += tmp ) %=MD;
	}
	ans = ans * bpow(2, n) % MD;
	cout << ans <<"\n";
	return 0;
}


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

int main(){
  int A,B,N,cnt=1;
  cin >> A >> B;
  if (B == 1){
    cout << "0" << endl;
    return 0;
  }
  N = A-1;
  while (A<B){
    A += N;
    cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#define MAX 100000
char a[MAX],b[MAX];
using namespace std;
int main()
{
	cin>>a;
	int l=strlen(a);
	for(int i=0;i<l;i++) b[l-i-1]=a[i];
	for(int i=0;i<l;i++)
	if(b[i]=='b') b[i]='d';
	else if(b[i]=='d') b[i]='b';
	else if(b[i]=='p') b[i]='q';
	else if(b[i]=='q') b[i]='p';
	for(int i=0;i<l;i++)
	if(a[i]!=b[i])
	{
		cout<<"No";
		return 0;
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 384
antenna = [int(input()) for _ in range(5)]
d = int(input())

import itertools
i = 0
for v in itertools.combinations(antenna, 2):
    if abs(v[0]-v[1]) > d:
        print(":(")
        break
    else:
        pass
    i += 1
if i == 10:
    print("Yay!")

Measured memory_bytes: 3060
<?php

$N = fgets(STDIN);
$A = explode(" ", fgets(STDIN));

rsort($A);

$sumA = 0;
$sumB = 0;

for ($i = 0; $i < count($A); $i++) {
  if ($i % 2 === 0) {
    $sumA = $sumA + $A[$i];
  } else {
    $sumB = $sumB + $A[$i];
  }
}

// 差を出力
echo $sumA - $sumB;

?>


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;}


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

int K, A, B; cin >> K >> A >> B;

rep(i, A, B+1) {
    if (i % K == 0) {
        cout << "OK\n";
        return 0;
    }
}
cout << "NG\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

using namespace std;

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

	string S;
    cin >> S;
	if(S == "AAA" || S == "BBB"){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> void read(T &x){
	int f=0; x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	if(f) x=-x;
}

const int N=1000005;
const int mod[2]={1000000009,1019260817};
const int seed[2]={666,19260817};
namespace hsh{
	const int M=3051439;
	int A[M],B[M],L[M],h[M],sz;
	int harsh(ll a,ll b){
		return ((a<<13)^(a>>2)^(a<<4)^(b<<3)^(b>>5))%M;
	}
	void ins(int a,int b){
		int ha=harsh(a,b);
		A[++sz]=a,B[sz]=b,L[sz]=h[ha],h[ha]=sz;
	}
	int qry(int a,int b){
		int k=h[harsh(a,b)];
		for(;k;k=L[k]){
			if(A[k]==a&&B[k]==b){
				return 1;
			}
		}
		return 0;
	}
}
int f[2][N],rk[N],flag[26],n;
unordered_map<ll,int> cnt;
string s[N];
ll ans;

int main(){
	read(n);
	ios::sync_with_stdio(false);
	rep(i,1,n){
		cin>>s[i];
		rk[i]=i;
	}
	sort(rk+1,rk+n+1,[&](int a,int b){
		return s[a].size()<s[b].size();
	});
	rep(i,1,n){
		int k=rk[i],m=s[k].size();
		REP(t,2) per(j,m,1){
			f[t][j]=((ll)f[t][j+1]*seed[t]+s[k][j-1]-'a'+1)%mod[t];
		}
		memset(flag,0,sizeof flag);
		rep(j,1,m){
			flag[s[k][j-1]-'a']++;
			REP(c,26) if(flag[c]){
				int A=((ll)f[0][j+1]*seed[0]+c+1)%mod[0];
				int B=((ll)f[1][j+1]*seed[1]+c+1)%mod[1];
				ans+=hsh::qry(A,B);
			}
		}
		hsh::ins(f[0][1],f[1][1]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 53712
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
//#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

int main()
{
	FAST;
	string s;
	cin >> s;
	bool b1, b2;
	ll t1 = ((s[0]-'0')*10) + (s[1] - '0');
	ll t2 = ((s[2]-'0')*10) + (s[3] - '0');
	if((t1 <= 12)&&(t1 > 0))
		b1 = true;
	else
		b1 = false;
	if((t2 <= 12)&&(t2 > 0))
		b2 = true;
	else
		b2 = false;	
	if(b1 && b2)
		cout << "AMBIGUOUS";
	else if(b1 && (!b2))
		cout << "MMYY";
	else if((!b1) && b2)
		cout << "YYMM";
	else 
		cout << "NA";	
	
}


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

int main() {
	int n;
	cin >> n;
	if (n % 2 == 0) cout << fixed << setprecision(8) << (double)1 / 2;
	else cout << fixed << setprecision(8) << (double)(n + 1) / 2 / n;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char m[1002][1002];
char r[1002][1002];
struct node {
  unsigned x:10;
  unsigned y:10;
  unsigned int l;
  struct node* n;
} *qs,*qe;
typedef struct node st;
void push(int x,int y,int l)
{
  st *p = qe;
  if(qe == NULL){
    qe = (st *)(malloc(sizeof(st)));;
    qs = qe;
  }else{
    p->n = (st *)(malloc(sizeof(st)));
    qe = p->n;
  }
  qe->x = x;
  qe->y = y;
  qe->l = l;
  qe->n = NULL;
  r[y][x] = 1;
}
st *pop()
{
  st *p = qs;
  if(qs == NULL) return NULL;
  qs = qs->n;
  if(qs == NULL) qe = NULL;
  return p;
}
void flush()
{
  st *p = qs;
  while(p != NULL){
    qs = qs->n;
    free(p);
    p = qs;
  }
  qe = NULL;
}
int search(int* xs,int* ys,int d)
{
  st *p;
  int l,i,x,y;
  int xd[] = {-1,1,0,0}, yd[] = {0,0,-1,1};
  memset(r,0,sizeof(r));
  push(*xs,*ys,0);
  while((p = pop()) != NULL){
    for(i=0; i<4; i++) {
      x = (p->x) + xd[i];
      y = (p->y) + yd[i];
      if(m[y][x] == d) {
	*xs = x;
	*ys = y;
	l = (p->l) + 1;
	free(p);
	return l;
      }
      if((m[y][x] != -1) && (r[y][x] == 0))
	push(x, y, (p->l)+1);
    }
    free(p);
  }
}
int main(){
  int h,w,n,i,j,xs,ys,t=0;
  char c[1002];
  memset(m,-1,sizeof(m));
  scanf("%d%d%d\n",&h,&w,&n);
  for(i=1;i<=h;i++){
    scanf("%s",c);
    for(j=1;j<=w;j++){
      switch(c[j-1]){
      case 'S':
	xs = j; ys = i;
      case '.':
	m[i][j] = 0;
	break;
      case 'X':
	m[i][j] = -1;
	break;
      default:
	m[i][j] = c[j-1]-'0';
      }
    }
    scanf("\n");
  }
  for(i=1;i<=n;i++){
    t+=search(&xs,&ys,i);
    flush();
  }
  printf("%d\n",t);
  return 0;
}

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

int main(){
    string a, b;
    cin >> a >> b;
    bool flag = false;
    if(a == b){
        cout << "EQUAL\n";
    }else{
        if(a.size() == b.size()){
            int i = 0;
            while(a[i] == b[i]) i++;
            if(a[i] > b[i]) flag = true;
        }else{
            if(a.size() > b.size()) flag = true;
        }
        cout << (flag ? "GREATER\n" : "LESS\n");
    }

}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from math import floor

def main():
    n = int(input())
    A = [int(input()) for _ in range(n)]

    x = 0
    for a in A:
        if a == 0:
            yield x // 2
            x = 0
        x += a

    yield x // 2


print(sum(main()))


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

typedef long long ll;
const int NMAX = 2e5 + 10;
const int MOD = 1e9 + 7;
int main(int argc, char const *argv[])
{
	ll x,k,d;
	scanf("%lld%lld%lld",&x,&k,&d);
	x = abs(x);
	if(x/d >= k)
		return 0*printf("%lld\n",x - k*d );
	ll block = x/d;
	printf("%lld\n",abs(x - (block + ((k - block)&1))*d));
	return 0;
}

Measured memory_bytes: 3832
#include <iostream>
using namespace std;
int main(){
    int n,t;
    cin >> n >> t;
    int a[n];
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    int mini=a[0];
    int max_bene=0;
    int ans=0;
    for (int i=1; i<n; i++){
        if (a[i]<mini){
            mini=a[i];
            continue;
        }
        if (a[i]-mini>max_bene){
            max_bene=a[i]-mini;
            ans=1;
            continue;
        }
        if (a[i]-mini==max_bene){
            ans++;
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

int next(int u) {
  for (int v = nt[u]; v < n; v++) {
    nt[u] = v + 1;
    if (M[u][v]) return v;
  }
  return -1;
}

void dfs_visit(int r) {
  for (int i = 0; i < n; i++) nt[i] = 0;

  stack<int> S;
  S.push(r);
  color[r] = GRAY;
  d[r] = tt++;

  while (!S.empty()) {
    int u = S.top();
    int v = next(u);
    if (v != -1) {
      if (color[v] == WHITE) {
        color[v] = GRAY;
        d[v] = tt++;
        S.push(v);
      }
    } else {
      S.pop();
      color[u] = BLACK;
      f[u] = tt++;
    }
  }
}

void dfs() {
  for (int i = 0; i < n; i++) {
    color[i] = WHITE;
    nt[i] = 0;
  }
  tt = 0;

  for (int i = 0; i < n; i++) {
    if (color[i] == WHITE) dfs_visit(i);
  }
  for (int i = 0; i < n; i++) {
    cout << i + 1 << " " << d[i] + 1 << " " << f[i] + 1 << endl;
  }
}

int main() {
  int u, k, v;
  cin >> n;

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

  for (int i = 0; i < n; i++) {
    cin >> u >> k;
    u--;
    for (int j = 0; j < k; j++) {
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  dfs();
}


Measured memory_bytes: 3112
#include <stdio.h>

int main(void)
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a == b) printf ("%d\n", c);
    else if (a == c) printf ("%d\n", b);
    else printf ("%d\n", a);
    return (0);
}


Measured memory_bytes: 128
#include <stdio.h>

int
main()
{
	int n, x;
	int n1, n2, n3;
	int n_combinations;
	for (;;)
	{
		scanf("%d %d", &n, &x);

		if (n == 0 && x == 0)
			break;

		n_combinations = 0;
		for (n1 = 1;    n1 <= n; n1++)
		for (n2 = n1+1; n2 <= n; n2++)
		for (n3 = n2+1; n3 <= n; n3++)
			if (n1+n2+n3 == x)
				n_combinations++;
		printf("%d\n", n_combinations);
	}

	return 0;
}

Measured memory_bytes: 600
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

using ll = long long;


int main() {
    int N;
    cin >> N;
    set<char> s;
    char c;
    rep(i, N) {
        cin >> c;
        s.insert(c);
    }
    if (s.size() == 3) cout << "Three\n";
    else cout << "Four\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forna(i,a,n) for(int i =a; i < n; i++)
#define fornd(i,a) for (int i = (a)-1; i >= 0; i--)
#define pb push
#define fi first
#define se second
#define __ ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int unsigned lliu;
typedef long long int lli;
typedef pair<lli,lli> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;

int main(){__
    int n, aux;
    map<int, int> mapa;
    cin>>n;
    vi v(n);
    forn(i, n){
        cin>>v[i];
        mapa[v[i]]++;
    }
    lli suma=0;
    for(auto a: mapa){
        suma+=(1ll*a.second*(a.second-1))/2;
    }
    forn(i, n){
        cout<<suma-(mapa[v[i]]-1)<<"\n";
    }
    
}


Measured memory_bytes: 9600
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    cnt = 0
    temp = sys.maxsize
    for i in range(n):
        if a[i] <= temp:
            cnt += 1
            temp = a[i]
        else:
            pass
    print(cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 92988