akhauriyash/Code-Regression huggingface dataset:
//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up

void IO(){
#ifndef ONLINE_JUDGE 
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout); 
#endif 
}

const int MX=1e5+10;
int N,K; 
int t[MX];
int memo[MX];


int solve(int i){
	if(i==N-1) return 0;
	if(memo[i]!=-1)return memo[i];
	int ans=INF;
	for(int j=i+1; j<=min(N-1,i+K); j++) ans=min(ans,solve(j)+abs(t[i]-t[j]));
	return memo[i]=ans;
}

int32_t main(){
   boost;
   IO();

   memset(memo,-1,sizeof(memo));
   cin>>N>>K;
   for(int i=0; i<N;i++) cin>>t[i];

   cout << solve(0) << endl;
	


   return 0;
}



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

int main(){
    int x1,x2,x3,x4,x5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;
    if(x1==0){
        cout << 1 << endl;
    }
    else if(x2==0){
        cout << 2 << endl;
    }else if(x3==0){
        cout << 3 << endl;
    }else if(x4==0){
        cout << 4 << endl;
    }
    else{
        cout << 5 << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
// Choose Integers
#include <iostream>
using namespace std;
int a,b,c;
int main(){
    cin>>a>>b>>c;
    int x=a;
    while(true){
        if(x%b==c){
            cout<<"YES";
            return 0;
        }if(x%b==0){
            cout<<"NO";
            return 0;
        }
        x+=a;
    }
}

Measured memory_bytes: 256
//To compile : type "$     g++ test.cpp -std=c++14 -I .    "
#include <atcoder/lazysegtree>
#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
using namespace atcoder;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
//string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

struct S {
    ll num0, num1, inv_num;
    S(ll _0 = 0, ll _1 = 0, ll _inv = 0) : num0(_0), num1(_1), inv_num(_inv){}
};

using F = bool;

S op(S s, S t){
	return S(s.num0 + t.num0, s.num1 + t.num1, s.inv_num + t.inv_num + s.num1 * t.num0);
}

S e(){ return S(); }

S mapping(F f, S s){
	if(f) {
		ll a = s.num0, b = s.num1;
		return S(b, a, a * b - s.inv_num);
	}else{
		return s;
	}
}

F composition(F f, F g){
	return f ^ g;
}

F id(){ return false; }

int main() {
	cin>>N>>Q;
	vector<S> a(N);
	rep(i, N){
		scanf("%lld", &A);
		a[i] = S(A == 0, A == 1, 0);
	}
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
	rep(_, Q){
		int t, l, r;
		scanf("%d%d%d", &t, &l, &r);
		--l;
		if(t == 1){
			seg.apply(l, r, true);
		}else{
			printf("%lld\n", seg.prod(l, r).inv_num);
		}
	}
}

Measured memory_bytes: 20444
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long

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

	double a, b;
	cin >> a >> b;
	printf("%f\n", a / b);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	string N;
	cin>>N;
	ll ans=0;
	for(ll i=0;i<N.size();i++)
	{
		ans+=(N[i]-'0');
	}
	if(ans%9==0)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
}

Measured memory_bytes: 3752
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace abc168_d
{
  class Program
  {
    static void Main(string[] args)
    {
      var N = CIn.ReadInt();
      var M = CIn.ReadInt();
      var path = new List<int>[N];

      for (int i = 0; i < N; i++)
      {
        path[i] = new List<int>();
      }

      for (int i = 0; i < M; i++)
      {
        var A = CIn.ReadInt() - 1;
        var B = CIn.ReadInt() - 1;

        path[A].Add(B);
        path[B].Add(A);
      }

      var q = new Queue<int>();
      q.Enqueue(0);
      var ans = Enumerable.Repeat(-1, N).ToArray();
      ans[0] = 0;

      while (q.Count > 0)
      {
        var i = q.Dequeue();
        foreach (var e in path[i])
        {
          if (ans[e] == -1)
          {
            ans[e] = i;
            q.Enqueue(e);
          }
        }
      }

      var sb = new StringBuilder();
      sb.AppendLine("Yes");

      for (int i = 1; i < N; i++)
      {
        sb.AppendLine((ans[i] + 1).ToString());
      }

      Console.WriteLine(sb.ToString());
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}

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

long long h,w;

int main(){

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

    cin>>h>>w;
    if(w<h)swap(w,h);
    if(h!=1)cout<<(h/2)*(w/2)+((h+1)/2)*((w+1)/2)<<endl;
    else cout<<1<<endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static long A, B;
	static long[] a;

	static boolean p(long mid) {
		long extra = 0;
		for (int i = 0; i < N; i++) {
			long leftHealth = a[i] - (mid * B);
			if (leftHealth > 0)
				extra += leftHealth % (A - B) == 0 ? leftHealth / (A - B) : (leftHealth / (A - B)) + 1;
		}
		return extra <= mid;
	}

	static long BinarySearch() {
		long low = 0, high = (int) 1e9, ans = 0;
		while (low <= high) {
			long mid = low + ((high - low) >> 1);
			if (p(mid)) {
				high = mid - 1;
				ans = mid;
			} else
				low = mid + 1;
		}
		return ans;
	}

	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		N = sc.nextInt();
		A = sc.nextLong();
		B = sc.nextLong();
		a = new long[N];
		for (int i = 0; i < N; i++)
			a[i] = sc.nextLong();
		out.println(BinarySearch());
		out.flush();
		out.close();
	}

	static class MyScanner {
		StringTokenizer st;
		BufferedReader br;

		public MyScanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public MyScanner(String file) throws IOException {
			br = new BufferedReader(new FileReader(new File(file)));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}


Measured memory_bytes: 39220
h = int(input())
w = int(input())
n = int(input())

colored = 0
ans = 0

if h >= w:
  for i in range(w):
    colored += h
    if colored >= n:
      ans = i + 1
      break
else:
  for i in range(h):
    colored += w
    if colored >= n:
      ans = i + 1
      break

print(ans)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){

    int h,w;
    cin>>h>>w;
    char a[60][60];
    int b[60][60];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char x;
            cin>>x;
            if(i==0&&j==0);
            else if(i==0){
                b[i][j] = b[i][j-1] + x - '0';
            }
            else if(j==0){
                b[i][j] = b[i-1][j] + x - '0';
            }
            else {
                b[i][j] = min(b[i][j-1],b[i-1][j]) + x - '0';
            }
        }
    }
    cout<<b[h-1][w-1]<<endl;


    return 0;
}

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

long long n;
long long dp[100005] = {0};
long long c[] = {1,     6, 36, 216, 1296, 7776,
                 46656, 9, 81, 729, 6561, 59049};

long long solve();

int main() {
  cin >> n;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  dp[1] = 1;
  for(int i = 1; i < n; ++i) dp[i + 1] = 1000000000;
  for(int i = 1; i < n; ++i)
    for(int j = 0; j < 12; ++j)
      if(i + 1 >= c[j])
        dp[i + 1] = min(dp[i + 1], dp[i + 1 - c[j]] + 1);
  return dp[n];
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b << endl;
}

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

int main(){
    char s1[3],s2;
    int count=0;
    for(int i=0;i<3;i++){
        cin>>s1[i];
    }
    for(int i=0;i<3;i++){
        cin>>s2;
        if(s1[i]==s2)count++;
    }
    cout<<count;
}


Measured memory_bytes: 256
#import<iostream>
#import<vector>
#import<cstdlib>
using namespace std;main(){int n,m,k,x,d,h,i,j,D[158][151][10];for(;cin>>n>>m,n;cout<<x<<endl){vector<pair<int,int> >S[151];for(i=0;i++<n;)for(cin>>k;k--;S[i].push_back(make_pair(x,d)))cin>>x>>d;fill(**D,*D[158],x=1e9);for(i=S[1].size();i--;)D[m][1][i]=0;for(i=S[2].size();i--;)D[m-1][2][i]=0;for(h=1;h++<n;)for(i=m;~i;i--)for(j=S[h].size();j--;){for(k=S[h-1].size();k--;)D[i][h][j]=min(D[i][h][j],D[i][h-1][k]+(S[h][j].second+S[h-1][k].second)*abs(S[h][j].first-S[h-1][k].first));for(k=S[h-2].size();k--;)D[i][h][j]=min(D[i][h][j],D[i+1][h-2][k]+(S[h][j].second+S[h-2][k].second)*abs(S[h][j].first-S[h-2][k].first));}for(i=m;~i;i--)for(j=S[n].size();j--;)x=min(x,D[i][n][j]);for(i=m;i;i--)for(j=S[n-1].size();j--;)x=min(x,D[i][n-1][j]);}}

Measured memory_bytes: 1868
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <queue>
#include <stack>
#include <deque>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
#include <complex>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cstdlib>
#include <cctype>

#define REP(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rp(i,c) rep(i,(int)c.size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define mp make_pair
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(u) (u).rbegin(),(u).rend()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl
#define v_delete(a,b) (a).erase(remove((a).begin(), (a).end(), b), (a).end())
#define v_unique(a) (a).erase(unique((a).begin(), (a).end()), (a).end())
#define VV(T) vector<vector< T > >
#define init(a,b) memset((a), (b), sizeof((a)))
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e10,EPS=1e-9;


template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}

