akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const vector<int> v = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

int main() {
  int n;
  vector<int> sum(1024, 0);
  for (int i = 0; i <= 1024; ++i) {
    for (int j = 0; j < 10; ++j) {
      if ((i >> j) & 1) sum[i] += v[j];
    }
  }
  while (cin >> n) {
    int pos = 0;
    for (int i = 0; i <= 1024; ++i) {
      pos = i;
      if (sum[i] == n) break;
    }
    bool ok = false;
    for (int i = 0; i <= 10; ++i) {
      if ((sum[pos] >> i) & 1) {
        if (ok) {
          cout << ' ';
        } else {
          ok = true;
        }
        cout << (1 << i);
      }
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3108
//
//  main.cpp
//  ProblemSolving
//
//  Created by Mac mini on 1/7/20.
//  Copyright © 2020 Mac mini. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
long long int  dp[52][52][1300];
int x[52], n, a;

long long int call(int idx, int cnt, int amount) {
	if(idx >= n) {
		if((double)amount / cnt == a)
			return 1;
		return 0;
	}

	if(dp[idx][cnt][amount] != -1) return dp[idx][cnt][amount];

	long long int  ret1 = 0, ret2 = 0;

	ret1 = call(idx + 1, cnt + 1, amount + x[idx]);
	ret2 = call(idx + 1, cnt, amount);

	dp[idx][cnt][amount] = ret1 + ret2;

	return dp[idx][cnt][amount];
}

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

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

	memset(dp, -1, sizeof(dp));

	cout << call(0, 0, 0) << "\n";

}


Measured memory_bytes: 31060
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include<iomanip>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>

i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;

i64 cup(i64 xxx, i64 yyy) {//切り上げ
	return (xxx + yyy - 1) / yyy;
}

//メモリ置き場
int a, b;

//inputします
void input() {
	cin >> a >> b;
}

//ライブラリ置き場

//main
int main() {
	input();
	int ans = -1;
	ff(i, 1, 1001) {
		//cout <<i<<": "<< floor(i / 12.5) << " " << i / 10 << endl;
		if (floor(i /12.5) == a && (i /10) == b) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		double sum_max = 0;
		double sum_tmp = 0;
		int index_max_start = 0;
		double[] p = new double[N];


		for(int i=0;i<K;i++){
			p[i] = sc.nextDouble();
			sum_tmp += p[i];
		}
		
		sum_max = sum_tmp;
		
		for(int i=K;i<N;i++){
			
			p[i] = sc.nextDouble();
			sum_tmp = sum_tmp + p[i] - p[i-K];
			
			if(sum_tmp > sum_max){
				sum_max = sum_tmp;
				index_max_start = i - K + 1;
			}
		}
		
		double ans = 0;
		for(int i=index_max_start;i<index_max_start+K;i++){
			ans += ((double)p[i] + 1.000000000000) / 2.000000000000;
		}
		
		System.out.printf("%.12f",ans);

	}
}

Measured memory_bytes: 160472
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << "[" << pa.first << ", " << pa.second << "]";
}

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  os << "{";
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  os << "}";
  return os;
}

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << std::endl

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

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

  ll n,k;
  std::cin>>n>>k;

  ll cnt=0;

  rep(i,0,n){
    ll h;
    std::cin>>h;
    if(h>=k)cnt++;
  }

  std::cout<<cnt;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

int main(){
  int N,i;
  vector<int> s,in;
  map<int,int> mp;

  while(cin >> N){
    if(N == 0) break;

    s.clear(); in.clear();
    s.resize(N); in.resize(N);
    rep(i,N){
      cin >> in[i];
      s[i] = in[i];
    }

    int res = 0;
    while(1){
      bool used[100];
      mp.clear();
      rep(i,N) mp[s[i]]++;
      rep(i,100) used[i] = false;

//      rep(i,N) cout << s[i] << ' '; cout << endl;
//      foreach(mp,itr) cout << itr->first << ',' << itr->second << ' '; cout << endl;

      rep(i,N) foreach(mp,itr) if(s[i] == itr->first && !used[i]){
        s[i] = itr->second;
        used[i] = true;
      }

//      rep(i,N) cout << s[i] << ' '; cout << endl;

      if(s == in) break;
      in = s;
      res++;
    }

    cout << res << endl;
    rep(i,N){
      cout << s[i];
      if(i == N-1) cout << endl; else cout << ' ';
    }
  }

  return 0;
}

