akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define PER(i, x, y) for(ll i = x; i > y; i--)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

int main() {
    ll H, W, N;
    cin >> H >> W >> N;
    ll X[N], Y[N];
    REP(i, 0, N) {
        cin >> X[i] >> Y[i];
    }
    plglg pt[N + 1];
    REP(i, 0, N) {
        pt[i] = plglg(Y[i] - 1, X[i] - 1);
    }
    pt[N] = plglg(inf, inf);
    sort(pt, pt + N);
    ll num[W];
    fill(num, num + W, H - 1);
    ll h = 0;
    num[0] = 0;
    REP(i, 1, W) {
        h++;
        if (h >= H) {
            num[i] = -1;
            continue;
        }
        ll id = lower_bound(pt, pt + N + 1, plglg(i, h)) - pt;
        while (1) {
            if (pt[id].first != i || pt[id].second != h) {
                num[i] = h;
                break;
            } else {
                h++;
                id++;
                if (h >= H) {
                    num[i] = -1;
                    break;
                }
            }
        }
    }
    // REP(i, 0, W) {
    //     cout << num[i] << " ";
    // }
    // cout << endl;
    ll ans = H;
    REP(i, 0, N) {
        plglg p = pt[i];
        ll x = p.first;
        ll y = p.second;
        if (y > num[x] && num[x] != -1) {
            ans = min(ans, y);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 8064
#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		priority_queue< int, vector<int>, greater<int> >pq;
		int a;
		for (int i = 0; i < n; i++) {
			cin >> a;
			pq.push(a);
		}
		int counter = 0;
		int counter2 = 0;
		while (!pq.empty()) {
			a = pq.top();
			pq.pop();
			counter2 += a;
			counter += counter2;
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
#define MAX 7777777
bool u[MAX];
int main(){
  int m,n;
  while(cin>>m>>n,m||n){
    memset(u,0,sizeof(u));
    int i,j,k=m;
    for(i=0;i<n;i++){
      while(u[k]) k++;
      for(j=k;j<MAX;j+=k) u[j]=1;
    }
    for(;u[k];k++);
    cout<<k<<endl;
  }
  return 0;
}

Measured memory_bytes: 10680
#include <iostream>
#include <vector>
using namespace std;
 
int main(){
	int N, M, C;
	cin >> N >> M >> C;
	vector<int> B(M);
	vector<vector<int>> A;

	for(int i=0;i<M;i++){
		cin >>B[i];
	}
	for(int i = 0;i<N;i++){
		vector<int> IN(M);
		for(int j=0;j<M;j++){
			cin >> IN[j];
		}
		A.push_back(IN);
	}
	int count = 0;
	for(int i=0;i<N;i++){
		int sum = 0;
		for(int j=0;j<M;j++){
			sum += A[i][j] * B[j];
		}
		sum += C;
		if(sum > 0) count++;
	} 
	cout << count << endl;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
b = 0
ans = 0

for i in range(n-1):
    if a[i] < a[i+1]:
        b = 0
        continue
    b += 1
    ans = max(b,ans)

print(ans)

Measured memory_bytes: 14172
#pragma GCC optimize("trapv")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using ld = long double;
const int maxn = 5e2 + 10, mlg = 17, mod = 1e9 + 7;
ll n, k;
vi a;
ll z = 0;
ll floor(ll x, ll i) {
	if(i<0) x*=-1, i*=-1;
	if(x>0) return x/i;
	x = abs(x);
	x = (x+i-1)/i;
	return -x;
}
ll ceil(ll x, ll i) {
	if(i<0) x*=-1, i*=-1;
	if(x<0) return x/i;
	return (x+i-1)/i;
}
ll count(ll x) {
	ll ans = 0;
	for(auto i : a) {
		if(i<0) {
			ans += a.end()-lower_bound(all(a), ceil(x, i));
		} else {
			ans += upper_bound(all(a), floor(x, i))-a.begin();
		}
		if(i*i<=x) ans--;
	}
	ans/=2;
	if(x>=0) {
		ans += z*(z-1)/2;
		ans += z*(n-z);
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int t, i = 0; i < n; i++) {
		cin >> t;
		if(t==0)z++;
		else a.pb(t);
	}
	sort(all(a));
	ll ans = -(1ll<<60);
	for(ll z = 1ll<<62; z>>=1;)
		if(count(ans+z)<k)
			ans += z;
	cout << ans+1;
	return 0;
}


Measured memory_bytes: 2420
import sys

N=int(input())
sys.setrecursionlimit(100000)
u = [0]*(N-1)
v = [0]*(N-1)
w = [0]*(N-1)
for i in range(N-1):
    u[i], v[i], w[i] = map(int, input().split())
    u[i] -= 1
    v[i] -= 1

class Path:
    def __init__(self, next_node, length, num):
        self.next=next_node
        self.len=length
        self.num=num

class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []

    def append(self, next_node, length, num):
        self.paths.append(Path(next_node, length, num))

nodes = [Node(i) for i in range(N)]
for i in range(N-1):
    nodes[u[i]].append(v[i], w[i], i)
    nodes[v[i]].append(u[i], w[i], i)

past_paths = [0]*(N-1)
paints = [-1]*N

def rec(pos, color):
    if paints[pos] == -1:
        paints[pos] = color
    for path in nodes[pos].paths:
        # まだ通ってない道を通る
        if past_paths[path.num] == 0:
            past_paths[path.num] = 1
            rec(path.next, (color + path.len) % 2)
        # さっきの道を戻ってくる

rec(0, 0)

for i in paints:
    print(i)


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

int main()
{
  char c[4];
  rep(i,4) cin >> c[i];
  for(int i=1; i<4; ++i)
  {
    if(c[i-1]==c[i])
    {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
  return 0;
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[100005];

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }
    ll g = A[0];
    REP(i, N) {
        g = gcd(g, A[i]);
    }
    cout << g << endl;
    return 0;
}

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

int main(){
  int N,K,a=0,b=0;cin >> N >>K;
  vector<int> vec(N),ans(N-K+1);
  for(int i=0;i<N;i++){
    cin >> vec.at(i);
  }
  for(int i=0;i<K;i++){
    a +=vec.at(i);
  }
  ans.at(0)=a;
   for(int i=0;i<N-K;i++){
     a+=vec.at(i+K);
     a-=vec.at(i);
     ans.at(i+1)=a;
   }
   for(int i=0;i<N-K+1;i++){
     b = max(b,ans.at(i));
   }
  double c;
  c=b+K;
  cout << fixed << setprecision(1);
    cout << c/2 << endl;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(void) {
	long long a[5], p, b,q=5;

	cin >> p;
	cin >> b;
	for (int i = 1; i < 5; i++) {
		cin >> a[i];
		
		if (b > a[i]){
			b = a[i];
		}
	}

	q = q+p / b;
	if (p%b == 0) {
		cout << q-1 << endl;
	}
	else {
		cout << q << endl;
	}

	return 0;


}

Measured memory_bytes: 256
n = int(input())
xyhs = [list(map(int, input().split())) for _ in range(n)]
ans_cx = 0
ans_cy = 0
ans_h = 0

if n == 1:
    ans_cx, ans_cy, ans_h = xyhs[0]
elif all([xyh[2] == 0 for xyh in xyhs]):
    ans_cx = 0
    ans_cy = 0
    for x, y, h in xyhs:
        ans_cx += x
        ans_cy += y
    ans_cx //= n
    ans_cy //= n
    ans_h = abs(xyhs[0][0] - ans_cx) + abs(xyhs[0][1] - ans_cy)
else:
    for cx in range(101):
        for cy in range(101):
            h_set = set([h + abs(x - cx) + abs(y - cy) for x, y, h in xyhs if h != 0])
            if len(h_set) > 1:
                continue
            h_ = list(h_set)[0]
            if all([max(h_ - abs(x - cx) - abs(y - cy), 0) == h for x, y, h in xyhs]):
                ans_cx = cx
                ans_cy = cy
                ans_h = h_

print(ans_cx, ans_cy, ans_h)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  ll N;
  cin >> N;
  if(N%2==1) {
    cout << 0 << endl;
    return 0;
  }
  ll k = 1;
  ll ans = 0;
  while(1) {
    ll n = pow(5,k) * 2;
    ll cnt = N/n;
    if(cnt==0) break;
    ans += cnt;
    k++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
const double PI  =3.141592653589793238463;
using namespace std;
using ll = long long;
const ll INF = +10010010000;
typedef pair<int,int> P;
const int mod = 1e9+7;

struct mint{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a){
        (x+=a.x)%=mod;
        return *this;
    }
    mint& operator-=(const mint a){
        (x-=mod-a.x)%=mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x *= a.x)%= mod;
        return *this;
    }
    mint operator+(const mint a)const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a)const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a)const{
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
      if(!t)return 1;
      mint a = pow(t>>1);
      a*=a;
      if(t%1)a*=*this;
      return a;
    }

    // for prime mod
    mint inv() const {
      return pow(mod-2);
    }
    mint& operator/=(const mint a){
      return (*this) *= a.inv();
    }
    mint operator/(const mint a)const{
      mint res(*this);
      return res/=a;
    }
};

struct combination{
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1){
    fact[0] = 1;
    for(int i = 1; i<n;++i)fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i>=1;--i) ifact[i-1] = ifact[i] * i;
  }
  mint operator()(int n, int k){
    if(k<0 || k>n)return 0;
    return fact[n] * ifact[k] + ifact[n-k]; 
  }
};


int main(){
    int n;cin >> n;
    vector<int> a(n),ans(n,0);
    rep(i,n)cin >> a[i];
    int s=0;
    rep(i,n)s^=a[i];
    rep(i,n){
        int tmp = s^a[i];
        cout << tmp << endl;
    }
    return 0;

}

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

using namespace std;

template<class T>
struct Graph {
	struct Vertex {
		T cost;
		Vertex(T v1) : cost(v1) {}
		Vertex() {}
	};
	struct Edge {
		int to;
		T cost;
		Edge(int t, T c) : to(t), cost(c) {}
		Edge() {}
	};
	int sz;
	vector<Vertex> v;
	vector<vector<Edge>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = Vertex(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Dijkstra : public Graph<T> {
	Dijkstra(int n) : Graph<T>(n) {}
	void Dijkstra_solve(int start, T INF_COST) {
		auto& v = this->v;
		auto& e = this->e;
		for (auto& vv : v) vv.cost = INF_COST;
		using Q_T = pair<T, int>;
		priority_queue<Q_T, vector<Q_T>, greater<>> q;
		q.emplace(0, start);
		while (!q.empty()) {
			auto a = q.top();
			q.pop();
			if (a.first >= v[a.second].cost) continue;
			v[a.second].cost = a.first;
			for (auto& p : e[a.second]) {
				if (p.cost == INF_COST) continue;
				if (a.first + p.cost < v[p.to].cost) q.emplace(a.first + p.cost, p.to);
			}
		}
	}
};

void SoundHound2018_D() {
	int N, M, s, t;
	cin >> N >> M >> s >> t;
	s--;t--;
	Dijkstra<long long> G(N), G2(N);
	for (int i = 0; i < M; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--;b--;
		G.add_edge(a, b, c);
		G.add_edge(b, a, c);
		G2.add_edge(a, b, d);
		G2.add_edge(b, a, d);
	}
	G.Dijkstra_solve(s, LLONG_MAX);
	G2.Dijkstra_solve(t, LLONG_MAX);
	vector<long long> ans(N);
	for (int i = 0; i < N; i++) {
		ans[i] = G.v[i].cost + G2.v[i].cost;
	}
	for (int i = N - 1; i > 0; i--) {
		ans[i-1] = min(ans[i], ans[i-1]);
	}
	for (int i = 0; i < N; i++) {
		cout << (long long) 1e15 - ans[i] << endl;
	}
}

int main() {
	SoundHound2018_D();
}

Measured memory_bytes: 19000
#include<iostream>
#include <string>
#include<vector>
#include <algorithm>
#include <set>

using namespace std;

int N;
int P[100005];
vector<int> R[100005], L[100005];

set<int> S, T;

int INF = 999999;

int tmp[10];

int main(void) {

	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> P[i];
	}

	vector<int >Z;

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

		Z.clear();

		for (auto y : S) {
			if (y < P[i]) {
				//cout << "y= " << y << endl;
				R[y].push_back(i);
				if (R[y].size() >= 2) { Z.push_back(y);  }
			}
			else {
				break;
			}
		}

		for (int h = 0; h < (int)Z.size(); h++) { S.erase(Z[h]); }
		S.insert(P[i]);
	}

	for (int i = 1; i <= N; i++) {
		while (R[i].size() < 2) { R[i].push_back(INF); }
	}


	/*for (int i = 1; i <= N; i++) {
		cout <<"i= "<< i <<"   ";   for (auto y : R[i]) { cout <<" "<< y ; }
		cout << endl;
	}*/

	S.clear();

	

	for (int i = N; i >= 1; i--) {
		
		Z.clear();
		
		for (auto y : S) {
			
			if (y < P[i]) {
				L[y].push_back(i);
				if (L[y].size() >= 2) { Z.push_back(y); }
			}else{ break; }
		}

		for (int h = 0; h < (int)Z.size(); h++) { S.erase(Z[h]); }
		
		S.insert(P[i]);
	}


	for (int i = 1; i <= N; i++) {
		while (L[i].size() < 2) { L[i].push_back(-INF); }
	}

	/*for (int i = 1; i <= N; i++) {
		cout << "i= " << i << "   ";   for (auto y : L[i]) { cout << " " << y; }
		cout << endl;
	}*/


	long long int ans = 0;

	for (int k = 1; k <= N; k++) {

		int val = P[k];
		int j = min(R[val][0],N+1);
		int q = min(R[val][1],N+1);
		int i = max(L[val][0],0);
		int p = max(L[val][1],0);

		//cout << "p= " << p << " i= " << i << " j= " << j << " q= " << q << endl;
		
		if (j <= N) {
			ans += (long long int)(k - i)*(q - j)*val;
		}

		//cout << "ans=  " << ans << endl;
		
		if (i >= 1) {
			ans += (long long int)(i - p)*(j - k)*val;
		}

		//cout << "ans=  " << ans << endl;

	}

	cout << ans << endl;


	
	/*for (int i = 1; i <= N-1; i++) {
		for (int j = i + 1; j <= N; j++) {
			vector<int > V;
			for (int k = i; k <= j; k++) {
				V.push_back(P[k]);
			 }
			sort(V.rbegin(), V.rend());
			tmp[V[1]] += V[1];
		}
	}

	for (int i = 1; i <= 8; i++) {
		cout << "tmp[" << i << "]= " << tmp[i] << endl;
	}*/
	
	return 0;
}

Measured memory_bytes: 15872
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,a[100002];
long long s1[100002],s2[100002],s,ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		s1[i]=s1[i-1]+a[i];
		s2[i]=s2[i-1]+max(0,a[i]);
	}
	ans=max(s1[n]-s1[n-k],0ll)+s2[n-k];
	for(int i=n;i>k;i--)
	{
		s+=max(0,a[i]);
		ans=max(ans,s2[i-k-1]+max(s1[i-1]-s1[i-k-1],0ll)+s);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 2176
n = gets.chomp.to_i
ary = []
n.times do
    ary << gets.chomp.split.map(&:to_i)
    ary[-1][2] = ary[-1][0] + ary[-1][1]
end

ary.sort! {|a, b| b[2] <=> a[2]}

ans = 0
n.times do |i|
    if i%2 == 0
        ans += ary[i][0]
    else
        ans -= ary[i][1]
    end
end
puts ans

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

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    int s1 = 0, s2 = 0, s3 = 0;
    for(int i = 0; i < n; i++){
        int p;
        cin >> p;
        if(p <= a) s1++;
        if(p > a && p <= b) s2++;
        if(p > b) s3++;
    }
    cout << min({s1, s2, s3}) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
		   int n;
           cin>>n;
           int a,b;
           cin>>a>>b;
           cout<<(n*a<b ? n*a:b)<<endl;
}

Measured memory_bytes: 3576
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int N=300;
int n;
int hav[4];
double dp[N+1][N+1][N+1];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		hav[x]++;
	}
	for(int k=0;k<=n;k++)for(int j=0;j<=n;j++)for(int i=0;i<=n;i++)if(i+j+k&&i+j+k<=n){
		double x=(i?1.*i/n*dp[i-1][j][k]:.0)+(j?1.*j/n*dp[i+1][j-1][k]:.0)+(k?1.*k/n*dp[i][j+1][k-1]:.0);
		double y=1.*(i+j+k)/n;
		dp[i][j][k]=1./y*x+1./y;
//		printf("dp[%d][%d][%d]=%.5lf\n",i,j,k,dp[i][j][k]);
	}
	printf("%.100lf",dp[hav[1]][hav[2]][hav[3]]);
	return 0;
}
/*1
3
1 1 1
*/
/*2
1
3
*/
/*3
2
1 2
*/
/*4
10
1 3 2 3 3 2 3 2 1 3
*/

