akhauriyash/Code-Regression huggingface dataset:
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll a[Max];
ll n;
void solve(){
	cin>>n;
	string s;
	map<string,int> ma;
	int mx=0;
	vector<string> res;
	rep(i,0,n){
		cin>>s;
		ma[s]++;
		mx=max(mx,ma[s]); 
	}
	for(auto m:ma){
		if(m.se==mx)res.pb(m.fi);
	}
	sort(all(res));
	rep(i,0,sz(res))cout<<res[i]<<endl;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 25584
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 200000 + 10;

int n, a[maxn], K, Mx[20][maxn], Mn[20][maxn], Log[maxn], q[maxn], f[maxn];

inline int query_mx(int l, int r) {
	if(l > r) return 0;
	int k = Log[r - l + 1];
	int tmp = max(Mx[k][l],Mx[k][r - (1 << k) + 1]);
//	cout << "Mx " << l << ' ' << r << ' ' << tmp << endl;
	return tmp;
}

inline int query_mn(int l, int r) {
	if(l > r) return n + 1;
	int k = Log[r - l + 1];
	int tmp = min(Mn[k][l],Mn[k][r - (1 << k) + 1]);
//	cout << "Mn " << l << ' ' << r << ' ' << tmp << endl;
	return tmp;
}

inline bool check(int x, int y) {
	int tmp;
  if(f[x] < y - x) tmp = 0;
	else {
		if(f[x + K] < y - x - K + 1) tmp = 0;
		else {
			int Mx1 = query_mx(x,y - 1);
			int Mn2 = query_mn(y,x + K - 1), Mx2 = query_mx(y,x + K - 1);
			int Mn3 = query_mn(x + K,y + K - 1);
			if(Mx1 < Mn2 && Mx2 < Mn3) tmp = 1;
			else tmp = 0;
		}
	}
//	cout << x << ' ' << y << ' ' << tmp << endl;
	return tmp;
}

int main() {
//	freopen("data2.in","r",stdin);
  scanf("%d%d", &n, &K);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]), a[i] ++;
	memset(Mx,0,sizeof(Mx));
	memset(Mn,0x3f,sizeof(Mn));
	for(int i = 1;i <= n;i ++) {
		Mx[0][i] = Mn[0][i] = a[i];
	}
	for(int i = 1, j;i <= n;i = j + 1) {
    j = i;
		while(a[j + 1] > a[j])
			j ++;
		f[i] = j - i + 1;
		for(int k = i + 1;k <= j;k ++) f[k] = f[k - 1] - 1;
	}
	for(int j = 1;j <= 18;j ++) {
    for(int i = 1;i + (1 << j) - 1 <= n;i ++) {
			Mx[j][i] = max(Mx[j - 1][i],Mx[j - 1][i + (1 << (j - 1))]);
			Mn[j][i] = min(Mn[j - 1][i],Mn[j - 1][i + (1 << (j - 1))]);
		}
	}
	Log[1] = 0; for(int i = 2;i <= n;i ++) Log[i] = Log[i >> 1] + 1;
  int Ans = 0, head = 1, tail = 0, num = 0;
	for(int i = 1;i + K - 1 <= n;i ++) {
		while(head <= tail && q[head] <= i - K + 1)
			head ++;
		while(head <= tail) {
			if(!check(q[tail],i)) break;
			if(f[q[tail]] >= K) num --;
			Ans --;
			tail --;
		}
		if(f[i] >= K) num ++;
		q[++ tail] = i;
		Ans ++;
	}
	if(num) Ans = Ans - num + 1;
	printf("%d\n", Ans);
	return 0;
}


Measured memory_bytes: 34560
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
  
  string s;
  cin>>s;
  
  int ans = 0;
  
  for(int i=0;i<(int)s.size()/2;i++){
    
    if( s[i] != s[(int)s.size() - i - 1] ) ans++;
    
  }
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
typedef long long ll;
using namespace __gnu_pbds;

typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
/* ll t = 0;
ordered_multiset me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

///////////   t is insertion time
*/
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
typedef long double lld;

lld pi=3.14159265358;
ll powr(ll a,ll b)
{
    ll c=1;
    ll i;
    for(i=0;i<b;i++)
        c*=a;
    return c;
}
ll hell=1000000007;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
ll dp[100005][102];
ll n,W,i,j;
ll w[102];
ll v[102];
ll solve(ll we,ll i)
{
    if(we<0)
        return -10000000000000000;
    if(i==n)
        return 0;
    if(dp[we][i]!=(-1))
        return dp[we][i];
    ll x=max((solve(we,i+1)),(solve((we-w[i]),i+1)+v[i]));
    dp[we][i]=x;
    return x;
}

int main()
{

    cin>>n>>W;
    for(i=0;i<100005;i++)
        {for(j=0;j<102;j++)
            {dp[i][j]=-1;
            }
        }
    for(i=0;i<n;i++)
        cin>>w[i]>>v[i];
    cout<<solve(W,0);
    return 0;
}






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