Measured memory_bytes: 0
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vec<vec<char>> a(H, vec<char>(W));
  REP(i, H) REP(j, W) cin >> a[i][j];

  unordered_set<int> sy;
  REP(y, H) {
    REP(x, W) {
      if (a[y][x] == '#') {
        sy.emplace(y);
        break;
      }
    }
  }
  unordered_set<int> sx;
  REP(x, W) {
    REP(y, H) {
      if (a[y][x] == '#') {
        sx.emplace(x);
        break;
      }
    }
  }

  REP(y, H) {
    if (sy.count(y) == 0) {
      continue;
    }
    REP(x, W) {
      if (sx.count(x) == 0) {
        continue;
      } else {
        cout << a[y][x];
      }
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3668
import math
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

def f(X):
    s = 0
    for a in A:
        s += X ^ a
    return s

def main():
    if K == 0:
        print(f(0))
        return

    max_f0, max_x0 = f(0), 0
    max_f1, max_x1 = max_f0, 0
    for i in range(int(math.log(K, 2)) + 1):
        if (max_x0 | (1 << i)) > K:
            break
        tmp = f(max_x0 | (1 << i))
        if tmp > max_f0:
            max_f0 = tmp
            max_x0 |= 1 << i

    for i in range(int(math.log(K, 2)), -1, -1):
        if (max_x1 | (1 << i)) > K:
            continue
        tmp = f(max_x1 | (1 << i))
        if tmp > max_f1:
            max_f1 = tmp
            max_x1 |= 1 << i

    print(max(max_f0, max_f1))


main()

Measured memory_bytes: 14748
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <string>
#include <tuple>
#include <map>

int main() {
  size_t n;
  scanf("%zu", &n);

  std::map<std::string, int> map;
  char buf[262144];
  for (size_t i = 0; i < n; ++i) {
    scanf("%s", buf);
    std::string s(buf);
    ++map[s];
  }

  int max = 0;
  for (auto const& p: map)
    max = std::max(max, p.second);

  for (auto const& p: map)
    if (max == p.second)
      printf("%s\n", p.first.c_str());
}


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

LL GCD(LL a,LL b){ // a>=b とする
	if(a%b) return GCD(b,a%b);
	return b;
}

int main(){
	LL a,b;
	while(cin>>a>>b){
		LL gcd=GCD(max(a,b),min(a,b));
		cout<<gcd<<" "<<a*b/gcd<<endl;
	}
	return 0;
}



Measured memory_bytes: 3080
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const set<T> &st) {
	for (const auto &e : st) os << e << " ";
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
	for (const auto &e : mp) os << e << " ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

template<class T = lint>
struct Edge {
	int to;
	T cost;
	int tank;
	Edge() {}
	Edge(int to, T cost, int tank = 0) : to(to), cost(cost), tank(tank) {}
	bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M, L;
	cin >> N >> M >> L;

	vector<vector<Edge<int>>> edges(N);
	for (int i = 0; i < M; i++) {
		int u, v, len;
		cin >> u >> v >> len;
		u--, v--;
		if (len > L) continue;
		edges[u].emplace_back(v, len);
		edges[v].emplace_back(u, len);
	}

	auto bfs = [&](int st) {
		vector<pair<int, int>> dp(N, { INF, 0 });
		dp[st] = { 0, -L };
		using ppi = pair<pair<int, int>,int> ;
		priority_queue<ppi, vector<ppi>, greater<ppi>> que;
		que.emplace(dp[st], st);
		while (!que.empty()) {
			auto now = que.top();
			que.pop();

			if (now.first > dp[now.second]) continue;

			for (const auto &e : edges[now.second]) {

				auto tmp = now.first;
				if (e.cost > -tmp.second) {
					tmp.first++;
					tmp.second = -L + e.cost;
				}
				else tmp.second += e.cost;

				if (tmp < dp[e.to]) {
					dp[e.to] = tmp;
					que.emplace(tmp, e.to);
				}

			}
		}
		return dp;
	};

	vector<vector<pair<int, int>>> memo(N);
	for (int i = 0; i < N; i++) memo[i] = bfs(i);

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int s, t;
		cin >> s >> t;
		s--, t--;
		auto tmp = memo[s][t].first;
		if (tmp != INF) cout << tmp << "\n";
		else cout << -1 << "\n";
	}

	return 0;
}

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

int  kaibun(string s, int start, int end) {
    int n = end - start;

    int flag = 0;
    rep(i,n/2){
        if(s[start+i] != s[end-i-1]){
            flag = 1;
            break;
        }
    }
    return flag;
}

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

    int n = s.length();
    int flag = 0;
    flag += kaibun(s, 0, n );
    flag += kaibun(s, 0, (n-1)/2 );
    flag += kaibun(s, (n+3)/2 - 1, n );

    if(flag == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    
    return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))

    ans = 0
    for n_pick in range(min(N, K) + 1):
        for left in range(n_pick + 1):
            right = n_pick - left
            tmp = []
            for i in range(left):
                tmp.append(V[i])
            for i in range(right):
                tmp.append(V[N - i - 1])
            tmp.sort()
            s = sum(tmp)
            n_return = min(K - n_pick, len(tmp))
            for i in range(n_return):
                if tmp[i] < 0:
                    s -= tmp[i]
                else:
                    break
            if s > ans:
                ans = s

    print(ans)


