akhauriyash/Code-Regression huggingface dataset:
/* AtCoder My Practice
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>
#include <stdlib.h>

#define N_MAX (200001)

typedef struct _range {
    int upper, lower;
    struct _range *ubound, *lbound;
} Range;

Range *newRange(int lower, int upper) {
    Range *range = (Range*)malloc(sizeof(Range));
    range->lower = lower;
    range->upper = upper;
    return range;
}

int idx[N_MAX];
long long sum;
Range range;

void calc(int value, int index) {
    Range *tmp = &range;
    long long len1, len2, len3;
    for (;;) {
        if (tmp->lower <= index && index <= tmp->upper) {
            len1 = (long long)(tmp->upper - tmp->lower + 1);
            len2 = (long long)(tmp->upper - index);
            len3 = (long long)(index - tmp->lower);
            sum += (len1 * (len1 + 1LL) - (len2 * (len2 + 1LL)) - (len3 * (len3 + 1))) / 2LL * (long long)value;
            if (tmp->lower == index) {
                tmp->lower++;
            } else if (tmp->upper == index) {
                tmp->upper--;
            } else {
                tmp->lbound = newRange(tmp->lower, index - 1);
                tmp->ubound = newRange(index + 1, tmp->upper);
                tmp->lower = tmp->upper = index;
            }
            break;
        } else if (index < tmp->lower) {
            tmp = tmp->lbound;
        } else {
            tmp = tmp->ubound;
        }
    }
}

char buf[N_MAX * 10];
char *p = buf;

int getInt(void) {
    int v = 0;
    while (*p < '0' || '9' < *p) p++;
    while ('0' <= *p && *p <= '9') {
        v = v * 10 + (int)(*p - '0');
        p++;
    }
    return v;
}

int main(void){
    int i, n;
    int a;
    
    a = fread(buf, sizeof(char), sizeof(buf), stdin);
    
    n = getInt();

    for (i = 0; i < n; i++) {
        a = getInt();
        idx[a] = i;
    }
    
    range.upper = n - 1;
    
    for (i = 1; i <= n; i++) {
        calc(i, idx[i]);
    }
    
    printf("%lld\n", sum);

    return 0;
}


Measured memory_bytes: 6400
import copy
D = int(input())
c = list(map(int, input().split()))
s = []
for _ in range(D):
  s.append(list(map(int, input().split())))

t = [0] * 26

x = 0 # 満足度
for i in range(D): # i+1日目
  l = []
  for j in range(26): # すべてのコンテストに対して満足度を計算し、maxを求める
    y = x
    u = copy.deepcopy(t)
    u[j] = i+1
    y += s[i][j]
    for k in range(26): # シグマの中身
      y -= c[k] * ((i+1) - u[k])
    l.append(y)
  x = max(l)
  v = l.index(x)
  t[v] = i+1
  print(v+1)

Measured memory_bytes: 9368
#include <bits/stdc++.h>
using namespace std;
bool IsPrime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

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

  int n;
  cin >> n;
  for (int i = 0; ; i++) {
    if (IsPrime(n+i)) {
      cout << n+i << '\n';
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>//coded by Nurstan ^_^

#define ll long long
#define pb push_back
#define mp make_pair

#define all(x) x.begin(), x.end()

#define F first
#define S second

// fixed << setprecision
// next_permutation(a, a + n)
// set <int> :: iterator it = x.begin(); it != x.end(); it ++

using namespace std;

const ll INF = int(1e9) + 123;
const int UNF = int(1e5) * 2;

inline void boost(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

int main(){
	boost();
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, a, b;
	cin >> n >> a >> b;
	if((a + b) % 2 == 0) {
		cout << "Alice";
		return 0;
	}
	else {
		cout << "Borys";
		return 0;
	}
	exit(0); 
}


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

int n;
long long a[51];

long long solve() {
	long long k = 0;
	for(int i = 0; i < n; ++i) {
		k += a[i] / n;
		a[i] -= (a[i] / n) * (n + 1);
	}
	for(int i = 0; i < n; ++i)
		a[i] += k;
	return k;
}

bool allc() {
	for(int i = 0; i < n; ++i)
	if(a[i] >= n)
		return false;
	return true;
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%lld", a + i);
	long long ans = 0;
	while(!allc())
		ans += solve();
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

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

    vector<vector<int>> x(n, vector<int>(d));
    REP(i, n)
        REP(j, d){
            cin >> x[i][j];
        }

    int cnt = 0;
    REP(i, n){
        FOR(j, i+1, n){
            int dist = 0;
            REP(k, d)
                dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);

            bool ok = false;
            for(int k=1;k*k<=dist;k++)
                if(k * k == dist)
                    ok = true;

            if(ok)
                cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <bitset>
using namespace std;
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(); }
template<class T> inline T sqr(T x) { return x*x; }
typedef pair<int, int> P;
typedef long long ll;
typedef unsigned long long ull;

#define For(i,a,b)	for(int (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define rall(a)		(a).rbegin(), (a).rend()
#define sz(a)		(sizeof(a))
#define Fill(a,v)	fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)
#define fi first
#define se second
bool cheak(int x, int y, int xMax, int yMax){ return x >= 0 && y >= 0 && xMax > x && yMax > y; }
const int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
const int mod = 1000000007;
const int INF = 1e9;

int main()
{
	int n,//????????°
		m,//???????????????????????§?????¶?????????
		l,//??????????¨??????????????????°
		k,//?????¨???????????¶???????????°
		g,//??´??????
		s;//????????????


	while (cin >> n >> m >> l >> k >> g >> s && n){

		const int M = 101;

		int d[M][M];
		bool u[M]; clr(u);
		u[s] = 1; u[g] = 1;
		rep(i, l){
			int t;
			cin >> t;
			u[t] = 1;
		}
		Fill(d, INF);
		rep(i, n)d[i][i] = 0;
		rep(i, k){
			int x, y, t;
			cin >> x >> y >> t;
			d[x][y] = d[y][x] = t;
		}

		rep(k, n)rep(i, n)rep(j, n)d[i][j] = min(d[i][k] + d[k][j], d[i][j]);

		bool f[M]; clr(f);
		int c[M]; Fill(c, INF);
		queue<int> q;
		q.push(s);
		c[s] = 0;

		while (q.size()){
			int nx = q.front(); q.pop();

			rep(i, n)if (u[i] && !f[i]){
				if (d[nx][i] <= m && c[nx] + d[nx][i] < c[i]){
					c[i] = c[nx] + d[nx][i];
					q.push(i);
				}
			}

		}
		if (c[g] == INF)cout << "Help!" << endl;
		else{
			if (c[g] <= m)cout << c[g] << endl;
			else cout << c[g]*2 - m << endl;
		}

	}



	return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  for (int i = 0; i < N; i++)
    cin >> w[i] >> v[i];
  map<int, int> dp;
  dp[0] = 0;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    auto tmp = dp;
    for (auto it : tmp) {
      cnt++;
      if (it.first + w[i] <= W)
        dp[it.first + w[i]] = max(dp[it.first + w[i]], it.second + v[i]);
    }
  }
  int res = 0;
  for (auto it : dp)
    res = max(res, it.second);
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>

int search(int A[],int n,int key){
  int i=0;
  A[n] = key;
  while(A[i] != key)i++;
  return i != n;
}

int main(){
  int i,n,A[10000+1],q,key,sum = 0;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(search(A,n,key)) sum++;
  }
  printf("%d\n",sum);
  return 0;
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define st first
#define nd second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
template <class T> T read(T &a) {
    a=0;char x=getchar();bool f=0;
    for(;x<'0'||x>'9';x=getchar())f|=x=='-';
	for(;x>='0'&&x<='9';x=getchar())a=(a<<3)+(a<<1)+x-'0';
    if(f)a=-a;
    return a;
}
using namespace std;

const int N = 1e5 + 5;

int d[N];

vector<int> ans;

int main() {
	int n, m;
	read(n), read(m);
	int cnt = 0;
	for (int i = 1; i <= m; ++i) {
		read(d[i]);
	}
	for (int i = 1; i <= m; ++i) {
		cnt += (d[i] & 1);
	}
	if (cnt > 2) return puts("Impossible"), 0;
	cnt = 0;
	for (int i = 1; i <= m; ++i) {
		if ((d[i] & 1) && cnt == 0) {
			swap(d[i], d[1]);
			cnt = 1;
		} else 
		if ((d[i] & 1) && cnt == 1) {
			swap(d[i], d[m]);
			break;
		}
	}
	for (int i = 1; i <= m; ++i) {
		printf("%d ", d[i]);
	}
	puts("");
	for (int i = 1; i <= m; ++i) {
		if (d[i] & 1) {
			int range = d[i] >> 1;
			for (int j = 1; j <= range; ++j) {
				ans.pb(2);
			}
			if (i == 1) {
				if (m == 1) {
					ans.pb(1);
				} else ans.pb(2);
			}
		} else {
			if (m == 1) {
				ans.pb(2);
				if (d[i] > 2) {
					ans.pb(d[i] - 2);
				}
			} else 
			if (i == 1) {
				ans.pb(1);
				ans.pb(d[i]);
			} else
			if (i == m) {
				ans.pb(1);
				if (d[i] > 2) {
					ans.pb(d[i] - 2);
				}
			} else {
				ans.pb(d[i]);
			}
		}
	}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); ++i) {
		printf("%d ", ans[i]);
	}
    return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i = 0;i < n;i++)
#define rep1(i,n) for(int i = 1;i < n;i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

int main(){

    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    ll ans = 0;
    bool flag = true;
    int tmpi,tmpj;

    rep(k,n){
        rep(i,n){
            rep(j,n){
                if(j - k <0) tmpj = j - k + n;
                else tmpj = j - k;
                if(i - k < 0) tmpi = i - k + n;
                else tmpi = i - k;
                if(s[i][tmpj] != s[j][tmpi]){
                    flag = false;
                    break;
                }
                if(!flag){
                    break;
                }
            }
        }
        if(flag){
            ans++;
        }
        flag = true;
    }
    cout << n * ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;
#define int ll

ll n, k;
ll a[5000];
ll ans = 0;

signed main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int op = 0; op <= k; op++)
    {
        for (int take = 0; take <= min(op, n); take++)
        {
            for (int left = 0; left <= take; left++)
            {
                vector<int> v;
                for (int i = 0; i < left; i++)
                    v.push_back(a[i]);
                int other = take - left;
                for (int i = n - 1; i >= n - other; i--)
                    v.push_back(a[i]);
                sort(v.begin(), v.end());
                int out = k - take;
                int res = 0;
                for (int i = 0; i < v.size(); i++)
                {
                    if (v[i] < 0 && out > 0)
                    {
                        out--;
                    }
                    else
                    {
                        res += v[i];
                    }
                }
                ans = max(ans, res);
            }
        }
    }
    cout << ans;
}


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

typedef long long ll;

int main()
{
    ll n, w;
    cin >> n >> w;
    vector<ll> dp(w+1, 0);
    for(int i = 0; i < n; i++)
    {
        ll wht, val; cin >> wht >> val;
        for(ll j = w - wht; j >= 0; j--)
        {
            dp[j+wht] = max(dp[j]+val, dp[j+wht]);
        }
    }
    cout << dp[w] << endl;

    return 0;
}



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

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

  int N; cin >> N;
  vector<ll> A(N, 0), B(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }

  ll ans = 0;
  for (int i = N - 1; i >= 0; i--) {
    A[i] += ans;
    if (A[i] % B[i]) ans += (B[i] - (A[i] % B[i]));
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
  int n;
  cin >> n;
  if(n == 1) cout << "Hello World" << endl;
  else{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll a[100005];
ll k;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]%2==1){
            k++;
        }
    }
    if(k%2==0){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    
}


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

int main(void) {

  char s[500001];
  scanf("%s", s);
  long length = strlen(s);
  long a[length+1];
  for (long i = 0; i < length+1; i++) {
    a[i] = -1;
  }
  if (s[0] == '<') {
    a[0] = 0;
  }
  for (long i = 1; i < length; i++) {
    if (s[i-1] == '>' && s[i] == '<') {
      a[i] = 0;
    }
    if (s[i-1] == '<' && s[i] == '<') {
      a[i] = a[i-1]+1;
    }
  }
  if (s[length-1] == '<') {
    a[length] = a[length-1]+1;
  } else {
    a[length] = 0;
  }
  for (long i = length-1; i >= 0; i--) {
    if (a[i] == -1) {
      a[i] = a[i+1]+1;
      if (a[i] <= a[i-1] && i != 0) {
        a[i] = a[i-1]+1;
      }
    }
  }
  long sum = 0;
  for (long i = 0; i < length+1; i++) {
    sum += a[i];
  }
  printf("%ld\n", sum);

  return 0;
}

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

snuke = [0 for i in range(N)]
for i in range(K):
    d = int(input())
    okashi = list(map(int, input().split()))
    for j in range(d):
        snuke[okashi[j]-1] += 1
        
count = 0
for i in range(N):
    if snuke[i] == 0:
        count += 1
        
print(count)

Measured memory_bytes: 9200
//==========================================
// ABC129b
//
// 2019/08/26
//==========================================

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

int main(int argc, char* argv[])
{
  int n;
  cin >> n;
  vector<int> w(n);
  for(int i=0; i<n; i++) cin >> w[i];

  int sa;
  for(int i=0; i<n-1; i++)
  {
    int s1=0;
    int s2=0;

    for(int j=0; j<i+1; j++) s1 += w[j];
    for(int j=i+1; j<n; j++) s2 += w[j];

    if(i==0) sa = s2-s1;
    else if(abs(sa) > abs(s2-s1)) sa = s2-s1;
//    cout << "s1 : " << s1 << ", s2 : " << s2 <<endl;
  }
  cout << abs(sa) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
	string s="ACL",T="";
	int K;
  	cin>>K;
  	for(int i=0;i<K;i++){
      T +=s;
    }
  	cout<<T<<endl;
}

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

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

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

int main() {
  i64 K, Q;
  cin >> K >> Q;
  vector<i64> D(K);
  rep(i,0,K) {
    cin >> D[i];
  }
  rep(q,0,Q) {
    i64 n, x, m;
    cin >> n >> x >> m;
    i64 now = 0;
    i64 sum = 0;
    i64 ans = 0;
    rep(i,0,K) {
      i64 next = now + D[i];
      i64 diff = (next - now) % m;

      if(n % K == 0) {
        if(i != K - 1) {
          sum += diff * (n / K);
        }
        else {
          sum += diff * (n / K - 1);
        }
      }
      else if(i + 1 < n % K) {
        sum += diff * (n / K + 1);
      }
      else {
        sum += diff * (n / K);
      }
      if(diff == 0) {
        if(n % K == 0) {
          if(i != K - 1) {
            ans += 1 * (n / K);
          }
          else {
            ans += 1 * (n / K - 1);
          }
        }
        else if(i + 1 < n % K) {
          ans += 1 * (n / K + 1);
        }
        else {
          ans += 1 * (n / K);
        }
      }
      now = next;
    }
    sum += x % m;
    cout << n - ((sum / m) + ans) - 1 << endl;
  }
}


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

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

string replaceAll(string s, string f, string t) {
	string::size_type pos = s.find(f);
	while (pos != string::npos) {
		s.replace(pos, f.size(), t);
		pos = s.find(f, pos + t.size());
	}
	return s;
}

signed main() {
	string P; cin >> P;
	reverse(P.begin(), P.end());
	vector<int> ans;
	rep(i, 0, 10) {
		string tmp = replaceAll(P, "?", to_string(i));
		int P0 = tmp[0] - '0';
		int a = 0;
		rep(j, 1, tmp.size()) {
			if (j <= 6) {
				a += (tmp[j] - '0') * (j + 1);
			}
			else {
				a += (tmp[j] - '0') * (j - 5);
			}
		}
		a %= 11;
		if (a <= 1)a = 0;
		else a = 11 - a;
		if (P0 == a) ans.emplace_back(i);
	}
	if (ans.size() > 1)cout << "MULTIPLE" << endl;
	else cout << ans[0] << endl;
	return 0;
}

Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define emp emplace
 
using namespace std;
using ll = long long int;
using ii = pair<int, int>;
 
const int MOD = 1000 * 1000 * 1000 + 7;
const int N = 2*100000;
 
ll tree[2*N+N];

void build(int index, int l, int r){
    if(l == r){
        tree[index] = 0;
    }
    else{
        int mid = (l+r)/2;

        build(2*index+1, l, mid);

        build(2*index+2, mid+1, r);

        tree[index] = 0;
    }
}

void update(int node, int l, int r, int index, ll val){
    if(l>index || r<index)
        return;

    if(l==r)
        tree[node] = val;   
    else{
        int mid = (l+r)/2;
        update(2*node+1, l, mid, index, val);
        update(2*node+2, mid+1, r, index, val);

        tree[node] = max(tree[2*node+1], tree[2*node+2]);
    }
}

ll query(int index, int start, int end, int l, int r){
    if(start>r || end<l)
        return 0;

    if(start >=l && end <= r)
        return tree[index];
    else
    {
        int mid = (start+end)/2;
        return max(query(2*index+1,start,mid,l,r), query(2*index+2,mid+1,end,l,r));
    }
}


int main()
{

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

    for (int i = n-1; i >= 0; --i)
    {
        ll mx =query(0,0,n-1,height[i],n-1) + beauty[i];
        update(0,0,n-1,height[i]-1,mx);
    }

    cout<<query(0,0,n-1,0,n-1);
    return 0;
} 



Measured memory_bytes: 6656
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;


struct Mint {
	static const ll mod = (ll)(1e9 + 7);	
	ll val;

	Mint() { val = 0; }
	Mint(ll a) {
		val = a;
		verify_value();
	}

	void verify_value() {
		if (val >= mod) val %= mod;
		if (val < 0) val %= mod, val += mod;
	}

	Mint pow(ll p) const {
		Mint cur = Mint(val), ret = 1;
		while (p > 0) {
			if (p & 1) ret *= cur;
			cur *= cur;
			p >>= 1LL;
		}
		return ret;
	}
	Mint inv() const {
		if (val == 0) cerr << "CAUTION: inv() is called with 0." << endl;
		return pow(mod - 2); 
	}

	Mint operator+() const { return *this; }
	Mint operator-() const { return Mint(mod - val); }

	Mint operator+=(const Mint &a) {
		val += a.val;
		if (val >= mod) val -= mod;
		return Mint(val);
	}
	Mint operator*=(const Mint &a) {
		val *= a.val;
		if (val >= mod) val %= mod;
		return Mint(val);
	}
	Mint operator-=(const Mint &a) { return *this += -a; }
	Mint operator/=(const Mint &a) { return *this *= a.inv(); }

	Mint operator++() { return *this += Mint(1); }
	Mint operator--() { return *this -= Mint(1); }
	Mint operator++(int) {
		Mint ret = *this;
		++(*this);
		return ret;
	}
	Mint operator--(int) {
		Mint ret = *this;
		--(*this);
		return ret;
	}
};

Mint operator+(const Mint &a, const Mint &b) {
	ll ret = a.val + b.val;
	if (ret >= Mint::mod) ret -= Mint::mod;
	return Mint(ret);
}
Mint operator*(const Mint &a, const Mint &b) {
	ll ret = a.val * b.val;
	if (ret >= Mint::mod) ret %= Mint::mod;
	return Mint(ret);
}
Mint operator-(const Mint &a, const Mint &b) { return a + (-b); }
Mint operator/(const Mint &a, const Mint &b) { return a * b.inv(); }

ostream &operator<<(ostream &out, const Mint &a) { return out << a.val; }
istream &operator>>(istream &in, Mint &a) {
	in >> a.val;
	a.verify_value();
	return in;
}

string s[1003];
Mint dp[1005][1005];

int main() {
	int H, W; cin >> H >> W;
	for (int i = 0; i < H; i++) cin >> s[i], s[i] += "#";
	s[H] = string(W + 1, '#');
	dp[0][0] = 1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i + 1][j] != '#') dp[i + 1][j] = dp[i + 1][j] + dp[i][j];
			if (s[i][j + 1] != '#') dp[i][j + 1] = dp[i][j + 1] + dp[i][j];
		}
	}
	cout << dp[H - 1][W - 1] << endl;
	return 0;
}

Measured memory_bytes: 9216
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
#include <iomanip>
#include <set>
#include <functional>

#define MOD (1000000007)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> tup;
const int MAX = 3000000;

long long fac[MAX], finv[MAX], inv[MAX];


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


// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

map<ll,ll> prime;//素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
   for(ll i=2;i<=(ll)(l);i++) { //
        if(n%i==0){
            prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime[n]++;return;
}


int main() {

    int a;
    cin >> a;

    cout << a + a*a + a*a*a << endl;

    return 0;    
}



Measured memory_bytes: 3680
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/
*/

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

