akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;

struct Unionfind {
  vector<int> d;
  Unionfind(int n): d(n, -1) {}
  int root (int x){
    if (d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) {return root(x) == root(y);}
  int size(int x) {return -d[root(x)];}
};

int deg[100005];
vector<int> to[100005];

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  Unionfind uf(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    deg[a]++; deg[b]++;
    uf.unite(a, b);
  }
  rep(i, k){
    int a, b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  rep(i, n){
    int ans = uf.size(i) - 1 - deg[i];
    for (int u : to[i]) if (uf.same(i, u)) ans--;
    printf("%d%c", ans, i==n-1?'\n':' ');
  }
} 

Measured memory_bytes: 6784
N,M,Q = map(int,input().split())
A = [[0 for i in range(N+1)] for j in range(N+1)]
Acum = [[0 for i in range(N+1)] for j in range(N+1)]

for _ in range(M):
    L,R = map(int,input().split())
    A[L-1][R-1] += 1

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q][q]-Acum[p-1][q]-Acum[q][p-1]+Acum[p-1][p-1]
    print(A)


Measured memory_bytes: 15468
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 500;
const int INF = 1<<29;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int dp[MAX][MAX];

int main(){
    //cout<<"hi"<<endl;
    int H,W; cin>>H>>W;
    vector<string>s(H);
    for(int i=0;i<H;i++)cin>>s[i];
    auto id=[&](int x,int y){return x*W+y;};
    for(int i=0;i<MAX;i++){
        for(int j=0;j<MAX;j++)dp[i][j]=INF;
        dp[i][i]=0;
    }

    //cout<<"hi"<<endl;

    for(int x=0;x<H;x++){
        for(int y=0;y<W;y++){
            if(s[x][y]=='#')continue;
            for(int dir=0;dir<4;dir++){
                int nx=x+dx[dir],ny=y+dy[dir];
                if(nx<0 || nx>=H || ny<0 || ny>=W || s[nx][ny]=='#')
                continue;
                dp[id(x,y)][id(nx,ny)]=1;
                dp[id(nx,ny)][id(x,y)]=1;
            }
        }
    }
     //cout<<"hi"<<endl;
    int V=H*W;
    for(int k=0;k<V;k++){
        for(int i=0;i<V;i++){
            for(int j=0;j<V;j++){
                chmin(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
     //cout<<"hi"<<endl;
    int res=0;
    for(int x=0;x<H;x++){
        for(int y=0;y<W;y++){
            if(s[x][y]=='#')continue;
            for(int x2=0;x2<H;x2++){
                for(int y2=0;y2<W;y2++){
                    if(s[x2][y2]=='#')continue;
                    chmax(res,dp[id(x,y)][id(x2,y2)]);
                }
            }
        }
    }
    cout<<res<<endl;

}

Measured memory_bytes: 1280
<?php
  $n = intval(fgets(STDIN));
  
  $p = explode(" ", trim(fgets(STDIN)));
  $count = 0;
  for($i=1; $i<$n-1; $i++){
    if($p[$i-1]>=$p[$i] && $p[$i+1]<$p[$i]){
      $count++;
    }else if($p[$i+1]>=$p[$i] && $p[$i-1]<$p[$i]){
      $count++;
    }
  }

  echo $count."\n";

Measured memory_bytes: 4604
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    int ans = 0;
    for(int i=1; i<n-1; i++){
        ans += (v[i] != min({v[i-1], v[i], v[i+1]}) && v[i] != max({v[i-1], v[i], v[i+1]}));
    }
    cout << ans << endl;
}

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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n,p,ans=1,a=2;

main() {
    cin >> n >> p;
    if(n>=40) {
        ct(ans)
        return 0;
    }
    if (n==1) {
        ct(p)
        return 0;
    }
    while(1) {
        int hoge = pow(a,n);
        if (hoge < 0 || hoge > p) break;
        while (!(p%hoge)) {
            ans *= a;
            p /= hoge;
        }
        if (a==2) a++;
        else a+=2;
    }
    ct(ans)

}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
        sum += a.at(i);
    }

    int m = round((double)sum / n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (a.at(i) - m) * (a.at(i) - m);
    }
    cout << ans << endl;
}   

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

int main() {
    int a, b, c; cin >> a >> b >> c;

    if (a == b && b == c)
        puts("No");
    else if (a == b || b == c || a == c) {
        puts("Yes");
    }
    else
    {
        puts("No");
    }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#include <chrono>
#define int long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
namespace IO{ //IO template by *Julao* Alphagocc!
template<typename T>
void __RI(T&x){
	int ch=getchar(),neg=1;
	x=0;
	for(;!(isdigit(ch)||ch=='-'||ch==EOF);ch=getchar());
	if(ch==EOF)return;
	if(ch=='-')neg=-1,ch=getchar();
	for(;isdigit(ch);ch=getchar())x=x*10+ch-48;
	x*=neg;
}
void R(int&x){__RI(x);}
#ifndef int
void R(int64_t&x){__RI(x);}
#endif
template<typename T1,typename T2>
void R(std::pair<T1,T2>&x){
	R(x.first);
	R(x.second);
}
template<typename T>
void R(std::vector<T>&x){
	for(auto&i:x){R(i);}
}
template<typename T>
void R(T&x){
	std::cin>>x;
}
template<typename T,typename...Args>
void R(T &x,Args&...args){
	R(x),R(args...);
}
char space=' ';
template<typename T>
void __WI(T x){
	if(x==0)putchar('0');
	if(x<0)putchar('-'),x=-x;
	char ch[64];
	int pos=0;
	while(x)ch[pos++]=x%10+48,x/=10;
	while(pos)putchar(ch[--pos]);
}
void W(){}
void W(const int&x){__WI(x);}
#ifndef int
void W(const int64_t&x){__WI(x);}
#endif
void W(const double&x){printf("%lf",static_cast<double>(x));}
void W(const char&x){putchar(x);}
void W(const std::string&x){printf("%s",x.c_str());}
template<typename T1,typename T2>
void W(const std::pair<T1,T2>&x){
	W(x.first);
	W(space);
	W(x.second);
}
template<typename T>
void W(const std::vector<T>&x){
	for (auto it=x.cbegin();it!=x.cend();it++){
		W(*it);
		W(space);
	}
	W('\n');
}
template<typename T>
void W(const T&x){
	std::cout<<x;
}
template<typename T,typename...Args>
void W(const T&x,const Args&...args){
	W(x),W(space),W(args...);
}
template<typename...Args>
void WL(const Args&...args){
	W(args...),W('\n');
}
}; // namespace IO
int n,ans,ax,ay;
pii a[200010];
int h[200010];
signed main(){
	IO::R(n);
	for(int i=1;i<=n;i++)IO::R(a[i].F,a[i+n].F),a[i].S=i,a[i+n].S=-i;
	sort(a+1,a+n+n+1);
	for(int i=1;i<=n;i++){
		ans+=a[i].F;
		ax|=h[abs(a[i].S)];
		h[abs(a[i].S)]++;
		ay|=(a[i].S*a[i-1].S)<0;
	}
	if(ax||!ay)IO::WL(ans);
	else if(a[n].S+a[n+1].S==0)IO::WL(ans+min(a[n+2].F-a[n].F,a[n+1].F-a[n-1].F));
	else IO::WL(ans-a[n].F+a[n+1].F);
	return 0;
}


Measured memory_bytes: 4096
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    String s=sc.next();
    int count=0;

    for (int i=0;i<s.length()-1;i++) {

        if (s.charAt(i)==s.charAt(i+1)) {

        }else{
          count=count+1;
        }

    }

    System.out.println(count+1);
  }
}