if __name__ == "__main__":
    main()


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

int main() {
  int n ;
  cin >> n;
  vector < pair <int , int> > a(n);
  int sum = 0 ;
  for ( int i=0 ; i<n ; i++){
    int t ;
    cin >> t;
    a.at(i) = make_pair ( i, t);
    sum += t;
  }
  int m ;
  cin >> m;
  for ( int i=0 ; i<m ; i++) {
    int p,b,c,t , ans;
    cin >> p >> b;
    tie(c,t) = a.at (p-1) ;
    ans = sum - t + b ;
      cout << ans << endl;
  }
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m; cin >> n >> m;
  vector<pair<ll,ll>> v(n);
  REP(i,n){
      ll a,b; cin >> a >> b;
      v[i] = mp(a,b);
  }
  sort(all(v));
  ll ans = 0;
  REP(i,n){
      if(v[i].second < m){
          ans += v[i].second * v[i].first;
          m -= v[i].second;
      }else{
          ans += v[i].first * m;
          break;
      }
  }
  cout << ans << endl;


}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1000000000000000000L;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

unordered_map<ll, ll> memo;

ll inv(ll a) {
    if(memo.find(a) != memo.end()) return memo[a];
    ll x, y;
    extgcd(a, MOD, x, y);
    return memo[a] = (x + MOD) % MOD;
}

ll f[1001];
ll dp[1001][1001];

int main() {
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    f[0] = 1;
    rep(i, n) {
        f[i + 1] = f[i] * (i + 1) % MOD;
    }

    rep(i, n + 1) rep(j, n + 1) dp[i][j] = 0;
    dp[a - 1][0] = 1;
    for(int i = a; i <= b; i++) {
        rep(j, n + 1) {
            dp[i][j] += dp[i - 1][j];
            ll in = 1;
            ll invf = inv(f[i]);
            rep(k, c) {
                in = in * invf % MOD;
            }
            for(int k = c; k <= min(d, j / i); k++) {
                ll tmp = f[n - j + i * k] * inv(f[n - j]) % MOD;
                tmp = tmp * in % MOD;
                in = in * invf % MOD;
                tmp = tmp * inv(f[k]) % MOD;
                dp[i][j] = (dp[i][j] + dp[i - 1][j - i * k] * tmp % MOD) % MOD;
            }
        }
    }

    /*
    rep(i, n + 1) {
        rep(j, n + 1) {
            cout << " " << dp[i][j];
        }
        cout << endl;
    }
    */

    cout << dp[b][n] % MOD << endl;
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050

#define ll long long
#define ld long double
#define lli long long int

#define pb emplace_back
#define INF 1000000000000

#define mod 1000000007

// trignometric function always give value in Radians only
#define PI acos(-1) //3.1415926535897932384626433832795028
#define dsin(degree) sin(degree*(PI/180.0))
#define dcos(degree) cos(degree*(PI/180.0))
#define dtan(degree) tan(degree*(PI/180.0))

#define rsin(radian) sin(radian)
#define rcos(radian) cos(radian)
#define rtan(radian) tan(radian)

#define loop(i,n) for (lli i = 0; i < n; i++)
#define loopitr(xt,vec) for (auto xt : vec)
#define FOR(i,a,b) for (lli i = a; i < b; i+=1)
#define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
#define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
#define itr :: iterator it
#define WL(t) while(t --)

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(x) int(x.size())
#define F first
#define S second

#define mii map<lli,lli>
#define vi vector<lli>
#define vvi vector<vector<lli>>
#define vbool vector<bool>
#define seti set<lli>
#define pii pair<lli,lli>
#define pcc pair<char , char>

#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)

#define endl '\n'

template <typename T>
void print(T x){cout<<x<<endl;}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}

#define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
#define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}

#define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
#define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";

#define FD(N) fixed<<setprecision(N)

#define deb(x) cout<<#x<<" "<<x<<endl;


