akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class FForkInTheRoad {
public:
    int N, M;
    vc<double> dp;
    vvc<int> G;

    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        in>>N>>M;
        G.resize(N);
        REP(i, M){
            int s, t;
            in>>s>>t;
            s--, t--;
            G[s].pb(t);
        }
        dp.resize(N, 0);
        for(int i=N-2;0<=i;--i){
            for(auto& u : G[i]) dp[i] += dp[u];
            dp[i] = dp[i] / LEN(G[i]) + 1;
        }
        double ans = dp[0];
        REP(i, N-1){
            if(LEN(G[i])==1) continue;
            int v = -1;
            double mx = -1;
            for(auto& u : G[i]){
                if(chmax(mx, dp[u])) v = u;
            }
            auto test = [&](int x, int y){
                fill(ALL(dp), 0);
                for(int i=N-2;0<=i;--i){
                    int sz = LEN(G[i]);
                    for(auto& u : G[i]){
                        if(i==x and u==y){
                            --sz;
                            continue;
                        }
                        dp[i] += dp[u];
                    }
                    dp[i] = dp[i] / sz + 1;
                }
                return dp[0];
            };
            chmin(ans, test(i, v));
        }
        out<<fixed<<setprecision(12)<<ans<<'\n';
    }
};


int main() {
	FForkInTheRoad solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 4484
#include <bits/stdc++.h>
#define maxn (int)(2e5)
#define i64 long long
#define pii pair<i64,i64>
#define all(x) x.begin(),x.end()
#define LB(x,v) lower_bound(all(x), v) - x.begin()
#define fread() freopen("in.txt", "r", stdin);
using namespace std;

double v[51];
int main() {
    /*BEFORE SUBMIT, CHECK
    sample i/o format
    statements for debugging are removed/comment out
    global values / stl containers are initialized/cleared for each test (if needed)
    all array size are sufficient
    loop variable or output value doesn't cross min/max limit of input
    */
    // #ifndef ONLINE_JUDGE
    //     fread();
    // #endif

    int n;    
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++) scanf("%lf",&v[i]);
        sort(v,v+n);
        double ans = v[0];
        for(int i=1;i<n;i++){
            //printf("%lf %lf\n", ans, v[i]);
            ans = (ans+v[i])/2.0;
        }
        printf("%lf\n", ans);      
    }   
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main{

public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
       int n=s.nextInt(),m=s.nextInt();
       System.out.println(Math.max(0,n-2*m)); 
    }
}
    
  












Measured memory_bytes: 23892
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if(a <= b){
      System.out.println(a);
    }else{
      System.out.println(a-1);
    }
  }
}

Measured memory_bytes: 23764
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#include <fstream>
#include <cassert>
#include <cmath>
#include <sstream>
#include <time.h>
#include <complex>

#include <unordered_map>
#include <unordered_set>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define DFOR(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define rep(i,n) FOR(i,0,n)
#define repn(i,n) FORN(i,1,n)
#define drep(i,n) DFOR(i,n-1,0)
#define drepn(i,n) DFOR(i,n,1)
#define MAX(a,b) a = Max(a,b)
#define MIN(a,b) a = Min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define Reset(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(all(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)
#define forever for(;;)
#define PINF 1000000000000
#define newline '\n'

#define test if(1)if(0)cerr
using namespace std;

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef pair<char,char> cc;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l4;
const double pi = acos(-1.0);


const int maxn = 1e5+1;
vector<int> g[maxn];
int n;

int dfs(int cur, int p)
{
    int ret = 1;
    for (auto nxt : g[cur]) if (nxt != p)
    {
        ret += dfs(nxt, cur);
    }
    if (ret == 2) ret = 0;
    return ret;
}
int main()
{
    cin >> n;
    rep(i, n-1)
    {
        int u, v;   cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cout << (dfs(1, 0)==0?"Second":"First") << newline;
}


Measured memory_bytes: 5888
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	// AtCoder Beginner Contest 079
	// https://atcoder.jp/contests/abc079/tasks
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int[] mochis = new int[n];
		
		for (int i = 0; i < n; i++) {
			mochis[i] = sc.nextInt();
		}
		Arrays.sort(mochis);
		int res = 1;
		
		for (int i = n - 2; i >= 0; i--) {
			if (mochis[i] < mochis[i+1]) {
				res++;
			}
		}
		System.out.println(res);
	}
	
	static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine()); 
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try{ 
                str = br.readLine(); 
            } catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}