// utility of stdin,stdout
#define _CRT_SECURE_NO_WARNINGS
#define OUT cout << 
#define BR << endl
#define RET return 0
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int cnt = 0;
	string s,t;
	cin >> s;
	cin >> t;
	for (int i = 0; i < s.size(); ++i)
	{
		if(s.at(i) == t.at(i))	++cnt;
	}
	OUT(cnt) BR;
	RET;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] height=new int[10];
		for(int i=0;i<10;i++) {
			height[i]=sc.nextInt();
		}
		Arrays.sort(height);
		for(int i=9;i>=7;i--) {
			System.out.println(height[i]);
		}
	}

}


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int std_in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};
const int MOD = 1000000007;


int H, W, K;
ll nop1[10], nop2[10];    //num of patterns
ll dp[101][10];

void enum_pattern(int W){
    REP(i, 10) nop1[i] = nop2[i] = 0;
    REP(i, (1 << W)){
        bool skip = false;
        REP(j, W - 1){
            if(((i >> j) & 3) == 3){
                skip = true;
                break;
            }
        }
        if(skip) continue;
        REP(j, W){
            if(((i >> j) & 1) == 1){
                nop1[j + 1]++;
            }
            if(j == 0 && ((i >> j) & 1) == 0){
                nop2[j + 1]++;
            }
            if(((i >> j) & 3) == 0){
                nop2[j + 2]++;
            }
        }
    }
}

