akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;

const int size = 100;
struct Node{
	int pos;
	vector<int> reachableIdx;
	vector<pair<int, int>> reachableIdx2;
	Node():reachableIdx(size){
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, l, q;
	cin >> n;
	vector<int> xs(n);
	vector<Node> nodes(n);
	for(int i=0;i<n;i++){
		cin >> xs[i];
		nodes[i].pos = xs[i];
	}
	cin >> l >> q;
	
	for(int i=0;i<size;i++){
		nodes[n - 1].reachableIdx[i] = n - 1;
		nodes[n - 1].reachableIdx2.emplace_back(n - 1, 0);
	}
	for(int i=n-2;i>=0;i--){
		int pos = nodes[i].pos + l;
		int idx = upper_bound(xs.begin(), xs.end(), pos) - xs.begin() - 1;
		nodes[i].reachableIdx[0] = i;
		nodes[i].reachableIdx2.emplace_back(i, 0);
		for(int j=1;j<size;j++){
			nodes[i].reachableIdx[j] = nodes[idx].reachableIdx[j - 1];
		}
		int len = 0;
		auto np = nodes.begin() + i;
		for(int j=1;j<size;j++){
			len += size - 1;
			np = nodes.begin() + np -> reachableIdx.back();
			nodes[i].reachableIdx2.emplace_back(np - nodes.begin(), len);
		}
		// println(nodes[i].reachableIdx2);
	}

	for(int i=0;i<q;i++){
		int a, b;
		cin >> a >> b;
		if(a > b){
			swap(a, b);
		}
		a--;
		b--;
		Node n = nodes[a];
		int len = 0;
		// for(int i=0;i<5;i++){
		// 	cout<<n.reachableIdx[i]<<' ';
		// }cout << endl;
		bool jump = true;
		while(1){
			// cout<<len<<' ';
			if(n.reachableIdx.back() >= b){
				len += lower_bound(n.reachableIdx.begin(), n.reachableIdx.end(), b) - n.reachableIdx.begin();
				// cout<<len<<endl;
				break;
			// }else if(n.reachableIdx2.back() >= pair<int, int>{b, 1e9}){
			// }else if(n.reachableIdx2.back().first != nodes.size() - 1){
			}else if(jump){
			// }else{
				// auto next = *(lower_bound(n.reachableIdx2.begin(), n.reachableIdx2.end(), pair<int, int>{b, 1e9}) - 1);
				auto nextite = (lower_bound(n.reachableIdx2.begin(), n.reachableIdx2.end(), pair<int, int>{b, 1e9}) - 1);
				if(nextite -> first == nodes.size() - 1){
					jump = false;
					continue;
				}
				auto next = *nextite;
				len += next.second;
				n = nodes[next.first];
				// cout<<len<<' '<<next.first<<' '<<next.second<<endl;
			// }else if(n.reachableIdx2.back() < pair<int, int>{b, 1e9}){
			// 	auto next = n.reachableIdx2.back();
			// 	len += next.second;
			// 	n = nodes[next.first];
				// cout<<len<<' '<<next.first<<' '<<next.second<<endl;
			}else{
				len += size - 1;
				n = nodes[n.reachableIdx.back()];
			}
		}
		cout << len << endl;
	}
	return 0;
}



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

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  for (int i=0; i<N; i++) {
    cin >> S[i];
  }
  bool ans=true;
  for (int i=0; i<N-1; i++) {
    for (int j=i+1; j<N; j++) {
      if (S[i]==S[j]) {
        ans=false;
      }
    }
  }
  for (int i=0; i<N-1; i++) {
    if (S[i+1][0]!=S[i][S[i].size()-1]) {
      ans=false;
    }
  }
  if (ans==true) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  } 
}


Measured memory_bytes: 384
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

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

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <string>
#include <algorithm>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)
using namespace std;

int main()
{
int n,x,k;
cin>>n>>x>>k;
int r=n/x;
int f=n%x;
if(f==0){
    cout<<k*r<<endl;
}
else {
    cout<<(r+1)*k<<endl;
}

    return 0;
}


Measured memory_bytes: 3612
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

