akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#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 ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const ll mod = 7 * 17 * (1 << 23) + 1;
const ll inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, dp[100100], p[100100];
void bt(int x) {
	if(x==n) return;
	cout << p[x]-x << " ";
	bt(p[x]);
}
int main() { //DINIC ORZ
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	string s;
	cin >> s;
	int j = n;
	set<pair<int, int>> a;
	a.insert({0, n});
	for(int i = n; i--;) {
		if(s[i]=='1') continue;
		while(!a.empty()&&a.begin()->second>i+m) a.erase(a.begin());
		if(a.empty()) {
			p[i] = -1;
			continue;
		}
		dp[i] = a.begin()->first+1;
		p[i] = a.begin()->second;
		a.insert({dp[i], i});
	}
	if(p[0]==-1) return cout << -1, 0;
	bt(0);
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

const int MOD = 1e9 + 7;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, K; cin >> N >> K;
	vector<int> v(N);
	for (int i = 0; i < N; i++) cin >> v[i];

	priority_queue<pll> pq; //(값, 부호)
	for (int i = 0; i < N; i++) pq.push({ abs(v[i]), v[i] >= 0 });

	vector<int> neg, pos;
	for (int i = 0; i < K; i++) {
		pll a = pq.top();
		pq.pop();
		if (a.sc == 1) pos.push_back(a.fr);
		else neg.push_back(a.fr);
	}

	if (neg.size() % 2 == 1) {
		//2가지 선택지가 있음 ( pos : a, b , neg : c, d)
		//1. neg를 하나 더 추가한다. (c, d)
		//2. neg를 하나 뺀다. (a, b)

		ll a, b, c, d;
		a = c = b = d = -1;
		if (pos.size()) a = pos.back();
		if (neg.size()) c = neg.back();

		while (pq.size()) {
			pll a = pq.top();
			pq.pop();
			if (a.sc == 0 && d == -1) d = a.fr;
			if (a.sc == 1 && b == -1) b = a.fr;
			
			if (b != -1 && d != -1) break;
		}

		bool flag = 1;
		if (b == -1 && d == -1);
		else if (b == -1) {
			if (pos.size()) {
				neg.push_back(d);
				pos.pop_back();
			}
		}
		else if (d == -1) {
			if (neg.size()) {
				pos.push_back(b);
				neg.pop_back();
			}
		}
		else {
			if (a * b > c * d) {
				if (neg.size()) {
					pos.push_back(b);
					neg.pop_back();
				}
				else if (pos.size()){
					neg.push_back(d);
					pos.pop_back();
				}
			}
			else{
				if (pos.size()) {
					neg.push_back(d);
					pos.pop_back();
				}
				else if (neg.size()) {
					pos.push_back(b);
					neg.pop_back();
				}
			}
		}

		if (neg.size() % 2 == 1) {
			neg.clear(); pos.clear();
			vector<pll> tmp;
			for (int i = 0; i < N; i++) tmp.push_back({ abs(v[i]), v[i] >= 0 });
			sort(all(tmp));
			for (int i = 0; i < K; i++) {
				if (tmp[i].sc == 1) pos.push_back(tmp[i].fr);
				else neg.push_back(tmp[i].fr);
			}
		}
	}

	ll ans = 1;
	for (int i = 0; i < pos.size(); i++) ans = ans * pos[i] % MOD;
	for (int i = 0; i < neg.size(); i++) ans = ans * -neg[i] % MOD;
	ans = (ans + MOD) % MOD;
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 15136
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
    cout<<a<<" "<<b<<" "<<c<<endl;
    return 0;
}


Measured memory_bytes: 3080
N = int(input())

S_list= [[i+1,list(map(str,input().split()))] for  i in range(N)]
# lambda を用いて、2元配列をそれぞれソート可能
S_list = sorted(S_list,key = lambda x :(x[1][0],-int(x[1][1]) ))

for i in range(N):
    print(S_list[i][0])


Measured memory_bytes: 3060
#include <stdio.h>
#include <ctype.h>

int stack[102]; int top;
char buf[2000];

int main()
{
	int  v1, v2;
	char *p;

	fgets(p=buf, 500, stdin);
	top = 0;
	while (*p >= ' ') {
		while (isspace(*p)) p++;
		if (isdigit(*p)) {
			v1 = 0;
			while (isdigit(*p)) v1 = 10*v1 + (*p++ & 0xf);
			stack[top++] = v1;
		} else {
			v1 = stack[--top];
			v2 = stack[--top];
			if      (*p == '+') v2 += v1;
			else if (*p == '-') v2 -= v1;
			else if (*p == '*') v2 *= v1;
			stack[top++] = v2;
			p++;
		}
	}
	printf("%d\n", stack[--top]);
	return 0;
}


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

int main() {
	int N;
	cin >> N;
	vector<int> d(10);
	int b, c;

	for (int i = 0; i<N; i++){
		for (int k = 0; k < 10; k++)
			cin >> d.at(k);

		b = d.at(0);
		c = 0;
		for (int k = 1; k < 10; k++){
			if (b < c){
				if (b > d.at(k)){
					cout << "NO" << endl;
					break;
				}
				else{
					if (c < d.at(k))
						c = d.at(k);
					else
						b = d.at(k);
				}
			}

			else{
				if (c > d.at(k)){
					cout << "NO" << endl;
					break;
				}
				else{
					if (b < d.at(k))
						b = d.at(k);
					else
						c = d.at(k);
				}
			}
			if (k == 9)
				cout << "YES" << endl;
		}
	}
}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