void solve(){
    string inp; cin>>inp;
    int s = inp.size();

    if(inp[inp.size()-1]!='s'){
       char answer[s+1];
       int i=0;
       for( i=0;i<s;i++)
        answer[i]=inp[i];
        answer[i++]='s';
        answer[i]='\0';
        cout<<answer<<endl;
    }
    else{
       char answer[s+2];
       int i=0;
       for(i=0;i<s;i++)
        answer[i]=inp[i];
        answer[i++]='e';
        answer[i++]='s';
        answer[i++]='\0';
        cout<<answer<<endl;
    }
}
int main(){
	fastio
	lli t=1;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3668
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main(){
	int N, T;
	cin >> N >> T;
	vector<int> v(N);
	for(int i=0; i<N; i++) cin >> v[i];

	int res=v[N-1]+T;
	for(int i=0; i<N-1; i++){
		if(v[i+1]-v[i] > T) res -= abs(T - (v[i+1]-v[i]));
	}
	cout << res << endl;
}



Measured memory_bytes: 1024
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static int MOD = 1000000007;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		String s = sc.next();
		sc.close();
		String[] day = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
		for (i = 0; i < day.length; i++) {
			if(s.equals(day[i])) {
				break;
			}
		}
		int ans=7-i;
		out.println(ans);
	}
}


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

#define int long long
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define sq(x) (x)*(x)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define t4i tuple<int,int,int,int>
#define mii map<int,int>

const int INF = 1LL<<60;
const int MOD = 998244353;

template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
string to_string(string s) {return s;}
string to_string(bool b) {return b?"true":"false";}
template <typename A, typename B>
string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) { return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";}
template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}
string bin_string(int x) {
    const int d = 32;
    string result(d, ' ');
    REP(i, 0, d) result[d-1-i] = '0'+(x>>i & 1LL);
    return result;
}

int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n,m;
    cin >> n >> m;
    vi a(n);
    cin >> a;
    sort(a.begin(), a.end());
    vi suff(n+1);
    RREP(i, n-1, -1) suff[i] = suff[i+1] + a[i];
    int SFN = 1e5+10;
    vi xx(SFN);
    REP(i, 0, n) ++xx[a[i]];
    RREP(i, SFN-2, -1) xx[i] += xx[i+1];

    int k=0;
    int upp = 1e15+5;
    for (int b=upp; b>=1; b/=2) {
        while (k+b<=upp) {
            int check = k+b;
            int shakes = 0;
            REP(i, 0, n) {
                if (check-a[i] < 0) shakes += n;
                else if (check-a[i] < SFN) shakes += xx[check-a[i]];
            }
            if (shakes < m) break;
            k += b;
        }
    }
    int res = 0, shakes=0;
    REP(i, 0, n) {
        if (k-a[i] < 0) {
            shakes += n;
            res += n*a[i]+suff[0];
        } else if (k-a[i] < SFN) {
            shakes += xx[k-a[i]];
            res += xx[k-a[i]]*a[i] + suff[n-xx[k-a[i]]];
        }
    }
    res -= (shakes-m)*k;
    cout << res;
}

Measured memory_bytes: 2560
#include <iostream>
#include <map>
#include <functional>
#include <vector>
#include <cmath>

class Factoriser
{
    std::vector<int> factors;

public:
    using map_type = std::map<int, int>;
    
    Factoriser(int N)
    {
        factors.resize(N+1, 0);
        int sqrN = static_cast<int>(std::sqrt(N));

        for (int i = 2; i <= sqrN; ++i)
        {
            if (factors[i] == 0)
            {
                for (int j = i * 2; j <= N; j += i)
                {
                    if (factors[j] == 0)
                    {
                        factors[j] = i;
                    }
                }
            }
        }
    }

    map_type Factorise(int M) const
    {
        map_type P;
        int mm = M;

        while (factors[mm])
        {
            ++P[factors[mm]];
            mm /= factors[mm];
        }

        if (mm >= 2) ++P[mm];
        return P;
    }
    
    bool IsPrime(int M) const
    {
        return factors[M] == 0;
    }
};


///////////////////////////////////////////////////

using plist_citr_t = Factoriser::map_type::const_iterator;
using vi = std::vector<int>;

bool contains_dfs(int a, std::function<bool(int)> exists, int cur, plist_citr_t it, plist_citr_t last)
{
    if (cur == a) return false;
    if (it == last)  return exists(cur);

    auto [p, m] = *it++;
    for (int i = 0; i <= m; ++i)
    {
        bool r = contains_dfs(a, exists, cur, it, last);
        if (r) return true;
        cur *= p;
    }
    return false;
}

bool contains(int a, std::function<bool(int)> exists, const Factoriser &fac)
{
    auto plist = fac.Factorise(a);
    return contains_dfs(a, exists, 1, plist.begin(), plist.end());
}

