akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long int;using ld = long double;using P = pair<ll,ll>;const int MOD = (int)1e9+7;const string rt = "\n";const string sp = " ";/* 最大公約数 */template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}/* UnionFind */template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};/* コンビネーション */template<typename T> ll combpm(T N_, T C_) {const int NUM_=400001;static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];if (fact[0]==0) {inv[1]=fact[0]=factr[0]=1;for (int i=2;i<=NUM_;++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%MOD, factr[i]=factr[i-1]*inv[i]%MOD;}if(C_<0 || C_>N_) return 0;return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;}/* 多次元ベクター */template<class T>vector<T> multi_vector(size_t a){return vector<T>(a);}template<class T, class... Ts>auto multi_vector(size_t a, Ts... ts){return vector<decltype(multi_vector<T>(ts...))>(a, multi_vector<T>(ts...));}/* テスト関数 */void test(ll n){cout << "test" << n << endl;}/* 小数点以下 */void fixsp(ll n){cout << fixed << setprecision(n);}void defsp(ll n){cout << defaultfloat << setprecision(n);}/* 重み付きUnionFind */struct WUnionFind {vector<int> par;vector<int> rank;WUnionFind(int n = 1) {init(n);}void init(int n = 1) {par.resize(n); rank.resize(n);for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;}int root(int x) {if (par[x] == x) {return x;}else {int r = root(par[x]);return par[x] = r;}}bool issame(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (rank[x] < rank[y]) swap(x, y);if (rank[x] == rank[y]) ++rank[x];par[y] = x;return true;}};/* IO高速化 */void fastio(){ios::sync_with_stdio(false);cin.tie(NULL);}
/* ここからコード開始 */

int main(){fastio;
  ll N;
  cin >> N;
  ll h[N+1];
  h[0] = 0;
  ll sum{};
  rep(i, 1, N+1){
    cin >> h[i];
    sum += max(0LL, h[i] - h[i-1]);
  }
  cout << sum << rt;
}

Measured memory_bytes: 256
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def f(s, k, N):
    if len(s) == N:
        print(s)
        return

    for i in range(k+1):
        f(s + l_alp[i], max(k, i+1), N)


def main():
    N = I()
    ans = []

    f('a', 1, N)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()



Measured memory_bytes: 57556
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
ll c=1e9;

int main() {
    ll s;
    cin >> s;
    vector<ll> x(3);
    vector<ll> y(3);
    x[0]=0;
    y[0]=0;
    x[1]=c;
    y[1]=1;
    if (s%c==0) y[2]=s/c;
    else y[2]=s/c+1;
    x[2]=c*y[2]-s;
    for (int i=0;i<3;i++) cout << x[i] << ' ' << y[i] << ' ';
    cout << endl;
}

Measured memory_bytes: 256
/*input
7
100 130 130 130 115 115 150
*/

// #include<bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cstdint>
#include <tuple>
#endif
 
using namespace std;
long long mod=1e9+7;
long long INF=1e7;
double EPS = 1e-12;
const long long lim = 2e5+100;
typedef long long int lld;
typedef long long ll;

#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }


#define popcount __builtin_popcountll

ll powP(ll x, ll y) {
    ll ans = 1, po = x % mod;
    while(y > 0) {
        if(y & 1) ans = ans * po % mod;
        y >>= 1; po = po * po % mod;
    }
    return ans;
}


vector<ll> V;
ll Array[lim], C[lim];
vector<pair<ll,ll> > Allstocks;

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    lld T,i,p,j,l,e,r,b,c,k,m,q,a,d,w,x,y,u,v,z,t,curr,prev,sum=0,val,countA=0,indicator=0,pos,h,minA,maxA,type,n,ans=0,left,right;
    cin>>n;
    C[0]=1000;
    for(int i=1;i<=n;i++) {
        cin>>Array[i];
        C[i]=C[i-1];
        for(auto j: Allstocks) {
            C[i] = max(C[i],j.first+j.second*Array[i]);
        }
        Allstocks.push_back(make_pair(C[i-1] - (C[i-1]/Array[i])*Array[i],C[i-1]/Array[i]));

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


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define SORT(x) sort((x).begin(),(x).end())
#define REP(i,x,y) for(int i=(x);i<(y);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int lli;
typedef pair<int,int> pii;

const int INF=1<<30;
const long long int INF_=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

int CalcMid(int lb,int ub,int size){
	int mid;
	if(lb<ub) mid=(ub+lb)/2;
	else mid=(lb+ub+size)/2;
	mid%=size;
	return mid;
}

bool Sub_Check(int last,int mid,lli m,const vector<lli> &a){
	lli d;
	if(last<mid){
		if(last>0) d=a[mid]-a[last-1];
		else d=a[mid];
	}else if(last>mid){
		if(last>0) d=a[a.size()-1]-a[last-1]+a[mid];
		else d=a[last];
	}else{
		if(last>0) d=a[last]-a[last-1];
		else d=a[last];
	}
	return d>=m;
}

bool Check(const vector<lli> &a,lli m){
	REP(i,0,a.size()){
		int cnt=0,last=i;
		REP(i,0,3){
			int lb=last,ub=last-1;
			if(ub<0) ub=a.size()-1;
			do{
				int mid=CalcMid(lb,ub,a.size());
				if(Sub_Check(last,mid,m,a)) ub=mid;
				else lb=mid;
			}while(abs(ub-lb)>1&&!(lb==a.size()-1&&ub==0));
			if(Sub_Check(last,lb,m,a)) ub=lb;
			if(last<=ub) cnt+=ub-last+1;
			else cnt+=ub+a.size()-last+1;
			if(!(cnt<=a.size())) break;
			last=(ub+1)%a.size();
		}
		if(cnt<=a.size()) return true;
	}
	return false;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int N;
	cin >> N;
	vector<lli> A(N);
	REP(i,0,N){
		int a;
		cin >> a;
		if(i==0) A[i]=a;
		else A[i]=A[i-1]+a;
	}
	lli lb=0,ub=INF_;
	while(ub-lb>1){
		lli mid=(lb+ub)/2;
		if(Check(A,mid)) lb=mid;
		else ub=mid;
	}
	cout << lb << endl;
	return 0;
}

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

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()  
{ 
    FAST_INP;
    int a,b; 
    cin >> a >> b;
    cout << a*b << endl;
    return 0;
} 

Measured memory_bytes: 3652
#include <stdio.h>
#define MAX 251

int A[MAX];

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i + 1;
}