bool comp(pii &a, pii &b)
{
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vpi abs;
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        abs.push_back(make_pair(a, b));
    }

    // for(auto &p : abs) cout << p.first << ", " << p.second << endl;
    // cout << endl;
    sort(abs.begin(), abs.end(), comp);
    // for(auto &p : abs) cout << p.first << ", " << p.second << endl;
    int cnt = 1;
    int g = abs.at(0).second;
    for(auto &p : abs)
    {
        // cout << p.first << ", " << p.second << endl;
        if(p.first >= g)
        {
            cnt++;
            g = p.second;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 1400
n,k=map(int,input().split())

l=[0 for i in range(10**5)]
for i in range(n):
  a,b=map(int,input().split())
  a-=1
  l[a]+=b

cnt=0
for i in range(len(l)):
  cnt+=l[i]
  if cnt>=k:
    print(i+1)
    exit()

Measured memory_bytes: 5924
#include<cstdio>
#include<complex>

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

using namespace std;

typedef complex<double> Point;

const double EPS=1e-9;

int n;
Point p[300];

int f(const Point &c){
	int res=0;
	rep(i,n) if(abs(p[i]-c)<1+EPS) res++;
	return res;
}

int main(){
	for(;scanf("%d",&n),n;){
		rep(i,n){ double x,y; scanf("%lf%lf",&x,&y); p[i]=Point(x,y); }

		int ans=1;
		rep(j,n) rep(i,j) {
			double d=abs(p[j]-p[i])/2;
			Point v=(p[j]-p[i])/(2*d);
			if(d<1){
				ans=max(ans,f(p[i]+d*v+sqrt(1-d*d)*v*Point(0,+1)));
				ans=max(ans,f(p[i]+d*v+sqrt(1-d*d)*v*Point(0,-1)));
			}
		}
		printf("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 816
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int main(){
//  freopen("data.in","r",stdin);
  int n,m;
  scanf("%d %d",&n,&m);
  char s[12];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%s",s);
      if(strcmp(s,"snuke")==0){
        printf("%c%d\n",j+'A',i+1);
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main(){
  int h, w, d; cin >> h >> w >> d;
  vector<vector<int>> a(h, vector<int>(w));
  vector<pair<int, int>> x(h * w);
  rep(i, h) rep(j, w) {
    cin >> a[i][j];
    a[i][j]--;
    x[a[i][j]] = make_pair(i, j);
  }

  vector<vector<int>> maryoku(d);

  for(int i = 0; i < d; i++){
    int pre = i, next = i + d;
    maryoku[i].push_back(0);
    while(next < h * w){
      pair<int, int> preid = x[pre], nextid = x[next];
      maryoku[i].push_back(abs(preid.first - nextid.first) + abs(preid.second - nextid.second) + maryoku[i].back());
      pre = next;
      next += d;
    }
  }

  /*rep(i, d){
    rep(j, maryoku[i].size()){
      cout << maryoku[i][j] << " ";
    }
    cout << endl;
  }*/


  int q; cin >> q;
  vector<ll> ans(q);
  rep(i, q){
    int l, r; cin >> l >> r;
    l--; r--;
    ans[i] = maryoku[l % d][r / d] - maryoku[l % d][l / d];
  }

  rep(i, q){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 10064
# -*- coding:utf-8 -*-
while True:
    (H,W) = [int(s) for s in input().split()]
    if H == W == 0:
        break
    for i in range(H):
        if i ==0 or i == H-1:
            print('#'*W)
        else:
            print('#' + '.'*(W-2) + '#')
    print()

Measured memory_bytes: 7664
#include <iostream>
using namespace std;
int main(){
    int n, x, ans[200005], a[200005];
    cin >> n;
    for(int i = 2; i <= n; i ++) cin >> a[i];
    for(int i = 2; i <= n; i ++) ans[a[i]] ++;
    for(int i = 1; i <= n; i ++){
        cout << ans[i] << "\n";
    }
    
}

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

int main(){
    int x[5];
    for(int i = 0; i < 5; i++){
        cin >> x[i];
    }

    for(int i = 0; i < 5; i++){
        if(x[i] == 0){
            cout << i + 1 << endl;
        }
    }
}

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

class Main {
  public static TreeMap<Integer, TreeMap<Integer, Integer>> map = new TreeMap<Integer, TreeMap<Integer, Integer>>();
  public static void main(String[] args) throws Exception{
    try (Scanner sc = new Scanner(System.in)){
      int N = sc.nextInt();
      int M = sc.nextInt();

      for (int i = 0; i < M; i++) {
        int P = sc.nextInt();
        int Y = sc.nextInt();
        if (map.containsKey(P)) {
          map.get(P).put(Y, i);
        } else {
          map.put(P, new TreeMap<Integer, Integer>());
          map.get(P).put(Y,i);
        }
      }
      String[] ans = new String[M];
      int count = 0;
      for (Integer i : map.keySet()) {
        count = 0;
        for (Integer j : map.get(i).keySet()) {
          count++;
          ans[map.get(i).get(j)] = String.format("%06d%06d", i, count);
        }
      }
      for (int i = 0; i < M; i++) {
        System.out.println(ans[i]);
      }
    }
  }
}


Measured memory_bytes: 159720
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
using namespace std;
typedef long long int ll;

int main(){
	ll s; cin >> s;
	if(s<=1e9){
		cout << 0 << " " << 0 << " " << s << " " << 0 << " " <<0 << " " <<  1 << endl;
	}
	else if(s==1e18){
		cout << 0 << " " << 0 << " " << 1000000000 << " " << 0 << " " << 0 << " " << 1000000000 << endl;
	}
	else{
		ll cp=s;
		cp/=1e9;
		cp*=1e9;
		ll c=s-cp;
		cp=cp/1e9+1;
		cout << 0 << " " << 1 << " " << 1000000000 << " "  << 0 << " " << c <<" " <<  cp << endl;
	}
}

Measured memory_bytes: 256
# python 3.4.3
import sys
input = sys.stdin.readline
import numpy as np

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
K = int(input())
X = int(input())
Y = int(input())

print(min(N,K)*X + max(N-K,0)*Y)

Measured memory_bytes: 12504
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
#define dprint(v) cout << #v"=" << v << endl //;)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
#define forall(it,v) for(auto it=v.begin();it!=v.end();++it)
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define INF (ll)1e16
#define endl '\n'
#define isin(x,y) ((y).find(x)!=(y).end())

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
        string s;
        cin>>s;
        ll cnt=0;
        forn(i,sz(s))if(s[i]=='o')++cnt;
        if(cnt>=8||(15-sz(s))+cnt>=8){
            cout<<"YES"<<endl;
            return 0;
        }
        cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;


void print() {
    cout << endl;
}
 
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << ' ';
    print(forward<Tail>(tail)...);
}
 
template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << ' ';
    }
    cout << endl;
}
 
template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}
 

int main(){
  ll a,b;cin >> a >> b;
  if(b%a)print(b-a);
  else print(a+b);
}

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

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

int n;
ll l[100001],r[100001];
multiset<ll> dpl,dpr;

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&l[i],&r[i]);
	}
	dpl.insert(-1LL<<60);
	dpr.insert(1LL<<60);
	ll ofl=0,ofr=0;
	ll res=0;
	for(int i=0;i<n;i++){
		if(i>0){
			ofl-=r[i]-l[i];
			ofr+=r[i-1]-l[i-1];
		}
		if(l[i]<*dpl.rbegin()+ofl){
			res+=*dpl.rbegin()+ofl-l[i];
		}else if(*dpr.begin()+ofr<l[i]){
			res+=l[i]-(*dpr.begin()+ofr);
		}
		if(l[i]<*dpl.rbegin()+ofl){
			dpr.insert(*dpl.rbegin()+ofl-ofr);
			dpl.insert(l[i]-ofl);
			dpl.insert(l[i]-ofl);
			dpl.erase(dpl.find(*dpl.rbegin()));
		}else if(*dpr.begin()+ofr<l[i]){
			dpl.insert(*dpr.begin()+ofr-ofl);
			dpr.insert(l[i]-ofr);
			dpr.insert(l[i]-ofr);
			dpr.erase(dpr.begin());
		}else{
			dpl.insert(l[i]-ofl);
			dpr.insert(l[i]-ofr);
		}
	}
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 11136
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    x = LI()
    f = [[] for i in range(n)]
    l = I()
    for i in range(n):
        xi = x[i]
        j = bisect.bisect_right(x,l+xi)-1
        f[i].append(j)
    h = int(math.log(n,2))+1
    for j in range(h-1):
        for i in range(n):
            f[i].append(f[f[i][j]][j])
    q = I()
    for _ in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        if b < a:
            a,b = b,a
        ans = 0
        for i in range(h)[::-1]:
            if f[a][i] < b:
                a = f[a][i]
                ans += 1<<i
        print(ans+1)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 112340
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>

using namespace std;
typedef long long int ll;

int n,m,pp,yy;
vector<int> p,y,t;
map<int,int> ga;

void sortvec(vector<int> &target,vector<int> &secondnum,vector<int> &www)
{
    int vecsize=target.size();
    vector<int> baseint,target2(vecsize),secondnum2(vecsize),w3(vecsize);
    for(int i=0;i<vecsize;i++)baseint.push_back(i);
    sort(baseint.begin(),baseint.end(),[&](int a,int b){return target[a]<target[b];});
    for(int i=0;i<vecsize;i++){
        target2[i]=target[baseint[i]];
        secondnum2[i]=secondnum[baseint[i]];
        w3[i]=www[baseint[i]];
    }
    target=target2;secondnum=secondnum2;www=w3;
}


int main(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d %d",&pp,&yy);
        p.push_back(pp);y.push_back(yy);t.push_back(i);
        ga[pp]=1;
    }
    sortvec(y,p,t);
    //sortvec(p,y,t);
    for(int i=0;i<m;i++){
        y[i]=ga[p[i]];
        ga[p[i]]++;
    }
    

    sortvec(t,p,y);
    
    for(int i=0;i<m;i++){
        //printf("%d %d %d\n",p[i],y[i],t[i]);
        cout<<setfill('0')<<right<<setw(6)<<p[i];
        cout<<setfill('0')<<right<<setw(6)<<y[i];
        cout<<endl;
    }
    
}


Measured memory_bytes: 8140
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

using namespace std;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int h, w, d; cin >> h >> w >> d;
  pair<int, int> p[h*w+1];
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      int a; cin >> a;
      p[a] = make_pair(i, j);
    }
  }
  int sum[h*w+1];
  for(int i=0;i<d;i++){
    sum[i] = 0;
    for(int j=i+d;j<=h*w;j+=d){
      sum[j] =
      sum[j-d] + abs(p[j].first - p[j-d].first) + abs(p[j].second - p[j-d].second);
    }
  }
  int q; cin >> q;
  for(int i=0;i<q;i++){
    int l, r; cin >> l >> r;
    cout << sum[r] - sum[l] << endl;
  }
}

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

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

  int a,b,c;cin>>a>>b>>c;
  cout<<max(0, c-(a-b))<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll  long long
