akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (int y = 0; y < H; y++) cin >> S[y];

  struct Point {
    int x;
    int y;
    int t;
  };

  const int dx[] = {-1, 0, +1, 0};
  const int dy[] = {0, -1, 0, +1};
  int answer = 0;
  for (int sy = 0; sy < H; sy++) {
    for (int sx = 0; sx < W; sx++) {
      if (S[sy][sx] == '#') continue;
      queue<Point> q;
      q.push({sx, sy, 0});

      vector<vector<bool>> visit(H, vector<bool>(W, false));
      visit[sy][sx] = true;
      int max_dist = 0;
      while (!q.empty()) {
        Point p = q.front();
        q.pop();

        max_dist = max(max_dist, p.t);

        for (int d = 0; d < 4; d++) {
          int nx = p.x + dx[d];
          int ny = p.y + dy[d];
          if (nx < 0 || W <= nx || ny < 0 || H <= ny) continue;
          if (visit[ny][nx]) continue;
          if (S[ny][nx] == '#') continue;
          q.push({nx, ny, p.t + 1});
	  visit[ny][nx] = true;
        }
      }
      answer = max(answer, max_dist);
    }
  }

  cout << answer << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] arg) {
        try {
            Scanner scan = new Scanner(System.in);
            int i = 1;
            while (scan.hasNext()) {
                int x = scan.nextInt();
                if (i > 10000) {
                    break;
                }
                if (0 < x && x < 10001) {
                    System.out.println("Case " + i + ": " + x);
                    i++;
                }
            }
        } catch (InputMismatchException ex) {
            System.out.println("??´??°?????\?????????????????????");
        }
    }
}

