akhauriyash/Code-Regression huggingface dataset:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int cost=1000000;
    for(int i=-100;i<=100;i++){
        int ct=0;
        for(int j=0;j<n;j++)
            ct+=(a[j]-i)*(a[j]-i);
        chmin(cost,ct);
    }
    cout<<cost<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------







Measured memory_bytes: 256
def main():
    from itertools import product
    n, a, b, c, *l = map(int, open(0).read().split())
    k = ['A', 'B', 'C', 'D']
    cost = []
    for abcd in product(k, repeat=n):
        s, t, u = [], [], []
        for p, q in zip(abcd, l):
            if p == 'A':
                s.append(q)
            elif p == 'B':
                t.append(q)
            elif p == 'C':
                u.append(q)
        tmp = 0
        for p, q in zip([a, b, c], [s, t, u]):
            tmp += abs(p - sum(q)) + 10 * (len(q) - 1)

        if len(s) > 0 and len(t) > 0 and len(u) > 0:
            cost.append(tmp)

    ans = min(cost)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5084
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>


using namespace std;
#define MAX 100000

int main(){
    int n, m, d;

    scanf("%d%d%d", &n, &m, &d);

    double ans;

    ans = ((n - d) * 2) / (pow(n, 2)) * (m - 1);
    if (d == 0) ans /= 2;

    printf("%.10lf", ans);

    return 0;
}

Measured memory_bytes: 128
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int a[200005],b[200005],c[200005];
int main ( ) {
	int n,m,i,j,k,s=0;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		if (a[i]-b[a[i]]>0) {
			c[a[i]-b[a[i]]]++;
			if (c[a[i]-b[a[i]]]>1) s++;
			b[a[i]]++;
		}
		else {
			c[1]++;
			if (c[1]>1) s++;
			b[a[i]]++;
		}
	}
	for (i=1;i<=m;i++) {
		int x,y,t;
		scanf("%d%d",&x,&y);
		t=a[x];a[x]=y;
		if (t-b[t]+1>0) {
			b[t]--;
			c[t-b[t]]--;
			if (c[t-b[t]]!=0) s--;
		}
		else {
			b[t]--;
			c[1]--;
			if (c[1]!=0) s--;
		}
		if (y-b[y]>0) {
			c[y-b[y]]++;
			if (c[y-b[y]]>1) s++;
			b[y]++;
		}
		else {
			c[1]++;b[y]++;
			if (c[1]>1) s++;
		}
		printf("%d\n",s);
	}
	return 0;
}
/*
Sample Input 1
5 3
1 1 3 4 5
1 2
2 5
5 4
Sample Output 1
0
1
1
Sample Input 2
4 4
4 4 4 4
4 1
3 1
1 1
2 1
Sample Output 2
0
1
2
3
Sample Input 3
10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7
Sample Output 3
1
0
1
2
2
3
3
3
3
2
*/

Measured memory_bytes: 3712
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        abc156_b solver = new abc156_b();
        solver.solve(1, in, out);
        out.close();
    }

    static class abc156_b {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long N = in.nextLong();
            int K = in.nextInt();
            String comp = Long.toString(N, K);
            out.println(comp.length());

        }

    }
}



Measured memory_bytes: 22868
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) (((a) >> (b)) & 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int N;
  while (cin >> N, N) {
    static char c[1010][1010];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        cin >> c[i][j];
      }
    }

    //初期化
    static int dp[1010][1010]; // dp[y][x]:=上からy,左からjの点から左上に伸ばして作れる最大の正方形。
    m0(dp);
    for (int i = 0; i < N; i++) {
      if (c[i][0] != '*') dp[i][0] = 1;
      if (c[0][i] != '*') dp[0][i] = 1;
    }

    int ans = 0;
    for (int i = 1; i < N; i++) {
      for (int j = 1; j < N; j++) {
        if (c[i][j] == '*') {
          dp[i][j] = 0;
        } else {
          dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
        }
        chmax(ans, dp[i][j]);
      }
    }

    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 11928
#include <stdio.h>
 
int main(void)
{
  
  char buf[100];
  int x;
  
  fgets(buf, sizeof(buf), stdin);
  sscanf(buf, "%d", &x);
  
  int y = x % 1000;
  int z = 1000 - y;
  
  if(y != 0){
      printf("%d\n", z);
  } else {
    printf("0");
  }
}