#define PB push_back
#define ld long double
#define ff first
#define ss second
# define st(v) (v).begin(),(v).end()
#define   pr pair<int,int>
const int N = 1e5+4 , M=N,inf=(int)1e9;
const ll mod=1e9+7;
int fastAbs(int n) { return (n ^ (n >> 31)) - (n >> 31); }
ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
int ans = INT_MAX;
map< pair<int,int> , int > mp;
const int dx[4] = {1,0,0,-1};
const int dy[4] = {0,-1,1,0};
void solve(){
	int n ; 
	cin >> n ;
	vector < long double > coins(n);
	for( int i = 0 ; i < n ; i++) cin >> coins[i];
	vector < vector< long double > > dp( n , vector < long double > ( n+1,0) ) ;
	dp[0][0] = 1 - coins[0] ;
	dp[0][1] = coins[0] ;
	for( int i = 1 ; i < n ; i++){
		dp[i][0]=dp[i-1][0]*(1-coins[i]);
		for( int j = 1 ; j <= i+1 ; j++){
			dp[i][j] += coins[i]*dp[i-1][j-1];
			dp[i][j] += (1-coins[i])*dp[i-1][j]; 
		}
	} 
	long double ans =0 ;
	for( int i = 1 ; i <=n ; i++){
		if(i>n-i){
			ans+=dp[n-1][i];
		}
	}
	cout << fixed << setprecision(10) <<  ans ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q=1;
    //cin >> q;
    while(q--)
        solve();
}