Measured memory_bytes: 213376
#include<stdio.h>
int main(void){
  int A1,A2,A3;
  scanf("%d",&A1);
  scanf("%d",&A2);
  scanf("%d",&A3);
  if(A1+A2+A3<=21){
    printf("win");
  }
  else{
    printf("bust");
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main() {
  ll N;
  scanf("%lld", &N);
  ll ans = 0;
  
  ll base = N/11;
  N = N%11;
  if(N<=6 && N!=0) ++ans;
  else if(N==0);
  else ans += 2;

  cout << ans + base*2 << endl;



}



Measured memory_bytes: 256
def nCr(n, r):
    r = min(r, n-r)
    numerator=1
    for i in range(n,n-r,-1):
        numerator*=i
    denominator=1
    for i in range(r,1,-1):
        denominator*=i
    return numerator//denominator
n,p=map(int,input().split())
a,b,e,o=list(map(int,input().split())),0,0,0
for i in range(len(a)):
    if a[i]%2==0:
        e+=1
    else:
        o+=1
for i in range((o-p)//2+1):
    b+=nCr(o,p+2*i)
print(b*(2**e))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
int ar[200005]={0},boll[200005]={0};
int main(){
  int n;
  cin>>n;
  vector<int> ans;
  for(int i=1;i<=n;i++){
    int a;
    cin>>a;
    ar[i]=a;
  }
  int pos=n;
  for(;pos>(n/2);pos--){
    boll[pos]=ar[pos];
    if(ar[pos]==1) ans.push_back(pos);
  }
  for(;pos>0;pos--){
    int rsum=0;
    for(int i=pos*2;i<=n;i+=pos){
      rsum+=boll[i];
    }
    rsum%=2;
  //  cout<<pos<<" "<<rsum<<" "<<ar[pos]<<endl;
    if(rsum!=ar[pos]){
      boll[pos]++;
      ans.push_back(pos);
    }
  }
  cout<<ans.size()<<endl;
  for(int i=0;i<ans.size();i++) cout<<ans[i]<<(i==ans.size()-1?"\n":" ");
}


Measured memory_bytes: 2936
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<tgmath.h>
#include<stdbool.h>
#include<sys/queue.h>
#include<time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

const ll mod = 1000000007ll;

ll n, a, b, ans = 1, tmp = 2;

ll power(ll x, ll y){
    if(y == 0ll)return 1ll;
    ll res = 1, tmp = x;
    while(y){
        if(y&1){
            res *= tmp;
            res %= mod;
        }
        tmp *= tmp;
        tmp %= mod;
        y >>= 1;
    }
    return res;
}

ll COM(ll x, ll y){
    if(x < y) return 0;
    if(x < 0 || y < 0) return 0;
    ll res = 1;
    for(int i=0; i<y; i++){
        res *= x - i;
        res %= mod;
        res *= power(y-i, mod-2);
        res %= mod;
    }
    return res;
}

main(){
    scanf("%lld%lld%lld", &n, &a, &b);
    ans = power(2, n) - 1;
    ans += 2*mod - COM(n, a) - COM(n, b);
    ans %= mod;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 128
n = int(input())
count = 0

for i in range(n):
  d1,d2 = map(int,input().split())
  if(d1 == d2):
    count += 1
  else:
    count = 0
  if(count == 3):
    print("Yes")
    break

if(count != 3):
  print("No")


Measured memory_bytes: 9192
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int x=n/100;
    int y=(n%100-n%10)/10;
    int z=n%10;
    if(x==1){x=9;}
    else{x=1;}
    if(y==1){y=9;}
    else{y=1;}
    if(z==1){z=9;}
    else{z=1;}
    cout<<x<<y<<z<<endl;
    return 0;}

Measured memory_bytes: 256
N = int(input().rstrip())
Ss = []
for _ in range(N):
    Ss.append(input().rstrip())
# print(Ss)
print(f'AC x {Ss.count("AC")}')
print(f'WA x {Ss.count("WA")}')
print(f'TLE x {Ss.count("TLE")}')
print(f'RE x {Ss.count("RE")}')


Measured memory_bytes: 16264
#include<iostream>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
int main()
{
    ll n,r;
    cin>>n>>r;
    if(n>=10)
    cout<<r<<endl;
    else
    cout<<(10-n)*100+r<<endl;;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
    char x[1001];
    while(1){
        scanf("%s",&x);
        if (x[0] == '0')break;
        int sum = 0;
        for (int i = 0; i < strlen(x); i++)
        {
            sum += (x[i] - '0');
        }
        printf("%d\n",sum);
    }
return 0;
}


Measured memory_bytes: 2760
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>
 
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;
 


int main(){
  string s;
  cin >> s;
  int res = 0;
  rep(i, 3){
    if(s[i] == 'R'){
      if(i > 0 && s[i - 1] == 'S')res = 0;
      res++;
    }
  }
  
  cout << res << endl;
}
 

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, E, T, r;
int a[maxn];
ll Min1, Min2 = 1e18, f[maxn];
int main()
{
	multiset<ll> S; 
	scanf("%d%d%d", &n, &E, &T);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	S.insert(0);
	for(int i = 1; i <= n; ++i)
	{
		while((a[i] - a[r + 1]) * 2 >= T)
		{
			Min2 = min(Min2, f[r] - 2 * a[r + 1]);
			S.erase(S.find(f[r]));
			++r;
		}
		f[i] = min(Min1 + 1ll * i * T, Min2 + 2 * a[i]);
		if(!S.empty()) f[i] = min(f[i], *S.begin() + T);
		Min1 = min(Min1, f[i] - 1ll * i * T);
		S.insert(f[i]); 
	}
	printf("%lld\n", f[n] + E);
	return 0;
}

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

template<typename T, typename U> void cmax(T &a, U b) { if (a < b) a = b; }
template<typename T, typename U> void cmin(T &a, U b) { if (a > b) a = b; }

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  long a = LONG_MIN, b = LONG_MAX;
  long c = LONG_MIN, d = LONG_MAX;
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    cmax(a, x + y);
    cmin(b, x + y);
    cmax(c, x - y);
    cmin(d, x - y);
  }
  cout << max(a - b, c - d) << "\n";
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define REP(i,i_len) for (ll i = 0, i##_len = (i_len); i < i##_len; i++)
#define ALL_OF(v) (v).begin(), (v).end()

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    while (cin >> n >> m, n) {

        vector<ll> h(n), w(m);
        REP(i, n) cin >> h[i];
        REP(i, m) cin >> w[i];
        
        vector<ll> himos(n+1), wimos(m+1);
        wimos[0] = himos[0] = 0;
        REP(i, n) himos[i+1] = himos[i] + h[i];
        REP(i, m) wimos[i+1] = wimos[i] + w[i];

        vector<ll> hs, ws;
        hs.reserve(n * (n-1) / 2);
        ws.reserve(m * (m-1) / 2);
        REP(i, n+1) REP(j, i) hs.push_back(himos[i] - himos[j]);
        REP(i, m+1) REP(j, i) ws.push_back(wimos[i] - wimos[j]);
        sort(ALL_OF(hs));
        sort(ALL_OF(ws));
        // for (ll h : hs) cerr << h << " "; cerr << "\n";
        // for (ll w : ws) cerr << w << " "; cerr << "\n";
        ll ans = 0;
        for (ll i = 0, j = 0, hl = hs.size(), wl = ws.size(); i < hl && j < wl; ) {
            if (hs[i] == ws[j]) {
                ll ip = i, jp = j;
                while (i < hl && hs[i] == hs[ip]) i++;
                while (j < wl && ws[j] == ws[jp]) j++;
                // cerr << i - ip << " x " << j - jp << " = " << (i - ip) * (j - jp) << endl;
                ans += (i - ip) * (j - jp);
            } else if (hs[i] > ws[j]) {
                j++;
            } else {
                i++;
            }
        }
        // cerr << "[ANS] ";
        cout << ans << endl;
    }

}


Measured memory_bytes: 38076
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, K = LI()
    A = LI()
    cumsum = [0] * (N+1)
    c = collections.defaultdict(list)
    memo = [0] * (N+1)
    c[0].append(0)
    for i in range(N):
        # cumsum[i] ... [0, i)
        cumsum[i+1] = (cumsum[i] % K + A[i]) % K
        val = (cumsum[i+1] - (i+1)) % K
        memo[i+1] = val
        c[val].append(i+1)
    # print(cumsum)
    # print(memo)
    # print(c)
    ans = 0
    for i in range(N+1):
        val = memo[i]
        l_ix = bisect.bisect_right(c[val], i)
        r_ix = bisect.bisect_right(c[val], i + (K-1))
        # print('i: {}, memo[i]: {}, c[val]: {}, l_ix: {}, r_ix: {}'.format(i, memo[i], c[val], l_ix, r_ix))
        ans += r_ix - l_ix
    # for i in range(N):
    #     if A[i] % K == 1:
    #         ans += 1
    print(ans)
main()



Measured memory_bytes: 144768
#include <cstdio>
#include <iostream>

#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>

using namespace std;

#define MAX_N 100
int S[MAX_N];

int main() {

  // -----------------------------
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  // input
  int N;
  cin >> N;

  string S;
  cin >> S;
  
  string s, t;
  s = "";
  t = "";

  if (N%2 != 0) {
    cout << "No" << endl;
    return 0;
  }
  
  int n = N/2;
  
  for(int i = 0; i < n; i++){
    s = s + S[i];
    t = t + S[i + n];
  }
  
  if (s == t) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int n,i,min,max;
	long int sum=0;
	int data[10000];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&data[i]);
		sum +=data[i];
	}
	max = data[0];
	min = data[0];
	for(i=1;i<n;i++){
		if(max<=data[i]){
			max = data[i];
		}
		if(min>=data[i]){
		min = data[i];
		}
	}
	printf("%d %d %ld\n",min,max,sum);
}