ll solve(){
    REP(i, 101) REP(j, 10) dp[i][j] = 0;
    dp[0][1] = 1;
    FOR(i, 1, H + 1){
        FOR(j, 1, W + 1){
            dp[i][j] = dp[i - 1][j - 1] * nop1[j - 1] % MOD + dp[i - 1][j + 1] * nop1[j] % MOD + dp[i - 1][j] * nop2[j];
            dp[i][j] %= MOD;
        }
    }
    return dp[H][K];
}

signed main(){
    cin >> H >> W >> K;
    if(W == 1){
        PRINT("1");
        return 0;
    }
    enum_pattern(W - 1);
    PRINT(solve());
    return 0;
}

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

int top, S[1000];

void push(int x){
    S[++top] = x;
}

int pop(){
    return S[(--top)+1];
}

int main(){
    char s[100];
    int x, y;
    top = 0;
    while(scanf("%s", s)!=EOF){
        if(s[0]=='+'){
            x = pop();
            y = pop();
            push(x+y);
        }
        else if(s[0]=='-'){
            x = pop();
            y = pop();
            push(y-x);

        }
        else if(s[0]=='*'){
            x = pop();
            y = pop();
            push(x*y);
        }
        else push(atoi(s));
    }
    printf("%d\n", pop());
    return 0;
}