Measured memory_bytes: 141056
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                                                                  \
  ios_base::sync_with_stdio(0);                                                \
  cin.tie(0);                                                                  \
  cout.tie(0);
#define oprecision                                                             \
  cout.precision(30);                                                          \
  cerr.precision(7);
#define bb bool
#define ii int
#define ll long long
#define ff float
#define dd double
#define cc char
#define ss string
#define forn(sz) for (int i = 1; i <= sz; i++)
#define forni(i, sz) for (int i = 1; i <= sz; i++)
#define fornid(i, m, sz) for (int i = m; i <= sz; i++)
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vii vector<ii>
#define vii64 vector<ll>
#define vb vector<bb>
using namespace std;
ll sz, BIG = (1LL << 60), arr[3010], dp[3010][3010];
ll rec(ll l, ll r) {
  if (l > r) {
    return 0;
  }
  if (l == r) {
    return arr[l];
  }
  if (dp[l][r] != BIG) {
    return dp[l][r];
  }
  return dp[l][r] = max(arr[l] - rec(l + 1, r), arr[r] - rec(l, r - 1));
}
int main() {
  speed;
  oprecision;
  /*#ifndef ONLINE_JUDGE
freopen("outd.txt", "rt", stdin);
#endif*/
  // code
  for (int i = 0; i <= 3001; i++) {
    for (int j = 0; j <= 3001; j++) {
      dp[i][j] = BIG;
    }
  }
  cin >> sz;
  forn(sz) { cin >> arr[i]; }
  cout << rec(1, sz);
// endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}


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

int main(){
    ll a,b;
    cin>>a>>b;
    ll d = max(a,b)-min(a,b)+1;
    if(max(a,b)>=0 && min(a,b)<=0) cout<<"Zero";
    else if(max(a,b)<0 && min(a,b)<0 && d%2==1) cout<<"Negative";
    else cout<<"Positive";
}

Measured memory_bytes: 256
///AJoy Sarker ,CSE JAHANGIRNAGAR UNIVERSITY 48 Batch

#include<bits/stdc++.h>

using namespace std;
#define SORT(c) sort((c).begin(),(c).end());
#define inf INT_MAX/3
#define pb push_back
#define MP make_pair
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 3.141592653589793
#define in scanf
#define out printf
#define ll long long
#define ull unsigned long long
typedef unsigned long long UL;
template<typename T>inline T  S(T a)
{
    return a*a;
}
template<class T>inline string tostring(T a)
{
    ostringstream os("");
    os << a;
    return os.str();
}
template<typename T>inline ll tolong(T a)
{
    ll res;
    istringstream os(a);
    os>>res;
    return res;
}
template<typename T>inline T gcd(T a, T b)
{
    if (b == 0)return a;
    else return gcd(b, a % b);
}
template<typename T>inline T bigmod(T a, T b, T m)
{
    if (b == 0)return 1;
    else if (b % 2 == 0)return S(bigmod(a, b / 2, m)) % m;
    else return (a % m*bigmod(a, b - 1, m)) % m;
}

int main()
{
    ios_base::sync_with_stdio(0);
    //ll n,c,cnt=0,prev;
    int h,w;
    cin>>h>>w;
    vector<string>s(h);
    for(int i=0;i<h;i++)cin>>s[i];
    for(int i=0;i<w+2;i++)cout<<'#';
    cout<<endl;
    for(int i=0;i<h;i++)
    {
        cout<<'#'<<s[i]<<'#'<<endl;
    }
   for(int i=0;i<w+2;i++)cout<<'#';

    return 0;
}




Measured memory_bytes: 256
inputs = input().strip().split()

N = int(inputs[0])
K = int(inputs[1])

inputs = input().strip().split()
problem = list(map(lambda x: int(x), inputs))

ans = 10000000000000000000000000

if N == K:
    left = problem[0]
    right = problem[K - 1]
    if left * right >= 0:
        if abs(right) > abs(left):
            if ans > abs(right):
                ans = abs(right)
        else:
            if ans > abs(left):
                ans = abs(left)
    else:
        if abs(right) > abs(left):
            if ans > (2 * abs(left) + abs(right)):
                ans = (2 * abs(left) + abs(right))
        else:
            if ans > 2*abs(right)+abs(left):
                ans = 2*abs(right)+abs(left)
else:
    for i in range(N - K + 1):
        left = problem[i]
        right = problem[i+K-1]
        if left * right >= 0:
            if abs(right) > abs(left):
                if ans > abs(right):
                    ans = abs(right)
            else:
                if ans > abs(left):
                    ans = abs(left)
        else:
            if abs(right) > abs(left):
                if ans > (2 * abs(left) + abs(right)):
                    ans = (2 * abs(left) + abs(right))
            else:
                if ans > 2*abs(right)+abs(left):
                    ans = 2*abs(right)+abs(left)

print(ans)

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

int main(){
    int N; cin >> N;
    bool flag = true;
    for(int i=0;i<N;i++){
        int A; cin >> A;
        if(A%2==0){
            if(A%3==0 || A%5==0){
                continue;
            }else{
                flag = false;
                break;
            }
        }else{
            continue;
        }
    }
    if(flag){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
}

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

#define MAX 30

typedef struct{
  int parent;
  int left;
  int right;
}Roll;

int PreorderPrint(int root,Roll *Tree){
    if(root == -1) return -1;
    printf(" %d",root);
    PreorderPrint(Tree[root].left,Tree);
    PreorderPrint(Tree[root].right,Tree);
    return 0;
}

int InorderPrint(int root,Roll *Tree){
  if(root==-1)return -1;
  InorderPrint(Tree[root].left,Tree);
  printf(" %d",root);
  InorderPrint(Tree[root].right,Tree);
  return 0;
}

int PostorderPrint(int root,Roll *Tree){
  if(root==-1)return -1;
  PostorderPrint(Tree[root].left,Tree);
  PostorderPrint(Tree[root].right,Tree);
  printf(" %d",root);
  return 0;
}

void init(Roll *Tree){
  int i;
  for(i=0;i<MAX;i++){
    Tree[i].left=Tree[i].right=Tree[i].parent=-1;
  }
}

int main(){
  Roll Tree[MAX];
  int id,left,right;
  int i,n,root=0;
  scanf("%d",&n);
  init(Tree);
  for(i=0;i<n;i++){
     scanf("%d%d%d",&id,&left,&right);
     Tree[id].left=left;
     Tree[id].right=right;
     if(left!=-1) Tree[left].parent=id;
     if(right!=-1) Tree[right].parent=id;
   }
  for(i=0;i<n;i++){
    if(Tree[i].parent==-1){
      root=i;
      break;
    }
  }
  printf("Preorder\n"); 
  PreorderPrint(root,Tree);
  printf("\n");
  printf("Inorder\n"); 
  InorderPrint(root,Tree);
  printf("\n");
  printf("Postorder\n"); 
  PostorderPrint(root,Tree);
  printf("\n");
  return 0;
}
  

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

#define int long long

using namespace std;



const int MAXN = 100 * 1000 + 23;












int n, x[MAXN], m, a[MAXN], k, xp[MAXN], p[MAXN], res[MAXN];
bitset<MAXN> mark;
vector<int> help;




int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		if (i) xp[i] = x[i] - x[i - 1];
		else xp[i] = x[i];
	}
	iota(p, p + n, 0);
	cin >> m >> k;
	for (int i = 0; i < m; i++) {
		int z;
		cin >> z;
		swap(p[z], p[z - 1]);
	}
	int z;
	for (int i = 0; i < n; i++) {
		help.clear();
		z = i;
		if (!mark[i]) {
			while (!mark[z]) {
				help.push_back(z);
				mark[z] = true;
				z = p[z];
			}
			z = k % ((int)help.size());
			for (auto i : help) res[i] = help[z++ % help.size()];
		}
	}
	z = 0;
	for (int i = 0; i < n; i++) {
		z += xp[res[i]];
		cout << z << '\n';
	}
	return 0;
}