Measured memory_bytes: 1064
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define int long long
#define INF 1e9 + 7
#define cae cout << ans << endl;
#define cye cout << "Yes" << endl;
#define cne cout << "No" << endl;
#define r0 return 0;
#define ll long long
using namespace std;
typedef pair<int, int>P;
signed main() {
    int n;
    int l[1000], r[1000];
    int ans = 0;
    cin >> n;
    rep(i, n) {
        cin >> l[i] >> r[i];
        ans += r[i] - l[i] + 1;
    }
    cae
    r0
}


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

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

    int n; cin >> n;
    string S; cin >> S;
    int len = S.size();

    vector<vll> dp(n + 1, vll(n + 1, 0));
    dp[0][0] = 1;

    rep(i, n){
        rep(j, n){
            int cur = dp[i][j];
            if(cur == 0) continue;
            
            dp[i + 1][j + 1] = ADD(dp[i + 1][j + 1], 2 * cur, mod);
            dp[i + 1][max(0, j - 1)] = ADD(dp[i + 1][max(0, j - 1)], cur, mod);
        }
    }

    ll res = 1;
    rep(i, len) res = MUL(res, 2, mod);
    cout << DIV(dp[n][len], res, mod) << endl;

    return 0;
}


Measured memory_bytes: 195840
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,srt,end) for(long long i=(srt); i<(long long)(end); i++) 
ll N;
int main(){
    vector<ll> A(9,0);
    rep(i,0,9)cin>>A[i];
    cin>>N;
    vector<ll> b(N,0);
    rep(i,0,N)cin>>b[i];
    rep(i,0,9){
        rep(j,0,N){
            if(A[i]==b[j])A[i]=0;
        }
    }
    //bingo (0,1,2)(3,4,5)(6,7,8) (0,3,6)(1,4,7)(2,5,8) (0,4,8)(2,4,6)
    if(A[0]==A[1]&&A[1]==A[2]||A[3]==A[4]&&A[4]==A[5]||A[6]==A[7]&&A[7]==A[8]
     ||A[0]==A[3]&&A[3]==A[6]||A[1]==A[4]&&A[4]==A[7]||A[2]==A[5]&&A[5]==A[8]
     ||A[0]==A[4]&&A[4]==A[8]||A[2]==A[4]&&A[4]==A[6])
        cout<<"Yes";
    else
       cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pye cout << "yes" << endl
#define pno cout << "no" << endl
#define pYe cout << "Yes" << endl
#define pNo cout << "No" << endl
#define pYE cout << "YES" << endl
#define pNO cout << "NO" << endl
#define prin(num) cout << num << endl
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 1000005
#define NIL -1
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PA;
typedef priority_queue<ll> PQ;
typedef pair<double, double> doup;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef map<ll, ll> Map;

vector<ll> v
;
void fact(ll n) {
    ll i;
    for(i=1; i*i<=n; i++) {
        if(n%i==0) {
            v.push_back(i);
            
            if(i*i!=n)
                v.push_back(n/i);
        }
    }
}

int main(void) {
    ll N, M;
    cin >> N >> M;
    ll i;
    
    fact(M);
    sort(v.begin(), v.end());
    
    
    for(i=0; i<v.size(); i++) {
        if(N<=v[i]) {
            prin(M/v[i]);
            return 0;
        }
        
    }
    
}

Measured memory_bytes: 256
#include<cstdio>
#define min(a,b) a<b?a:b
typedef long long LL;
int main()
{
	LL a,b,T,ans=0;
	bool flag=0;
	LL mi=1111111111;
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld%lld",&a,&b);
		if(a!=b) flag=1;
		ans+=a;
		if(a>b)
			mi=min(b,mi);
	}
	if(!flag)
		ans=mi;
	printf("%lld",ans-mi);
}//