int main(){
  int i,H;
  scanf("%d",&H);
  for(i=1; i<=H; i++) scanf("%d",&A[i]);
  
  for(i=1; i<=H; i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(i>1)  printf("parent key = %d, ",A[parent(i)]);
    if(left(i)<= H) printf("left key = %d, ",A[left(i)]);
    if(right(i) <= H) printf("right key = %d, ",A[right(i)]);
    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 600
#include "bits/stdc++.h"
using namespace std;

int main(void)
{
     int n;
    while(cin>>n){
        if(n==-1)break;
        double x,y;
        x=1.0;
        y=0.0;
        for(int i=0; i<n-1; i++){
            double temp_x=x;
            double temp_y=y;
            //M_PI_2
            y+=sin((M_PI_2-atan2(temp_y, temp_x)));
            x-=cos((M_PI_2-atan2(temp_y, temp_x)));
        }
        cout<<x<<endl<<y<<endl;
    }

}

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

const ll INF = 1LL << 62;
const double PI = acos(-1);
const double eps = 1e-10;

const ll dx[4] = {-1, 0, 0, 1};
const ll dy[4] = {0, -1, 1, 0};

int main() {
  ll h, w, ch, cw, dh, dw;
  cin >> h >> w >> ch >> cw >> dh >> dw;
  ch--, cw--, dh--, dw--;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<vector<ll>> d(h, vector<ll>(w, INF));

  auto is_range = [&](ll x, ll y) {
    return 0 <= x && x < h && 0 <= y && y < w;
  };

  auto print_d = [&]() {
    rep(i, h) {
      rep(j, w) {
        if (s[i][j] == '#')
          cerr << "#";
        else if (d[i][j] == INF)
          cerr << "x";
        else
          cerr << d[i][j];
      }
      cerr << endl;
    }
    cerr << endl;
    return;
  };

  queue<P> q, r;
  q.push(P(ch, cw));
  d[ch][cw] = 0;
  while (!q.empty() || !r.empty()) {
    while (!q.empty()) {
      ll x = q.front().first, y = q.front().second;
      q.pop();
      for (ll i = -2; i <= 2; i++) {
        for (ll j = -2; j <= 2; j++) {
          ll nx = x + i, ny = y + j;
          // cerr << nx << " " << ny << endl;
          if (!is_range(nx, ny)) continue;
          if (nx == x && ny == y) continue;
          if (s[nx][ny] == '#') continue;
          // if (d[nx][ny] <= d[x][y]) continue;

          if (abs(i) + abs(j) <= 1) {
            if (d[nx][ny] <= d[x][y]) continue;
            d[nx][ny] = d[x][y];
            q.push(P(nx, ny));
          } else {
            if (d[nx][ny] <= d[x][y] + 1) continue;
            d[nx][ny] = d[x][y] + 1;
            r.push(P(nx, ny));
          }
        }
      }
    }
    // print_d();

    swap(q, r);
  }

  if (d[dh][dw] == INF) {
    cout << -1 << endl;
  } else {
    cout << d[dh][dw] << endl;
  }

  return 0;
}


Measured memory_bytes: 13428
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef pair<double, PIII> PDIII;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

struct edge{
  int to, limit;
  double dis;
  edge(){}
  edge(int to, double dis, int limit) : to(to), limit(limit), dis(dis) {}
};

double dist[40][40][40];
vector<edge> G[40];

int main(){
  int n, m, s, g;
  while(cin >> n >> m, n + m){
    REP(i, 40) G[i].clear();
    
    cin >> s >> g;
    s--, g--;
    REP(i, m){
      int x, y, c;
      double dis;
      cin >> x >> y >> dis >> c;
      x--, y--;
      G[x].push_back(edge(y, dis, c));
      G[y].push_back(edge(x, dis, c));
    }

    double ans = -1;
    fill(&dist[0][0][0], &dist[0][0][0] + 40 * 40 * 40, 1e20);
    priority_queue<PDIII, vector<PDIII>, greater<PDIII> > que;
    dist[s][0][n] = 0.0;
    que.push(PDIII(0, PIII(s, PII(0, n))));
    
    while(!que.empty()){
      double d   = que.top().first;
      int    pos = que.top().second.first;
      int    v   = que.top().second.second.first;
      int    pre = que.top().second.second.second;
      que.pop();
      if(pos == g && v == 1){
        ans = d;
        break;
      }
      if(d > dist[pos][v][pre]) continue;
      

      REP(i, G[pos].size()){
        int to = G[pos][i].to;
        for(int j = -1; j <= 1; j++){
          if(to == pre) continue;
          int nv = v + j;
          
          
          if(nv < 1 || nv > G[pos][i].limit) continue;
          double tmp = G[pos][i].dis / nv + d;
          if(tmp < dist[to][nv][pos]){
            dist[to][nv][pos] = tmp;
            que.push(PDIII(tmp, PIII(to, PII(nv, pos))));
          }
        }
      }
    }
    if(ans < 0){
      cout << "unreachable" <<endl;
    }else{
      printf("%.20lf\n", ans);
    }
  }
  return 0;
}

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

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

using namespace std;

template<class T> struct interval{
	T l,r;
	interval():l(T{}),r(T{}){}
	interval(const T& l,const T& r):l(l),r(r){}
	bool operator<(const interval& I)const{ return make_tuple(r,l)<make_tuple(I.r,I.l); }
};

int main(){
	int n; scanf("%d",&n);
	vector<interval<int>> I(n);
	rep(i,n){
		int x,l; scanf("%d%d",&x,&l);
		I[i]={x-l,x+l};
	}

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

	int ans=0,now=-INT_MAX;
	for(auto J:I) if(now<=J.l) {
		ans++;
		now=J.r;
	}
	printf("%d\n",ans);

	return 0;
}


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

int main(){
 int A[25],B[25],C[25];
  int n,ans=0;
  cin >> n;
  for(int i = 0;i<n;i++){
    cin >> A[i];
  }
  for(int i = 0;i<n;i++){
    cin >> B[i];
  }
  for(int i = 0;i<n;i++){
    cin >> C[i];
  }
  for(int i = 0;i<n;i++){
    ans += B[A[i]-1];
    if(A[i]+1==A[i+1]){
      ans += C[A[i]-1];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//long long
vector<long long>Wx, Wy, Vx, Vy;
long long X1[2100], Y1[2100], X2[2100], Y2[2100], n, dp[4100][4100], sum;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
        
        Wx.push_back(X1[i]); Wx.push_back(X2[i]);
        Wy.push_back(Y1[i]); Wy.push_back(Y2[i]);
    }

    sort(Wx.begin(), Wx.end()); sort(Wy.begin(), Wy.end());
    for (int i = 0; i < Wx.size(); i++) {
        if (i == 0 || Wx[i] != Wx[i - 1])Vx.push_back(Wx[i]);
        if (i == 0 || Wy[i] != Wy[i - 1])Vy.push_back(Wy[i]);
    }
    for (int i = 0; i < n; i++) {

        int pos1 = lower_bound(Vx.begin(), Vx.end(), X1[i]) - Vx.begin();
        int pos3 = lower_bound(Vx.begin(), Vx.end(), X2[i]) - Vx.begin();
        int pos2 = lower_bound(Vy.begin(), Vy.end(), Y1[i]) - Vy.begin();
        int pos4 = lower_bound(Vy.begin(), Vy.end(), Y2[i]) - Vy.begin();
        dp[pos1][pos2]++; dp[pos3][pos2]--; dp[pos1][pos4]--; dp[pos3][pos4]++;
    }
    for (int i = 0; i < 4100; i++) {
        for (int j = 1; j < 4100; j++)dp[i][j] += dp[i][j - 1];
    }
    for (int i = 1; i < 4100; i++) {
        for (int j = 0; j < 4100; j++)dp[i][j] += dp[i - 1][j];
    }
    for (int i = 0; i < Vx.size(); i++) {
        for (int j = 0; j < Vy.size(); j++) {
            if (dp[i][j] >= 1)sum += (Vx[i + 1] - Vx[i])*(Vy[j + 1] - Vy[j]);
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 134668
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)
















int main(){
    int h, w;
    scanf("%d %d", &h, &w);
    char s[100][101];
    for(int i = 0; i < h; i++){
        scanf("%s", s[i]);
    }
    int dp[100][100] = {};
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            dp[i][j] = 1 << 16;
        }
    }
    dp[0][0] = s[0][0] == '#';
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(i < h - 1) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (s[i][j] == '.' && s[i + 1][j] == '#'));
            if(j < w - 1) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (s[i][j] == '.' && s[i][j + 1] == '#'));
        }
    }
    printf("%d\n", dp[h - 1][w - 1]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 999999

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a, b;
	cin >> a >> b;
	cout << a - 1 + min(1, b/a) << endl;
}

