akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

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

	short n; // [2, 20]
	cin >> n;
	short a[n], b[n], c[n];

	short i; //[0, 19]
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (i = 0; i < n; ++i) {
		cin >> b[i];
	}
	for (i = 0; i < n - 1; ++i) {
		cin >> c[i];
	}

	int sat = 0;
	for (i = 0; i < n; ++i) {
		sat += b[a[i] - 1];
		if (i > 0 && a[i - 1] + 1 == a[i]) {
			sat += c[a[i - 1] - 1];
		}
	}

	cout << sat << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#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;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

    int H, W, K;
    cin >> H >> W >> K;

    vs c(H);
    rep(i, H) cin >> c[i];

    ll ans = 0;

    for (int bith = 0; bith < (1 << H); ++bith)
    {
        set<int> hs;
        for (int i = 0; i < H; ++i)
        {
            if (bith & (1 << i)) hs.insert(i);
        }

        for (int bitw = 0; bitw < (1 << W); ++bitw)
        {
            set<int> ws;
            for (int i = 0; i < W; ++i)
            {
                if (bitw & (1 << i)) ws.insert(i);
            }

            ll count = 0;
            rep(i, H)
            {
                if (hs.count(i) > 0) continue;
                rep(j, W)
                {
                    if (ws.count(j) > 0) continue;

                    if (c[i][j] == '#') count++;
                }
            }

            if (count == K)
            {
                ans++;
            }
        }
    }

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