Measured memory_bytes: 42516
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll gcd(int a,int b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(int a,int b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll INFS=1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);

int main() {//   4 5 6 7 8 9
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll cntc=b/c-(a-1)/c;
  ll cntd=b/d-(a-1)/d;
  ll cntcd=b/(lcm(c,d))-(a-1)/(lcm(c,d));
  ll cnt=cntc+cntd-cntcd;
  ll ans=b-a+1-cnt;
  cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define INF 100000000000
#define MAX 200001
#define MOD 1000000007

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    ll ans = 0;
    vector<ll> A(N + 1);
    vector<ll> B(M + 1);
    A[0] = 0;
    B[0] = 0;
    for(int i = 1; i < N + 1; i++) cin >> A[i];
    for(int i = 1; i < M + 1; i++) cin >> B[i];
    for(int i = 1; i < N + 1; i++) A[i] += A[i - 1];
    for(int i = 1; i < M + 1; i++) B[i] += B[i - 1];
    for(ll i = 0; i < N + 1; i++){
        int a = A[i];
        int t = K - a;
        if(t < 0) break;
        auto iter = upper_bound(B.begin(), B.end(), t);
        ll index1 = iter - B.begin();
        ans = max(ans, i + index1 - 1);
    }
    cout << ans << endl;
}   

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

int where(int *ar, int key,int size) {
	int c, f = 0, e = size;
	c = e / 2;
	while (f < e) {
		if (ar[c] == key) {
			return c;
		}else{
			if(ar[c] > key){
				//goto left
				e = c;
			}else{
				f = c+1;
			}
		}

		c = (f+e)/2;
	}
	return -1;
}

int main() {

	int cnt = 0;
	ios::sync_with_stdio(false);
	int tmp1,tmp2;
	cin >> tmp1;
	int ar1[tmp1];
	for (int i = 0; i < tmp1; i++)
		cin >> ar1[i];

	cin >> tmp2;
	int ar2[tmp2];
	for (int i = 0; i < tmp2; i++){
		cin >> ar2[i];
		if(where(ar1, ar2[i],tmp1) != -1){
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 3684
#include <cstdio>
#include <iostream>
#include <map>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
using namespace std;

map<int, int> table;

int main(void) {
  int n;
  scanf("%d", &n);
  REP(i, n) {
    int v;
    scanf("%d", &v);
    table[v]++;
  }
  int res = 0;
  FOR(it, table) {
    if(it->second % 2 == 1) {
      ++res;
    }
  }
  printf("%d\n", res);
  return 0;
}


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

using namespace std;

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

  int n;
  cin >> n;

  map<string, int> m;

  int cmd, val;
  string key;
  for (int i = 0; i < n; i++) {
    cin >> cmd;
    if (cmd == 0) {
      cin >> key >> val;
      // m.insert(make_pair(key, val));
      m[key] = val;
    } else {
      cin >> key;
      cout << m.at(key) << endl;
    }
  }
}




Measured memory_bytes: 25880
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		boolean cont=true;
		while(cont){
			String[] ary = br.readLine().split(" ");
	        int a = Integer.parseInt(ary[0]);
	        int b = Integer.parseInt(ary[2]);
	        switch(ary[1].charAt(0)){
	        case '+':
	        	sb.append(a+b+"\n");
	        	break;
	        case '-':
	        	sb.append(a-b+"\n");
	        	break;
	        case '*':
	        	sb.append(a*b+"\n");
	        	break;
	        case '/':
	        	sb.append(a/b+"\n");
	        	break;
	        default:
	        	System.out.print(sb);
	        	cont=false;
	        	break;
	        }
		}
	}
}

Measured memory_bytes: 24360
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
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 (a > b) {a = b; return 1;} return 0; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール

// 処理内容
int main() {
    
    ll n; cin >> n;
    vector<vector<pair<ll, ll>>> g(n); // {dst, parity}
    REP(i, n-1) {
        ll u, v, w; cin >> u >> v >> w;
        u--; v--; // 0-indexed
        g[u].emplace_back(v, w % 2);
        g[v].emplace_back(u, w % 2);
    }

    vector<bool> visited(n, false);
    vector<bool> parity(n, 0);
    deque<ll> q = {0};
    visited[0] = true;
    parity[0] = 0;
    while (!q.empty()) {

        ll v = q.front();
        q.pop_front();

        for (auto &nbrp : g[v]) {
            ll nbr = nbrp.first;
            ll prt = nbrp.second;
            if (visited[nbr]) continue;
            visited[nbr] = true;
            parity[nbr] = parity[v] ^ prt;
            q.push_back(nbr);
        }

    }

    REP(i, n) {
        cout << parity[i] << endl;
    }
    
}

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

int main() {
  string s;
  cin >> s;
  if(s == "SUN") cout << '7' << endl;
  if(s == "MON") cout << '6' << endl;
  if(s == "TUE") cout << '5' << endl;
  if(s == "WED") cout << '4' << endl;
  if(s == "THU") cout << '3' << endl;
  if(s == "FRI") cout << '2' << endl;
  if(s == "SAT") cout << '1' << endl;
}


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

// input
int N;
vector<int> A;


void input() {
    cin >> N;
    A = vector<int>(N);
    rep(i, N) cin >> A[i];
}


int main() {
    input();
    set<int> s;
    for (int a : A) {
        if (s.count(a)) s.erase(a);
        else s.insert(a);
    }
    int ans = s.size();
    cout << ans << endl;
}


Measured memory_bytes: 8116
#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> P;

int main() {
    int w, h;
    int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
    int map[50][50];
    while (true) {
        int count = 0;
        cin >> w >> h;
        if (w == 0) {
            return 0;
        }
        for (int y=0; y<h; y++) {
            for (int x=0; x<w; x++) {
                cin >> map[x][y];
            }
        }
        for (int y0=0; y0<h; y0++) {
            for (int x0=0; x0<w; x0++) {
                queue<P> q;
                if (map[x0][y0] == 0) {
                    continue;
                }
                count++;
                q.push(P(x0, y0));
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for (int i=0; i<8; i++) {
                        int nx = x+dx[i];
                        int ny = y+dy[i];
                        if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
                            continue;
                        }
                        if (map[nx][ny] == 0) {
                            continue;
                        }
                        map[nx][ny] = 0;
                        q.push(P(nx, ny));
                    }
                }
            }
        }
        cout << count << endl;
    }
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#include <string>
#include <vector>
/* 変数i を n回繰り返すマクロ */
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
int main()
{
    cout << fixed << setprecision(10);//小数点以下10桁出力
    int h,a;
    cin >> h >> a;
    int cnt = 0;
    while(h > 0){
        h -= a;
        cnt++;
    }   
    cout << cnt << endl;
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<float> v(N);
  for(int i=0; i<N; i++){
    cin >> v.at(i);
  }
  int i=0;
  float tmp;
  sort(v.begin(),v.end());

  while(v.size()!=1){
    tmp=(float)(v.at(i)+v.at(i+1))/2.0;
    v.at(i+1)=tmp;
    v.erase(v.begin());
  }
  cout << (float)v.at(0) << endl;

}

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

char r[10500];
int main(){
    int p = 0;
    int res = 0;
    while(~(r[p]=getchar())){
	if('0' <= r[p] && r[p] <= '9'){
	    p++;
	    r[p + 1] = 0;
	    continue;
	}
	else{
	    int t;
	    if(1==sscanf(r, "%d", &t))res += t;
	    p = 0;
	    r[p + 1] = 0;
	}
    }
    int t;
    if(1==sscanf(r, "%d", &t))res += t;
    cout << res << endl;
}

Measured memory_bytes: 1220
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int main()
{
	int a,i;
	char s[10000];
	scanf("%d", &a);
	scanf("%s", s);
	if (a >= 3200)printf("%s\n", s);
	else printf("red\n");
	return 0;
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;

int main() {
	int n;
	cin >> n;
	
	vector<int>a(n),b(n),c(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i]; a[i]--;
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n - 1; i++) {
		cin >> c[i];
	}
	int ans = 0;

	for (int i = 0; i < n; i++)ans += b[a[i]];

	for (int i = 0; i < n-1; i++) {
		if (a[i]+1 != a[i + 1] )continue;
		ans += c[a[i]];
	}
	cout << ans << endl;

	return 0;


}

