akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll INF = 1'000'000'000'000'000'000;
namespace utils{
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool up_min(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool up_max(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }

    ll operator"" _64(unsigned long long x){ return ll(x); }
    ull operator"" _64u(unsigned long long x){ return ull(x); }

    template<class T>
    vector<T> make_mdvector(int n, T t){
        return vector<T>(n, t);
    }
    template<class ...Ts>
    auto make_mdvector(int n, Ts ... ts){
        return vector<decltype(make_mdvector(ts...))>(n, make_mdvector(ts...));
    }

    inline ll bit(int x){
        return 1ll << x;
    }

    template<class T>
    istream& operator>>(istream& is, vector<T>& v){
        for (auto &&x : v) { is >> x; } return is;
    }

    template<class T>
    ostream& operator<<(ostream& os, const vector<T>& v){
        for (auto &&x : v) { os << x << ' '; } cout << endl; return os ;
    }
}
using namespace utils;

class solver{
    istream& is;
    ostream& os;

public:
    solver(istream& I, ostream& O) :is(I), os(O) {}
    ll N;
    void run();
};

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef XELMH
    string test_cases = "test_A.txt";
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int loop = 0;
    while(fs) {
        loop++;
        cout << '#' << loop << "#------\n";
        solver(fs, cout).run();
    }
    if(loop <= 1) {
        cout << "===" << endl;
        while(cin) solver(cin, cout).run();
    }
#else
    solver(cin, cout).run();
#endif
    return 0;
}


void solver::run(){
    string S;
    is >> S;
    if(!is) return;
    if(S[0] == 'S'){
        os << "Cloudy\n";
    }
    else if(S[0] == 'C'){
        os << "Rainy\n";
    }
    else os << "Sunny\n";
}


Measured memory_bytes: 256
k = 26
D = gets.to_i
c = gets.split.map(&:to_i)
s = D.times.map { gets.split.map(&:to_i) }
D.times do |d|
  max_e = -1
  max_i = -1
  k.times do |i|
    e = s[d][i] # + c[i] * 50
    if e > max_e
      max_e = e
      max_i = i
    end
  end
  puts (d + 1) % k + 1
end


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