Measured memory_bytes: 25644
#include<stdio.h>
int main()
{
  int h,a;
  scanf("%d%d",&h,&a);
  int count=0;
  int sum=0;
  for(int i=0;i<=h;i++)
  {
    sum+=a;
    count++;
    if(sum>=h)
    {
      printf("%d\n",count);
      break;
    }
  }
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
#define int long long
pair<int,int> ans;
const int N=3005;
int f[N],g[N],A,B,C,D,n,m;
signed main()
{
	cin>>A>>B>>C>>D>>n>>m;
	f[0]=1;
	for (int i=0;i<=m;++i)
		if (f[i])
		{
			if (i+A*100<=m)
				f[i+A*100]=1;
			if (i+B*100<=m)
				f[i+B*100]=1;
		}
	g[0]=1;
	for (int i=0;i<=m;++i)
		if (g[i])
		{
			if (i+C<=m)
				g[i+C]=1;
			if (i+D<=m)
				g[i+D]=1;
		}
	ans=mp(-1,-1);
	g[0]=0;
	for (int i=1;i<=m;++i)
		g[i]=g[i]?i:g[i-1];
	for (int i=1;i<=m;++i)
		if (f[i])
		{
			int x=g[min(m-i,i/100*n)];
			if (ans.first==-1||x*ans.first>(x+i)*ans.second)
				ans=mp(i+x,x);
		}
	cout<<ans.first<<' '<<ans.second;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10; //1e-9?
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int d, n; cin >> d >> n;
    if (n == 100)++n;
    FOR(i, 0, d)n *= 100;
    cout << n << "\n";
}

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

using namespace std;

int sum(int n);

int main()
{
	int n;
	
	cin >> n;
	
	vector<int> x(n), y(n);
	double ans = 0;

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

		for (int j = 0; j < i; j++) {
			ans += sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
		}
	}
	
	printf("%.10f\n", ans / (n*0.5));

	return 0;
}

int sum(int n)
{
	return (int)(n * (n + 1) * 0.5);
}


Measured memory_bytes: 256
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def resolve():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()
    k = int(input().rstrip())

    for i in range(k):
        if s[i] != "1":
            print(s[i])
            return

    print(1)