Measured memory_bytes: 256
n  = int(input())
red = [list(map(int,input().split())) for i in range(n)]
blue = [list(map(int,input().split())) for i in range(n)]

red.sort(reverse=True)
blue.sort()

ans = 0
for i in range(n):
    x = red[i][0]
    y = red[i][1]
    index = -1
    now_by = 201
    for j in range(len(blue)):
        if x < blue[j][0] and y < blue[j][1] and now_by > blue[j][1]:
            index = j
            now_by = blue[j][1]
    if index >= 0:
        ans += 1
        blue.pop(index)


print(ans)

Measured memory_bytes: 3064
//
//  main.cpp
//  sample
//
//  Created by h3037178 on 2017/07/27.
//  Copyright ?? 2017??´ ?????£?????????. All rights reserved.
//

#include<iostream>
using namespace std;
int main(){
    int i,s;
    char op;
    for(;;){
        cin>>i>>op>>s;
    if(op=='+'){
        cout<<i+s;
    }
    if(op=='-'){
        cout<<i-s;
    }
    if(op=='*'){
        cout<<i*s;
    }
    if(op=='/'){
        cout<<i/s;
    }
    if(op=='?'){
        break;
    }
        cout<<endl;
    }
}

Measured memory_bytes: 3096
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
#include<algorithm>
#include<functional>
using namespace std;