Measured memory_bytes: 256
/*May The Force Be With Me*/
#include <bits/stdc++.h>
#include <stdio.h>
#include <ctype.h>
#pragma GCC optimize ("Ofast")
#define ll long long
#define MOD 1000000007
#define endl "\n"
#define vll vector<long long>
#define mll map<long long,long long>
#define pll pair<long long, long long>
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define pb push_back
#define f first
#define s second
#define inf INT_MAX
#define size_1d 10000000
#define size_2d 1000
//Snippets: delta, sieve, fastexp, dfs, bfs, dijkstra, floodfill

using namespace std;

ll n;

void Input() {
	cin >> n;
}

void Solve() {
	string ans = "";
	while (n > 0) {
		n--;
		ans += 'a' + n % 26;
		n /= 26;
	}
	reverse(all(ans));
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll T = 1;
	//cin >> T;
	//ll t = 1;
	while (T--) {
		Input();
		//cout << "Case " << t << ": ";
		Solve();
		//t++;
	}
	return 0;
}

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

using namespace std;

#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(0)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> matrix;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(c) c.begin(),c.end()
#define mp make_pair
#define pb push_back
#define f first
#define int ll
#define tcase int t; cin>> t; for( ; t; --t)
#define s second
#define endl '\n'
const int MAX = 1e6+1;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
double n;