int main()
{
    int N;
    std::map<int, int> A;
    std::cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a;
        std::cin >> a;
        ++A[a];
    }

    constexpr int MAX_A = 1000000;
    std::vector<int> kusi(MAX_A+1, 0);
    for (auto [a, i] : A)
        kusi[a] = i;
        
    Factoriser fac(MAX_A);

    int ans = 0;
    if (kusi[1] > 1)
    {
        ans = 0;
    }
    else if (kusi[1] == 1)
    {
        ans = 1;
    }
    else
    {
        for (auto [a, i] : A)
        {
            if (i == 1 && !contains(a, [&A](int a){ return A.count(a) > 0; }, fac)) ++ans;
        }
    }
    std::cout << ans << std::endl;
}

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

int main()
{
 bool prime[1000000];

 prime[0]=prime[1]=false;
 for(int i=2;i<1000000;i++){
	prime[i]=true;
 }
 for(int i=2;i*i<1000000;i++){
	if(prime[i]){
		for(int j=i*i;j<1000000;j+=i){
			prime[j]=false;
		}
	}
 }

//???????????§?´???°??¨
 int n,x,pea;
 
 
 while(1){
	pea=0;
	cin>>n;
  if(n==0)break;
	for(int i=0;i<n/2+1;i++){
		if(prime[i]){
			x=n-i;
			if(prime[x]){
				pea++;
			}
		}
 	 }
 //	cout<<"??????????????????"<<pea<<"???????????????"<<endl;
	cout<<pea<<endl;
 }

 return 0;
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(lint i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(lint i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct weightedUnionFind{

    vector<int> par, rank, wei;

    void init(int n){
        par.resize(n);
        rank.resize(n, 0);
        wei.resize(n, 0);
        rep(i, n){
            par[i] = i;
        }
        return;
    }

    int root(int x){
        if(par[x] == x){
            return x;
        }else{
            int r = root(par[x]);
            wei[x] += wei[par[x]];
            return par[x] = r;
        }
    }

    bool unite(int x, int y, int w){
        w = -w;
        w += weight(x);
        w -= weight(y);
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            return false;
        }
        if(rank[rx] < rank[ry]){
            swap(rx, ry);
            w = -w;
        }
        if(rank[rx] == rank[ry]){
            rank[rx]++;
        }
        par[ry] = rx;
        wei[ry] = w;
        return true;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int weight(int x){
        root(x);
        return wei[x];
    }

    int diff(int x, int y){
        return weight(x) - weight(y);
    }

};

int main(){
    int n, m;
    cin >> n >> m;
    weightedUnionFind uf;
    uf.init(n);
    bool flag = true;
    rep(i, m){
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        if(uf.same(l, r)){
            if(uf.diff(l, r) != d){
                flag = false;
                break;
            }
        }else{
            uf.unite(l, r, d);
        }
    }
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// AtCoder
const i64 CYCLES_PER_SEC = 2800000000;

struct Timer {
	i64 start;
	Timer(){reset();}
	void reset(){start=getCycle();}
	inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
	inline i64 getCycle(){
		u32 low,high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((i64)low)|((i64)high<<32);
	}
};

Timer timer;


uint32_t xor128(){
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int D;
  cin>>D;

  const int A = 26;
  vector<int> cs(A+1);
  for(int j=1;j<=A;j++) cin>>cs[j];

  vector s(D+1,vector<int>(A+1));
  for(int i=1;i<=D;i++)
    for(int j=1;j<=A;j++)
      cin>>s[i][j];

  vector<int> ts(D+1);
  {
    vector<int> ls(A+1,0);
    for(int i=1;i<=D;i++){
      vector<int> ss(A+1,0);
      for(int j=1;j<=A;j++)
        ss[j]=s[i][j]+cs[j]*(i-ls[j]);
      ts[i]=max_element(ss.begin()+1,ss.end())-ss.begin();

      ls[ts[i]]=i;
    }
  }

  auto calcScore=[&]()->int{
    int res=0;
    vector<int> ls(A+1,0);
    for(int i=1;i<=D;i++){
      res+=s[i][ts[i]];
      ls[ts[i]]=i;
      for(int j=1;j<=A;j++)
        res-=cs[j]*(i-ls[j]);
    }
    return res;
  };

  int iter_num = 0;
  int tmpScore=calcScore();
  while(timer.get()<1.9){
    iter_num++;
    int d=xor128()%D+1;
    int q=xor128()%A+1;

    int p=ts[d];
    ts[d]=q;

    int nxtScore=calcScore();
    if(tmpScore<nxtScore) tmpScore=nxtScore;
    else ts[d]=p;
  }

  cerr<<iter_num<<endl;
  cerr<<tmpScore<<":"<<calcScore()<<endl;
  for(int i=1;i<=D;i++) cout<<ts[i]<<newl;
  return 0;
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> a(m),d(m-1);
    rep(i,m) cin>>a[i];
    if(n>=m){
        cout<<0;
        return 0;
    }
    sort(all(a));
    int dis=0;
    rep(i,m-1){
        d[i]=abs(a[i+1]-a[i]);
        dis+=d[i];
    }
    sort(all(d));
    reverse(all(d));
    ll koma=1,i=0;
    while(koma<n&&dis-d[i]>0){
            dis-=d[i];
            koma++;
            i++;
    }
    cout<<dis;
}

Measured memory_bytes: 4824
//Name : Rupa Dey
  //Date :
//joi sri gour hori gobindo...
//gobindo ja hobe vlor jonnoi hobe..
#include<bits/stdc++.h>
#define ll long long
#define d double
#define ld long double
#define vi vector<int>
#define vul vector<ull>
#define vl vector<ll>
#define pb push_back
#define si set<int>
#define sl set<ll>
#define yes cout<<"YES\n"<<endl
#define no cout<<"NO\n"<<endl
#define ys cout<<"Yes\n"<<endl
#define n cout<<"No\n"<<endl
#define test cin>>t; while(t--)
#define for(i,a,n) for(i=a;i<n;i++)
#define mp make_pair
#define ft first
#define sc second
#define gap " ";
#define MAX 9999999
#define MOD 1000000007
#define nd endl
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char s;
    cin>>s;
    if(s>='A' && s<='Z')
        cout<<"A"<<endl;
    else if(s>='a' && s<='z') cout<<"a"<<endl;
    //cout<<"a"<<endl;

}
//hare krishna...
//hey gobindo kripa koro......
//only gobindo exists..^..


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#define MOD 1000000007
#define INT long long int
#define REP(i,n) for(int(i)=0;(i)<(n);(i)++) 
using namespace std;
const long long INF = numeric_limits<long long>::max();


int main()
{
    int N,K;
    cin >> N >> K;
    int D[K];
    REP(i,K) cin >> D[i];
    bool num[10];
    REP(i,10) num[i] = true;
    REP(i,K) num[D[i]] = false;

    string s;
    for (int i=N;i<=10*N;i++){
        s = to_string(i);
        bool flag = true;
        for (int j=0;j<s.size();j++){
            if (!num[(int)(s[j]-'0')]){
                flag = false;
                break;
            }
        }
        if (flag){
            cout << i << endl;
            return 0;
        }
    }


    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <array>
#include <cstdio>

using namespace std;

const long long int INF = 1LL << 50;

int main()
{
    const char *inf = "inf";

    int N, M;
    if (scanf("%d%d", &N, &M) < 2) return 0;

    const int NMAX = 1000;
    const int MMAX = 2000;

    array<int, MMAX> a, b;
    array<long long int, MMAX> c;

    for (int i = 0; i < M; i++)
    {
        if (scanf("%d%d%lld", &a[i], &b[i], &c[i]) < 3) return 0;
        c[i] = -c[i];
    }

    array<long long int, NMAX> dist;

    dist.fill(INF);

    dist[0] = 0;

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (dist[a[j] - 1] == INF) continue;
            if (dist[b[j] - 1] > dist[a[j] - 1] + c[j])
            {
                dist[b[j] - 1] = dist[a[j] - 1] + c[j];
            }
        }
    }

    long long int ans = dist[N - 1];

    array<bool, NMAX> negative;

    negative.fill(false);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (dist[a[j] - 1] == INF) continue;

            if (dist[b[j] - 1] > dist[a[j] - 1] + c[j])
            {
                dist[b[j] - 1] = dist[a[j] - 1] + c[j];
                negative[b[j] - 1] = true;
            }

            if (negative[a[j] - 1] == true)
            {
                negative[b[j] - 1] = true;
            }
        }
    }

    if (negative[N - 1]) printf("%s\n", inf);
    else printf("%lld\n", -ans);

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

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

	string s;
	cin >> s;

	vector<int> a(n);
	int c = 0;
	for (int i = 1; i < n; i++)
	{
		string t = s.substr(i - 1, 2);

		if (t == "AC")
		{
			c++;		
		}
		a.at(i) = c;
	}

	for (int i = 0; i < q; i++)
	{
		int l, r;
		cin >> l >> r;

		cout << a.at(r - 1) - a.at(l - 1) << endl;
	}
}