Measured memory_bytes: 3204
N,M = map(int, input().split())
KA = []
a = []
ans = 0

for i in range(N):
    KA = list(map(int, input().split()))
    A = KA[1:]
    a += A
for j in range(1,M+1):
    if a.count(j) == N:
        ans += 1
print(ans)


Measured memory_bytes: 3060
n = int(input())
heap = list(map(int, input().split()))
for i in range(len(heap)):
    out = 'node {}: key = {}, '.format(i + 1, heap[i])
    parent = (i - 1) // 2
    out += 'parent key = {}, '.format(heap[parent]) if parent >= 0 else ''
    left = (2 * i) + 1
    out += 'left key = {}, '.format(heap[left]) if left < len(heap) else ''
    right = (2 * i) + 2
    out += 'right key = {}, '.format(heap[right]) if right < len(heap) else ''
    print(out)

Measured memory_bytes: 7684
#include <stdio.h>
int main(){
	int a,b,x;
	char op;
	for(;;){
		scanf("%d %c %d",&a,&op,&b);
		if(op=='?')break;
		switch(op){
			case'+':x=a+b;break;
			case'-':x=a-b;break;
			case'*':x=a*b;break;
			case'/':x=a/b;break;
		}
		printf("%d\n",x);
	}
	return 0;
}

