akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define DEBUG true
#define $(x) {if (DEBUG) {cout << #x << " = " << (x) << endl;}}


int main() {
    LL N, Q;
    cin >> N >> Q;
    vector<pair<LL, pair<bool, LL>>> events;
    REP(i, N) {
        LL s, t, x;
        cin >> s >> t >> x;   // 区間[s, t)とそのラベルx
        events.PB(MP(s - x, MP(true, x)));   // true: 区間開始、false: 区間終了
        events.PB(MP(t - x, MP(false, x)));   // 実質 s == t であっても t = s + 1 とする
    }
    FSORT(events);   // 区間の座標だけで
    VI D(Q);
    REP(i, Q) {
        cin >> D[i];
    }

    LL q_index = 0;
    set<LL> curr_pos;   // 同じposをもつ複数の区間は重ならないとする(重なる場合はmultiset？)
    EACH(x, events) {
        auto time = x.first;
        auto entering = x.second.first;
        auto pos = x.second.second;
        //cout << time << " " << entering << " " << pos << endl;
        while (q_index < Q && D[q_index] < time) {
            q_index++;
            if (SZ(curr_pos) == 0) {
                cout << "-1" << endl;
            } else {
                cout << *curr_pos.begin() << endl;
            }
        }
        if (entering) {
            curr_pos.insert(pos);
        } else {
            curr_pos.erase(pos);
        }
        /*EACH(p, curr_pos) {
            $(p);
            }*/
    }
    while (q_index < Q) {
        q_index++;
        cout << "-1" << endl;
    }
	
    return 0;
}


Measured memory_bytes: 22856
using System;

public class Program
{
	public static void Main(string[] args)
	{
		var ss = new StreamScanner();
		//---------------------------------
		var x = ss.Next<int>();
		var y = ss.Next<int>();
		int mul = x * y;
		int sum = 2 * x + 2 * y;
		Console.WriteLine(mul+" "+sum);

		/*
		//????????????int, double, string?????????????????£????????????
		int i = ss.Next<int>();
		double d = ss.Next<double>();
		string s = ss.Next<string>();

		//?????°???????????????????????¨?????????????????????????????????????????????????´???????
		int[] array = ss.Next<int>(10);
		*/
		//---------------------------------
	}
}

public class StreamScanner
{
	private readonly char[] _c = { ' ' };
	private int _index = -1;
	private string[] _input = new string[0];
	private readonly System.IO.StreamReader _sr = new System.IO.StreamReader(Console.OpenStandardInput());

	public T Next<T>()
	{
		if (_index == _input.Length - 1)
		{
			_index = -1;
			while (true)
			{
				string rl = _sr.ReadLine();
				if (rl == null)
				{
					if (typeof(T).IsClass) return default(T);
					return (T)typeof(T).GetField("MinValue").GetValue(null);
				}
				if (rl != "")
				{
					_input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
					break;
				}
			}
		}
		return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
	}

	public T[] Next<T>(int x)
	{
		var ret = new T[x];
		for (var i = 0; i < x; ++i) ret[i] = Next<T>();
		return ret;
	}

	public T[][] Next<T>(int x, int y)
	{
		var ret = new T[y][];
		for (var i = 0; i < y; ++i) ret[i] = Next<T>(x);
		return ret;
	}
}

Measured memory_bytes: 9764
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <limits>
#include <math.h>
#include <map>
#include <string>

using namespace std;
typedef long long ll;

int main() {
  string s2;
  cin >> s2;
  string s = "???????" + s2;
  int cur = s.size() - 1;

  string t = "";
  while (cur > 6) {
    if (s[cur] == 'r' && s[cur - 5] == 'e') {
      cur -= 6;
      t = "eraser" + t;
    } else if (s[cur] == 'r' && s[cur - 6] == 'd') {
      cur -= 7;
      t = "dreamer" + t;
    } else if (s[cur] == 'e' && s[cur - 4] == 'e') {
      cur -= 5;
      t = "erase" + t;
    } else if (s[cur] == 'm' && s[cur - 4] == 'd') {
      cur -= 5;
      t = "dream" + t;
    } else {
      puts("NO");
      return 0;
    }
  }
  if (s2.compare(t) == 0) {
    puts("YES");
  } else {
    puts("NO");
  }
  return 0;
}


Measured memory_bytes: 796
#include <stdio.h>

int main (void){
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);

    for(int j = 1; j<=1000; j++){
        if((int)(j*0.08) == a && (int)(j*0.1) == b){
         printf("%d\n",j);
         return 0;     
        }
    }
    printf("-1\n");
    return 0;
}


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


struct Card { char suit, value; };

// バブルソート
void bubble(struct Card A[], int N) {
    for ( int i =0; i < N; i++){
        for ( int j = N - 1; j >= i + 1; j-- ) {
            if ( A[j].value < A[j - 1].value ) {
                Card t = A[j]; A[j] = A[j - 1]; A[j - 1] = t;
            }
        }
    }
}