Measured memory_bytes: 3620
// kartikay26
#include <bits/stdc++.h>
using namespace std;
#define debug(x...) 
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
void print(){cout << endl;} void prints(){}
template<typename T=int> T get(){T x; cin >> x; return x;}
template<typename T> void get(T* x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T> void get(T& x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T, typename... A> void print(T x,A... r){cout << x << " ";print(r...);}
template<typename T, typename... A> void prints(T x,A... r){cout << x << " ";prints(r...);}
typedef long long int ll; typedef double db; typedef vector<ll> vi; typedef pair<ll, ll> pii;
#define int ll
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clear(x) memset(x, 0, sizeof(x))
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int mod = 1e9+7;
const int N = 1e6+1;

int32_t main(){

	int n = get();
	db p[n];
	get(p, n);
	debug(arr(p, n+1));

	//  prob = dp[heads]

	db dp[n+2];
	clear(dp);

	dp[0] = 1;

	for (int i = 0; i < n; ++i) {
		for (int h = n; h >= 0; --h) {
			dp[h+1] += dp[h] * p[i];
			dp[h] *= (1-p[i]);
		}
		debug(arr(dp, n+1));
	}

	db ans = 0;
	for (int h = n/2+1; h <= n; ++h) {
		ans += dp[h];
	}

	printf("%.10f\n", ans);
	
	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    s = input()
    n = len(s)
    if n <= k:
        print(s)
    else:
        print(s[:k] + "...")


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9164
#define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
//#include <bits/stdc++.h>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// print(x, y, z);
// print(va.begin(), va.end());
void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}
template<typename Iterator> void printVec(Iterator begin, Iterator end)
{
  for (Iterator it = begin; it != end; it++) {
    std::cout << "[" << std::distance(begin, it) << "] " << *it << " ";
    if (std::distance(begin, it) % 20 == 19) { std::cout << std::endl; }
  }
  std::cout << std::endl;
}

template<typename T> T lminimum(const std::vector< T >& v) {return *std::min_element(v.begin(), v.end());}
template<typename T> T lmaximum(const std::vector< T >& v) {return *std::max_element(v.begin(), v.end());}
template<typename T> void lunique(std::vector< T >& v) {v.erase(std::unique(v.begin(), v.end()), v.end());}
template<typename T> void lsort(std::vector< T >& v) {std::sort(v.begin(), v.end());}
template<typename T> void lgreatersort(std::vector< T >& v) {std::sort(v.begin(), v.end(), std::greater<>());}
template<typename T> bool lnext_permutation(std::vector< T >& v) {return std::next_permutation(v.begin(), v.end());}

int main(int argc, char* argv[])
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  ll N, K, X, Y;
  std::cin >> N >> K >> X >> Y;

  ll ans = std::min(N, K) * X + std::max(0LL, (N - K)) * Y;
  print(ans);

  return 0;
}


Measured memory_bytes: 256
// Last Change: 11/07/2019 18:37:25.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

void solve(ll m, ll nMin, ll nMax) {
  vector<ll> P(m);
  for (auto &&e : P) {
    cin >> e;
  }

  ll gap = 0, res = nMin;
  for (int i = nMin - 1; i < nMax; ++i) {
    if (gap <= P[i] - P[i + 1]) {
      gap = P[i] - P[i + 1];
      res = i + 1;
    }
  }

  cout << res << endl;
}

int main() {
  ll m, nmin, nmax;
  while (cin >> m >> nmin >> nmax and !(m == 0 and nmin == 0 and nmax == 0)) {
    solve(m, nmin, nmax);
  }
}



Measured memory_bytes: 3084
#include <stdio.h>

int main(void)
{
    int N, M;
    int sum = 0;
    int result = 0;
    scanf("%d", &N);
    scanf("%d", &M);
    for(int i=0; i<M; i++){
        int data;
        scanf("%d", &data);
        sum = sum + data;
    }
    result = N - sum;
    if(result >= 0){
        printf("%d", result);
    }else{
        printf("-1");
    }
    
    return 0;
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<ll, ll>;

vector<P> prime_factor(ll n){
    vector<P> res;
    for(ll i = 2; i * i <= n; ++i){
        if(n % i != 0) continue;
        ll cnt = 0;
        while(n % i == 0){
            n /= i;
            cnt++;
        }
        res.push_back(P(i, cnt));
    }
    if(n != 1) res.push_back(P(n, 1));//nが素数の時
    return res;
}

int main(){
    ll n; cin >> n;
    vector<P> vec = prime_factor(n);
    ll ans = 0;
    for(auto p : vec){
        ll q = p.first;
        ll num = p.second;
        int tmp = 2 * num;
        tmp = sqrt(tmp) - 1;
        //cout << q << " " << num << endl;
        for(ll k = tmp; ; k++){
            if(k * (1 + k) <= 2 * num && 2 * num < (k+1) * (k+2)) {
                ans+=k;
                //cout << k << endl;
                break;
            }
        }
    }
    cout << ans << endl;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}


int main(void) {
	string s;
	cin >> s;
	if (s <= "2019/04/30") {
		cout << "Heisei" << endl;
	}else{
		cout << "TBD" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;
 
int main()
{
  int h,w,ans=0;
  cin>>h>>w;
  vector<string> field(h);
  for(auto&& e: field) 
  {
    cin>>e;
  }
  vector<vector<int>> left(h,vector<int>(w,1));
  vector<vector<int>> right(h,vector<int>(w,1));
  vector<vector<int>> up(h,vector<int>(w,1));
  vector<vector<int>> down(h,vector<int>(w,1));
  //left
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      if(field[i][j]=='#') left[i][j]=0;
      else if(j==0) left[i][j]=1;
      else left[i][j]=left[i][j-1]+1;
    }
  }
  //right
  for (int i = 0; i < h; ++i)
  {
    for (int j = w-1; j >= 0; --j)
    {
      if(field[i][j]=='#') right[i][j]=0;
      else if(j==w-1) right[i][j]=1;
      else right[i][j]=right[i][j+1]+1;
    }
  }
  //down
  for (int i = 0; i < w; ++i)
  {
    for (int j = 0; j < h; ++j)
    {
      if(field[j][i]=='#') down[j][i]=0;
      else if(j==0) down[j][i]=1;
      else down[j][i]=down[j-1][i]+1;
    }
  }
  //up
  for (int i = 0; i < w; ++i)
  {
    for (int j = h-1; j >= 0; --j)
    {
      if(field[j][i]=='#') up[j][i]=0;
      else if(j==h-1) up[j][i]=1;
      else up[j][i]=up[j+1][i]+1;
    }
  }

  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      int tmp=up[i][j]+down[i][j]+left[i][j]+right[i][j]-3;
      ans=(ans>tmp)? ans:tmp;
    }
  }
  cout<<ans<<endl;

}

Measured memory_bytes: 67200
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset>
#define mall (nxd*)mallxc(sizexf(nxd))
using namespace std;
typedef long long ll;
struct node{
	ll x,y,z;
}a[200005];
ll n;
ll pa[200005],le[200005];
bool cmp(node a1,node a2)
{
	if(a1.x==a2.x) return a1.y>a2.y;
	return a1.x>a2.x;
}
bool cmp1(node a1,node a2)
{
	return a1.z<a2.z;
}
ll find(ll x)
{
	if(x==pa[x]) return x;
	else return pa[x]=find(pa[x]);
}
void unite(ll x,ll y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(le[x]>le[y])
	{
		pa[y]=x;
		le[x]+=le[y];
	}
	else
	{
		pa[x]=y;
		le[y]+=le[x];
	}
}
int main(void)
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].z=i;
	sort(a+1,a+n+1,cmp);
	for(ll i=0;i<=n;i++) pa[i]=i,le[i]=1;
	map<ll,ll> mp;
	map<ll,ll>::iterator ite;
	mp[a[1].y]=1;
	for(ll i=2;i<=n;i++)
	{
		ite=mp.end();
		ite--;
//		printf("   %lld %lld\n",ite->first,a[i].y);
		if(ite->first<a[i].y)
		{
			mp[a[i].y]=1;
			continue;
		}
		ll x=ite->first;
		for(;ite!=mp.begin()&&ite->first>a[i].y;)
		{
			ll y=ite->first;
			ite--;
			mp.erase(y);
			unite(y,a[i].y);
		}
		if(ite==mp.begin()&&ite->first>a[i].y)
		{
			unite(ite->first,a[i].y);
			mp.clear();
			mp[x]=1;
		}
		else
		{
			mp[x]=1;		
		}
	}
	sort(a+1,a+n+1,cmp1);
	for(ll i=1;i<=n;i++)
	{
		printf("%lld\n",le[find(a[i].y)]);
	}
}

