akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val K = readLine()!!.toInt()
    val X = readLine()!!.split(" ").map(String::toInt)

    var sum = 0
    for (x in X) {
        val calc = Math.abs(K - x)
        if (x < calc) {
            sum += x * 2
        } else {
            sum += calc * 2
        }
    }
    println(sum)
}



Measured memory_bytes: 37736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 4;

vector<ll> ans;

void dfs(ll idx, ll now){
    if(idx == 10) return;
    for(int i = -1; i <= 1; ++i){
        ll tmp = now%10 + i;
        if(tmp == -1 || tmp == 10) continue;
        ll now2 = 10 * now + tmp;
        ans.push_back(now2);
        dfs(idx + 1, now2);
    }
}

void solve() {
    ll K; cin >> K;
    string s = "3234566667";
    int n = s.size();
    for(int i = 1; i < 10; i++) {
        ans.push_back(i);
        dfs(0, i);
    }
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    cout << ans[K-1] << endl;
    return;
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt", "input5.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


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

const int K = 18, N = 1<<K, M = 1e9+7;
int prod[N][K];
int a[N];

vector<pair<int, int>> vp[N];

void add(int x, int z, int mul) {
    assert(vp[x].empty() || vp[x].back().first <= z);
    if (vp[x].empty() || vp[x].back().first < z)      vp[x].push_back({z, mul});
    else {
        vp[x].back().second += mul;
        if (vp[x].back().second >= M) vp[x].back().second -= M;
    }
}

int rgt[N];

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

    int k;
    cin>>k;

    int L = 1<<(k-1);

    for (int i=L; i<2*L; i++) {
        prod[i][0] = i;
        for (int j=1; j<k; j++) {
            prod[i][j] = (1LL*prod[i][j-1]*(i>>j))%M;
        }
    }

    for (int i=0; i<N; i++)   vp[i].reserve(2*K);

    for (int i=L; i<2*L; i++) {
        int x;
        cin>>x;
        a[i] = x+L-1;
    }

     for (int k1=k-1; k1>=0; k1--) {
        for (int k2=k-1; k2>=0; k2--) {
            for (int i=L; i<2*L; i++) {
                int x = a[i];
                int pr = (1LL*prod[i][k1]*prod[x][k2])%M;

                int a1 = (i>>k1), a2 = (x>>k2);
                add(a2, a1, pr);
            }
        }
    }

    long long ans = 0;
    for (int i=1; i<=L; i++) {
        int ll = 2*i, rr = 2*i+1;

        for (auto pr: vp[rr])       rgt[pr.first] = pr.second;

        for (auto pr: vp[ll]) {
            int x = pr.first;
            if (x == 1) continue;
            unsigned long long con = (1LL*pr.second*rgt[x^1])%M;
            con = (con*i*(x>>1))%M;
            ans += con;
        }

        for (auto pr: vp[rr])       rgt[pr.first] = 0;
    }
    cout<<ans%M<<endl;
}


Measured memory_bytes: 270116
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  vector<int> vec;
  int A, B, C;
  cin >> A >> B >> C;
  vec.push_back(A);
  vec.push_back(B);
  vec.push_back(C);
  sort(vec.begin(), vec.end());
  int dif, diff;
  dif = vec[1] - vec[0];
  diff = vec [2] - vec[1];
  int ans = 0;
  ans += diff;
  if(dif % 2 == 0)
  {
    ans += dif / 2;
  }
  else if(dif % 2 == 1)
  {
    ans += dif /2;
    ans += 2;
  }
  
  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[] v = new int[n];
		int[] c = new int[n];
		int[] diff = new int[n];
		int tot = 0;

		for (int i=0; i<n; i++) {
			v[i] = sc.nextInt();
		}

		for (int i=0; i<n; i++) {
			diff[i] = v[i] - sc.nextInt();
			if (diff[i] > 0) {
				tot += diff[i];
			}
		}

		System.out.println(tot);
	}
}



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

int main() {
    std::string n;
    std::cin >> n;
    int sum = 0;
    for (char c : n) {
        int i = c - '0';
        sum += i;
    }
    if (sum % 9 == 0) {
        std::cout << "Yes";
    }
    else {
        std::cout << "No";
    }
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
int keta(int a){
    int sum = 0;
    while (a > 0){
        sum += a % 10;
        a /= 10;
    }
    return sum;
}
int main(){
    int n, a, b;
    cin >> n >> a >> b;
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int k =keta(i);
        if (k >= a && k <= b)
            ans += i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))


mod = 10**9 + 7

ans = 0
for i in range(61):
    zero = 0
    one = 0
    for a_ in a:
        if (a_ >> i) & 1:
            one += 1
        else:
            zero += 1
    ans += one * zero * pow(2, i, mod) % mod
    ans %= mod