int main(){
  long long n=0;
  char c;
  while(cin >> c){
    n += c - '0';
  }
  if(n%9==0){
    cout << "Yes" <<endl;
  } else {
    cout << "No" <<endl;
  }
}

Measured memory_bytes: 3644
/*
author : seryu
title : AGC022A_"Diverse Word"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define mrep(i,from,n) for(int i = from; i < n; i++)
#define mreps(i,from,n) for(int i = from; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
typedef long long ll;
typedef pair<ll, ll> P;
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; }
ll MOD = 1000000007;

void solve()
{	
    string s;
    cin >> s;
    string last_word = "";
    rep(i, 26)last_word.push_back('z'-i);
    if(s == last_word)
    {
        cout << -1 << endl;
        return;
    }
    reverse(all(last_word));
    if(s == last_word)
    {
        cout << last_word.substr(0,24)+"z" << endl;
        return;        
    }
    int n = sz(s);
    if(n < 26)
    {
        bool a[26] = {false};
        rep(i, n)
        {
            a[s[i]-'a'] = true;
        }
        string ans = s;
        rep(i, 26)
        {
            if(!a[i])
            {
                ans.push_back('a'+i);
                cout << ans << endl;
                return;
            }
        }
    }
    else
    {
        int k = n-1;
        while (true)
        {
            if(s[k-1] < s[k])break;
            k--;
        }
        bool a[26] = {false};
        rep(i, k)a[s[i]-'a'] = true;
        k--;
        mrep(i, s[k]-'a'+1,26)
        {
            if(!a[i])
            {
                string ans = s.substr(0, k);
                ans.push_back('a'+i);
                cout << ans << endl;
                return;
            }    
        }
    }
    
	return;
}

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



Measured memory_bytes: 256
s = input()
t = input()

n = len(s)
m = len(t)

dp = [[0 for a in range(3300)] for b in range(3300)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

rewsna = ""

while n >= 0 and m >= 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define se second
#define fi first

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    ll s,c;
    cin >>s>>c;

    ll dec=min(s,c/2);
    
    ans += dec;
    s -= dec;
    c -= dec*2;
    ans += c/4;

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


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

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

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

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

    int A, B;
    std::cin >> A >> B;

    if(B == 1) {
        std::cout << 0 << std::endl;
    }
    else {
        int ans = 1;
        B -= A;
        while(0 < B) {
            B -= A - 1;
            ans++;
            if(B == 0) break;
        }

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

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  int x1, y1, x2, y2, x3, y3, x4, y4;
  cin >> x1 >> y1 >> x2 >> y2;
  struct VEC
  {
    int x;
    int y;
  };
  struct VEC ab_vec;
  ab_vec.x = x2-x1;
  ab_vec.y = y2-y1;
  //回転行列(Θ=90度)
  x3 = x2 - ab_vec.y;
  y3 = y2 + ab_vec.x;
  //回転行列(Θ=90度)
  x4 = x1 - ab_vec.y;
  y4 = y1 + ab_vec.x;
  cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 << endl;
}

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

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

	unordered_set<int> paper;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (paper.count(a) > 0) {
			paper.erase(a);
		} else {
			paper.insert(a);
		}
	}
	cout << paper.size() << endl;

	return 0;
}

Measured memory_bytes: 4388
/* 拡張ダイクストラ */
#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()
typedef pair<ll, ll>    P;

int main() {
    ll a, b, n;
    cin >> a >> b >> n;
    ll tmp = min(b-1, n);
    cout << a * tmp / b - a * (tmp / b) << endl;
    return 0;
}

Measured memory_bytes: 3620
#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 < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl;
#define peintD(a) cout << setprecision(10) << ans << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<int>& a,int n);

int n,m;

signed main(){
    vec(a,10);
    input(a,10);
    Sort(a);
    Reverse(a);
    REP(i,3){
        print(a[i])
    }
    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<int>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}



Measured memory_bytes: 3088
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

int N;
char str[10];
int query(int id) {
	printf("%d\n", id), fflush(stdout);
	scanf("%s", str);
	
	if(str[0] == 'V') exit(0);
	return (str[0] == 'M') ? 0 : 1;
}

int main() {
	scanf("%d", &N);
	
	int val = query(0), L = 0, R = N / 2, M; //(L, R]
	while(R - L > 1) {
		M = (L + R) / 2;
		if(query(M * 2) == val) L = M; else R = M;
	}
	query(R * 2); query(R * 2 - 1);
}

Measured memory_bytes: 760
# デバッグ用
GBN_DEBUG = False
def dprn(s, i):
    if GBN_DEBUG: print(", " + s + " = " + str(i), end = "")
def dprns(s):
    if GBN_DEBUG: print(", " + s, end = "")
def dprni(i):
    if GBN_DEBUG: print(i, end=" ")
def endl(): 
    if GBN_DEBUG: print('')
def puts(s): print(s)

#本体ここから

a = int(input())
s = input()
#S, T = input().split()
#N, M = map(int, input().split())
#W = [input() for _ in range(N)]
#A = list(map(int, input().split()))