Measured memory_bytes: 11824
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())

    s = [0] * n
    t = [0] * n

    for i in range(n):
        s[i], t[i] = input().split()
        t[i] = int(t[i])

    x = input()

    idx = s.index(x)
    ans = 0

    for i in range(idx+1, n):
        ans += t[i]

    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, m;
  char a[50][50], b[50][50];
  cin >> n >> m;
  for(int x=0;x<n;x++) 
    for(int y=0;y<n;y++) 
      cin >> a[x][y];
  for(int x=0;x<m;x++) 
    for(int y=0;y<m;y++) 
      cin >> b[x][y];
  bool exit = false;
  for(int x=0;x<=n-m && !exit;x++){
    for(int y=0;y<=n-m && !exit;y++){
      bool f = true;
      for(int dx=0;dx<m && f;dx++){
        for(int dy=0;dy<m && f;dy++){
          if(b[dx][dy] != a[x+dx][y+dy]) f = false;
        }
      }
      if(f) exit = true;
    }
  }
  cout << (exit?"Yes":"No") << endl;
}

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

ll N;

ll dfs(string s){
    ll ret = 0;
    ll num = 0, dig = 1;
    for(ll i = s.size()-1; i >= 0; i--){
        num += dig * (s[i] - '0');
        dig *= 10;
    }
    if(N < num) return 0;
    bool san = false, go = false, nana = false;
    for(auto ss : s){
        if(ss == '3') san = true;
        if(ss == '5') go = true;
        if(ss == '7') nana = true;
    }
    if(san && go && nana) ret++;
    ret += dfs(s+"3");
    ret += dfs(s+"5");
    ret += dfs(s+"7");
    return ret;
}

int main(){
    cin >> N;
    cout << dfs("3") + dfs("5") + dfs("7") << endl;
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    int count = 0, ans = 0;
    for (int i = 1; i < n; i++)
    {
        if (h[i - 1] >= h[i])
            count++;
        else
        {
            ans = max(ans, count);
            count = 0;
        }
    }
    ans = max(ans, count);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
haiku = list(int(i) for i in input().split())
seven = 0
five = 0
for i in range(3):
    if int(haiku[i]) == 7:
        seven += 1
    elif int(haiku[i]) == 5:
        five += 1
if seven == 1 and five == 2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)
#define rep1(i, n) for(int i = 1; i <= (int) n; i++)
#define all(v) v.begin(),v.end()

int main() {
    ll x;
    cin >> x;
    ll a = 100;
    for (int i = 0; ; i++)
    {
        if (a >= x) {
            cout << i << endl;
            return 0;
        }
        a += a*0.01;
    }
    
    return 0;
}

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