signed main(void)
{
  int n, m;
  cin >> n >> m;
  vector<PII> v;
  REP(i, m) {
    int c, d;
    cin >> c >> d;
    if(c < d) v.PB({d, c});
  }
  sort(ALL(v));

  if(v.size() == 0) {
    cout << n+1 << endl;
    return 0;
  }

  int ret = n+1;
  for(int i=0; i<m; ++i) {
    // cout << "i:" << i << endl;
    int l = v[i].second, r = v[i].first;
    int idx = i;
    for(int j=i+1; j<m; ++j) {
      if(v[j].second <= r) {
        r = v[j].first;
        chmin(l, v[j].second);
        idx = j;
      }
      // cout << l << " " << r << " " << idx << endl;
    }
    ret += (r-l)*2;
    i = idx;
  }

  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 3140
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;



int main() {
    int n;
    scanf("%d", &n);
    // dp[heads]
    // if we had i tosses, then tails=i-heads
    vector<double> dp(n + 1);
    // dp[i] - p-bility that there are i heads so far
    dp[0] = 1;
    for(int coin = 0; coin < n; ++coin) {
        double p_heads;
        scanf("%lf", &p_heads);
        for(int i = coin + 1; i >= 0; --i) {
            dp[i] = (i == 0 ? 0 : dp[i-1] * p_heads) + dp[i] * (1 - p_heads);
        }
    }
    double answer = 0;
    for(int heads = 0; heads <= n; ++heads) {
        int tails = n - heads;
        if(heads > tails) {
            answer += dp[heads];
        }
    }
    printf("%.10lf\n", answer);
}

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

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

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

int main(){
	
	int N;
	long D;
	
	cin >> N >> D;
	
	vector<long> X(N), Y(N);
	
	for(int i = 0;i < N;i++){
		cin >> X[i] >> Y[i];
	}
	
	int sum = 0;
	for(int i = 0;i < N;i++){
		if( (X[i] * X[i] + Y[i] * Y[i]) <= (D * D) ){
			sum++;
		}
	}
	
	cout << sum;
	
	return 0;
	
}


Measured memory_bytes: 6424
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int N;
int A[200005];
vector <int> pos[1000005];
bool isCorrect[200005];
int ans;

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		isCorrect[i] = true;
	}
	sort(A, A + N);
	for (int i = 0; i < N; i++)
		pos[A[i]].push_back(i);

	for (int i = 0; i < N; i++) {
        if (i != 0 && A[i - 1] == A[i]) {
            isCorrect[i - 1] = false;
            isCorrect[i] = false;
        }
		if (isCorrect[i]) {
			for (int j = A[i] * 2; j < 1000005; j += A[i]) {
                if (pos[j].empty()) continue;
				for (int k : pos[j]) isCorrect[k] = false;
			}
		}
	}
	for (int i = 0; i < N; i++)
		if (isCorrect[i])
			ans++;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 33924
#include <iostream>
#include <string>
using namespace std;
 
int main() {
	int n;cin >> n;
	for (int i =0; i<n;++i) {
		string s;cin >>s;
		if(s=="Y"){
			cout << "Four" << endl;
			return 0;
		}
	}
	cout << "Three" << endl;
	return 0;
}

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

#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()

{
	string s;
	cin >> s;

	int size = s.size();

	cout << s[0] << size - 2 << s[size - 1] << endl;

	return 0;
}

Measured memory_bytes: 3592
long m=1e9+7,f[1<<20]={1},v[1<<20]={1},a=1;i;
long p(long a,long b){return b?p(a*a%m,b/2)*(b%2?a:1)%m:1;}
main(n){
	for(scanf("%d",&n);i++<n;)v[i]=p(f[i]=a=a*i%m,m-2);
	for(i=n/2;i<n;i++)a=(a-f[i]*f[i-1]%m*v[2*i-n]%m+m)%m;
	printf("%ld",a);
}

Measured memory_bytes: 15744
#include<bits/stdc++.h>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;
struct PrimalDual{
	struct edge{
		int to,cap,cost,rev;
	};
	vector<vector<edge>>graph;
	bool negative=false;
	void add_edge(int from,int to,int cap,int cost){
		graph[from].push_back({to,cap,cost,len(graph[to])});
		graph[to].push_back({from,0ll,-cost,len(graph[from])-1});
		if(cost<0)negative=true;
	}
	int minCostFlow(int s,int t,int f){
		int V=len(graph);
		vector<int>potential(V),minCost,prevv(V,-1),preve(V,-1);
		int res=0;
		if(negative){
			minCost.assign(V,inf);
			minCost[s]=0;
			rep(_,V-1){
				rep(i,V){
					rep(j,len(graph[i])){
						edge &e=graph[i][j];
						if(e.cap>0&&chmin(minCost[e.to],minCost[i]+e.cost+potential[i]-potential[e.to])){
							prevv[e.to]=i;
							preve[e.to]=j;
						}
					}
				}
			}
			if(minCost[t]==inf)return -1;
			rep(i,V)potential[i]+=minCost[i];
			for(int i=t;i!=s;i=prevv[i]){
				graph[prevv[i]][preve[i]].cap--;
				graph[i][graph[prevv[i]][preve[i]].rev].cap++;
			}
			res+=potential[t];
			f--;
		}

		while(f>0){
			minCost.assign(V,inf);
			minCost[s]=0;
			priority_queue<P,vector<P>,greater<>>que;
			que.push({0,s});
			while(!que.empty()){
				P p=que.top();que.pop();
				if(minCost[p.second]<p.first)continue;
				rep(i,len(graph[p.second])){
					edge &e=graph[p.second][i];
					if(e.cap>0&&chmin(minCost[e.to],p.first+e.cost+potential[p.second]-potential[e.to])){
						prevv[e.to]=p.second;
						preve[e.to]=i;
						que.push({minCost[e.to],e.to});
					}
				}
			}

			if(minCost[t]==inf)return -1;
			rep(i,V)potential[i]+=minCost[i];
			int addflow=f;
			for(int i=t;i!=s;i=prevv[i])chmin(addflow,graph[prevv[i]][preve[i]].cap);
			f-=addflow;
			res+=addflow*potential[t];
			for(int i=t;i!=s;i=prevv[i]){
				edge &e=graph[prevv[i]][preve[i]];
				e.cap-=addflow;
				graph[i][e.rev].cap+=addflow;
			}
		}
		return res;
	}
	PrimalDual(int V):graph(V){};
};