#GBN_DEBUG = True

if a >= 3200:
    print(s)
else:
    print('red')


Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			final int X = s.nextInt();
			final int Y = s.nextInt();
			final int Z = s.nextInt();
			final int K = s.nextInt();
			final List<Long> A = new ArrayList<>(X);
			final List<Long> B = new ArrayList<>(Y);
			final List<Long> C = new ArrayList<>(Z);

			for (int i = 0; i < X; i++) {
				A.add(s.nextLong());
			}
			Collections.sort(A, Comparator.reverseOrder());

			for (int i = 0; i < Y; i++) {
				B.add(s.nextLong());
			}
			Collections.sort(B, Comparator.reverseOrder());

			for (int i = 0; i < Z; i++) {
				C.add(s.nextLong());
			}
			Collections.sort(C, Comparator.reverseOrder());

			List<Long> ret = new ArrayList<>(106307);
			for (int x = 1; x <= X; x++) {
				for (int y = 1; y <= Math.min(Y, 3000 / x); y++) {
					for (int z = 1; z <= Math.min(Z, 3000 / x / y); z++) {
						ret.add(A.get(x - 1) + B.get(y - 1) + C.get(z - 1));
					}
				}
			}
			Collections.sort(ret, Comparator.reverseOrder());
			for (int i = 0; i < K; i++) {
				System.out.println(ret.get(i));
			}
		}
	}
}


Measured memory_bytes: 32200
N = int(input())
answer = 0
for i in range(6):
  if N >= 10**i:
    if i%2 == 1:
      answer += 10**i-10**(i-1)
  else:
    if i%2 == 1:
      answer += N-10**(i-1)+1
    break
print(answer)





Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>

using namespace std;

int main() {
    int R;
    cin >> R;
    if (R < 1200) {
        cout << "ABC" << endl;
    } else if (R < 2800) {
        cout << "ARC" << endl;
    } else {
        cout << "AGC" << endl;
    }




    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

const int mod = 1'000'000'007;
int fact[1'000'000], ifact[600'001];

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	--a;
	
	fact[0] = 1;
	for (int i = 1, max = a + b + c; i <= max; ++i)
		fact[i] = (i * (long long)fact[i - 1]) % mod;

	int imax = b + c; if (a > imax) imax = a;
	long long cur = fact[imax];
	int pow = mod - 2, inv = 1;
	while (pow > 0) {
		if (pow & 1) inv = (inv * cur) % mod;
		pow >>= 1;
		cur = (cur*cur) % mod;
	}
	for (ifact[imax] = inv; imax > 0; --imax)
		ifact[imax - 1] = (imax * (long long)ifact[imax]) % mod;

	unsigned int sum = 1, res = 1;
	for (int i = 1, max = b + c; i <= max; ++i) {
		sum = 2 * (sum + mod);
		if (i > b) sum -= ((long long)fact[i - 1] * ifact[b] % mod) * ifact[i - b - 1] % mod;
		if (i > c) sum -= ((long long)fact[i - 1] * ifact[c] % mod) * ifact[i - c - 1] % mod;
		sum %= mod;
		res *= 3;
		res += sum * (long long)fact[a + i] % mod * ifact[a] % mod * ifact[i] % mod;
		res %= mod;
	}
	cout << res << endl;
}


Measured memory_bytes: 6400
from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

print(*ans, sep="\n")

Measured memory_bytes: 23364
#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 sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

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

  int T;
  // cin >> T;
  T = 1;

  while (T--) {
      solve();
  }
}

// youtube editorial
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  vector<int> dp(n); // 配る dp
  dp[0] = 1;

  vector<vector<int> > v(200005);
  rep(i, n) v[a[i]].eb(i);
  // rep(i, 3) { for (int j : v[i]) cout << j << " "; cout << endl; }

  /*
  ほしいのは直前と, 同じ数の 1 つ前
  */
  rep(i, n) {
    // 直後に
    if (i < n - 1 && a[i] != a[i + 1]) add(dp[i + 1], dp[i]);

    // 1 つあとの同じ数のとこ
    int it = ub(v[a[i]], i);
    if (it == sz(v[a[i]])) continue;
    it = v[a[i]][it];
    // cout << i << " " << it << endl;
    add(dp[it], dp[i]);
    // cout << dp << endl;
  }

  // cout << dp << endl;
  cout << dp[n - 1] << endl;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
const LL MOD = 998244353;
const LL INF = (LL) 1e9 + 5;
const int MAXN = 1000005;

LL inv(LL x) {
	LL pw = MOD - 2, res = 1;
	while (pw) {
		if (pw & 1) res = res * x % MOD;
		pw >>= 1;
		x = x * x % MOD;
	}
	return res;
}