if __name__ == "__main__":
    resolve()


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

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int64_t> stick(n + 1);
    vector<vector<int64_t>> dp(n + 1, vector<int64_t>(n + 1));
    for (int i = 1; i <= n; i++) {
        cin >> stick[i];
        stick[i] += stick[i - 1];
    }
    for (int len = 2; len <= n; len++) {
        for (int s = 0; s + len <= n; s++) {
            dp[s][s + len] = 1e18;
            for (int i = s + 1; i < s + len; i++) {
                dp[s][s + len] = min(dp[s][s + len], dp[s][i] + dp[i][s + len]);
            }
            dp[s][s + len] += stick[s + len] - stick[s];
        }
    }
    cout << dp[0][n] << '\n';
    return 0;
}

Measured memory_bytes: 4400
fun main(args: Array<String>) {
    val n = readLine()?.toInt() ?: return
    val k = readLine()?.toInt() ?: return

    var result = 1

    for (i in 0 until n) {
        if (result <= k) {
            result *= 2
        } else {
            result += k
        }
    }

    println(result)
}

Measured memory_bytes: 31772
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // freopen("input.txt", "r", stdin);

    long long n, m, x; cin >> n >> m >> x;
    vector<int> h(n); REP(i, n) cin >> h[i];
    vector<vector<pair<int, int> > > edge(n);
    REP(i, m) {
        int a, b, t; cin >> a >> b >> t; --a; --b;
        edge[a].emplace_back(b, t);
        edge[b].emplace_back(a, t);
    }
    vector<long long> cost(n, LINF);
    cost[0] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > que;
    que.emplace(0, 0);
    while (!que.empty()) {
        auto pr = que.top(); que.pop();
        long long now_cost = pr.first;
        int now_ver = pr.second;
        long long now_height = max(x - now_cost, 0LL);

        if (cost[now_ver] < now_cost) continue;

        if (now_ver == n - 1){
            cout << cost[n-1] + h[n-1] - max(x - cost[n-1], 0LL) << '\n';
            return 0;
        }

        for (auto eda : edge[now_ver]) {
            int nx_ver = eda.first;
            long long len = eda.second;
            long long nx_cost = cost[now_ver];

            if (h[now_ver] - len < 0)
                continue;

            if (now_height - len > h[nx_ver]) {
                nx_cost += now_height - h[nx_ver];
            }
            else if (now_height - len > 0) {
                nx_cost += len;
            }
            else {
                nx_cost += len - now_height + len;
            }

            if (nx_cost < cost[nx_ver]) {
                cost[nx_ver] = nx_cost;
                que.emplace(nx_cost, nx_ver);
            }
        }
    }
    if (cost[n-1] == LINF) cout << -1 << '\n';
//    else cout << cost[n-1] + h[n-1] - max(x - cost[n-1], 0LL) << '\n';
    // REP(i, n) cout << cost[i] << '\n';
    return 0;
}



Measured memory_bytes: 16020
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  long long int a[10001000];
  int count = 0;
  for(int i=0; i < 3*N; i++){
    cin >> a[i];
  }
  
 sort(a, a + 3*N, greater<int>());
  
  long long ans = 0;
  
  for(int i = 0; i < 2*N; i++){
    if(i%2 == 0){
      continue;
  }
    else{
      ans += a[i];
    }
  }
  
 
 
  cout << ans << endl;
   
}

Measured memory_bytes: 4352
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [0] + a
dp = [a] #dp[k][i]はiから2^k回移動した後にいる町の番号
for x in range(1,60):#2^0～2^100回まで移動した
    dp.append([0]) #先頭を0に
    for i in range(1,n+1):
        j = dp[x-1][i] #k-1回移動した後にいる場所
        dp[x].append(dp[x-1][j])

now = 1

for i in range(60):
    if k & 2 ** i > 0: #k=5(101)の場合1回移動してから4回移動
        now = dp[i][now] #nowから2^iだけ移動する
        k -= 2 ** i
print(now)

Measured memory_bytes: 218048
import java.util.*;

public class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int length = sc.nextInt();
    char[] array = sc.next().toCharArray();
    long[] rgb = new long[3];   // r -> 0, g -> 1, b -> 2

    for ( int i = 0; i < array.length; i++ ) {
      switch ( array[i] ) {
        case 'R':
          rgb[0]++;
          break;
        case 'G':
          rgb[1]++;
          break;
        case 'B':
          rgb[2]++;
          break;
      }
    }

    long sum = rgb[0] * rgb[1] * rgb[2];
    for ( int i = 0; i < length - 2; i++ ) {
      for ( int j = i + 1; j < length - 1; j++ ) {
        final int k = (j << 1) - i;
        if ( k >= length ) break;
        var con1 = array[i] != array[j];
        var con2 = array[i] != array[k];
        var con3 = array[j] != array[k];
        if ( con1 && con2 && con3 ) sum--;
      }
    }
    System.out.println(sum);
  }
}


Measured memory_bytes: 36360
//
//  main.cpp
//  ALDS1_10_B:MatrixChainMultiplication
//
//  Created by Kang on 2020/8/14.
//  Copyright © 2020 Kang. All rights reserved.
//

