akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,sse4")
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define is insert
#define er erase

using namespace std;

const int MAX_N = 2e5 + 5;

const ll INF = 1e18;

int solve();

#define TASK ""

int main()
{
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        //freopen(TASK".in", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    #endif // DEBUG
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

int n;

int a[MAX_N];

ll dp1[MAX_N][16];
ll dp2[MAX_N][16];

ll mult[16];

ll ans;

double al[MAX_N];

int solve()
{
    mult[0] = 1;
    for (int i = 1; i < 16; ++i)
    {
        mult[i] = mult[i - 1] * 4;
    }
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        al[i] = log2(a[i]);
    }
    for (int i = 0; i < 16; ++i)
    {
        dp2[n + 1][i] = 0;
        dp2[n][i] = 2 * i;
    }
    for (int i = n - 1; i >= 1; --i)
    {
        for (int k = 0; k < 16; ++k)
        {
            dp2[i][k] = INF;
            bool t = false;
            for (int j = 0; j < 16; ++j)
            {
                if (a[i] * mult[k] <= a[i + 1] * mult[j])
                {
                    dp2[i][k] = min(dp2[i][k], dp2[i + 1][j] + 2 * k);
                    t = true;
                }
            }
            if (!t)
            {
                int x = ceil(k - 15.0 + al[i] / 2.0 - al[i + 1] / 2.0);
                dp2[i][k] = min(dp2[i][k], dp2[i + 1][15] + 2 * (n - i) * x + 2 * k);
            }
        }
    }
    ll cur = 0;
    ans = dp2[1][0];
    for (int i = 1; i <= n; ++i)
    {
        cur++;
        a[i] *= -2;
        al[i] = log2(-a[i]);
        if (i == 1)
        {
            for (int k = 0; k < 16; ++k)
            {
                dp1[1][k] = 2 * k;
            }
        }
        else
        {
            for (int k = 0; k < 16; ++k)
            {
                dp1[i][k] = INF;
                bool t = false;
                for (int j = 0; j < 16; ++j)
                {
                    if (a[i - 1] * mult[j] <= a[i] * mult[k])
                    {
                        dp1[i][k] = min(dp1[i][k], dp1[i - 1][j] + 2 * k);
                        t = true;
                    }
                }
                if (!t)
                {
                    int x = ceil(k - 15.0 + al[i] / 2.0 - al[i - 1] / 2.0);
                    dp1[i][k] = min(dp1[i][k], dp1[i - 1][15] + 2 * (i - 1) * x + 2 * k);
                }
            }
        }
        ans = min(ans, cur + dp1[i][0] + dp2[i + 1][0]);
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 52608
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
long long int inf = 1e18;

int main() {
  string s; cin >> s;
  int n = s.size();

  int ans = 0;
  for(int i=0; i<n; i++){
    if( i*2 == n ) continue;
    string t = s.substr(0, i) + s.substr(0, i);
    string tt = s.substr(0, 2*i);
    if( t == tt ) ans = max(ans, i);
  }
  cout << ans*2 << endl;

  return 0;
}




//


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

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

using namespace std;

typedef long long ll;

int f(int t, int n, vector<int> a) {
  int score = 0;
  rep(i, n) {
    score += (a[i]-t)*(a[i]-t);
  }
  return score;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;

  int n; cin >> n;
  int sum = 0;
  vector<int> a(n);

  rep(i, n) {
    cin >> a[i];
    sum += a[i];
  }
  
  if ( f((sum+n-1)/n, n, a) < f(sum/n, n, a) ) {
    cout << f((sum+n-1)/n, n, a) << endl;
  } else {
    cout << f(sum/n, n, a) << endl;
  }

  return 0;
}

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

int main(){
	long long N,th = 0,pattern = 0,count = 0,a = 0;
  cin >> N;
  vector<long long> num(N);
  vector<long> check;
  map<long long, long long> check2;;
  for(int i = 0;i < N;i++){
    cin >> num.at(i);
    if(!check2.count(num.at(i))){
      check.push_back(num.at(i));
      check2[num.at(i)] = 1;
      count++;
    }else{
      check2[num.at(i)]++;
  }
  }
    for(int i = 0;i < count;i++){
      pattern += check2.at(check.at(i)) * (check2.at(check.at(i)) - 1)/2;
  }
  vector<int> a1(count),a2(count);
  for(int i = 0;i < N;i++){
    if(check2.at(num.at(i)) - 2 <= 0){
      cout << pattern - check2.at(num.at(i))*(check2.at(num.at(i)) - 1) / 2 + (check2.at(num.at(i)) - 1)*0/ 2 << endl;
    }else{
  	cout << pattern - check2.at(num.at(i))*(check2.at(num.at(i)) - 1) / 2 + (check2.at(num.at(i)) - 1)*(check2.at(num.at(i)) - 2) / 2 << endl;
    }
    }
return 0;
}

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

int main(){
  string data;
  cin>>data;
  
  int a=0,b=0;
  for(int i=1;i<=data.size();i++){
    if(a==0 and data[i-1]=='A'){
      a=i;
    }
    if(data[i-1]=='Z'){
      b=i;
    }
  }
  cout<<b-a+1;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */


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

	string s; cin >> s;
	LL ans = 0LL;
	for (auto c : s) {
		ans += c == '1';
	}
	
	
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
n=int(input())
li=list(map(int,input().split()))
#print(li)
cut=0
for i in range(1,n-1):
    if li[i-1]+li[i]+li[i+1]-max(li[i-1],li[i],li[i+1])-min(li[i-1],li[i],li[i+1])==li[i]:
        cut+=1
print(cut)

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

int main()
{
    int n, i;
    cin>>n;
    double arr[n];
    double sum=0;

    for(i=0; i<n; i++)
    {
        cin>>arr[i];
        sum = sum + double(1/arr[i]);

    }
    printf("%0.9lf", 1/sum);


}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;

public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        String[] t = br.readLine().split(" ");
        int ope1, ope2;
        for(int i = 0; i < t.length; i++){
            //if( t[i].equals("+") || t[i].equals("-") || t[i].equals("*") ){          
            //int ope1 = stack.pop();                                                  
            //int ope2 = stack.pop();                                                  
            if(t[i].equals("+") ){
                ope1 = stack.pop();
                ope2 = stack.pop();
                stack.push(ope1 + ope2);
            }else if(t[i].equals("-") ){
                ope1 = stack.pop();
                ope2 = stack.pop();
                stack.push(ope2 - ope1);
            }else if(t[i].equals("*") ){
                ope1 = stack.pop();
                ope2 = stack.pop();
                stack.push(ope1 * ope2);
            }else{
                //int ope = Integer.parseInt(t[i]);                                    
                stack.push(Integer.parseInt(t[i]));
            }
        }
        //int ans = stack.pop();                                                       
        System.out.println(stack.pop());
    }

}

Measured memory_bytes: 24232
from collections import deque

mod = 10 ** 9 + 7

n, k = map(int, input().split())
es = tuple(set() for _ in range(n))
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].add(b)
    es[b].add(a)