Measured memory_bytes: 256
N=int(input())
a=list(map(int,input().split()))
a.sort()
a.append(0)
i=0
ans=0
while i<N:
    x=a[i]
    count=0
    while a[i]==x:
        i+=1
        count+=1
    if count<x:
        ans+=count
    else:
        ans+=count-x
print(ans)


Measured memory_bytes: 20832
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = sc.nextInt();
    int[] m = new int[n];
    for (int i = 0; i < n; i++) {
      m[i] = sc.nextInt();
    }
    Arrays.sort(m);
    for (int i = 0; i < n; i++) {
      x -= m[i];
    }
    int count = n;
    while (x >= m[0]) {
      x -= m[0];
      count++;
    }
    System.out.println(count);
  }

}


Measured memory_bytes: 21972
use input::Input;

fn main() {
    let mut input = Input::default();

    let n = input.parse();

    let mut ans = 0;
    for i in 1..=n {
        ans += i * g((n + i) / i);
    }
    println!("{}", ans);
}

fn g(n: u64) -> u64 {
    n * (n - 1) / 2
}

#[allow(dead_code)]
pub mod input {
    #[derive(Default)]
    pub struct Input(Vec<String>);

    impl Input {
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).ok().expect("read error");
            s
        }
        pub fn parse<T: std::str::FromStr>(&mut self) -> T {
            let x = if let Some(x) = self.0.pop() {
                x
            } else {
                let s = self.read_line();
                self.0 = s.split_whitespace().map(String::from).rev().collect();
                self.0.pop().expect("reached EOF")
            };
            x.parse().ok().expect("parse error")
        }
    }
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  rep(i, 100005) {
    if (i * (k - 1) + 1 >= n) {
      cout << i << endl;
      return 0;
    }
  }



  
  return 0;
}