Measured memory_bytes: 5364
(let* ((n (read))
       (m (read))
       (h (make-array `(,(1+ n))))
       (g (make-array `(,(1+ n)) :initial-element t))
       (ans 0))
  ; read
  (loop :for i :from 1 :to n
        :do (setf (aref h i) (read)))
  ;
  (loop :for i :from 1 :to m
        :do (let ((a (read))
                  (b (read)))
              (if (<= (aref h a) (aref h b))
                  (setf (aref g a) nil))
              (if (>= (aref h a) (aref h b))
                  (setf (aref g b) nil))))
  ;
  (loop :for i :from 1 :to n
        :if (aref g i)
        :do (incf ans))
  (format t "~A~%" ans))


Measured memory_bytes: 78932
#include <iostream>
#include <cmath>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <vector>
using namespace std;
#define INF 1000000007
#define ll long long
#define rep(i_, __start, __end) for(ll i_=(ll)__start; i_<(ll)__end; i_++)
#define print(_a) cout << _a << endl;
#define printarray(a, len) rep(ii,0,len) cout << a[ii] << " ";
#define printarray2(aa, len) rep(ij,0,len) printarray(aa[ij], aa[ij].size()); print("");


int main(){
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    cout << s1[0] << s2[1] << s3[2] << endl;
   
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<set>
#include<utility>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>
#include<iomanip>

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

#define P pair<int, int>

typedef long long ll;

using namespace std;


const ll INF = 1e18;

int N;
ll a[405], sum[405] = {}, dp[405][405];
int main() {
	cin >> N;
	rep(i, N) cin >> a[i], sum[i+1] = a[i] + sum[i];

	rep(i, N + 1)rep(j, N + 1) dp[i][j] = INF;
	rep(i, N) {
		dp[i][i] = 0;
	}
	for (int len = 1; len <= N; len++) {
		for (int i = 0; i + len < N; i++) {
			int j = i + len;
			ll add = sum[j+1] - sum[i];
			for (int k = i; k < j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + add);
			}
		}
	}
	cout << dp[0][N-1] << endl;

	return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    int N,M,Q;cin >> N >> M >> Q;
    vector<pair<int,int>> lr(M);
    rep(i,M)cin >> lr[i].F >> lr[i].S;
    vector<pair<int,int>> p(Q);
    rep(i,Q)cin >> p[i].F >> p[i].S;

    // a に二次元の座標LRを格納
    vector<vector<int>> a(N+1, vector<int>(N+1,0));
    rep(i,M){
        int s = lr[i].F;
        int t = lr[i].S;
        a[s][t]++;
    }

    // 二次元累積和
    vector<vector<int> > s(N+2, vector<int>(N+2, 0));
    rep(i,N+1)rep(j,N+1)s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + a[i][j];

    // クエリ [x1, x2) × [y1, y2) の長方形区域の和
    rep(i,Q){
        int x1 = p[i].F;
        int x2 = p[i].S + 1;
        int y1 = p[i].F;
        int y2 = p[i].S + 1;
        cout << s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] << endl;
    }

    

}