Measured memory_bytes: 21460
import sys
import itertools

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = int(readline())
h = S // 3600
m = (S % 3600) // 60
s = (S % 3600) % 60

print(f'{h}:{m}:{s}')



Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793;

int main(){
  int a[5];
  int b[5];
  rep(i, 5) cin >> a[i];
  rep(i, 5) b[i] = a[i]%10 == 0 ? 20 : a[i]%10;
  sort(b, b+5);
  int k;
  k = b[0] == 20 ? 10 : b[0];
  int ans = 0;
  rep(i, 5){
    a[i] = a[i] - a[i]%10 + (a[i]%10 == 0 ? 0 : 10);
    ans += a[i];
  }
  cout << ans - (10 - k)<<endl;
}

Measured memory_bytes: 256
// agrawal117
//chahatagrawal117
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long int ll;
#define MAX 1005
ll dp[1000009][4];
string s;
ll solve(int i,int carry)
{
    if(i<0)  return carry;
    if(dp[i][carry]!=-1) return dp[i][carry];
    if(carry==1){
        int n=s[i]-'0';
        ll y;
        if(n==9){
            n=0;
            y=solve(i-1,1);
        }
        else{
           n++; 
           y= min(n+solve(i-1,0) , 10-n+solve(i-1,1));
        }
        dp[i][carry]=y;
        return y;
    }
    else{
        int n=s[i]-'0';
        ll y= min(n+solve(i-1,0) , 10-n+solve(i-1,1));
        dp[i][carry]=y;
        return y;
    }
}
int main()
{
     cin>>s;
     for(int i=0;i<s.size()+1;i++)  { dp[i][0]=-1; dp[i][1]=-1; }
     ll ans=solve(s.size()-1,0);
     cout<<ans<<endl;
    
}

Measured memory_bytes: 126340
#include <stdio.h>

int main(){
  int N,K;
  // int A[200000];
  int A;
  scanf("%d %d",&N,&K);
  for(int i=0;i<N;i++)
    //  scanf("%d",&A[i]);
    scanf("%d",&A);
  printf("%d\n",(N-K)/(K-1)+((N-K)%(K-1)?1:0)+1);
  
  return 0;
}


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


int sum[1000010];
void init(){
    for(int i = 2 ; i <= 1000000 ; i++){
        sum[i] = sum[i-1] + 1;
        for(int j = 2 ; j*j <= i ; j++){
            if( i % j == 0 ){
                sum[i]--;
                break;
            }
        }
    }
}
int main() {
    init();
    int n;
    while( cin >> n && n ){
        cout << sum[n] << endl;
    }
}


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

int main()
{
  char input_str[1000];
  char order_str[7];
  char replace_str[1000];
  char temp;

  int order_num;
  int counter_i = 0, counter_j;
  int order_a, order_b;

  scanf("%s", input_str);
  scanf("%d", &order_num);

  for(counter_i = 0 ; counter_i < order_num ; counter_i++)
  {
    scanf("%s %d %d", order_str, &order_a, &order_b);
    if(strcmp(order_str, "print") == 0)
    {
      while(order_a <= order_b)
      {
        printf("%c", input_str[order_a]);
        order_a++;
      }
      printf("\n");
    }

    if(strcmp(order_str, "reverse") == 0)
    {
      while(order_a < order_b)
      {
        temp = input_str[order_a];
        input_str[order_a] = input_str[order_b];
        input_str[order_b] = temp;
        order_a++;
        order_b--;
      }
    }

    if(strcmp(order_str, "replace") == 0)
    {
      scanf("%s", replace_str);
      for(counter_j = 0 ; order_a <= order_b ; counter_j++, order_a++)
      {
        input_str[order_a] = replace_str[counter_j];
      }
    }
  }
}



Measured memory_bytes: 2124
#include<stdio.h>
 