int main(){
    int n,m=0,ans=0;
    cin >> n;
    vector <int> h(n);
    rep(i,n){
        cin >> h[i];
        if(m<=h[i]){
            ++ans;
            m=h[i];
        }
    }

    cout << ans << endl;
    
    

    return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#define int long long
using namespace std;
int n, ai;
vector<int> data;
int32_t main(){
    cin >> n;
    int summ = 0;
    for (int i=0;i<n;i++){
        cin >> ai;
        data.push_back(ai);
        summ += ai;
    }
    if (summ % 10 != 0){
        cout << summ << endl;
    }
    else{
        sort(data.begin(), data.end());
        for (int i=0;i<n;i++){
            if (data[i] % 10 != 0){
                cout << summ - data[i] << endl;
                return 0;
            }
        }
        cout << 0 << endl;
    }
    return 0;
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int di2[] = {1, 1, -1, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1};
const int dj2[] = {1, -1, 1, -1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;


int main(){
  vector<int> prime(100001, true);
  prime[0] = prime[1] = false;
  for(ll i = 2; i <= 100000; ++i) {
    if(prime[i]) {
      for(ll j = i*i; j <= 100000; j += i) prime[j] = false;
    }
  }
  vector<int> vec(100001, 0);
  rep(i, 100001) {
    if(i%2==0) continue;

    if(prime[i] && prime[(i+1)/2]) ++vec[i];
  }
  rep(i, 100000) vec[i+1] += vec[i];
  int q; cin >> q;
  vector<int> ans;
  rep(i, q) {
    int l, r; cin >> l >> r;
    ans.push_back(vec[r] - vec[l-1]);
  }
  for(auto x : ans) cout << x << endl;
}

Measured memory_bytes: 4688
import java.util.*;

class Main {
	Scanner sc;
	int N, K, Q;
	int[] p;

	Main() {
		sc = new Scanner(System.in);
	}
	
	void calc() {
		N = sc.nextInt();
		K = sc.nextInt();
		Q = sc.nextInt();
		p = new int[N+1];
		for (int i = 0; i < Q; i++) {
			int a = sc.nextInt();
			p[a]++;
		}
		for (int i = 1; i <= N; i++) {
			if (K-Q+p[i] > 0) System.out.println("Yes");
			else System.out.println("No");
		}
	}

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

Measured memory_bytes: 55448
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
int n,t,a[200010]={};

int main(){
	cin >> n >> t;
	REP(i,0,n) cin >> a[i];

	ll s=0;
	REP(i,0,n){
		if(a[i+1]&&a[i+1]<a[i]+t) s+=a[i+1]-a[i];
		else s+=t;
	}
	
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

using mint=modint998244353;
struct S{
    mint a,sz,rp;
};

S op(S l,S r){
    return {l.a*r.sz+r.a,l.sz*r.sz,l.rp*r.sz+r.rp};
}

S e(){
    return {0,1,0};
}

S mapping(int l,S r){
    if(l) return {r.rp*l,r.sz,r.rp};
    return r;
}

int composition(int l,int r){
    if(l) return l;
    return r;
}

int id(){
    return 0;
}

void solve(){
    int n,q;
    cin>>n>>q;
    lazy_segtree<S, op, e, int, mapping, composition, id> seg(vector(n,S{1,10,1}));
    {
        int l,r,d;
        for(int i{};i<(q);++i){
            cin>>l>>r>>d;
            --l;
            seg.apply(l,r,d);
            cout<<seg.all_prod().a.val()<<endl;
        }
    }
}

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

Measured memory_bytes: 12732
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

ll N, M, K, Q;
string S;

int main() {
    cin >> S;
    int N = (int)S.size();
    bool flag = true;
    for (int i = 0; i <= N / 2; i++) {
        if (S[i] != S[N - 1 - i]) flag = false;
    }
    // cout << flag << endl;

    string s = "";
    int n = (N - 1) / 2;
    for (int i = 0; i < n; i++) {
        // cout << i << " ";  // debug
        s.push_back(S[i]);
    }
    //cout << endl;

    for (int i = 0; i <= (int)s.size() / 2; i++) {
        if (s[i] != s[n - 1 - i]) flag = false;
    }

    s = "";
    n = (N + 3) / 2;
    for (int i = n - 1; i < N; i++) {
        //cout << i << " ";  // debug
        s.push_back(S[i]);
    }
    //cout << endl;
    for (int i = 0; i <= (int)s.size() / 2; i++) {
        if (s[i] != s[(int)s.size() - 1 - i]) flag = false;
    }

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

    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int N=in();
	auto A=vecin<ll>(N);
	sort(ALL(A));
	vector<ll> S(N+1,0);
	REP(i,N){
		S[i+1] = S[i]+A[i];
	}
	int impossible=0;
	REP(i,N-1){
		if(2LL*S[i+1]<A[i+1]) impossible = i+1;
	}
	out(N-impossible);
	return 0;
}


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

const int N = 100003;
const int Under = -(1 << 30);
const int Up = (1 << 30);

struct node {int nxt, to;} E[N << 1];
int cnt = 0, point[N], fa[N];

void ins(int u, int v) {E[++cnt] = (node) {point[u], v}; point[u] = cnt;}

bool flag = true;
int n, l[N], r[N], mark[N], dep[N], m[N], num[N];

void dfs(int u) {
	for (int i = point[u]; i; i = E[i].nxt) {
		int v = E[i].to;
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs(v);
		l[u] = max(l[u], l[v] - 1);
		r[u] = min(r[u], r[v] + 1);
	}
}

void dfs2(int u) {
	for (int i = point[u]; i; i = E[i].nxt) {
		int v = E[i].to;
		if (v == fa[u]) continue;
		num[v] = num[u] + 1;
		if (!(l[v] <= num[v] && num[v] <= r[v]))
			num[v] = num[u] - 1;
		dfs2(v);
	}
}

int main() {
	scanf("%d", &n);
	int u, v;
	for (int i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v);
		ins(u, v); ins(v, u);
	}
	
	for (int i = 1; i <= n; ++i)
		l[i] = Under, r[i] = Up;
	
	int k;
	scanf("%d", &k);
	int vi, pi;
	for (int i = 1; i <= k; ++i) {
		scanf("%d%d", &vi, &pi);
		l[vi] = r[vi] = pi;
		mark[vi] = pi;
	}
	
	dfs(1);
	
	for (int i = 1; i <= n; ++i)
		if (mark[i]) {
			m[1] = ((mark[i] & 1) ^ (dep[i] & 1));
			break;
		}
	
	for (int i = 1; i <= n; ++i)
		m[i] = m[1] ^ (dep[i] & 1);
	
	for (int i = 1; i <= n; ++i)
		if (mark[i] && (mark[i] & 1) != m[i])
			{puts("No"); return 0;}
	
	for (int i = 1; i <= n; ++i) {
		if (l[i] > r[i]) {puts("No"); return 0;}
		if (l[i] == r[i] && (l[i] & 1) != m[i]) {puts("No"); return 0;}
	}
	
	puts("Yes");
	
	num[1] = l[1];
	if (m[1] != (num[1] & 1)) ++num[1];
	dfs2(1);
	
	for (int i = 1; i <= n; ++i) printf("%d\n", num[i]);
	return 0;
}

Measured memory_bytes: 10240
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using ll = long long;
using itn = int;
using namespace std;
int main(){
    int n;
    cin >> n;
    ll a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<n; i++){
        a[i] -= i;
    }
    sort(a,a+n);
    int value=a[n/2];
    for(int i=0; i<n; i++){
        a[i]-=value;
    }
    ll ans=0;
    for(int i=0; i<n; i++){
        ans += abs(a[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


#n,*a = [int(i) for i in read().split()]

h,w,k = [int(i) for i in readline().split()]
b = [readline() for _ in range(h)]

ans = INF = 10**9
N = 2**(h-1)


for mask in range(N):
    res = [(mask>>j)&1 for j in range(h-1)]
    
    R = []
    now = [0]
    for i in range(h-1):
        if res[i] == 0:
            now.append(i+1)
        else:
            R.append(now[:])
            now = [i+1]
    if now: R.append(now[:])
    
    L = len(R)
    val = res.count(1)

    num = [0]*L
    for i in range(w):
        nnum = [0]*L
        for j in range(L):
            p = 0
            for kk in R[j]:
                if b[kk][i]=="1": p += 1
            nnum[j] = p
        
        #print(R,i,num,nnum)
        for j in range(L):   
            if num[j] + nnum[j] > k:
                val += 1
                num = nnum
                break
        else:
            for j in range(L): num[j] += nnum[j]
        
        
        if any(ni>k for ni in nnum):
            val = INF
            break
    
    #print(val)
    ans = min(ans,val)

print(ans)






    

Measured memory_bytes: 51672
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using P = pair<int, int>;

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}


int main(){
	int n;
    cin >> n;
    vector<P> r(n), b(n);

    int x,y;
    rep(i,n){
        cin >> x >> y;
        r[i].first=y; r[i].second=x;
    }
    rep(i,n){
        cin >> x >> y;
        b[i].first=x; b[i].second=y;
    }
    sort(r.begin(), r.end(), greater<P>());
    sort(b.begin(), b.end());

    int ans=0;
    set<int> used_r;
    rep(i,n){
        int bx = b[i].first, by = b[i].second;
        rep(j,n){
            if(used_r.count(j)) continue;
            int rx = r[j].second, ry = r[j].first;
            if(rx < bx && ry < by){
                ans++;
                used_r.insert(j);
                break;
            }
        }
    }

    cout << ans << endl;


// failed attempt below

    // rep(i,n){
    //     int x,y;
    //     cin >> x >> y;
    //     r[i].first = x;
    //     r[i].second = y;
    // }
    // rep(i,n){
    //     int x,y;
    //     cin >> x >> y;
    //     b[i].first = x;
    //     b[i].second = y;
    // }
    
    // VVI RinB(n, VI(n, 0));
    // rep(i,n)rep(j,n){
    //     int rx,ry,bx,by;
    //     rx = r[i].first;
    //     ry = r[i].second;
    //     bx = b[j].first;
    //     by = b[j].second;
    //     if(rx < bx && ry < by) RinB[i][j] = 1;
    // }

    // int ans = 0;
    // while(1){
    //     int icnt=1000, jcnt=0, rr=-1, bb=-1;
    //     rep(i,n){
    //         int sum = 0;
    //         rep(j,n) sum += RinB[i][j];
    //         if(sum > 0) if(chmin(icnt, sum)) rr = i;
    //     }
    //     if(rr == -1) break;

    //     rep(j,n){
    //         if(RinB[rr][j] == 0) continue;
    //         int sum = 0;
    //         rep(i,n) sum += RinB[i][j];
    //         if(chmax(jcnt, sum)) bb=j;
    //     }

    //     rep(j,n) RinB[rr][j] = 0;
    //     rep(i,n) RinB[i][bb] = 0;
    //     ans++;
    // }
    
    // cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>

using namespace std;
typedef long long ll;
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;}
const ll INF = 1e18+1;

int N, M;
/*
aiとbiの間の区間に1が少なくとも一つあるようにする
全てのaiとbiの間にそれを実現するための必要な1の最小数

全部被った区間があったら1でよい

にぶたんだろ
ある数以上あったらすべて分断できる
それ未満ならできない

->

1の数xコのときに、すべてのaiとbiの間を分断できるかどうか->やるまでもなかった ソート貪欲

終端ソートして、それまで分断した部分の最大値を保存


-
--
---
----
 -
 --
 ---
  -
  --
   -

-
--
 -
---
 --
  -
----
 ---
  -- 
   -


3 5
4 6
2 7
1 8
7 9

島を0~N-1,各区間を0~N-2でナンバリング


*/

int main() {
    cin >> N >> M;
    vector<pair<int,int> > p(M);
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b; a--; b--;
      p[i] = make_pair(b,a);
    }
    sort(p.begin(),p.end());

    int lb = -1, res = 0;
    for (int i = 0; i < M; i++) {
      if (p[i].second >= lb) {
        res++;
        lb = p[i].first;
      }
    }

    cout << res << endl;


    


}

Measured memory_bytes: 1024
n=int(input())

ue=list(map(int,input().split()))
sita=list(map(int,input().split()))
mmax=0
for k in range(n):
    sum=ue[k]+sita[k]
    for l in range(k):
        sum=sum+ue[l]
    for m in range(k+1,n):
        sum=sum+sita[m]

    if mmax<sum:
        mmax=sum

print(mmax)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> P;

int main() {
  int n;
  cin >> n;
  P a[n];
  for(int i=0; i<n; i++) cin >> a[i].first >> a[i].second;
  P p=P(a[0].first+a[n/2].first,a[0].second+a[n/2].second);
  bool ok=1;
  for(int i=1; i<n/2; i++) {
    if(p!=P(a[i].first+a[i+n/2].first,a[i].second+a[i+n/2].second)) ok=0;
  }
  if(!ok || n%2) cout << "NA" << endl;
  else printf("%.10f %.10f\n",p.first/2,p.second/2);
  return 0;
}


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

typedef pair<int,int> P;
int h, w;
bool ans;

void debug(vector<string> s){
	cout << "[debug]" << endl;
	for(int y=0 ; y < h ; y++ ){
		cout << s[y] << endl;
	}
	cout << endl;
}

// ツ債カツ湘」ツづ?右ツ可コツづ個催?標ツづーツ陛板つキ
pair<P,P> get_size(const vector<string>& s, char c){
	int max_x=0, max_y=0, min_x=1e+8, min_y=1e+8;
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			if( s[y][x] == c ){
				max_x = max( max_x , x );
				max_y = max( max_y , y );
				min_x = min( min_x , x );
				min_y = min( min_y , y );
			}
		}
	}
	return pair<P,P>( P(min_x,min_y) , P(max_x,max_y) );
}

// ツ陳キツ陛サツ形ツつゥツ陳イツづ猟づゥ
bool is_rect(const vector<string>& s, char c){
	pair<P,P> pp = get_size( s , c );
	
	int min_x = pp.first.first;
	int min_y = pp.first.second;
	int max_x = pp.second.first;
	int max_y = pp.second.second;
	//cout << "char c : " << c << " (" << min_x << "," << min_y << ") , (" << max_x << "," << max_y << ")" << endl;
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			if( min_x <= x && min_y <= y && x <= max_x && y <= max_y ){
				if( s[y][x] == c || s[y][x] == '*' ){
				}else{
					return false;
				}
			}else{
				if( s[y][x] == c ) return false;
			}
		}
	}
	return true;
}

// ツ嘉猟閉ィツづーツ偲ヲツづィツ渉慊つュ
vector<string> remove(vector<string> s, char c){
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			if( s[y][x] == c ){
				s[y][x] = '*';
			}
		}
	}
	return s;
}