int N;
LL num[MAXN], sum[MAXN];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		num[x]++;
	}
	
	for (int i = 1; i < MAXN; i++) {
		for (int j = i; j < MAXN; j += i) {
			sum[i] += j * num[j];
			sum[i] %= MOD;
		}
	}
	
	LL ans = 0;
	for (int i = MAXN - 1; i >= 1; i--) {
		sum[i] = sum[i] * sum[i] % MOD;
		for (int j = i + i; j < MAXN; j += i) {
			sum[i] = (sum[i] - sum[j] + MOD) % MOD;
		}
		ans = (ans + sum[i] * inv(i)) % MOD;
	}
	
	for (int i = 0; i < MAXN; i++) {
		ans = (ans - num[i] * i % MOD + MOD) % MOD;
	}
	ans = ans * inv(2) % MOD;
	
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int mod = 1000000007;
int n;
int dp[101][5][5][5];	//A,G,C,T,-

bool check(int a, int b, int c, int d) {
	if (b == 0 && c == 1 && d == 2) return true;
	if (a == 0 && c == 1 && d == 2) return true;
	if (a == 0 && b == 1 && d == 2) return true;
	if (b == 0 && c == 2 && d == 1) return true;	//ACG
	if (b == 1 && c == 0 && d == 2) return true;	//GAC
	return false;
}

signed main() {
	int i, j, k, l, m;
	
	cin >> n;
	dp[0][4][4][4] = 1;
	
	rep(i, n) {
		rep(j, 5) {
			rep(k, 5) {
				rep(l, 5) {
					rep(m, 4) {
						if (check(j, k, l, m)) continue;
						dp[i + 1][k][l][m] += dp[i][j][k][l];
						dp[i + 1][k][l][m] %= mod;
					}
				}
			}
		}
	}
	
	int ans = 0;
	rep(j, 5) rep(k, 5) rep(l, 5) ans += dp[n][j][k][l];
	cout << ans % mod << endl;
	return 0;
}

Measured memory_bytes: 384
using namespace std;
#include<iostream>
#include<algorithm>
#include<ctime>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<numeric>
#include<queue>
#include<deque>
#include<cfloat>
#include<functional>
#include<tuple>
#include<math.h>
#include<bitset>
#include<stack>
#include<set>
#include<random>
#include<stdlib.h>
#define rip(i,n) for(ll i=0;i<n;i++)
#define Rip(i,n) for(int i=1;i<n;i++)
#define all(V) V.begin(),V.end()
#define ll long long
#define ld long double
#define MOD 1000000007
#define mod 998244353
#define sec setprecision
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
constexpr double eps = 1e-9;
constexpr double pi = 3.141592653589793238462643383279;
ll gcd(ll a, ll b)
{
	if (a % b == 0)	return(b);
	else return(gcd(b, a % b));
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
ll pow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return pow(x * x % m, n / 2, m);
	else
		return x * pow(x, n - 1, m) % m;
}
int main() {
	char a;
	cin >> a;
	if (a - 'a' >= 0)cout << 'a' << endl;
	else cout << 'A' << endl;
}

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

int main() {
  string S;
  cin >> S;
  if (S == "SUN") cout << 7 << endl;
  else if (S == "MON") cout << 6 << endl;
  else if (S == "TUE") cout << 5 << endl;
  else if (S == "WED") cout << 4 << endl;
  else if (S == "THU") cout << 3 << endl;
  else if (S == "FRI") cout << 2 << endl;
  else if (S == "SAT") cout << 1 << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>

using namespace std;

int main() {
    int N;
    cin >> N;
    int magic = 0;
    int count = 0;
    int color;
    int color_prev = -1;
    for (int i = 0; i < N; i++) {
        cin >> color;
        if (color != color_prev) {
            magic += count / 2;
            count = 0;
        }
        color_prev = color;
        count++;
    }
    magic += count / 2;
    cout << magic;
    return 0;
}

Measured memory_bytes: 256
# x2y3 - y2x3 = S
s = int(input())
if s == 10**18:
	print(0, 0, 10**9, 10**9, 0, 10**9)
	exit()
x_2 = 10**9
x_3 = 10**9 - s%(10**9)
y_2 = 1
y_3 = s//(10**9) + 1
print(0, 0, x_2, x_3, y_2, y_3)

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

using namespace std;

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

	int x;
	cin >> x;
	int ret = 1;
	for(int i = 2; i <= sqrt(x); i++)
		for(int j = 2; pow(i, j) <= x; j++)
		{
			if(pow(i, j) <= x)ret = max(ret, (int)pow(i, j));
		}
	cout << ret << endl;

	return 0;
}


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

long int cnt = 0;