int digitSum(int n) {
    int sum = 0;
    while(n>0){
        sum += n%10;
        n /= 10;
    }
    return sum;
}
int main() {
    int n; cin >> n;
    cout << (n%digitSum(n) == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

class LazySegmentTree{
public:
	int n = 1;
	vector<int> node[3], lazy;
	vector<bool> lazyF;
	void init(int N){
		while(n < N)n *= 2;
		rep(i,3)node[i].resize(2*n-1);
		lazy.resize(2*n-1);lazyF.resize(2*n-1, false);
	}
	void lazy_evaluate(int k, int l, int r){
		if(lazyF[k] == false)return;
		rep(i,3)node[i][k] = i==2 ? lazy[k]*(r-l) : lazy[k];
		if(k < n-1){
			rrep(i,2)lazy[2*k+i] = lazy[k];
			rrep(i,2)lazyF[2*k+i] = true;
		}
		lazyF[k] = false;
	}
	void update(int a, int b, int x, int k, int l, int r){
		lazy_evaluate(k, l, r);
		if(r <= a || b <= l)return;
		if(a <= l && r <= b){
			lazy[k] = x;
			lazyF[k] = true;
			lazy_evaluate(k, l, r);
			return;
		}
		update(a, b, x, k*2+1, l, (l+r)/2);
		update(a, b, x, k*2+2, (l+r)/2, r);
		node[0][k] = max(node[0][k*2+1], node[0][k*2+2]);
		node[1][k] = min(node[1][k*2+1], node[1][k*2+2]);
		node[2][k] = node[2][k*2+1]+node[2][k*2+2];
	}
	int calc(int a, int b, int k, int l, int r, int f){
		lazy_evaluate(k, l, r);
		if(r <= a || b <= l)return !f ? -INF : f==1 ? INF : 0;
		if(a <= l && r <= b)return node[f][k];
		int vl = calc(a, b, k*2+1, l, (l+r)/2, f);
		int vr = calc(a, b, k*2+2, (l+r)/2, r, f);
		return !f ? max(vl, vr) : f==1 ? min(vl, vr) : vl+vr;
	}
	void replace(int a, int b, int x){update(a, b, x, 0, 0, n);}
	int get_max(int a, int b){return calc(a, b, 0, 0, n, 0);}
	int get_min(int a, int b){return calc(a, b, 0, 0, n, 1);}
	int get_sum(int a, int b){return calc(a, b, 0, 0, n, 2);}
};

signed main(){
	int n, q, MAX = (1LL<<31)-1;
	scanf("%lld%lld", &n, &q);
	LazySegmentTree seg;
	seg.init(n+1);
	//rep(i,n)seg.replace(i, i+1, MAX);
	
	rrep(i,q){
		int c, s, t, x;
		scanf("%lld",&c);
		if(c == 0){
			scanf("%lld%lld%lld", &s, &t, &x);
			seg.replace(s, t+1, x);
		}else{
			scanf("%lld%lld", &s, &t);
			printf("%lld\n", seg.get_sum(s, t+1));
		}
	}
	return 0;
}








Measured memory_bytes: 11044
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]
Money = 2e6
for i in range(2 ** N):
    P = [0] * M
    m = 0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(len(P)):
                P[k] += CA[N - 1 - j][k + 1]
            m += CA[N - 1 - j][0]
    ok = True
    for k in range(M):
        if P[k] < X:
            ok = False
    if ok:
        Money = min(Money, m)
if Money == 2e6:
    print('-1')
else:
    print(Money)

Measured memory_bytes: 9240
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>

using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main() {
	string str;
	while(getline(cin, str)) {
		stack<double> s;
		stringstream ss;
		ss << str;
		while(ss >> str) {
			if(isdigit(str[0]) || str.length() > 1) {
				s.push(atoi(str.c_str()));
			} else {
				double a = s.top(); s.pop();
				double b = s.top(); s.pop();
				double c;
				if(str[0] == '+') c = a + b;
				else if(str[0] == '-') c = b - a;
				else if(str[0] == '*') c = a * b;
				else c = b / a;						
				s.push(c);
			}
		}
		printf("%.6lf\n", s.top());
	}
	return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
vector<string> split(string s, char p){vector<string>v;stringstream m(s);string b;while(getline(m,b,p))v.push_back(b);return v;}
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 (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;

int main(){
    ll a; cin >> a;
    cout << a+a*a+a*a*a << "\n";
}


Measured memory_bytes: 3656
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<int> z_algorithm(const string &s) {
    int n = s.size();
    vector<int> lcp(n);
    lcp[0] = n;
    int i = 1, j = 0;
    while (i < n) {
        while (i + j < n && s[j] == s[i + j]) j++;
        lcp[i] = j;
        if (j == 0) { i++; continue; }
        int k = 1;
        while (i + k < n && k + lcp[k] < j) lcp[i + k] = lcp[k], k++;
        i += k, j -= k;
    }
    return lcp;     // longest common prefix of s and s[i:n]
}

vector<vector<int>> divisors_table(int n) {     // 自分自身を含まない
    vector<vector<int>> divisors(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i + i; j <= n; j += i) divisors[j].emplace_back(i);;
    }
    return divisors;
}

int main() {
    string s; cin >> s;
    int n = s.length();
    if (s == string(n, s[0])) return !(cout << n << endl << 1 << endl);
    string s_r = s;
    reverse(begin(s_r), end(s_r));
    vector<int> lcp = z_algorithm(s), lcp_r = z_algorithm(s_r);
    auto ds = divisors_table(n);
    auto check = [&](int len) {
        for (int d: ds[len]) if (lcp[d] >= len - d) return false;
        len = n - len;
        for (int d: ds[len]) if (lcp_r[d] >= len - d) return false;
        return true;
    };
    if (check(n)) return !(cout << 1 << endl << 1 << endl);
    int cnt = 0;
    for (int i = 1; i < n; i++) cnt += check(i);
    cout << 2 << endl << cnt << endl;
    return 0;
}


Measured memory_bytes: 60824
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

int a[100000];

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

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	int low = 0, high = 100000 * 10000;

	while (true)
	{
		if (high <= low)
		{
			break;
		}
		int mid = (low + high) / 2;
		int need_trucks_num = 1;
		int temp_weight = 0;
		for (int i = 0; i < n; i++)
		{
			if (a[i] + temp_weight <= mid)
			{
				temp_weight += a[i];
			}
			else if (a[i] > mid)
			{
				need_trucks_num = k + 1;
				break;
			}
			else
			{
				need_trucks_num++;
				temp_weight = a[i];
				if (need_trucks_num > k)
				{
					break;
				}
			}
		}
		if (need_trucks_num > k)
		{
			low = mid + 1;
		}
		else
		{
			high = mid;
		}
		
	}

	printf("%d\n", low);

	return 0;
}


Measured memory_bytes: 3600
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];

  static bool dp[101010];
  dp[0] = false;

  for (int i = 0; i <= K; i++) {
    dp[i] = false;

    for (int k = 0; k < N; k++) {
      if (i - a[k] >= 0) {
        dp[i] |= !dp[i - a[k]];

      } else {
        break;
      }
    }
  }

  if (dp[K]) {
    cout << "First" << endl;
  } else {
    cout << "Second" << endl;
  }
  return 0;
}


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