Measured memory_bytes: 1408
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

n = int(input())
k = int(input())
print(solve(n,k))


Measured memory_bytes: 3060
// ref: https://atcoder.jp/contests/abc110/submissions/3251714

#include <bits/stdc++.h>
using namespace std;
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;

uint64  divNum(uint64& target, const uint64 divisor){
    uint64 num=0ull;
    for(;;){
        if(target%divisor!=0){ break; }
        target /= divisor;
        ++num;
    }
    return num;
}

tuple<vector<uint64>,vector<uint64>> factor(uint64 target){
    vector<uint64> vecPrime;
    vector<uint64> vecNum;
    
    uint64 divisor=2ull;
    for(; divisor*divisor<=target; ++divisor){
        if(target==1){ break; }
        
        uint64 num = divNum(target, divisor);
        if(num==0ull){ continue; }
        
        vecPrime.push_back(divisor);
        vecNum.push_back(num);
    }
    if(target!=1ull){
        vecPrime.push_back(divisor);
        vecNum.push_back(1ull);
    }
    return tie(vecPrime, vecNum);
}

uint64 pow_mod(uint64 base, uint64 exp, const uint64 mod){
    uint64 ret=1ull;
    for(; exp>0ull; exp>>=1ull){
        if(exp & 1){
            ret = ret*base;
            ret %= mod;
        }
        base = base*base;
        base %= mod;
    }
    return ret;
}
uint64 comb_mod(uint64 n, uint64 r, const uint64 mod){
    if(n==r || n==0ull || r==0ull){ return 1ull; }
    
    uint64 p=1ull, q=1ull;
    r = min(r,n-r);
    for(uint64 i=1ull; i<=r; ++i){
        p *= n; --n;
        p %= mod;
        
        q *= i;
        q %= mod;
    }
    return (p*pow_mod(q,mod-2,mod)) % mod;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    const uint64 mod = 1e9 + 7;
    
    uint64 N, M; cin >> N >> M;
    
    vector<uint64> vecPrime, vecNum;
    tie(vecPrime, vecNum) = factor(M);
    
    uint64 ans=1ull;
    for(uint i=0; i<vecNum.size(); ++i){
        ans *= comb_mod(vecNum[i]+N-1ull, N-1ull, mod);
        ans %= mod;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
evi = []
for _ in range(n):
    m = int(input())
    evi.append([list(map(int, input().split())) for _ in range(m)])
ans = 0
for i in range(1 << n):
    for j in range(n):
        if ((i >> j) & 1) == 1:
            for x,y in evi[j]:
                if ((i >> (x-1))&1) != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,bin(i).count('1'))
print(ans)

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 60;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  ll n; cin >> n;
  auto f = [&](ll a, ll b) {
    return (int)max(to_string(a).size(), to_string(b).size());
  };
  int ans = INF;
  for(ll i = 1; i <= sqrt(n); ++i) {
    if(n%i == 0) chmin(ans, f(i, n/i));
  }
  cout << ans << endl;
}


Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1000000007;
int main() {
	ll i,j,k,l,m,n,t;
	// ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

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

  vector<double> dp(n + 1,1);
  for (i = 1; i <=n; i++) {
    vector<double> dp1(n + 1,1);
    dp1[0] = dp[0] * (1 - a[i - 1]);
    for (j = 1; j < i; j++)
    {
      dp1[j] = dp[j] * (1 - a[i-1]) + dp[j - 1] * a[i-1];
    }
    dp1[i] = dp[i - 1] * a[i-1];
    dp = dp1;
    // for (j = 0; j <= n;j++){
    //   cout << dp[j] << ' ';
    // }
    // cout << endl;
  }
  double ans = 0;
  for (i = (n + 1) / 2; i <= n; i++)
  {
    ans += dp[i];
  }
  printf("%.12lf\n", ans);
  return 0;
}

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