void swap(std::vector<int>& arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void merge(std::vector<int>& arr, int start, int mid, int end) {
    int length = end -start;
    int left = start, right = mid;
    std::vector<int> tmp(length);
    for (int i=0; i<length; i++) {
        if ( !(right < end) ) {
            tmp[i] = arr[left];
            left++;
        } else if ( !(left < mid) ) {
            tmp[i] = arr[right];
            right++;
        } else if ( arr[left] < arr[right] ) {
            tmp[i] = arr[left];
            left++;
        } else {
            tmp[i] = arr[right];
            right++;
            cnt+= mid - left;
        }
    }
    
    for (int i=0; i<length; i++) {
        arr[start+i] = tmp[i];
    }
}

void merge_sort(std::vector<int>& arr, int start, int end) {
    if ( end - start > 1 ) {
        if ( end - start == 2 ) {
            if ( arr[start] > arr[start+1] ) {
                swap(arr, start, start+1);
                cnt++;
            }
        } else {
            int mid = ( start + end ) / 2;
            merge_sort(arr, start, mid);
            merge_sort(arr, mid, end);
            merge(arr, start, mid, end);
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i=0; i<n; i++) {
        std::cin >> a[i];
    }
    
    merge_sort(a, 0, n);
    
    std::cout << cnt << std::endl;
}

Measured memory_bytes: 4736
n, k = map(int, input().split())
p = list(map(int, input().split())) 

sum_p = [None] * (n - k + 1)
sum_p[0] = sum(p[0:k])
for i in range(1, n - k + 1):
  sum_p[i] = sum_p[i -1] + p[i + k - 1] - p[i -1]

max_sum_p = max(sum_p)

print((k + max_sum_p) / 2)


Measured memory_bytes: 25060
#!/usr/bin/env python3
import sys
from bisect import bisect_right

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0

    for i in range(N-1):
        for j in range(i+1,N):
            diff = L[j] - L[i]
            index = bisect_right(L[:i],diff)
            ans += i-index
            # print(i,j,ans)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 50652
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string S;
vector<string> ss;
vector<int> ints,dists;
template <typename T>
void p(const vector<T>& xs) {
  for(const auto& x:xs) cout<<x<<endl;
}
int main() {
  cin>>S;
  for(int i=0;i<S.size()-2;++i){
    ss.push_back(S.substr(i, 3));
  }
  for(const auto& s:ss) ints.push_back(stoi(s));
  for(const auto& i:ints) dists.push_back(abs(i-753));
  sort(dists.begin(), dists.end());
  cout<<dists[0]<<endl;
}

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

int main(void)
{
    int i, n, turn;
    char taro[101], hanako[101];
    int tcount = 0, hcount = 0;
    scanf("%d", &n);

    for(i = 0; i < n; i++){
        scanf("%s %s", taro, hanako);
        if(!strcmp(taro, hanako)){
            tcount++;
            hcount++;
        }else if(strcmp(taro, hanako) > 0){
            tcount += 3;
        }else if(strcmp(taro, hanako) < 0){
            hcount += 3;
        }
    }
    printf("%d %d\n", tcount, hcount);

    return 0;
}


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

int N, Q;
int const INF = INT_MAX;
struct LazySegmentTree {
private:
    int n;
    vector<int> node, lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree(vector<int> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, INF);
        lazyFlag.resize(2*n-1, false);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    // k ?????????????????? ( ??????????????? [l, r) ) ?????????????????¶??????
    void lazy_evaluate(int k, int l, int r) {
        // ?????? lazy ???????????\??£??????????????????
        // ??????????????¨????????? (??? lazy) ???????????????????????????
        if(lazyFlag[k]) {
            node[k] = lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] = lazy[k];
                lazy[2*k+2] = lazy[k];
                lazyFlag[2*k+1] = true;
                lazyFlag[2*k+2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    // [a, b) ??????????´??????¨??? x ?????´??°??????
    // ????????????????????? k ??¨??????????????????????????????????????? [l, r) ??§??????
    void update(int a, int b, int x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b) {
            lazy[k] = x;
            lazyFlag[k] = true;
            lazy_evaluate(k, l, r);
        }
        else {
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[k*2+1], node[k*2+2]);
        }
    }

    int find(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return INF;
        if(a <= l && r <= b) return node[k];
        int vl = find(a, b, 2*k+1, l, (l+r)/2);
        int vr = find(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

int main() {
    cin >> N >> Q;
    LazySegmentTree seg( vector<int>(N, INF) );
    for(int i=0; i<Q; i++) {
        int query; cin >> query;
        if(query == 0) {
            int s, t, x; cin >> s >> t >> x;
            seg.update(s, t+1, x);
        }
        else {
            int i; cin >> i;
            cout << seg.find(i, i+1) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 5228
n = int(raw_input())
a = []
t = 1
count = 0
for i in xrange(n):
    a.append(int(raw_input()))
for v in a:
    if t == 1:
        count += v - 1
        t += 1
    elif v > t:
        if v % t == 0:
            count += v / t - 1
        else:
            count += v / t
    elif v == t:
        t += 1
print count
        
    


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

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_V(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_M(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}

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

    ll ans = (n / (a+b))*a, amari = n % (a+b);
    if(amari > a){
        ans += a;
    }else{
        ans += amari;
    }
    cout<<ans<<endl;

    return 0;
}

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

using namespace std;

#define fst first
#define snd second

int main() {
  int t, n;
  while(cin >> t >> n && (t|n)) {
    int M[200][200] = {};
    int const BX = 100, BY = 100;
    for(int i=0; i<n; i++) {
      int x, y;
      cin >> x >> y;
      M[y+BY][x+BX] = 1;
    }
    
    int const dx[] = {-1,1,0,0,1,-1};
    int const dy[] = {0,0,-1,1,1,-1};
    
    typedef pair<int, int> Pii;
    typedef pair<Pii, int> P;
    
    bool used[200][200] = {};
    int ans = 0;
    
    int sx, sy;
    cin >> sx >> sy; sx += BX, sy += BY;
    
    queue<P> Q;
    Q.push(P(Pii(sx, sy), t));
    used[sy][sx] = true;
    
    while(!Q.empty()) {
      P const p = Q.front(); Q.pop();
      ans ++;
      
      if(p.snd <= 0) continue;
      
      for(int i=0; i<6; i++) {
	int nx = p.fst.fst + dx[i], ny = p.fst.snd + dy[i];
	if(!used[ny][nx] && M[ny][nx] == 0) {
	  Q.push( P(Pii(nx, ny), p.snd-1) );
	  used[ny][nx] = true;
	}
      }
    }
    
    cout << ans << endl;
  }
  
  return 0;
}

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


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

    vi g;
    for(int i =1; i <= m; ++i) {
        if(m%i == 0) {
            g.push_back(i);
        }
        if((i+1)*(i+1) > m) break;
    }
    for(int i = g.size()-1; i >= 0; --i) {
        if(i*i == m) continue;
        g.push_back(m/g[i]);
    }

    int j=0;
    while(1) {
        if(j+1 == g.size()) {
            cout << g[j] << endl;
            break;
        }
        if(g[j+1] > m/n) {
            cout << g[j] << endl;
            break;
        }


        ++j;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <iterator>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 1000020;
const LL INF = 100000000000000LL;
const LL mod = 998244353;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define For(i,a,b) for(int i=a;i<=b;++i)

int n;
LL a[maxn];
LL t1[maxn], t2[maxn];
LL pre1[maxn], pre2[maxn];
int cmp(LL a, LL b) {
    return a > b;
}

void solve() {
    for(int i = 1;i <= n;i++) {
        scanf("%lld", &a[i]);
        a[i] -= i;
    }
    sort(a + 1, a + 1 + n);
    LL cnt1 = 0, cnt2 = 0;
    pre1[0] = 0, pre2[0] = 0;
    for(int i = 1;i <= n;i++) {
        if(a[i] >= 0) {
            t1[++cnt1] = a[i];
            //pre1[cnt1] = pre1[cnt1 - 1] + a[i];
        }
        else {
            a[i] *= -1;
            t2[++cnt2] = a[i];
            //pre2[cnt2] = pre2[cnt2 - 1] + a[i];
        }
    }
    sort(t1 + 1, t1 + 1 + cnt1, cmp);
    sort(t2 + 1, t2 + 1 + cnt2, cmp);
    for(int i = 1;i <= cnt1;i++) pre1[i] = pre1[i - 1] + t1[i];
    for(int i = 1;i <= cnt2;i++) pre2[i] = pre2[i - 1] + t2[i];
    LL ans = ((1ll)<<60);
    //cout << cnt1 << endl;
    for(LL i = 1;i <= cnt1;i++) {
        //cout << t1[i] << " ";
        ans = min(ans, pre1[i] - i * t1[i] + (cnt1 - i) * t1[i] - (pre1[cnt1] - pre1[i]) + cnt2 * t1[i] + pre2[cnt2]);
    }//cout << endl;
    //cout << cnt2 << endl;
    for(LL i = 1;i <= cnt2;i++) {
        //cout << t2[i] << " ";
        ans = min(ans, pre2[i] - i * t2[i] + (cnt2 - i) * t2[i] - (pre2[cnt2] - pre2[i]) + cnt1 * t2[i] + pre1[cnt1]);
    }//cout << endl;
    cout << ans << endl;
}

int main() {
	int t = 1;
    while(~scanf("%d", &n)) {
        solve();
    }
    return 0;
}


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



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

	long long sum;

	if (N == 1 && M == 1) {
		cout << 1 << endl;
	}else if (N == 1) {
		cout << M - 2 << endl;
	}
	else if (M == 1) {
		cout << N - 2 << endl;
	}
	else {
		sum = (N - 2)*(M - 2);
		cout << sum << endl;
	}
	
}

Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * 3102.cc: iff
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 300;

/* typedef */

/* global variables */

bool ms[MAX_N][MAX_N];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < n; i++) ms[i][i] = true;

  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    ms[a][b] = true;
  }

  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
	ms[i][j] = ms[i][j] || (ms[i][k] && ms[k][j]);

  for (int i = 0; i < n; i++) {
    for (int j = 0, cont = 0; j < n; j++)
      if (ms[i][j] && ms[j][i]) {
	if (cont) putchar(' ');
	printf("%d", j + 1);
	cont = 1;
      }
    putchar('\n');
  }  

  return 0;
}



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

int main(){
	char ch;
	int num[26] = {0};

	while(scanf("%c", &ch) != EOF){
		if(ch >= 'A' && ch <= 'Z'){
			ch += 'a' - 'A';
			num[ch - 'a']++;
		}else if(ch >= 'a' && ch <= 'z'){
			num[ch - 'a']++;
		}
	}

	for(int i = 0; i < 26; i++){
		cout << (char)(i + 'a') << " : " << num[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1156
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAX = 3000000;
const ll MOD = 1000000007;
//string s;
ll k;

int main() {
    cin >> k;
    ll lunlun[110000];
    ll ppNum = 0;
    ll pNum = 0;
    for(ll i=0; i<10; i++){
        if(i==0){
            for(ll j=0;j<9;j++){
                lunlun[j] = j+1;
                pNum = j;
            }
        }else{
            ll count = 0;
            for(ll j=ppNum;j<pNum;j++){
                ll lastN = lunlun[j]%10;
                if(lastN%10!=0){
                    count++;
                    lunlun[pNum+count] = lunlun[j]*10 + lastN - 1;
                    if(pNum+count>=100000)break;
                }
                count++;
                lunlun[pNum+count] = lunlun[j]*10 + lastN;
                if(pNum+count>=100000)break;
                if(lastN%10!=9){
                    count++;
                    lunlun[pNum+count] = lunlun[j]*10 + lastN + 1;
                    if(pNum+count>=100000)break;
                }
            }
            ppNum = pNum;
            pNum = pNum+count;
            if(pNum>=100000)break;
        }
    }
    cout << lunlun[k-1] << endl;
    return 0;
}


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

int main() {
	// your code goes here
	ll n;
	cin>>n;
	ll arr[n],brr[n],crr[n];
	for(ll i=0;i<n;i++)
	{
	cin>>arr[i]>>brr[i]>>crr[i];	
	}
	ll drr[n+1][3];
	drr[n][0]=0,drr[n][1]=0,drr[n][2]=0;
	for(ll i=n-1;i>=0;i--)
	{
		drr[i][0]=max(drr[i+1][1]+brr[i],drr[i+1][2]+crr[i]);
		drr[i][1]=max(drr[i+1][0]+arr[i],drr[i+1][2]+crr[i]);
		drr[i][2]=max(drr[i+1][1]+brr[i],drr[i+1][0]+arr[i]);
	}
	cout<<max({drr[0][0],drr[0][1],drr[0][2]});
	return 0;
}

Measured memory_bytes: 4864
from collections import deque
H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
flg = [[True] * W for i in range(H)]

def bfs(i,j,S,flg):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([(i,j)])
    black = 1
    cnt = 1

    while len(que) != 0:
        p = que.popleft()
        #print(p)
        flg[p[0]][p[1]] = False
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < H and ny >= 0 and ny < W and flg[nx][ny] == True:
                if S[p[0]][p[1]] == '#' and S[nx][ny] == '.':
                    que.append((nx,ny))
                    cnt += 1
                    flg[nx][ny] = False
                if S[p[0]][p[1]] == '.' and S[nx][ny] == '#':
                    que.append((nx,ny))
                    cnt += 1
                    black += 1
                    flg[nx][ny] = False
    # print(black,cnt-black)
    # val = 0
    # if black >= 2:
    #     val += (black*(black-1))//2
    return black * (cnt-black) 

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and flg[i][j] == True:
            ans += bfs(i,j,S,flg)

print(ans)


Measured memory_bytes: 83500
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int pm = 1000000;
		boolean[] prime = new boolean[pm+1000];
		for(int i=2;i<=pm;i++) prime[i] = true;
		for(int i=2;i<=pm+1;i++){
			for(int j=i+i;j<=pm;j+=i){
				prime[j]=false;
			}
		}
		
		while(true){
			int[] in = new int[2];
			in[0] = sc.nextInt();
			in[1] = sc.nextInt();
			if(in[0]==0 && in[1]==0) break;
			
			int[] m = new int[2];
			for(int i=0;i<2;i++){
				int max = -1;
				for(int j=in[i];j>1;j--){
					if(prime[j] && in[i]%j==0){
						if(max==-1) max = j;
						else m[i] += j;
					}
				}
				m[i] = max - m[i];
			}
			if(m[0]>m[1]) System.out.println("a");
			else System.out.println("b"); 
		}
	}
}

Measured memory_bytes: 23908
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	cin>>n;
	if(n%2==0)
		cout<<"0.5000000000"<<endl;
	else
	{
		int x=n/2+1;
		double ans=(double)x/(double)n;
		printf("%0.8f\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
// abc171_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (ll)(1e9)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    char x;
    cin >> x;

    char ans = x >= 'a' ? 'a' : 'A';
    print(ans);


    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i, j, n) for(size_t i = (j); i < (n); ++i)
#define rrep(i, j, n) for(size_t i = (n) - 1; (j) <= i; --i)
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;


string s;
ll ans = 0;

void dfs(int i, ll val, ll cnt) {
	if (i == s.size()) {
		ans += val + cnt;
		return;
	}
	ll x = s[i] - '0';
	ll res = 0;
	// iの左に+を入れる。
	dfs(i + 1, x, cnt + val);
	dfs(i + 1, val * 10 + x, cnt);
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> s;
	dfs(1, s[0] - '0', 0);
	cout << ans;
	return 0;

}


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

#define io ios::sync_with_stdio(false)
#define pb push_back
#define pqueue priority_queue
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
#define sz(x) (int)(x).size()
#define dbg(x) cout<<#x<<" --- "<<x<<endl
#define mst(x,a) memset(x,a,sizeof(x))
#define fin(a) freopen(a,"r",stdin)
#define fout(a) freopen(a,"w",stdout)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r; }
const int inf=0x7fffffff;
const int maxn=2e5+10;
map<ll,ll> mp,mm;
ll a[maxn];
ll n,k;

int main(){
	io;
	cin>>n>>k;
	for(ll i=1;i<=n;i++)cin>>a[i];
	for(ll i=1;i<=n;i++)a[i]=(a[i]+a[i-1])%k;
	mp[0]++;
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ll x=a[i]-i,y=a[i]-i+k;
		ans+=mp[x];
		ans+=mm[y];
		mp[x]++;
		mm[x]++;
		if(i+1-k>=1)mm[a[i+1-k]-i-1+k]--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 39296
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define myPair pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define qmax priority_queue<int>
#define qmin priority_queue<int,vector<int>,greater<int>>
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FORR(i,a,b) for(int i = a; i >= b; i--)

string s,r,ans;
const int mxn = 3005;
int dp[mxn][mxn];
bool c[mxn][mxn];

int f(int i,int j)
{
	if(c[i][j])
		return dp[i][j];
	if(i == 0 || j == 0)
		return 0;
	else if(s[i - 1] == r[j - 1])
		dp[i][j] = 1 + f(i - 1, j - 1);
	else
		dp[i][j] = max(f(i - 1,j), f(i, j - 1));
	c[i][j] = 1;
	return dp[i][j];
}

void construct(int i,int j)
{
	if(i == 0 || j == 0)
		return;
	if(s[i - 1] == r[j - 1])
	{
		ans += s[i - 1];
		construct(i - 1, j - 1);
	}
	else if(f(i - 1, j) > f(i, j - 1))
		construct(i - 1, j);
	else
		construct(i, j - 1);
}

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

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> s >> r;
	ans = "";
	memset(c,0,sizeof(c));
	construct(s.size(), r.size());
	reverse(all(ans));
	cout << ans;

	return 0;
}

Measured memory_bytes: 83292
import java.util.*;
public class Main {
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      // 整数の入力
      int n = sc.nextInt();
    double sum = 0.0;
      for(int i = 0; i < n; i++){
        sum += 1 / sc.nextDouble();
      }
      System.out.println(1 / sum);
  }
  
}

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

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

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

	int count = 1;
	int maxH = H[0];

	for (int i = 1; i < N; i++)
	{
		if (H[i] >= maxH) count++;
		maxH = max(maxH, H[i]);
	}

	cout << count << endl;
}

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

int main() {
	// your code goes here
	int n,i,a,ans=0,min=10;
	for(i=1;i<=5;i++){
		cin >> a;
		if(a%10!=0 && a%10<min) min=a%10;
		if(a%10!=0) a=(a-a%10+10);
		ans+=a;
	}
	if(min!=0){
		ans=ans-(10-min);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
long long mas[200005];
int main()
{
    int n,sum=0;
    cin>>n;
    for(int i=0; i<n; i++){
        char c;
        int in=0;
        cin>>c;
        if(c=='R'){
            in=1;
        }
        mas[i]=in;
        sum+=in;
    }
    int ans=0;
    for(int i=0; i<sum; i++){
        if(mas[i]==0) ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 5192
import java.util.*;
public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String s = sc.next();
      String ans = "";
      for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='0'){
          ans += "0";
        }else if(s.charAt(i)=='1'){
          ans += "1";
        }else{
          if(!ans.isEmpty()){
          	ans = ans.substring(0,ans.length()-1);
          }
        }
      }     
        System.out.println(ans);
    }
}

Measured memory_bytes: 38592
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
int N, a[100000];
int main()
{
	int count[100010] = { 0 };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}
	int i = 0;
	int an = 0;
	while (true) {
		if (i == 1) {
			printf("%d", an);
			return 0;
		}
		if (i == a[i] - 1) {
			printf("-1");
			return 0;
		}
		if (count[i] == 1) {
			printf("-1");
			return 0;
		}
		count[i] = 1;
		i = a[i] - 1;
		an++;
	}

	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long unsigned int ll;
 
int main() {
 
  int a,b;
  vector<int> c(3);
  cin >> a;
  cin >>b;
  c[0]=a+b;
  c[1]=a-b;
  c[2]=a*b;
  sort(c.begin(),c.end());
  cout << c[2] <<endl;
  
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	char s[19];
	for(int i=0;i<19;i++){
		cin>>s[i];
		if(s[i]==',') s[i]=' ';
	}
	for(int j=0;j<19;j++) {cout<<s[j];}
	cout<<endl;
    return 0;
}


Measured memory_bytes: 256