print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  vector<int> P(N);
  for (int i = 0; i < N; ++i)
    cin >> S[i] >> P[i];

  for (int i = 0; i < N; ++i)
    P[i] *= -1;

  vector<pair<pair<string, int>, int>> ans(N);
  for (int i = 0; i < N; ++i)
    ans[i].first.first = S[i], ans[i].first.second = P[i],
    ans[i].second = i + 1;

  sort(ans.begin(), ans.end());

  for (int i = 0; i < N; ++i)
    cout << ans[i].second << endl;
}


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

int main(){
    ll n, a, b; cin >> n >> a >> b;
    vector<ll> h(n); rep(i,n) cin >> h[i];
    sort(all(h));
    reverse(all(h));

    ll left = -1;
    ll right = 1002003004;
    while(right - left > 1){
        ll mid = (left + right)/2;
        ll cnt = 0;

        rep(i,n){
            if(h[i] - mid * b <= 0) break;
            cnt += max(0ll, ((h[i] - mid*b)+(a-b-1))/(a-b));
        }

        if(cnt > mid) left = mid;
        if(cnt <= mid) right = mid;

    }

    cout << right << endl;

}

Measured memory_bytes: 1024
/* -> Written by <-
   -----------
  |K_A_Z_A_M_A|
  |___________|
  |    ___    |
  |   (^_^)   |
  |  /( | )\  |
  |____|_|____|
    H O A N G
*/

#define Task ""

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define YES cout << "YES\n"
#define NO cout << "NO\n"

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

void Solve()
{
    int n, dem1 = 0, dem2 = 0, dem3 = 0, dem4 = 0;
    cin >> n;
    string s[maxn];
    for (int i = 1; i <= n; i ++)
        cin >> s[i];
    for (int i = 1; i <= n; i ++)
        if (s[i] == "AC") dem1 ++;
        else if (s[i] == "WA") dem2 ++;
        else if (s[i] == "TLE") dem3 ++;
        else if (s[i] == "RE") dem4 ++;
    cout << "AC x " << dem1 << endl;
    cout << "WA x " << dem2 << endl;
    cout << "TLE x " << dem3 << endl;
    cout << "RE x " << dem4 << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if(fopen(Task".inp", "r"))
    {
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }

    int test_case = 1;
//    cin >> test_case;
    while (test_case --)
        Solve();
    return 0;
}



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

int main() {
	int n, d, s1 = 0, s2 = 0;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> d;
		s1 += d;
		s2 += d*d;
	}
	cout << (s1*s1-s2)/2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}