int main(void)
{
  int L,R,d;
  scanf("%d",&L);
  scanf("%d",&R);
  scanf("%d",&d);
  int sum=0;
  for(int i=L;i<=R;i++)
  {
    if(i%d==0)
    {
      sum++;
    }
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

int main(void){
    string in; cin >> in;

    string res = "";
    for(auto & c : in){
        if(c == 'B'){
            if(res.size() >= 1) res.pop_back();
        }
        else {
            res += c;
        }
    }

    cout << res << endl;

    return 0;
}


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>;


void Main()
{
  int x;
  cin >> x;
  if (x >= 30) cout << "Yes" << endl;
  else cout << "No" << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 3652
N, K = map(int, input().split())

L = [1]
P = [1]

for i in range(N):
    L.append(L[i] * 2 + 3)
    P.append(P[i] * 2 + 1)

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + L[N-1]:
        return f(N-1, X-1)
    else:
        return P[N-1] + 1 + f(N-1, X-2-L[N-1])

print(f(N, K))

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll a,b,h;
    cin>>a>>b>>h;
    cout<<(h/2)*(a+b)<<"\n";
}


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

const long long mod = 1e9 + 7;

vector<long long> dp(2005, -1);

long long bfs(long long rem) {
  if ( rem == 0 ) { return 1; }
  if ( rem < 3 )  { return 0; }
  if ( dp[rem] != -1 ) { return dp[rem]; }

  long long ret = 0;
  for ( int i = 3; i <= rem; i++ ) {
    ret += bfs(rem-i);
    ret %= mod;
  }

  dp[rem] = ret;
  return ret;
}

int main() {
  long long s;
  cin >> s;
  cout << bfs(s) << endl;
  return 0;
}


Measured memory_bytes: 3636
import bisect
n = int(input())
lst1 = list(map(int,input().split()))

lst1.sort()

p = 0
ans = 1
if n == 1:
    print(1)
    exit()
while True:
    left = bisect.bisect_left(lst1,p)
    right = bisect.bisect_right(lst1,p+2)
    ans = max(ans,right-left)
    if right>=n:
        break
    p = max(p+1,lst1[left+1])
print(ans)

Measured memory_bytes: 53228
H, W = map(int, input().split())
i = []
for _ in range(H):
    i.append(input())

result = "Yes"
#  .
# .#. が無いか調べる
#  .
for j in range(H-1):
    for k in range(W):
        if i[j][k] == '.':
            if k == 0 or j == H - 1 or i[j+1][k-1] == '.':
                if i[j+1][k] == '#':
                    if j == H - 1 or k == W - 1 or i[j+1][k+1] == '.':
                        if j > H - 3 or i[j+2][k] == '.':
                            result = "No"


print(result)

Measured memory_bytes: 3064
#include<bits/stdc++.h>//懒人专用头文件
#define rpt(n) for(register int ttxyc=0;ttxyc<n;ttxyc++)
using namespace std;
main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%d",(a-c)/(b+c));
}/**/

Measured memory_bytes: 256
def mulmod(x, y, p=10**9 + 7):
    return x * y % p


def combmod(n, k, p=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, p - 2, p) % p


def solve(string):
    x, y = map(int, string.split())
    m0, m1, n = min(x, y), max(x, y), (x + y) // 3
    return "0" if (x + y) % 3 > 0 or m1 / m0 > 2 else str(combmod(n, m0 - n))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read()))


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

// using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
/***** MAIN *****/
signed main() {
  int n;
  cin >> n;
  vector<P> v(n);
  REP(i,n) {
    int posi, arm;
    cin >> posi >> arm;
    v[i] = P(posi+arm, posi-arm);
  }
  SORT(v);
  int ans = 0;
  int cur_right = LLONG_MIN;
  REP(i,n) {
    if(cur_right <= v[i].second) {
      ++ans;
      cur_right = v[i].first;
    }
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 1792
#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 ll  = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

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

    vector<vector<ll>> g(n);
    rep(i, m){
        ll a, b;
        cin >> a >> b;
        a--, b--;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    queue<int> que;
    que.push(0);

    ll dist[n];
    rep(i, n)dist[i] = -1;
    dist[0] = 0;

    ll parent[n];
    rep(i, n)parent[i] = -1;

    while(!que.empty()){
        int pos = que.front();

        que.pop();

        rep(i, g[pos].size()){
            int child = g[pos][i];

            if(dist[child] >= 0)continue;

            dist[child] = dist[pos] + 1;

            parent[child] = pos;

            que.push(child);
        }
    }
    
    cout << "Yes\n";
    for(ll i = 1; i < n; ++i)cout << parent[i] + 1 << endl;
}


Measured memory_bytes: 13584
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 998244353;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

ll power(ll x, ll y) {
	if (y==0) return 1;
	else if (y==1) return x%MOD;
	else if (y%2==0) { ll pow=power(x,y/2); return (pow*pow)%MOD; } 
	else { ll pow=power(x,y/2); return ((pow*pow)%MOD)*x%MOD; }
}

int main(){
	int n, s; cin >> n >> s;
	VI a(n); REP(i,n) cin >> a[i];
	VVI dp(n+1,VI(s+1,0));
	ll p=power(2,MOD-2);
	dp[0][0]=power(2,n);
	REP(i,n){
		REP(j,s+1){
			dp[i+1][j]=dp[i][j];
			if(j-a[i]>=0)
				dp[i+1][j]+=(dp[i][j-a[i]]*p)%MOD;
			dp[i+1][j]%=MOD;
		}
	}
	cout << dp[n][s] << endl;
	return 0;
}


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

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

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            String S = in.next();
            out.println(S.replaceAll("\\?", "D"));

        }

    }
}



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