int n,q;
int a=0;
int c=0;
int s[10000]={};
int t[10000]={};




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

	cin>>q;
	for(int j=0;j<q;j++)
	{
	cin>>t[j];
	}

	for(int k=0;k<n;k++)
	{
	for(int l=0;l<q;l++)
	{
	a=s[k]^t[l];
	if(a==0)
	{
	c+=1;
	t[l]=-1;
	}
	}
	
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INF 999999999
using namespace std;

int main(){
          int n,k;
          cin >> n >> k;
          unsigned long long int ans=0;
          ans+=k*pow((k-1),(n-1));
          cout << ans << endl;
          return 0;
}


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

int main() {
    int a, b;
    cin >> a >> b;
    if(a==b) cout << "a == b" << endl;
    if(a<b) cout << "a < b" << endl;
    if(a>b) cout << "a > b" << endl;
  return 0;
}



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

using namespace std;

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

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

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

pll A[300005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, W, M;
    cin >> H >> W >> M;
    vector<pll> X, Y;
    REP(i, H) {
        X.push_back(pll(0, i));
    }
    REP(i, W) {
        Y.push_back(pll(0, i));
    }

    std::map<pll, ll> mp;
    REP(i, M) {
        cin >> A[i].first >> A[i].second;
        A[i].first--;
        A[i].second--;
        mp[A[i]]++;
        X[A[i].first].first++;
        Y[A[i].second].first++;
    }

    sort(X.begin(), X.end(), greater<pll>());
    sort(Y.begin(), Y.end(), greater<pll>());

    ll xm = X[0].first, ym = Y[0].first;

    ll ans = xm + ym - 1;
    vector<ll> x, y;
    REP(i, X.size()) {
        if (X[i].first < xm)
            break;
        x.push_back(X[i].second);
    }
    REP(i, Y.size()) {
        if (Y[i].first < ym)
            break;
        y.push_back(Y[i].second);
    }

    REP(i, x.size()) {
        REP(j, y.size()) {
            pll p(x[i], y[j]);

            if (mp[p] == 0) {
                cout << xm + ym << endl;
                return 0;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 44628
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<' ';
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    string s; cin>>s;
    bool yymm = false, mmyy = false;
    if(1<=(s[0]-'0')*10+s[1]-'0' && (s[0]-'0')*10+s[1]-'0'<=12)mmyy = true;
    if(1<=(s[2]-'0')*10+s[3]-'0' && (s[2]-'0')*10+s[3]-'0'<=12)yymm = true;
    if(yymm && mmyy)cout<<"AMBIGUOUS"<<endl;
    else if(yymm)cout<<"YYMM"<<endl;
    else if(mmyy)cout<<"MMYY"<<endl;
    else cout<<"NA"<<endl; return 0;
}


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

int main(void)
{
	char str[81];
	int sum, number, i, len;
	
	sum = 0;
	while (scanf("%s", str) != EOF){
		len = strlen(str);
		
		for (i = 0; i < len; i++){
			number = 0;
			if (str[i] >= '0' && str[i] <= '9'){
				while (str[i] >= '0' && str[i] <= '9'){
					number = number * 10 + str[i] - '0';
					i++;
				}
				sum += number;
			}
		}
	}
	
	printf("%d\n", sum);
	
	return (0);
}

Measured memory_bytes: 540
#include"bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.141592653589793238

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	cout << min(N * A, B) << endl;
	return 0;
}

Measured memory_bytes: 256
///
#include <bits/stdc++.h>
#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, N) FOR(i, 0, N)
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll MOD = round(1e9+7);

int gcd(int a,int b){
  if(a<b) swap(a,b);
  while(a%b){
    int r = a%b;
    a=b;
    b=r;
  }
 return b;
}

int main() {
    int N,M; cin >> N>>M;
    vi a(N);rep(i,N) cin>>a[i];
  
    ll ans=(N-1+M-1-1)/(M-1);
  
    cout << ans << endl;
    return 0;
}


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


int main(){


    long long n, m, i, t;

    vector<long long> d(100001);


    cin >> n >> m;


    vector<long long> a(n + 1); 


    for( i = 0 ; i < m ; i = i + 1 ){

         cin >> t;

         a.at(t) = 1;

         }


    d.at(0) = 1;

    if( a.at(1) != 1 ) d.at(1) = 1;


    for( i = 2 ; i < n + 1 ; i = i + 1 ){

         if( a.at(i) != 1 ) d.at(i) = ( d.at(i - 1) % 1000000007 + d.at(i - 2) % 1000000007 ) % 1000000007;

         }


    cout << d.at(n) << endl;


    return 0;

    }


Measured memory_bytes: 1792
#include <stdio.h>
int main(void){
    int n, ans=0;
    scanf("%d", &n);
    
    if(n==0||n==1){ans=1;}
    
    else {
        int d[n+1];
        d[0]=1;
        d[1]=1;
        for(int i=2; i<=n; i++){
            d[i]=d[i-1]+d[i-2];
        }
        ans=d[n];
    }
    
    printf("%d\n", ans);
    
    return 0;
    
}


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

#define mp make_pair
#define pb push_back
#define f first
#define s second 
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define int long long
#define forn(i, x, y) for(int i = x; i <= y; i++)
#define forev(i, y, x) for(int i = y; i >= x; i--)

using namespace std;

const int maxn = (int)3e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int)1e6 + 7;
const int inf = (int)1e9 + 7;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef long double ld;

using namespace std;

int n, a[maxn], b[maxn], cnt, ans;
set<pii> s;
int prv(int x){
	if(x == 1) return n;
	return x - 1;
}
int nxt(int x){
	if(x == n) return 1;
	return x + 1;
}
main () {
	int cnt=0;
	cin >> n;
	forn(i, 1, n)
		cin >> a[i];
	forn(i, 1, n)
		cin >> b[i], s.insert(mp(b[i], i));
	while(sz(s)){
		cnt++;
		if(cnt==5000000){
			cout<<-1;
			return 0;
		}
		int val = s.rbegin()->f, pos = s.rbegin()->s;
		int l=0,r=1000000000,res=-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(val-mid*b[prv(pos)]-mid*b[nxt(pos)]>=a[pos]){
				res=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		ans+=res;
		val = val-res*b[prv(pos)]-res*b[nxt(pos)];
		s.erase(*s.rbegin());
		if(val!=a[pos]){
			s.insert(mp(val,pos));
		}
		b[pos] = val;
	}
	cout << ans;
}

Measured memory_bytes: 18432
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;

ll dp[10010][2][110] = { 0 };
int main(void) {
	string s;
	ll d, sum = 0;
	cin >> s >> d;
	dp[0][0][0] = 1;
	for (ll i = 0;i < s.length();i++) {
		ll x = s[i] - '0';
		for (ll j = 0;j < 2;j++) {
			for (ll k = 0;k < d;k++) {
				for (ll l = 0;l <= (j?9 : x);l++) {
					dp[i + 1][j || l < x][(k+l)%d] = (dp[i + 1][j || l < x][(k+l)% d] + dp[i][j][k]) % N;
				}
			}
		}
	}
	
	cout << (dp[s.length()][0][0] + dp[s.length()][1][0] - 1+N)%N << endl;
}

Measured memory_bytes: 17408
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val (n, c) = readIntegerList()
    val changeCostArrays = Array(c) { readIntegerList() }
    val colorArrays = Array(n) { readIntegerList().map { it - 1 } }

    val changeCosts = Array(3) { IntArray(c) }
    repeat(n) { h ->
        repeat(n) { w ->
            val index = (h + w) % 3
            val currentColor = colorArrays[h][w]
            repeat(c) { color ->
                changeCosts[index][color] += changeCostArrays[currentColor][color]
            }
        }
    }

    var ans = Int.MAX_VALUE
    repeat(c) { c1 ->
        repeat(c) { c2 ->
            repeat(c) { c3 ->
                if (c1 != c2 && c2 != c3 && c3 != c1) {
                    ans = min(ans, changeCosts[0][c1] + changeCosts[1][c2] + changeCosts[2][c3])
                }
            }
        }
    }
    out.println(ans)
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 60004
s = input()

ans = [0] * len(s)

prev = "L"
for i, si in enumerate(s):
    if si == "R" and prev == "L":
        num_r = 0
        num_l = 0
    if si == "R":
        num_r += 1

    if si == "L" and prev == "R":
        rl = i
        ans[rl] = num_r // 2
        ans[rl - 1] = num_r - num_r // 2
    if si == "L":
        num_l += 1
        ans[rl - (num_l + 1) % 2] += 1

    prev = si

print(*ans)


Measured memory_bytes: 6400
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
cnt = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            cnt[y][x] = 0
            q.append((y, x))

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while q:
    y, x = q.popleft()
    for Dy, Dx in zip(dy, dx):
        ny = y + Dy
        nx = x + Dx
        if 0 <= ny < H and 0 <= nx < W and cnt[ny][nx] == -1 and A[ny][nx] == ".":
            cnt[ny][nx] = cnt[y][x] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    ans = max(ans, max(cnt[i]))
print(ans)

Measured memory_bytes: 120564
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vec(k) vector<k>
#define vecvec(k) vector<vector<k> >
#define pai(k) pair<k,k>
#define mod 1000000007
#define mpai make_pair
#define p1 first
#define p2 second
#define umap(x,y) unordered_map<x,y>

struct sack
{
	ll value;
	ll weight;
};

// int solve(sack *arr, int n, int w)
// {
// 	sack dp[n+1];
// 	dp[0].weight=0;
// 	dp[0].value=0;
// 	for(int i=1;i<=n;i++)
// 	{
// 		dp[i].weight=0;
// 		dp[i].value=0;
// 		for(int j=0;j<i;j++)
// 		{
// 			if((dp[j].weight+ arr[i-1].weight)<= w && dp[i].value < (dp[j].value+arr[i-1].value))
// 			{
// 				dp[i].value=dp[j].value+arr[i-1].value;
// 				dp[i].weight=dp[j].weight+arr[i-1].weight;
// 				cout<<(dp[j].weight+ arr[i-1].weight)<<". ";
// 			}
			

// 		}
// cout<<"\n";
// 	}
// 	for(int i=0;i<=n;i++)
// 		cout<<dp[i].value<<" ";

// 	return dp[n].value;
// }
ll solveagain(sack *arr, int n, int w)
{
	ll dp[n+1][w+1];
	memset(dp,0,sizeof(dp));
	// dp[1][arr[0].weight]=arr[0].value;

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=w;j++)
		{
			dp[i][j]=dp[i-1][j];

			if(arr[i-1].weight<=j)
				dp[i][j]=max(dp[i][j], dp[i-1][j-arr[i-1].weight]+arr[i-1].value);
				

		}
	}
	ll maxans=0;
	for(int i=1;i<=w;i++)
		maxans=max(maxans, dp[n][i]);
	return dp[n][w];

}

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

    ll n,x,w;
    cin>>n>>w;
   	sack arr[n];
    for(int i=0;i<n;i++){
    	cin>>arr[i].weight;
	cin>>arr[i].value;
	

}
ll ans=solveagain(arr, n, w);
cout<<ans<<"\n";


return 0;
}