const int N = 1e5 + 5;

int A[N];

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

    vector <int> v;
    for(int i = 1 ; i <= n; i++)
    {
        cin>>A[i];
        if(A[i] == i)
        {
            v.push_back(i);
        }
    }

    int m = v.size(), cnt = 0;
    for(int i = 0; i < m; i++)
    {
        if(i <= m-2 and v[i] + 1 == v[i+1])
        {
            cnt++;
            i++;
        }
        else
        {
            cnt++;
        }
    }

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

Measured memory_bytes: 1148
#include <cassert>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <numeric>
using namespace std;

string to_string(bool x) {
	return x ? "true" : "false";
}

string to_string(char x) {
	return string(1, x);
}

string to_string(string s) {
	return '"' + s + '"';
}

string to_string(const char *s) {
	return to_string((string) s);
}

template<typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() {
	cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define all(x) (x).begin(), (x).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define two(a) (1LL << (a))
#define has(mask, i) ((mask >> i) & 1)
//#define int ll

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector < int >;
using vll = vector < ll >;
using vvi = vector < vector < int > >;
using vpii = vector < pii >;
using ld = long double;
using vs = vector < string >;

//mt19937_64 rnd((unsigned long) chrono::high_resolution_clock::now().time_since_epoch().count());

int N, K;
string S;
vpii ww;

int calc(int d_ch) {
  vi arr;
  for (int i = 0; i < sz(ww); i++) {
    if (ww[i].fi == d_ch) {
      arr.pb((i - 1 >= 0) + (i + 1 < sz(ww)));
    }
  }
  debug(arr);
  sort(all(arr));
  int k = K;
  int ans = 0;
  while (k && !arr.empty()) {
    int val = arr.back();
    arr.pop_back();
    ans += val;
    k--;
  }
  return ans;
}

void solve() {
  cin >> N >> K >> S;
  int ans = 0;
  ww.pb({ S[0] == 'R', 1 });
  for (int i = 1; i < N; i++) {
    int ch = (S[i] == 'R');
    if (ch == ww.back().fi)
      ww.back().se++;
    else
      ww.pb({ ch, 1 });
  }
  for (auto w : ww)
    ans += (w.se - 1);
  debug(ans);
  debug(ww);
  debug(calc(0));
  debug(calc(1));
  int val = max(calc(0), calc(1));
  ans += val;
  cout << ans;
}

signed main() {
#ifdef LOCAL
	freopen("xxx.in", "r", stdin);
	freopen("xxx.out", "w", stdout);
	auto start_time = clock();
#endif

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(12);
	cerr.setf(ios::fixed | ios::showpoint);
	cerr.precision(4);

	solve();

#ifdef LOCAL
	auto end_time = clock();
	cerr << "time: " << (end_time - start_time) * 1.0 / CLOCKS_PER_SEC << endl;
#endif

	return 0;
}


Measured memory_bytes: 1604
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef long long ll;


int main(){
	string s;
	cin >> s;
	
	vector<int> v(s.size());
	
	for(int i=1;i<s.size();++i){
		if(s[i-1] == 'R' && s[i] == 'L'){
		//	cout << s[i-1] << " " << s[i] << " " << i-1<< " " << i <<endl; 
			int j = i-1;
//			v[i] =1;
//			v[i-1] = 1;
			while(s[j] == 'R' || j>= i-1){
				if((i-j)%2==0) v[i]++;
				else v[i-1]++;
				j--;
			}

			j = i;
			while(s[j] == 'L' || j<i-1){
				if((i-1-j)%2==0) v[i-1]++;
				else v[i]++;
				j++;
			}
			
		}
	}
	
	for(int i=0;i<s.size()-1;++i){
		cout << v[i]<< " ";
	}
	cout << v[s.size()-1] <<endl;
	
	
	return 0;
}


Measured memory_bytes: 1024
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();
        long x = sc.nextLong();
        long y = sc.nextLong();
        double ans = w * h / 2.0;
        System.out.print(ans + " ");
        if(x * 2 == w && y * 2 == h){
        	System.out.println(1);
        }else{
        	System.out.println(0);
        }
	}
}