Measured memory_bytes: 640
/**
*   author:  akifpathan
*   created: Sunday 13.09.2020 03:56:48 PM
**/

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#ifdef LOCAL
#include "debug.h"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(x...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using ordered_set= tree<T, null_type, 
		less<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> 		
using ordered_mset= tree<T, null_type, 
		less_equal<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
		
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

const ll base=29;

ll ara[6000],power[6000];

void solve()
{
	int n;
	cin>>n;
	
	string s;
	cin>>s;
	
	s='.'+s;
	
	power[0]=1LL;
	for(int i=1;i<=n;i++) power[i]=(power[i-1]*base);
	
	for(int i=1,j=n-1;i<=n;i++,j--)
	{
		ara[i]=ara[i-1]+(power[j]*s[i]);
	}
	
	int hi=n/2;
	int lo=1;
	int ans=0;
	
	while(hi>=lo)
	{
		int mid=(hi+lo)/2;
		
		map<ll,vector<int>>indx;
		
		for(int i=1;i+mid-1<=n;i++)
		{
			ll temp=ara[i+mid-1]-ara[i-1];
			
			temp*=power[i-1];
			
			indx[temp].push_back(i);
		}
		
		bool flag=false;
		
		for(auto it: indx)
		{
			if(it.second.size()>=2)
			{
				flag|=(it.second[0]+mid<=it.second.back());
			}
		}
		
		if(flag)
		{
			ans=mid;
			lo=mid+1;
		}
		else hi=mid-1;
	}
	
	
	cout<<ans;
	
}		

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int testcase=1;
	//cin>>testcase;
	
	for(int i=1;i<=testcase;i++)
	{
		//cout<<"Case "<<i<<": ";
		solve();
	}
	
	#ifdef LOCAL
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	#endif
	
	
	return 0;
}



Measured memory_bytes: 4284
package main

import (
	"fmt"
)

func main() {
	var s int
	fmt.Scan(&s)

	var as []int

	as = append(as,s)
	newVal := 0
	for i := 1; i <= 1000000; i++{
		if as[i-1] % 2 == 0 {
			newVal = as[i-1]/2
		} else {
			newVal = 3 * as[i-1]+1
		}
		for _,v := range as {
			if v == newVal {
				fmt.Println(i+1)
				return
			}
		}
		as = append(as,newVal)
	}
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		Scanner scan = new Scanner(System.in);
		
		// ?????????????????????
		Dise2 dise = new Dise2();
		// ?????¢?????°??????????????????
		for(int i = 0; i < 6; i++) {
			dise._values[i] = scan.nextInt();
		}
		//??????????????°???????????????
		int q = scan.nextInt();
		// ???????????°????????°?????????
		for(int i = 0; i < q; i++) {
			// ?????? ???????????????
			int top = scan.nextInt();
			int front = scan.nextInt();
			// ??????????????????????????????????´????????????°
			boolean result = false;
			
			// ?¢????
			for(int i2 = 0; i2 < 4; i2++) {
				// ?????¢????¢????
				if (dise._values[1] == front) {
					// ?????¢????¢????
					result = topVarueCheck(dise, top, result);
				}
				else {
					dise.MoveSouth();
				}
				if (result == true) break;
			}
			if (result == false) {
				dise.MoveEast();
				dise.MoveSouth();
				// ?????¢????¢????
				if (dise._values[1] == front) {
					// ?????¢????¢????
					result = topVarueCheck(dise, top, result);
				}
				else { 
					dise.MoveSouth();
					dise.MoveSouth();
					// ?????¢????¢????
					result = topVarueCheck(dise, top, result);
				}
			}
		}
		
	}

	private static boolean topVarueCheck(Dise2 dise, int top, boolean result) {
		// ?????¢????????£????????????????????¢??????????????§??????
		for(int i3 = 0; i3 < 4; i3++) {
			if (dise._values[0] == top) {
				// ?????¢?????????
				System.out.println(dise._values[2]);
				result = true;
				break;
			}
			else dise.MoveEast();
		}
		return result;
	}
}