Measured memory_bytes: 79232
import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((2 * Y - X) / 3)
    m = int(Y - 2 * n)
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod

    r = n
    n = n+m
    # if n - r < r:
    #     r = n - r
    # if r == 0:
    #     return 1
    # if r == 1:
    #     return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    # return result
    print(result % mod)


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

int main()
{
	vector<long long> h;
	int k, n;
	cin >> n >> k;
	h.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	sort(h.begin(), h.end());

	long long min = 1000000001;
	long long diff;
	for (int i = k - 1; i < n; ++i) {
		diff = h[i] - h[i - k + 1];
		if (diff < min) {
			min = diff;
		}
	}

	cout << min << endl;

	return 0;
}

Measured memory_bytes: 1024
def min(a, b)
  return (a < b) ? a : b   
end

ni = gets().to_i
bc = gets().split(" ")

ary = []

for i in 0..ni-1 do
  a = []

  if i == 0
    a.push(bc[i].to_i)
  elsif i==ni-1
    a.push(bc[i-1].to_i)
  else
    a.push(bc[i-1].to_i, bc[i].to_i)
  end

  ary.push(a)
end

a2 = 0

ary.each do | a0, a1|
  if a0 == nil || a1 == nil
    a2 += (a0==nil) ? a1 : a0;
  else
    a2 += min(a0, a1)
  end
end

p a2


Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<map>
#include<utility>

using namespace std;