ans = k

q = deque()

can_use = k - 1
# vに隣接する未着色の頂点を塗るのに使える色の数
# k色 - (親、自分)
for u in es[0]:
    ans = (ans * can_use) % mod
    can_use -= 1
    q.append((u, 0))

while q:
    v, pr = q.popleft()
    can_use = k - 2
    # vに隣接する未着色の頂点を塗るのに使える色の数
    # k色 - (親、自分)
    for u in es[v]:
        if u == pr:
            continue
        ans = (ans * can_use) % mod
        can_use -= 1
        q.append((u, v))

print(ans)


Measured memory_bytes: 78624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
const long long INF = 1LL << 60;
int main() 
{
    int n;
    cin >> n;
    long long a[n+10],b[100100],mini,rep=1;

    rep(i,100100){
        b[i]=0;
    }

    rep(i,n){
        cin >> a[i];
        b[a[i]]++;
    }

    rep(i,100000){
            mini = b[i]+b[i+1]+b[i+2];
            rep = max(rep,mini);
    }

    cout << rep << endl;


}

Measured memory_bytes: 1792
import sys
input = sys.stdin.readline
from itertools import accumulate


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, MOD=10**9+7):
    S = list(accumulate(A[::-1]))[::-1]
    ans = 0
    for i in range(N-1):
        ans += A[i] * S[i+1]
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


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

int main(){
	int N,M;
	bool check[200001]={false};
	cin >> N >> M;
	//島1<->島N　の船があるかどうか調べる。
	
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a >> b;
		if(a==1){
			if(check[b]==true){
				cout << "POSSIBLE" << endl;
				return 0;
			}else{
				check[b] = true;
			}
		}else if(b==N){
			if(check[a]==true){
				cout << "POSSIBLE" << endl;
				return 0;
			}else{
				check[a] = true;
			}
		}
	}
	cout << "IMPOSSIBLE" << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int64_t Gcd(int64_t n, int64_t m){
    if(n%m==0) return m;
    return Gcd(m,n%m);
}

int main(){
    int64_t N,K; cin>>N>>K;
    vector<int64_t> A;
    rep(n,0,N) {
        int64_t a; cin>>a;
        A.emplace_back(a);
    }
    
    int64_t gcd=A.front(), maxA=A.front();
    rep(i,1,N){
        maxA=max(maxA,A.at(i));
        gcd=Gcd(gcd,A.at(i));
    }

    string ans="IMPOSSIBLE";
    if(K<=maxA && K%gcd==0) ans="POSSIBLE";
    cout<<ans<<endl;
}