// memo[i] : iツ氾板姪堋づ個嘉猟閉ィツづーツ陳イツづ猟つスツつゥツづ?つ、ツつゥ, vc[i] : iツ氾板姪堋づ個嘉猟閉ィツづーツ表ツつキツ閉カツ篠?
// s : w*hツづ個湘ウツ妥? cnt : ツ偲ヲツづィツ渉慊つ「ツつスツ嘉猟閉ィツづ個青?
void solve(vector<bool> memo, vector<char> vc, vector<string> s, int cnt){
	if( ans ) return;
	if( cnt == vc.size() ){
		ans = true;
		return;
	}
	
	for(int i=0 ; i < vc.size() ; i++ ){
		if( memo[i] ) continue;
		//debug( s );
		char c = vc[i];
		if( is_rect( s , c ) ){
			memo[i] = true;
			s = remove( s , c );
			//debug( s );
			solve( memo , vc , s , cnt+1 );
			memo[i] = false;
		}
	}
}

int main(){
	int T;
	cin >> T;
	for(int i = 0 ; i < T ; i++ ){
		cin >> h >> w;
		vector<string> s;
		for(int y=0 ; y < h ; y++ ){
			string s_;
			cin >> s_;
			s.push_back( s_ );
		}

		int f[256] = {0};
		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				char c = s[y][x];
				if( c >= 'A' && c <= 'Z' ){
					f[c] = 1;
				}
			}
		}
		vector<char> vc;
		for(char c='A' ; c <= 'Z' ; c++ ){
			if( f[c] ){
				vc.push_back( c );
			}
		}

		//debug( s );
		if( vc.size() == 0 ){
			cout << "SAFE" << endl;
		}else{
			ans = false;
			vector<bool> memo( (int)vc.size() , false );
			solve( memo , vc , s , 0 );
			if( ans ){
				cout << "SAFE" << endl;
			}else{
				cout << "SUSPICIOUS" << endl;
			}
		}
	}
}

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