Measured memory_bytes: 5248
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
  int a,b,c;
  for(;cin>>a>>b>>c,a||b||c;)
    {
      int item[a+b+c];
      for(int ii=0;ii<a+b+c;ii++)
	item[ii]=2;
      int n;
      cin>>n;
      int i[n],j[n],k[n],r[n];
      for(int ii=0;ii<n;ii++)
	{
	  cin>>i[ii]>>j[ii]>>k[ii]>>r[ii];
	  i[ii]--;
	  j[ii]--;
	  k[ii]--;  
	  if(r[ii]==1)
	    {
	      item[i[ii]]=1;
	      item[j[ii]]=1;
	      item[k[ii]]=1;	      
	    }
	}
      for(int ii=0;ii<n;ii++)
	{
	  if(r[ii]==0)
	    {
	      if(item[i[ii]]==1 &&item[j[ii]]==1)
		item[k[ii]]=0;
	      if(item[i[ii]]==1 &&item[k[ii]]==1)
		item[j[ii]]=0;
	      if(item[j[ii]]==1 &&item[k[ii]]==1)
		item[i[ii]]=0;
	    }
	}
      for(int ii=0;ii<a+b+c;ii++)
	cout<<item[ii]<<endl;
    }
}

Measured memory_bytes: 1176
#include <stdio.h>