// ??????????????????
class Dise2 {

	public int _values[] = new int[6];
	
	public void Dice(int values[]) {
    	for (int i = 0; i < values.length; i++)
    	this._values[i] = values[i];
	}
    
    public enum ValueType
    {
        Top,
        Front,
        Right,
        Left,
        Back,
        Bottom
    }
    
    public void MoveWest()
    {
        int tmp = this._values[0];
        this._values[0] = this._values[2];
        this._values[2] = this._values[5];
        this._values[5] = this._values[3];
        this._values[3] = tmp;
    }
    public void MoveEast()
    {
        int tmp = this._values[0];
        this._values[0] = this._values[3];
        this._values[3] = this._values[5];
        this._values[5] = this._values[2];
        this._values[2] = tmp;
    }
    public void MoveNorth()
    {
        int tmp = this._values[0];
        this._values[0] = this._values[1];
        this._values[1] = this._values[5];
        this._values[5] = this._values[4];
        this._values[4] = tmp;
    }
    public void MoveSouth()
    {
        int tmp = this._values[0];
        this._values[0] = this._values[4];
        this._values[4] = this._values[5];
        this._values[5] = this._values[1];
        this._values[1] = tmp;
    }


}

Measured memory_bytes: 26136
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		// input
		int xRight = scan.nextInt();
		int xLeft = 0;
		int yUp = scan.nextInt();
		int yDown = 0;
		int num = scan.nextInt();
		for (int i = 0; i < num; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			switch (scan.nextInt()) {
			case 1:
				if (x > xLeft) {
					xLeft = x;
				}
				break;
			case 2:
				if (x < xRight) {
					xRight = x;
				}
				break;
			case 3:
				if (y > yDown) {
					yDown = y;
				}
				break;
			case 4:
				if (y < yUp) {
					yUp = y;
				}
			}
		}

		int width = 0;
		if (xRight > xLeft) {
			width = xRight - xLeft;
		}
		int height = 0;
		if (yUp > yDown) {
			height = yUp - yDown;
		}

		System.out.println(width * height);

	}
}


Measured memory_bytes: 22100
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define REP(i, n) for(int i=0; i<(n); i++)
#define REPS(i, n) for(int i=0; i<=(n); i++)
#define FOR(i, a, b) for(int i=a; i<(b); i++)
#define FORS(i, a, b) for(int i=a; i<=(b); i++)
// for container x
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#pragma endregion

int main(){
    int a;
    cin >> a;
    cout << a+a*a+a*a*a << endl;
    return 0;
}

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