int main(){
  int n,k,item,begin;
  double u,v,t,l,d[201],ans,remain,limit;
  while(cin >> n >> k >> t >> u >> v >> l){
    for(int i=0;i<n;i++) cin >> d[i];
    d[n] = l;

    ans = d[0] / u;
    limit = t * v * (k + 1);
    begin = remain = 0;
    for(int i=0;i<n;i++){
      remain = min(remain + t * v, limit);
      double dis = d[i+1] - d[i];
      if(dis > remain){
	ans += remain / v + (dis - remain) / u;
	remain = 0;
      } else{
	ans += dis / v;
	remain -= dis;
      }

    }


    printf("%.9f\n",ans);
  }
}

Measured memory_bytes: 1248
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

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

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

  int d, g;
  cin >> d >> g;
  int p[d], c[d];
  for(int i = 0; i < d; i++) cin >> p[i] >> c[i];

  g /= 100;
  for(int i = 0; i < d; i++){
    c[i] /= 100;
  }

  int dp[d + 1][200001];
  for(int i = 0; i <= d; i++){
    fill(dp[i], dp[i] + 200001, INF_INT);
  }

  dp[0][0] = 0;
  for(int i = 1; i <= d; i++){
    for(int j = 0; j <= 200000; j++){
      for(int k = 0; k < p[i - 1]; k++){
        if(j - (i * k) >= 0)
          dp[i][j] = min(dp[i][j],
              dp[i - 1][j - (i * k)] + k);
      }
      if(j - (i * p[i - 1] + c[i - 1]) >= 0)
        dp[i][j] = min(dp[i][j],
            dp[i - 1][j - (i * p[i - 1] + c[i - 1])] + p[i - 1]);
    }
  }

  int ans = INF_INT;
  for(int i = g; i <= 200000; i++){
    ans = min(ans, dp[d][i]);
  }

  cout << ans << endl;

  return 0;
}


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

template<typename T>
T power(T x, long long k, long long mod){
  T ret{1};
  while(k > 0){
    if(k&1) ret *= x, ret %= mod;
    x *= x, x %= mod;
    k /= 2;
  }
  return ret;
}

int main(){
  int N;
  string X;
  cin >> N >> X;
  int p = 0;
  for(int i = 0; i < N; ++i){
    p += (X[i] -'0');
  }
  
  auto f = [](int x){
             int ret = 0;
             while(x > 0){
               ++ret;
               x %= __builtin_popcount(x);
             }
             return ret;
           };

  int l = 0, m = 0, r = 0;
  for(int i = 0; i < N; ++i){

    m *= 2, r *= 2;
    int d = X[i] - '0';
    m += d, r += d;
    m %= p, r %= p+1;
    if(p > 1){
      l *= 2;
      l += d;
      l %= p-1;
    }
  }

  for(int i = 0; i < N; ++i){
    if(X[i] == '0'){
      int t = (r + power<long long>(2,N-i-1,p+1))%(p+1);
      cout << 1+f(t) << '\n';
    }else{
      if(p == 1){
        cout << 0 << '\n';
        continue;
      }
      int t = (l - power<long long>(2,N-i-1,p-1))%(p-1);
      t = (t+p-1)%(p-1);
      cout << 1+f(t) << endl;
    }
  }
}


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

using namespace std;

typedef long long ll;
#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define mem(a,i) memset(a,i,sizeof(a))

const double pi=acos(-1);
const int maxn=1e6+10;
const int mod=1e9+7;

int main()
{
    string s1,s2,s3;
    cin>>s1>>s2;
    int a,b;
    cin>>a>>b;
    cin>>s3;
    if(s3==s1)
        {if(a)
        a--;}
    else
       {if(b)
        b--;}
    cout<<a<<" "<<b;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

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

    int ans = 0;
    repi(i, 1, N + 1) {
        string S = to_string(i);
        if(S.size() % 2 == 1) ans++;
    } 

    cout << ans << endl;
}