Measured memory_bytes: 1400
function Main(input) {
  var input = input.split(" ");
  var a = input[0];
  var b = input[1];
  var c = a * b;
  if (c % 2 == 0) {
    console.log('Even');
  } else {
    console.log('Odd');
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <tuple>
#include <regex>
#include <map>

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

#define EPS (1e-7) 

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

	// 駒をおくかずが増えるとさぼれる空間が増える。
	// 座標間の距離を求めておき、最大箇所をさぼるのが良い。

	sort(begin(X), end(X));

	vector<int> kyori(M -1);
	for (size_t i = 0; i < M - 1; i++) {
		kyori[i] = X[i + 1] - X[i]; // 正の数になるはずだ。
	}

	sort(begin(kyori), end(kyori));

	N = (N > M) ? M : N; // 多すぎれば減らす

	while (N > 1) {
		kyori.pop_back(); // さぼる
		N--;
	}

	int sum = 0;
	if (kyori.size() > 0) {
		sum = accumulate(begin(kyori), end(kyori), 0);
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
 
int main() {
    string line;
    cin>>line;
    int sum=0;
    for (int i=0; i<line.length()-1; i++){
    	if (line[i]!=line[i+1])	{
    		sum++;
    	}	
    }
    cout << sum <<  endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define LFOR(i, a, b) for (long long int i = (a); i <= (b); i++)
#define LRFOR(i, a, b) for (long long int i = (a); i >= (b); i--)
#define MOD 1000000007
#define INF 1000000000           // 2000000000
#define LINF 1000000000000000000 // 9000000000000000000
#define DINF 1000000000000000.0
#define PI 3.14159265358979

//.size()はunsigned int　0-1をするとオーバーフローする

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

int dy[5] = {-1, 0, 1, 0, 0};
int dx[5] = {0, -1, 0, 1, 0};

int main(void) {
    long long int n,m;
    long long int wa=0;
    long long int ac=0;

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

    FOR(i,1,m){
        cin>>p>>s;
        if(s=="AC"){
            if(dp[p]>=0){
                dp[p]=-dp[p]-1;
            }
        }else{
            if(dp[p]>=0){
                dp[p]++;
            }
        }
    }
    FOR(i,1,n){
       if(dp[i]<0) {
           ac++;
           wa+=(-dp[i]-1);
       }
    }
    cout<<ac<<" "<<wa<<endl;

}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <iterator>
#include <set>
#include <queue>

using namespace std;

bool isPrime(long N) {
    if (N <= 1) {
        return false;
    }

    for (long i = 2; i * i <= N; ++i) {
        if (N % i == 0) {
            return false;
        }
    }
    return true;
}

// vector<int> s = cumulativeSum(vs,N);
// [left, right) => s[right] - s[left]
vector<int> cumulativeSum(vector<int> vs, int N) {
    vector<int> rs(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        rs[i + 1] = rs[i] + vs[i];
    }
    return rs;
}

int main() {


    int Q;
    cin >> Q;

    vector<int> V;
    int m = 100000;
    for (int i = 0; i <= m; ++i) {
        if (i % 2 == 0) {
            V.push_back(0);
            continue;
        }
        if (isPrime(i) && isPrime((i + 1) / 2)) {
            V.push_back(1);
        } else {
            V.push_back(0);
        }
    }

    vector<int> ys = cumulativeSum(V,m);

    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;

        // [l,r] = [l,r+1)

        cout << ys[r + 1] - ys[l] << endl;

    }


    return 0;
}

Measured memory_bytes: 4584
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll s,w;
        cin>>s>>w;
        if(w>=s)
        {
            cout<<"unsafe"<<endl;
        }
        else
        {
            cout<<"safe"<<endl;
        }
    }
    return 0;
}

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

int n,W;
int v[100],w[100];
int dp[101][10001];

int func(int i,int j){
    if(dp[i][j]>=0)return dp[i][j];
    int res;
    if(i==n){
        res=0;
    }
    else if (j<w[i]){
        res=func(i+1, j);
    }
    else{
        res=max(func(i+1, j-w[i])+v[i], max(func(i+1, j), func(i, j-w[i])+v[i]));
    }
    return dp[i][j]=res;
}

int main(){
    cin>>n>>W;
    for (int i=0; i<n; i++) {
        cin>>v[i]>>w[i];
    }
    for (int i=0; i<101; i++) {
        for (int j=0; j<10001; j++) {
            dp[i][j]=-1;
        }
    }
    cout<<func(0,W)<<endl;
    return 0;
}

Measured memory_bytes: 7500
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int a,b,c;
    cin>>a>>b;
    if(b<10) c=a*10+b;
    else if(b<100) c=a*100+b;
    else c=a*1000+b;
    if(int(sqrt(c))*int(sqrt(c))==c) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i < (n); i++)