int main(){
    int N,M;
    cin >> N >> M;
    if(N==M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    } 
    
    
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  REP(i, n) {
    int _a;
    cin >> _a;
    a[i] = make_pair(_a, i + 1);
  }
  sort(ALL(a));
  int ans = 0;
  REP(i, n) {
    if (i % 2 != 0)
      continue;
    if ((i + 1) % 2 != a[i].second % 2)
      ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,ans;
  int pos = 10;
  cin >> a >> b;
  if(a > b) for(int i=0;i<a;i++) cout << b;
  else for(int i=0;i<b;i++) cout << a;
  printf("\n");

}

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

typedef pair<int, int> P;

int n;

vector<int> dijkstra(int s, vector<vector<P>> &G){
    vector<int> dist(n, 1e9);
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s] = 0;
    que.emplace(0, s);

    while(!que.empty()){
        int ccost, cv;
        tie(ccost, cv) = que.top();
        que.pop();

        if(dist[cv] < ccost) continue;

        for(auto x : G[cv]){
            int nv, ncost;
            tie(nv, ncost) = x;
            
            if(dist[cv] + ncost < dist[nv]){
                dist[nv] = dist[cv] + ncost;
                que.emplace(dist[nv], nv);
            }
        }
    }

    return dist;
}

int main(){
    cin>>n;
    vector<vector<P>> G(n);
    for(int i=0; i<n-1; i++){
        int s, t, w; cin>>s>>t>>w;
        G[s].emplace_back(t, w);
        G[t].emplace_back(s, w);
    }

    vector<int> dist1 = dijkstra(0, G);
    int v1 = max_element(dist1.begin(), dist1.end()) - dist1.begin();
    vector<int> dist2 = dijkstra(v1, G);
    
    cout << *max_element(dist2.begin(), dist2.end()) << endl;
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()

template <class T>
inline bool chmin(T &a, T b){
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b){
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using DoP = pair<double, double>;
using edge = struct { int to; double cost;}; // edge x = {to, cost}

const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1<<29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;

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

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};
// h(n, r) = c(n+r-1, r)
struct combination
{
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1)
  {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
      fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i)
      ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k)
  {
    if (k < 0 || k > n)
      return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int main(){
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<int>> x(n+1, vector<int>(n+1, 0));
  rep(i, m) {
    int l, r; cin >> l >> r;
    ++x[l][r];
  }
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j < n; ++j) {
      x[i][j+1] += x[i][j];
    }
  }
  for(int j = 1; j <= n; ++j) {
    for(int i = 0; i < n; ++i){
      x[i+1][j] += x[i][j];
    }
  }
  vector<int> ans(q);
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    ans[i] = x[r][r] - x[r][l-1] - x[l-1][r] + x[l-1][l-1];
  }
  for(auto z : ans) cout << z<< endl;
}

Measured memory_bytes: 2304
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> P;
#define make_pair mp
#define first f
#define second s
int num[205][3],n,ans[205]={};
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
	scanf("%d %d %d",&num[i][0],&num[i][1],&num[i][2]);
}
bool a=false;
for(int k=0;k<3;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j){
if(num[i][k]==num[j][k]){
a=true;
break;
}
}
}
if(!a){ ans[i]+=num[i][k];}
a=false;
}
}
for(int i=0;i<n;i++){
	printf("%d\r\n",ans[i]);
}
return 0;
}

Measured memory_bytes: 1028
#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 n, k;
  cin >> n >> k;
  string s;
  cin >> s;

  vector<int> a(n);
  rep(i, n) a[i] = s[i] - '0';

  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }

  vector<pair<int, int>> b;
  int cnt = 1;
  rep(i, n - 1) {
    if (a[i] != a[i + 1]) {
      b.push_back(make_pair(a[i], cnt));
      cnt = 1;
    } else {
      cnt++;
    }
    if (i == n - 2) {
      if (a[i] != a[i + 1]) {
        b.push_back(make_pair(a[i + 1], 1));
      } else {
        b.push_back(make_pair(a[i], cnt));
      }
    }
  }

  int ans = 0;
  cnt = 0;
  int d = 0;
  queue<int> q;
  rep(i, b.size()) {
    cnt += b[i].second;
    d += b[i].second;
    if (!b[i].first) {
      q.push(d);
      d = 0;
    }
    if (q.size() > k) {
      cnt -= q.front();
      q.pop();
    }
    ans = max(ans, cnt);
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1912
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	k := getNextInt(scanner)

	dp := make([][]int64, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int64, n+1)
		dp[0][i] = 1
	}

	for i := 1; i <= n; i++ {
		for ii := i; ii <= n; ii++ {
			dp[i][ii] = (dp[i-1][ii-1] + dp[i][ii-1]) % 1000000007
		}
	}

	for i := 1; i <= k; i++ {
		if n == k {
			if i == 1 {
				fmt.Fprintln(writer, 1)
				continue
			}
			fmt.Fprintln(writer, 0)
			continue
		}
		ans := (dp[i-1][k-1]) * ((dp[i-1][n-k-1] + dp[i-1][n-k-1] + dp[i][n-k-1]) % 1000000007)
		if i > 1 {
			ans += dp[i-1][k-1] * dp[i-2][n-k-1]
		}
		ans %= 1000000007
		fmt.Fprintln(writer, ans)
	}

	writer.Flush()
}