int N,M;
char c[55][55];
bool used[55][55];
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>M;
	rep(i,N)rep(j,M)cin>>c[i][j];
	PrimalDual F(N*M+2);
	int cnt=0;
	rep(i,N)rep(j,M){
		if(c[i][j]=='o'){
			cnt++;
			memset(used,0,sizeof(used));
			F.add_edge(N*M,i*M+j,1,0);
			used[i][j]=true;
			rep(k,N)rep(l,M){
				if((k!=i||l!=j)&&used[k][l]){
					F.add_edge(i*M+j,k*M+l,1,-(k-i+l-j));
				}
				if(c[k+1][l]!='#')used[k+1][l]|=used[k][l];
				if(c[k][l+1]!='#')used[k][l+1]|=used[k][l];
			}
		}
		F.add_edge(i*M+j,N*M+1,1,0);
	}
	cout<<-F.minCostFlow(N*M,N*M+1,cnt)<<"\n";
}


Measured memory_bytes: 9468
from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = [0] * n
    flag = False
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if max(counter) > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()


Measured memory_bytes: 11140
import heapq
def _int(x):
    return -int(x)
N, M = map(int, input().split())
A = list(map(_int, input().split()))
heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, x-x//2)
print(-sum(A))

Measured memory_bytes: 72216
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var x = ReadLong();
            return x == 0 ? 1 : 0;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 27536
#include<iostream>
#include<math.h>
using namespace std;

bool check(float num){
  bool result = false;
  if(ceil(num)==floor(num) && num>=0) result = true; 
  return result;
}

int main(){
  int x,y;
  int crane, turtle;
  string result="No";
    
  cin >> x >> y; 
  turtle = float(0.5 * y - x);
  crane = float(2*x - 0.5*y);
  
//  cout << crane << " : " << turtle << endl;
  
  if(check(turtle) && check(crane)) result="Yes";
  if(y%2!=0) result="No";
 
  cout << result << endl;
}
  
  

Measured memory_bytes: 3644
import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

a, b, x = na()
d = x / (a * a)
if 2 * d < b:
    angle = math.atan(b / (2 * a * d / b)) * (180 / math.pi)
else:
    angle = math.atan(2 * (b - d) / a) * (180 / math.pi)
if angle < 0:
    angle += 180
if angle > 180:
    angle -= 180
print(angle)







Measured memory_bytes: 3188
n,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
from collections import defaultdict

reached=defaultdict(int)
reached[1]=1
i=1
for j in range(1,n+1):
    if reached[A[i]]==0:
        reached[A[i]]=j+1
    else:
        t1=reached[A[i]]
        t2=j+1
        break
    i=A[i]
reached=dict(reached)
if k>t1-1:
    ama=(k-(t1-1))%(t2-t1)
    ans=[s for s,h in reached.items() if h==t1+ama]
else:
    ans=[s for s,h in reached.items() if h==k+1]
print(ans[0])

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

const int N = 14;

int a[N][N], c[N], val[N];
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, x; cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
		for (int j = 0; j < m; j++) cin >> a[i][j];
	}
	int ans = 1e9;
	for (int mask = 1; mask < (1 << n); mask++) {
		int nw = 0;
		memset(val, 0, sizeof val);
		for (int i = 0; i < n; i++) if (mask >> i & 1) {
			for (int j = 0; j < m; j++) val[j] += a[i][j];
			nw += c[i];
		}
		int ok = 1;
		for (int i = 0; i < m; i++) if (val[i] < x) ok = 0;
		if (ok) ans = min(ans, nw);
	}
	if (ans == 1e9) ans = -1;
	cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