int main(){
    int a, b;
    cin >> a >> b;
    int ans= 10000;
    bool ok = false;
    int c, d, i;
    for(i=10; i<1010; i++){
        c = 0.08 * i;
        d = 0.1 * i;
        if(c == a && d == b){
            ans = min(ans, i);
            ok = true;
        }
    }
    if(ok){
        cout << ans <<endl;
    } else {
        cout << "-1" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int a,b,c;
signed main(){
	cin>>a>>b>>c;
	cout<<max(0ll,c-(a-b))<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int main()
{
    ll a,b,c;
    cin>>a>>b>>c;
    if(a <= b * c){
        printf("Yes");
    } 
    else{
        printf("No");
    }
    return 0;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using vl = vector<long long>;
using P = pair<long long,long long>;
const ll mod = 1000000007;
ll ruijo(ll x, ll n){
	if(n == 0)return 1;
    if(n%2 == 0)return ruijo(x*x%mod ,n/2)%mod;
	return x * ruijo(x*x%mod ,n/2)%mod;
}

int main(){
    ll n,k; cin >> n >> k;
    ll M=0,m=0;
    rep(i,k){
        m += i;
        M += n-i;
    }
    ll ans = M - m + 1;
    for(ll i =k;i<n+1;i++){
        m += i;
        M += n-i;
        ans += M - m + 1;  
    }
    cout << ans%mod << endl;
}



Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i,m,n) for(int i = m - 1; i >= n; i--)
#define ALL(v) v.begin(), v.end()
#define itn int
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
#define println(x) cout << x << endl
#define print(x) cout << x << " "
template<typename T, typename U>
inline bool CMAX(T &m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool CMIN(T &m, U x) { if (m > x) { m = x; return true; } return false; }

typedef long long lint;
typedef long double ldouble;
const int INF = 1e9;
const lint LINF = 1e18;
const int MOD = 1e9+7;
int main(){
    int n;
    lint d;
    cin >> n >> d;
    int cnt = 0;
    REP(i,n){
        lint p,q;
        cin >> p >> q;
        if(sqrt((p*p) + (q * q)) <= d)
            cnt++;
    }
    println(cnt);
    return 0;
}

Measured memory_bytes: 3672
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
typedef long double ld;

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

int main() {
    ll D,N;
    cin >> D >> N;

    ll zero=1;
    rep(i,D){
        zero *= 100;
    }

    ll ans = zero*N;

    if(D == 0){
        if(N == 100){
            cout << 101 << endl;
        }else{
            cout << N << endl;
        }
    }else{
        if(D == 1 && N == 100){
            cout << 10100 << endl;
        }else if(D == 2 && N == 100){
            cout << 1010000 << endl;
        }else{
            cout << ans << endl;
        }
        
    }
}


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素


int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> a(n),b(n);
    bool ac[n]={};
    rep(i,n) cin>>a[i].first>>a[i].second;
    rep(i,n) cin>>b[i].first>>b[i].second;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int j=0;
    int ans=0;
    rep(i,n){
        pair<int,int> sel_b=b[i];
        int max_y=-1;
        int sel_a;
        rep(j,n){
            if(ac[j])continue;
            if(a[j].first<sel_b.first && a[j].second<sel_b.second){
                if(a[j].second>max_y){
                    max_y=a[j].second;
                    sel_a=j;
                }
            }
        }
        if(max_y>-1){
            ans++;
            ac[sel_a]=true;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int s = 0, n, t;
  cin >> n;
  t = n;
  while(t) {
    s += t % 10;
    t /= 10;
  }
  if(n % s)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

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

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

typedef long long ll;

ll INF = 100000000000000;
ll MOD = 1e9+7;

int main(){
   int N,K;cin >> N >> K;
   vector<int> H(N);
   for(int i = 0;i < N;i++){
       cin >> H[i];
   }
   //cout << "00" << ' ';
   ll dp[100010];
   for(int i = 1;i < N;i++){
       ll cost = INF;
       for(int j = i-1;j >= max(i - K,0);j--){
           cost = min(cost,dp[j+1] + abs(H[i] - H[j]));
       }
       dp[i+1] = cost;
       //cout << dp[i+1] << ' ';
   }
   //cout << endl;
   cout << dp[N] << endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }


int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >>x2 >> y2;

    int dx = x2-x1;
    int dy = y2-y1;

    cout << x2-dy << " " <<  y2+dx << " " << x1-dy << " " <<y1+dx << endl; 
}



Measured memory_bytes: 3540
N, M = map(int, input().split())
connected = [list(map(int,input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(1<<N):
    for j,lst in enumerate(connected):
        count = 0
        for s in lst[1:]:
            if (i>>(s-1)) & 1:
                count += 1
        if count % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)


Measured memory_bytes: 68088
while True:
    n,x = map(int, raw_input().split())
    if n == 0 and x == 0: break
    c = 0
    for i in range(1, min(n-1,x/3)):
        for j in range(i+1, min(n,x/2)):
            for k in range(j+1, n+1):
                ijk = i + j + k
                if ijk == x:
                    c += 1
                    break
                elif ijk > x: break
    print c    

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

int main() {
    ll A1, A2, A3; cin >> A1 >> A2 >> A3;
    if (A1 +  A2 + A3 > 21){
        cout << "bust" << endl;
    }
    else {
        cout << "win" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
const double PI = acos(-1);
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
namespace std{
    bool operator < (const P& a, const P& b){
        return !EQ(a.X,b.X) ? a.X<b.X : a.Y+EPS<b.Y;
    }
    bool operator == (const P& a, const P& b){
        return abs(a-b) < EPS;
    }
}

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //ccw
    if(cross(b,c) < -EPS) return -1; //cw
    if(dot(b,c) < -EPS) return +2; //c-a-b
    if(abs(c)-abs(b) > EPS) return -2; //a-b-c
    return 0; //a-c-b
}
P rotate(const P &p, double rad){
    return p *P(cos(rad), sin(rad));
}

int main(){
    while(1){
        int n;
        cin >> n;
        if(n==0) break;

        if(n==1){
            double d;
            cin >> d >> d >> d >> d;
            cout << 0 << endl;
            continue;
        }

        //重心を原点に平行移動
        vector<VP> p(2, VP(n));
        for(int d=0; d<2; d++){
            P centroid(0, 0);
            for(int i=0; i<n; i++){
                double x,y;
                cin >> x >> y;
                p[d][i] = P(x, y);
                centroid += p[d][i];
            }
            centroid /= n;
            //p0が重心に重なると角度が取れなくなるので例外処理
            if(p[d][0] == centroid){
                swap(p[d][0], p[d][1]);
            }
            for(int i=0; i<n; i++){
                p[d][i] -= centroid;
            }
        }

        //同じ点が2点以上ないという仮定で、全部このsetに入って入ればokとする
        set<P> pset;
        for(int i=0; i<n; i++){
            pset.insert(p[0][i]);
        }
        double ans = INF;
        for(int i=0; i<n; i++){
            //p[1][i]を回転させてp[0][0]に合わせる
            if(!EQ(abs(p[0][0]), abs(p[1][i]))) continue;
            double angle = arg(p[1][i]/p[0][0]);
            bool ok = true;
            for(int j=0; j<n; j++){
                P rot = rotate(p[1][j], -angle);
                if(pset.find(rot) == pset.end()){
                    ok = false;
                    break;
                }
            }
            if(ok){
                ans = min(ans, abs(angle));
            }
        }
        cout << fixed << setprecision(10);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3756
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#define maxn 100005
#define mod 998244353
using namespace std;
typedef long long LL;
int main()
{
    int n;
    scanf("%d",&n);
    int t=n-n/500*500;
    printf("%d",n/500*1000+t/5*5);
    return 0;
}


Measured memory_bytes: 760
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define MEM(x) memset(x,0,sizeof(x))
#define vc vector<int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 0x3f3f3f3f
#define t_case int tt; cin>>tt; while (tt--)
#define lnginf 9223372036854775807
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define For(i,j,k) for (int i=(int)(j);i<(int)(k);i++)
#define ins insert
#define in(x); { for (auto &i : x) cin >> i; }
#define out(x); { for (auto i : x) cout<<i<<' ' ; }
#define PI 3.14159265359
const long long LL_INF = (long long) 2e18 + 5;
using namespace std;
const int N = 1e5 + 1;
void solve() {
	string a, b; cin >> a >> b;
	int ans = 0;
	For(i, 0, a.size()) {
		if (a[i] != b[i])ans++;
	}
	cout << ans << '\n';

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


	fastio   solve();


}

Measured memory_bytes: 3796
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long int ll;
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define  ff          first
#define  ss          second
#define  pb          push_back
#define  IOS         ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  lb          lower_bound
#define  ub          upper_bound
#define  D2(x)       { cerr << "[" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n"; }
#define  all(x)      (x).begin(), (x).end()
#define  mem(a)      memset(a , 0 ,sizeof a)
#define  deb(x)      cout << #x << " - " << x << "\n";
#define  ps(x,y)     fixed<<setprecision(y)<<x
#define  setbit(x)   __builtin_popcount(x)
#define  deb2(x,y)   cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n"
#define  rep(i,a,b)  for(int i=a ; i<b ; ++i)
#define  repr(i,a,b)  for(int i=a ; i>=b ; --i)
 
#define PI 3.141592653589793
const ll p = 5;
const ll INF = 1000000000;
const ll MAX_N = 2e5 + 2;

int v[21][21] = {0}, vis[21][21] = {0}, dist[21][21] = {0}, dirsX[4] = {1,-1,0,0}, dirsY[4] = {0,0,1,-1}, r , c;
queue<pair<int,int>>q;

int solve(int sx,int sy){
    pair<int,int> pr;
    
    // Clearing stuff
    while(!q.empty()) q.pop();
    rep(i,0,r){
        rep(j,0,c) dist[i][j] = vis[i][j] = 0;
    }
    
    // Finding out paths
    q.push({sx,sy}), dist[sx][sy] = 0, vis[sx][sy] = 1;
    
    while(!q.empty()){
        pr = q.front();
        q.pop();
        
        rep(i,0,4){
            int x = dirsX[i] + pr.ff, y = dirsY[i] + pr.ss;
            
            if(x>=r || y>=c || x<0 || y<0 || (vis[x][y]==1) || (v[x][y]==0)) continue;
            
            dist[x][y] = dist[pr.ff][pr.ss] + 1;
            vis[x][y] = 1;
            q.push({x,y});
        }
        
    }
    
    int temp = 0;
    rep(i,0,r){
        rep(j,0,c) temp = max(temp , dist[i][j]);
    }
    return temp;
}

int main() {
    IOS;
    cin >> r >> c;
    string s;
    rep(i,0,r){
        cin >> s;
        rep(j,0,c) v[i][j] = (s[j] == '.');
    }
    
    int ans = 1;
    rep(i,0,r){
        rep(j,0,c){
            if(v[i][j] == 0) continue;
            ans = max(ans, solve(i,j));
        }
    }
    cout << ans;
}

Measured memory_bytes: 3656
import itertools
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
a = list(itertools.permutations(list(range(1,n+1))))
pp,qq = 0,0
for i,j in enumerate(a):
  if p == j:
    pp = i
  if q == j:
    qq = i
print(abs(pp-qq))

Measured memory_bytes: 13804
N,L = [int(x) for x in input().split()]
min_taste=float('inf')
x = 0
for i in range(N):
    if(min_taste>abs(L+i)):
        min_taste = abs(L+i)
        x = i
print((N+1)*N//2+(L-1)*N-(L+x))
    

Measured memory_bytes: 2940
#include<iostream>
#include<cmath>
#include<string>
#include<deque>
#include<algorithm>
#include<vector>
using namespace std;

int N;
int a[100000+5];
 
int main()
{ 
	cin>>N;
	
	int count=1;
	
	for(int j=1;j<=N;j++)
	{
	    int num;
	    cin>>num;
		a[num]=count; 
		count++;
	} 
	  
	for(int n=1;n<=N;n++)
		cout<<a[n]<<" "; 
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

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

    vector<vector<bool>> G(N, vector<bool> (N, true));
    for (int i = 0; i < N; i++) {
        G[i][i] = false;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(i == j) continue;
            for (int k = 0; k < N; k++) {
                if(i == k) continue;
                if(j == k) continue;
                if(A[i][j] + A[j][k] < A[i][k]){
                    printf("-1\n");
                    return 0;
                }
                else if(A[i][j] + A[j][k] == A[i][k]){
                    G[i][k] = false;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(G[i][j]){
                ans += A[i][j];
            }
        }
    }
    ans = ans / 2;
    printf("%lld\n", ans);

}

Measured memory_bytes: 4448
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

#define ll long long

using namespace std;

int main(){
	//freopen("in","r",stdin);
	//ios_base::sync_with_stdio(false); cin.tie(0);
	//cout << fixed << setprecision(20);


	int n,k; scanf("%d%d",&n,&k);
	vector<int> a(n);
	for(int i = 0;i < n;i++) scanf("%d",&a[i]);
	ll cur = 0; for(int i = 0;i < k;i++) cur += a[i];
	ll m = cur;
	for(int i = k;i < n;i++){
		cur += a[i]-a[i-k];
		m = max(cur,m);
	}
	double res = (double)(m+k)/2;
	//cout << res << endl;
	printf("%lf\n", res);
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include <map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
using namespace std;
#define LONG_INF 10000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353LL
#define seg_size 65536*4
#define REP(i,n) for(long long i = 0;i < n;++i)
#define ll long long
int grid[2000][2000] = {};
long long dp[2000][2000] = {};
long long visited[2000][2000] = {};
int main() {
	long long h, w, a, b;
	cin >> h >> w >> a >> b;
	pair<int, int> start, end;
	REP(i, h) {
		string s;
		cin >> s;
		REP(q, s.length()) {
			if (s[q] == 'g') end = make_pair(i, q);
			else if (s[q] == '#') grid[i][q] = 1;//wall
			else if (s[q] == '*') grid[i][q] = 2;//bomb
			else if (s[q] == 's') start = make_pair(i, q);
		}
	}
	priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> next;
	next.push(make_tuple(0, start.first, start.second));
	REP(i, h) {
		REP(q, w) {
			dp[i][q] = LONG_INF;
		}
	}
	dp[start.first][start.second] = 0;
	while (next.empty() == false) {
		tuple<ll, ll, ll> now = next.top();
		next.pop();
		if (visited[get<1>(now)][get<2>(now)] == 1) continue;
		visited[get<1>(now)][get<2>(now)] = 1;
		int xe[8] = { 0,0,1,-1,1,1,-1,-1 };
		int ye[8] = { 1,-1,0,0,1,-1,1,-1 };
		//move road
		for (int t = 0; t < 4; ++t) {
			int x = xe[t] + get<1>(now);
			int y = ye[t] + get<2>(now);
			if (x >= 0 && x < h&&y >= 0 && y < w) {
				if (grid[x][y] != 1) {
					int cost = get<0>(now) + a;
					if (cost < dp[x][y] && visited[x][y] == 0) {
						dp[x][y] = cost;
						next.push(make_tuple(cost, x, y));
					}
				}
			}
		}
		//check for bomb
		int bombing = 0;
		for (int i = max(0LL, get<1>(now) - 1); i <= min(h - 1, get<1>(now) + 1); ++i) {
			for (int q = max(0LL, get<2>(now) - 1); q <= min(w - 1, get<2>(now) + 1); ++q) {
				if (grid[i][q] == 2) bombing = 1;
			}
		}
		if (bombing == 0) {
			for (int t = 0; t < 8; ++t) {
				int x = xe[t] + get<1>(now);
				int y = ye[t] + get<2>(now);
				if (x >= 0 && x < h&&y >= 0 && y < w) {
					int cost = get<0>(now) + a + b;
					if (t >= 4) cost += a;
					if (cost < dp[x][y] && visited[x][y] == 0) {
						dp[x][y] = cost;
						next.push(make_tuple(cost, x, y));
					}
				}
			}
		}
	}
	if (dp[end.first][end.second] == LONG_INF) {
		cout << "INF" << endl;
		return 0;
	}
	cout << dp[end.first][end.second] << endl;
	return 0;
}


Measured memory_bytes: 34448
#include<bits/stdc++.h>
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 ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    ll n,m; cin >> n >> m;
    vector<ll> a(n),s(n+1);
    rep(i,n) cin >> a[i];
    sort(ALL(a));
    rep(i,n) s[i+1] = s[i] + a[i];

    auto check = [&](ll p){
        ll ret = 0;
        rep(i,n){
            if(a[n-1] + a[i] < p) continue;
            ret += n - (lower_bound(ALL(a), p - a[i]) - a.begin());
        }
        return ret;
    };

    ll ok = 0, ng = a[n-1] * 2 + 1;
    while(ng - ok > 1){
        ll mid = (ok + ng) / 2;
        if(check(mid) >= m) ok = mid;
        else ng = mid;
    }

    ll ans = 0;
    rep(i,n){
        if(a[n-1] + a[i] < ok) continue;
        ll tmp = lower_bound(ALL(a), ok - a[i]) - a.begin();
        ans += (n - tmp) * a[i] + (s[n] - s[tmp]);
    }

    ans -= ok * (check(ok) - m);
    cout << ans << endl;
}

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

const ll MAXN = 200000;
const ll INF = 1001001001;
const ll MOD = 1000000007;

ll N, ans=0, tmp=0;
vector<ll> A, B, C, D;

ll gcd(ll a, ll b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
signed main(){
    cin >> N;
    for(int i=0;i<N;i++) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
        D.push_back(d);
    }
    for(int i=0;i<N;i++) {
        //cout << "i : " << i+1 << endl;
        if(A[i]-B[i]>=0&&B[i]<=D[i]) {
            ll dlt = gcd(B[i], D[i]);
            //cout << "gcd : " << dlt << endl;
            ll init = (A[i]-B[i])%dlt;
            if(init<0) init += dlt;
            //cout << "init : " << init << endl;
            ll num = (min(A[i],C[i]+1)-B[i])%dlt;
            if(num<0) num += dlt;
            //cout << "num : " << num << endl;
            ll minv = min(A[i],C[i]+1)-B[i]+init-num;
            if(init-num<0) minv += dlt;
            //cout << "minv : " << minv << endl;
            if(minv>=0) {
                cout << "Yes" << endl;
                continue;
            }
        }
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    m, d = map(int, input().split())
    md, dd = map(int, input().split())

    if (m == 1 and d == 31 and md == 2 and dd == 1):
        print(1)
    elif (m == 2 and d == 28 and md == 3 and dd == 1):
        print(1)
    elif (m == 3 and d == 31 and md == 4 and dd == 1):
        print(1)
    elif (m == 4 and d == 30 and md == 5 and dd == 1):
        print(1)
    elif (m == 5 and d == 31 and md == 6 and dd == 1):
        print(1)
    elif (m == 6 and d == 30 and md == 7 and dd == 1):
        print(1)
    elif (m == 7 and d == 31 and md == 8 and dd == 1):
        print(1)
    elif (m == 8 and d == 31 and md == 9 and dd == 1):
        print(1)
    elif (m == 9 and d == 30 and md == 10 and dd == 1):
        print(1)
    elif (m == 10 and d == 31 and md == 11 and dd == 1):
        print(1)
    elif (m == 11 and d == 30 and md == 12 and dd == 1):
        print(1)
    elif (m == 12 and d == 31 and md == 1 and dd == 1):
        print(1)
    else:
        print(0)

    


if __name__ == '__main__':
    main()


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

int main(){
    ll X, N;
    cin >> X >> N;
    if(N == 0){
        cout << X << endl;
        return 0;
    }
    vector<ll> p(N,0);
    for(int i = 0; i < N; i++) cin >> p[i];
    sort(p.begin() , p.end());
    auto result = find(p.begin(), p.end() ,X);
    ll tmp1 = X - 1,tmp2 = X + 1;
    if(result == p.end()){
        cout << X << endl;
        return 0;
    }else{
        while(1){
            result = find(p.begin(), p.end() ,tmp1);
            if(result == p.end()){
                cout << tmp1 << endl;
                return 0;
            }

            result = find(p.begin(), p.end() ,tmp2);
            if(result == p.end()){
                cout << tmp2 << endl;
                return 0;
            }
            tmp1--;
            tmp2++;
        }
    }
    
    
}

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

int main() {
    string s, t;
    cin >> s >> t;

    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.at(i) != t.at(i)) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3920
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    ll c[3][3];
    rep(i,3) rep(j,3) cin >> c[i][j];
    ll yoko1 = c[0][1] - c[0][0];
    if(yoko1 != c[1][1]-c[1][0] || yoko1 != c[2][1]-c[2][0]){
        puts("No");
        return 0;
    }
    ll yoko2 = c[0][2] - c[0][1];
    if(yoko2 != c[1][2]-c[1][1] || yoko2 != c[2][2]-c[2][1]){
        puts("No");
        return 0;
    }
    ll tate1 = c[1][0]-c[0][0];
    if(tate1 != c[1][1]-c[0][1] || tate1 != c[1][2]-c[0][2]){
        puts("No");
        return 0;
    }
    ll tate2 = c[2][0]-c[1][0];
    if(tate2 != c[2][1]-c[1][1] || tate2 != c[2][2]-c[1][2]){
        puts("No");
        return 0;
    }
    puts("Yes");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	int N,M,L,sw = 0;
  cin >> L >> M >> N;
  for(int i = M;i <= N;i++){
  if(i % L == 0){
    sw = 1;
  }
  }
  if(sw == 1){
    cout << "OK" << endl;
  }else{
    cout << "NG" << endl;
  }
return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
const ll MOD = 1e9 + 7;

int mainsolve(){

	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i,n) cin >> a[i];

	map<P,ll> dp; // dp[P(now,cnt)] = val : nowから始めてcnt個とるときの最大値val
  	dp[P(n-1,1)] = a[n-1];
  	if(n-2 >= 0) dp[P(n-2,1)] = max(a[n-1],a[n-2]);

	for(ll now = n-3; now >= 0; now--){

      ll tmp;
      if((n-now)%2 == 0) tmp = (n-now)/2;
      else tmp = (n-now)/2 + 1;
      
		for(ll cnt = max(1ll,tmp-2); tmp >= cnt; cnt++){
			ll dpUse, dpNotUse;
			if(!dp.count(P(now+1,cnt))) dpNotUse = -1e18;
			else dpNotUse = dp[P(now+1,cnt)];
			if(!dp.count(P(now+2,cnt-1))) dpUse = -1e18;
			else dpUse = dp[P(now+2,cnt-1)];

			//dp[P(now,cnt)] = max(dp[P(now+1,cnt)], dp[P(now+2,cnt-1)] + a[now]);
			dp[P(now,cnt)] = max(dpNotUse, dpUse + a[now]);
		}      
      
	}


	cout << dp[P(0,n/2)] << endl;
	return 0;
}

int main(){
	
	//ll TC;cin>>TC;rep(I,TC){cout<<"case:"<<I+1<<"---"<<endl; // comment out!
		mainsolve();
	//} // comment out!
	return 0;
}


Measured memory_bytes: 42296
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=1e9+7;

int main() {
    int n;
    cin>>n;
    vector<int> H(n);
    rep(i,n) cin>>H[i];
    int ans=0,temp=0;
    rep(i,n-1){
        if(H[i+1]<=H[i]) temp++;
        else{
            ans=max(temp,ans);
            temp=0;
        }
        //cout<<i<<" "<<temp<<endl;
    }
    ans=max(temp,ans);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
//AtCoder ABC048 B - Between a and b ...
#include <bits/stdc++.h>
using namespace std;
using lli=int64_t;

int main() {
    lli a,b,x;
    cin>>a>>b>>x;
    lli st=max(a-1,(lli)0)/x;
    lli ed=b/x;
    lli ans=ed-st;
    if(a==0)++ans; //0だと加える
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
Scanf.scanf "%d" (fun x ->
    let module S = Set.Make (struct type t = int let compare = compare end) in
    let rec loop i c set =
        if i = 32 then set else
        if c > x then loop (i + 1) ((i + 1) * (i + 1)) set else
            loop i (c * i) (S.add c set)
    in
    loop 2 4 (S.singleton 1) |> S.max_elt |> Printf.printf "%d\n"
)

Measured memory_bytes: 3908