int32_t main(){
	fastio;
	cin>> n;
	cout<< fixed<< setprecision(16)<< 2*PI*n<< endl;
	return 0;
}


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

int main(void){

    int N,ans=0;
    string S;
    cin >> N >> S;
    int len = S.size();
    
    for(int i=0;i<len-2;i++) if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') ans++;
    
    cout << ans << endl;
}

Measured memory_bytes: 3548
import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])




Measured memory_bytes: 54748
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
int main() {
ll rl=0;
ll lr=0;
ll r=0;
ll l=0;
ll f=0;
ll q=0;
string a;
cin>>a;
char b;
ll n=a.size();
ll aa[n]={};
for(ll i=0; i<n; i++){
if(a.at(i)=='R'){
r++;
}
else{
l++;
}
if(r>0&&l>0){
b=a.at(i);
rl=i;
for(int k=i+1; k<n; k++){
if(b!=a.at(k)){
lr=k;
i=k;
f++;  
break;}
else{
if(b=='R'){
r++;}
else{
l++;}}
}
if(f==0){q++;}
else f=0;
if(r%2==0){
aa[rl-1]+=r/2;
aa[rl]+=r/2;}
else{
aa[rl-1]+=r/2+1;
aa[rl]+=r/2;}
if(l%2==0){
aa[rl-1]+=l/2;
aa[rl]+=l/2;}
else{
aa[rl-1]+=l/2;
aa[rl]+=l/2+1;}
r=1;
l=0;}
if(q==1){
break;
}
}
for(ll i=0; i<n; i++){
cout<<aa[i]<<" ";}}