Measured memory_bytes: 1812
#include<bits/stdc++.h>
using namespace std;
int n, f[105], vis[105][5][5][5][5], a[105][5][5][5][5];
#define ll long long
const int mod=1e9+7;
int dfs(int k){
	if(k>=3) {
		if(f[k-3]==1&&f[k-2]==2&&f[k-1]==3) return 0;
		if(f[k-4]==1&&f[k-2]==2&&f[k-1]==3) return 0;
		if(f[k-4]==1&&f[k-3]==2&&f[k-1]==3) return 0;
		if(f[k-3]==1&&f[k-2]==3&&f[k-1]==2) return 0;
		if(f[k-3]==2&&f[k-2]==1&&f[k-1]==3) return 0;
	}
	if(k==n+1){
		return 1;
	}
	ll s=0;
	for(int i=1;i<=4;i++){
		f[k]=i;
		if(vis[k][f[k-3]][f[k-2]][f[k-1]][i]) s+=a[k][f[k-3]][f[k-2]][f[k-1]][i];
		else s+=(a[k][f[k-3]][f[k-2]][f[k-1]][i]=dfs(k+1));
		vis[k][f[k-3]][f[k-2]][f[k-1]][i]=1;
		s%=mod;
		f[k]=0;
	}
	return s;
}
int main(){
	cin>>n;
	cout<<dfs(1);
}