int main(){
   int x,n;
   cin >> n >> x;
   vector<int> a(n);
   int ans=0;
   for (int i=0;i<n;i++){
      cin >> a.at(i);
   }
   sort(a.begin(),a.end());
   for (int i=0;i<n;i++){
      if(x<a.at(i)){
         cout << ans << endl;
         return 0;
      }
      x-=a.at(i);
      ans++;
   }
   if (x==0) ans++;
   cout << ans-1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N,M;
    cin >> N >> M;
    vector< P >V(M);
    rep(i,0,M){
        int a,b;
        cin >> a >> b;
        V[i] = P(b,a);
    }
    sort(V.begin(), V.end());
    int cnt = 0,pre = 0;
    rep(i,0,M){
        if(V[i].second <= pre)continue;
        pre = V[i].first - 1;
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

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

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
/*bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}*/

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

const ll mod = 1e9 + 7;
const ll IMF = 1LL<<29;
const double PI = 3.14159265358979323846;


// ******************************CODE**********************************//





int main(){


        int n;
        cin >> n;
        string ans = "";
        while(n != 0)
        {
                if(n%2 != 0)
                {
                        n--;
                        ans = "1" + ans;
                }
                else ans = "0" + ans;
                n /= -2;
        }

        //入力が0の時
        if(ans == "") ans = "0";

        cout << ans << endl;
        return 0;





}


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

using namespace std;

#define int long long

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

    string s;

    cin >> s;

    if (s[0] == s[1])
    {
        cout << "Bad" << endl;
        return 0;
    }
    if (s[1] == s[2])
    {
        cout << "Bad" << endl;
        return 0;
    }
    if (s[2] == s[3])
    {
        cout << "Bad" << endl;
        return 0;
    }

    cout << "Good" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1222;
int n,m,a,b,c[N][N];
int main() {
	read(n);read(m);read(a);read(b);
	rep(i,1,n){
		rep(j,1,m)printf("%d",(j<=a)^(i<=b));
		puts("");
	}
	return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;

string S,T;
int memo[26];

int main(){
    cin>>S>>T;

    rep(i,26) memo[i]=-1;
    rep(i,S.size()){
        if(memo[S[i]-'a']==-1){
            //cout<<"memo["<<S[i]-'a'<<"] = "<<T[i]<<endl;
            memo[S[i]-'a']=T[i];
        }else{
            if(memo[S[i]-'a']!=T[i]){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }

    rep(i,26) memo[i]=-1;
    rep(i,T.size()){
        if(memo[T[i]-'a']==-1){
            //cout<<"memo["<<T[i]-'a'<<"] = "<<S[i]<<endl;
            memo[T[i]-'a']=S[i];
        }else{
            if(memo[T[i]-'a']!=S[i]){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }

    cout<<"Yes"<<endl;
}

Measured memory_bytes: 776
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI 3.14159265358979323846264338327950L

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b){
    if(a % b == 0){
        return(b);
    }
    else{
        return(gcd(b, a % b));
    }
}

bool isPalindrome(string s){
    REP(i, s.length() / 2){
        if(s[i] != s[(s.length() - 1) - i]){
            return false;
        }
    }
    return true;
}

//scanf("%lld", &);
//cin >> ;
//cout << ans << endl;

ll N, M, i, j, k, l, tmp, ans, X, T;
ll D, x, y;
ll cnt;

int main(){
    cin >> N >> X >> T;
    tmp = (N + (X - 1)) / X;
    cout << T * tmp << endl;
    return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << (x) << endl
using namespace std;
using ld = long double;
template <typename T, typename A>
inline ostream& operator<<(ostream& os, const vector<T, A>& v)
{
    os << "[";
    for (const auto& p : v) { os << p << ","; }
    return (os << "]" << endl);
}
int main()
{
    int H, N, P, M, K;
    cin >> H >> N >> P >> M >> K, P--;
    vector<int> yoko(H, -1);
    for (int i = 0, A, B; i < M; i++) { cin >> A >> B, yoko[A - 1] = B - 1; }
    vector<vector<ld>> dp(K + 1, vector<ld>(N, 0)), pr(K + 1, vector<ld>(H, 0));
    for (int i = H - 1, rest = H - M; i >= 0; i--) {
        for (int k = 0; k <= K; k++) {
            if (yoko[i] != -1) {
                pr[k][i] = 0;
            } else {
                for (int k = 0; k <= K; k++) { pr[k][i] = (K - k > rest) ? (ld)0 : (ld)(K - k) / rest; }
            }
        }
        rest -= (yoko[i] == -1 ? 1 : 0);
    }
    dp[0][P] = 1;
    for (int i = H - 1; i >= 0; i--) {
        vector<vector<ld>> tmp(K + 1, vector<ld>(N, 0));
        if (yoko[i] != -1) {
            tmp = dp;
            for (int k = 0; k <= K; k++) { swap(tmp[k][yoko[i]], tmp[k][yoko[i] + 1]); }
        } else {
            for (int k = 0; k <= K; k++) {
                const ld p = pr[k][i];
                for (int j = 0; j < N; j++) { tmp[k][j] += dp[k][j] * (1 - p); }
                if (k == K) { break; }
                for (int j = 0; j < N; j++) {
                    if (j == 0 or j == N - 1) {
                        tmp[k + 1][j] += dp[k][j] * (p - p / (N - 1)) + dp[k][j == 0 ? 1 : N - 2] * (p / (N - 1));
                    } else {
                        tmp[k + 1][j] += dp[k][j] * (p - 2 * p / (N - 1)) + (dp[k][j - 1] + dp[k][j + 1]) * (p / (N - 1));
                    }
                }
            }
        }
        dp = tmp;
    }
    cout << fixed << setprecision(15) << *max_element(dp[K].begin(), dp[K].end()) << endl;
    return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector <int> a(n), b(n - 1);
    for (int tsumugi = 0; tsumugi < n - 1; tsumugi++){
        cin >> b[tsumugi];
    }

    long long ans;
    a[0] = b[0];
    for (int karen = 1; karen < n - 1; karen++){
        // ans += b[karen - 1];
        // ans += min({b[karen - 1], b[karen]});
        a[karen] = min(b[karen - 1], b[karen]);
    }
    a.back() = b.back();
    // for (auto x:a){
    //     cout << "a:" << x << endl;
    // }
    ans = accumulate(a.begin(), a.end(), 0);

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

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
int main() {
    int n;
    std::cin >> n;
    int h0 = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int h1;
        std::cin >> h1;
        if (h0 <= h1) {
            h0 = h1;
            ans++;
        }
    }
    std::cout << ans;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<functional>
#include<vector>
#include<queue>
using namespace std;
#define f(i,n) for(int i=0;i<(int)n;i++)
#define MOD 1000000009

int main(void){
	long long k, x, y, ans;

	scanf("%lld %lld %lld", &k,&x,&y);
	if (x >= k)ans = 1;
	else if (x > y){
		ans = (k - x - 1) / (x - y);
		ans = ans * 2 + 3;
	}

	if (x<=y&&x<k)printf("-1\n");
	else printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 128
#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;
    vector<int>l(n);
    rep(i,n)cin>>l[i];
    int count=0;
    sort(l.begin(),l.end());
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if((l[k]==l[j])or(l[j]==l[i]))continue;
                if(l[k]<l[j]+l[i])count++;
            }
        }
    }
    cout<<count;
}

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

int main() {
    int r,x,y;
    cin >> x >> y;
    if(y>x)swap(x,y);
    while(true){
        r = x%y;
        if(r==0){
            cout << y << endl;
            break;
        }
        x=y;
        y=r;
    }
    
    return 0;
}


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

void doRoutine() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(322179);
#ifdef LOCAL
    freopen("/root/alg/clion_main/input.txt", "rt", stdin);
    freopen("/root/alg/clion_main/output.txt", "wt", stdout);
#endif
}

#define DBG(VAR) cerr << #VAR << ": " << VAR << endl

#define all(x) x.begin(), x.end()
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vc vector

#ifndef LOCAL
#define cerr if(0) cerr
#define DBG(...) (true)
#endif

#define D double
#define int long long

// ----------------------------- CODE NOW ------------------------

bool inner(int l, int r, int g) {
    if (l % g == 0) {
        return true;
    }
    int x = l - l % g + g;
    return x < r;
}

void solve(int a, int b, int c, int d) {
    if (a < b) {
        cout << "No" << endl;
    }
    else {
        if (d < b) {
            cout << "No" << endl;
        }
        else {
            if (c >= b - 1) {
                cout << "Yes" << endl;
            }
            else {
                a %= b, d %= b, c %= b;

                if (d == 0) {
                    if (a > c) {
                        cout << "No" << endl;
                    }
                    else {
                        cout << "Yes" << endl;
                    }
                    return;
                }
                if (a > c) {
                    cout << "No" << endl;
                    return;
                }

                int from = c - a + 1;
                int to = b - a;
                int g = __gcd(d, b);
                if (inner(from, to, g)) {
                    cout << "No" << endl;
                }
                else {
                    cout << "Yes" << endl;
                }
            }
        }
    }
}

signed main() {
    doRoutine();

    int t;
    cin >> t;
    while (t--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        solve(a, b, c, d);
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<P> d(n);
	rep(i, 0, n){
		int x, l;
		cin >> x >> l;
		d[i] = {x + l, x - l};
	}
	sort(d.begin(), d.end());
	int r = -INF, ans = 0;
	rep(i, 0, n){
		if(r <= d[i].second){
			r = d[i].first;
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
X,Y,Z,K = map(int,input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]

Dness_AB = []
for a in A:
    for b in B:
        Dness_AB.append(a+b)
Dness_AB.sort(reverse=True)

Dness_ABC = []
for i in range(min(K,len(Dness_AB))):
    for c in C:
        Dness_ABC.append(Dness_AB[i]+c)
Dness_ABC.sort(reverse=True)

for i in range(K):
    print(Dness_ABC[i])


Measured memory_bytes: 150572
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

s = input()
if s == "SSS":
    print(0)
elif s == "RRR":
    print(3)
elif s == "RRS" or s == "SRR":
    print(2)
else:
    print(1)




Measured memory_bytes: 61696
//Author : pakhandi
//
using namespace std;

#include <bits/stdc++.h>

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

#define IGNORE cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');

const ll INF = (1LL << 58);

#ifdef BUGGY
	bool DEBUG = 1;
#endif
#ifndef BUGGY
	bool DEBUG = 0;
#endif

const int MAX_LIMIT = 505;

int N;
int C[MAX_LIMIT], S[MAX_LIMIT], F[MAX_LIMIT];

int getTimeTaken(int station, int currTime) {
	int startTime = S[station];

	if(currTime <= startTime) {
		return (startTime - currTime) + C[station];
	}

	int tempTime = currTime - startTime;
	tempTime %= F[station];
	
	if(!tempTime) {
		return C[station];
	}

	return F[station] - tempTime + C[station];
}

int main()
{
	scanf("%d", &N);
	N--;

	for(int i = 0; i < N; i++) {
		scanf("%d %d %d", &C[i], &S[i], &F[i]);
	}

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

		int currTime = 0;

		for(int i = caseNo; i < N; i++) {
			int timeTaken = getTimeTaken(i, currTime);
			// cout << i << " : " << timeTaken << "\n";
			currTime += timeTaken;
		}

		printf("%d\n", currTime);
	}
	printf("0\n");

	return 0;
}
/*
	Powered by Buggy Plugin
*/

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

int main() {
  double w, h, x, y;
  cin >> w >> h >> x >> y;
  double ans = w * h / 2;
  int num;
  if (w / 2 == x && h / 2 == y) num = 1;
  else num = 0;
  printf("%.10f %d\n", ans, num); 
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func countDivs(n int) (c int) {
	c = 0
	for i := 1; i <= n; i++ {
		if n%i == 0 {
			c++
		}
	}
	return
}

func main() {
	var N int
	fmt.Scan(&N)
	cnt := 0
	for i := 1; i <= N; i = i + 2 {
		if countDivs(i) == 8 {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 512
import math

N, D = map(int,input().split())
XY = list(list(map(int,input().split())) for _ in range(N))

count = 0
for i in range(N):
  if math.sqrt(XY[i][0] ** 2 + XY[i][1] ** 2) <= D: count += 1

print(count)

Measured memory_bytes: 45580
s = int(input())
xy = [0, 0, 10**9, 1, 0, 0]

m = s % xy[2]
d = s // xy[2]

xy[4] = 0 if m == 0 else (xy[2] - m)
xy[5] = d if m == 0 else (d + 1)

print(*xy)


Measured memory_bytes: 38448
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
enum MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std;
// dfmt on

void main()
{
    long a, b;
    scan(a, b);
    writeln(a * b);
}


Measured memory_bytes: 3720
r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)

Measured memory_bytes: 151148
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005;
int n,Q,S1,S2,a[N];
ll s[N],dp[N],ans;
struct wzpakking{
	ll c[N];
	void change(int x,ll v){
		for (;x<=n;x+=x&(-x))
			c[x]=min(c[x],v);
	}
	ll ask(int x){
		ll s=4e18;
		for (;x;x-=x&(-x))
			s=min(s,c[x]);
		return s;
	}
}T[2];
void insert(ll v,int p){
	T[0].change(p,v-p);
	T[1].change(n-p+1,v+p);
}
int main(){
	scanf("%d%d%d%d",&n,&Q,&S1,&S2);
	for (int i=1;i<=Q;i++) scanf("%d",&a[i]);
	for (int i=2;i<=Q;i++) s[i]=s[i-1]+abs(a[i]-a[i-1]);
	for (int i=1;i<=n;i++) T[0].c[i]=T[1].c[i]=4e18;
	insert(abs(S1-a[1]),S2);
	insert(abs(S2-a[1]),S1);
	ans=s[Q]+min(abs(S1-a[1]),abs(S2-a[1]));
	for (int i=2;i<=Q;i++){
		dp[i-1]=min(T[0].ask(a[i])+a[i],T[1].ask(n-a[i]+1)-a[i])+s[i-1];
		ans=min(ans,dp[i-1]+s[Q]-s[i]);
		insert(dp[i-1]-s[i],a[i-1]);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 7296
#include<iostream>
#include<cmath>
using namespace std;
int solve(int E)
{
    int ans=3000000;
    int x;
    for(int y=0;y<=1000;++y)
        for(int z=0;z<=100;++z)
        {
            x=E-y*y-z*z*z;
            if((x+y+z<ans)&&(x>=0))
                ans=x+y+z;
        }
    return ans;
}
int main()
{
    int E;
    while(cin>>E&&E>0)
        cout<<solve(E)<<endl;
    return 0;
}


Measured memory_bytes: 3064
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.List

main :: IO ()
main = do
  [n, h] <- readInts
  ks <- replicateM n readInts
  print $ solve h ks

readInts :: IO [Int]
readInts = map read . words <$> getLine

solve :: Int -> [[Int]] -> Int
solve h ks = solve' h 0 a bs
  where
    a = maximum [ _a | [_a, _] <- ks ]
    bs = sortOn negate $ [ b | [_, b] <- ks, b > a ]

solve' :: Int -> Int -> Int -> [Int] -> Int
solve' !h !n a []
  | h <= 0 = n
  | otherwise = solve' (h - a) (n + 1) a []
solve' !h !n a (b:bs)
  | h <= 0 = n
  | otherwise = solve' (h - b) (n + 1) a bs



  


Measured memory_bytes: 155004
#include<bits/stdc++.h>
using namespace std;
int n,m,a[13],b[13];
string s[13],ss[13];
void dfs1(int x,bool allow){
	if(x==m){
		cout<<"YES"<<endl;
		exit(0);
	}
	else if(b[x]!=-1)
		dfs1(x+1,allow);
	else{
		for(int i=x+1;i<m;i++){
			if(b[i]!=-1) continue;
			bool ok=true;
			for(int j=0;j<n;j++)
				if(s[j][x]!=s[a[j]][i]){
					ok=false;
					break;
				}
			if(ok){
				b[x]=i;
				b[i]=x;
				dfs1(x+1,allow);
				b[x]=-1;
				b[i]=-1;
			}
		}
		if(allow){
			b[x]=x;
			dfs1(x+1,0);
			b[x]=-1;
		}
	}
} 
void dfs2(int x,bool allow){
	if(x==n)
		dfs1(0,(m%2));
	else if(a[x]!=-1)
		dfs2(x+1,allow);
	else{
		for(int i=x+1;i<n;i++){
			if(ss[i]==ss[x]&&a[i]==-1){
				a[x]=i;
				a[i]=x;
				dfs2(x+1,allow);
				a[x]=-1;
				a[i]=-1;
			}
		}
		if(allow){
			a[x]=x;
			dfs2(x+1,0);
			a[x]=-1;
		}
	}
}
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>s[i];
	memset(a,-1,sizeof(a));
	memset(b,-1,sizeof(b));
	for(int i=0;i<n;i++){
		ss[i]=s[i];
		sort(ss[i].begin(),ss[i].end());
	}
	dfs2(0,(n%2));
	cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstddef>
#include <cmath>
#include <iostream>
 
bool check_ratio(const int ratio)
{
  bool result = true;
  if (ratio < 1) {
    result = false;
  }
  else if (100 < ratio) {
    result = false;
  }
  return result;
}
 
int main()
{
  int ratio;
  std::cin >> ratio;
  if (!check_ratio(ratio)) {
    std::cout << "invarid input as ratio. (1 <= ratio <= 100)" << std::endl;
  }
  else {
    std::cout << 2.0 * ratio * M_PI << std::endl;
  } 
}

Measured memory_bytes: 3232
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
vector<ll> node[100005];
bool used[100005]={0};
ll dist[100005]={0};
ll dp_val[100005]={0};
void dfs(ll pos,ll cos){
  dist[pos]=cos;
  used[pos]=true;
  cos++;
  for(int i=0;i<node[pos].size();i++){
    ll to=node[pos][i];
    if(!used[to]){
      used[to]=true;
      dfs(to,cos);
    }
  }
}
ll dp(ll pos){
  used[pos]=true;
  ll zcnt=0,res=0;
  for(int i=0;i<node[pos].size();i++){
    ll son=node[pos][i];
    if(!used[son]){
      ll kans=dp(son);
      res+=kans;
      if(kans==0) zcnt++;
    }
  }
  return dp_val[pos]=res+max(zcnt-1,(ll)0);
}
int main(){
  ll n;
  cin>>n;
  for(int i=0;i<n;i++) used[i]=false;
  for(int i=1;i<n;i++){
    ll s,t;
    cin>>s>>t;
    node[s].push_back(t);
    node[t].push_back(s);
  }
  dfs(0,0);
  ll st=0,md=0;
  for(int i=0;i<n;i++){
    if(dist[i]>md){
      md=dist[i];
      st=i;
    }
  }
  for(int i=0;i<n;i++) used[i]=false;
  ll ans=dp(st);
  cout<<ans+1<<endl;
}


Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int n,a,b,t,s=0;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> a >> b;
	REP(i,0,n){
		cin >> t;
		if(b<=t or t<a) s++;
	}
	
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	long n,p,i, mod;
	cin>>n;
	p=1;
mod=1000000007;
	if (n>1){for (i=1; i<=n; i++) {p=(p*(i%mod)%mod);}}
else p=1;
	cout << p % mod << '\n';
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

void solve(){
  int n, m, k; cin >> n >> m >> k;
  vector<vector<int> > f(n + 1), b(n + 1);
  for(int i = 0; i < m; i++){
    int x, y; cin >> x >> y;
    f[x].push_back(y);
    f[y].push_back(x);
  }
  for(int i = 0; i < k; i++){
    int x, y; cin >> x >> y;
    b[x].push_back(y);
    b[y].push_back(x);
  }
  vector<int> ans(n + 1, 0);
  int id = 0;
  vector<int> visited(n + 1, -1);
  vector<vector<int> > sb(n + 1);
  for(int i = 1; i <= n; i++){
    if(visited[i] != -1) continue;
    queue<int> q;
    q.push(i);
    visited[i] = id;
    sb[id].push_back(i);
    while(q.size() > 0){
      int c = q.front();
      q.pop();
      for(int j = 0; j < f[c].size(); j++){
        int nx = f[c][j];
        if(visited[nx] == -1){
          visited[nx] = id;
          sb[id].push_back(nx);
          q.push(nx);
        }
      }
    }
    id++;
  }
  /*for(int i = 0; i < id; i++){
    for(int j = 0; j < sb[i].size(); j++){
      cout << sb[i][j] << " ";
    }
    cout << endl;
  }*/
  for(int i = 1; i <= n; i++){
    int ans = sb[visited[i]].size() - f[i].size() - 1;
    for(int j = 0; j < b[i].size(); j++){
      if(visited[b[i][j]] == visited[i]) ans--;
    }
    cout << ans << " ";
  }
  cout << endl;

  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 15460
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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 < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    string n;
    cin >> n;

    int sum;
    for (char c : n) {
        sum += (int)(c - '0');
        sum %= 9;
    }

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

    return 0;
}


Measured memory_bytes: 3736