def get_node_count(n):
    sum = 0
    for i in range(10**6):
        sum += i
        if sum == n:
            return i+1
        if sum > n:
            return False


def main():
    n = int(input())
    k = get_node_count(n)
    if not k:
        print("No")
        return

    nodes = [[] for _ in range(k)]
    edges = []
    dup_num = 1
    for from_ in range(k-1):
        for to in range(from_+1, k):
            edge = (from_, to, dup_num)
            edges.append(edge)
            dup_num += 1

    for from_, to, num in edges:
        nodes[from_].append(num)
        nodes[to].append(num)

    print("Yes")
    print(k)
    for node in nodes:
        print(k-1, *node)


if __name__ == "__main__":
    main()


Measured memory_bytes: 23312
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {
			// TODO 172_C
			Scanner sc = new Scanner(System.in);

			int iMax = 0;

			int N = sc.nextInt();
			int M = sc.nextInt();
			long K = sc.nextLong();

			Long[] lA = new Long[N+1];
			Long[] lB = new Long[M+1];

			int i = 0;

			lA[0] = (long) 0;
			lB[0] = (long) 0;

			for(i=1; i<N+1; i++) {
					lA[i] = lA[i-1] + sc.nextLong();
			}
			for(i=1; i<M+1; i++) {
					lB[i] = lB[i-1] + sc.nextLong();
			}
			// Scannerクラスのインスタンスをクローズ
			sc.close();

			int b = M;
			while(lB[b] > K) {
				b--;
			}
			iMax = b;

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

				if(lA[a] > K) {
					break;
				}

				// Aからa冊読むとして
				// 残りをBから読めるだけ読む
				while(lA[a] + lB[b] > K) {
					b--;
				}

				// 最大冊数を更新
				if (iMax < a+b) {
					iMax = a+b;
				}

			}

    		System.out.println(iMax);
    	}
    }

Measured memory_bytes: 72176
N = int(input())
S = input()

d = {"W" : 0, "E" : 0}
for i in range(N):
    d[S[i]] += 1