int main(){
    long long n, m;
    cin >> n >> m;
    if (n == 2 || m == 2){
        cout << 0 << endl;
    } else if (n == 1 && m == 1) {
        cout << 1 << endl;
    } else if (n == 1){
        cout << m - 2 << endl;
    } else if (m == 1){
        cout << n - 2 << endl;
    } else {
        cout << (n-2) * (m-2) << endl;
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
        a[i]--;
    }
    vector<bool> did(n,false);
    int now = 0;
    int cnt = 0;
    while(true) {
        if(now == 1) {
            cout << cnt << endl;
            return 0;
        }
        if(did[now]) {
            cout << -1 << endl;
            return 0;
        }
        did[now] = true;
        cnt++;
        now = a[now];
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int main(void){
char string[222];
cin>>string;
int n=strlen(string);
for(int i=n-2;i;i-=2){
    if(strncmp(string,string+i/2,i/2)==0){
        cout<<i<<endl;
        return 0;
    }
    
}
}

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long;
const int N=110;
int a[N],n,dp[100100];
int mex(set<int> t){
	int x=0;
	while(t.find(x)!=t.end())
		x++;
	return x;
}




int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int k;
	cin>>n>>k;
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	dp[0]=0;
	for (int j = 1; j <= k; ++j)
	{
		set<int> t;
		for (int i = 0; i <n ; ++i)
		{
			if(j>=a[i])
				t.insert(dp[j-a[i]]);
		}
		dp[j]=mex(t);
	}
	if(dp[k]){
		cout<<"First\n";
	}else{
		cout<<"Second\n";
	}
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define el endl
#define INF 1e8
typedef long long ll;
typedef long double ld;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    for(int i = 1; i < n; i++){
        if(a[i] == a[i-1]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}



Measured memory_bytes: 1024
n,m=map(int,input().split())
ans=[10**10]*n
edge=[[]for _ in range(n)]
for _ in range(m):
	l,r,d=map(int,input().split())
	l-=1
	r-=1
	edge[l].append([r,d])
	edge[r].append([l,-d])
for i in range(n):
	if ans[i]==10**10:
		ans[i]=0
		Q=[i]
		while Q:
			P=[]
			for i in Q:
				for j,d in edge[i]:
					if ans[j]==10**10:
						P+=[j]
						ans[j]=ans[i]+d
			Q=P
for i in range(n):
	for j,k in edge[i]:
		if ans[i]+k!=ans[j]:print("No");exit()
print("Yes")

Measured memory_bytes: 77568
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,sin,cos
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m=mii()

mat=[[] for i in range(n)]

#前の場所がどこだったか
ans=[-1]*n

for i in range(m):
    a,b=mii()
    mat[a-1].append([a-1,b-1])
    mat[b-1].append([b-1,a-1])


q=deque(mat[0])
#print(q,ans[1])
while len(q)>0:

    node = q.popleft()
    #print(node[1],111,type(node[1]),mat[node[1]])
    if node is not None:
        if ans[node[1]]==-1:
            ans[node[1]]=node[0]
            for i in mat[node[1]]:
                q.append([node[1],i[1]])

print("Yes")
for i in range(1,n):
    print(ans[i]+1)




Measured memory_bytes: 157924
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

using namespace std;

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;

const long long int MOD = 1e9 + 7;
const long long int INF = 2e9 + 13;
const long long int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

ll N, U, V;
vll maxDepth, distFromV, distFromU;
vvll AdjList;

ll maxAdim = 0, yukari;

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    //freopen("output.txt", "w", stdout);

    cin >> N >> U >> V; U--; V--;
    AdjList.resize(N);
    distFromU.resize(N, INF);
    distFromV.resize(N, INF);

    for(ll i = 0; i < N-1; ++i){
        ll u, v; cin >> u >> v;
        u--; v--;
        AdjList[u].pb(v);
        AdjList[v].pb(u);
    }

    queue<pll> bfs;
    vector<bool> visited(N, false);

    bfs.push(mp(U, 0));
    visited[U] = true;
    distFromU[U] = 0;
    while(!bfs.empty()){
        pll tp = bfs.front(); bfs.pop();
        for(ll i = 0; i < AdjList[tp.st].size(); ++i){
            ll v = AdjList[tp.st][i];
            if(visited[v]) continue;
            visited[v] = true;
            distFromU[v] = tp.nd+1;
            bfs.push(mp(v, tp.nd+1));
        }
    }
    
    bfs.push(mp(V, 0));
    visited.assign(N, false);
    visited[V] = true;
    distFromV[V] = 0;
    while(!bfs.empty()){
        pll tp = bfs.front(); bfs.pop();
        for(ll i = 0; i < AdjList[tp.st].size(); ++i){
            ll v = AdjList[tp.st][i];
            if(visited[v]) continue;
            visited[v] = true;
            distFromV[v] = tp.nd+1;
            bfs.push(mp(v, tp.nd+1));
        }
    }

    ll ans = 0; 
    if(AdjList[U].size() == 1 and AdjList[U][0] == V){
        cout << 0 << endl; return 0;
    }

    for(ll i = 0; i < N; ++i){
        if(distFromV[i] > distFromU[i]) ans = max(ans, distFromV[i]-1);
    }
    cout << ans << endl;

    return 0;
}

//cikisir



Measured memory_bytes: 8192
// ConsoleApplication7.cpp : ??????????????? ??¢????????±????????§????????¨????????? ?????????????????????????????????
//

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
	int i;
	int a, b;
	int num;
	int aa[10000], bb[10000];
	char o;
	char op[10000];
	char temp[15];

	for (num = 0; 1; num++) {
		fgets(temp, sizeof(temp), stdin);
		sscanf(temp, "%d", &a);
		o = *(strchr(temp, ' ') + 1);
		if (o == '?') break; 
		sscanf(strrchr(temp, ' ') + 1, "%d", &b);
		aa[num] = a;
		bb[num] = b;
		op[num] = o;
	}
	for (i = 0; i < num; i++) {
		switch (op[i]) {
		case '+':
			printf("%d\n", aa[i] + bb[i]);
			break;
		case '-':
			printf("%d\n", aa[i] - bb[i]);
			break;
		case '*':
			printf("%d\n", aa[i] * bb[i]);
			break;
		case '/':
			printf("%d\n", aa[i] / bb[i]);
			break;
		default:
			break;
		}
	}
	
	return 0;
}

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

int main()
{
    long long n, i, mut, minim;
    cin>>n;
    minim=n-1;
    for(i=2; i<=sqrt(n); i++)
        if(n%i==0)
        {
            mut=(i-1)+(n/i-1);
            if(mut<minim)
                minim=mut;
        }
    cout<<minim;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct tree
{
	int ans;
	int price;
}t[1005];
int dp[20005];
const int inf=0x3f3f3f3f;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&t[i].ans,&t[i].price);
	}
	for(int i=1;i<=20002;i++)
	{
		dp[i]=inf;
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=t[i].ans;j<=20002;j++)
		{
			dp[j]=min(dp[j],dp[j-t[i].ans]+t[i].price);
		}
	}
	int res=inf;
	for(int i=n;i<=20002;i++)
	{
		res=min(res,dp[i]);
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 384
#define _GLIBCXX_DEBUG
#include<cstring>
#include<iostream>
#include<algorithm>
#include<utility>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<list>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>
#include<array>
#include<stack>

using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
const ll MAX_N=10,MAX_D=10;
const double EPS=1e-12;
ll N,D,X[MAX_N][MAX_D];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>D;
    REP(i,N)REP(j,D)cin>>X[i][j];
    ll ans=0;
    REP(i,N)FOR(j,i+1,N){
        double d=0.0;
        REP(k,D){
            d+=(X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
        }
        d=sqrt(d);
        ll id=d;
        if(abs(d-id)<EPS){
            ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n, d[100005][50];

int f(int p, int q) {
	int i, mn=1e9;
	if(!p && q) return q;
	if(q>45) return 1e9;
	if(d[p][q]) return d[p][q];
	d[p][q] = 1e9;
	for(i=0; i<=9; i++) mn = min(mn, f((p*10+i)%n, q+i));
	return d[p][q] = mn;
}

int main() {
	cin>>n;
	cout<<f(0,0);
	return 0;
}

Measured memory_bytes: 223104
#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= 9; ++i)
		for (int j = 1; j <= 9; ++j) {
			int mid1 = 0;
			int mid2 = 0;
			for (int k = 1; k <= n; ++k) {
				int h = k, t = k % 10;
				while (h >= 10)
					h /= 10;
				if (h == i && t == j)
					mid1++;
				if (h == j && t == i)
					mid2++;
			}
			sum += mid1 * mid2;
		}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 384
<?php

fscanf(STDIN,'%d', $d);
$a = explode(' ',trim(fgets(STDIN)));

$same = $a[0];
$same_flg = true;
foreach ($a as $value) {
//    var_dump($same, $value);
    if ($same !== $value){
        $same_flg = false;
    }
}
if ($same_flg){
    echo '0'.PHP_EOL;
    exit;
}

$max = 0;
foreach ($a as $value){
    if ($value > $max) {
        $max = intval($value);
    }
}

$min_cache = PHP_INT_MAX;

$hoge = [];
for ($i = -100; $i<=100;$i++){
    $sum = 0;
    foreach ($a as $value){
        if ($value == $i) {
            continue;
        }

        $sum += pow(($value-$i),2);
    }
////    var_dump($i,$sum);
//    if ($sum < $min_cache) {
//        $min_cache = $sum;
////        $itr_cache = $i;
//    }
    $hoge[] = $sum;
}


echo min($hoge).PHP_EOL;

Measured memory_bytes: 4732
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
const ll MOD = 1000000007;//998244353;
struct pq_greater{
   bool operator() (const priority_queue<int, vector<int>, greater<int>>& x, const priority_queue<int, vector<int>, greater<int>>& y)const{return x.top()>y.top();}
};
// UnionFind
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};
int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n, m; cin >> n >> m;
   vector<int> A(n);
   rep(i,n)cin >> A[i];
   UnionFind uf(n);
   rep(i,m){
      int x, y; cin >> x >> y;
      uf.unite(x, y);
   }
   if (m==n-1){
      cout << 0 << endl;
      return 0;
   }
   if (2*(n-m-1) > n){
      cout << "Impossible" << endl;
      return 0;
   }
   map<int, vector<int>> mp;
   rep(i,n){
      mp[uf.find(i)].push_back(A[i]);
   }
   
   vector<priority_queue<int, vector<int>, greater<int>>> v(mp.size());
   int cnt = 0;
   for (auto &&i : mp){
      for (auto &&j : i.second)
         v[cnt].push(j);
      cnt++;
   }
   ll ans = 0;
   priority_queue<int, vector<int>, greater<int>> pq;
   cnt = 0;
   for (auto &&i : v){
      cnt++;
      ans += i.top();
      i.pop();
      while(!i.empty()){
         pq.push(i.top());
         i.pop();
      }
   }
   for (; cnt < 2*(n-m-1); cnt++)
   {
      ans += pq.top();
      pq.pop();
   }
   
   cout << ans << endl;
}

Measured memory_bytes: 13248
#include <stdio.h>

int main(){
  char line[100];
  int a, b, c;
  fgets(line, sizeof(line), stdin);
  sscanf(line, "%d %d %d", &a, &b, &c);
  if((a<b)&&(b<c))
	printf("Yes\n");
  else
	printf("No\n");
  return 0;
}



Measured memory_bytes: 2100
// AOJ 0590: Available Areas
// 2017.10.1 bal4u@uu

#include <stdio.h>

int check(int s)
{
	int x, t;

	for (x = 1; ; x++) {
		t = x << 1;
		if (t * (x+1) > s) break;
		if ((s - x) % (t + 1) == 0) return 1;
	}
	return 0;
}

int main()
{
	int n, s, ans;

	scanf("%d", &n);
	ans = 0; 
	while (n -- > 0) {
		scanf("%d", &s);
		if (!check(s)) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1852
#include<iostream>
#include<cstdio>
#include<cstring>

typedef long long ll;
ll n,m;

int main()
{
	scanf("%lld%lld",&n,&m);
	if(n==1 && m==1){printf("%lld\n",1ll);}
	else if(n==1 || m==1){printf("%lld\n",n*m-2);}
	else printf("%lld\n",(n-2)*(m-2));
	return 0;
}


Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<stdio.h>
#include<sys/time.h>
#define ck 26

unsigned long long seed;

unsigned long long xorshift(){
  seed=seed^(seed<<13);
  seed=seed^(seed>>7);
  seed=seed^(seed<<17);
  return seed;
}

int d;
int c[32];
int s[512][32];
int res[512];

int eval(){
  int i,j,lc[32],r=0;
  for(i=1;i<=ck;i++){lc[i]=-1;}
  for(i=0;i<d;i++){
    r+=s[i][res[i]];
    lc[res[i]]=i;
    for(j=1;j<=ck;j++){
      r-=c[j]*(i-lc[j]);
    }
  }
  return r;
}

int sum(int x){
  return (x*(x+1))/2;
}

int delq(int tg,int x){
  if(res[tg]==x){return 0;}
  int r,i;
  int bfb=-1,bff=d,afb=-1,aff=d;
  r=s[tg][x]-s[tg][res[tg]];

  for(i=tg-1;i>=0;i--){
    if(res[i]==res[tg]){bfb=i;break;}
  }
  for(i=tg+1;i<d;i++){
    if(res[i]==res[tg]){bff=i;break;}
  }

  for(i=tg-1;i>=0;i--){
    if(res[i]==x){afb=i;break;}
  }
  for(i=tg+1;i<d;i++){
    if(res[i]==x){aff=i;break;}
  }
  
  r+=c[res[tg]]*sum((tg-bfb)-1);
  r+=c[res[tg]]*sum((bff-tg)-1);
  r-=c[res[tg]]*sum((bff-bfb)-1);

  r-=c[x]*sum((tg-afb)-1);
  r-=c[x]*sum((aff-tg)-1);
  r+=c[x]*sum((aff-afb)-1);
  return r;
}

void getperm(int n,int p[]){
  int i,tg,mem;
  for(i=0;i<n;i++){
    p[i]=i;
  }
  for(i=n-1;i>=1;i--){
    tg=(xorshift()%(i+1));
    mem=p[tg];
    p[tg]=p[i];
    p[i]=mem;
  }
}

int main(){
  long long stt,nt;
  struct timeval tv;
  gettimeofday(&tv, NULL);
  seed=(tv.tv_sec*1000000+tv.tv_usec);
  stt=seed;
  int i,j,q,r,tg,x,p[32],dv[32];
  int tgpm[512];
  scanf("%d",&d);
  for(i=1;i<=ck;i++){scanf("%d",&c[i]);}
  for(i=0;i<d;i++){
    for(j=1;j<=ck;j++){
      scanf("%d",&s[i][j]);
    }
  }
  for(i=0;i<d;i++){
    res[i]=(i%ck)+1;
  }
  r=eval();
  q=0;
  getperm(d,tgpm);
  while(1){
    tg=tgpm[q];
    for(i=1;i<=ck;i++){dv[i]=delq(tg,i);}
    getperm(ck,p);
    for(i=0;i<ck;i++){
      if(dv[res[tg]]<=dv[p[i]+1]){res[tg]=p[i]+1;}
    }
    q++;
    if(q==d){
      getperm(d,tgpm);
      q=0;
      gettimeofday(&tv, NULL);
      nt=(tv.tv_sec*1000000+tv.tv_usec);
      if((nt-stt)>=1988000){break;}
    }
  }
  for(tg=0;tg<d;tg++){
    for(i=1;i<=ck;i++){dv[i]=delq(tg,i);}
    getperm(ck,p);
    for(i=0;i<ck;i++){
      if(dv[res[tg]]<=dv[p[i]+1]){res[tg]=p[i]+1;}
    }
  }
  for(i=0;i<d;i++){
    printf("%d\n",res[i]);
  }
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  
  int i = 0;
  while(i < N){
    int l ,r;
    cin >> l >> r;
    sum += (r - l + 1);
    i++;
  }
  cout << sum << endl;
}


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

int main() {
    int N,K;
    cin >> N >> K;
    vector<bool>vec(10,true);
    for(int i = 0; i < K; i++) {
        int D;
        cin >> D;
        vec[D] = false;
    }
    for(int i = N; i < 1000000; i++) {
        string S = to_string(i);
        bool ok = true;
        for(char x : S) {
            if(!vec[x-'0']) {
                ok = false;
            }
        }
        if(ok) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 200010;
const int MAXM = 200010;
const int MAXK = 110;
const int MAXQ = 200010;

ll l, r, dp[65][2][2][2];

ll solve(int d, bool top, bool bot, bool lead) {
    if (d < 0) return 1;
    if (dp[d][top][bot][lead] != -1) return dp[d][top][bot][lead];
    ll res = 0;

    FOR(xbit,0,1)
        FOR(ybit,0,1) {
            if (xbit > ybit) continue;
            if (!lead && xbit != ybit) continue;

            int rh = !!(r & (1LL << d));
            int lh = !!(l & (1LL << d));

            if (top && rh < ybit) continue;
            if (bot && lh > xbit) continue;

            res = (res + solve(d-1, top && rh == ybit, bot && lh == xbit, lead || ybit == 1)) % MODBASE;
        }

    return dp[d][top][bot][lead] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> l >> r;
    FOR(i,0,62) FOR(j,0,1) FOR(k,0,1) FOR(p,0,1) dp[i][j][k][p] = -1;
    cout << solve(62, true, true, false);
    return 0;
}


Measured memory_bytes: 256