Measured memory_bytes: 38676
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <bitset>
using namespace std;

int main(void){
    long long int d, g;
    int cnt = 0, ans = 0;
    cin >> d >> g;
    pair<int, int> pc[d];

    for(int i = 0; i < d; i++){
        cin >> pc[i].first >> pc[i].second;
    }

    int point = 0;
    for(int i=d-1; i>=0; i--){
        for(int j=1; j <= pc[i].first; j++){
            point += (i+1)*100;
            cnt++;
            if(point >= g){
                ans = cnt;
                break;
            }
        }
        point += int(pc[i].second);
        if(point >= g){
            ans = cnt;
            break;
        }
    }

    for(int bit = 0; bit < (1<<d); bit++){
        cnt = 0; point = 0;
        for(int i = 0; i < d; i++){
            if(bit & (1<<i)){
                point = point + (i+1)*pc[i].first*100 + pc[i].second;
                cnt += pc[i].first;
            }
        }
        if(point >= g){
            ans = min(ans, cnt);
        } else if(~bit & (1<<(d-1))) {
            for(int i = 0; i < pc[d-1].first; i++){
                point += d*100; cnt++;
                if(point >= g) ans = min(ans, cnt);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define dbg(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define dpri(x) dbg(#x ": %d\n", x)
#define dprs(x) dbg(#x ": %s\n", x)
#include <stdio.h>
const int INF = 1e9+7;

int main(int argc, char **argv)
{
	int x;
	scanf("%d", &x);
	printf("%d\n", x*x*x);
	return 0;
}

Measured memory_bytes: 596