Measured memory_bytes: 1408
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;
const int IINF = 1e9;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

#define dump(x) cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl

void chmin(ll &a, ll b) {
  if (a > b) {
    a = b;
  }
}
void chmax(ll &a, ll b) {
  if (a < b) {
    a = b;
  }
}

int main() {
  string s;
  int q;
  cin >> s >> q;
  stack<char> front;
  stack<char> tail;
  bool swi = true;

  int ops;
  int f;
  char c;
  for (int i = 0; i < q; i++) {
    cin >> ops;
    if (ops == 1) {
      swi = !swi;
    } else {
      cin >> f >> c;
      if (f == 1) {
        if (swi) {
          front.push(c);
        } else {
          tail.push(c);
        }
      } else {
        if (swi) {
          tail.push(c);
        } else {
          front.push(c);
        }
      }
    }
  }

  if (swi) {
    string headString = "";
    while (front.size() > 0) {
      headString += front.top();
      front.pop();
    }
    string tailString = "";
    while (tail.size() > 0) {
      tailString += tail.top();
      tail.pop();
    }
    reverse(tailString.begin(), tailString.end());
    cout << (headString + s + tailString) << endl;
  } else {
    string headString = "";
    while (front.size() > 0) {
      headString += front.top();
      front.pop();
    }
    reverse(headString.begin(), headString.end());
    string tailString = "";
    while (tail.size() > 0) {
      tailString += tail.top();
      tail.pop();
    }
    reverse(s.begin(), s.end());
    cout << (tailString + s + headString) << endl;
  }
  return 0;
}

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

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