t = {"W" : 0, "E" : 0}
ans = 300000
for i in range(N):
    ans = min(ans,t["W"] + d["E"] - t["E"] - (S[i] != "W"))
    t[S[i]] += 1
print(ans)
        


Measured memory_bytes: 3700
H, W, K = map(int, input().split())
cw = [input() for i in range(H)]

cnt = 0
for cols in range(2**H):
    for rows in range(2**W):
        black = 0
        for i in range(H):
            for j in range(W):
                if ((cols >> i) & 1) == 0 and ((rows >> j) & 1) == 0:
                    if cw[i][j] == '#':
                        black += 1
        if black == K:
            cnt += 1
print(cnt)


Measured memory_bytes: 9128
#include<iostream>
#include<vector>
#include<algorithm>

int main(){

    size_t n, prev = 0;
    size_t cnt = 0;
    
    std::cin >> n;
    
    std::vector<size_t> v;

    for(size_t i = 0; i < n; i++){
        size_t h;
        std::cin >> h;
        if(h <= prev){
            cnt++;
        }else{
            v.emplace_back(cnt);
            cnt = 0;
        }
        prev = h;
    }

    v.emplace_back(cnt);

    std::cout << *std::max_element(v.begin(), v.end()) << std::endl;
    
    return 0;
}


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

int main()
{
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a.at(i);
    }
    int j = 1;
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        j = a.at(j - 1);
        count++;
        if (j == 2)
            break;
    }
    if (count == N)
    {
        cout << -1 << "\n";
    }
    else
    {
        cout << count << "\n";
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int n, l;
	cin >> n >> l;
	vector<string> s(n);
	for(int i = 0;i < n;i++){
		cin >> s[i];
	}
	sort(s.begin(), s.end());
	
	string ans;
	
	for(int i = 0;i < n;i++){
		ans += s[i];
	}
	
	cout << ans;
}
	
	

Measured memory_bytes: 256
x=int(input())
ans=0
if x==1:
    print(1)
else:
    for i in range(2,32):
        p=2
        while i**p<=x:
            if i**(p+1)>x:
                a=i**p
                break
            else:
                p +=1
        ans=max(ans,a)
    print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include<bits/stdc++.h>
#define ll int
using namespace std;

vector<pair<ll,ll>> v;
vector<double> ans;

double dist(ll a, ll b, ll a1, ll b1)
{
    double k = (double)sqrt((double)((a-a1)*(a-a1)) + (double)((b-b1)*(b-b1)));
    return k;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll n;cin>>n;
    
    
    for(ll i=0;i<n;i++)
    {
        ll a,b;cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end());
    bool flag = true;
    while(flag)
    {
        double k = 0.0;
        for(ll i=0;i<n-1;i++)
        {
            double di = (double)dist(v[i].first,v[i].second,v[i+1].first,v[i+1].second);    
            k += (double)di;
        }
        ans.push_back(k);
        flag = next_permutation(v.begin(),v.end());
        
    }
    double sum = 0.0;
    
    for(ll i=0;i<ans.size();i++)
    {
        sum+=ans[i];
    }
    sum = (double)sum/ans.size();
    
    cout<<setprecision(10)<<sum<<endl;
    
    return 0;
    
}


Measured memory_bytes: 892
N=int(input())
Destinations=[[0,0,0]]
for i in range(N):
    Destinations.append(list(map(int, input().split())))

for i in range(N):
    x_distance = Destinations[i+1][1] - Destinations[i][1]
    y_distance = Destinations[i+1][2] - Destinations[i][2]
    if x_distance < 0:
        x_distance = -x_distance
    if y_distance < 0:
        y_distance = -y_distance
    move_distance = x_distance+y_distance

    move_time = Destinations[i+1][0] - Destinations[i][0]

    if move_distance == 0:
        print("No")
        break

    if move_distance > move_time*1:
        print("No")
        break
    elif move_distance%2 == move_time%2:
        pass
    else:
        print("No")
        break

    if i == N-1:
        print("Yes")

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

using namespace std;

const int N = 1e5+200;
int a[N],ans;