#include <cstdio>
using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    int p[101];       // 矩阵维数
    int dp[101][101]; // 只用上三角
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i], &p[i+1]);
    }
    // j-i = dif, dif = 0, 1, ..., n - 1
    for (int dif = 0; dif < n; dif++) {     // dif = j - i;
        for (int i = 1; i <= n-dif; i++) {  // i表示行数
            if(dif == 0) {dp[i][i] = 0;}
            else {
                int min = ~(1 << 31);
                int tmp;
                for (int k = i; k < i + dif; k++) {
                    tmp = dp[i][k] + dp[k + 1][i+dif] + p[i-1] * p[k] * p[i + dif];
                   /*printf("dp[%d][%d] + dp[%d][%d] + p[%d] * p[%d] * p[%d] = %d\n",
                          i, k, k+1, i+dif, i-1, k, i+dif, tmp);*/
                    if (tmp < min) min = tmp;
                }
                dp[i][i+dif] = min;
                
                // printf("dp[%d][%d] = %d\n",i, i+dif, min);
                // printf("--------------------\n");
            }
        }
    }
    printf("%d\n", dp[1][n]);
    
    return 0;
}



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

using namespace std;

int n;
vector<double> p;
vector<vector<double>> dp;

int main(){
    cin>>n;
    p.resize(n + 1);
    // this part is important for solving the problem start from 1 not from 0.
    dp.resize(n + 1, vector<double>(n + 1));
    for(int i = 1; i <= n; i++){
        cin>>p[i];
    }
    vector<double> pp(n + 1);
    pp[0] = 1.0;
    for(int i = 1; i <= n; i++){
        pp[i] = pp[i-1] * (1 - p[i]);
    }
    dp[0][0] = 1.0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0){
                dp[i][0] = pp[i];
            }else{
                dp[i][j] = p[i] * dp[i-1][j-1] + (1 - p[i]) * dp[i-1][j];
            }
        }
    }
    auto res = 0.0;
    for(int i = n/2 + 1; i <= n; i++){
        res += dp[n][i];
    }
    cout<<setprecision(15)<<endl;
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 73664
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Area {
	Area(double x, double y, double s){
		x1 = x - s; y1 = y - s;
		x2 = x + s; y2 = y + s;
	}
	double x1, y1, x2, y2;
};

int main(){
	for(int dataset = 1; true; ++dataset){
		int n;
		cin >> n;
		if(n == 0){ break; }
		vector<Area> areas;
		for(int i = 0; i < n; ++i){
			double x, y, s;
			cin >> x >> y >> s;
			areas.push_back(Area(x, y, s));
		}
		set<double> xpos;
		for(int i = 0; i < n; ++i){
			xpos.insert(areas[i].x1);
			xpos.insert(areas[i].x2);
		}
		double answer = 0.0, height = 0.0, curx = *(xpos.begin());
		for(set<double>::iterator it = xpos.begin(); it != xpos.end(); ++it){
			answer += height * (*it - curx);
			curx = *it;
			vector< pair<double, int> > ypos;
			for(int i = 0; i < n; ++i){
				if(areas[i].x1 <= *it && *it < areas[i].x2){
					ypos.push_back(make_pair(areas[i].y1, 1));
					ypos.push_back(make_pair(areas[i].y2, -1));
				}
			}
			sort(ypos.begin(), ypos.end());
			int depth = 0;
			double nextheight = 0.0, prevy = 0.0;
			for(int i = 0; i < ypos.size(); ++i){
				pair<double, int> entry = ypos[i];
				if(depth == 0 && entry.second > 0){
					prevy = entry.first;
				}else if(depth == 1 && entry.second < 0){
					nextheight += (entry.first - prevy);
					prevy = entry.first;
				}
				depth += entry.second;
			}
			height = nextheight;
		}
		printf("%d %.2lf\n", dataset, answer);
	}
	return 0;
}

Measured memory_bytes: 0
from collections import deque

h,w=map(int,input().split())
sx,sy=1,1
gx,gy=h,w
w+=2

grh=[list('#')*w]
res=0
for i in range(h):
    tmp=input()
    res+=tmp.count('.')    
    grh+=[list('#'+tmp+'#')]
grh+=[list('#')*w]
h+=2


def bfs():
    que=deque()
    g=[[float('inf')]*w for i in range(h)]
    g[sx][sy]=1
    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que.append((sx,sy))

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if grh[nx][ny]=='.' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1

    return g[gx][gy]


res-=bfs()
print(-1 if res==float('-inf') else res)

Measured memory_bytes: 3316
k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9):
    tmp=[]
    for val in cand[-1]:
        s=str(val)
        if s[-1]=='0':
            tmp.append(val*10)
            tmp.append(val*10+1)
        elif s[-1]=='9':
            tmp.append(val*10+8)
            tmp.append(val*10+9)
        else:
            tmp.append(val*10+(int(s[-1])-1))
            tmp.append(val*10+(int(s[-1])))
            tmp.append(val*10+(int(s[-1])+1))
    cand.append(tmp)