Measured memory_bytes: 3764
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define gcd __gcd
#define lcm(n, m) n * m / gcd(n, m)
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define so(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数

int main() {
  int N;
  ci(N);
  ve<int> d(N);
  rep(i, N){
    ci(d.at(i));
  }
  so(d);
  co(d.at(N / 2) - d.at(N / 2 - 1));
}

Measured memory_bytes: 640
def aux(s):
  return(s[1]*int(s[0]) + s[2:])

while True:
  try:
    s = input().strip()
    v = s.split('@')
    t = v[0]
    for i in (map(lambda x:aux(x), v[1:])):
      t += i
    print(t)

  except EOFError:
      break

Measured memory_bytes: 7616
#include <stdio.h>

int main()
{
	int j,i,n,ice[10],in;

	scanf("%d",&n);

	while(n != 0){
		for(i = 0; i < 10; i++){
			ice[i] = 0;
		}

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

		for(i = 0; i < 10; i++){
			if(ice[i] == 0){
				printf("-");
			}
			for(j = 0; j < ice[i]; j++){
				printf("*");
			}
			printf("\n");
		}

		scanf("%d",&n);
	}

	return 0;
}

Measured memory_bytes: 1000
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
  char s;
  cin >> s;
  if (isupper(s)) {
    cout << "A" << endl;
  } else {
    cout << "a" << endl;
  }
}

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