int main()
{
  int cnt;
  int N,A,B;
  int min, max;
  int min_rem = 0;
  int min_s, max_s;

  cnt = scanf("%d %d %d", &N, &A, &B);

  if (A > B) {
    max = A;
    min = B;
  }else{
    max = B;
    min = A;
  }

  max_s = min;

  min_rem = N - min;

  if (min_rem < max) {
    min_s = max - min_rem;
  } else {
    min_s = 0;
  }

  printf("%d %d", max_s, min_s);
  
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>

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

long N;
long ans = 1;

int main() {
  cin >> N;
  for (int i=1; i<=N; i++) {
    ans *= i;
    ans %= 1000000007;
  }
  cout << ans << endl;
}


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

#define rep(i,N) repv(i,0,N)
#define reps(i,N) repvs(i,0,N)
#define repv(i,a,b) for(int i=a;i<b;i++)
#define repvs(i,a,b) for(int i=a+1;i<=b;i++)
#define repr(i,N) for(int i=N-1;i>=0;i--)
#define reprs(i,N) for(int i=N;i>0;i--)

#define d(a) if(isDebugMode) cout<<#a<<"="<<a<<","
#define d2(a,b) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b<<" "
#define d3(a,b,c) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c
#define d4(a,b,c,d) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<","<<#d<<"="<<d
#define da(arr,N){if(isDebugMode){rep(i,N+1){if(arr[i]==INF)printf("INF ");else cout<<arr[i]<<" ";} cout<<endl;}}
#define da2(arr,N,M){if(isDebugMode)rep(i,N+1){rep(j,M+1){if(arr[i][j]==INF)printf(" INF");else printf(" %3d",arr[i][j]);}cout<<endl;}}
#define pb push_back
#define pob pop_back
#define s(a) cout<<a<<endl;

auto chmax =[](int &a,int b){ a = max(a, b);};
auto chmin =[](int &a,int b){ a = min(a, b);};

typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
const int MOD = 100000007;
const int dx[4] = { 0, 1, 0,-1};
const int dy[4] = { 1, 0,-1, 0};

bool isDebugMode=0;
//--------------------------------------//
int n,W;
vector<int> b[4];
ll w1;
void solve(){
	int ans=0;
	rep(i,4){
		b[i].pb(INT_MAX);
		sort(b[i].begin(),b[i].end(),greater<int>());
		b[i][0]=0;
		rep(j,b[i].size()-1){
			b[i][j+1]+=b[i][j];
		}
	}
	rep(i,b[0].size()){
		rep(j,b[1].size()){
			rep(k,b[2].size()){
				rep(l,b[3].size()){
					ll w=0;
					int v=0;
					w+=w1*i;
					v+=b[0][i];
					w+=(w1+1)*j;
					v+=b[1][j];
					w+=(w1+2)*k;
					v+=b[2][k];
					w+=(w1+3)*l;
					v+=b[3][l];
					d2(v,w);
					if(w<=W) chmax(ans,v);
				}
			}
		}
	}
	s(ans);
}

int main(){
	cin>>n>>W;
	rep(i,n) {
		int w,h;
		cin>>w>>h;
		if(i==0)w1=w;
		b[w-w1].pb(h);
	}
	solve();
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	run()
}

func run() {
	setSpace()
	N, W := int(readN()), readN()

	dp := make([][]int, N+1)
	// dp[i][sumW]
	// i 番目まで品物を選んで、合計の重さが sumW のときの価値の最大値

	dp[0] = make([]int, W+1)
	for i := 0; i < N; i++ {
		w, v := readN(), readN()
		dp[i+1] = make([]int, W+1)
		// i + 1 番目の更新は、
		for sumW := 0; sumW <= W; sumW++ {
			// i 番目までの価値をそのまま更新する
			dp[i+1][sumW] = dp[i][sumW]
			if sumW-w >= 0 {
				// もし、選べるとしたら, 比較して、価値があがるのであれば更新する
				chmax(&dp[i+1][sumW], dp[i][sumW-w]+v)
			}
		}
	}

	fmt.Println(dp[N][W])
}

func chmax(a *int, b int) {
	if *a > b {
		return
	}
	*a = b
}

// ------以下、ユーティリティ------

var sc = bufio.NewScanner(os.Stdin)

func setSpace() {
	sc.Split(bufio.ScanWords)
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readN() int {
	n, err := strconv.Atoi(read())
	if err != nil {
		panic(err)
	}
	return n
}


Measured memory_bytes: 81664
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    

    string s,t;
    cin >> s >> t;
    int ans = 0;
    for (ll i=0;i<3;i++){
        if(s[i] == t[i]){
            ans += 1;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
input_line = input().split()
stack = []
for i in input_line:
    if i == '+':
        stack.append(stack.pop() + stack.pop())
    elif i == '-':
        a = stack.pop()
        b = stack.pop()
        stack.append(b - a)
    elif i =='*':
        stack.append(stack.pop() * stack.pop())
    else:
        stack.append(int(i))
print(stack[0])




Measured memory_bytes: 5600
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

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

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}

//素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


int main() {
  int N;
  cin >> N;
  // vector<vector<ll>> ab(N,vector<ll>(2));
  // rep(i,N) cin >> ab[i][0] >> ab[i][1];
  vector<ll> A(N),B(N);
  rep(i,N) {
    cin >> A[i] >> B[i];
    // A[i]*=-1;
  }
  sort(A.begin(),A.end());
  sort(B.rbegin(),B.rend());
  // cout << A << endl << B << endl;
  if (N%2) {
    int n = N/2+1;
    cout << (B[n-1] - A[n-1])+1 << endl;
  }
  else {
    int n=N/2;
    ll x0=A[n-1],x1=B[n],y0=A[n],y1=B[n-1];
    cout << (y1+x1) - (y0+x0) +1 << endl;
  }
}

Measured memory_bytes: 6428
import java.util.*;


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

        int[] ans = new int[N];

        for (int i = 0; i < M; i++) {
            int p = sc.nextInt() - 1;
            int a = sc.nextInt();

            if (ans[p] != a && ans[p] != 0) {
                System.out.println(-1);
                System.exit(0);
            }
            
            ans[p] = a;
                
            if (p == 0 && a == 0 && N != 1) {
                System.out.println(-1);
                System.exit(0);
            }
            sc.nextLine();
        }

        int s = 1;
        int a = 0;
        if (ans[0] == 0 && N != 1) { ans[0] = 1; }

        for (int i = N-1; i >= 0; i--) {
            a += ans[i] * s;
            s *= 10;
        }

        System.out.println(a);
    }
}

Measured memory_bytes: 21844
N = gets.to_i
h = gets.split.map(&:to_i)

c = 0

while h.inject(:+) > 0
  l = h.index(h.max)
  r = l

  while h[r+1] == h.max
    r += 1
  end

  h.map!.with_index{|k, i| (l..r).include?(i) ? k-1 : k}
  
  c += 1
end

puts c


Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define endl '\n';
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;



int main() {
    
    int x,y,z;
    cin>>x>>y>>z;
    swap(x,y);
    swap(x,z);
    cout<<x<<" "<<y<<" "<<z<<endl;
}



Measured memory_bytes: 256
n,m=map(int,input().split())
d=[-1]*n
def find(x):
    if d[x]<0:
        return x
    d[x]=find(d[x])
    return d[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if d[x]>d[y]:
        x,y=y,x
    d[x]+=d[y]
    d[y]=x
    return
ans=(int)(n*(n-1)/2)
a=[0]*m
b=[0]*m
stack=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
a.reverse()
b.reverse()
for i in range(m):
    stack.append(ans)
    a[i]=find(a[i])
    b[i]=find(b[i])
    if find(a[i])!=find(b[i]):
        ans-=(int)(-d[a[i]])*(-d[b[i]])
        unite(a[i],b[i])
while stack:
    print(stack.pop())

Measured memory_bytes: 83700
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int[] A)
        {
            int[] counts = new int[100002];
            foreach (int a in A)
            {
                ++counts[a + 0];
                ++counts[a + 1];
                ++counts[a + 2];
            }
            return counts.Max();
        }

        static void Main(string[] args)
        {
            int N = ReadInt();
            Console.WriteLine(Solve(ReadInts()));
        }
    }
}