int main(){

    int n,k;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
      cin >> a[i];
    }
    k = a[0];
    for(int i= 0; i < n; i ++)
    {
        if(i == n -1)
        {
            if(a[i] >= k) k = a[i];
            ans+=k;
        }
        else
        {
            if(a[i] >= k) k = a[i];
            else
            {
                ans += k - a[i];
                k = a[i];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

int main (int argc, char *argv[]) {
    int n, Y, M, D;

    // prepare
    const int b = 20;
    const int s = 19;
    int total = 0;
    for (int i = 1; i < 1000; ++i) {
        if ( i % 3 == 0) {
            total += b * 10;
        }
        else total += b * 5 + s * 5;
    }
    total += 1;

    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>Y>>M>>D;
        int input = 0;
        // Y
        for (int j = 1; j < Y; ++j) {
            if (j % 3 == 0) {
                input += b * 10;
            }
            else input += b * 5 + s * 5;
        }
        // M
        if (Y % 3 == 0) {
            input += b * (M - 1);
        }
        else {
            for (int k = 1; k < M; ++k) {
                if (k % 2 == 0) {
                    input += s;
                }
                else input += b;
            }
        }
        // D
        input += D;

        // ans
        cout<<total - input<<endl;
    }
    return 0;
}

Measured memory_bytes: 3016
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXN 500000
struct node {
	int key;
	node *ch[2];
};
node tree[MAXN+5];
node *Root, *NIL, *ncnt;
void Init(){
	NIL = &tree[0];
	ncnt = &tree[1];
	Root = NIL;
}
inline node *NewNode(int val) {
	node * p = ++ncnt;
	p->key = val;
	p->ch[0] = p->ch[1] = NIL;
	return p;
}
void Insert(node * &rt, int val) {
	if(rt == NIL) {
		rt = NewNode(val);
		return ;
	}
	int d = (val >= rt->key);
	Insert(rt->ch[d], val);
}
void PreOrder(node *rt) {
	if(rt == NIL) return;
	printf(" %d", rt->key);
	PreOrder(rt->ch[0]);
	PreOrder(rt->ch[1]);
}
void InOrder(node *rt) {
	if(rt == NIL) return;
	InOrder(rt->ch[0]);
	printf(" %d", rt->key);	
	InOrder(rt->ch[1]);
}
int main() {
	int n, x;
	char op[100];
	Init();
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%s", op);
		if(op[0] == 'i') {
			scanf("%d", &x);
			Insert(Root, x);
		}
		else {
			InOrder(Root);
			puts("");
			PreOrder(Root);
			puts("");			
		}
	}
	return 0;
}

Measured memory_bytes: 14468
#include <stdio.h>
int main(void){
    // Your code here!
    int a,b,c;
    int cnt = 0;
    
    scanf("%d%d%d",&a,&b,&c);
    
    if(a != b && b != c && a != c){
        cnt = 3;
    }
    else if(a == b && b == c){
        cnt = 1;
    }
    else{
        cnt = 2;
    }
    
    printf("%d\n",cnt);
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long a, b;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        if(b>a)
            printf("%lld\n",(b-2*a)/4+a);
        else
            printf("%lld\n",b/2);

    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;
 
    int limit = 24*3600;
    int data[limit];
    for(int i = 0; i < limit; i++) {
      data[i] = 0;
    }
 
    for(int i = 0; i < n; i++) {
      int h, m, s;
      int ss, gs;
      scanf("%d:%d:%d", &h, &m, &s);
      ss = h*3600 + m*60 +s;
      scanf("%d:%d:%d", &h, &m, &s);
      gs = h*3600 + m*60 +s;
      for(int j = ss; j < gs; j++) {
        data[j]++;
      }
    }
 
    int max = -1;
    for(int i = 0; i < limit; i++) {
      if(data[i] > max) max = data[i];
    }
 
    cout << max << endl;
  }
  return 0;
}

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

static const int maxn=10000;

struct Node {
  int p,l,r;
};

Node T[maxn];

void preParse(int u) {
  if (u==(-1)) {
    return ;
  }
  cout<<" "<<u<<flush;
  preParse(T[u].l);
  preParse(T[u].r);
}
void inParse(int u) {
  if (u==(-1)) {
    return ;
  }
  inParse(T[u].l);
  cout<<" "<<u<<flush;
  inParse(T[u].r);
}
void postParse(int u) {
  if (u==(-1)) {
    return ;
  }
  postParse(T[u].l);
  postParse(T[u].r);
  cout<<" "<<u<<flush;
}

int main() {
  std::ios::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int n;
  cin>>n;
  for (int i=0; i<n; i++) {
    T[i].p=(-1);
  }
  for (int i=0; i<n; i++) {
    int v,l,r;
    cin>>v>>l>>r;
    T[v].l=l;
    T[v].r=r;
    if (l!=(-1)) {
      T[l].p=v;
    }
    if (r!=(-1)) {
      T[r].p=v;
    }
  }
  int root=0;
  for (int i=0; i<n; i++) {
    if (T[i].p==(-1)) {
      root=i;
    }
  }
  cout<<"Preorder"<<endl;
  preParse(root);
  cout<<endl;
  cout<<"Inorder"<<endl;
  inParse(root);
  cout<<endl;
  cout<<"Postorder"<<endl;
  postParse(root);
  cout<<endl;
  return 0;
}


Measured memory_bytes: 3176
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<string>

using namespace std;


int main(){

	while(1){
		int n,r;	
		cin >> n >> r;
		if(n==0&&r==0) break;
		vector<int> huda(n);
		for(int i=0;i<n;i++) huda[i]=n-i;
		
		for(int i=0;i<r;i++){
			int p,c;
			cin >> p >> c;
			p--;c--;
			for(int j=c;j>=0;j--){
				int a = huda[p+c];
				huda.erase(huda.begin()+p+c);
				huda.insert(huda.begin(),a);
			}
		}

		cout << huda[0] << endl;
	}
}

Measured memory_bytes: 1224
// finish date: 2018/01/20
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000


int main() {
    string X, Y;
    cin >> X >> Y;
    if (X > Y) cout << ">" << endl;
    else if (X == Y) cout << "=" << endl;
    else cout << "<" << endl;
    return 0;
}


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

int main() {
  int K;
  string S;
  cin >> K >> S;
  
  if (S.size() <= K) {
    cout << S << endl;
  }
  else { for (int i = 0; i < K; i++) {
      cout << S.at(i);
    }
    cout << "..." << endl;
  }
}