template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T> void input(T* a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
typedef pair<int,int> pii;

inline bool IN(int x, int y, int w, int h)
{
    return 0 <= x && x < w && 0 <= y && y < h;
}


int main()
{
	int n;
	while(cin >> n){
		int ans=0;
		rep(a,10){
			rep(b,10){
				rep(c,10){
					rep(d,10){
						(a+b+c+d==n)?ans++:ans;
					}
				}
			}
		}
		cout << ans << endl;
	}

}

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

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for (int i=a; i<b; i++)
#define M00(i, a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _<< " _ " <<

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ll a, v, b, w, t;
	cin >> a >> v >> b >> w >> t;
	if(v <= w) {
		cout << "NO" << endl;
		return 0;
	}
	ll speed = v - w;
	ll del = abs(a-b);
	if((del + speed - 1)/speed <= t) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main()
{
    int ans, start, end;
    string s;
    cin >> s;
    start = s.find('A');
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] == 'Z')
        {
            end = i;
            break;
        }
    }
    ans = 1 + end - start;

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

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB(x) push_back(x)
#define MP make_pair
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<'Y'<<'e'<<'s'<<endl
#define coutn cout<<'N'<<'o'<<endl
#define coutY cout<<'Y'<<'E'<<'S'<<endl
#define coutN cout<<'N'<<'O'<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;
//cout<<fixed<<setprecision(15)<<