Measured memory_bytes: 19296
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))

    max_i=0
    for i in range(n):
        if abs(a[max_i])<abs(a[i]):
            max_i=i
    
    a=list(map(lambda x:x+a[max_i],a))
    ans=[]
    for i in range(n):
        ans.append([max_i+1,i+1])
    
    if a[0]>=0:
        for i in range(n-1):
            ans.append([i+1,i+2])
    else:
        for i in range(n-1,0,-1):
            ans.append([i+1,i])

    print(2*n-1)
    for i in range(2*n-1):
        print(*ans[i])

if __name__=="__main__":
    main()

Measured memory_bytes: 3188
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int N;
ll L;
vll A;

int main(){
    cin >> N >> L;
    A = vll(N);
    rep(i, N)scanf("%lld", &A[i]);

    int idx = -1;
    rep(i, N - 1)if(A[i] + A[i + 1] >= L){
        idx = i;
        break;
    }
    if(idx == -1){
        puts("Impossible");
        return 0;
    }

    puts("Possible");
    ++idx;
    vi ans;
    for(int i = idx; i <= N - 1; ++i)ans.push_back(i);
    for(int i = idx - 1; i >= 1; --i)ans.push_back(i);
    reverse(all(ans));
    each(a, ans)printf("%d\n", a);
}

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int s = max(a,max(b,c)) - min(a,min(b,c));
    if(s == a || s == b || s == c){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
  int a=0,b=0,ans=0;
  int n=0,n1=0,n2=0,n3=0,n4=0,n5=0;
  
  cin >> a >> b;
  
  for (int i=a; i<=b; i++) {
    n = i;
    
    n1 = n-(n/10)*10;
    n /= 10;
    n2 = n-(n/10)*10;
    n /= 10;
    n3 = n-(n/10)*10;
    n /= 10;
    n4 = n-(n/10)*10;
    if (n4 != n2) continue;
    n /= 10;
    n5 = n-(n/10)*10;
    if (n5 != n1) continue;
    ans += 1;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
n = gets.to_i
list = gets.chomp.split(' ').map{|v| v.to_i}

count = 0
(1..n-2).each {|i|
    p0 = list[i-1]
    p1 = list[i]
    p2 = list[i+1]
    count += 1 if (p0 < p1 and p1 < p2) or (p0 > p1 and p1 > p2)
}

puts count

Measured memory_bytes: 1788
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

//?????§????????¢ O(H*W)
//???????????°??????????????§????????¢????±????????????¨????§?
void largest_rectangle() {
	int H, W; cin >> H >> W;
	vector<vector<int>> v(H, vector<int>(W));
	rep(i, 0, H) rep(j, 0, W) {
		int x; cin >> x;
		v[i][j] = !x;
	}
	rep(i, 0, H - 1)rep(j, 0, W) {
		if (v[i + 1][j] == 0)continue;
		v[i + 1][j] += v[i][j];
	}
	using P = pair<int, int>;
	int ans = 0;
	rep(i, 0, H) {
		stack<P> st;
		st.emplace(-1, -1);
		rep(j, 0, W) {
			if (st.top().first == v[i][j])
				continue;
			int pos = j;
			while (st.top().first >= v[i][j]) {
				chmax(ans, st.top().first*(j - st.top().second));
				pos = st.top().second;
				st.pop();
			}
			st.emplace(v[i][j], pos);
		}
		while (st.size()) {
			chmax(ans, st.top().first*(W - st.top().second));
			st.pop();
		}
	}
	cout << ans << endl;
}

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

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

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

	for (int i = 0; i < S.size(); i++) {
		if (S.at(i) != T.at(i)) {
			cout << "No" << endl;
			return 0;
		}
	}

	if (T.at(S.size ()) != NULL) {
			cout << "Yes" << endl;
		}
		else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3644
from collections import deque
N,u,v = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def bfs(s):
  dist = [-1]*N
  que = deque([s-1])
  dist[s-1] = 0
  while que:
    v = que.popleft()
    d = dist[v]
    for w in edge[v]:
      if dist[w]>-1: continue
      dist[w] = d+1
      que.append(w)
  return dist

ud,vd = bfs(u),bfs(v)
ans = 0
for ud_i,vd_i in zip(ud,vd): ans = max(ans, vd_i-1) if ud_i<vd_i else ans
print(ans)


Measured memory_bytes: 29336