ans=[]
for i in range(len(cand)):
    for val in cand[i]:
        ans.append(val)
ans=sorted(ans)
print(ans[k-1])

Measured memory_bytes: 15108
#include <iostream>
#include <cmath>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <bitset>
#include <iomanip>
#include <map>
#include <queue>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Graph = vector<vector<T>>;

struct Dest {
    int to;
    int cost;
};

struct Node {
    vector<Dest> dests;
    int id;
    int distance;
    int dest;
    bool checked;
};

void printFixedDouble(double d, int fix) {
    cout << std::fixed;
    cout << std::setprecision(fix) << d << endl;
}

int main() {
    int nodeNum, linkNum;
    cin >> nodeNum >> linkNum;
    vector<Node> nodes(nodeNum);
    rep(i, nodeNum) {
        Node n;
        n.id = i + 1;
        n.distance = -1;
        n.dest = -1;
        n.checked = false;
        nodes[i] = n;
    }
    rep(i, linkNum) {
        int s, t;
        cin >> s >> t;
        nodes[s-1].dests.push_back({.to = t-1, .cost = 1});
        nodes[t-1].dests.push_back({.to = s-1, .cost = 1});
        // nodes[t].dests.push_back({.to = s, .cost = d});
    }

    auto compare = [](Node x, Node y) {
        return x.distance > y.distance;
    };

    int startIndex = 0;
    std::priority_queue<Node, vector<Node>, decltype(compare)> queue{compare};
    nodes[startIndex].distance = 0;
    queue.push(nodes[startIndex]);

    while (!queue.empty()) {
        Node n = queue.top();
        queue.pop();
        if (n.checked) continue;
        n.checked = true;
        for (auto& next : n.dests) {
            if (nodes[next.to].distance == -1 || nodes[next.to].distance > n.distance + next.cost) {
                nodes[next.to].distance = n.distance + next.cost;
                nodes[next.to].dest = n.id;
                queue.push(nodes[next.to]);
            }
        }
    }

    // rep(i, nodeNum) {
    //     if (nodes[i].dest == -1) {
    //         cout << "No" << endl;
    //         return 0;
    //     }
    // }

    cout << "Yes" << endl;
    reps(i, 1, nodeNum) {
        cout << nodes[i].dest << endl;
    }
}

Measured memory_bytes: 20752
#include<stdio.h>

int main(){

    int N;
    scanf("%d", &N);

    int B[N-1];
    for (int i = 0; i < N-1; i++){
        scanf("%d", &B[i]);
    }

    int sum = 0;

    for (int i = 0; i < N; i++){

        if(i == 0){
            sum += B[i];
        }else if(i == N-1){
            sum += B[i-1];
        }else{

            if(B[i-1] <= B[i]){
                sum += B[i - 1];
            }else{
                sum += B[i];
            }
        }
    }

    printf("%d", sum);

    return 0;
}

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

const int MAX_N = 1 << 17;
const int def = 0;
const int INF = 1 << 25;

struct MaxSegTree {
	int n;
	ll dat[2 * MAX_N - 1];
	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = def;
	}

	void update(int k, ll a) {
		k += n - 1;
		dat[k] = a;
		while(k > 0) k = (k - 1) / 2, dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}

	ll query(int a, int b) { return query(a, b, 0, 0, n); }

	ll query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return def;
		if(a <= l && r <= b) return dat[k];
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}

	void show() {
		for(int i = 0; i < n; i++) cout << dat[i + n - 1] << " ";
		cout << endl;
	}
};


MaxSegTree st;

typedef pair<ll, int> P;
ll x[100000];
ll dp[100000];

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

	ll n;
	cin >> n;
	st.init(n);
	vector<P> v;
	for(int i = 0; i < n; i++) {
		cin >> x[i];
		v.push_back({ x[i], i });
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for(auto t : v) {
		int i = t.second;
		dp[i] = x[i] + st.query(i + 1, n);
		st.update(i, dp[i]);
	}

	ll ans = n * (n + 1) / 2 - st.query(0, n);
	cout << ans << endl;
}

Measured memory_bytes: 8228
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
X=sorted([(A[i],B[i]) for i in range(N)],key=lambda x:x[1])
A=[X[i][0] for i in range(N)]
B=[X[i][1] for i in range(N)]
C=sorted([(A[i],i) for i in range(N)],key=lambda x:x[0])
for i in range(N):
    if C[i][0]>B[i]:
        print("No")
        exit()
if len(set(A))<N:
    print("Yes")
    exit()
Y=[0 for i in range(N)]
j=0
for i in range(N):
    Y[j]=1
    j=C[j][1]
    
if sum(Y)==N:
    #A:C[i][0]
    #B:X[i][1]
    for i in range(N-1):
        if C[i+1][0]<=X[i][1]:
            print("Yes")
            exit()
    print("No")
else:
    print("Yes")


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