Measured memory_bytes: 1752
(let* ((n (read))
       (m (read))
       (k (make-array (list (1+ m))))
       (s (make-array (list (1+ m) (1+ n))))
       (p (make-array (list (1+ m))))
       (ans 0))
  (loop :for i :from 1 :to m
        :do (setf (aref k i) (read))
        :do (loop :for j :from 1 :to (aref k i)
                  :do (setf (aref s i j) (read))))
  (loop :for i :from 1 :to m
        :do (setf (aref p i) (read)))
  (defun check (cnt sw)
    (if (= cnt (+ n 1))
        (if (= (loop :for i :from 1 :to m
                     :if (= (mod (loop :for j :from 1 :to (aref k i)
                                       :sum (aref sw (aref s i j))) 
                                 2)
                            (aref p i))
                     :sum 1)
               m)
              (incf ans))
        (loop :for a :from 0 :to 1
              :do (setf (aref sw cnt) a)
              :do (check (1+ cnt) sw))))
  (check 1 (make-array (list (1+ n))))
  (format t "~A~%" ans))


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

using namespace std;
typedef long long ll;

int main(){
    ll h, w;
    cin >> h >> w;
    vector<vector<ll>> m(h, vector<ll>(w, 0));
    vector<ll> wsum(h, 0);
    vector<ll> hsum(w, 0);
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            char c;
            cin >> c;
            if(c == '#'){
                m.at(i).at(j) = 1;
                wsum.at(i) += 1;
                hsum.at(j) += 1;
            }
        }
    }

    ll newh = 0, neww = 0;
    for(ll x : wsum){ newh += (x > 0); }
    for(ll x : hsum){ neww += (x > 0); }

    for(int i = 0; i < h; ++i){
        if(wsum.at(i) == 0){ continue; }
        for(int j = 0; j < w; ++j){
            if(hsum.at(j) == 0){ continue; }
            if(m.at(i).at(j)){
                cout << '#';
            }else{
                cout << '.';
            }
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
ll mod=pow(10,9)+7;
ll K,ans;
mat G;

struct Permutation{
    vec n,n_rev;

    Permutation(int N){
        n.resize(N+1);
        n_rev.resize(N+1);
        n[0]=1;n_rev[1]=1;
        for(int i=1;i<=N;i++){
            n[i]=((ll)i*n[i-1])%mod;
        }
        for(int i=2;i<=N;i++){
            n_rev[i]=matpow(n[i],mod-2);
        }
    }

    //累乗(aのk乗)
    ll matpow(ll a,int k){
        ll dp=1,mt=a;
        while(k>0){
            if(k & 1)dp=(dp*mt)%mod;
            mt=(mt*mt)%mod;
            k/=2;
        }
        return dp;
    }

    ll perm(int N,int r){  
        if(N<r)return 0;
        if(N==r)return n[N];
        return (n[N]*n_rev[N-r])%mod;
    }
};

Permutation Perm(100000);
void DFS(int start,int s,int p){
    int r=G[s].size()-1;
    if(s==start){
        ans=(ans*Perm.perm(K-1,r+1))%mod;       
    }
    else{
        ans=(ans*Perm.perm(K-2,r))%mod;
    }
    for(int t:G[s]){
        if(t==p)continue;
        DFS(start,t,s);
    }
}

int main(){
    int N;cin>>N>>K;
    if(K==1){
        if(N==1)cout<<1<<endl;
        else    cout<<0<<endl;
        return 0;
    }
    G.resize(N+1);
    int a,b;
    for(int i=1;i<N;i++){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ans=K;
    DFS(1,1,0);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 10752
#include <stdio.h>

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

    int i;
    int input;
    int weight[11] = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    while (scanf("%d", &input) != EOF) {
        int idx = 0;
        int n[11] = {0};
        for (i = 10; i > 0; i--) {
            if (input - weight[i] >= 0) {
                //printf("%dが含まれる\n", weight[i]);
                input -= weight[i];
                n[i]++;
                if (idx < i) {
                    idx = i;
                }
            }
        }
        for (i = 1; i <= 10; i++) {
            if (n[i]) {
                printf("%d", weight[i]);
                if (i != idx) {
                    printf(" ");
                }
            }
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 600
import sys

def ii2ss(n):
    return [sys.stdin.readline() for _ in range(n)]

def sp2nn(sp, sep=' '):
    return [int(s) for s in sp.split(sep)]

def ss2nn(ss):
    return [int(s) for s in list(ss)]

def count(hh, n):
    c = 0
    b = False
    for h in hh:
        if h >= n:
            if b == False:
                b = True
                c += 1
        else:
            if b == True:
                b = False
    return c
    
def main(ss):
    hh = sp2nn(ss[1])
    total = 0
    n = 1
    while True:
        c = count(hh, n)
        if c == 0:
            break
        total += c
        n += 1
    print(total)

main(ii2ss(2))

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

int sumEachDigit(int);

int main(void) {
    int N,A,B;
    cin>>N>>A>>B;
    int result = 0;
    for (int i = 1; i <= N; i++) {
        int s = sumEachDigit(i);
        if (A <= s && s <= B) result += i;
    }
    cout << result << endl;
    return 0;
}

int sumEachDigit(int C) {
    int result = 0;
    while (C > 0) {
        result += C % 10;
        C /= 10;
    }
    return result;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=2e5+10,mod=998244353;
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int n,R[maxn],L[maxn];
int b[maxn],c[maxn];
long long f[maxn];
struct Node
{
    int x,d;
}a[maxn];
bool operator <(Node A,Node B) { return A.x<B.x;}

int lowbit(int x) {return x&-x;}
void add(int x,int k)
{
    while(x<=n)
        c[x]=max(c[x],k),x+=lowbit(x);
}
int query (int x) 
{
	int res=0;
    while(x>0)
        res=max(res,c[x]),x-=lowbit(x);
    return res;
}

int main()
{
    #ifdef __LOCAL__
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    scanf("%d",&n);
    _rep(i,1,n)
        scanf("%d%d",&a[i].x,&a[i].d);
    sort(a+1,a+n+1);

    // R[n]=n;
    // for(int i=1;i<n;i++)
    // {
    //     int j=i,far=a[i].x+a[i].d;
    //     while(far>a[j+1].x&&j<n)
    //     {
    //         far=max(far,a[j+1].x+a[j+1].d);    
    //         j++;
    //     }                
    //     R[i]=j;
    // }

    _rep(i,1,n)
        b[i]=lower_bound(a+1,a+1+n,(Node){a[i].x+a[i].d,0})-a-1;    

    //i~b[i]-1
    // _rep(i,1,n)
    // {
    //     int mx=b[i];
    //     for(int j=i;j<=mx;j++)
    //     {
    //         d[i]=max(d[i],b[j]);
    //         if(b[j]>mx)
    //             mx=b[j];
    //     }
    // }
    // for(int i=1;i<=n;i++)
    //     cout<<R[i]<<" "<<d[i]<<endl;

    for(int i=n;i>=1;i--)
    {
        L[i]=max(i,query(b[i]));
        add(i,L[i]);
        // for(int i=1;i<=n;i++)
        //     cout<<c[i]<<" ";
        // cout<<endl;
    }

    // for(int i=n;i>=1;i--)
    //     cout<<i<<" "<<R[i]<<" "<<L[i]<<endl;

    f[n+1]=1;
    for(int i=n;i>=1;i--)
        f[i]=(f[i+1]+f[L[i]+1])%mod;

    cout<<f[1]<<endl;
    return 0;
}

Measured memory_bytes: 6400
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;



int main(){
    int n, m, q;
    int a[55], b[55], c[55], d[55];
    cin >> n >> m >> q;
    for(int i = 0;i < q;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    vector<int> vec(n+m-1, 1);
    for(int i = 0;i < m-1;i++)vec[i] = 0;
    int ans = 0;
    do{
        int zero_cnt = 0;
        int score = 0;
        vector<int> A;
        for(int i = 0;i < n+m;i++){
            if(vec[i] == 0)zero_cnt++;
            else A.push_back(zero_cnt + 1);
        }
        for(int i = 0;i < q;i++){
            if(A[b[i]] - A[a[i]] == c[i])score += d[i];
        }
        ans = max(ans, score);
    }while(next_permutation(vec.begin(), vec.end()));

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


Measured memory_bytes: 3580
import numpy as np

H, W = map(int, input().split())

A = np.zeros((H, W), dtype=np.int)

for i in range(H):
    s = input()
    c = [j for j in range(W) if s[j] == "#"]
    A[i][c] = 1

while True:
    # find x
    a = A.sum(axis=0)
    if np.any(a == 0):
        del_lines = np.where(a == 0)[0]
        A = np.delete(A, del_lines, axis=1)
        continue

    # find y
    a = A.sum(axis=1)
    if np.any(a == 0):
        del_lines = np.where(a == 0)[0]
        A = np.delete(A, del_lines, axis=0)
        continue

    # break if no white line
    break

A = A.tolist()
num2char = {0: ".", 1: "#"}
for l in A:
    s = list(map(lambda x: num2char[x], l))
    print("".join(s))

Measured memory_bytes: 12516
n = int(input())
for i in range(1, n + 1):
	if i % 3 == 0:
		print(' %d' % i, end="")
	else:
		j = i
		while j > 0:
			if j % 10 == 3:
				print(' %d' % i, end="")
				break
			j //= 10
print("")



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

int main() {
    int N;
    cin>>N;
    if(N==1) cout <<"Hello World"<<endl;
    else{
        int A,B;
        cin >>A>>B;
        cout <<A+B<<endl;
    }
}


Measured memory_bytes: 256
n = int(input())
lst = []
for i in range(n):
  lst.append(tuple(map(int, input().split())))
dis = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    dis += ((lst[i][0] - lst[j][0]) ** 2 + (lst[i][1] - lst[j][1]) ** 2) ** 0.5
print(dis * 2 / n)

Measured memory_bytes: 9364
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// Nの入力
		int N = sc.nextInt();
		
		// 1/Aiの計算
		double sum = 0;
		for (int i = 0; i < N; i++) {
			double a = sc.nextDouble();
			sum += 1/a;
		}
		
		System.out.println(1/sum);
		
		sc.close();
	}

}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int main(){
    string s;
    int k, n;
    cin >> s >> k;
    n = s.size();
    set<string> subs;
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= min(n - i, k); j++){
            subs.insert(s.substr(i, j));
        }
    }
    set<string>::iterator t = subs.begin();
    while(--k) t++;
    cout << *t << endl;

    return 0;
}

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

using namespace std;

// AtCoderを信じる！

using int64 = long long;
const int INF = 1 << 30;

int main() {
  int N, pos[200000];

  cin >> N;
  for(int i = 0; i < N; i++) {
    int X;
    cin >> X;
    pos[--X] = i;
  }
  int len = 1, ret = 1;
  for(int i = 1; i < N; i++) {
    if(pos[i - 1] < pos[i]) {
      ++len;
      ret = max(ret, len);
    } else {
      len = 1;
    }
  }
  cout << N - ret << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

main(){
    int x,n;
    cin>>x>>n;
    int p[n],isthere[105] = {0};
    for(int i = 0;i<n;i++){
        cin>>p[i];
        isthere[p[i]] = 1;
    }
    int y = x;
    if(isthere[x]==0){
        cout<<x;
    } 
    else{
        while(isthere[x]==1 && isthere[y]==1){
            x++;
            y--;
        }
        if(!isthere[y]) cout<<y;
        else if(!isthere[x]) cout<<x;
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, string>> v(m);
  rep(i, m){
    cin >> v[i].first >> v[i].second;
    v[i].first--;
  }
  vector<bool> ac(n, false);
  ll res1 = 0, res2 = 0;
  vector<int> pena(n);

  for (int i = 0; i < m; i++) {
    int num = v[i].first;
    bool isac = (v[i].second == "AC");
    if(!ac[num]){
      if(isac){
        ac[num] = true;
        res2+=pena[num];
        res1++;
      }else{
        pena[num]++;
      }
    }
    // cout << res1 << ' ' << pena << endl;
  }

  cout << res1 << ' ' << res2 << endl;

}


Measured memory_bytes: 6912
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>
#include <sstream>
#include <iomanip>

using namespace std;



int main()
{
	long long N;

	cin >> N;

	int s_n = (int)sqrt(N);

	long long ans = N - 1;
	for(int a = s_n; a > 0; a--){
		if (N % a == 0){
			ans = a -1 + N / a - 1;
			break;
		}
	}

	cout << ans;

	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) { rep(_, n) cout << a[_] << " "; cout << endl; }
#define outp(a, n) { cout << endl; rep(_, n) cout << a[_].F << " " << a[_].S << endl; }
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)
#define LB(v, n) (int)(lower_bound(all(v), n) - v.begin())
#define UB(v, n) (int)(upper_bound(all(v), n) - v.begin())

int n, m;
const int MAX_N = 100010;
vector<int> g[MAX_N];
int color[MAX_N];

// ある点のcolorが0でないからといってcontinueできない
// その先の頂点は別
// v, dのpairでメモ化
bool fin[MAX_N][11];

void dfs(int v, int d, int c) {
    if (fin[v][d]) return;
    fin[v][d] = 1;
    if (d == 0) {
        color[v] = c;
        return;
    }
    dfs(v, d - 1, c);
    for (auto nxt : g[v]) {
        dfs(nxt, d - 1, c);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].eb(b);
        g[b].eb(a);
    }
    
    int q;
    cin >> q;
    
    vector<int> v(q), d(q), c(q);
    rep(i, q) cin >> v[q - 1 - i] >> d[q - 1 - i] >> c[q - 1 - i];
    
    // rep(i, q) cout << v[i] << " " << d[i] << " " << c[i] << endl;
    
    rep(i, q) {
        dfs(v[i] - 1, d[i], c[i]);
    }
    
    rep(i, n) out(color[i]);
}


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



bool f(){
    int p,q;
    cin>>p>>q;
    int s = p*p+q*q;

    for(int i=1;i*i<=s;i++){
        if(s%i==0){
            for(int j=0;j*j<=i;j++){
                int x = j;
                int y = sqrt(i-j*j);
                if(y!=sqrt(i-j*j))
                    continue;

                int t = s/i;
                for(int k=0;k*k<=t;k++){
                    int m = k;
                    int n = sqrt(t-k*k);
                    if(n!=sqrt(t-k*k))
                        continue;

                    for(int a=-1;a<2;a+=2){
                        for(int b=-1;b<2;b+=2){
                            for(int c=-1;c<2;c+=2){
                                for(int d=-1;d<2;d+=2){
                                    if(a*m*c*x-b*n*d*y==p&&a*m*d*y+b*n*c*x==q){
                                        if(!(m==0&&n==1)&&!(m==1&&n==0)&&!(x==0&&y==1)&&!(x==1&&y==0)){
                                        
                                            return false;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return true;
}




signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        if(f()){
            cout<<"P"<<endl;
        }
        else{
            cout<<"C"<<endl;
        }
    }
}



Measured memory_bytes: 3104
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
//#define PI 3.14159265358979

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1 << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(11);
	}
};
initializer _____;

int N, M, K, T, Q;
signed main() {
	cin >> N;
	vector< pii > P(N);
	rep(i, N) {
		cin >> P[i].first;
		P[i].second = i;
	}
	sort(P.rbegin(), P.rend());
	multiset< int > s;
	s.insert(N);
	s.insert(N);
	s.insert(-1);
	s.insert(-1);
	int ans = 0;
	rep(k, N) {
		int i = P[k].second;
		int p = P[k].first;
		auto it = s.upper_bound(i);
		it++;
		int z = *it;
		it--;
		int y = *it;
		it--;
		int x = *it;
		it--;
		int w = *it;
		s.insert(i);
		ans += (i - x) * (z - y) * p;
		ans += (y - i) * (x - w) * p;
		/*cout << p << endl
			 << w << " " << x << " " << i << " " << y << " " << z << endl
			 << ans << endl;
			*/
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
 
int main (){
 
  int n;
  cin >> n;
  
  cout << "ABC";
  if(n<10) cout << '0' << '0' << n << endl;
  else if(n<100) cout << '0' << n << endl;
  else cout << n << endl;
  
}

Measured memory_bytes: 256
s = input()
q = int(input())

front = []
back = []
cnt = 0
for i in range(q):
    t = input()
    if t[0] == '1':
        cnt ^= 1
    else:
        f = 1 if int(t[2]) == 1 else 0
        c = t[4]
        if cnt ^ f:
            front.append(c)
        else:
            back.append(c)

ans = ''.join(front)[::-1] + s + ''.join(back)
print(ans[::-1] if cnt else ans)


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

using namespace std;

int main() {
    string s;
    string s1;
    bool flag = true;
    cin >> s;

    for (int i = 0; i <= s.length(); i++)
    {
        if ( s.substr(i, 1) == s1 ) flag = false;
        s1 = s.substr(i, 1);
    }

    if (flag) {
        cout << "Good" << endl;
    } else {
        cout << "Bad" << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		int N = sc.nextInt();
		int M = sc.nextInt();
		Set<Integer>[] edges = new Set[N];
		for (int i = 0; i < N; i++) {
			edges[i] = new HashSet<>();
		}
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			edges[a].add(b);
			edges[b].add(a);
		}
		TreeSet<Node> nodes = new TreeSet<>();
		for (int i = 0; i < N; i++) {
			nodes.add(new Node(edges[i].size(), i));
		}
		int ans = -1;
		if (M % 2 == 0) {
			boolean[] need = new boolean[N];
			while (!nodes.isEmpty()) {
				Node cur = nodes.first();
				int me = cur.index;
				int from = me, to = edges[me].iterator().next();
				if (cur.degre == 1) {
					if (!need[me]) {
						int tmp = from;
						from = to;
						to = tmp;
					}
				}
				need[from] = !need[from];
				out.println((from + 1) + " " + (to + 1));
				edges[from].remove(to);
				edges[to].remove(from);
				nodes.remove(new Node(edges[from].size() + 1, from));
				nodes.remove(new Node(edges[to].size() + 1, to));
				if (!edges[from].isEmpty()) {
					nodes.add(new Node(edges[from].size(), from));
				}
				if (!edges[to].isEmpty()) {
					nodes.add(new Node(edges[to].size(), to));
				}
			}
		} else {
			out.println(ans);
		}
		
		out.flush();
	}
	
	static class Node implements Comparable<Node> {
		int degre, index;
		
		public Node(int degre, int index) {
			this.degre = degre;
			this.index = index;
		}
		
		@Override
		public int compareTo(Node o) {
			int cmp = Integer.compare(degre, o.degre);
			if (cmp != 0) return cmp;
			return Integer.compare(index, o.index);
		}
	}
	
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}


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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  sort(a.begin(), a.end(), greater<int>());
  
  int Alice=0;
  int Bob=0;
  
  rep(i, N) {
    if (i%2==0) Alice+=a[i];
    else Bob+=a[i];
  }
  cout << Alice - Bob << endl;
}


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

int	main(void)
{
	int k, a, b;
	cin >> k >> a >> b;
	for (int i = a; i <= b; i++)
	{
		if (i % k == 0)
		{
			cout << "OK" << endl;
			return (0);
		}
	}
	cout << "NG" << endl;
	return (0);
}


Measured memory_bytes: 3640
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input())for _ in range(n)]
a.sort()
ans1=0
ans2=0
if n%2:
    for i in range(n):
        if i<n//2:
            ans1-=a[i]*2
        elif i<n//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    for i in range(n):
        if i<(n-2)//2:
            ans2-=a[i]*2
        elif i<(n-2)//2+2:
            ans2-=a[i]
        else:
            ans2+=a[i]*2
    print(max(ans1,ans2))

else:
    for i in range(n):
        if i<(n-2)//2:
            ans1-=a[i]*2
        elif i<(n-2)//2+1:
            ans1-=a[i]
        elif i<(n-2)//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    print(ans1)


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

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(v) (int) v.size()

int f ( char x ){
    return x - '0';
}

int main(){
    long long a;
    string b;

    cin >> a >> b;

    long long c = 1LL * ( f( b[0] ) * 100 + f( b[2] ) * 10 + f( b[3] ) );

    a = a * c;

    cout << a / 100;

    return 0;
}


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

using namespace std;

int main(void){
	int n;
	scanf("%d", &n);
	int t = 0, x = 0, y = 0;
	bool f = true;
	for(int i = 0;i < n;++i){
		int tt, tx, ty;
		scanf("%d %d %d", &tt, &tx, &ty);
		if(tt - t != abs(tx - x) + abs(ty - y) && !(tt - t > abs(tx - x) + abs(ty - y) && (tt - t - abs(tx - x) - abs(ty - y)) % 2 == 0)) f = false;
		t = tt; x = tx; y = ty;
	}
	puts(f ? "Yes" : "No");

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/rope"
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
#define lambdify(x) [&](auto &&...args){ return x(forward<decltype(args)>(args)...); }
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	long long res = 1;
	vector<long long> a(n);
	for(auto i = 0; i < n; ++ i){
		cin >> a[i];
		if(!a[i]){
			cout << 0;
			return 0;
		}
	}
	for(auto i = 0; i < n; ++ i){
		if(__builtin_mul_overflow_p(res, a[i], 0LL) || res * a[i] > (long long)1e18){
			cout << -1;
			return 0;
		}
		res *= a[i];
	}
	cout << res;
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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

using namespace std;

int main (void) {
    int n[5];
    for (int i = 0; i < 5; i++) {
        cin >> n[i];
    }
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < 5; j++) {
            if (n[i] < n[j]) {
                swap(n[i], n[j]);
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        if (i) cout << ' ';
        cout << n[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<long long> p(n);
    vector<double> e(n), s(n);
    for(int i = 0; i < n; ++i){
        cin >> p.at(i);
        e.at(i) = (double(p.at(i)) + 1.0) / 2.0;
        if(i != 0) s.at(i) = s.at(i - 1) + e.at(i);
        else s.at(i) = e.at(i);
    }
    double ans = s.at(k - 1);
    for(int i = 0; i < n - k; ++i) ans = max(ans, s.at(i + k) - s.at(i));
    cout << fixed << setprecision(10);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8016
double a[4],b[4],c[4];main(i){for(;~scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",a,b,a+1,b+1,a+2,b+2,a+3,b+3);puts(c[0]*c[1]*c[2]*c[3]>0?"YES":"NO"))for(i=0;i<4;i++)c[i]=(a[(i+1)%4]-a[i])*(b[(i+2)%4]-b[i])-(b[(i+1)%4]-b[i])*(a[(i+2)%4]-a[i]);exit(0);}

Measured memory_bytes: 608
#include <stdio.h>

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


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+5,M=1e6+5,OO=0x3f3f3f3f;
long long n,t[N],m,x,sum;
int p;
int main ()
{
    scanf("%lld",&n);
    for(int i=0;i<n;++i){
        scanf("%lld",t+i);
        sum+=t[i];
    }
    scanf("%lld",&m);
    for(int i=0;i<m;++i){
       scanf("%d %lld",&p,&x);
       //cout<<sum<<" "<<t[p]<<" "<<x<<endl;
       cout<<sum-t[p-1]+x<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
a = [0] * N
for i in range(1, N):
    if S[i - 1 : i + 1] == 'AC':
        a[i] = a[i - 1] + 1
    else:
        a[i] = a[i - 1]
for i in range(Q):
    l, r = map(int, input().split())
    print(a[r - 1] - a[l - 1])


Measured memory_bytes: 6140
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n, h;
	cin >> n >> h;
	vector<string> s(n);
	vector<int> t(n);
	for(int i = 0; i < n; ++i){ cin >> s[i] >> t[i]; }
	int success = 0, fail = 0;
	for(int i = 0; i < n && h >= 0; ++i){
		string cur_s = s[i];
		int cur_t = t[i], cur_p = 0;
		while(cur_p < s[i].size() && cur_t >= 0 && h > 0){
			cout << "? " << cur_s << endl;
			string input;
			cin >> input;
			if(tolower(cur_s[cur_p]) == tolower(input[0])){
				cur_s[cur_p] = '_';
				++cur_p;
				++success;
			}else{
				--cur_t;
				++fail;
			}
		}
		if(cur_p < s[i].size()){ --h; }
	}
	if(h <= 0){
		cout << "! Game Over" << endl;
	}else{
		const int rate = (success * 1000) / (success + fail);
		cout << "! Game Clear " << rate / 10 << "." << rate % 10 << endl;
	}
	return 0;
}

Measured memory_bytes: 1300
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <string>

using namespace std;

typedef long long llint;

void print() { cout << "\n"; }

template <typename...T, typename X>
void print(X& x, T... args) { cout << x << " "; print(args...); }

void input() { /* pass */ }

template <typename...T, typename X>
void input(X& x, T&... args) { cin >> x; input(args...); }

int main()
{
    int n;
    input(n);

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

    map<int, int> mp;
    for (auto num: ns) {
        mp[num]++;
    }

    llint tot = 0;
    for (auto kv: mp) {
        tot += 1LL * kv.second * (kv.second - 1) / 2;
    }

    for (int i = 0; i < n; i++) {
        llint u = tot;
        int cur = ns[i];
        int cnt = mp[cur];
        u -= 1LL * cnt * (cnt - 1) / 2;
        u += 1LL * (cnt - 1) * (cnt - 2) / 2;
        puts(to_string(u).c_str());
    }

    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
struct SegmentTree {
  int sz;
  vector<int> d, m, dm;
  SegmentTree(string s) {
    int n = (int)(s.size());
    sz = 1;
    while(sz < n) sz *= 2;
    d.clear();
    m.clear();
    dm.clear();
    d.resize(2*sz+1, 0);
    m.resize(2*sz+1, 0);
    dm.resize(2*sz+1, 0);
    for(int i=0;i<n;++i) {
      if(s[i] == 'D') {
        d[i+sz-1] = 1;
      } else if(s[i] == 'M') {
        m[i+sz-1] = 1;
      }
    }
    for(int i=sz-2;i>=0;--i) {
      d[i] = d[2*i+1] + d[2*i+2];
      m[i] = m[2*i+1] + m[2*i+2];
      dm[i] = dm[2*i+1] + dm[2*i+2] + d[2*i+1] * m[2*i+2];
    }
  }
  tuple<int, int, int> query(int a, int b, int l, int r, int k) {
    if(b <= l || r <= a) return make_tuple(0, 0, 0);
    if(a <= l && r <= b) return make_tuple(d[k], m[k], dm[k]);
    tuple<int, int, int> v1 = query(a, b, l, (l+r)/2, 2*k+1);
    tuple<int, int, int> v2 = query(a, b, (l+r)/2, r, 2*k+2);
    int resd = get<0>(v1) + get<0>(v2);
    int resm = get<1>(v1) + get<1>(v2);
    int resdm = get<2>(v1) + get<2>(v2) + get<0>(v1) * get<1>(v2);
    return make_tuple(resd, resm, resdm);
  }
  tuple<int, int, int> query(int a, int b) {
    return query(a, b, 0, sz, 0);
  }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  string s; cin >> s;
  vector<int> su(n);
  su[0] == s[0] == 'M';
  for(int i=1;i<n;++i) {
    su[i] = su[i-1] + (s[i] == 'M');
  }
  int q; cin >> q;
  for(int i=0;i<q;++i) {
    int k; cin >> k;
    ll cntd = 0, cntm = 0, now = 0, ans = 0;
    for(int j=0;j<k;++j) {
      if(s[j] == 'D') {
        cntd++;
      } else if(s[j] == 'M') {
        now += cntd;
      } else if(s[j] == 'C') {
        ans += now;
      }
    }
    for(int j=k;j<n;++j) {
      if(s[j-k] == 'D') {
        cntd--;
        now -= su[j-1] - su[j-k];
      }
      if(s[j] == 'D') {
        cntd++;
      } else if(s[j] == 'M') {
        now += cntd;
      } else if(s[j] == 'C') {
        ans += now;
      }
    }
    cout << ans << endl;
  }
}


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

typedef vector <long> vl;
typedef vector <vl> vvl;

typedef vector <int> vi;
typedef vector <vi> vvi;

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

    vl itemWeights(N);
    vl itemValues(N);
    int maxValue = 0;
    for(int i = 0; i < N;i++){
        cin >> itemWeights[i] >> itemValues[i];
        maxValue += itemValues[i];
    }
    vl values(maxValue+1,1e18L+5);
    values[0] = 0;
    for(int i = 0; i < N;i++){
        for(long v = maxValue - itemValues[i]; v >= 0;--v){
            values[v + itemValues[i]] = min( values[v + itemValues[i]], values[v] + itemWeights[i] );
        }
    }
    long bestValue = 0;
    for(long v = 1; v <= maxValue;v++){
        if(values[v] <= W){
            bestValue = max(v,bestValue);
        }
    }
      
    cout << bestValue <<  endl;
    return 0;
    // EDABC
}




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

int N; map<char,long long> M;
void input()
{
    cin >> N;
    for (int i = 0; i < N; ++i){
        string s; cin >> s;
        M[s[0]]++;
    }
}

void solve()
{
    vector<char> head = {'M','A','R','C','H'};
    long long ans = 0;
    for (int i = 0; i < head.size()-2; ++i){
        for (int j = i+1; j < head.size()-1; ++j){
            for (int k = j+1; k < head.size(); ++k){
                // cout << head[i] << " " << head[j] << " " <<  head[k] << endl;
                ans += M[head[i]] * M[head[j]] * M[head[k]];
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main() {
	int N, K;
	string S;
	cin >> N >> K;
	cin >> S;
	K--;
	if (S[K] == 'A') S[K] = 'a';
	if (S[K] == 'B') S[K] = 'b';
	if (S[K] == 'C') S[K] = 'c';
	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int ani=scan.nextInt();
    int leg=scan.nextInt();
    if(leg<ani*2 || leg>ani*4){
      System.out.println("No");
    }else if(leg%2==0){
      System.out.println("Yes");
    }else {
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 35720
#include<bits/stdc++.h>
// debug
#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl;
#define ddd(x, y, z) cerr << "(" #x "," #y "," #z "):(" << x << "," << y << "," << z << ")" << endl;
#define dump(v) cerr<<#v":[ ";for (auto macro_vi:v){cerr<<macro_vi<< " ";}cerr<<"]"<<endl;
#define ddump(v) cerr<<#v":"<<endl;for(auto macro_row:v) {cerr<<"["; for (auto macro__vi:macro_row){cerr<<macro__vi<< " ";}cerr<<"]"<<endl;}
#define damp(m) for(auto macro_pair:m){cerr<< macro_pair.first<<":"<<macro_pair.second<<endl;}
#define dpair(p) cerr << #p":"<<"(" << p.first << "," << p.second << ")" << endl;
// iterate
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define all(v) v.begin(), v.end()
// etc
#define chmin(mi, val) mi = min(mi, val);
#define chmax(ma, val) ma = max(ma, val);
using ll = long long;

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; 
    cin >> n;
    vector<int> A(n), B(n), C(n-1);
    rep(i,n) cin >> A[i];
    rep(i,n) A[i]--;
    rep(i,n) cin >> B[i];
    rep(i,n) cin >> C[i];

    dump(A)
    int ans=0;
    rep(i,n){
        int r = A[i];
        ans+=B[r];
    }
    for(int i=0; i<n-1;i++){

        if(A[i+1]-A[i]==1){
            ans+=C[A[i]];

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

string s;

int main(void){
	
	cin >> s;
	string temp = s;
	reverse(temp.begin(), temp.end());
	
	if(s == temp) printf("Yes\n");
	else printf("No\n");
	
    return 0;
}


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

int main(){
    int A,B,C,X;
    cin >> A >> B >> C >> X;
    int ans = 0;
    for(int ia = 0; ia <= A; ia++) {
        for (int ib = 0; ib <= B; ib++) {
            for (int ic = 0; ic <= C; ic++){
                if(ia *500+ ib*100 + ic*50 == X) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
////////////////////////////////////////////////////////////////////
int main()
{
    string S; cin >> S;
    ll ans1=0, ans2=0;

    REP(i,S.size()){
        if(i%2==0){
            if(S[i]!='0') ans1++;
        }else{
            if(S[i]!='1') ans1++;
        }
    }

    REP(i,S.size()){
        if(i%2!=0){
            if(S[i]!='0') ans2++;
        }else{
            if(S[i]!='1') ans2++;
        }
    }

    cout << min(ans1, ans2) << endl;

    return 0;
}


Measured memory_bytes: 512