Measured memory_bytes: 3616
S = input()
max_len = 0
for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        s = S[i:j]
        s = s.replace('A', '.')
        s = s.replace('T', '.')
        s = s.replace('G', '.')
        s = s.replace('C', '.')
        flag = True
        for ss in s:
            if ss != '.':
                flag = False
        if flag:
            if max_len < len(s):
                max_len = len(s)
print(max_len)


Measured memory_bytes: 3064
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()
/* libraries */

constexpr int MOD = 1e9+7;
struct mint
{
	int v;
	mint():v(0){}
	mint(int v):v((v+MOD)%MOD){}
	mint operator-()const{ return mint(0) - *this; }
	mint& operator+=(const mint& a){ if((v+=a.v)>=MOD) v-=MOD; return *this; }
	mint& operator-=(const mint& a){ if((v+=MOD-a.v)>=MOD) v-=MOD; return *this; }
	mint& operator*=(const mint& a){ (v*=a.v)%=MOD; return *this; }
	mint& operator/=(const mint& a){ (*this) *= a.inv(); return *this; }
	mint operator+(const mint& a)const{ return mint(*this) += a; }
	mint operator-(const mint& a)const{ return mint(*this) -= a; }
	mint operator*(const mint& a)const{ return mint(*this) *= a; }
	mint operator/(const mint& a)const{ return mint(*this) /= a; }
	bool operator<(const mint& a)const{ return v < a.v; }
	bool operator==(const mint& a)const{ return v == a.v; }
	mint pow(int k)const{ mint r(1),t(v); while(k){ if(k&1) r*=t; t*=t; k>>=1; } return r; }
	mint inv()const{ return pow(MOD-2); }
	static mint comb(int n, int k) {
		if(n-k<k) k=n-k;
		mint num(1), dom(1);
		for(int i=0;i<k;i++) { num*=n-i; dom*=i+1; }
		return num/dom;
	}
};
std::istream& operator>>(std::istream&i,mint&a){ int t; i>>t; a=mint(t); return i; }
std::ostream& operator<<(std::ostream&o,const mint&a){ o<<a.v; return o; }


signed main() {
	std::string l;
	std::cin >> l;

	int n = l.size();

	mint count = 0;
	int ones = 0;
	rep(i,n) {
		if(l[i]=='1') {
			count+=mint(2).pow(ones)*mint(3).pow(n-i-1);
			ones++;
		}
	}
	count+=mint(2).pow(ones);
	print(count);
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<math.h>
#define N 100

using namespace std;
int main()
{
	int n;
	int total = 0;
	int A[N];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = n - 1; j > 0; j--)
		{
			if (A[j] < A[j - 1])
			{
				swap(A[j], A[j - 1]);
				total++;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << A[i];
		if (i < n - 1)
			cout << ' ';
	}
	cout << endl;
	cout << total << endl;
	return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const long long INF = 1LL << 60;
const int MOD = 1000000007;
using ping = pair<ll, ll>;

int main(){
    ll N;
    cin >> N;
    vector<ll> X(N);
    vector<ll> orderd(N);
    for (int i = 0; i < N; i++) {
      ll a;
      cin >> a;
      X[i] = a, orderd[i] = a;
    }

    sort(orderd.begin(), orderd.end());

    for (int i = 0; i<N; i++){
      if(X[i]<=orderd[N/2-1]){
        cout << orderd[N / 2] << endl;
      }
      else{
        cout << orderd[N/2-1] << endl;
      }
    }
    return 0;
}

Measured memory_bytes: 6404
fun main(args: Array<String>) {
  val K = readInt()
  val S = readString()
  if (S.length <= K) {
    println(S)
  } else {
    println("${S.substring(0 until K)}...")
  }
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readLong() = readString().toLong()
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }


Measured memory_bytes: 36016
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int h = sc.nextInt();
		int w = sc.nextInt();

		int black = H * W;

		int white = h * W;
		H = H - h;
		white += w * H;
		System.out.println(black - white);

	}

}


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

int main(){


  int used;
  while(1){
    cin >> used ;
    if(used == -1) break;
    int cost=0;

    if(30 < used){
      cost += 160 * (used-30);
      used = 30;
    }
    if(20 < used){
      cost += 140 * (used-20);
      used = 20;
    }
    if(10 < used ){
      cost += 125 * (used-10);
      used = 10;
    }
    if(used <= 10){
      cost += 1150;
    }


    cout << 4280 - cost << "\n";

  }


}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
const int P=1e9+7,maxn=2e5+10;
int n,s[maxn],l[maxn],r[maxn],dp[maxn],tot,ans,fxk,j;
struct psc{int x,v,id;}a[maxn];
struct ask{int l,r;}b[maxn];
inline bool operator <(psc a,psc b){return a.v<b.v;}
inline bool cmp(psc a,psc b){return a.x<b.x;}
inline bool operator <(ask a,ask b){return a.l<b.l||a.l==b.l&&a.r<b.r;}
int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d",&a[i].x,&a[i].v);
    sort(a+1,a+n+1);
    rep(i,1,n) a[i].id=i;
    sort(a+1,a+n+1,cmp);fxk=n+1;
    per(i,n,1) fxk=min(fxk,a[i].id),l[a[i].id]=fxk;
    fxk=0;
    rep(i,1,n) fxk=max(fxk,a[i].id),r[a[i].id]=fxk;
    //rep(i,1,n) printf("%d %d\n",l[i],r[i]);
    rep(i,1,n) b[i].l=l[i],b[i].r=r[i];sort(b+1,b+n+1);
    dp[0]=tot=1;
    rep(i,1,n){
        while(j<i&&b[j].r+1<b[i].l) tot=(tot-dp[j]+P)%P,++j;
        dp[i]=tot;tot=(tot+dp[i])%P;
    }
    j=n;
    while(b[j].r==n) ans=(ans+dp[j])%P,--j;
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<stack>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