Measured memory_bytes: 256
while True:
    n = int(input())
    if n == 0:
        break

    a_point = 0
    b_point = 0
    for _ in range(n):
        a, b = [int(x) for x in input().split()]

        if a > b:
            a_point += a + b
        elif a < b:
            b_point += a + b
        else:
            a_point += a
            b_point += b
    print(a_point, b_point)

Measured memory_bytes: 7732
//int main(){for(int i=1;i<1e2;i++)std::cout<<(i%3?(i%5?std::to_string(i):"Buzz"):(i%15?"Fizz":"FizzBuzz"))<<std::endl;}
#include<bits/stdc++.h>

using namespace std;
using ll = long long;


int main()
{
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(a * n, b) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

int main() {
  ll N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  rep(i, N) {
    if (B >= A+i*C-(N-i-1)*D && B <= A+i*D-(N-i-1)*C) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
  return 0;
}

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

using namespace std;
#define INF 1e15
#define MAX_V 100000

typedef struct{
    int to;
    long cost;
} edge; // 辺を定義

typedef struct{
    long dist; //　計算された距離
    int v; // ノードのインデックス
} vtx;

bool operator< (const vtx a, const vtx b){
    return a.dist > b.dist;  // ascend　これで小さい順に　vtxが出てくる
}
bool operator> (const vtx a, const vtx b){
    return a.dist < b.dist;  // ascend　これで小さい順に　vtxが出てくる
}

long distance(int s, int g, vector<edge> * G, int N){  // 結局は隣接リストに行先のその辺のコストを渡せば十分である。
    long d[N];
    fill(d, d + N, INF);

    priority_queue< vtx > que;
    d[s] = 0;
    que.push(vtx{d[s], s});
    
    while(!que.empty()){
        vtx now = que.top(); que.pop();
        if(now.dist > d[now.v]) continue;
        for(edge e : G[now.v]){
            if(d[e.to] > d[now.v] + e.cost){
                d[e.to] = d[now.v] + e.cost;
                que.push(vtx{d[e.to], e.to});
            }         
        }
    }
    if(d[g] == INF) return -1;
    else return d[g];
}

int main(){
    int N, M;
    cin >> N >> M;
    int l, r;
    long c;
    vector<edge> G[N];
    for(int i=0; i<M; i++){
        cin >> l >> r >> c;
        l--; r--;
        G[l].emplace_back(edge{r, c});
        G[r].emplace_back(edge{l, c});
    }
    for(int i=0; i<N-1; i++) G[i+1].emplace_back(edge{i, 0});
    cout << distance(0, N-1, G, N) << endl;
    return 0;
}

Measured memory_bytes: 12536
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define maxn 310
using namespace std;
long long a[maxn][maxn],n,b[maxn][maxn],ans;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		scanf("%lld",&a[i][j]),b[i][j]=a[i][j],ans+=a[i][j];
		ans/=2;
	for(int k=1;k<=n;++k)
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	b[i][j]=min(b[i][j],b[i][k]+b[k][j]);
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	if(a[i][j]!=b[i][j]) {
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n-1;++i)
	for(int j=i+1;j<=n;++j)
	{
		for(int k=1;k<=n;++k)
		if(a[i][j]==a[i][k]+a[k][j]&&k!=i&&k!=j) 
		{
		ans-=a[i][j];
		break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
using System;

namespace Aizu {
    public class OnlineJudge {
        static void Main() {
            var count = 0;
            var last = 'A';
            foreach (var c in Console.ReadLine()) {
                if (c <= last) {
                    ++count;
                }
                last = c;
            }

            Console.WriteLine(count);
        }
    }
}



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

using P = pair <int, int>;
void hoge(vector <vector <P>> & origin, vector <P> vp);

int main() {
    int n;
    while (cin >> n, n) {
        vector <vector <P>> origin;

        int m;
        cin >> m;
        vector <P> tmp;
        rep (i, m) {
            int x, y;
            cin >> x >> y;
            tmp.emplace_back(x, y);
        }
        hoge(origin, tmp);
        reverse(tmp.begin(), tmp.end());
        hoge(origin, tmp);

        rep (i, n) {
            cin >> m;
            int x0, y0;
            vector <P> comparison;
            rep (j, m) {
                int x, y;
                cin >> x >> y;
                if (j == 0) {
                    x0 = x, y0 = y;
                    x = y = 0;
                }
                else {
                    x -= x0, y -= y0;
                }
                comparison.emplace_back(x, y);
            }

            if (comparison.size() != origin[0].size()) continue;
            rep (j, origin.size()) {
                bool flag = true;
                rep (k, origin[j].size()) flag &= (origin[j][k] == comparison[k]);
                if (flag) {
                    cout << i + 1 << endl;
                    break;
                }
            }
        }
        cout << "+++++" << endl;
    }
    return 0;
}

void hoge(vector <vector <P>> & origin, vector <P> vp) {
    int x0 = vp.front().first, y0 = vp.front().second;
    vector <P> tmp = vp;
    vector <P> va = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
    rep (i, 4) {
        vp = tmp;
        rep (j, vp.size()) {
            vp[j].first  -= x0;
            vp[j].second -= y0;

            vp[j].first  *= va[i].first;
            vp[j].second *= va[i].second;
            if (i > 1) swap(vp[j].first, vp[j].second);
        }
        origin.push_back(vp);
    }
}


Measured memory_bytes: 3100
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();

            int count = 0;
            for (int n = 1; n <= N; n++) {
                int mask = 0;
                if (n / 1 > 0) {
                    mask |= (1 << 0);
                }
                if (n / 10 > 0) {
                    mask |= (1 << 1);
                }
                if (n / 100 > 0) {
                    mask |= (1 << 2);
                }
                if (n / 1000 > 0) {
                    mask |= (1 << 3);
                }
                if (n / 10000 > 0) {
                    mask |= (1 << 4);
                }
                if (n / 100000 > 0) {
                    mask |= (1 << 5);
                }

                if ((32 - Integer.numberOfLeadingZeros(mask)) % 2 == 1) {
                    count++;
                }
            }

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


Measured memory_bytes: 27220
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		double N = scanner.nextInt();
		double x = 0;
		x = Math.ceil(N / 2);
		double p = x / N;
//		System.out.println(x);
//		System.out.println(N);
		System.out.println(p);
	}
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int main(){
  int h,n;
  cin>>h>>n;
  vector<int> a(n),b(n);
  for(int i=0;i<n;i++){
	cin>>a[i]>>b[i];
  }
  vector<int> dp(h+1,INF);
  dp[0]=0;
  for(int i=0;i<h;i++){
	for(int j=0;j<n;j++){
      for(int k=1;k==1||a[j]*k<h*2;k*=2){
        dp[min(h,i+a[j]*k)]=min(dp[min(h,i+a[j]*k)],dp[i]+b[j]*k);
      }
    }
  }
  cout<<dp[h]<<endl;
  return 0;
}

Measured memory_bytes: 256
def main():
    limit = int(input())
    result = False
    for i in range(26):
        for j in range(15):
            if 4 * i + 7 * j == limit:
                result = True
                break
    if result:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second
int INF=1e9;
string s;
P init=P(INF,-INF);
vector<vector<P> >dp(200,vector<P>(200,init));

P dfs(int l,int r){
	if(l==r)return P(s[l]-'0',s[l]-'0');
	if(dp[l][r]!=init)return dp[l][r];
	P res=init;
	if(s[l]=='('&&r-l>2) res=dfs(l+1,r);
	if(s[r]==')'&&r-l>2) res=dfs(l,r-1);
	for(int i=l+1;i<r;i++){
		if(!(s[i]=='-'||s[i]=='+'))continue;
		P a=dfs(l,i-1);
		P b=dfs(i+1,r);
		if(s[i]=='-'){
			res.F=min(res.F,a.F-b.S);
			res.S=max(res.S,a.S-b.F);
		}
		if(s[i]=='+'){
			res.F=min(res.F,a.F+b.F);
			res.S=max(res.S,a.S+b.S);
		}
	}
	return dp[l][r]=res;
}

main(){
	cin>>s;
	cout<<dfs(0,s.size()-1).S<<endl;
}


Measured memory_bytes: 3352
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort()

dp = [0]*(T)
ans = 0
for a,b in AB:
    ans = max(ans,dp[-1]+b)
    for i in range(T-1,-1,-1):
        if i-a >= 0:
            dp[i] = max(dp[i],dp[i-a]+b)
print(ans)


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

using namespace std;

typedef long long int ll;

const ll mod = 1e9 + 7;
const ll MAXN = 1e5 + 5;

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

  string s;
  cin >> s;
  ll n = s.length();
  vector < ll > a(n);
  ll l, r;
  for(int i = 0; i < n; i++){
    if(i + 1 < n && s[i] == 'R' && s[i + 1] == 'L'){
      l = r = 0;
      int j = i;
      while(j >= 0 && s[j] == 'R'){
        if(j % 2 == i % 2) l++;
        else r++;
        j--;
      }
      j = i + 1;
      while(j < n && s[j] == 'L'){
        if(j % 2 == (i + 1) % 2) r++;
        else l++;
        j++;
      }
      a[i] = l;
      a[i + 1] = r;
      i = j - 1;
    }
  }

  for(int i = 0 ;i < n; i++) cout << a[i] << " ";
  cout << endl;
}


Measured memory_bytes: 1488
//
//  main.cpp
//
 
#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
 
template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

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

struct Mod {
	static ll gcd(ll x, ll y, ll* out_cx, ll* out_cy) {
		if (x < 0) {
			ll d = gcd(-x, y, out_cx, out_cy);
			if (out_cx) {
				*out_cx *= -1;
			}
			return d;
		}
		if (y < 0) {
			ll d = gcd(x, -y, out_cx, out_cy);
			if (out_cy) {
				*out_cy *= -1;
			}
			return d;
		}
		if (x > y) {
			return gcd(y, x, out_cy, out_cx);
		}
		if (x == 0) {
			if (out_cx && out_cy) {
				*out_cx = 0;
				*out_cy = 1;
			}
			return y;
		}
		ll q = y / x;
		ll r = y % x;
		ll d = gcd(r, x, out_cy, out_cx);
		if (out_cx) {
			*out_cx -= q * *out_cy;
		}
		return d;
	}
};

int main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> As(N);
	rep(i,0,N) {
		cin >> As[i];
		if (As[i] % 2 != 0) {
			cout << 0 << endl;
			return 0;
		}
		As[i] /= 2;
	}
	ll lcm = As[0];
	rep(i,1,N) {
		ll gcd = Mod::gcd(lcm, As[i], nullptr, nullptr);
		lcm = (lcm / gcd) * As[i];
		if (lcm > M) {
			cout << 0 << endl;
			return 0;
		}
	}
	vector<ll> divs(N);
	rep(i,0,N) {
		divs[i] = lcm / As[i];
		if (divs[i] % 2 == 0) {
			cout << 0 << endl;
			return 0;			
		}
	}
	cout << M / lcm - M / (2 * lcm) << endl;
}

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

// #define multitest 1
#ifdef WIN32
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
#define pc(...) PC(#__VA_ARGS__, __VA_ARGS__);
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.first << ", " << p.second << ']';
	return out;
}
template <typename Arg>
void PC(const char *name, Arg &&arg)
{
	std::cerr << name << " { ";
	for (const auto &v : arg)
		cerr << v << ' ';
	cerr << " }\n";
}
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
{
	const char *comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
#else
#define db(...)
#define pc(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
const long long mod = 1000000007;
auto TimeStart = chrono::steady_clock::now();

const int nax = 2e5 + 10;

void solve()
{
	int n;
	cin >> n;
	int Even = n - n / 2;
	cout << fixed << setprecision(9) << (long double)Even / n;
}

int main()
{
#ifndef WIN32
	ios_base::sync_with_stdio(0);
	cin.tie(0);
#endif
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
	while (t--)
		solve();
#ifdef WIN32
	cerr << "\n\nTime elapsed: " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n";
	flush(cout);
#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define fore(x, a) for(auto &x : a)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define inf 2001001001
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
#define F first
#define S second
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
template<class T>using vv = vector<T>;
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; }
template<class T>void show(const vector<T> &a) { for (int i = 0; i < (int)a.size(); ++i) cout << a[i] << (i != (int)a.size()-1 ? " " : "\n"); }
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
int dy[]={0, 1, -1, 0};
int dx[]={1, 0, 0, -1};

int h, w, k;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> h >> w >> k;
    k--;
    ll dp[h + 1][w];
    fill(dp[0], dp[h+1], 0);
    dp[0][0] = 1;
    rep(i, 0, h) {
      rep(bit, 0, (1 << (w - 1))) {
        bool flag = true;
        rep(j, 0, w-2) 
          if ((bit >> j) % 4 == 3) flag = false; 
        if (flag) {
          int to[w];
          iota(to, to + w, 0);
          rep(j, 0, w-1) {
            if ((bit >> j) & 1) swap(to[j], to[j+1]);
          }
          rep(j, 0, w) {
            dp[i+1][to[j]] += dp[i][j];
            dp[i+1][to[j]] %= MOD;
          }
        }
      }
    }
    cout << dp[h][k] << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <utility>
#include <deque>
#include <set>
#include <cmath>
#include <ctime>

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time_init() clock_t clock_start = clock()
#define time_now()  debug("Time since start: %.3f seconds.\n", (double)(clock() - clock_start) / CLOCKS_PER_SEC)

using namespace std;

int main(){

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

    int n, k;
    cin >> n >> k;

    int x;
    vector<long long> a;
    for(int i = 0; i < n; ++i){
        cin >> x;
        a.push_back((x + k - 1) % k);
    }

    // for(int i = 0; i < n; ++i){
    //     cout << a[i] << " ";
    // }
    // cout << "\n";
    
    map<long long, long long> counts;
    vector<long long> sum(n);
    int i = 0;
    long long ans = 0;
    for(auto num: a){

        // for(auto p: counts){
        //     cout << p.first << ":" << p.second << "  ";
        // }
        // cout << "ans is " << ans << "\n";

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

        sum[i] %= k;
        
        ans += counts[sum[i]];
        counts[sum[i]] += 1;

        if(sum[i] == 0 and i < k - 1){
            ans += 1;
        }

        if(i + 1 >= k){
            counts[sum[i + 1 - k]] -= 1;
        }
      
        i += 1;
    }
    
    cout << ans << "\n";
}


Measured memory_bytes: 15856