signed main(){
    string s; cin >> s;
    int n=s.size();
    int res=(n)*(n-1)/2+1;
    map<char,int> map;
    rep(i,n) map[s[i]]++;
    for(char i='a'; i<='z'; i++){
        res-=map[i]*(map[i]-1)/2;
    }
    cout<<res<<endl;
    
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main()
{
  string S;
  cin >> S;
  long ans = 0;
  int cnt = 0;
  for (int i = 0; i < S.length(); i++)
  {
    if (S[i] == 'W')
    {
      ans += (long)(i - cnt);
      cnt++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        n: usize,
        s: [Chars; n],
    }
    let mut result = 0usize;
    let mut b = vec![vec![' '; n]; n];
    for a in 0..n {
        for i in 0..n {
            for j in 0..n {
                b[(i + a) % n][j] = s[i][j];
            }
        }
        if (0..n).all(|i| (0..i).all(|j| b[i][j] == b[j][i])) {
            result += n;
        }
    }
    println!("{}", result);
}


Measured memory_bytes: 3016
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
#define vv(a,b) vector< vector<int> > v(a,vector<int>(b,0));
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const int mod =1e9+7;

int main()
{
    int n;
    cin>>n;
    vector<P> m(n);
    vector<P> xl(n);
    rep(i,n)
    {
        cin>>xl[i].first>>xl[i].second;
    }
    rep(i,n)
    {
        
        m[i].first=xl[i].first+xl[i].second;
        m[i].second=xl[i].first-xl[i].second;
    }
    sort(m.begin(),m.end());
    ll prev=-1e9;
    int ans=0;
    rep(i,n)
    {
        if(m[i].second>=prev)
        {
            ans++;
            prev=m[i].first;
        }
    }
    cout<<ans;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  string s;
  ll k,nop;
  cin>>s>>k;
  for(nop=0;nop < s.size();nop++)
    if(s[nop]=='1')
      continue;
    else
      break;
  if(nop == s.size()){
    cout<<1<<endl;
    return 0;
  } // 全部1
  if(k <= nop) cout<<1<<endl;
  else cout<<s[nop]<<endl;
  return 0;
}

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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  each(x,vec) is >> x;
  return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  rep(i,vec.size()) {
    if (i) os << " ";
    os << vec[i];
  }
  return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
  rep(i,vec.size()) {
    if (i) os << endl;
    os << vec[i];
  }
  return os;
}

const ll m = 20;

vector<vector<ll>> f(const vector<ll>& dp0) {
  const ll n = dp0.size();
  vector<vector<ll>> dp(n, vector<ll>(m));
  rep(i, n) dp[i][0] = dp0[i];
  rep(i, 1, m) rep(v, n) {
    dp[v][i] = dp[dp[v][i-1]][i-1];
  }
  return dp;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  vector<ll> x(n); cin >> x;
  vector<ll> dpl0(n, 0), dpr0(n, 0);
  ll L; cin >> L;
  rep(i, n) {
    dpl0[i] = lower_bound(all(x), x[i]-L) - x.begin();
    dpr0[i] = upper_bound(all(x), x[i]+L) - x.begin() - 1;
  }
  vector<vector<ll>> dpl = f(dpl0);
  vector<vector<ll>> dpr = f(dpr0);
  ll Q; cin >> Q;
  rep(q, Q) {
    ll a, b; cin >> a >> b; --a, --b;
    ll ans = 0;
    if (a < b) {
      ll v = a;
      rrep(i, m) if (dpr[v][i] < b) {
        v = dpr[v][i];
        ans += 1LL<<i;
      }
      if (v != b) ++ans;
    }
    else {
      assert(a > b);
      ll v = a;
      rrep(i, m) if (dpl[v][i] > b) {
        v = dpl[v][i];
        ans += 1LL<<i;
      }
      if (v != b) ++ans;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 42240
n = gets.to_i
a = n.times.map{gets.split.map(&:to_i)}.sort_by{|i,j|i+j}
r = -10**9
ans = 0
n.times do |i|
    if a[i][0]-a[i][1] >= r
        ans += 1
        r = a[i][0]+a[i][1]
    end
end
puts ans

Measured memory_bytes: 12664
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

int main() {
 UL N; scanf("%u",&N);
 UL A[200001]; rep(i,N) scanf("%u",&A[i]); A[N]=~0u;
 UL M; scanf("%u",&M);
 UL B[200001]; rep(i,M) scanf("%u",&B[i]); B[M]=~0u;
 UL p=0,q=0;
 while(p+q<N+M){
  if(A[p]<B[q]){ printf("%u\n",A[p]); p++; }
  else if (A[p]>B[q]){ printf("%u\n",B[q]); q++; }
  else { p++; q++; }
 }
 return 0;
}



Measured memory_bytes: 4744
"use strict";
function lowerThanDateOnly(date1, date2) {
    let d1 = date1.split('/');
    let year1 = d1[0] - 0;
    let month1 = d1[1] - 0;
    let day1 = d1[2] - 0;

    let d2 = date2.split('/');
    let year2 = d2[0] - 0;
    let month2= d2[1] - 0;
    let day2 = d2[2] - 0;

    if (year1 == year2) {
        if (month1 == month2) {
            return day1 < day2;
        }
        else {
            return month1 < month2;
        }
    } else {
        return year1 < year2;
    }
}
function Main(input) {
    let lines = input.split("\n")[0];
    console.log(lowerThanDateOnly(lines, '2019/05/01') ? "Heisei" : "TBD");
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
import java.util.Scanner;

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

        long node = 0;

        while (h > 0) {
            h /= 2;
            node += 1;
        }
        sc.close();
        long ans = pow(2, node) - 1;
        System.out.println(ans);

    }

    public static long pow(long a, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return a;
        }
        if (n % 2 == 0) {
            return pow(a * a, n / 2);
        } else {
            return a * pow(a * a, (n - 1) / 2);
        }
    }
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
struct point{
    ll x, y;
};
typedef vector<point> vp;

/*------------------------------------------------------*/

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化

    int n, m;  cin >> n;
    map<string, int> mp;
    for(int i = 0; i < n; i++){
        string s;  cin >> s;
        auto itr = mp.find(s);
        if(itr != mp.end()) mp[s]++;
        else mp[s] = 1;
    }
    cin >> m;
    for(int i = 0; i < m; i++){
        string s; cin >> s;
        auto itr = mp.find(s);
        if(itr != mp.end()) mp[s]--;
        else continue;
    }
    int ans = 0;
    for(auto i : mp){
        ans = max(ans, i.second);
    }
    cout << ans << "\n";
}

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

typedef pair<int, int> P;

static const int MAX_H = 1000;
static const int MAX_W = 1000;

int H, W;
char grid[MAX_H][MAX_W + 1];
int count[MAX_H][MAX_W];

//#define OCTAS
#ifdef OCTAS
static const int dh[] = {-1, -1, -1, 0, 0, +1, +1, +1};
static const int dw[] = {-1, 0, +1, -1, +1, -1, 0, +1};
#else
static const int dh[] = {-1, 0, 0, +1};
static const int dw[] = {0, -1, +1, 0};
#endif

void initialize() {
  // memset(::count, -1, sizeof(::count));
  fill_n(::count[0], MAX_H * MAX_W, -1);
}

int bfs() {
  queue<P> que;

  for (int h{}; h < H; ++h) {
    for (int w{}; w < W; ++w) {
      if (grid[h][w] == '#') {
        ::count[h][w] = 0;
        que.push(P(h, w));
      }
    }
  }

  int cnt{};
  while (!que.empty()) {
    P p = que.front();
    que.pop();
    cnt = ::count[p.first][p.second];
    for (int i = 0; i < sizeof(dh) / sizeof(int); ++i) {
      int nh = p.first + dh[i];
      int nw = p.second + dw[i];
      if (nh < 0 || nh >= H ||
          nw < 0 || nw >= W ||
          ::count[nh][nw] >= 0 ||
          grid[nh][nw] == '#')
        continue;
      ::count[nh][nw] = cnt + 1;
      que.push(P(nh, nw));
    }
  }

  return cnt;
}

int main() {
  initialize();
  scanf("%d%d", &H, &W);
  for (int h = 0; h < H; ++h) {
    scanf("%s", &grid[h][0]);
  }

  printf("%d\n", bfs());
  return 0;
}


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

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

    vector<int> p(n);

    for (ll i = 0; i < n; i++){
        cin >> p[i];
    }

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

    int sum = 0;

    for (ll i = 0; i < m; i++){
        sum += p[i];
    }

    cout << sum << endl;
}

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

int main(){
    //input
    int n;
    cin >> n;
    int mi = 1000;
    int ma = 0;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        mi = min(a,mi);
        ma = max(a,ma);
    }

    cout << ma - mi << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
const int MOD = 1e9 + 7;
vector<long long> fact_inv, inv, Com;
void init_nCk(int n, int SIZE) {
    fact_inv.resize(SIZE + 5);  // 逆元の積
    inv.resize(SIZE + 5);       // 逆元
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; // 正で最小のものに揃えてる
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
    Com.resize(SIZE + 5);       // nCk を保存
    Com[0] = 1;
    for (int i = 1; i < SIZE + 5; i++) {
        Com[i] = Com[i - 1] * ((n - i + 1) * inv[i] % MOD) % MOD;
    }
}
long long nCk(int k) {
    assert(!(k < 0));       // kは非負でなくてはいけない
    return Com[k];
}
int main() {
    ll x, y;
    cin >> x >> y;
    ll ans = 0;
    if ((x + y)%3 == 0) {
        if (x - (x + y)/3 >= 0 && x - (x + y)/3 <= (x + y)/3) {
            init_nCk((x + y)/3, x - (x + y)/3);
            ans = nCk(x - (x + y)/3);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11088
import itertools
def ans(n, m, x, list_all):
    for i in range(m):
        sum_m=0
        for j in range(n):
            sum_m+=list_all[j][i+1]
        if x>sum_m:
            return -1
    price=pow(10,7)
    for i in itertools.product([0,1], repeat=n):
        list=[0]*(m+1)
        boo=True
        for j in range(n):
            if i[j]==1:
                for k in range(m+1):
                    list[k]+=list_all[j][k]
        for j in range(m):
            if list[j+1]<x:
                boo=False
        if boo:
            if price>list[0]:
                price=list[0]
    return price


n, m, x =(int(x) for x in input().split())
list_all=[]
for i in range(n):
    li_i=list(map(int, input().split()))
    list_all.append(li_i)
print(ans(n, m, x, list_all))


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

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

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

    constexpr int num = 55555;
    vector<bool> prime(num + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= num; i++) {
        if (!prime[i]) continue;
        for (int j = 2 * i; j <= num; j += i) prime[j] = false;
    }

    int n; cin >> n;
    for (int rest = 1; rest < 5; rest++) {
        vector<int> ans;
        for (int i = rest; i <= num; i += 5) {
            if (prime[i]) ans.push_back(i);
        }
        if (ans.size() < n) continue;
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " \n"[i==n-1];
        }
        break;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var firstLine = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var D = firstLine[0];
            var N = firstLine[1];
            var tmp = Math.Pow(100, D);
            if (N == 100)
            {
                N++;
            }
            Console.WriteLine(tmp * N);
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define YN {puts("YES");}else{puts("NO");}
const ll MAX = 1000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}
long long COM(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
ll llpow(ll n,ll i){ll cnt=n;  for(ll j=0;j<i-1;j++){n*=cnt;}return n;}

int main() {
  int n;
  cin>>n;
  vector<vector<int>> a(n,vector<int>(3));
  vector<vector<int>> dp(n+1,vector<int>(3));
  rep(i,n){
    rep(j,3) cin>>a[i][j];
  }
  rrep(i,n){
    rep(j,3){
      rep(k,3){
        if(j==k) continue;
        maxs(dp[i][k],dp[i-1][j]+a[i-1][k]);
      }
    }
  }
  int ans=0;
  rep(i,3){
    maxs(ans,dp[n][i]);
  }
  cout<<ans<<endl;
}    


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

signed main(void)
{
	char a;
	cin >> a;
	if (a >= 'A' && a <= 'Z')
		cout << 'A' << endl;
	else
		cout << 'a' << endl;
	return 0;
}


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

int main( )
{
    int n, m, i, j, k;
    cin >> n >> m;
    string A[55], B[55];
    for (i = 1; i <= n; i++) {
        cin >> A[i];
        A[i] = "#" + A[i];
    }
    for (i = 1; i <= m; i++) {
        cin >> B[i];
        B[i] = "#" + B[i];
    }
    for (i = 1; i + m - 1 <= n; i++) {
        for (j = 1; j + m - 1 <= n; j++) {
            int fl = 1;
            //cout << i << '-' << j << '\n';
            for (k = 1; k <= m; k++) {
                string s = "#" + A[i + k - 1].substr(j, m);
                //cout << s << ' ' << B[k] << '\n';
                if (s != B[k]) {
                    fl = 0;
                    break;
                }
            }
            if (fl) {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
  	struct drink {
  		long price;
  		int num;
	};
    vector<drink> AB(N);
  	int index=0;
  	while(cin >> AB[index].price >> AB[index].num) index++;
    sort(AB.begin(), AB.end(), 
     [](const drink& x, const drink& y) { return x.price < y.price;});
    //for(int i=0;i<N;i++) cerr << AB[i].price << ":" << AB[i].num << endl;
  	long total = 0;
  	long num = 0;
  	for(int i=0;i<N;i++)
    {
      if(AB[i].num + num <= M)
      {
        total += AB[i].price * AB[i].num;
        num += AB[i].num;
      }
      else
      {
        total += AB[i].price * (M - num);
        num+= M-num;
      }
      if(M==num) break;
    }
  	cout << total << endl;
  	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(void){
	int n,i,j,v;
	int a[100];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(j=0;j<n-1;j++){
			printf("%d ",a[j]);
	}
	printf("%d\n",a[n-1]);
	for(i=1;i<n;i++){
		v=a[i];
		j=i-1;
		while(j>=0 && a[j]>v){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=v;
		for(j=0;j<n-1;j++){
			printf("%d ",a[j]);
		}
		printf("%d\n",a[n-1]);
	}
	return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
int main()
{
	int j,i,a,b,c,d,s;
	s=0;
	while(~scanf("%d%d%d%d",&a,&b,&c,&d))
	{
		if(a>=d||b<=c)
			printf("%d",s);
	else
	{
		j=a;
		if (j<c)
		{
			j=c;
		}
		i=b;
		if (i>d)
		{
			i=d;
		}
		s=i-j;
		printf("%d\n",s);
	}
	}
	return 0;
 } 		

Measured memory_bytes: 128
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Math;

class program
{
    static public int mod = 1000000007;
    static void Main()
    {
        var n = rint();
        var a = inta();
        long ans = 0;
        int amx = a[0];
        for(int i = 1; i < n; i++)
        {
            if (amx > a[i])
                ans += amx - a[i];
            else
                amx = a[i];
        }
        Write(ans);
    }

    static int pow(int a, int b) { string binary = Convert.ToString(b, 2); int bileng = binary.Length; long a_power = a; long value = 1; for (int i = bileng - 1; i >= 0; i--) { if (binary[i] == '1') { value = value * a_power % mod; } a_power = a_power * a_power % mod; } return (int)value; }
    static string rstr() { return ReadLine(); }
    static int rint() { return int.Parse(ReadLine()); }
    static long rlong() { return long.Parse(ReadLine()); }
    static string[] stra() { return ReadLine().Split(' '); }
    static char[] chara() { string[] a = stra(); string b = ""; for (int i = 0; i < a.Length; i++) { b += a[i]; } return b.ToCharArray(); }
    static int[] inta() { string[] read_str_array = ReadLine().Split(' '); int[] return_int_array = new int[read_str_array.Length]; for (int countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_int_array[countup_i] = int.Parse(read_str_array[countup_i]); } return return_int_array; }
    static long[] longa() { string[] read_str_array = ReadLine().Split(' '); long[] return_long_array = new long[read_str_array.Length]; for (long countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_long_array[countup_i] = long.Parse(read_str_array[countup_i]); } return return_long_array; }
    static double[] doublea() { string[] read_str_array = ReadLine().Split(' '); double[] return_double_array = new double[read_str_array.Length]; for (long countup_i = 0; countup_i < read_str_array.Length; countup_i++) { return_double_array[countup_i] = double.Parse(read_str_array[countup_i]); } return return_double_array; }
    static long GCD(long a, long b) { if (a < b) { long temp = a; a = b; b = temp; } if (a % b == 0) { return b; } else { long temp = b; b = a % b; a = temp; return GCD(a, b); } }
    static long LCM(long a, long b) { return a * b / GCD(a, b); }
    static void WriteArray2(int[,] a, int b, int c) { for (int i = 0; i < b; i++) { for (int j = 0; j < c; j++) { if (j != 0) Write(" "); Write(a[i, j]); } WriteLine(); } }
    static void WriteArray(int[] a, int b) { for (int i = 0; i < b; i++) { Write(" "); Write(a[i]); } WriteLine(); }
}


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

int main(){
  string s;
  int k;
  cin >> s >> k;
  vector<int> v;
  bool f = false;
  int p = 0;
  int one = 0;
  rep(i,s.length()) {
    if(s[i] == '0') {
      f = true;
      v.push_back(p);
      p = 0;
    } else {
      one++;
      p++;
    }
  }
  if(p > 0) v.push_back(p);
  if(!f) {
    cout << 1 << endl;
    return 0;
  }
  int l = v.size();
  k = min(k,300);
  vector<vector<vector<ll>>> dp(l+1,vector<vector<ll>>(k+1,vector<ll>(k+1)));
  dp[0][0][0] = 1;
  reverse(v.begin(),v.end());
  rep(i,l) {
    rep(j,k+1) {
      rep(a,k+1) {
        rep(b,a+1) (dp[i+1][j][b] += dp[i][j][a]) %= mod; 
      }
    }
    rep(j,k+1) {
      rep(a,k+1) {
        for(int b = 1; b <= v[i]; b++) {
          if(a+b <= k and j+b <= k) (dp[i+1][j+b][a+b] += dp[i][j][a]) %= mod;
        }
      }
    }
  }
  ll ans = 0;
  rep(i,k+1) (ans += dp[l][i][0]) %= mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 112976
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<int, int> P;

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

mat G(100, vec(0));
vector<bool> used(100, false);
vector<int> rank_dim(100, 0);
void dfs(int v, int &k){
    used[v] = true;
    int dim = 0;
    for(ll to : G[v]){
        if(!used[to]){
            ++dim;
            ++k;
            dfs(to, k);
            --k;
        }
    }
    //cout<<v + 1<<' '<<dim<<endl;
    chmax(rank_dim[k], dim);
}

int main() {
    cin>>N;
    mat dist(N, vec(N, 200));
    rep(i, N - 1){
        cin>>A>>B;
        --A;
        --B;
        G[A].push_back(B);
        G[B].push_back(A);
        dist[A][B] = dist[B][A] = 1;
    }
    rep(i,N) dist[i][i] = 0;
    rep(k,N)rep(i,N)rep(j,N) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    ll diam = 0;
    int l, r;
    rep(i,N) rep(j,N) {
        if(chmax(diam, dist[i][j])) {
            l = i;
            r = j;
        }
    }
    //cout<<diam<<' '<<l<<' '<<r<<endl;
    if((diam&1) == 0){
        int p, k = 0;
        rep(i,N) if(dist[l][i] == diam/2 && dist[r][i] == diam/2) p = i;
        dfs(p, k);
        ll ans = 1;
        rep(i, diam / 2) ans *= rank_dim[i];
        for(int to : G[p]){
            rep(i,100) {
                used[i] = false;
                rank_dim[i] = 0;
            }
            used[p] = used[to] = true;
            dfs(p, k);
            dfs(to, k);
            ll temp = 2;
            rep(i, diam / 2) temp *= rank_dim[i];
            chmin(ans, temp);
        }
        cout<<diam / 2 + 1<<' '<<ans<<endl;
    }else{
        int p, q, k = 0;
        rep(i,N) if(dist[l][i] == diam / 2 && dist[r][i] == (diam + 1) / 2) p = i;
        rep(i,N) if(dist[l][i] == (diam + 1) / 2 && dist[r][i] == diam / 2) q = i;
        //cout<<p<<' '<<q<<endl;
        used[p] = used[q] = true;
        dfs(p, k);
        dfs(q, k);
        ll ans = 2;
        rep(i, diam / 2) ans *= rank_dim[i];
        cout<<(diam + 1) / 2<<' '<<ans<<endl;
    }
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

bool solve(vvi& field,int x,int y,int xg,int yg,int c)
{
	if(field[y][x]==0)
		return false;
	if(field[y][x]!=c)
		return false;
	if(x==xg && y==yg)
		return true;
	field[y][x]=-1;
	bool res=0;
	res|=solve(field,x-1,y,xg,yg,c);
	res|=solve(field,x+1,y,xg,yg,c);
	res|=solve(field,x,y-1,xg,yg,c);
	res|=solve(field,x,y+1,xg,yg,c);
	return res;
}

int main()
{
	for(int w,h;cin>>w>>h,w|h;){
		int xs,ys,xg,yg,n; cin>>xs>>ys>>xg>>yg>>n;
		vvi field(110,vi(110));
		rep(k,n){
			int c,d,x,y; cin>>c>>d>>x>>y;
			if(d)
				rep(i,4) rep(j,2)
					field[y+i][x+j]=c;
			else
				rep(i,2) rep(j,4)
					field[y+i][x+j]=c;
		}
		cout<<(solve(field,xs,ys,xg,yg,field[ys][xs])?"OK":"NG")<<endl;
	}
	
	return 0;
}

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

int main() {
    int i, j, k;
    int n, d;
    cin >> n >> d;
    int x[n][d];
    for (i = 0; i < n; i++) {
        for (j = 0; j < d; j++) {
            cin >> x[i][j];
        }
    }

    int count = 0;
    for (i = 0; i < n; i++) {
         for (j = i+1; j < n; j++) {
            double sum = 0;
            double dist; 
            for (k = 0; k < d; k++) {
                sum += (x[i][k] - x[j][k])*(x[i][k] - x[j][k]);
            }
            dist = sqrtl(sum);
            if (dist - ceil(dist) == 0) {
//                printf("%f\n", dist);
                count++;
            }
        }
    }

    cout << count << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
using namespace std;
typedef pair<int, int> pii;
#define MAX 99999999
int main(){
    vl v(5,0);rep(i,5)cin>>v[i];
    sort(v.begin(),v.begin()+3);
    cout<<v[0]+min(v[3],v[4])-50<<endl;
}

Measured memory_bytes: 3120
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int INT_INF = 500000000;
const long long LONG_LONG_INF = (long long)pow(10, 18);
const int MOD = pow(10, 9) + 7;
/* contest template */
long long A, B, C, K;

int main() {
  cin >> A >> B >> C >> K;
  if (A > B && A > C) {
    cout << A * pow(2, K) + B + C << endl;
  } else if (B > C && B > A) {
    cout << A + B * pow(2, K) + C << endl;
  } else {
    cout << A + B + C * pow(2, K) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){

int W,H,x,y,r;
cin>>W>>H>>x>>y>>r;

if((x+r<=W)&&(x-r>=0)&&(y+r<=H)&&(y-r>=0)) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}


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

int main() {
  int m, n; cin >> m >> n;
  vector<vector<int>> g(m);
  vector<int> cnt(m, 0);
  while (n--) {
    int x, y; cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    ++cnt[y];
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < m; ++j) {
      if (cnt[j] == 0) {
        cout << j + 1 << endl;
        cnt[j] = -1;
        for (auto&& x : g[j]) {
          if (cnt[x] == -1) continue;
          cnt[x] = max(0, cnt[x] - 1);
        }
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3164
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<deque>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int sum[100010];
bool ok[100010];
bool isp[100010];

void func()
{
	isp[0] = isp[1] = true;
	for(int i = 2;i < 10000;i++)
	{
		if(!isp[i])
		{
			for(int j = 2*i;j < 100010;j += i)isp[j] = true;
		}
	}
	
	for(int i = 1;i < 100010;i++)
	{
		if(!isp[i] && !isp[(i+1)/2])ok[i] = true;
	}
	
	for(int i = 1;i < 100010;i++)
	{
		sum[i] = sum[i-1];
		if(ok[i])sum[i]++;
	}
	
}

int main()
{
	func();
	
	int q;cin >> q;
	
	REP(i,q)
	{
		int a,b;cin >> a >> b;
		cout << sum[b] - sum[a-1] << endl;
	}
	
	return 0;
}

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

int main(void) {
	long long A, B, K;
	scanf("%lld %lld %lld", &A, &B, &K);
	if (A >= K) {
		A -= K;
		K = 0;
	} else {
		K -= A;
		A = 0;
	}

	if (B >= K) {
		B -= K;
		K = 0;
	} else {
		K -= B;
		B = 0;
	}

	printf("%lld %lld", A, B);

	return 0;
}


Measured memory_bytes: 3828