int main(void) {
    string S;cin>>S;
    int pointer = S.size();
    while (pointer > 0) {
        if (pointer >= 5 && S.substr(pointer - 5, 5) == "dream") {
            pointer -= 5;
        } else if (pointer >= 7 && S.substr(pointer - 7, 7) == "dreamer") {
            pointer -= 7;
        } else if (pointer >= 5 && S.substr(pointer - 5, 5) == "erase") {
            pointer -= 5;
        } else if (pointer >= 6 && S.substr(pointer - 6, 6) == "eraser") {
            pointer -= 6;
        } else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 512
//abc066_b ss


#include <bits/stdc++.h>
using namespace std;

namespace
{
bool Chk( const char *S, const int iNum )
{
int i;
char C;

	for( i = 0; i < iNum; i++ )
	{
		C = S[ i ];
		if( C == '\0' || C != S[ i + iNum ] ) return false;
	}

	return true;
}


}

int main()
{
int i;
int iLen;
char S[ 210 ];

	cin >> S;
	iLen = strlen( S );
	for( i = iLen / 2 - 1; i > 0; i-- )
	{
		if( Chk( S, i ) )
		{
			cout << i * 2 << endl;

			return 0;
		}
	}

	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 repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rrepa(i,a,n) for(int i=n-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

int main(){

    int x;
    rep(i,5){
        cin>>x;
        if(x==0){
            cout<<i+1<<"\n";
            return 0;
        }
    }

    return 0;

}

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

using namespace std;

struct isp {
  int i;
  string s;
  int p;
};

int main(){
  int n,p;
  string s;
  cin >> n;
  vector<isp> isps;
  for(int i=0;i<n;i++){
    cin >> s >> p;
    isps.push_back({i+1, s, p});
  }

  sort(isps.begin(), isps.end(), [](const isp& x, const isp& y){return x.s < y.s;});
  stable_sort(isps.begin(), isps.end(),
  [](const isp& x, const isp& y){
    if(x.s==y.s)
      return x.p > y.p;
    else
      return x.p == y.p;});

  for(int i=0;i<n;i++){
    cout << isps[i].i << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>

void run(void){
  int n;
  scanf("%d",&n);
  int a[51];
  int i;
  for(i=1;i<=n;i++) scanf("%d",a+i);
  int min=1,max=1;
  for(i=2;i<=n;i++){
    if(a[min]>a[i]) min=i;
    if(a[max]<a[i]) max=i;
  }
  printf("%d\n",2*n-1);
  if(a[min]>=0 || a[max]>=-a[min]){
    for(i=1;i<=n;i++) printf("%d %d\n",max,i);
    for(i=2;i<=n;i++) printf("%d %d\n",i-1,i);
  } else {
    for(i=1;i<=n;i++) printf("%d %d\n",min,i);
    for(i=n-1;i>=1;i--) printf("%d %d\n",i+1,i);
  }
}

int main(void){
  run();
  return 0;
}


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

const ll INF=1e18+7;

int f(int x) { return max(0, min(x, 255)); }

int main() {
  int n,m; 

  while (1) {
    cin>>n>>m;
    if (n==0&&m==0) break;
    vector<int> c(m),x(n);
    rep(i, m) cin>>c[i];
    rep(i, n) cin>>x[i];

    vector<vector<ll>> dp(n+1, vector<ll>(256, INF));
    dp[0][128]=0;
    rep(i, n) {
      rep(j, 256) {
        if (dp[i][j]==INF) continue;
          rep(k, m) {
          int y=f(j+c[k]);
          dp[i+1][y]=min(dp[i+1][y], dp[i][j]+(ll)(x[i]-y)*(ll)(x[i]-y));
        }
      }
    }
    ll res=INF;
    rep(i, 256) res=min(res, dp[n][i]);
    cout<<res<<endl;
  }
}



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

int main() {
  int n,m,x;
  cin >> n >> m >> x;
  int64_t ans=10000000000;
  vector<int> mo(n);
  vector<vector<int>> sk(n,vector<int>(m));
  rep(i,n){
    cin >> mo.at(i);
    rep(j,m){
      cin >> sk.at(i).at(j);
    }
  }
  int64_t ka=0;
  
  for (int tmp = 0; tmp < (1 << n); tmp++) {
    vector<int> ri(m,0);
    bitset<12> s(tmp);
    rep(i,n)rep(j,m){
      if(s.test(i)) ri.at(j)+=sk.at(i).at(j);
    }
    rep(i,n){
      if(s.test(i)) ka+=mo.at(i);
    }
    bool j=true;
    rep(i,m){
      if(ri.at(i)<x) j=false;
    }
    if(j==true) ans=min(ans,ka);
    ka=0;
  }
  
  if(ans!=10000000000) cout << ans << endl;
  else cout << -1 << endl;
  
}

Measured memory_bytes: 3636
w = input()
a = "abcdefghijklmnopqrstuvwxyz"
w_list = list(a)
hoge = 0
for word in w_list:
  s = w.count(word)
  if s%2 != 0:
    print('No')
    hoge += 1
    break
if hoge == 0:
  print('Yes')

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

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

long long INF = 1LL<<60;
int main(){
    int n=-1,k=-1;
    while(true){
    cin>>n>>k;
    if(n==0&&k==0)break;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    vector<ll> sum(n+1,0);
    rep(i,n)sum[i+1]=sum[i]+a[i];
    ll max=-INF;
    rep(i,n-k){
        chmax(max,sum[i+k]-sum[i]);
    }
    cout<<max<<endl;
    }
}





Measured memory_bytes: 3888
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    X = int(input())
    C = X // 100
    if X >= C * 100 and X <= C * 105:
        print(1)
    else:
        print(0)

if __name__=="__main__":
    main()

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


int main() {
  int a;
  cin >> a;
  
 
  double b = 3.141592;
  cout <<2*a*b << endl; 
  

  
}





Measured memory_bytes: 3808
void main() {
    int[] a = readln.split.to!(int[]);
    writeln(a.reduce!max - a.reduce!min);
}

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

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	char a, b;
	cin >> a >> b;
	printf((a < b) ? "<\n" : (a == b) ? "=\n" : ">\n");
}

Measured memory_bytes: 256
n=int(input())
s=input()
s=s[::-1]
e=0;w=0
for i in range(n):
    e+=(s[i]=="E")
    w+=(s[i]=="W")

w2=w
e2=0
ans=n-1
for i in range(n):
    w2-=(s[i]=="W")
    ans=min(ans,w2+e2)
    e2+=(s[i]=="E")
print(ans)




Measured memory_bytes: 9716
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main()
{
    string S, T;
    cin >> S >> T;
    int n = S.size();
    vector<int> sdist(26, 0), tdist(26, 0);
    for (int i = 0; i < n; ++i)
    {
        ++sdist[S[i] - 'a'];
        ++tdist[T[i] - 'a'];
    }
    if (sdist.size() != tdist.size())
    {
        cout << "No" << endl;
        return 0;
    }

    sort(sdist.begin(), sdist.end());
    sort(tdist.begin(), tdist.end());
    for (int i = 0; i < 26; ++i)
    {
        if (sdist[i] != tdist[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3916
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	A, B, K := nextInt(), nextInt(), nextInt()
	if K <= A {
		A -= K
	} else if K-A <= B {
		B -= K - A
		A = 0
	} else {
		A, B = 0, 0
	}
	fmt.Println(A, B)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

int main() {
  i64 N, M;
  cin >> N >> M;
  if(N % 2 == 1) {
    rep(i,0,M) {
      cout << (i + 1) << " " << ((N - i)) << endl;
    }
  }
  else {
    i64 on = 0;
    rep(i,0,M) {
      if(i * 2 >= N - i * 2 - 2) {
        on = 1;
      }
      cout << (i + 1) << " " << ((N - i - on)) << endl;
    }
  }
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll; 


int main() {
	int n;
	cin >> n;
	double x[n], y[n];

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

	double totalTwo = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			double dx = x[i] - x[j];
			double dy = y[i] - y[j];
			double cur = sqrt(dx * dx + dy * dy);
			totalTwo += cur;
		}
	}

	cout << fixed << setprecision(9) << totalTwo / (double) n << endl;



	return 0;
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;


const ll mx = 1e5+9;
ll dp[mx][2];
int main(){
	
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    dp[0][0]=1; dp[0][1]=2;
    
    string s; cin>>s;
    ll n=s.size();
    REP(i,n-1){
        if(s[i+1]=='1'){
            dp[i+1][0] = 3*dp[i][0] + dp[i][1];
            dp[i+1][1] = 2*dp[i][1];
            dp[i+1][0]%=mod; dp[i+1][1]%=mod;
        }
    
        else{
            dp[i+1][0] = 3*dp[i][0];
            dp[i+1][1] = dp[i][1];
            dp[i+1][0]%=mod; dp[i+1][1]%=mod;
        }
    }
    cout<< (dp[n-1][0]+dp[n-1][1]) % mod <<endl;
    return 0;
}

Measured memory_bytes: 2000
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int mod = 1e9 + 7;

int dp[1<<18][44][2];
int n, x, y, z;

int good(int msk){
	return (msk >> z) % 2 && (msk >> (z + y)) % 2 && (msk >> (x + y + z)) % 2;
}

int f(int msk, int n, int dx){
	if(n == 0) return dx;
	if(~dp[msk][n][dx]) return dp[msk][n][dx];
	lint ret = 0;
	for(int i=1; i<=10; i++){
		int nmsk = (msk << i) | 1;
		nmsk &= (1<<18)-1;
		ret += f(nmsk, n - 1, dx | good(nmsk));
	}
	return dp[msk][n][dx] = ret % mod;
}

int main(){
	cin >> n >> x >> y >> z;
	memset(dp, -1, sizeof(dp));
	cout << f(1, n, 0) << endl;
}


Measured memory_bytes: 90368
S = input()
T = input()
N = len(S)
L = len(T)

ans = float("inf")
for i in range(N):
    if N-i < L:
        break
    tmp = 0
    for s, t in zip(S[i:i+L], T):
        if s != t:
            tmp += 1
    if ans > tmp:
        ans = tmp

print(ans)

Measured memory_bytes: 73476
#include<bits/stdc++.h>
using namespace std;
int a[15];
long long ans,k;
string s;
void dfs(long long cn,int st)
{
	if(st==s.size())
	{
		k+=cn;
		ans+=k;
		return;
	}
	long long tmp=k;
	dfs(cn*10+a[st+1],st+1);
	k=tmp+cn;
	dfs(a[st+1],st+1);
}
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
		a[i+1]=(s[i]-'0');
	dfs(a[1],1);
	cout<<ans;

	return 0;
}


Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        BitSet[] bs = new BitSet[n];
        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
            bs[i] = new BitSet(25);
            int tmp = a[i];
            for(int j=24; j>=0; j--){
                int pow = (int)Math.pow(2, j);
                if(tmp >= pow){
                    bs[i].set(j);
                    tmp -= pow;
                }
            }
        }
        sc.close();

        long ans = n;

        if(n == 1){
            System.out.println(1);
            return;
        }

        int l=0, r = 1;
        BitSet cbs = (BitSet)bs[0].clone();

        while(true){
            BitSet tmp = (BitSet)cbs.clone();
            tmp.and(bs[r]);
            if(tmp.cardinality() == 0){
                ans += r - l;
                cbs.or(bs[r]);
                r++;                
            }else{
                cbs.xor(bs[l]);
                l++;
            }
            if(l == r){
                cbs = (BitSet)bs[r].clone();
                r++;
            }            
            if(r == n) break;
        }

        // boolean flag = false;
        
        // while(true){
        //     BitSet tmp = (BitSet)cbs.clone();
        //     tmp.and(bs[r]);
        //     if(tmp.cardinality() == 0){
        //         if(flag){
        //             ans += r-l;
        //             flag = false;
        //         }else{
        //             ans++;
        //         }
        //         cbs.or(bs[r]);
        //         r++;                
        //     }else{
        //         cbs.xor(bs[l]);
        //         l++;
        //         flag = true;
        //     }
        //     if(l == r){
        //         cbs = (BitSet)bs[r].clone();
        //         r++;
        //         flag = false;
        //     }            
        //     if(r == n) break;
        // }
        // ans += (n - l)*(n-l - 1) / 2 - (n-l-1);

        System.out.println(ans);
    }
}

Measured memory_bytes: 102112
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>

using namespace std;

int main(){
  int a,b,c, n;
  cin >> n;
  int w[100];
  int t[100];
  for(int i = 0; i < n ; i++){
    cin >> w[i];
  }
  t[0] = w[0];
  for(int i = 1 ; i < n ; i++){
    t[i] = t[i-1] + w[i];
  }
  int min = 10000;
  for(int i = 0 ; i < n ; i++){
    if(min > abs(t[n-1] - t[i] - t[i])){
      min = abs(t[n-1] - t[i] - t[i]);
    }
  }
  cout << min  << endl;
}


Measured memory_bytes: 256
def get_two_int():
    two_int = input().split()
    for i in range(2):
        two_int[i] = int(two_int[i])
    return two_int

def distribute_stone(candidate_num, stone_num):
    bowl_stone = stone_num
    candidate_list = [0] * candidate_num
    i = 0
    while True:
        order = i % candidate_num
        if bowl_stone != 0:
            candidate_list[order] += 1
            bowl_stone -= 1
        elif bowl_stone == 0 and candidate_list[order] == stone_num:
            return order
        else:
            bowl_stone = candidate_list[order]
            candidate_list[order] = 0
        i += 1


if __name__ == "__main__":
    while True:
        candidate_num, stone_num = get_two_int()
        if candidate_num == 0:
            break
        # print("candidate_num", candidate_num) # debug
        # print("stone_num", stone_num) # debug
        order = distribute_stone(candidate_num, stone_num)
        # print("order", order) # debug
        print(order)



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

using namespace std;

int main()
{
  int A, B, C;
  cin >> A >> B >> C;
  if (A * A + B * B == C * C)
    cout << A * B / 2 << endl;
  else if (A * A + C * C == B * B)
    cout << A * C / 2 << endl;
  else
    cout << B * C / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
using lint=long long;
#define debug(output) cout<<#output<<"= "<<output<<endl
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int n;cin>>n;
  int sn=0;
  int buf=n;
  while(buf>0){
      sn+=buf%10;buf/=10;
  }
	if(n%sn==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
  return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

ll col(ll n){
    if (n % 2LL == 0) return n / 2LL;
    else return 3LL * n + 1LL;
}

int main() {
    int n; cin >> n;
    if (n == 3 || n == 5 || n == 7) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

int main(){
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    if (a + b > c + d){
        cout << "Left" << endl;
    }else if (a + b < c + d){
            cout << "Right" << endl;
    }else{
        cout << "Balanced" << endl;
    }

return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0);
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
int main() {
    IO;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(c - a) <= d|| (abs(b - a) <= d && abs(c - b) <= d)) cout << "Yes"; else cout << "No";
    return 0;
}


Measured memory_bytes: 256