// 選択ソート
void selection(struct Card A[], int N) {
    for ( int i = 0; i < N; i++) {
        int minj = i;
        for ( int j = i; j < N; j++ ) {
            if ( A[j].value < A[minj].value ) minj = j;
        }
        Card t = A[i]; A[i] = A[minj]; A[minj] = t;
    }
}

void print(struct Card A[], int N) {
    for ( int i = 0; i < N; i++ ) {
        if (i) cout << " ";
        cout <<  A[i].suit << A[i].value;
    }
    cout << endl;
}

// バブルソートと選択ソートの結果を比較
bool isStable( struct Card C1[], struct Card C2[], int N) {
    for ( int i = 0; i < N; i++ ) {
        if ( C1[i].suit != C2[i].suit ) return false;
    }
    return true;
}

int main() {
    Card C1[100], C2[100];
    int N;
    char ch;

    cin >> N;
    for ( int i = 0; i < N; i++ ) {
        cin >> C1[i].suit >> C1[i].value;
        C2[i] = C1[i];
    }

    for ( int i = 0; i < N; i++ ) C2[i] = C1[i];

    bubble(C1, N);
    selection(C2, N);

    print(C1, N);
    cout << "Stable" << endl;
    print(C2, N);
    if ( isStable(C1, C2, N) ) {
        cout << "Stable" << endl;
    
    } else {
        cout << "Not stable" << endl;
    }

    return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> H(n); rep(i, n) cin >> H[i];
  int ans = 0;
  while(1) {
    int cnt = 0;
    bool flag = false;
    rep(i, n) {
      if(flag && H[i]<=0) {
        cnt++; flag = false;
      } else if(!flag && H[i]>0) {
        flag = true;
      }
    }
    if(flag) cnt++;
    if(cnt) {
      ans += cnt;
      rep(i, n) H[i]--;
    } else {
      break;
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3556
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate など
#include <stdexcept>
#include <cassert> // assert
using namespace std;

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

// #define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll MOD = 1'000'000'007;
constexpr int LARGE = 1000000LL + 9;
ll n;
ll res = 0;
int bound;
ll p;
array<bool, LARGE> isprimes;

bool isprime(ll m)
{
    for (int i = 2; (ll)i * (ll)i <= m; i++)
    {
        if (m % i == 0)
        {
            return false;
        }
    }
    return true;
}

// n < p * p なる素因数 p があるか？
void test()
{
    ll maxdiv = 1;
    for (int i = 1; (ll)i * (ll)i <= n; i++)
    {
        if ((ll)i * (ll)i == n)
        {
            bound = i;
            p = 0;
            return;
        }
        if (n % i == 0)
        {
            maxdiv = i;
        }
    }
    bound = maxdiv;
    p = n / maxdiv;
    p = (isprime(p) ? p : 0);
}

int main()
{
    cin >> n;
    test();
    if (p > 0)
    {
        res++;
    }

    // 素因数分解する
    REP(i, bound + 1)
    {
        isprimes.at(i) = true;
    }
    for (int i = 2; i < bound + 1; i++)
    {
        if (isprimes.at(i) == false)
        {
            continue;
        }
        for (int j = 2; (ll)i * (ll)j < bound + 1; j++)
        {
            isprimes.at(i * j) = false;
        }
        ll pw = i;
        for (int k = 1; n % pw == 0; k++)
        {
            res++;
            n = n / pw;
            pw *= i;
        }
    }

    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 4528
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
ll dp[105][100005],n,k,a[105];

int main()
{ quick;

	cin>>n>>k;
	fab(0,n,i)
	cin>>a[i];
	ll pref[k+1]={0};
	dp[0][0]=1;
	pref[0]=1;
	fab(1,a[0]+1,i)
	{
		dp[0][i]=1;
		//pref[i]=pref[i-1]+dp[0][i];

	}
	fab(1,k+1,i)
	pref[i]=(pref[i-1]+dp[0][i])%MOD;
	fab(0,n,i)
	dp[i][0]=1;

	fab(1,n,i)
	
	{
		fab(1,k+1,j)
		{
			ll tot=max((ll)(0),j-a[i]),op;
			if(tot==0)
				op=(pref[j])%MOD;
			else
				op=(pref[j]-pref[tot-1])%MOD;
			//assert(op>=0);
			op=op+MOD;

			dp[i][j]=(op)%MOD;//+(tot==0?j:a[i]);


			

		}
		//cout<<pref[0]<<" ";
		fab(1,k+1,j)
		{
			//cout<<pref[j]<<" ";
			pref[j]=(pref[j-1]%MOD+dp[i][j])%MOD;
		}
		//cout<<endl;

	}
	//cout<<"\n\n";
	/*fab(0,n,i)
	{fab(0,k+1,j)
	cout<<dp[i][j]<<" ";
	cout<<endl;}*/
	cout<<dp[n-1][k]%MOD;


	return 0;
}


Measured memory_bytes: 80896
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <numeric>
#include <vector>
#include <cassert>
#include <ctime>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int>> vvi;
typedef  pair<int,int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000000007;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
int main() {
    int n, m;
    set<int> f1, fn;
    scanf("%d %d", &n, &m);
    while(m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if(a == 1) f1.insert(b);
        if(b == n) fn.insert(a);
    }
    vector<int> res;
    set_intersection(f1.begin(), f1.end(), fn.begin(), fn.end(), back_inserter(res));
    if(res.size()) printf("POSSIBLE");
    else printf("IMPOSSIBLE");
    return 0;
}


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

int main(){
	int N,K,j,i;
	cin>>N>>K;
  	vector<char>s(K);
  	for(i=0;i<K;++i)cin>>s[i];
  	for(i=N;;++i){
    	string t=to_string(i);
      	for(j=0;j<K;++j)if(t.find(s[j],0)!=-1)break;
      	if(j==K){cout<<t<<endl;return 0;}
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

string s;
Int ans[5500000];
Int sum;

int main(){
    cin >> s;
    int n = s.size() + 1;
    if(s[0] == '<')ans[0] = 0;
    if(s[n-1] == '>')ans[n] = 0;
    for(int i = 1;i < n;i++){
        if(s[i-1] == '>' && s[i] == '<')ans[i] = 0;
    }
    for(int i = 0;i < n;i++){
        if(s[i] == '<')ans[i+1] = ans[i] + 1;
    }
    for(int i = n-1;i >= 0;i--){
        if(s[i] == '>')ans[i] = ans[i+1] + 1;
    }
    for(int i = 1;i < n;i++){
        if(s[i-1] == '<' && s[i] == '>')ans[i] = max(ans[i-1], ans[i+1]) + 1;
    }
    for(int i = 0;i <= n;i++)sum += ans[i];
    cout << sum << endl;
    return 0;
}

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

using edges = vector<int>;
using Graph = vector<edges>;

int N, Q;
Graph G;
vector<int> val, ans;

void dfs(int v, int pv, int s) {
    ans[v] = s + val[v];
    for (int nv : G[v]) if (nv != pv) {
        dfs(nv, v, ans[v]);
    }
}

int main() {
    cin >> N >> Q;
    G.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    val.resize(N, 0);
    ans.resize(N);
    for (int i = 0; i < Q; ++i) {
        int p, x;
        cin >> p >> x;
        p--;
        val[p] += x;
    }
    dfs(0, -1, 0);
    for (int i = 0; i < N; ++i) {
        cout << ans[i] << " \n"[i + 1 == N];
    }
}

Measured memory_bytes: 24320
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
#define INF __INT32_MAX__
#define LINF __LONG_LONG_MAX__

bool check(vi list, int val) {
    bool ok = true;

    while (val > 0) {
        int digit = val % 10;
        bool tmpng = false;
        rep(i, list.size()) {
            if (digit == list[i]) {
                tmpng = true;
                ok = false;
                break;
            }
        }
        if (tmpng) break;

        val /= 10;
    }

    return ok;
}

int main() {
    int N, K;
    cin >> N >> K;
    vi D(K);
    rep(i, K) {
        cin >> D[i];
    }

    while (1) {
        if (check(D, N)) {
            break;
        }
        N++;
    }

    cout << N << endl;
}

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

int main() {
    ll A, B, C, D, T;
    cin >> A >> B >> C >> D;

    ll M = max(C, D);
    ll N = min(C, D);

    while (T = M % N) {
        M = N;
        N = T;
    }

    ll G = N;
    ll L = (C * D) / G;

    ll X = B - (B / C) - (B / D) + (B / L);
    ll Y = (A - 1) - ((A - 1) / C) - ((A - 1) / D) + ((A - 1) / L);

    cout << X - Y << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans += a[i]/2;
        if(a[i]%2 && i != n-1 && a[i+1] > 0){
            a[i+1]--;
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int A, B, C, K;
    cin >> A >> B >> C >> K;

    if(K % 2 == 0){
        cout << A - B;
    }else{
        cout << B - A;
    }

    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max = 5e2 + 5, Mod = 1e9 + 7;
int n;
vector<int> a[1005];
vector<int> G[1000005];
int dp[1000005];

int H(int x, int y)
{
	if (x > y)
		swap(x, y);
	return 1000 * x + y;
}

int Try(int u)
{
	if (dp[u] != -1)
		return dp[u];
	dp[u] = 1;
	for (auto v : G[u])
		dp[u] = max(dp[u], Try(v) + 1);
	return dp[u];
}
bool v1[1000005], v2[1000005];

bool check(int u)
{
	if (v2[u])
		return 1;
	if (v1[u])
		return 0;
	v1[u] = v2[u] = 1;
	for (auto v : G[u])
		if (check(v))
			return 1;
	v2[u] = 0;
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < n - 1; j++)
		{
			int x;
			cin >> x;
			a[i].push_back(x);
		}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < n - 1; j++)
		{
			int u = H(i, a[i][j - 1]);
			int v = H(i, a[i][j]);
			G[u].push_back(v);
		}
	}
	memset(dp, -1, sizeof(dp));
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		if (check( H(i,j) ))
		{
			cout << -1 << endl;
			return 0;
		}
	int ans = 0;
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			ans = max(ans,Try(H(i,j) ));
		cout << ans << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

int main() {
    ll n, k, x, y; cin >> n >> k >> x >> y;
    ll m = min(n, k);
    ll ans = m * x;
    n -= m;
    ans += (n * y);
    cout << ans << endl;
}


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

int a[100000], b[100000], c[100000], n, m;
ll s[100000];
int bit[200000];
vector<P>v;

void add(int k, int x) {
	while (k <= v.size()) {
		bit[k] += x;
		k += k&-k;
	}
}
int sum(int k) {
	int res = 0;
	while (k) {
		res += bit[k];
		k -= k&-k;
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	rep(i, n)v.push_back(P(0, i));
	rep(i, m) {
		scanf("%d%d", &a[i], &b[i]); b[i]--;
		if (a[i] == 0) {
			scanf("%d", &c[i]);
			s[b[i]] += c[i];
			v.push_back(P(s[b[i]], b[i]));
		}
	}
	auto f = [](P a, P b) {
		if (a.first == b.first)return a.second > b.second;
		return a.first < b.first;
	};
	sort(v.begin(), v.end(), f);
	rep(i, n)add(i + 1, 1);
	memset(s, 0, sizeof(s));
	rep(i, m) {
		if (a[i] == 0) {
			add(lower_bound(v.begin(), v.end(), P(s[b[i]], b[i]), f) - v.begin() + 1, -1);
			s[b[i]] += c[i];
			add(lower_bound(v.begin(), v.end(), P(s[b[i]], b[i]), f) - v.begin() + 1, 1);
		}
		else {
			int l = 1, r = v.size();
			while (l != r) {
				int t = (l + r) / 2;
				if (sum(t) >= n - b[i])r = t;
				else l = t + 1;
			}
			printf("%lld %lld\n", v[l - 1].second + 1, v[l - 1].first);
		}
	}
}

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

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int[] fib = new int[n+1];
		fib[0] = 1;
		fib[1] = 1;
		for (int i=2; i<=n; i++) {
			fib[i] = fib[i-1] + fib[i-2]; 
		}
		System.out.println(fib[n]);
	}
}

Measured memory_bytes: 17324
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 200005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

int N, M, a[MAXM], b[MAXM],  cur, tmp, level = 0;
vi d[MAXM] = {}, dist(MAXM, -1);
queue<int> q;

void dfs(){
    q.push(0);
    dist[0] = 0;

    while(!q.empty()){
        cur = q.front();
        q.pop();
        
        rep(i, d[cur].size()){
            tmp = d[cur][i];
            if(dist[tmp]==-1){
                // cout << tmp << " ";
                q.push(tmp);
                dist[tmp] = dist[cur] + 1;
            }
        }
        // cout << endl;
    }
}

void solve(){
    dfs();

    if(dist[N-1]==2)
        cout << "POSSIBLE" << endl;
    else
        cout << "IMPOSSIBLE" << endl;
}

int main(){
    cin >> N >> M;

    rep(i,M){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        d[a[i]].push_back(b[i]);
        d[b[i]].push_back(a[i]);
    }

    solve();
}


Measured memory_bytes: 14704
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    let ans = (1..4).any(|c| a*b*c % 2 != 0);
    println!("{}", if ans { "Yes" } else { "No" });
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
//#define kk
//#define int long long
#define FOR(i, n) for(int i=1; i<=n; i++)
#define ff first
#define ss second
#define ll int
#define inf 1000000000
#define pb push_back
#define mod 1000000007
 
const long long INF=1e18+5;
typedef pair<int, int> pi;

double h[3000];
double dp[3000][3000];

void solve(){
	int n;
	cin>>n;
	
	FOR(i, n) cin>>h[i];
	
	dp[0][0]=1;
	
	FOR(i, n) dp[i][0]=dp[i-1][0]*(1-h[i]);
	
	FOR(i, n)
		FOR(j, i)
			dp[i][j]=((dp[i-1][j-1]*h[i])+(dp[i-1][j]*(1-h[i])));
			
	double ans=0;
	
	for(int i=n/2+1; i<=n; i++) ans+=dp[n][i];
	
	cout<<ans<<endl;
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cout<<fixed<<setprecision(10);
	
	#ifdef kk
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	
	int T=1;
	//cin>>T;
	
	while(T--){
		solve();
	}
}


Measured memory_bytes: 49972
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,h[200500],a[200500];
ll dp[200500],tr[200500];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void add(int pos,ll val)
{
	for (int i=pos;i<=n;i+=lowbit(i)) tr[i]=max(tr[i],val);
}

ll query(int pos)
{
	ll ans=0;
	for (int i=pos;i;i-=lowbit(i)) ans=max(tr[i],ans);
	return ans;
}

int main()
{
	n=read();
	rep(i,1,n) h[i]=read();
	rep(i,1,n) a[i]=read();
	ll ans=0;
	rep(i,1,n)
	{
		dp[i]=query(h[i])+a[i];
		add(h[i],dp[i]);ans=max(ans,dp[i]);
	}
	printf("%lld",ans);
	return 0;
}
	


Measured memory_bytes: 4992
S = gets.chomp

if S.count("B") == 0 and
   S.count("D-Z") == 0 and
   S.count("A") == 1 and
   S.count("C") == 1 and
   S[0] == 'A' and
   S[2..-2].count('C') == 1
    puts "AC"
else
  puts "WA"
end

Measured memory_bytes: 1788
n = int(input())
a = []
for i in range(3):
    a.append(list(input()))
c = 0
for i in range(n):
    d,e = [],[]
    for j in range(3):
        d.append(a[j][i])
    e = [d.count(i) for i in d]
    c += 3 - max(e)
print(c)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int n;
  cin >> n;
  vector<string> v(n);
  rep(i,n) cin >> v[i];
  map<string, int> mp;
  char prev = v[0][0];
  rep(i,n) {
    if (mp[v[i]] || prev != v[i][0]) {
      cout << "No" << endl;
      return;
    }
    prev = v[i][v[i].size()-1];
    mp[v[i]]++;
  }
  cout << "Yes" << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 3576
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let mut n: u64 = sc.read();
    let mut divisors = vec![];
    for prime in 2.. {
        if prime * prime > n {
            break;
        }
        if n % prime == 0 {
            let mut count = 0;
            while n % prime == 0 {
                n /= prime;
                count += 1;
            }
            divisors.push((prime, count));
        }
    }
    if n != 1 {
        divisors.push((n, 1));
    }

    let min = divisors.len();
    let mut max = 1;
    for (_, count) in divisors.into_iter() {
        max *= count + 1;
    }

    println!("{} {}", min, max - 1);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



Measured memory_bytes: 5032
#include <stdio.h>

void merge_sort(long long x[], int n)
{
	static long long y[200001] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p] < x[q])? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, a, b;
	long long K, A[200001], B[200001];
	scanf("%d %lld", &N, &K);
	for (i = 0, a = 0, b = 0; i < N; i++) {
		scanf("%lld", &(A[a]));
		if (A[a++] < 0) B[b++] = -A[--a];
	}
	if (a > 0) merge_sort(A, a);
	if (b > 0) merge_sort(B, b);
	
	int j;
	long long L, R, M, sum;
	if (a > 0 && b > 0) {
		L = -(A[a-1] * B[b-1] + 1);
		R = (A[a-1] * A[a-1] > B[b-1] * B[b-1])? A[a-1] * A[a-1] + 1: B[b-1] * B[b-1] + 1;
	} else if (a > 0) {
		L = -1;
		R = A[a-1] * A[a-1] + 1;
	} else {
		L = 0;
		R = B[b-1] * B[b-1] + 1;
	}
	while (L < R) {
		M = (L + R >= 0)? (L + R) / 2: (L + R - 1) / 2;
		sum = 0;
		
		for (i = 0, j = a; i < a; i++) {
			for (; j > 0 && A[j-1] * A[i] > M; j--);
			sum += j;
			if (j > i) sum--;
		}
		for (i = 0, j = b; i < b; i++) {
			for (; j > 0 && B[j-1] * B[i] > M; j--);
			sum += j;
			if (j > i) sum--;
		}
		sum /= 2;
		for (i = 0, j = b; i < a; i++) {
			for (; j > 0 && B[j-1] * A[i] >= -M; j--);
			sum += b - j;
		}
		fflush(stdout);
		
		if (sum < K) L = M + 1;
		else R = M;
	}

	printf("%lld\n", L);
	fflush(stdout);
	return 0;
}

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

int main(){
	int b,r,g,c,s,t;
	while(cin >> b >> r >> g >> c >> s >> t , b+r+g+c+s+t != 0){
		int x = b * 5 + r * 3 ;
		cout << 100+x*15+g*7+c*2+(b+r)*15-x*2-(t-x-s)*3 << endl;
	}
}

Measured memory_bytes: 0
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> ump;
typedef pair<ll, ll> P;

ump mp;
bool seen[8][8];
char a[8][8];
int h, w;

bool dfs(ll i, ll j, ll ti, ll tj) {
    seen[i][j] = true;
    if (i == ti && j == tj) return true;
    if (i + 1 <= h - 1 && !seen[i + 1][j] && a[i + 1][j] == '#') return dfs(i + 1, j, ti, tj);
    if (j + 1 <= w - 1 && !seen[i][j + 1] && a[i][j + 1] == '#') return dfs(i, j + 1, ti, tj);
    return false;
}

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        cin >> h >> w;
        rep(i, h) rep(j, w) cin >> a[i][j];

        if (dfs(0, 0, h - 1, w - 1)) {
            rep(i, h) {
                rep(j, w) {
                    if (a[i][j] == '#' && !seen[i][j]) {
                        cout << "Impossible" << endl;
                        return 0;
                    }
                }
            }
            cout << "Possible" << endl;
        } else {
            cout << "Impossible" << endl;
        }


#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
// Original macro is in https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = || -> String {
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [$t:tt]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// for adhoc read (ex. https://atcoder.jp/contests/abc112/tasks/abc112_a)
#[allow(dead_code)]
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

#[allow(dead_code)]
fn lcm(a: i64, b: i64) -> i64 {
    a*b / gcd(a, b)
}

fn main() {
    input! { n: usize, a: [i32;n] }

    let mut sorted = a.clone();
    sorted.sort();

    let mut check = true;
    for i in 0..n {
        if a[i] != sorted[i] {
            check = false;
            break;
        }
    }
    if check {
        println!("YES");
        return;
    }

    for i in 0..n-1 {
        for j in i+1..n {
            let mut b = a.clone();
            let tmp = b[i];
            b[i] = b[j];
            b[j] = tmp;

            // println!("b {:?}", b);
            // println!("sorted {:?}", sorted);

            let mut is_ok = true;
            for k in 0..n {
                if b[k] != sorted[k] {
                    is_ok = false;
                    break;
                }
            }
            if is_ok {
                println!("YES");
                return;
            }
        }
    }
    println!("NO");
}


Measured memory_bytes: 4352
import math
N = int(input())

def eval_ab(a, b):
    if a == 1 or b == 1:
        return a + b - 1
    else:
        return a + b - 2
    
min_e = N - 1
a = int(math.sqrt(N)) + 2
for i in range(1, a):

    if N % i == 0:
        j = N // i
        e = eval_ab(i, j)
        min_e = min(e, min_e)

print(min_e)

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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<ll> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;



int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> dp(n + 1, 0);

    for (int i = n; i >= 0; i--) {
        if (s[i] == '0') dp[i] = i;
        else dp[i] = dp[i + 1];
    }
    int now = n;

    vector<int> ans;
    while (now > 0) {
        int next = dp[max(now - m, 0)];
        if (next == now) {
            cout << -1 << endl;
            ret();
        }
        ans.push_back(now - next);
        now = next;
    }

    reverse(ans.begin(), ans.end());

    for (int a : ans) cout << a << ' ';

}

Measured memory_bytes: 4288
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
int main(){
	ll n;
	cin>>n;
	vector<ll> a,od,ev;
	a.pb(0);
	for(int i=1;i<=n;i++){
		ll x;
		cin>>x;
		a.pb(x);
		if( i%2==1)od.pb(x);
		else ev.pb(x);
	}
	sort( od.begin(), od.end() );
	sort( ev.begin(), ev.end() );
	vector<ll> us;
	ll ans = 0;
	if( od[od.size()-1]<0 && ev[ev.size()-1]<0){
		ll tmp = max(od[od.size()-1],ev[ev.size()-1]);
		ans = tmp;
		ll f=0;
		for(int i=1;i<=n;i++){
			if( a[i]==tmp && f==0){
				us.pb(i);
				f=1;
			}
		}
	}
	else{
		ll odm = -1, evm = -1;
		vector<ll> odu,evu;
		for(int i=1;i<=n;i++){
			if(a[i]>=0){
				if(i%2==1){
					if(odm==-1)odm=0;
					odu.pb(i);
					odm += a[i];
				}
				else{
					if(evm==-1)evm=0;
					evu.pb(i);
					evm += a[i];
				}
			}
		}
		if( odm>evm ){
			ans = odm;
			us = odu;
		}
		else{
			ans = evm;
			us = evu;
		}
	}
	cout<<ans<<endl;
	vector<ll> tej;
	reverse(us.begin(),us.end());
	for(int i=0;i<us.size();i++){
		if(i==0){
			for(int j=n;j>=us[i]+1;j--){
				tej.pb(j);
			}
		}
		if(i!=us.size()-1){
			ll mid = (us[i]+us[i+1])/2;
			ll tur = (us[i]-us[i+1])/2;
			for(int j=0;j<tur;j++){
				tej.pb(mid-j);
			}
		}
		if(i==us.size()-1){
			for(int j=1;j<us[i];j++){
				tej.pb(1);
			}
		}
	}
	cout<<tej.size()<<endl;
	for(int i=0;i<tej.size();i++){
		cout<<tej[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
const int N=200050;
using namespace std;
int gi(){
  char ch=getchar(); int x=0,q=0;
  while(ch<'0' || ch>'9') (ch=='-'?q=1:0),ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
char s[N];
int sum[N][26],n,nx[N],cir;
ll calc(ll m,int c){
  if (m<=n) return sum[m][c];
  if (n%cir==0)
    return 1ll*m/cir*sum[cir][c]+sum[m%cir][c];
  else{
    ll a=cir,b=n,sa=sum[cir][c],sb=sum[n][c];
    while(m>=a+b){
      b+=a,sb+=sa;
      a=b-a,sa=sb-sa;
    }
    return sb+calc(m-b,c);
  }
}
int main(){
  scanf("%s",s+1);
  n=strlen(s+1)/2;
  for (int i=1; i<=n; ++i){
    for (int j=0; j<26; ++j)
      sum[i][j]=sum[i-1][j];
    ++sum[i][s[i]-'a'];
  }
  for (int i=2; i<=n; ++i){
    int j=nx[i-1];
    while(j&&s[j+1]!=s[i]) j=nx[j];
    nx[i]=j+(s[j+1]==s[i]);
  }
  cir=n-nx[n];
  ll l,r;
  cin>>l>>r;
  for (int i=0; i<26; ++i)
    printf("%lld ",calc(r,i)-calc(l-1,i));
  return 0;
}


Measured memory_bytes: 12288
n, m = map(int, input().split())
s = list(input())
s = s[::-1]
ans_list = []

for i in range(n+1):
    if i == 0:
        tmp_count = 0
        tmp_ans = 0
    else:
        tmp_count += 1
        if s[i] == '0':
            tmp_ans = tmp_count
        if tmp_count == m:
            ans_list.append(tmp_ans)
            tmp_count -= tmp_ans
            tmp_ans = tmp_count

if 1 <= tmp_ans <= m:
    ans_list.append(tmp_ans)
if ans_list.count(0) >= 1:
    ans_list = [-1]
    
for i in range(len(ans_list)):
    ans_list[i] = str(ans_list[i])
ans_list = ans_list[::-1]
print(' '.join(ans_list))

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

const int N = 1e5 + 10;
const long long mod = 1e9 + 7;

long long a[N], dp[N], sum[N];

int main(){
	int n, p, last;
	long long A, B, ans;
	scanf("%d %lld %lld",&n,&A,&B);
	for (int i = 1; i <= n; i++) scanf("%lld",&a[i]);
	if (A < B) swap(A, B);
	for (int i = 3; i <= n; i++){
		if (a[i] - a[i - 2] < B){
			printf("0\n");
			return 0;
		}
	}
	dp[0] = sum[0] = 1; p = last = 0;
	for (int i = 1; i <= n; i++){
		while (p < i - 1 && a[i] - a[p + 1] >= A) p++;
		if (last <= p) dp[i] += (sum[p] - (last ? sum[last - 1] : 0) + mod) % mod;
		sum[i] = (sum[i - 1] + dp[i]) % mod;
		if (i > 1 && a[i] - a[i - 1] < B) last = i - 1; 
	}
	ans = 0;
	for (int i = n; ~i; i--){
		ans += dp[i];
		ans %= mod;
		if (i > 0 && i < n && a[i + 1] - a[i] < B) break;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2560
n, k = gets.split.map(&:to_i)
heights = []
minimum = 100000000000000000000000000000
n.times do
  heights << gets.to_i
end

heights = heights.sort

(0..heights.size - k).each do |i|
  selected_trees = heights[i..i+k-1]
  diff = selected_trees[-1] - selected_trees[0]
  if minimum > diff
    minimum = diff
  end
end

puts minimum

Measured memory_bytes: 4528
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include<iomanip>
#include <fstream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end()
#define ITE(c) typeof((c).begin())

#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))

using namespace std;

int main(){
	int n;
	cin>>n;
	rep(I,n){
		int no=0, po=0;
		int base[3]={0,0,0};
		while(no<3){
			string cmd;
			cin>>cmd;
			if(cmd=="HIT"){
				if(base[2]) po++;
				for(int i=2;i>0;--i){
					base[i]=base[i-1];
				}
				base[0]=1;
			}else if(cmd=="OUT"){
				no++;
			}else if(cmd=="HOMERUN"){
				int co=0;
				rep(i,3){
					if(base[i]){
						co++;
						base[i]=0;
					}
				}
				po+=co+1;
			}
		}
		cout<<po<<endl;
	}
	return 0;
}

Measured memory_bytes: 1208
package main

import "fmt"

func main() {
	var h, w int
	fmt.Scanf("%d %d", &h, &w)
	if h == 1 || w == 1 {
		fmt.Println(1)
	} else if h%2 == 0 || w%2 == 0 {
		fmt.Println(h * w / 2)
	} else {
		fmt.Println((h-1)/2*w + (w+1)/2)
	}
}


Measured memory_bytes: 1836
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int a = sc.nextInt();
      	int b = sc.nextInt();
      	int c = sc.nextInt();
      	int d = sc.nextInt();      	
      	
      	System.out.println(Math.max(a*b, c*d));
    }
}

Measured memory_bytes: 35656
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 100010;
int N;
int x[MAX], y[MAX];
VI graph[MAX];

int dfs(int now, int prev) {
    int res = 0;
    FORE(e, graph[now]) {
        if (e != prev) {
            res ^= dfs(e, now);
        }
    }
    return res + 1;
}

int main(void) {
    scanf("%d", &N);
    int oneCnt = 0;
    REP(i, N - 1) {
        scanf("%d%d", x + i, y + i);
        oneCnt += ((x[i] == 1) || (y[i] == 1));
        x[i]--;
        y[i]--;
        graph[x[i]].EB(y[i]);
        graph[y[i]].EB(x[i]);
    }
    if (oneCnt == 1) {
        cout << "Alice" << endl;
        return 0;
    }
    else {
        cout << (dfs(0, -1) != 1 ? "Alice" : "Bob") << endl;
    }
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define LL long long
#define P 1000000007
#define M 1000005
using namespace std; 
int main() { 
	int n,x,a,s=0,cnt=1;
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		s+=a;
		if(s<=x)cnt++;
		else break;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  double r = 1 / 1.08;
  double x = r * n;
  double xp = ceil(x);
  double yp = floor(x);
  if(floor(xp*1.08) == n){
    cout<<floor(xp)<<endl;
  }
  else if(floor(yp*1.08) == n){
    cout<<floor(yp)<<endl;
  }
  else{
      cout<<":("<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long int ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<vi > vvi;
typedef std::vector<vll > vvll;
typedef std::pair<int,int> ii;
typedef std::pair< ll, ll > lp;
typedef std::vector<ii> vii;
typedef std::vector<vii > vvii;

#define pb push_back 
#define PB pop_back
#define pf push_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)
#define lb(a,b) lower_bound(all(a),b)
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define in1(a,n) F(i,1,n)cin>>a[i]
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define ff first
#define ss second
#define F(i,a,b) for (ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define rep(i,n) F(i,0,n-1)
#define clr(a) (a).clear()
#define rz resize
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin() ,(a).rend()
#define endl '\n'

#define mod 1000000007

ll add(ll a, ll b){return (a%mod + b%mod)%mod;}
ll sub(ll a , ll b){return (a%mod - b%mod + mod)%mod;}
ll mul(ll a, ll b){return (a%mod * b%mod)%mod;}
ull poww(ull a,ull b){ull res=1;while(b){if(b&1){res*=a;}a=a*a;b>>=1;}return res;}
ll poww(ll a,ll b,ll MOD){ll res=1;while(b){if(b&1){res*=a;res%=MOD;}a=a*a;a%=MOD;b>>=1;}return res;}

#define dbg(x) cout<<#x<<" :: "<<x<<endl;
#define dbg2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define dbg4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;

//end of template

int main(int argc, char const *argv[])
{
	crap;
	int n, k;
	cin >> n >> k;
	cout << n - k + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
num=int(input())
AC=0
WA=0
TLE=0
RE=0
for i in range(num):
    date=input()
    if date=="AC":
        AC += 1
    elif date=="WA":
        WA += 1
    elif date=="TLE":
        TLE += 1
    else:
        RE += 1
print("AC x "+str(AC))
print("WA x "+str(WA))
print("TLE x "+str(TLE))
print("RE x "+str(RE))

Measured memory_bytes: 9040
import java.util.Scanner;

//20180509
//02

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

		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int[][] a = new int[n][m];
		int[] b = new int[m];

		for(int y = 0;y < n;y++) {
			for (int x = 0; x < m; x++) {
				a[y][x] = scanner.nextInt();
			}
		}

		for(int y = 0;y < m;y++) {
			b[y] = scanner.nextInt();
		}

		for(int y = 0;y < n;y++) {
			int ans = 0;
			for (int x = 0; x < m; x++) {
				ans += a[y][x] * b[x];
			}
			System.out.println(ans);
		}

		scanner.close();
    }
}


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

int main() {
    string S;
    cin >> S;
    bool ans = false;
    if (S[0]==S[1] && S[2]==S[3] && S[0]!=S[2]) ans = true;
    if (S[0]==S[2] && S[1]==S[3] && S[0]!=S[1]) ans = true;
    if (S[0]==S[3] && S[1]==S[2] && S[0]!=S[1]) ans = true;

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

Measured memory_bytes: 256