signed main()
{
  int N, P;

  while(cin >> N >> P, N || P) {
    
    int w = P, i = 0, have[55] = {0};
    while(1) {
      if(w) have[i]++, w--;
      else w += have[i], have[i] = 0;
      if(have[i] == P) { cout << i << endl; break; }
      i++; if(i == N) i = 0;
    }

  }

  return 0;
}

Measured memory_bytes: 2968
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#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() {

string s;
cin >> s;


int n=s.size();
bool kaibun=true;


for (size_t i = 0; i < s.size()/2; i++)
{
  if(s.at(i)!=s.at(n-1-i))
  kaibun=false;
}

//2こめ
for (size_t i = 0; i < (n-1)/2; i++)
{
  if(s.at(i)!=s.at((n-1)/2 -1-i))
  kaibun=false;
}
// ok cout << s.at((n-1)/2 -1)<<endl;

//3こめ

s=s.substr((n+3)/2-1);
for (size_t i = 0; i < s.size()/2; i++)
{
  if(s.at(i)!=s.at(s.size()-1-i))
  kaibun=false;
}
//cout << s << endl;

if(kaibun){cout << "Yes"<<endl;}
else{cout << "No"<<endl;}


}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
int main(){
    int n;
    while(cin>>n,n){
        long long S[4000]={0};
        int B[4000]={0},cnt=1;
        while(n--){
            long long n,m,o;
            cin>>n>>m>>o;
            S[n-1]+=m*o;
            if(B[n-1]==0){
                B[n-1]=cnt;
                cnt++;
            }

        }
        vector<pii>V;
        for(int i=0;i<4000;i++)
            if(S[i]>=1000000){
                V.push_back(pii(B[i],i));
            }
        sort(V.begin(),V.end());
        for(int i=0;i<V.size();i++)cout<<V[i].second+1<<endl;
        if(V.size()==0)cout<<"NA"<<endl;
    }
}

Measured memory_bytes: 1276
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vii;
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()

const int MOD = 1e9 + 7;
const int N = 10001;
const int D = 100;
char s[N];
int dp[N][D][2];

void add_self(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int d;
	scanf("%s%d", s, &d);

	int n = strlen(s);
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < d; j++) {
			int k = s[i] - '0';
			add_self(dp[i+1][(j+k)%d][0], dp[i][j][0]);
			for (int x = 0; x < k; x++)
				add_self(dp[i+1][(j+x)%d][1], dp[i][j][0]);
			for (int x = 0; x < 10; x++)
				add_self(dp[i+1][(j+x)%d][1], dp[i][j][1]);
		}
	}
	int answer = dp[n][0][0] + dp[n][0][1] - 1;
	if (answer < 0) answer += MOD;
	printf("%d\n", answer);
}


Measured memory_bytes: 8064
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
#include <cstdint>
using namespace std;
using LL = long long;

string S;
LL K;

LL splyu(string S) {
	S.push_back('*');
	char lc = S[0];
	LL ln = 0;
	vector<LL>vec;
	for (char c : S) {
		if (lc == c) {
			ln++;
		}
		else {
			vec.push_back(ln);
			ln = 1;
		}
		lc = c;
	}
	LL ans = 0;
	for (LL elm : vec) {
		ans += elm / 2;
	}
	return ans;
}

int main() {
	cin >> S >> K;
	set<char>s;
	for (char c : S) {
		s.insert(c);
	}
	if (s.size() == 1) {
		//全部同じ
		LL len = (LL)S.size() * K;
		cout << len / 2 << endl;
	}
	else {
		if (S[0] != S[S.size() - 1] || K == 1) {
			//最初と最後が違う、またはKが1
			auto ans = splyu(S);
			ans *= K;
			cout << ans << endl;
		}
		else {
			//最初と最後が一緒でKが2以上
			string T = S, U = S;
			char xx = S.front();
			while (U.front() == xx) {
				S.push_back(U[0]);
				U.erase(0, 1);
				T.push_back(S.front());
				S.erase(0, 1);
				S.size();
			}
			LL ta = splyu(T);
			LL ma = splyu(S);
			LL ua = splyu(U);
			LL ans = ta + ma * (K - 2) + ua;
			cout << ans << endl;
		}
	}
	return 0;
}

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

int min(int x, int y){
  if(x < y) return x;
  else return y;
}

int main(){
  int n;
  int sum = 0;
  std::cin >> n;

  int a[n];
  int b[n-1];
  for(int i=0; i < n-1; i++){
    std::cin >> b[i];
  }

  a[0] = b[0];
  sum += a[0];
  for(int i=1; i < n-1; i++){
    a[i] = min(b[i-1], b[i]);
    sum += a[i];
  }
  sum += b[n-2];

  std::cout << sum << "\n";

  return 0;
}


Measured memory_bytes: 256