akhauriyash/Code-Regression huggingface dataset:
N, M = list(map(int, input().split()))
P = [0] * M
S = [0] * M

WA = [0] * (100000+1)
AC = [0] * (100000+1)

for i in range(M):
    p, s = list(map(str, input().split()))
    p = int(p)
    if s == 'AC':
        AC[p] = 1
    else:
        if AC[p] == 0:
            WA[p] += 1

for i in range(100000+1):
    if AC[i] == 0:
        WA[i] = 0

print(sum(AC),end=' ')
print(sum(WA))

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

// https://github.com/atcoder-live/library/blob/master/mint.cpp
const std::int64_t mod = 1000000007;
struct mint {
    std::int64_t x; // typedef long long ll;
    mint(std::int64_t x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(std::int64_t t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
std::istream& operator>>(std::istream& is, const mint& a) { return is >> a.x;}
std::ostream& operator<<(std::ostream& os, const mint& a) { return os << a.x;}

int main() {
    ll N; cin >> N;
    mint a = 1;
    for (int i = 0; i < N; ++i) a *= 10;
    mint b = 1;
    for (int i = 0; i < N; ++i) b *= 9;
    mint c = 1;
    for (int i = 0; i < N; ++i) c *= 8;
    cout << a - mint(2) * b + c << endl;
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
int main(){
	int sampai, hasil, counter;
	for(int i=0; ; i++){
		scanf("%d %d", &sampai, &hasil);
		counter = 0;
		if(hasil==0 && sampai==0) break;
		for(int j=1; j<=sampai; j++){
			for(int k=j+1; k<=sampai; k++){
				for(int l=k+1; l<=sampai; l++){
					if(hasil==(j+k+l)) counter++;
				}
			}
		}
		printf("%d\n", counter);
	}
}


Measured memory_bytes: 3232
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
using namespace std;

#define ll long long int

const int MOD = 1000000007;

int max(int a, int b) {

	if (a > b)return a;
	else return b;

}
int main() {

	string A, B, C;

	cin >> A >> B >> C;
	cout << "A" << B[0] << "C" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
typedef pair<int,int> P;
typedef vector<int> vi;

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; }

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

int main(){
    ios::sync_with_stdio(false);
		ll a,v,b,w,t;
		cin >> a >> v;
		cin >> b >> w;
		cin >> t;
		if(v<=w){
			cout << "NO" << endl;
		} else{
			ll x=abs(a-b);
			ll y=v-w;
			if(x<=t*y){
				cout << "YES" << endl;
			} else{
				cout << "NO" << endl;

			}
		}
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

signed main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
//  #ifndef ONLINE_JUDGE
//     freopen ("INPUT.txt" , "r" , stdin);
//     freopen ("OUTPUT.txt" , "w" , stdout);
//  #endif

// -------------------------------------Code starts here---------------------------------------------------------------------     

   int n,k;
   cin>>n>>k;
   int h[n];
   int s=0;
   for(int i=0;i<n;i++)
   {
      cin>>h[i];
      s+=h[i];
   }   
   sort(h,h+n,greater<>());
   for(int i=0;i<min(n,k);i++)
   {
      s-=h[i];
   }
   cout<<s;

// -------------------------------------Code ends here------------------------------------------------------------------
     clock_t clk;
 	clk = clock();
 
    clk = clock() - clk;
 	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
 	return 0;
 }

Measured memory_bytes: 1792
#!/usr/bin/python3
# -*- coding: utf-8 -*-


"""
https://beta.atcoder.jp/contests/abc054/tasks/abc54_1
"""

import sys
import math
from inspect import currentframe

def debug_print(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]


delta = N - M
match = False

if delta == 0:
    match = (A==B)
else:
    for dx in range(delta):
        for dy in range(delta):
            window = [pixels[dx:dx+M] for pixels in A[dy:dy+M]]
            if window == B:
                match = True
                break

if match:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 4620
#include<iostream>

using namespace std;

int main(){
	int d;
	cin >> d;
	if(d == 25){
		cout << "Christmas" << endl;
	}
	if(d == 24){
		cout << "Christmas Eve" << endl;
	}
	if(d == 23){
		cout << "Christmas Eve Eve" << endl;
	}
	if(d == 22){
		cout << "Christmas Eve Eve Eve" << endl;
	}
}

Measured memory_bytes: 256
#include"iostream"
#include"cstdio"
using namespace std;
int main()
{
	int n,a[250],tot=0,t;
	cin>>n;
	for(int i=1;i<=n*2;i++)
		cin>>a[i];
	for(int i=1;i<n*2;i++)
		for(int j=i+1;j<=n*2;j++)
			if(a[i]>a[j])
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
	for(int i=1;i<=n*2;i++)
		if(i%2==1)
			tot=tot+a[i];
	cout<<tot;
	return 0;
}

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

int main() {
   int N, K, x;
   x = 1;
   cin >> N >> K;
   int i=0;
   while (2*x < x+K){
        if (i>=N) {break;}
   		x*=2;
        i++;
   }
   for (int j=0; j<N-i; j++){
     	x+=K;
   }
   cout << x << endl;
}


Measured memory_bytes: 3608
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define rep(i, j) for(int i = 0; i < j; i++)
using namespace std;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
struct axis { int x, y; };
int main()
{
	int N;  while (cin >> N && N != 0)
	{
		vector<axis> dat(N + 2);
		axis mx; mx.x = 0, mx.y = 0;
		axis mn; mn.x = 0, mn.y = 0;
		for(int i = 1; i < N; i++)
		{
			int pic = 0, dir = 0; cin >> pic >> dir;
			dat[i].x = dat[pic].x + dx[dir];
			dat[i].y = dat[pic].y + dy[dir];
			mx.x = max(mx.x, dat[i].x);
			mx.y = max(mx.y, dat[i].y);
			mn.x = min(mn.x, dat[i].x);
			mn.y = min(mn.y, dat[i].y);
		}
		printf("%d %d\n", abs(mx.x) + abs(mn.x) + 1, abs(mx.y) + abs(mn.y) + 1);
	}
}

Measured memory_bytes: 3088
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  string S;
  cin >> S;

  int N = S.length();
  vector<pair<int, int>> cnt1(N), cnt2(N);
  vector<int> ans(N);

  cnt1[0] = make_pair(1, 0);
  for(int i = 1; i < N; i++){
    if(S[i - 1] == 'L' && S[i] == 'R'){
      cnt1[i] = make_pair(1, 0);
    }else if(S[i - 1] == 'L' && S[i] == 'L'){
      continue;
    }else if(S[i] == 'R'){
      cnt1[i] = make_pair(cnt1[i - 1].second + 1, cnt1[i - 1].first);
    }else{
      ans[i] = cnt1[i - 1].second;
      ans[i - 1] = cnt1[i - 1].first;
    }
  }

  cnt2[N - 1] = make_pair(1, 0);
  for(int i = N - 2; i >= 0; i--){
    if(S[i + 1] == 'R' && S[i] == 'L'){
      cnt2[i] = make_pair(1, 0);
    }else if(S[i + 1] == 'R' && S[i] == 'R'){
      continue;
    }
    if(S[i] == 'L'){
      cnt2[i] = make_pair(cnt2[i + 1].second + 1, cnt2[i + 1].first);
    }else{
      ans[i] += cnt2[i + 1].second;
      ans[i + 1] += cnt2[i + 1].first;
    }
  }

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

}


Measured memory_bytes: 2624
#include <stdio.h>
#define MAX 100
#define W 0
#define G 1
#define B 2

int n,A[MAX][MAX];
int c[MAX],d[MAX],f[MAX],e;

void cdf_v(int u){
  int v;
  c[u]=G;
  d[u]=++e;
  for(v=0;v<n;v++){
    if(A[u][v]==0)continue;
    if(c[v]==W){
      cdf_v(v);
    }
  }
  c[u]=B;
  f[u]=++e;
}

void cdf(){
  int u;
  for(u=0;u<n;u++)c[u]=W;

  e=0;

  for(u=0;u<n;u++){
    if(c[u]==W)cdf_v(u);
  }
  for(u=0;u<n;u++){
    printf("%d %d %d\n",u+1,d[u],f[u]);
  }
}

int main (){
  int x,y,z,i,j;
  scanf("%d",&n);

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

  for(i=0;i<n;i++){
    scanf("%d%d",&x,&z);
    x--;
    for(j=0;j<z;j++){
      scanf("%d",&y);
      y--;
      A[x][y]=1;
    }
  }

  cdf();

  return 0;
}
  



Measured memory_bytes: 2088
#include<bits/stdc++.h> 
#define ll long long 
#define pb push_back
#define vec vector<int>
#define fo(i, n) for (int i = 0; i < n; i++)
#define so(v) sort(v.begin(), v.end())
#define fi first
#define se second
using namespace std;  

int main()
{
   int n;
   cin>>n;
   int sum=0;
   for(int i=0;i<=n;i++)
   {
       sum+=i;
   }
   cout<<sum;
}


Measured memory_bytes: 3576
void main() {
    auto w = readln.chomp.to!(dchar[]).sort!"a < b".group.assocArray;
    writeln(w.values.all!(t => t % 2 == 0) ? "Yes" : "No");
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

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

using namespace std;
typedef long long ll;

int mod=1e9+7;
const int N=4e6+5;
int k[10];
int main()
{

  string s[200];
  int n,l;
  cin>>n>>l;
  for(int i=0;i<n;i++)
  cin>>s[i];
  sort(s,s+n);
  for(int i=0;i<n;i++)
  cout<<s[i];
  return 0;
}


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

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<double> x(n),y(n);
  for(Int i=0;i<n;i++) cin>>x[i]>>y[i];

  auto dist=[&](Int i,Int j){
    return hypot(x[i]-x[j],y[i]-y[j]);
  };
  
  const double INF = 1e15;
  auto dp=make_v<double>(n,n);
  fill_v(dp,INF);
  dp[n-1][n-1]=0;
  for(Int i=n-1;i>0;i--){
    for(Int j=n-1;j>0;j--){
      Int k=min(i,j)-1;
      chmin(dp[i][j],dp[j][i]);
      chmin(dp[j][i],dp[i][j]);
      chmin(dp[k][j],dp[i][j]+dist(i,k));
      chmin(dp[i][k],dp[i][j]+dist(j,k));
      chmin(dp[k][j],dp[j][k]);
      chmin(dp[j][k],dp[k][j]);
      chmin(dp[i][k],dp[k][i]);
      chmin(dp[k][i],dp[i][k]);
    }
  }
  
  double ans=INF;
  for(Int i=0;i<n;i++){
    chmin(ans,dp[0][i]+dist(0,i));
    chmin(ans,dp[i][0]+dist(i,0));
  }
  cout<<ans<<endl;
  return 0;
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,K;
ll from[101010];
ll S[101010];
ll to[101010];
ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	from[0]=1;
	
	FOR(i,N) {
		FOR(x,101000) S[x]=((x?S[x-1]:0)+from[x])%mo;
		cin>>x;
		FOR(y,101000) from[y]=(S[y]+mo-((y-x-1)<0?0:S[y-x-1]))%mo;
	}
	
	cout<<from[K]<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

// syntax sugar: `for (int i = 0; i < N; ++i)`
#define rep(i, N) for (int i = 0; i < (int)(N); ++i)
// syntax sugar: `for (int i = 0; i < N; ++i)`
#define REP(type, name, beginValue, endCondValue) \
  for (type name = beginValue; name < endCondValue; ++name)
// syntax sugar: 多次元vector
#define VECTOR_DIM3(T, name, d1, d2, d3, initValue) \
    std::vector<std::vector<std::vector<T>>> name(d1, std::vector<std::vector<T>>(d2, std::vector<int>(d3, initValue)));
#define VECTOR_DIM2(T, name, d1, d2, initValue) \
    std::vector<std::vector<T>> name(d1, std::vector<T>(d2, initValue));
#define VECTOR_DIM1(T, name, d1, initValue) \
    std::vector<T> name(d1, initValue);


// ABC081C - Not so Diverse
int main(){
  int N, K; // N個のボール、K種類以下にしたい
  cin >> N >> K;

  std::unordered_map<int, int> data;
  int ai;
  rep(i,N) {
    cin >> ai;
    data[ai]++;
  }
  if (data.size() <= K) {
    cout << 0 << endl;
    return 0;
  }
  vector<int> elems;
  for (const auto& p: data) {
    elems.push_back(p.second);
  }
  int total = 0;
  std::sort(elems.begin(), elems.end());
  for (int i = 0; i < data.size()-K;++i) {
    total+=elems[i];
  }


  cout << total << endl;


  return 0;
}


Measured memory_bytes: 10312
N = int(input())
count_list = []

for i in range(1,N+1):
    count = 0
    c = 1
    while c > 0:
        if i % 2 == 0:
            count += 1
            i /= 2
        else:
            c -= 1
    count_list.append(count)

print(2**max(count_list))


Measured memory_bytes: 2940
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		//List<Integer> list=new ArrayList<Integer>();
		//Integer[] array = new Integer[m];
		int n= sc.nextInt();
		int answer = 0;
		List<Integer> list=new ArrayList<Integer>();
		for(int i=0;n-1>i;i++) {
			int a = sc.nextInt();
			list.add(a);
		}
		answer = list.get(0);
		for(int i=0;n-2>i;i++) {
			int a = list.get(i);
			int b = list.get(i+1);
			if(a<b)
				answer = answer+a;
			else
				answer = answer+b;
		}
		answer = answer+list.get(n-2);
		System.out.println(answer);
	}
}

Measured memory_bytes: 23892
#include<iostream>

using namespace std;

int main()
{
    // スペース区切りの整数の入力
    int a, b, k;
    cin >> a >> b >> k;
    int min;
    if(a > b) {
        min = b;
    } else {
        min = a;
    }

    int i = 0, count = 0, *n;
    n = new int[min];

    for(i = 1; i <= min; ++i) {
        if((a % i) == 0 && (b % i) == 0) {
            count++;
            n[count] = i;

        }
    }

    cout << n[count-k+1] << endl;

    return 0;
}

Measured memory_bytes: 888
w,h,x,y = map(int,input().split())
res = w * h / 2

if (w==1) or (h==1):
    print(res, 0)
else:
    if (x==(w//2)) and (y==(h//2)) and w%2==0 and h%2==0:
        print(res, 1)
    else:
        print(res, 0)

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

ll solve() {
    ll N, K, a;
    cin >> N >> K;
    atcoder::mcf_graph<ll, ll> g(2*N+2);
    int vs = 2*N, vt = 2*N+1;
    ll MA = 1e9;
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            cin >> a;
            g.add_edge(i, N+j, 1, MA-a);
        }
    }
    for ( int i = 0; i < N; i++ ) {
        g.add_edge(vs, i, K, 0);
        g.add_edge(N+i, vt, K, 0);
    }
    // 選ばない
    g.add_edge(vs, vt, N*K, MA);

    auto f = g.flow(vs, vt, N*K);
    
    vector<string> ans(N, string(N, '.'));
    for ( auto e : g.edges() ) {
        if ( e.from != vs && e.to != vt && e.flow > 0 ) {
            ans[e.from][e.to-N] = 'X';
        }
    }
    cout << (MA*K*N)-f.second << "\n";
    for ( auto ans1 : ans ) {
        cout << ans1 << "\n";
    }

    return 0;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 3932
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n); for(ll i = 0; i < (ll)n; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  ll n; cin >> n;
  
  rep(i, 10){
    rep(j, 10){
      if(i*j == n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3644
from bisect import bisect_left, bisect_right
from itertools import accumulate
def resolve():
    def shake_cnt(x):
        cnt = 0
        pos = 0
        for i in range(N):
            pos = bisect_left(A, x - A[i])
            cnt += N - pos
        return cnt < M # X以上の和がM個未満かどうか

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

    # 終了時にngにX-1,okにXが入っている。
    ng = 0
    ok = 10 ** 6
    while abs(ok - ng) > 1:
        mid = (ok + ng)//2
        if shake_cnt(mid):
            ok = mid
        else:
            ng = mid

    acc = [0] + list(accumulate(A))
    ans = 0
    for i in range(N):
        pos = bisect_right(A, ng - A[i])
        cnt = N - pos
        ans += cnt * A[i] + (acc[N] - acc[pos])
        M -= cnt
    ans += M * ng
    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 21288
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


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

    A, B, C = il()
    A, B = B, A
    A, C = C, A
    print(A, B, C)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;
using gragh = vector<vector<int>>;

int main() {
    ll ans = 0;
    int n,p;
    string s;
    cin>>n>>p>>s;
    map<int,int>modp;
    int now=0;
    vector<int>S(n+1,0);

    if(p == 2){

        for (int i = n-1; i >=0 ; --i) {
            int target = s[i]-'0';
            if(target%2==0){
                ans += i+1;
            }
        }
    }else if(p==5){
        for (int i = n-1; i >=0 ; --i) {
            int target = s[i]-'0';
            if(target ==0 || target==5){
                ans += i+1;
            }
        }
    }else{
        int ten = 1;
        modp[0]=1;
        for (int i = n-1; i >= 0; --i) {
            int target = s[i]-'0';
            now =  target * ten % p;
            S[i] = (S[i+1] + now) % p;
            ten *= 10;
            ten %= p;
            ans += modp[S[i]];
            modp[S[i]] ++;
        }
       
    }


    cout<<ans<<endl;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int K;
  cin >> K;
  char tar = '1';
  for(int i = 0; i < K && i < S.size(); i++) {
    if(S[i] != '1') {
      tar = S[i];
      break;
    }
  }
  cout << tar << endl;

  return 0;
}

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

int main(int argc, char *argv[]){
  string s;
  while(cin >> s){
    int ansj = 0, ansi = 0;
    for (int i = 0; i < s.length() - 2; i++) {
      if(s.substr(i, 3) == "JOI")ansj++;
      if(s.substr(i, 3) == "IOI")ansi++;
    }
    std::cout << ansj << std::endl;
    std::cout << ansi << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1212
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
int n,x;
int sz[55],p[55];
int get(int len,int pos){
	if(pos==1)return len==0?1:0;
	if(pos<=1ll+sz[len-1]){
		return get(len-1,pos-1ll);
	}
	if(pos==2ll+sz[len-1]){
		return p[len-1]+1ll;
	}
	if(pos<=2ll+2ll*sz[len-1]){
		int ret=p[len-1]+1ll;
		return ret+get(len-1,pos-2ll-sz[len-1]);
	}
	return 1ll+p[len-1]+p[len-1];
}
signed main(){
	cin>>n>>x;
	sz[0]=1;p[0]=1;
	for(int i=1;i<=50;i++){
		sz[i]=sz[i-1]*2ll+3ll;
		p[i]=p[i-1]*2ll+1ll;
	}
	cout<<get(n,x)<<endl;
	return 0;
}

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

typedef long long ll;
int modulo(int , int );
int minimum(int , int );
int fun(int * ,int ,int * ) ;


int main()
{
	int H;
	cin>>H;
	int h[H],memo[H];
	for(int i=0;i<H;i++)
	{
		cin>>h[i];
		memo[i]=-1;
	}
	cout<<fun(h,H-1,memo) ;
   return 0;	
}

int modulo(int a , int b)
{
	if(a>=b) return(a-b);
	return(b-a) ;
}

int minimum(int a , int b)
{
	if(a<=b) return(a) ;
	return(b) ;
}

int fun(int h[] , int n,int memo[])
{
	if(memo[n]!=-1) return(memo[n]) ;
	int temp1,temp2;
	if(n==0) 
	{
		return 0;
	}
	if(n==1)
	{
		return(modulo(h[1],h[0])) ;
	}
	
	temp1=fun(h,n-1,memo)+modulo(h[n],h[n-1]) ;
	temp2=fun(h,n-2,memo)+modulo(h[n],h[n-2]) ;
	memo[n]=minimum(temp1,temp2);
	return(memo[n]) ;
	
}

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

const int N = 100400,M = 1e9;

int n,k,s,m;
vector<int> ans;
    
void out() {
    for(auto x:ans) cout<<x<<" ";
    cout<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n>>k>>s;
    
    if(k==n) {
        for(int i=0;i<n;i++) ans.push_back(s);
        out();
        return 0;
    }
    if(k==0) {
        int t = s==M ? 1 : s+1;
        for(int i=0;i<n;i++) ans.push_back(t);
        out();
        return 0;
    }
    if(s==1) {
        for(int i=0;i<k;i++) ans.push_back(1);
        while(ans.size()<n) ans.push_back(M);
        out();
        return 0; 
    }
    for(int i=0;i<=k;i++) {
        if(i%2) {
            ans.push_back(1);
        }else {
            ans.push_back(s-1);
        }
    }
    int t = s==M ? 2 : s+1;
    while(ans.size()<n) ans.push_back(t);
    out();



    return 0;
}




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

int main(int argc, char const *argv[])
{
	int a,b;
	string s;

	cin >> a >> b;
	
	if (a > b) s = "a > b";
	else if (a < b) s = "a < b";
	else s = "a == b";

	cout << s << endl;

	return 0;
}



Measured memory_bytes: 3136
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

int main()
{
    ll n,arr[100005],dp[100005];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    dp[0]=0;
    dp[1]=abs(arr[0]-arr[1]);
    if(n>2) dp[2]=abs(arr[0]-arr[2]);
    for(int i=3;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
    }
    cout<<dp[n-1]<<'\n';
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pii pair<int, int>
#define ll long long
#define INF 1000000000
#define MAXN 3010
#define MAXL 22

using namespace std;

int bit[MAXN], N, nums[MAXN];

void add(int i)
{
	for(; i; i -= (i & -i))
		bit[i]++;
}

int query(int i)
{
	int r = 0;
	for(; i < MAXN; i += (i & -i))
		r += bit[i];
	return r;
}

int query(int A, int B)
{
	//Maiores que B - A
	int x = query(B - A);
	//menores que A + B
	int y = query(A + B - 1);

	int z = y - x;

	return max(0, z - 3);
}

int main(int argc, char const *argv[])
{
	optimize;

	cin >> N;

	for(int i = 0; i < N; i++)
		cin >> nums[i];

	sort(nums, nums + N);

	ll r = 0LL;

	for(int i = 0; i < N; i++)
	{
		for(int j = i + 1; j < N; j++)
		{
			int k = query(abs(nums[j] - nums[i]) + 1);
			// cout << nums[i] << " " << nums[j] << " == " << k << endl;
			r += k;
		}

		add(nums[i]);
	}

	// r /= 3;
	cout << r << endl;

	return 0;	
} 	

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=2e4+7; 
ll p[N],inv[N],n,k;
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int main(){
	cin>>n>>k;
	p[0]=inv[0]=1;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*i%mod;
	inv[n]=qpow(p[n],mod-2);
	for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=1;i<=k;i++){
		if(n-k-i+1<0) cout<<0<<endl;
		else{
			ll ans=1;
			ans=ans*p[k-1]*inv[k-i]%mod*inv[i-1]%mod;
			ans=ans*p[n-k+1]%mod*inv[n-k-i+1]%mod*inv[i]%mod;
			cout<<ans<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#define FOR(i,a,n) for(i=(a);i<(n);i++)
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define LOCAL
#ifdef LOCAL
    #define DEBUG(...) printf(" "__VA_ARGS__)
#else
    #define DEBUG(...)
#endif /* LOCAL */
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int x[100000];
int main(void)
{
	int n,k,i;
	ll n1,n2,t,res=1000000000000000LL;
	scanf("%d%d",&n,&k);
	FOR(i,0,n) scanf("%d",&x[i]);
	FOR(i,0,n-k+1){
		if(x[i]>=0&&x[i+k-1]>=0)  t=MAX(x[i],x[i+k-1]);
		else if(x[i]<=0&&x[i+k-1]<=0)  t=-MIN(x[i],x[i+k-1]);
		else{
			n1=abs(x[i]),n2=abs(x[i+k-1]);
			if(n1>n2) t=n1+2*n2;
			else t=2*n1+n2;
		}
		res=MIN(res,t);
	}
	printf("%lld\n",res);
	return 0;
}
    
    
    
    
    

Measured memory_bytes: 512
n=int(input())
w1=list(input())
s="S"
w="W"
o="o"
x="x"
l=[[s,s],[s,w],[w,w],[w,s]]
for j in range(4):
    for i in range(1,n):
        if w1[i]==o:
            if l[j][-1]==s:
                if l[j][-2]==s:
                    l[j].append(s)
                else:
                    l[j].append(w)
            else:
                if l[j][-2]==s:
                    l[j].append(w)
                else:
                    l[j].append(s)
        else:
            if l[j][-1]==s:
                if l[j][-2]==s:
                    l[j].append(w)
                else:
                    l[j].append(s)
            else:
                if l[j][-2]==s:
                    l[j].append(s)
                else:
                    l[j].append(w)
b=False
for i in range(4):
  if l[i][0]==l[i][-1] and not b:
    del l[i][-1]
    if l[i][0]==s:
      if (l[i][1]==l[i][-1] and w1[0]==o) or (l[i][1]!=l[i][-1] and w1[0]==x):
        answer=l[i]
        b=True
        break
    else:
      if (l[i][1]!=l[i][-1] and w1[0]==o) or (l[i][1]==l[i][-1] and w1[0]==x):
        answer=l[i]
        b=True
        break
if not b:
    print(-1)
else:
    print("".join(answer))

Measured memory_bytes: 7376
#include <stdio.h>
#include <math.h>
 
typedef struct{
  double x;
  double y;
} Point;
 
void Koch(int, Point, Point);
 
int main()
{
  int n;
  Point p1, p2;
 
  scanf("%d", &n);
 
  p1.x = 0;
  p2.x = 100;
  p1.y = 0;
  p2.y = 0;
 
  printf("%.8f %.8f\n", p1.x, p1.y);
  Koch(n, p1, p2);
  printf("%.8f %.8f\n", p2.x, p2.y);
 
  return 0;
}
 
void Koch(int n, Point p1, Point p2)
{
  Point s, t, u;
   
  if( n == 0 ) return;
 
  s.x = (2.0 * p1.x + 1.0 * p2.x) / 3;
  s.y = (2.0 * p1.y + 1.0 * p2.y) / 3;
  t.x = (1.0 * p1.x + 2.0 * p2.x) / 3;
  t.y = (1.0 * p1.y + 2.0 * p2.y) / 3;
  u.x = (t.x - s.x) * cos(M_PI/3) - (t.y - s.y) * sin(M_PI/3) + s.x;
  u.y = (t.x - s.x) * sin(M_PI/3) + (t.y - s.y) * cos(M_PI/3) + s.y;
 
  Koch(n-1, p1, s);
  printf("%.8f %.8f\n", s.x, s.y);
  Koch(n-1, s, u);
  printf("%.8f %.8f\n", u.x, u.y);
  Koch(n-1, u, t);
  printf("%.8f %.8f\n", t.x, t.y);
  Koch(n-1, t, p2);
   
}

Measured memory_bytes: 640
#!/usr/bin/env python3
import heapq

N = int(input())
A = [int(s) for s in input().split()]
A_s = zip(list(range(N)), A)
A_s = sorted(A_s, key=lambda x: x[1], reverse=True)

kokoti = 0
kokoti += A_s[0][1]

#h = list(map(lambda x: (-1*x[0], x[1]), A_s))
h = []
heapq.heapify(h)  # リストを優先度付きキューへ
heapq.heappush(h, (-A_s[1][1]))
heapq.heappush(h, (-A_s[1][1]))

for i in range(2, N):
    x = heapq.heappop(h)  # 最大値の取り出し
    kokoti += (-x)
    #heapq.heappush(h, (-A_s[i][1], (a[0], A_s[i][0])))  # 要素の挿入
    #heapq.heappush(h, (-A_s[i][1], (A_s[i][0], a[1])))
    heapq.heappush(h, (-A_s[i][1]))  # 要素の挿入
    heapq.heappush(h, (-A_s[i][1]))

print(kokoti)

Measured memory_bytes: 47584
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 10000007

int main()
{
    ll n;
    cin>>n;
    ll cost[n+1];
    ll dp[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>cost[i];

    }
    dp[n]=0;
    dp[n-1]=abs(cost[n]-cost[n-1]);

    for(int i=n-2;i>0;i--)
    {
        //if(i!=(n-1))
        dp[i]=min((dp[i+1]+abs(cost[i+1]-cost[i])),(dp[i+2]+abs(cost[i+2]-cost[i])));
    }
    cout<<dp[1]<<endl;
}


Measured memory_bytes: 5144
#include<bits/stdc++.h>
using namespace std;
int main(){
    const int mod=1000000007;
    string K;
    cin>>K;
    int d;
    cin>>d;
    vector<int>n;
    for(int i=0;i<K.size();i++)n.push_back(K[i]-'0');
    int s=n.size();
    long long dp[s][d][2]={};//dp[i][j][k]:i桁見て、mod d=jで、10方向遷移が(k=0:出来る、1:出来ない)
    for(int i=0;i<n[0];i++)dp[0][i%d][0]++;
    dp[0][n[0]%d][1]++;
    for(int i=0;i<s-1;i++){
        for(int j=0;j<d;j++){
            for(int k=0;k<=9;k++){//10方向遷移が可能
                dp[i+1][(j+k)%d][0]+=dp[i][j][0]%mod;
            }
            for(int k=0;k<n[i+1];k++){//10方向遷移が不可能
                dp[i+1][(j+k)%d][0]+=dp[i][j][1]%mod;
            }
            dp[i+1][(j+n[i+1])%d][1]+=dp[i][j][1]%mod;
        }
    }
    cout<<(dp[s-1][0][0]+dp[s-1][0][1]-1)%mod<<endl;
    return 0;
}

Measured memory_bytes: 16000
/**
 *    author:  tourist
 *    created: 29.12.2019 23:00:19       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  b = min(b, 2 * c);
  a = min(a, 2 * c);
  long long ans = min(a + b, 2 * c) * min(x, y);
  ans += a * (x - min(x, y));
  ans += b * (y - min(x, y));
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    #define SpeeD ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #define ll long long
    //pair<int, int> *p=new pair<int, int>[n];
    //std::vector<pair<int,int>> vp;
    //v.push_back(make_pair(x,y))
    //pair<int, int> p[1001];
    //string *s=new string [n];
     
    //int freq[e];
    //freq[a[i]-'a']++; freq[a[i]]++;
    using namespace std;  
        ll t,c1,c2,c3,sum,m,mn,k;
        vector<int>v1,v2,v3;

    int main(void)
    {
        SpeeD;  
string s;
cin>>s;
for (int i=0;i<s.length();i++)
cout<<"x";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
  long long res,n,k; cin>>n>>k;
  res=(k*(k-1)*(2*k-1)-(n+1)*(n+2)*(2*n+3))/6+(n+1)*((n+1)*(n+2)-k*(k-1))/2+n-k+2;
  cout<<res%1000000007;
  return 0;
}

Measured memory_bytes: 3636
package main
 
import (
	"fmt"
)
 
func main() {
    var h, w, a, b int
	fmt.Scan(&h, &w, &a, &b)
	s0 := ""
	s1 := ""
 
	for j := 0; j < w-a; j++ {
		s0 += "1"
		s1 += "0"
	}
	for j := 0; j < a; j++ {
		s0 += "0"
		s1 += "1"
	}
 
	for i := 0; i < h-b; i++ {
		fmt.Println(s0)
	}
	for i := 0; i < b; i++ {
		fmt.Println(s1)
	}
}

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


int main(){
    ll l,r,d;cin>>l>>r>>d;
    ll cn=0;
    rep(i,1,102){
        if(i*d>=l&&i*d<=r)cn++;
    }
    cout<<cn<<endl;
}

    









Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
typedef long long ll;
#define lim 1000000000000000001


ll root(ll x,vector<ll>&v)
{
    while(v[x]!=x)
    {
        v[x]=v[v[x]];
        x=v[x];
    }
    return x;
}

int main()
{
     fast;
    string s;
    cin>>s;
    ll cn=0,c2=0;
    for(int i=0;i<3;i++)
    if(s[i]=='A')
    cn++;
    else
    {
        c2++;
    }
    
    if(cn&&c2)
    cout<<"Yes\n";
    else
    {
        cout<<"No";
    }
    
     

    return 0;
}

Measured memory_bytes: 384
n = input()
s = list(input())
line = [0 for _ in range(0,len(s)+1)]
for i in range(0,len(s)):
    if s[i] =="W":
        line[0] += 1
        line[i+1] -= 1
    if s[i] =="E":
        line[i] += 1
        line[len(s)] -= 1
for i in range(0,len(line)-1):
    line[i+1] += line[i]
print(len(s) - max(line))


Measured memory_bytes: 17784
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T &a){int t = 0;for(auto itr :a){if(t++)cout << " "; cout << itr;} cout <<endl; }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    //    std::ios_base::sync_with_stdio(false);
    //    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    int val = n / k;
    val *= val* val;
    if(k % 2){
        cout << val << endl;
    } else {
        int cnt = 0;
        for(int i = k/2 ; i <= n; i += k)++cnt;
        cout << val + cnt * cnt * cnt << endl;
    }
}




Measured memory_bytes: 256
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
//#include <vector>
//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 
 
int getIntSubstr(string s,int start_index,int length){
    return atoi(s.substr(start_index,length).c_str());
}

int main(){

    string S;
    cin >> S;

    int min;
    min=5000;
    int tmp;
    for( int ni = 0 ; ni < S.length() - 2 ; ni++ ){
        tmp = getIntSubstr(S,ni,3);
        if(min > abs(753-tmp)){
            min = abs(753-tmp);
        }
    }
    cout << min;
}

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

int main(){
    int H,W;
    while(1){
    cin >> H >> W;
    if(H==0&&W==0) break;
    
    for(int i=0; i<H;i++ ){
        for(int j=0; j<W;j++){
        cout << "#" ;
       }
       cout <<"\n";
    }
    cout <<endl;
   }
   return 0;
}


Measured memory_bytes: 3096
N = int(input())
A = [int(x) for x in input().split()]
A.append(0)
f = [0] * N
for i in range(N):
    if A[i] < A[i+1]:
        f[i] = 1
    elif A[i] > A[i+1]:
        f[i] = 2
cnt = 1000
stock = 0
prev = 0
for i in range(N):
    if stock == 0 and prev != 1 and f[i] == 1:
        stock = cnt // A[i]
        cnt %= A[i]
    elif prev != 2 and f[i] == 2:
        cnt += stock * A[i]
        stock = 0
    prev = f[i]
print(cnt)


Measured memory_bytes: 61976
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S,T;
  cin>>S>>T;
  int N=S.size(),a=0;
  for(int i=0;i<N;i++){
    string A,B;
    for(int j=0;j<i;j++){
      A.push_back(S.at(j));
    }
    for(int j=i;j<N;j++){
      B.push_back(S.at(j));
    }
    string C=B+A;
    if(C==T){
      a=1;
      break;
    }
  }
  if(a==0)
    cout<<"No"<<endl;
  else
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 3568
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)
def run():
    N,M,K = map(int, input().split())
    mod = 998244353
    modM = [1]
    for x in range(1,N):
        val = modM[-1] * (M-1)
        val %= mod
        modM.append(val)

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        if n < 2:
            return ret[:n+1]

        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(N-1, mod)

    combs = []
    def comb_mod(n, a, mod):
        """
        return: [n, a] % mod
        Note: mod must be a prime number
        """
        combs.append(1)
        ret = 1
        for i in range(1, a+1):
            ret *= n-i+1
            ret %= mod
            ret *= inv[i]
            ret %= mod
            combs.append(ret)
        return None
    comb_mod(N-1, N-1, mod)


    ret = 0
    for k in range(K+1):
        tmp = (modM[N-1-k] * M) % mod
        tmp *= combs[k]
        tmp %= mod
        ret += tmp
        ret %= mod
    print(ret%mod)

if __name__ == "__main__":
    run()

Measured memory_bytes: 32600
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define p(x) cout << x << endl;

#define MOD 1000000007
#define PI 3.14159265359

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

    int n;
    cin >> n;
    int p[n];
    rep(i, n) cin >> p[i];

    sort(p, p + n);

    int num = p[n - 1] / 2;

    int sum = 0;
    rep(i, n - 1){
        sum += p[i];
    }

    int ans = sum + num;

    p(ans);
}

Measured memory_bytes: 256
using System;
using System.Linq;

public class Test
{
	public static void Main()
	{
		
		string alpha = Console.ReadLine();
		string hantei = "qwertyuiopasdfghjklzxcvbnm";
		int counter = 0;
		string b = "a";
		for(int i=0;i!=26;i++){
			b = hantei.Substring(i,1);
			if(alpha==b){
				counter++;
			}
		}
		
		if(counter==0){
			Console.WriteLine("A");
		}else{
			Console.WriteLine("a");
		}
	}
}

Measured memory_bytes: 25876
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define int ll
using pint = pair<int,int>;
using Graph = vector<vector<int>>;
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 1e10; //10^10
const double PI = acos(-1.0L);
const int dx[4] = {1, 0, -1, 0} , dy[4] = {0, 1, 0, -1};
/*mod逆元*/long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}
template< typename T >T mod_pow(T x, T n, T p=MOD) {T ret = 1;while(n > 0) {if(n & 1) (ret *= x) %= p;(x *= x) %= p;n >>= 1;}return ret;}
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}

//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int a,b; cin >> a >> b;
    int ans = 1;
    while(a*2<=b){
        a*=2;
        ans++;
    }
    out(ans);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
	int W, H, x, y, r;
	std::cin >> W >> H >> x >> y >> r;
	if ((x >= r) && (y >= r) && ((x + r) <= W) && ((y + r) <= H))
	{
		std::cout << "Yes" << std::endl;
	}
	else
	{
		std::cout << "No" << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3100
import java.util.*;

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

    int n = sc.nextInt();
    long[] A = new long[n];

    for (int i=0; i < n; i++) {
      A[i] = sc.nextLong() - i - 1;
    }

    Arrays.sort(A);

    long b = A[n/2];
    long ans = 0;

    for (int i=0; i < n; i++) {
      ans += Math.abs(A[i] - b);
    }

    System.out.println(ans);
  }
}


Measured memory_bytes: 67116
#include <stdio.h>
#include <math.h>

int main(){
  double x1,y1,x2,y2;

  scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

  printf("%f\n",sqrt((pow(x2-x1,2.0)+pow(y2-y1,2.0))));


  return 0;
}



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

int main() {
  char a;
  cin >> a;
  int i;
  i = (int)(a-'A'+1);
  
  if(1<=i && i<=26) cout << 'A' << endl;
  else cout << 'a' << endl;
	return 0;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
#define REP(i,m,n) for(LL i=(m);i<(n);i++)

int main(){
  LL n,k,ans=0;
  cin >> n >> k;
  VLL x(n);
  REP(i,0,n){
    cin >> x.at(i);
    ans += min(x.at(i), k-x.at(i))*2;
  }
  
  
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3628
import math

def solve():
    n, a, b = list(map(int, input().split()))
    h = [int(input()) for _ in range(n)]
    h = sorted(h)

    def is_enough(t):
        t_check = 0
        for hh in h:
            hh -= b*t
            if hh > 0:
                t_check += math.ceil(hh/(a-b))
        if t_check > t: return False
        else: return True

    t_min = 1
    t_max = h[-1]//b+1 # number of spell
    while t_min != t_max-1:
        t_next = (t_min+t_max)//2
        if is_enough(t_next):
            t_max = t_next
        else:
            t_min = t_next
        # print(t_min, t_max)

    if is_enough(t_min): print(t_min)
    else: print(t_max)
    return

solve()

Measured memory_bytes: 8300
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <queue>
#include <cstdio>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif // LOCAL

    char str[105][105];
    int h,w;
    scanf("%d%d",&h,&w);
    for(int i=1;i<=h;i++)
        scanf("%s",str[i]);
    for(int i=1;i<=h;i++)
    {
        printf("%s\n",str[i]);
        printf("%s\n",str[i]);
    }
    return 0;
}


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

int main(){
	string str;
	char tmp[10001];
	
	while(scanf("%s", tmp) != EOF){
		str = tmp;

		int joi = 0;
		int ioi = 0;

		for (int i = 0; i < str.size() - 2; i++){
			if(str.substr(i, 3) == "JOI"){
				joi++;
			}else if(str.substr(i, 3) == "IOI"){
				ioi++;
			}
		}

		printf("%d\n%d\n", joi, ioi);
	}

	return 0;
}

Measured memory_bytes: 1092
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        if (a<10&&a>0 && b<10&&b>0) {
            System.out.println(a*b);
        }else{
            System.out.println(-1);
        }
    }
    
    private static void sort(int[] d, int left, int right){
        if(left>=right){return;}
        int p = d[(left+right)/2];
        int l=left, r=right;
        int tmp;
        while(l<=r){
            while(d[l]>p){l++;}
            while(d[r]<p){r--;}
            if(l<=r){
                tmp=d[l];
                d[l] = d[r];
                d[r] = tmp;
                l++; r--;
            }
        }
        sort(d, left, r);
        sort(d, l, right);
    }
}

Measured memory_bytes: 23764