int main() {
    ll n;
     double t, a;
    cin >> n >> t >> a;
    int ans = 0;
    double zans = 999999;
    vector<double> z(n);
    for (int i = 0; i < n; i++) {
        cin >> z.at(i);
        double f = abs(a - (t - z.at(i) * 0.006));
        if (f < zans) {
            zans = f;
            ans = i + 1;
        }
        
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    g=gcd(a,b)
    return a/g*b

n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for x in a:
    ans=gcd(ans,x)
print(int(ans))


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

int main() {
    int N, M, a, c, d;
    cin >> N >> M;
    vector<vector<int>> ans(M,vector<int>(pow(2,N),100000001));
    vector<vector<int>> S(M,vector<int>(N + 1));

    for(int i = 0; i < M; i++) {
        cin >> S.at(i).at(0);
        int b;
        cin >> b;
        int l = b + 1;
        while (b > 0) {
            cin >> S.at(i).at(l - b);
            b--;
        }
    }
    ans.at(0).at(0) = 0;
    for (int i = 0; i < M - 1; i++) {
        for(int j = 0; j < N; j++) {
          	if (S.at(i).at(j + 1) != 0){
          		d = pow(2,S.at(i).at(j + 1) - 1);
            	a = a | d; // ビット
         	 }
        }
        for (int j = 0; j < pow(2,N); j++) {
            ans.at(i + 1).at(j) = ans.at(i).at(j);
        }
        for (int j = 0; j < pow(2,N); j++) {
            c = a | j;
            ans.at(i + 1).at(c) = min(ans.at(i + 1).at(c),ans.at(i).at(j) + S.at(i).at(0));
        }
      a = 0;
      c = 0;
    }
    if (ans.at(M - 1).at(pow(2,N) - 1) == 100000001) {
        cout << -1 << endl;
    }
    else {
    cout << ans.at(M - 1).at(pow(2,N) - 1) << endl;
    }
}

Measured memory_bytes: 16384
#include "bits/stdc++.h"
using namespace std;

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

    int Amax = -100;
    int Amin = 100;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        Amax = max(Amax, A[i]);
        Amin = min(Amin, A[i]);
    }

    int ans = pow(10, 9);
    int sum = 0;
    for (int i = Amin; i <= Amax; i++) {
        for (int j = 0; j < N; j++) {
            sum += pow(A[j] - i, 2);
        }

        ans = min(ans, sum);
        sum = 0;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
//#include <bits/stdc++.h>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define INF_LL 1LL << 40
#define INF 2000000000
#define MOD 1000000007
#define ll long long
#define all(x) x.begin(), x.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)
#define prique priority_queue
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;
typedef vector<vector<int>> matrix;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int sign[2] = {1, -1};
template <class T> bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
struct edge {
    int to, cost;
};

int main() {
    int n;
    cin >> n;
    vi a(n), m(n);
    rep(i, n) cin >> a[i];
    m[0] = a[0];
    rep(i, n - 1) m[i + 1] = min(m[i], a[i + 1]);
    int ans = -1 * INF;
    rep(i, n - 1) { chmax(ans, a[i + 1] - m[i]); }
    cout << ans << endl;
}



Measured memory_bytes: 4372
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
ll n, mx, sum, a[105];
//bool b[105][105];


//void g(ll p)
//{
//    for(ll i = p; i <= n; i += p)
//    {
//        if(bo[i] == false)bo[i] = true;
//    }
//}
//
void f(ll p)
{
    int b[105];
    if(p > n)
    {
        sum = 0;
        for(ll i = 1; i <= n; i++)
        {
            sum += a[i];
        }
        mx = max(mx, sum);
        return;
    }
    f(p + 1);
    if(a[p] < 0) {
        for(int i = 1; i <= n; i++) b[i] = a[i];
        for(int i = p; i <= n; i += p) a[i] = 0;
        f(p + 1);
        for(int i = 1; i <= n; i++) a[i] = b[i];
    }
}

int main()
{
    scanf("%lld", &n);
    for(ll i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    for(ll i = n / 2 + 1; i <= n; i++)
    {
        if(a[i] < 0) a[i] = 0;
    }
    f(1);
    printf("%lld", mx);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

#define MOD 1000000007

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

    int N; cin >>N;
    vector<int> A(N+1);
    vector<int> pos(N, -1);
    int l, r;
    rep(i, N+1) {
        cin >> A[i];
        A[i]--;
        if (pos[A[i]] == -1) {
            pos[A[i]] = i;
        } else {
            l = pos[A[i]];
            r = i;
        }
    }

    vector<ll> fact(N+1+1);
    vector<ll> finv(fact.size());
    vector<ll> inv(fact.size());
    
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    inv[0] = 0; inv[1] = 1;
    for (int i = 2; i < fact.size(); i++) {
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

    auto C = [&](int n, int r) { return fact[n] * finv[n-r] % MOD * finv[r] % MOD; };

    cout << N+1-1 << endl;
    for (int k = 2; k <= N+1; k++) {
        ll a = C(N+1, k);
        ll b = l + N+1-(r+1) >= k - 1 ? C(l + N+1-(r+1), k-1) : 0;
        ll s = (a - b) % MOD;
        while (s < 0) s += MOD;
        cout << s << endl;
    }
}

Measured memory_bytes: 4352
n,m = map(int,input().split())

s = [0 for _ in range(m)]
c = [0 for _ in range(m)]

for i in range(m):
    S,C = map(int,input().split())
    s[i] = S
    c[i] = str(C)
if(n == 1):
    for i in range(10):
        t = str(i)
        for j in range(m):
            if(c[j] != t):
                break
        else:
            print(i)
            exit()
    else:
        print(-1)
        exit()
elif(n == 2):
    for i in range(10,100):
        t = str(i)
        for j in range(m):
            if(c[j] != t[s[j]-1]):
                break
        else:
            print(i)
            exit()
    else:
        print(-1)
        exit()
elif(n == 3):
    for i in range(100,1000):
        t = str(i)
        for j in range(m):
            if(c[j] != t[s[j]-1]):
                break
        else:
            print(i)
            exit()
    else:
        print(-1)
        exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int main()
{
	#ifndef ONLINE_JUDGE
	freopen(".in.txt", "r", stdin);
	freopen(".out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a, v, b, w, t; cin >> a >> v >> b >> w >> t;
	if(v > w) cout << (abs(a - b)/(v - w) + (abs(a - b) % (v - w) != 0) <= t ? "YES" : "NO");
	else cout << "NO";

	return 0;
}

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

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

  vector<pair<long long, long long>> p(N);
  for (int i = 0; i < N; i++) {
    long long a;
    long long b;
    cin >> a >> b;
    p.at(i) = make_pair(a, b);
  }

  sort(p.begin(), p.end());

  long long cnt = M;
  long long ans = 0;
  for (int i = 0; i < N; i++) {
    long long a;
    long long b;
    tie(a, b) = p.at(i);
    
    if (cnt > b) {
      cnt -= b;
      ans += a * b;
    } else {
      ans += cnt * a;
      break;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N, C; cin >> N >> C; int D[35][35], c[505][505];
  rep(i, C){
    rep(j, C){
      cin >> D[i][j];
    }
  }
  rep(i, N){
    rep(j, N){
      cin >> c[i][j]; c[i][j]--;
    }
  }
  int cost[3][35] = {};
  rep(k, C){
    rep(i, N){
      rep(j, N){
        if((i+j+2)%3==0) cost[0][k] += D[c[i][j]][k];
        else if((i+j+2)%3==1) cost[1][k] += D[c[i][j]][k];
        else cost[2][k] += D[c[i][j]][k];
      }
    }
  }
  
  int ans = inf;
  rep(i, C){
    rep(j, C){
      rep(k, C){
        if(i!=j && j!=k && i!=k) ans = min(cost[0][i]+cost[1][j]+cost[2][k], ans);
      }
    }
  }
  cout << ans << endl;    
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll h; cin >> h;
    ll a; cin >> a;
    cout << (h+a-1)/a << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#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 fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int A[3][3];
    REP(i,3) REP(j,3) cin >> A[i][j];
    bool flag = true;
    REP(i,2){
        int sa = A[i][0] - A[i+1][0];
        FOR(j,1,3) if(sa != A[i][j] - A[i+1][j]) flag = false;
    }

    REP(j,2){
        int sa = A[0][j] - A[0][j+1];
        FOR(i,1,3) if(sa != A[i][j] - A[i][j+1]) flag = false;
    }

    if(flag){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

}

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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  string res = ":(";
  for (int i = 1; i < 50001; i++) {
    if ((int) (i * 1.08) == n) {
      res = to_string(i);
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
long long n,a[200005],sm[200005];
void init(){
    scanf("%lld",&n);
    sm[0]=0;
    for(long long i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        sm[i]=sm[i-1]+a[i];
    }
    long long p=2,q=1;
    long long ans=INF;
    for(long long i=2;i<=n-2;++i){
        while(q+1<i&&Abs(sm[q]-(sm[i]-sm[q]))>=Abs(sm[q+1]-(sm[i]-sm[q+1]))){
            ++q;
        }
        while(p+1<n&&Abs((sm[p]-sm[i])-(sm[n]-sm[p]))>=Abs((sm[p+1]-sm[i])-(sm[n]-sm[p+1]))){
            ++p;
        }
        ans=Min(ans,Max(Max(sm[n]-sm[p],sm[p]-sm[i]),Max(sm[i]-sm[q],sm[q]))-Min(Min(sm[n]-sm[p],sm[p]-sm[i]),Min(sm[i]-sm[q],sm[q])));
    }
    printf("%lld",ans);
} 
int main(){
    init();
    return 0;
}

Measured memory_bytes: 3456
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();

            int N = Integer.parseInt(s);

            int ans = 0;

            for (int i = 0; i <= N; i++) {
                int i2 = i * i;
                if (N < i2) break;
                ans = i2;
            }

            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
//#pragma GCC optimize(2)
//#define int long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	int a=0,b=0;
	for(int i=0;i<3;i++)
		if(s[i]=='A')
			a++;
		else
			b++;
	if(a&&b) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


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

int main()
{
  string s, t;
  cin >> s >> t;
  int n = s.size(), count = 0;
  for(int i = 0; i < n; i++)
  {
    if(s[i] != t[i]) count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 3856
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#define ll long long
#define maxn 4001000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
const ll P=1e9+7;
using namespace std;
int main(){
	int a[]= {1,2,3};
	int c,b;
	cin>>c>>b;
	for(int i = 0;i < 3;++i){
		if(a[i] != c&&a[i] != b) {
			return cout<<a[i],0;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define pb push_back
#define si second
#define int long long
#define mod 998244353
#define debug(x) cout << #x << " " << x <<endl;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define double long double
#define all(o) o.begin(),o.end()
using namespace std;
int power(int x, int y)
{
    int res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1; // y = y/2
        x = (x*x) % mod;
    }
    return res%mod;
}
int inv(int  n)
{
    return power(n,mod-2)%mod;
}


pii a[25];

int t[200005],n,k;

void upd(int i,int val){
    while(i<=n)
    {
        t[i]+=val;
        t[i]%=mod;
        i+=i&-i;
    }
}
int qry(int i){
    int sum=0;
    while(i){
        sum+=t[i];
        sum%=mod;
        i-=i&-i;
    }
    return sum;
}
int rsum(int l,int r){
    return (qry(r)-qry(l-1)+mod)%mod;
}

int32_t main(){

    fast
    cin>>n>>k;
    int i,j;
    for(i=0;i<k;i++)
        cin>>a[i].fi>>a[i].si;
    sort(a,a+k);
    upd(1,1);
    for(i=2;i<=n;i++){
        int l,r;

        for(j=0;j<k;j++){
             
             l=i-a[j].si;
             r=i-a[j].fi;
             if(r>=1)
            {
                l=max(l,1LL);
                upd(i,rsum(l,r));
            }
        }
    }
    cout<<rsum(n,n)<<"\n";

}




 

Measured memory_bytes: 5116
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> counts;

bool comp(int i, int j) {
  return counts[i] > counts[j];
}

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  map<int, int> m;
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    if (m.find(a) == m.end())
      m[a] = 0;
    if (m.find(a + 1) == m.end())
      m[a + 1] = 0;
    if (m.find(a - 1) == m.end())
      m[a - 1] = 0;
    ++m[a];
    ++m[a + 1];
    ++m[a - 1];
  }

  vector<int> n(m.size());
  vector<int> indices(m.size());
  counts.resize(m.size());
  int c = 0;
  for (map<int, int>::iterator i = m.begin(); i != m.end(); ++i) {
    indices[c] = c;
    n[c] = i->first;
    counts[c] = i->second;
    ++c;
  }

  sort(indices.begin(), indices.end(), comp);

  cout << counts[indices[0]] << endl;

  return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef pair<int, int> p;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    set<int> a;
    REP(i, m)
    {
        int tmp;
        cin >> tmp;
        a.insert(tmp);
    }

    vector<ll> dp(n + 1);
    dp[0] = 1;
    FOR(i, 1, n + 1)
    {
        if (a.count(i) == 0)
        {
            if (i == 1)
                dp[1] = dp[0];
            else
                dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
        else
        {
            dp[i] = 0;
        }
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 5760
# -*- coding: utf-8 -*-
h,w,k=map(int,input().split())
masu=[]
ans=0
for i in range(h):
  slist=list(map(str,input()))
  masu.append(slist)
for i in range(2**h):
  for j in range(2**w):
    black=0
    for m in range(h):
      for n in range(w):
        if ((i >> m) & 1) and ((j >> n)&1) and masu[m][n]=='#':
          black+=1
    if black==k:
        ans+=1
print(ans)

Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 4e3 + 10;
int r[NMAX],g[NMAX],b[NMAX];
typedef long long ll;
bool calisr(char ch1,char ch2)
{
	return ch1 == 'G' && ch2 == 'B' || ch1 == 'B' && ch2 == 'G';
}
bool calisg(char ch1,char ch2)
{
	return ch1 == 'R' && ch2 == 'B' || ch1 == 'B' && ch2 == 'R';
}
bool calisb(char ch1,char ch2)
{
	return ch1 == 'G' && ch2 == 'R' || ch1 == 'R' && ch2 == 'G';
}
int main(int argc, char const *argv[])
{
	int n;
	char str[NMAX];
	scanf("%d",&n);
	scanf("%s",str+1);
	for(register int i = 1;i <= n;i++)
	{
		if(str[i] == 'R')	r[i]++;
		else if(str[i] == 'G') g[i]++;
		else b[i]++;
		r[i] += r[i-1];
		g[i] += g[i-1];
		b[i] += b[i-1];
	}
	ll ans = 0;
	for(register int i = 1;i < n;i++)
		for(register int j = i+1;j < n;j++)
		{
			if(calisr(str[i],str[j]))
				ans += r[n] - r[j];
			else if(calisg(str[i],str[j]))
				ans += g[n] - g[j];
			else if(calisb(str[i],str[j]))
				ans += b[n] - b[j];
		}
	for(int j = 1;j <= n/2;j++)
		for(register int i = 2;i < n;i++)
		{
			int left,mid = i,right;
			left = mid - j;
			right = mid + j;
			if(left < 1 || right > n)	continue;
			if(str[left] != str[mid] && str[left] != str[right] && str[mid] != str[right])
				ans--;
		}
	printf("%lld\n",ans );
	return 0;
}

Measured memory_bytes: 3868
#include<set>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long read(){
	long long f=1,x=0;
	char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f*x;
}
#define MAXN 100000
struct node{
	int t,x,y;	
	node(){}
	node(int T,int X,int Y){t=T,x=X,y=Y;}
}test[MAXN+5];
bool cmp(node a,node b){return a.t<b.t;}
int main(){
	int n=read(),tmp;
	for(int i=1;i<=n;i++)
		test[i].t=read(),test[i].x=read(),test[i].y=read();
	sort(test+1,test+n+1,cmp);
	node Now(0,0,0);
	for(int i=1;i<=n;i++)
	{
		if(test[i].x!=Now.x||test[i].y!=Now.y)	
		{
			tmp=abs(test[i].x-Now.x)+abs(test[i].y-Now.y);
			if(Now.t+tmp>test[i].t)
			{
				printf("No\n");	
				return 0;
			}
			else
				Now.t+=tmp,Now.x=test[i].x,Now.y=test[i].y;
		}
		if(test[i].x==Now.x&&test[i].y==Now.y)
		{
			if(test[i].t%2!=Now.t%2)
			{
				printf("No\n");	
				return 0;
			}
			else
				Now.t=test[i].t;
		}
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 1408
N = int(input())
v = [9**5, 9**4, 9**3, 9**2, 9, 6**6, 6**5, 6**4, 6**3, 6**2, 6, 1]
dp = [0] + [float('inf')] * N
for i in range(N):
    for j in v:
        if i + j <= N:
            dp[i + j] = min(dp[i + j], dp[i] + 1)
print(dp[N])

Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int s;
signed main(){
	cin>>s;
	int x1=0,y1=0;
	int m=1000000000;
	int x2=(s-1)/m+1,y3=m;
	int x3=1,y2=m-(s%m==0?m:s%m);
	cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<endl;
	return 0;
}


Measured memory_bytes: 764
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int N=100005;

int n,ans;
int a[N];

int main(){
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	for (i=1;i<=n;i=j+1){
		j=i;
		while (j<n&&a[j+1]==a[i]) j++;
		ans+=(j-i+1)/2;
	}
	printf("%d\n",ans);
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;
const int mod = 1e9 + 7;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    int res = 0;
    for (int i = 0; i < k; ++i) {
        res += p[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 3588
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String T = sc.next();
        int result = 0;
        for(int i = 0; i < 3; i++){
            if(S.charAt(i) == T.charAt(i)){
                result++;
            }
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 21588
#include<stdio.h>
int main(void){
    int t1,t2,t3,t4;
    int n1,n2,n3,n4;
    scanf("%d %d",&t1,&n1);
    scanf("%d %d",&t2,&n2);
    scanf("%d %d",&t3,&n3);
    scanf("%d %d",&t4,&n4);
    if(t1==1){
        printf("%d\n",6000*n1);
    }else if(t1==2){
        printf("%d\n",4000*n1);
    }else if(t1==3){
        printf("%d\n",3000*n1);
    }else if(t1==4){
        printf("%d\n",2000*n1);
    }
    if(t2==1){
        printf("%d\n",6000*n2);
    }else if(t2==2){
        printf("%d\n",4000*n2);
    }else if(t2==3){
        printf("%d\n",3000*n2);
    }else if(t2==4){
        printf("%d\n",2000*n2);
    }
    if(t3==1){
        printf("%d\n",6000*n3);
    }else if(t3==2){
        printf("%d\n",4000*n3);
    }else if(t3==3){
        printf("%d\n",3000*n3);
    }else if(t3==4){
        printf("%d\n",2000*n3);
    }
    if(t4==1){
        printf("%d\n",6000*n4);
    }else if(t4==2){
        printf("%d\n",4000*n4);
    }else if(t4==3){
        printf("%d\n",3000*n4);
    }else if(t4==4){
        printf("%d\n",2000*n4);
    }
    return 0;
}


Measured memory_bytes: 2148
# include <bits/stdc++.h>
# define rr
const int N=100010,INF=0x3f3f3f3f;
char s[5];
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	long long a;
	scanf("%lld",&a);
	scanf("%s",s+1);
	long long b,c1,c2,c3;	
	c1=s[1]-'0',c2=s[3]-'0',c3=s[4]-'0';
	b=c1*100ll+c2*10ll+c3;
	printf("%lld",a*b/100ll);
	return 0;
}


Measured memory_bytes: 3828
#include<iostream>
using namespace std;
int main(){
  int a,d,n,so[1000000]={},i,j;
  so[1]=1;
  for(i=2;i<1000;i++)if(so[i]==0)for(j=2;i*j<1000000;j++)so[i*j]=1;
  while(1){
    cin>>a>>d>>n;
    if(n==0)break;
    j=0;
    for(i=a;j<n;i+=d)if(so[i]==0)j++;
    cout<<i-d<<endl;
  }
  return 0;
}

Measured memory_bytes: 5072
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
const ll MOD = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
 
VI ans(200001, 0);
VI add(200001, 0);
vector<vector<int>> edge(200001, vector<int>(0));
 
void dfs(int v, int p) {
	ans[v] = ans[p] + add[v];
	for (int i = 0; i < edge[v].size(); i++) {
		if (edge[v][i] != p) {
			dfs(edge[v][i], v);
		}
	}
}
 
int main() {
	int n, q;
	cin >> n >> q;
	int a, b;
	REP(i, n - 1) {
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	int p, x;
	REP(i, q) {
		cin >> p >> x;
		add[p] += x;
	}
	dfs(1, 0);
	REP(i, n) {
		cout << ans[i + 1] << ' ';
	}
}

Measured memory_bytes: 24320
/*
問題内容：
某国に住んでいる友達がお金に困って、あるヤミ金融業者から 10 万円の借金をしたまま、全く返済していないといいます。
この業者は、一週間ごとに 5% の利子を借金に加え、さらに借金の 1,000 円未満を切り上げます。

n を入力したとき、n 週間後の借金の残高を出力し終了するプログラムを作成して下さい。n は 100 以下とします。

・手順：
・第六回授業で使用したプログラムを再利用。
・変更点は、切り上げの部分。
・なぜか不正解。
*/
#include <stdio.h>
#include <math.h>

double ceil00(double n, int i);

int main()
{
	int n,i;
	double result=100000;
	while(1){
		scanf("%d",&n);
		if(0<n&&n<=100){			//nが1〜100でなければやり直す。
			break;
		}
	}
	for(i=1; i<=n; i++){
		result+=(result*5/100);			//5%増やす。
		result=ceil00(result,-3);
	}
	printf("%d\n",(int)result);
    return 0;
}

double ceil00(double n, int i)
{
	if(i==-5){
		n/=100000;
		n=ceil(n);
		n*=100000;
	}
	else if(i==-4){
		n/=10000;
		n=ceil(n);
		n*=10000;
	}
	else if(i==-3){
		n/=1000;
		n=ceil(n);
		n*=1000;
	}
	else if(i==-2){
		n/=100;
		n=ceil(n);
		n*=100;
	}
	else if(i==-1){
		n/=10;
		n=ceil(n);
		n*=10;
	}
	else if(i==1){
		n=ceil(n);
	}
	else if(i==2){
		n*=10;
		n=ceil(n);
		n/=10;
	}
	else if(i==3){
		n*=100;
		n=ceil(n);
		n/=100;
	}
	else if(i==4){
		n*=1000;
		n=ceil(n);
		n/=1000;
	}
	else if(i==5){
		n*=10000;
		n=ceil(n);
		n/=10000;
	}
	return n;
}

Measured memory_bytes: 592
/*****************************************************

Code by: Vichitr
Compiled On: 23rd March 2019

*****************************************************/

#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
#define pb push_back
#define pf pop_front
#define mp make_pair
#define loop(i,n) for(int i=0;i<n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;
#define ip pair<int, int>
#define N 100007
const ll MOD = 1e9+7;
const ll SZ = 107;
int n;
double dp[3000][3000], p[3000];

double solve(int x, int y)
{
    if(x+y==n)
    {
        if(x>y) return 1.0;
        return 0.0;
    }
    if(dp[x][y] != -1)
        return dp[x][y];
    double ans = 0;
    ans += p[x+y]*solve(x+1, y);
    ans += (1-p[x+y])*solve(x, y+1);
    return dp[x][y] = ans;
}

signed main()
{
    fast;

    //int n, m;
    cin>>n;
    //double p[n];
    for(int i=0;i<n;i++) cin>>p[i];

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
            dp[i][j] = -1;
    }
    cout<<fixed<<setprecision(10);
    cout<<solve(0, 0);
    
    return 0;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
 
int main() {
  int N;
  cin >> N;
  map<string,int> cnt;
  rep(i,N){
    string s;
    cin >> s;
    cnt[s]++;    
  }
  for(string s : {"AC", "WA", "TLE", "RE"}){
    cout << s << " x " << cnt[s] << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
int st[maxn], fr = 0, ed = 0;
int fl[2][maxn];
int p[maxn];
int ext[maxn];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		scanf("%d", &p[i]);
	ext[0] = 0;
	for (int i = 1; i < n; i++)
		if (p[i] > p[i - 1]) ext[i] = ext[i - 1];
		else ext[i] = i;
	fr = ed = 0;
	for (int i = 0; i < n; i++) {
		while (fr < ed && p[st[ed - 1]] < p[i]) ed--;
		while (fr < ed && st[fr] <= i - k) fr++;
		st[ed++] = i;
		if (ed - fr == 1) fl[1][i] = 1;
	}
	fr = ed = 0;
	for (int i = n - 1; i >= 0; i--) {
		while (fr < ed && p[st[ed - 1]] > p[i]) ed--;
		while (fr < ed && st[fr] >= i + k) fr++;
		st[ed++] = i;
		if (ed - fr == 1) fl[0][i] = 1;
	}
	int ans = 0, ff = 0;
	for (int i = k - 1; i < n; i++) {
		if (i >= k) {
			if (fl[1][i] && fl[0][i - k]) continue;
			if (ff && ext[i] <= i - k + 1) continue;
		}
		ans++;
		if (ext[i] <= i - k + 1) ff = 1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define mem0(s) memset(s,0,sizeof(s))
#define meminf(s) memset(s,0x3f,sizeof(s))
#define mp_insert(a,b,c) mp.insert(map<pair<int,int>,int>::value_type(make_pair(a,b),c))
double pi=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
inline ll lowbit(ll x){return x&(-x);}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}
const int INF=0x3f3f3f3f,max_n=100005,mod=1e9+7;
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll pow(ll a,ll b,ll mod){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;}

int dad[max_n];
int deep[max_n];
int people[max_n];
int find(int x)
{
    if(dad[x]==x)return x;
    return dad[x]=find(dad[x]);
}
void link(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
    {
        return;
    }
    else if(deep[x]<deep[y])
    {
        dad[x]=y;people[y]+=people[x];
    }
    else if(deep[x]>deep[y])
    {
        dad[y]=x;people[x]+=people[y];
    }
    else if(deep[x]==deep[y])
    {
        dad[x]=y;
        deep[y]++;
        people[y]+=people[x];
    }
}
struct Edge
{
    int from,to;
}e[100005];
int V,E,q;
int cnt;
int x;
int tt;
vector<int>v1;
long long ans;
int peng[100005];
int feng[100005];
int main()
{
	int V,m,k;cin>>V>>m>>k;int a,b;
    for(int i=1;i<=V;i++)
    {
        dad[i]=i;people[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
    	cin>>a>>b;
    	peng[a]++;
    	peng[b]++;
    	link(a,b);
	}
	for(int i=1;i<=k;i++)
	{
		cin>>a>>b;
		if(find(a)==find(b))
		{
			feng[a]++;
			feng[b]++;
		}
	}
    for(int i=1;i<=V;i++)
    {
        if(dad[i]==i)
        {
            cnt++;
            v1.push_back(people[find(i)]);
        }
	}
    for(int i=1;i<=V;i++)
    {
    	cout<<people[find(i)]-peng[i]-feng[i]-1<<' ';
	}
}

Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

class Com{
public:
    int n;
    int mod;
    vector<long long> f, fInv, inv;

    Com(int n, int mod){
        this->n = n;
        this->mod = mod;

        f.resize(n + 1);
        fInv.resize(n + 1);
        inv.resize(n + 1);

        f[0] = f[1] = 1;
        fInv[0] = fInv[1] = 1;
        inv[1] = 1;

        for(int i = 2; i <= n; i++){
            f[i] = (f[i - 1] * i) % mod;
            inv[i] = mod - (inv[mod % i] * (mod / i)) % mod;
            fInv[i] = (fInv[i - 1] * inv[i]) % mod;
        }
    }

    long long query(int n, int k){
        if(n < k){
            return 0;
        }
        if(n < 0 || k < 0){
            return 0;
        }
        return (((f[n] * fInv[k]) % mod) * fInv[n - k]) % mod;
    }
};

const int MOD = 1e9 + 7;

int main(){

    int n, a, b;
    cin >> n >> a >> b;

    vector<long long> two(30);
    two[0] = 2;
    for(int i = 1; i < 30; i++){
        two[i] = (two[i - 1] * two[i - 1]) % MOD;
    }

    long long temp1 = 1;
    for(int i = 0; i < 30; i++){
        if(n & (1 << i)){
            temp1 = (temp1 * two[i]) % MOD;
        }
    }

    Com com(max(a, b), MOD);
    long long temp2 = 1;
    for(int i = 0; i < a; i++){
        temp2 = (temp2 * (n - i)) % MOD;
    }
    for(int i = 1; i <= a; i++){
        temp2 = (temp2 * com.inv[i]) % MOD;
    }

    long long temp3 = 1;
    for(int i = 0; i < b; i++){
        temp3 = (temp3 * (n - i)) % MOD;
    }
    for(int i = 1; i <= b; i++){
        temp3 = (temp3 * com.inv[i]) % MOD;
    }

    long long ans = (temp1 - 1 + MOD) % MOD;

    ans = (ans - temp2 + MOD) % MOD;
    ans = (ans - temp3 + MOD) % MOD;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4992
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

count = 0
for i in range(1, N+1, 2):
    ylist = make_divisors(i)
    if len(ylist) == 8:
        count += 1

print(count)

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


const int M = 1000005;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> p(M);
	rep(i, n) cin >> a[i];
	rep(i, n) {
		if (p[a[i]] != 0) {
			p[a[i]] = 2;
			continue;
		}
		for (int j = a[i]; j <= M; j += a[i]) p[j]++;
	}
	int ans = 0;
	rep(i, n) {
		if (p[a[i]] == 1) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7940
n, m = map(int, input().split())
#nは問題数　mは提出数（AC_WAの配列長）

p = [0]*m
p_tmp = "0"
s = [0]*m
check = [0]*n
memory_penalty = [0]*n
for i in range(m):
  p_tmp, s[i] = (map(str, input().split()))
  p[i] = int(p_tmp)
  #pは問題No. 　sはAC or WA
  #check[i] = 0 ならwa 1なら既にac
  
for i in range(n):
  check[i] = 0
  memory_penalty[i] = 0
  
num_correct = 0
num_penalty = 0

for i in range(m):
  if( check[ p[i]-1 ] == 0 and s[i] == "WA"):
    memory_penalty[ p[i]-1 ] = memory_penalty[ p[i]-1 ] + 1
  elif( check[ p[i]-1 ] == 0 and s[i] == "AC"):
    num_correct = num_correct + 1
    num_penalty = num_penalty + memory_penalty[ p[i]-1 ]
    check[p[i]-1] = 1

print(num_correct, num_penalty)

Measured memory_bytes: 14936
H,W=map(int,input().split())
M=[input() for x in range(H)]
A=[[0 for x in range(W)]for y in range(H)]
nx=[-1,0,1]
ny=[-1,0,1]

for i in range(H):
  for j in range(W):
    if M[i][j]=='.':
      cnt=0
      for x in nx:
        for y in ny:
          if (0<= i+x <H) and (0<= j+y <W) and M[i+x][j+y]=="#":
            cnt+=1
      A[i][j]=str(cnt)
    else:
      A[i][j]="#"
      
for i in range(H):
  print("".join(A[i]))

Measured memory_bytes: 3188