Measured memory_bytes: 28160
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

bool solve(int n, vector<int> a){
  if(all_of(ALL(a), [](int x){return x==0;})) return true;
  
  if(n%3) return false;

  map<int,int> c;
  for(auto x : a){
    ++c[x];
  }

  vector<int> b;
  for(auto &kv : c){
    if(kv.snd % (n/3) == 0){
      REP(i,kv.snd/(n/3)) b.push_back(kv.fst);
    }else{
      return false;
    }
  }

  if((b[0]^b[1]) == b[2]){
    return true;
  }
  
  return false;
}


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

  int n;
  while(cin >> n){
    vector<int> a(n); cin >> a;

    bool ans = solve(n,a);

    cout << (ans ? "Yes" : "No") << endl;
  }
  
  return 0;
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using vl=vector<ll>;
using vb=vector<bool>;
using vs=vector<string>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
const ll oo =0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORD(i,a,b) for(ll i=ll(b)-1;i>=(a);i--)
#define TR(X) ({if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

const ll MOD = 1e9 + 7;
const ll MAX_N = 100000 * 2;
int main(){
	ll N; cin >> N;
	vl cs(N);
	FOR(i, 0, N) {
		cin >> cs[i];
		cs[i] --;
	}

	vector<pll> segs;

	vl lasts(MAX_N+10, -1);

	FOR(i, 0, N) {
		if (lasts[cs[i]] != -1 && lasts[cs[i]] != i - 1) {
			segs.pb( {lasts[cs[i]], i});
		}
		lasts[cs[i]] = i;
	}

	if (!sz(segs)) {
		cout << 1 << endl;
		return 0;
	}

	sort(all(segs));

	vl mem(sz(segs));
	mem[sz(mem)-1] = 2;

	FORD(i, 0, sz(mem)-1) {
		pll search = pll(segs[i].yy, -1);
		auto non_overlap = lower_bound(segs.begin() + i, segs.end(), search);
		assert(non_overlap == segs.end() || (non_overlap - segs.begin()) < sz(mem));
		// Nehmen
		if (non_overlap != segs.end() && (non_overlap - segs.begin()) < sz(mem) && (non_overlap - segs.begin() >= 0)) {
			mem[i] += mem[non_overlap - segs.begin()];
		} else {
			mem[i] += 1;
		}
		mem[i] = mem[i] % MOD;
		// Nicht nehmen
		mem[i] += mem[i+1];
		mem[i] = mem[i] % MOD;
	}

	//FOR(i, 0, sz(mem)) { cerr << i << ": " << mem[i] << endl; }

	cout << mem[0] << endl;
	return 0;

} //cin.tie(0) bei schnellem Wechseln



Measured memory_bytes: 9072
#include<iostream>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<char,ll> P;
int main(){
  vector <P> a,b,c;
  ll i,j,k;
  char ch;
  while(cin>>ch,ch!='$'){
    cin >> k;
    a.push_back(P(ch,k));
  }
  while(cin>>ch,ch!='$'){
    cin >> k;
    b.push_back(P(ch,k));
  }
  while(cin>>ch,ch!='$'){
    cin >> k;
    c.push_back(P(ch,k));
  }
  if(b.size()==1){
    for(i=0;i+b.size()<=a.size();i++){
      if(a[i].first!=b[0].first||a[i].second<b[0].second) continue;
      a[i].second-=b[0].second;
      a.insert(a.begin()+i,c.begin(),c.end());
      break;
    }
  }else{
    for(i=0;i+b.size()<=a.size();i++){
      if(a[i].first!=b[0].first||a[i].second<b[0].second) continue;
      bool f = true;
      k=b.size()-1;
      for(j=1;j<k;j++){
	if(a[i+j].first!=b[j].first||a[i+j].second!=b[j].second) {
	  f=false;
	  break;
	}
      }
      if(a[i+k].first!=b[k].first||a[i+k].second<b[k].second) continue;
      if(f){
	//cout << i << endl;
	for(j=0;j<k+1;j++){
	  a[i+j].second-=b[j].second;
	}
	a.insert(a.begin()+i+1,c.begin(),c.end());
	//i+=b.size()+c.size()-1;
	break;
      }
    }
  }

  bool ff=true;
  while(ff){
    ff=false;
    k=0;
    while(k<a.size()){
      if(a[k].second==0) {
	a.erase(a.begin()+k);
	ff=true;
      }else k++;
    }
    for(i=0;i<a.size()-1;i++){
      if(a[i].first==a[i+1].first){
	a[i+1].second+=a[i].second;
	a[i].second=0;
      }
    }
  }
  
  for(i=0;i<a.size();i++){
    if(a[i].second==0) continue;
    cout << a[i].first << " " << a[i].second << " ";
  }
  cout << "$" << endl;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

ll l[200];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&l[i]);
    }
    sort(l,l+n);

    ll ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(l[i]+l[j]>l[k]&&l[i]!=l[j]&&l[k]!=l[j]&&l[k]!=l[i]) ans++;
            }
        }
    }

    printf("%lld",ans);
}