Measured memory_bytes: 768
# -*- coding: utf-8 -*-
import sys

htable = [0] * 4 ** 12


def to_int(s):
    if s == 'A':
        return 1
    elif s == 'C':
        return 2
    elif s == 'G':
        return 3
    else:
        return 4


def to_hash(string):
    h = 0
    for i, s in enumerate(string):
        ints = to_int(s)
        h += 4**i * ints

    return h


def insert(string):
    h = to_hash(string)
    htable[h] = 1


def find(string):
    h = to_hash(string)
    if htable[h]:
        print('yes')
    else:
        print('no')


# if __name__ == '__main__':

n = int(input())

for line in sys.stdin:
    cmd, string = line.strip().split()

    if cmd == 'insert':
        insert(string)
    else:
        find(string)



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

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

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

  bool flag = true;
  for (int i = n - 2; i >= 0; --i) {
    if(a[i] >= a[i + 1] + 2) {
      flag = false;
      break;
    } else if(a[i] == a[i + 1] + 1) {
      a[i]--;
    }
  }
  if(flag) cout << "Yes" << '\n';
  else cout << "No" << '\n';
  return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
   int A,B,C;
   cin >>A>>B>>C;
   A<=100 && A>=-100 ;
   B<=100 && B>=-100 ;
   C<=100 && C>=-100 ;
   if (A==B) cout<<C;
   else if (A==C) cout<<B;
   else cout<<A;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
//    for(auto& it : m)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
//  priority_queue<ll int> pq;
//  priority_queue <ll int, vector<ll int>, greater<ll int> > pq;
//  vector<ll int> v;
//  vector< pair<ll int,ll int> > v;
//  set<ll int>::iterator it=s.begin();
//  unordered_map<  pair<ll int,ll int>, ll int> mp;
 
 
const int ALPHABET_SIZE = 26; 
  
// trie node 


int main() 
{ 
ll int T;T=1;
while(T--)
{ll int k,i,j,z,sum=0;
  cin>>k;
  for(i=1;i<=k;i++)
  {
    for(j=1;j<=k;j++)
    {
      for(z=1;z<=k;z++)
      {
        sum+=__gcd(i,__gcd(j,z));
      }
    }
  }
  cout<<sum<<endl;
}


       
    return 0; 
} 


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
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; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

string s;
int k, ans = INF;
vector<int> l;

void dfs(string t = "") {
  if (s.size() <= t.size()) {
    if (stoi(s) <= stoi(t)) chmin(ans, stoi(t));
    if (s.size() < t.size()) return;
  }
  for (int v: l) dfs(t + (char)('0' + v));
}