#define mp make_pair
#define int long long
#define mod 1000000007
#define DEBUG cout<<"Hello1\n";
#define all(v) (v).begin(),(v).end()
#define clr(x) memset(x,0,sizeof(x))
#define deb(...) debug(#__VA_ARGS__, __VA_ARGS__);
const int N = 1e6 + 5;
const double pi =  acosl(-1);
const long long inf = 1e18 + 5;
using namespace std;
template<typename T> void debug(string s, T x)
{
	cout << s << " = " << x << "\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args)
{
	cout << s.substr(0, s.find(',')) << " = " << x << " | ";
	debug(s.substr(s.find(',') + 2), args...);
}
template<class T> void print_container(T &container)
{
	for (auto &t : container)
	{
		cout << t << " ";
	}
	cout << endl;
}
template<class T> void print_pair_container(T &container)
{
	for (auto &t : container)
	{
		cout << t.first << " " << t.second << endl;
	}
	cout << endl;
}
template<class T> void printArr(T &a, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
typedef long long ll;
typedef pair<int, int> pii;

//Template Ends
int n;
int dp[N];

void solve()
{
	cin >> n;

	dp[0] = 1;
	for (int i = 3; i <= n; i++) {

		dp[i] = 1;
		for (int j = i - 3; j >= 3; j--) {
			dp[i] += (dp[j] + (i - j != j) ? dp[i - j] : 0 ) % mod;
			dp[i] %= mod;
		}
	}

	// printArr(dp, n + 1);
	cout << dp[n] << endl;
}

int32_t main()
{
	IOS;
	solve();

	return 0;
}



Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (int)1e9 + 7

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

int main()
{
    int n;
    cin >> n;
    V v(n);
    REP(i, n)
    {
        int a;

        cin >> a;

        v[a]++;
    }

    for (int i = n % 2 == 0; i < n; i += 2)
    {
        if ((i == 0 && v[i] != 1) ||
            (i > 0 && v[i] != 2))
        {
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;
    REP(i, n / 2)
    {
        ans *= 2;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
/*
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll max3(ll a, ll b, ll c){return max(a, max(b, c));};
ll min3(ll a, ll b, ll c){return min(a, min(b, c));};
ll max4(ll a, ll b, ll c, ll d){return max(max(a, b), min(c, d));};
ll min4(ll a, ll b, ll c, ll d){return min(min(a, b), min(c, d));};
ll max5(ll a, ll b, ll c, ll d, ll e){return max(max(a, b), max3(c, d, e));};
ll min5(ll a, ll b, ll c, ll d, ll e){return min(min(a, b), min3(c, d, e));};
*/
const ll INFL = 1LL << 60;//10^18 = 2^60
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD = 998244353;

vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

//デバッグ
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

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


ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}


//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; 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;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

//素因数分解O(√n)
vector<pair<ll, ll>> MakePrimeList(ll x) {
    vector<pair<ll, ll>> res;
    for(ll k=2; k*k<=x; k++) {
        if(x % k == 0) {
            ll cnt = 0;
            while(x % k == 0){
              x /= k;
              cnt++;
            }
            res.pb({k, cnt});
        }
    }
    if(x > 1) res.push_back({x, 1});
    return res;
}


ll N, P;

int main(){
  cin >> N >> P;
  vector<pair<ll, ll>> primes = MakePrimeList(P);
  ll ans = 1;
  rep(i, primes.size()){
    if(primes[i].s >= N){
      ans *= pow_long(primes[i].f, (primes[i].s / N));
    }
  }
  cout << ans << endl;
}


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


public class Main{
	public static void main(String[] args) throws Exception{
		//入力
		String[][] in_data=input();
		

		String A[]=new String[2];
		for(int k=0;k<=in_data.length-1;k++){
		//出力	
			A[0]=in_data[k][0];
			A[1]=in_data[k][1];	
			outPut(A);
		}
	}
	//入力inut関数を用意a
	public static String[][] input() throws Exception{
		
		int s=0;
		String str="";
		String text="";
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while((str=br.readLine())!=null){
		        text=text+str+"\n";
			s=s+1;
			}
		
		String[] tempArray=text.split("\n");

		String twoArray[][]=new String[s][1];
		for(int k=0;k<=s-1;k++){
			twoArray[k]=tempArray[k].split(" ");	
		}
		return twoArray;
	}
	
	//出力処理関数
	public static void outPut(String[] data) throws Exception{
	
	//描写クラスからインスタンス化
		Draw rec=new Draw();
		rec.draw(data);
	}


}

class Draw{
	public void draw(String[] drawArray) throws Exception{
		String mark="";
		int W;
		int H;
		int i=1;
		int j=1;
		
		H=Integer.parseInt(drawArray[0]);
		W=Integer.parseInt(drawArray[1]);
		
		if(W==0 && H==0){
			
		}else{
		
		while(j<=W){
			mark=mark+"#";
			j=j+1;}
		while(i<=H){
			System.out.println(mark);
			i=i+1;}
		System.out.println("");
	}}


}


Measured memory_bytes: 25712
#include <iostream>
using namespace std;
int main(void){
    int x, y, z, w, u;
    int time = 0;
    cin >> x >> y >> z >> w >> u;
    if(x < 0){
       x = -x;
       time = x*z + w + y*u;
       cout << time <<endl;
    }
    else{
        time = (y-x)*u;
        cout << time << endl;
    }
}



Measured memory_bytes: 3052
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll n,t[200010],mx = 10000000000000000;
ll dp[100010];
vector<pair<int,ll>> v[100010];
void built(){
	for(int i = n-1;i>0;i--){
		t[i] = min(t[i<<1],t[i<<1|1]);
	}
}

void update(ll p,ll a){
	for(t[p+=n] = a;p>1;p >>= 1){
		t[p>>1] = min(t[p],t[p^1]);
	}
}

ll query(int l, int r){
	ll mn = mx;
	for(l += n, r += n; l<r; l >>= 1,r >>= 1){
		if(l&1) mn = min(mn,t[l++]);
		if(r&1) mn = min(mn,t[--r]);
	}
	return mn;
}

int main(){
	int i,j,m;
	cin >> n >> m;
	for(i=0;i<m;i++){
		int l,r,c;
		cin >> l >> r >> c;
		l--; r--;
		v[r].push_back({l,c});
	}
	for(i=0;i<n;i++){
		dp[i] = mx;
		t[i + n] = mx;
	}
	built();
	dp[0] = 0;
	update(0,0);
	for(i=1;i<=n;i++){
		for(j=0;j<v[i].size();j++){
			dp[i] = min(dp[i],query(v[i][j].first,i) + v[i][j].second);
		}
		update(i,dp[i]);
	}
	if(dp[n - 1]!=mx){
		cout << dp[n - 1] << endl;
	}else{
		cout << -1 << endl;
	}
}

Measured memory_bytes: 7936
n,h =map(int,input().split())

a=[]
b=[]

for _ in range(n):
  aa,bb =map(int,input().split())
  a.append(aa)
  b.append(bb)
  
b.sort()
c=max(a)
b=b[::-1]
#print(c,b)

count=0
damage=0

for item in b:
  if item>=c and damage<h:
    damage+=item
    count+=1
  else:
    break

if damage >= h:
  print(count)
else:
  print(count+((damage-h)//c)*(-1))


Measured memory_bytes: 11832
from itertools import accumulate
import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_acc = [0] + list(accumulate(a))  # aを0冊読む=1冊も読まない場合があるので、[0]を先頭に追加します
b_acc = list(accumulate(b))  # bisect_rightでは、x以下の要素がいくつあるか？を求めるので、こちらに0は入れません

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        # aをこれ以上読めません
        break

    bn = bisect.bisect_right(b_acc, rem)
    ans = max(ans, an + bn)

print(ans)

Measured memory_bytes: 49128
import static java.lang.Integer.parseInt;
import static java.lang.System.out;
import java.io.File;
import java.util.Scanner;

public class Main extends BaseExe {

    public static void main(String[] args) {
        new Main().exeSysIn();
    }

    @Override
    protected void execute(Scanner scan) {
        String inDataStr = "";
        int[] combiList = getConb();
        while (scan.hasNextLine() && !"".equals(inDataStr = scan.nextLine())) {
            out.println(combiList[parseInt(inDataStr)]);
        }
    }

    private int[] getConb() {
        int[] combiList = new int[51];
        for (int a = 0; a < 10; a++)
            for (int b = 0; b < 10; b++)
                for (int c = 0; c < 10; c++)
                    for (int d = 0; d < 10; d++)
                        combiList[a + b + c + d]++;
        return combiList;
    }

}

abstract class BaseExe {

    public void exeSysIn() {
        try (Scanner scan = new Scanner(System.in)) {
            execute(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void exeFileIn(String inDataPath) {
        try (Scanner scan = new Scanner(new File(inDataPath))) {
            execute(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    protected abstract void execute(Scanner scan);
}

Measured memory_bytes: 26124
#include<bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define ios cin.tie(0); ios::sync_with_stdio(false)
#define FIX(a) cout << fixed << setprecision(a)
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//manip
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power_mod(T a, T b) {return b ? power_mod(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
template<class T> T power(T a, T b) {return b ? power(a * a, b / 2) * (b % 2 ? a : 1) : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
template<typename T> T gcd(T a, T b) {if (b == 0) return a; return gcd(b, a % b);}
template<typename T> T lcm(T a, T b) {return a / gcd(max(a, b), min(a, b)) * b;} //先に割る!!
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outaa(a, m, n) rep(i, m) {rep(j, n) cout << a[i][j] << " "; cout << endl;} cout << endl
#define out(a) cout << a << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl

//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//minimal required terms
//cast caution
//look constraints always


int main() {
    
    
    
    int n, m; cin >> n >> m;
    vector<vector<int> > v(3 * n);
    rep(i, m) {
        int s, t; cin >> s >> t; s--; t--;
        
        v[s * 3].eb(t * 3 + 1); //0 to 1
        v[s * 3 + 1].eb(t * 3 + 2);
        v[s * 3 + 2].eb(t * 3);
        
    }
    int s, t; cin >> s >> t; s--; t--;
    
    
    
    ll reached[300001]; fill_n(reached, 300001, -1);
    queue<pair<int, ll> > q;
    q.push(pii(s * 3, 0));
    reached[s * 3] = 0;
    while (!q.empty()) {
        int now = q.front().F;
        ll cost = q.front().S;
        q.pop();
        rep(i, SZ(v[now])) {
            int nxt = v[now][i];
            if (reached[nxt] != -1) continue;
            reached[nxt] = cost + 1;
            q.push({nxt, cost + 1});
        }
    }
    //outa(reached, 9);
    out((reached[t * 3] == -1 ? -1 : reached[t * 3] / 3));
}


Measured memory_bytes: 18944
#include<stdio.h>
#include<math.h>
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int i;
    int a[30], b[30];
    for (i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    int p[10][10] = {};
    for (i = 0; i < m; i++)
        p[a[i] - 1][b[i] - 1] = p[b[i] - 1][a[i] - 1] = 1;
    int x, now, y;
    int j, k;
    int q[10];
    int ans = 0;
    for (j = 0; j < pow(n, n - 1); j++)
    {
        for (i = 0; i < n; i++)
            q[i] = 0;
        x = j;
        now = x % n;
        x /= n;
        k = 0;
        q[now] = 1;
        for (i = 1; i < n; i++)
        {
            y = x % n;
            x /= n;
            if (q[y] == 1)
            {
                k++;
                break;
            }
            if (p[now][y] == 0)
            {
                k++;
                break;
            }
            now = y;
            q[now] = 1;
        }
        if (k == 0)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

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


int n, a, b, p;
int x, y, z;
int main(){
	cin>>n>>a>>b;
	for(int i=0; i<n; i++){
		cin>>p;
		if(p<=a) x++;
		else if(p>=b+1) z++;
		else y++;
	}
	cout<<min({x, y, z});
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

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

    vector<vector<double>> dp(n+1, vector<double>(n+1, 0.0));
    dp[0][0] = 1.0;

    REP(i, n){
        double p;
        cin >> p;
        REP(j, n){
            dp[i+1][j+1] += dp[i][j] * p;
            dp[i+1][j] += dp[i][j] * (1-p);
        }
    }

    double ans = 0.0;
    for(int i=n; i>n/2; i--){
        ans += dp[n][i];
    }

    cout << setprecision(10) << ans << endl; 
    
    return 0;
}

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> dices(N);
    for (int i = 0; i < N; i++)
    {
        cin >> dices.at(i);
    }
    ll diceSum = 0;
    for (int i = 0; i < K; i++)
    {
        diceSum += dices.at(i);
    }
    ll diceSumMax = 0;
    ll diceMaxLeftIndex = 0;
    for (int i = 1; i < N - K + 1; i++)
    {
        diceSum = diceSum + dices.at(i + K - 1) - dices.at(i - 1);
        if (diceSum > diceSumMax)
        {
            diceSumMax = diceSum;
            diceMaxLeftIndex = i;
        }
    }
    double answer = 0;
    for (int i = diceMaxLeftIndex; i < diceMaxLeftIndex + K; i++)
    {
        double dice = dices.at(i);
        answer += dice * (dice + 1) / 2 / dice;
    }
    cout << fixed << setprecision(6) << answer << endl;
    return 0;
}


Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG
    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
     int a , b;
      cin >> a >> b;
      if(a>b){
        cout << "safe" << endl;
      }
      else{
        cout << "unsafe" << endl;
      }
    }

Measured memory_bytes: 3636
let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  Printf.printf "%.9f\n" @@
  1. /. Array.fold_left (fun s a -> s +. 1. /. float_of_int a) 0. as_


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

int main() {
	int n,sum=0;
	int i=0;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n;i++) {
		cin >> vec.at(i);
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	for (int i = 0; i <n; i++) {


		if (i % 2 == 0) {
			sum += vec.at(i);
		}
		else {
			sum -= vec.at(i);
		}
	}
	cout << sum<< endl;


	//system("pause");
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

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

	vector<int> H(N);
	for (int i = 0; i < N; i++)
		cin >> H[i];

	int ans = 0;
	int h = 0;
	for (int i = 0; i < N; i++) {
		if (H[i] >= h) {
			ans++;
			h = H[i];
		}
	}

	cout << ans << endl;

	return 0;
}


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

int main() {
    // your code goes here
    ll n,k,l;
    cin >> n >> k;
    l=k;
    for(ll i=1;;i++){
        if(n<k){
            cout << i << endl;
            return 0;
        }
        k*=l;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define ll long long

int main(){
  ll A, B, C;
  cin >> A >> B >> C;
  if ((A*B*C)%2==0) { cout << 0 << endl; return 0; }

  cout << min(min(A*B, B*C), C*A) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
// Welcome to my source code!

int main() {
    IOS
    int N, Y, x = -1, y = -1, z = -1;
    cin >> N >> Y;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N - i; j++) {
            int f = N - (i + j);
            if (f >= 0 && Y == (10000 * i + 5000 * j + 1000 * f)) {
                x = i; y = j; z = f;
                break;
            }
        }
    }
    cout << x << ' ' << y << ' ' << z << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]


    token = lines[0].split()
    a = int(token[0])
    b = int(token[1])
    c = int(token[2])

    return (a, b, c)


def solve(a, b, c):

    result = "No"
    if a <= c and c <= b:
        result = "Yes"
    if a >= c and c >= b:
        result = "Yes"

    return result


def main():
    # 出力

    print("%s" % solve(*parse_input()))

if __name__ == '__main__':

    main()
	

Measured memory_bytes: 3064
wide = []
high = []

count = 0;

while wide[count - 1] != 0 && high[count - 1] != 0  do
	high[count],wide[count] = gets.split().map(&:to_i)
	count += 1 
end

for value in 0...count-1

	for countH in 0...high[value]

		for countW in 0...wide[value]
			case countH%2
			when 0
				if countW > 0 && countW%2 != 0 
					print '.'
				else 
					print '#'
				end
			else
				if countW > 0 && countW%2 != 0 
					print '#'
				else 
					print '.'
				end
			end
		end
		puts ""
	end
	puts "\n"
end

Measured memory_bytes: 8736
# -*- coding: utf-8 -*-

import math

# 階乗しないで求める版
# 素数数え上げないで計算する版

x = int(input())

# 素数判定用関数
def is_prime_2(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False
    # 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step
    return True

# xまでの間にある素数を列挙
sosu_list = []
for i in range(x+1):
    if is_prime_2(i):
        sosu_list.append(i)

# 各素数毎に、数え上げないで計算する
sosu_cnt = {}
for sosu in sosu_list:
    i = sosu
    while i <= x:
        if sosu in sosu_cnt:
            sosu_cnt[sosu] += x // i
        else:
            sosu_cnt[sosu] = x // i
        i *= sosu

# 素数カウントを使って、約数の個数を求める
ans = 1
for key, value in sosu_cnt.items():
    sosu_cnt[key] += 1
    ans = (ans * sosu_cnt[key]) % (10 ** 9 + 7)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

const int N = 202;
int n, use[N];
string s[N];

void dfs(int node, int col, int ant) {
	use[node] = col;
	for(int i = 0; i < n; i++) {
		if(i == node || i == ant || s[node][i] == '0') continue;
		if(use[i] == use[node]) {
			cout << "-1\n";
			exit(0);
		}
		if(!use[i])
			dfs(i, 3 - col, node);
	}
}

int bfs(int node) {
	// dbg(node);
	memset(use, 0, sizeof use);
	queue <int> q;
	q.push(node);
	use[node] = 1;

	int d = 2;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		d = max(d, use[x]);
		for(int i = 0; i < n; i++) {
			if(s[x][i] == '0' || i == x) continue;
			if(!use[i])
				q.push(i), use[i] = use[x] + 1;
			else 
				assert(use[i] == use[x] + 1 || use[i] == use[x] - 1);
		}
	}
	return d;
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n;

	for(int i = 0; i < n; i++)
		cin >> s[i];
	
	dfs(0, 1, -1);

	int ans = 2;
	for(int i = 0; i < n; i++)
		ans = max(bfs(i), ans);
	cout << ans << '\n';
}	

	

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
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; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
#define pll pair<ll,ll>
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

ll a[220000];
int main(){
    ll n,k,ans=0;
    string s;
    cin>>s;
    ll tmp=0;
    rep(i,0,3){
        
        if(s[i]=='R')tmp++;
        else{ans=max(ans,tmp);tmp=0;}
    }
    ans=max(ans,tmp);
    cout<<ans;
}




Measured memory_bytes: 3592
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define  ll long long
#define size 200020
using namespace std;
ll a[size],q[size];
ll dp[size];
double slope(int j,int k) {
	double y=dp[j]+a[j]*a[j]-dp[k]-a[k]*a[k];
	double x=a[j]-a[k];
	return y/x;
}
int main()
{
	int n;
	ll c;
	while(cin>>n>>c){
		for(int i=1;i<=n;i++)
			cin>>a[i];
		dp[0]=0;
		int head=1,tail=1;
		q[head]=1;
		for(int i=2;i<=n;i++){
			while(head<tail&&slope(q[head],q[head+1])<=2*a[i]) head++;
			int j=q[head];
			dp[i]=dp[j]+c+(a[i]-a[j])*(a[i]-a[j]);
			while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) tail--;
			q[++tail]=i;
//			cout<<dp[i]<<endl;
		}
		cout<<dp[n]<<endl;
	}
}




Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int h[1000000];
int dp[1000000];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>h[i];
    }
    dp[1]=0;
    dp[2]=abs(h[1]-h[2]);
    for(int i=3; i<=n; i++)
    {
        dp[i]=999999999LL;
        for(int j=i-1; j>=max(1LL,i-k); j--)
        {
            dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));

        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 5120
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,A,B=map(int,input().split())
    if A>B:
        print(0)
    elif N==1:
        if A!=B:
            print(0)
        else:
            print(1)
    elif N>=2:
        res=N-2
        print(B*res-A*res+1)


resolve()

Measured memory_bytes: 38384
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
const int INF=1e9+7;
const int mod=1e9+7;
struct poi{
	int X;int Y;int Z;
  bool operator<(const poi&R)const{
		return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
	}
};
//
//ACACACACACACACACACACACAC//
//WAWAWAWAWAWAWAWAWAWAWAWA//
//CECECECECECECECECECECECE//
//RERERERERERERERERERERERE//
//TLETLETLETLETLETLETLETLE//
//
ll DP[51][51][3000];
int main(){
	ll N,A;
	ll X[50];
	cin>>N>>A;
	FOR(i,0,N){
		cin>>X[i];
	}
	DP[0][0][0]=1;
	FOR(i,0,N){
		FOR(j,0,N){
			FOR(k,0,3000){
				if(DP[i][j][k]==0){
					continue;
				}else{
					DP[i+1][j+1][k+X[i]]+=DP[i][j][k];
					DP[i+1][j][k]+=DP[i][j][k];
				}
			}
		}
	}
	ll ans=0;
	FOR(i,1,N+1){
		ans+=DP[N][i][i*A];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 58112
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> P;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll modpow(ll a,ll n){
  if(n==0)return 1;
  if(n%2==0){
    ll t=modpow(a,n/2);
    return (t*t)%MOD;
  }
  return a*modpow(a,n-1)%MOD;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n;
  cin >> n;
  vector<int>sum1(n+1,0),sum2(n+1,0);
  rep(i,n){
    int a;
    cin >> a;
    sum1[i+1]=sum1[i]+a;
  }
  rep(i,n){
    int a;
    cin >> a;
    sum2[i+1]=sum2[i]+a;
  }
  int ans=0;
  rep(i,n){
    ans=max(sum1[i+1]-sum1[0]+sum2[n]-sum2[i],ans);
  }
  cout << ans << endl;
  return 0;     
}


Measured memory_bytes: 256
M;s;x[101];i;n;main(a){for(;~scanf("%d",&a);x[i++]=a)n?s+=a:(n=a);for(M=s%10?s:0,i=0;i++<n;)M=fmax(M,(s-x[i])%10?s-x[i]:0);printf("%d",M);}

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

void f(vector<int> &x) {
  int can = 0;
  for (int i = 0; i < 10; i++) {
    if (x.at(i + 1) == -9) {
      can = i;
      break;
    }
    else {
      if (abs(x.at(i) + 1 - x.at(i + 1)) <= 1 && x.at(i) < 9) {
        can = i;
        break;
      }
    }
  }
  
  if (x.at(can) == 9) can++;
  if (x.at(can) == -9) x.at(can) = 1;
  else x.at(can)++;
  for (int i = can - 1; i >= 0; i--) {
    x.at(i) = max(0, x.at(i + 1) - 1);
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int k;
  cin >> k;
  
  vector<int> x(11, -9);
  x.at(0) = 1;
  
  for (int i = 1; i < k; i++) {
    f(x);
    /*for (int j = 10; j >= 0; j--) {
      if (x.at(j) >= 0) cout << x.at(j);
    }
    cout << endl;*/
  }
  
  for (int i = 10; i >= 0; i--) {
    if (x.at(i) >= 0) cout << x.at(i);
  }
  cout << '\n';
}

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

using namespace std;

const double PI = 3.141592653589;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define int long long
#define all(c) (c).begin(),(c).end()
#define M 1000000007
#define INF LLONG_MAX
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ", "; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
// Use pr(a,b,c,d,e) or cerr<<anything or prc(v.begin(),v.end()) or prc(v,v+n)
//  

int f(int h)
{
    if(h == 1) return 1;
    else if(h == 0) return 0;
    else return 1+ 2*f(h/2);
}

int32_t main()
{
    fastio;
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    int h;
    cin >> h; 
    int ans = f(h);
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>          // printf(), getc(), scanf()
#include <ctype.h>          // isdigit()

#define MAX_N 100000

int
main(int argc, char** argv)
{
	int n, q;
	int a[MAX_N];
	int c;
	int i;

	scanf("%d %d", &n, &q);
	c = getc(stdin);
	for (i = 0; i < n; ++i)
	{
		while (c == ' ' || c == '\n')
			c = getc(stdin);

		int d = 0;
		while (isdigit(c))
		{
			d = d * 10 + c - '0';
			c = getc(stdin);
		}

		a[i] = d;
	}

	for (i = 0; i < q; ++i)
	{
		while (c == ' ' || c == '\n')
			c = getc(stdin);

		long x = 0;
		while (isdigit(c))
		{
			x = x * 10 + c - '0';
			c = getc(stdin);
		}

		long count = 0;
		long sum = 0;
		int s, t;
		for (s = 0, t = 0; s < n; ++s)
		{
			sum += a[s];
			while (sum > x)
				sum -= a[t++];

			count += s - t + 1;
		}

		printf("%ld\n", count);
	}

	return 0;
}

Measured memory_bytes: 984