Measured memory_bytes: 3824
#include<stdio.h>
#include<algorithm>
using namespace std;
struct k{
	int a,b;
}p[200005];
int cmp(k x,k y)
{
	return x.a<y.a;
 } 
int main()
{
	int n,m,x,y,len,k,flag,i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		len=0;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			if(x==1||x==n)
			{
				p[len].a=y;p[len].b=x;len++;
			}
			if(y==1||y==n)
			{
				p[len].a=x;p[len].b=y;len++;
			}
		}
		sort(p,p+len,cmp);
		flag=0;
		for(i=0;i<len-1;i++)
		{
			if(p[i].a==p[i+1].a&&p[i].b!=p[i+1].b)
			{
				flag=1;break;
			}
		}
		if(flag)printf("POSSIBLE\n");
		else printf("IMPOSSIBLE\n");
	}
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;

#define PA pair<int,int>
int main(){
    int n; cin>>n;
    vector<PA> p;
    FOR(i,0,n){
        int a; cin>>a;
        p.PB(PA(a,1));
    }
    FOR(i,0,n){
        int a; cin>>a;
        p.PB(PA(a,-1));
    }
    sort(all(p));
    int b[200001]={};
    FOR(i,0,2*n){
        b[i+1]=b[i]+p[i].SE;
    }
    //FOR(i,0,2*n) printf("%d %d\n",p[i].SE,b[i+1]);
    ll dp[200001]={};
    dp[0]=1;
    FOR(i,1,2*n+1){
        if(b[i]==0){
            dp[i]=dp[i-1];
        }else if((b[i]>0)^(p[i-1].SE==-1)){
            dp[i]=(dp[i-1]*abs(b[i]))%MOD;
        }else{
            dp[i]=dp[i-1];
        }
    }
    co(dp[2*n]);
}


Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        

fast();
//ll t;cin>>t;while(t--)
{
  ll n,c,k,count=0,sum=0;
  cin>>n>>c>>k;
  ll a[n];
  ll pre[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    pre[i]=0;
  }
  sort(a,a+n);
pre[0]=a[0]+k;
for(int i=1;i<n;i++)
{
  
pre[i]=a[i]+k;
}
for(auto t:a)cerr<<t<<" ";
  cerr<<endl;
for(auto t:pre)cerr<<t<<" ";
  cerr<<endl;
ll aise=0;
  for(int i=0;i<n;i++)
  {  ll p=0;
       for(int j=i;j<n;j++)
       {
        if(a[j]<=a[i]+k&&p+1<=c)
        {
          p++;
          aise=1;
          continue;
        }
        else
        {
          //sum=pre[j-1];
          //cout<<"sum "<<sum<<endl;
          count++;
          i=j-1;
          aise=0;
          break;
        }

       }
  }
  if(aise==1)
    count++;
  cout<<max(1ll,count)<<endl;
    
}
return 0;
}


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

mt19937_64 llrand(random_device{}());

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define cl(x, v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<
#define gcd(x, y) __gcd((x), (y))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector<vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f, LMOD = 1011112131415161719ll;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 3e3+5;

ll n, v[N], memo[N][N][2];

ll dp (ll l, ll r, ll c) {
    if (memo[l][r][c] != LINF) return memo[l][r][c];

    if (c == 0) {
        if (l == r) return memo[l][r][c] = v[l];
        return memo[l][r][c] = max(v[l] + dp(l+1, r, c^1),
                                   v[r] + dp(l, r-1, c^1));
    }

    if (c == 1) {
        if (l == r) return memo[l][r][c] = -v[l];
        return memo[l][r][c] = min(-v[l] + dp(l+1, r, c^1),
                                   -v[r] + dp(l, r-1, c^1));
    }
}


int main () {
    cl(memo, 63);

    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);

    printf("%lld\n", dp(1, n, 0));


    return 0;
}

Measured memory_bytes: 141568
#include<bits/stdc++.h>
using namespace std;
int n;
char s1[105],s2[105];
int main(){
	scanf("%d",&n);
	scanf("%s%s",s1+1,s2+1);
	for (int ans=n;ans;ans--){
		int flag=0;
		for (int j=1;j<=ans;j++)
			if (s2[j]!=s1[n+j-ans])flag=1;
		if (!flag){
			printf("%d\n",2*n-ans);
			return 0;
		}
	}
	printf("%d\n",2*n);
}

Measured memory_bytes: 256