int main(){
	string s;
	cin>>s;
	rep(i,s.size())s[i]='x';
	cout<<s<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const long long INF = 1e15;
using namespace std;

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

    long long a = 0, b = 0;
    vector<long long> v(n);
    rep(i,n) {
        cin >> v[i];
        b += v[i];
    }

    long long ans = INF;
    rep(i,n - 1){
        a += v[i];
        b -= v[i];
        ans = min(ans, abs(a - b));
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <assert.h>   
#include <vector>
#include <algorithm>
#include <time.h>
#include <numeric>
#include <string>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <numeric>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
using namespace std;


//#define double long double
//#define int long long
//#define int unsigned long long

#define ll long long
#define ld long double 
#define pi pair<int, int> 
#define pl pair<ll,ll>  
#define pd pair<ld,ld> 
#define str string  
#define mp make_pair
#define vi vector<int> 
#define vl vector<ll> 
#define vd vector<ld> 
#define vs vector<str> 
#define vpi vector<pi> 
#define vpl vector<pl> 
#define vpd vector<pd> 
#define si set<int> 
#define FF(i,j,n) for(signed i=j;i<=n;i++)  
#define DD(i,j,n) for(signed i=j;i>=n;i--) 
#define F(i,j,n) for(signed i=j;i<n;i++)   
#define D(i,j,n) for(signed i=j;i>n;i--) 
#define mem(a,b) memset(a,b,sizeof(a))
#define ndl cout << endl
#define ull unsigned long long 

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;


#define sz(x) (signed)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back() 
#define X first
#define Y second
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


const int mod = 1e9 + 7;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 


//DEBUG, compile with -DLOCAL
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL 
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define HERE cout << "===GOTHERE===" << endl
#else
#define dbg(...) 42
#define HERE 42
#endif


 /* ============== END OF HEADER ============== */





const int maxn = 1e5*3+20;

int a[3000];

int n,_,q,k;

void solve(){
	cin >> n;
	F(i,0,n) cin >> a[i];
	sort(a,a+n);
	int cnt = 0;
	F(i,0,n){
		F(j,1,i){
			dbg(a[i], a[j]);
			int third = a[i] - a[j];
			int search = j - (upper_bound(a, a+j, third) - a);
			cnt += search;
		}
	}
	cout << cnt;
}

signed main(){
  //clock_t t1 = clock();  
	IOS
	solve();
  
  //cout << "THE ALGORITHM TOOK: " << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms"<< endl;
	return 0;
}

Measured memory_bytes: 3180
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,n) for(int i=1; i<=(n); i++)

int main() {
    int n,ans=0;
    cin>>n;
    vector<int>p(n);
    rep(i,n)cin>>p[i];
    rep(i,n-2){
        if((p[i]-p[i+1])*(p[i+1]-p[i+2])>0)ans++;
    }
    
    
    cout<<ans;
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    int N,v,j;
    cin >> N;
    int A[N];
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    
    cout << A[0];
    for(int i=1;i<N;i++){
        cout << " " << A[i] ;
    }
    cout << endl;
    
    for(int i=1; i<N; i++){
        v=A[i];
        j=i-1;
        while(j>=0 && A[j]>v){
            A[j+1] = A[j];
            j--;
            A[j+1] = v;
        }
        cout << A[0];
        for(int i=1;i<N;i++){
            cout << " " << A[i] ;
        }
        cout << endl;
    }
}



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


int main() {
	ll N;
	cin >> N;
	vector<ll>A(N);
	rep(0, N) {
		cin >> A[i];
	}

	ll count=0;
	ll tmp = 1;
	rep(0, N) {
		if (A[i] != tmp) {
			count++;
		}
		else {
			tmp++;
		}

	}
	if (tmp == 1) {
		cout << -1 << endl;
		return 0;
	}
	cout << count << endl;
}


Measured memory_bytes: 1792
N = int(input())
h = [int(i) for i in input().split()]
h.append(0)

cnt = 0
for H in range(max(h)):
    #print(h)
    for i in range(N):
        if h[i] >0:
            h[i] -= 1
            if h[i+1] == 0:
                cnt +=1

print(cnt)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  #define int long
  int k,a,b,ck=1,yn=0;
  cin>>k>>a>>b;
  if(a+2>=b)ck=k+1;
  else {
    int t=(k-a-2)/2;
    k-=a+2*t+1;
    ck=(t+1)*b-t*a; yn=0;
    if(k==1)ck++;
    else if(k==2)ck+=b-a;
    else cerr<<"wtf";
  }
  cout<<ck;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    for i in range(N):
        min_dist = 10**9
        min_index = None
        for j in range(M):
            dist = abs(a[i]-c[j])+abs(b[i]-d[j])
            if dist < min_dist:
                min_dist = dist
                min_index = j
        
        print(min_index+1)


    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int()] * (M)  # type: "List[int]"
    d = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, a, b, c, d)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316