int main() {
  IOS;
  cin >> s >> k;
  M m;
  REP(i,k) {
    int d; cin >> d;
    m[d]++;
  }

  REP(i,10) if (m[i] == 0) l.push_back(i);
  dfs();
  COUT(ans);

  return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;
const int eps = 1e-4;

long long bin_pow(long long a, long long n)
{
    long long  res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    int x;
    cin >> x;

    vector<bool> used(x + 1);

       // cout << pow(31, 2) << '\n';
    for(int i = 1; i <= x; ++i)
    {
        for(int j = 2; j <= 10; ++j)
        {

            int val = bin_pow(i, j);
            //cout << i << ' ' << j << ' ' << val << '\n';
            if(val > x)
                break;
            else
                used[val] = 1;
        }
    }

    for(int i = x; i >= 1; --i)
    {
        if(used[i])
            return cout << i << '\n', 0;
    }
}


Measured memory_bytes: 256
using System;
public class Hello{
    public static void Main(){
        var s = Console.ReadLine();
        var ans = "";
        for(var i = 0;i < s.Length;i++){
            if(char.IsUpper(s[i])){
                ans += s[i].ToString().ToLower();
            }else{
                ans += s[i].ToString().ToUpper();
            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 9052
function main(input) {
  const args = input.split(' ');
  const a = parseInt(args[0], 10);
  const b = parseInt(args[1], 10);
  
  var max = a + b;
  if(max < a - b) {
    max = a - b;
  }
  if(max < a * b) {
    max = a * b;
  }
  console.log(max)
  
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.DDCC2019_qual
{
    class D
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            long m = ReadInt();
            int[] ds = new int[m];
            long[] cs = new long[m];
            long digits = 0;
            long sum = 0;
            for(int i = 0; i < m; i++)
            {
                long[] dc = ReadLongs();
                ds[i] = (int)dc[0];
                cs[i] = dc[1];
                digits += cs[i];
                sum += cs[i] * ds[i];
            }
            long res = digits - 1;
            long ups = sum / 9;
            if (sum % 9 == 0) ups--;
            res += ups;
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 17324
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
const int mod = 1e9 + 7;
// const int mod = 998244353;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

unordered_map<int, vector<int>> edges;
int f[100010][2];
bool visited[100010];
int n, x, y;

void dfs(int u) {
    visited[u] = true;
    // 0-black 1-white
    f[u][0] = f[u][1] = 1;
    if (edges.count(u)) {
        for (int v: edges[u]) {
            if (!visited[v]) {
                dfs(v);
                f[u][0] = (LL)f[u][0] * f[v][1] % mod;
                f[u][1] = (LL)f[u][1] * (f[v][0] + f[v][1]) % mod;
            }
        }
    }
}

inline void work() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(1);
    cout << (f[1][0] + f[1][1]) % mod << "\n";
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    work();
    return 0;
}

Measured memory_bytes: 15524
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
    int n; cin >> n;
    vector<vector<int>> a(n,vector<int>(n));
    vector<int> now(n,0);
    rep(i,n) rep(j,n-1) cin >> a[i][j], a[i][j]--;
    int total = n * (n-1) / 2;
    int ans = 0;
    queue<int> q;
    set<int> se;
    rep(i,n){
        if(a[a[i][0]][0] == i){
            if(se.find(i) == se.end() && se.find(a[i][0]) == se.end()){
                q.push(i);
                se.insert(i); se.insert(a[i][0]);
            }
        }
    }
    while(total > 0){
        se.clear();
        int m = q.size();
        total -= m;
        vector<int> wait;
        rep(j,m){
            int u = q.front(); q.pop();
            int v = a[u][now[u]];
            wait.push_back(u);
            wait.push_back(v);
            now[u]++;
            now[v]++;
        }
        for(auto u : wait){
            if(se.find(u) != se.end()) continue;
            if(now[u] == n-1) continue;
            int v = a[u][now[u]];
            if(se.find(v) != se.end()) continue;
            if(now[v] == n-1) continue;
            if(a[v][now[v]] != u) continue;
            q.push(u);
            se.insert(u);
            se.insert(v);
        }
        if(!m){
            puts("-1");
            return 0;
        }
        ans++;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 7564
import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')

Measured memory_bytes: 54364
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> P;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e18;
const double PI=3.1415926535897932;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

#define REP(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end());
#define ADD(a,b) a=(a+b)%mod


int main(){
    ll A; double B;
    cin>>A>>B;
    B+=0.0001;
    B*=100;
    ll X=B;
    X*=A;
    X/=100;
    cout<<X<<endl;
}


Measured memory_bytes: 3760
import math
h, w = map(int, input().split())

out = 0
if min(h, w) == 1:
    out = 1
else:
    out += (h // 2) * 2 * (w // 2) * 2 / 2 + (h % 2) * math.ceil(w / 2) + (w % 2) * math.ceil(h / 2) - (h % 2) * (w % 2)
print(int(out))


Measured memory_bytes: 9080
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		StringBuilder sb=new StringBuilder("");
		int H=sc.nextInt(),W=sc.nextInt(),x;
		while (H!=0 || W!=0){
			x=0;
			for (int m=1;m<=W;m++){
				x++;
				sb.append("#");}
		for (int n=1;n<=H;n++){System.out.println(sb);}
			System.out.println();
			sb.delete(0,x);
			H=sc.nextInt();W=sc.nextInt();
				}}}

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

int main(){
  int N, X, Y;
  cin >> N >> X >> Y;
  int L, C, R;
  L = X-1;
  C = Y-X+1;
  R = N-Y;
  vector<int> ans(N);

  // L only
  for(int i=1;i<=L;i++){
    ans.at(i) += L-i+1;
  }
  // R only
  for(int i=1;i<=R;i++){
    ans.at(i) += R-i+1;
  }
  // L C R
  if(L>=1 && R>=1){
    for(int l=1;l<=L;l++){
      for(int r=1;r<=R;r++){
        ans.at(L+r-l+2)++;
      }
    }
  }
  // C only
  if(C%2 == 0){
    for(int i=1;i<=C/2-1;i++){
      ans.at(i) += C;
    }
    ans.at(C/2) += C/2;
  }else if(C%2 == 1){
    for(int i=1;i<=C/2;i++){
      ans.at(i) += C;
    }
  }
  // LC, CR;
  if(C%2 == 0){
    for(int l=1;l<=L;l++){
      for(int c=1;c<=C/2-1;c++){
        ans.at(L+c-l+1) += 2;
      }
      ans.at(L+C/2-l+1)++;
    }
    for(int r=1;r<=R;r++){
      for(int c=1;c<=C/2-1;c++){
        ans.at(R+c-r+1) += 2;
      }
      ans.at(R+C/2-r+1)++;
    }
  }else if(C%2 == 1){
    for(int l=1;l<=L;l++){
      for(int c=1;c<=C/2;c++){
        ans.at(L+c-l+1) += 2;
      }
    }
    for(int r=1;r<=R;r++){
      for(int c=1;c<=C/2;c++){
        ans.at(R+c-r+1) += 2;
      }
    }
  }

  // output
  for(int i=1;i<=N-1;i++){
    cout << ans.at(i) << endl;
  }

  return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())

dx = tx-sx
dy = ty-sy

ans = ""
for i in range(dx): ans += "R"
for i in range(dy): ans += "U"
for i in range(dx): ans += "L"
for i in range(dy): ans += "D"

ans += "D"
for i in range(dx+1): ans += "R"
for i in range(dy+1): ans += "U"
ans += "L"
ans += "U"
for i in range(dx+1): ans += "L"
for i in range(dy+1): ans += "D"
ans += "R"

print(ans)


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main()
{
	int a[6],i,j,t,m=0;
	for(i=0;i<6;i++)
	{
		cin>>a[i];
	}
	for(i=0;i<4;i++)
	{
		for(j=i+1;j<4;j++)
		{
			if(a[i]<a[j])
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
	}
	if(a[4]<a[5])
	{	
		t=a[4];
		a[4]=a[5];
		a[5]=t;
	}
	for(i=0;i<3;i++)
	{
		m=m+a[i];
	}
	cout<<m+a[4]<<endl;
	return 0;
}

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

using namespace std;

/**
 *  Name: Chris M. Perez
 *  University: Interamerican University Metro Campus
 *
**/

#define endl '\n'
#define MOD 10e18
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd(x , y) __gcd(x , y)
#define all(x) (x).begin() , (x).end()
#define forn(i , a , b) for(int i=(a);i<(b);i++)
#define forrange(j , a , b) for(int j=(a);j<=(b);j++)
#define nestedforn(i , a , b , j , c , d) for(int i=(a);i<=(b);i++) for(int j=(c);j<=(d);j++)
#define sort_all(x) sort(all(x))
#define zeros_at_beginning(x) __builtin_clz(x)
#define zeros_at_end(x) __builtin_ctz(x)
#define ones(x) __builtin_popcount(x)
#define parity_even_or_odd_ones __builtin_parity(x)

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef tuple<int , int , int> tiii;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int lli;


//template< typename T1, typename T2 > struct pair {
  //T1 first;
  //T2 second;
//};
               
inline int input(){
  int n;
  scanf("%d" , &n);
  return n;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif

  int n; cin >> n;
  if(n == 25) cout << "Christmas" << endl;
  if(n == 24) cout << "Christmas Eve" << endl;
  if(n == 23) cout << "Christmas Eve Eve" << endl;
  if(n == 22) cout << "Christmas Eve Eve Eve" << endl;
 
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

Measured memory_bytes: 256
import sys

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


def main():
    from itertools import accumulate
    n = int(readline())
    a = list(map(int, readline().split()))
    a.sort()
    acc = list(accumulate(a))

    ok = n - 1
    ng = -1

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        i = mid
        cur = acc[i]
        while i < n - 1:
            if 2 * cur >= a[i + 1]:
                cur += a[i + 1]
                i += 1
            else:
                break
        if i == n - 1:
            ok = mid
        else:
            ng = mid

    print(n - ok)


if __name__ == '__main__':
    main()


Measured memory_bytes: 90764
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e7+5,mod=998244353;
int n,ret,fact[N],inv[N],pw[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;
	for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
}
inline int C(CI n,CI m)
{
	return 1LL*fact[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	RI i,j; for (scanf("%d",&n),init(n),i=(n>>1)+1;i<=n;++i)
	inc(ret,1LL*C(n,i)*pw[n-i+1]%mod);
	return printf("%d",(quick_pow(3,n)-ret+mod)%mod),0;
}

Measured memory_bytes: 117376