akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


def S(): return input()


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


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


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


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


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


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


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


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


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


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

show_flg = False
# show_flg = True


def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def main():
    H, W = MI()
    N = 10
    d = [None for i in range(N)]
    A = [None] * H

    for i in range(N):
        d[i] = LI()

    for i in range(H):
        A[i] = LI()

    d = warshall_floyd(d, N)

    # print_matrix(d)

    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += d[A[i][j]][1]
                # print(A[i][j], 1, d[A[i][j]][1])
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
  int t=0,y=0;
  map<int,int> m;
  vector<int> a(12);
  rep(i, 12) cin >> a[i];
  rep(i,12){
    m[a.at(i)]++;
  }
  for (auto &v: m) y++;
  if (y==3){
    for (auto &v: m) if (v.second!=4) t=1;
  }
  else if (y==2){
    for (auto &v: m) {
        if (v.second==4 || v.second==8) t++;
    }
    if (t==2) t=0;
    else t=1;
  }
else if (y==1){
    for (auto &v: m) if (v.second!=12) t=1;
  }
if (y>=4) t=1;
if (t==0) cout << "yes" << endl;
if (t==1) cout << "no" << endl;
}


Measured memory_bytes: 3080
N, K = map(int,input().split())
num = list(map(int, input().split())) 
p = list(map(lambda x: (x+1)/2, num))
    
ans = sum(p[0:K])
temp = ans
for i in range(N-K):
    temp = temp-p[i]+p[i+K]
    ans = max(ans, temp)
print(ans)

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

using namespace std;

int N;
bool isPrime[1299710];

void primes() {
	fill(isPrime, isPrime + 1299710, 1);
	for (int i = 2; i < 1299710; i++) {
		if (isPrime[i]) {
			for (int j = 2 * i; j < 1299710; j += i) isPrime[j] = false;
		}
	}
}

void solve() {
	int l = N, r = N;
	while (!isPrime[l]) { l--; }
	while (!isPrime[r]) { r++; }
	cout << r - l << endl;
}

int main() {
	primes();
	
	while (1) {
		cin >> N; if (N == 0) break;
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 2428
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	long m,h,w,s[3];
	cin>>h>>w;
	m=h*w;
	for(int i=1;i<h;i++)
	{
		s[0]=i*w;
		if(w%2&&(h-i)%2)
		{
			s[1]=min(w,h-i)*(max(w,h-i)-1)/2;
			s[2]=min(w,h-i)*(max(w,h-i)+1)/2;
		}
		else
		{
			s[1]=s[2]=w*(h-i)/2;
		}
		sort(s,s+3);
		m=min(m,s[2]-s[0]);
	}
	swap(h,w);
	for(int i=1;i<h;i++)
	{
		s[0]=i*w;
		if(w%2&&(h-i)%2)
		{
			s[1]=min(w,h-i)*(max(w,h-i)-1)/2;
			s[2]=min(w,h-i)*(max(w,h-i)+1)/2;
		}
		else
		{
			s[1]=s[2]=w*(h-i)/2;
		}
		sort(s,s+3);
		m=min(m,s[2]-s[0]);
	}
	cout<<m<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 01:08:27 2020

@author: liang
"""

N = int(input())
A = [int(x) for x in input().split()]

count = 1
for a in A:
    if a == count:
        count += 1
if count == 1:
    ans = -1
else:
    ans = N - count + 1
print(ans)

Measured memory_bytes: 30916
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;

struct UnionFind{
    vector<int> data;
    //data[i] = -x ... iが根であり、サイズがx
    //data[i] = x ... iの親がx

    //最初は全員根
    UnionFind(int size): data(size,-1){}

    bool union_set(int x, int y){//サイズがx>yになるようにしてから、xにyをつなげる
        x=root(x);
        y=root(y);
        if(x != y){
            if(data[y] < data[x]) swap(x,y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find_set(int x, int y){//ルートが一致するかどうかを返す
        return root(x) == root(y);
    }
    int root(int x){//根を見つける。ついでに深さ2にしちゃう
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

struct Edge{
    int s,t,cost;
    bool operator<(const Edge &o) const{
        return cost < o.cost;
    }
};


int main() {
    int N,M; cin >> N >> M;
    vector<int> a(M);
    vector<int> b(M);
    REP(i,M){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    int ans = 0;
    REP(i,M){
        UnionFind uf(N);
        REP(j,M){
            if(i!=j){
                uf.union_set(a[j], b[j]);
            }
        }
        if(!uf.find_set(a[i],b[i])){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int N,M,X;
    cin >> N >> M >> X;
    vector<int> A(M);
    rep(i,M){
        cin >> A[i];
    }
    int counter_left = 0;
    int counter_right = 0;
    rep(i,X){
        rep(j,M){
            if (i == A[j]){
                counter_left++;
            }
        }
    }
    for(int i = X; i < N; i++){
        rep(j,M){
            if (i == A[j]){
                counter_right++;
            }
        }
    }
    cout << min(counter_right, counter_left) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[3001][3001][2];
ll a[3001];
ll solve(ll* a,ll i,ll j,bool turn)
{
	if(i>j)
		return 0;
	if(dp[i][j][turn]!=-1)
	{
		return dp[i][j][turn];
	}
	if(turn==1)
	{
		return dp[i][j][turn]=max(a[i]+solve(a,i+1,j,0),a[j]+solve(a,i,j-1,0));
	}
	else
		return dp[i][j][turn]=min(solve(a,i+1,j,1),solve(a,i,j-1,1));
}
int main()
{
	ll n;
	cin>>n;
	ll sum=0;
	for(ll p=1;p<=n;p++)
	{
		cin>>a[p];
		sum+=a[p];
	}
	memset(dp,-1,sizeof(dp));
	ll ScoreX = solve(a,1,n,1);
	ll ScoreY = sum- ScoreX;
	solve(a,1,n,1);
	cout<<ScoreX-ScoreY<<endl;
}

Measured memory_bytes: 144564
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<string>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    string s, t;
    cin >> s >> t;
    vector<int> start(26, -1);
    vector<int> goal(26, -1);
    rep(i, s.length()) {
        int a = s[i] - 'a';
        int b = t[i] - 'a';

        if ( start[a] != -1 || goal[b] != -1 ) {
            if ( start[a] != b || goal[b] != a ) {
                cout << "No" << endl;
                return 0;
            }
        }
        else {
            start[a] = b;
            goal[b] = a;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
int main(){
        int n,m; cin>>n>>m;
        vector<int> h(n+1);
        for(int i=1;i<=n;i++) cin>>h[i];
        vector<int> ans(n+1,1);
        int u,v;
        for(int i=1;i<=m;i++){
                cin>>u>>v;
                ans[u]&=(h[u]>h[v]);
                ans[v]&=(h[v]>h[u]);
        }
        int cnt=0;
        for(int i=1;i<=n;i++) if(ans[i]) cnt++;
        cout<<cnt<<endl;
}


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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,a,ans;
vector<int> v;

main() {
    cin >> n;
    rep(i,n) cin >> a,v.pb(a)
    sort(all(v));
    rep(i,n) {
        int memo=v[i],cnt=0;
        repo(j,i,n) {
            if (v[j] == v[i]) cnt++;
            else {
                i=j-1;
                break;
            }
            if (j==n-1) i=j;
        }
        if (memo<=cnt) ans += abs(memo-cnt);
        else ans += cnt;
    }
    ct(ans)
}


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

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

		int[] xs = new int[N];
		for (int i=0; i<N; i++) xs[i]=scanner.nextInt();
		Arrays.sort(xs);

		int minDist = Integer.MAX_VALUE;
		int ans = 0;

		for (int i=0; i<N; i++){
			minDist = Math.min(minDist, Math.abs(xs[i]-X));
			if (i!=0){
				if (ans==0) ans = Math.abs(xs[i]-xs[i-1]);
				else ans = euc(ans, Math.abs(xs[i]-xs[i-1]));
			}
		}
		if (ans==0) ans = minDist;
		else ans = euc(ans, minDist);
		System.out.println(ans);
	}

	static int euc(int a, int b){
		if (a<b){	//a>=bほしょー
			int c = a;	a = b;	b = c;
		}
		while(a%b!=0) {
			int c = a%b;	a=b;	b=c;
		}
		return b;
	}

}

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

int main() {
  double w,h,x,y;
  cin >> w >> h >> x >> y;
  if(x == w/2.0000 && y == h/2.0000){
    cout << w*h/2.0000 << endl;cout << 1 << endl;
  }
  else{
    cout << w*h/2.0000 << endl;cout << 0 << endl;
  }
}


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

double noudo(int a, int b) {
  return (100. * b) / (a + b);
}

int main(void) {
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;

  double maxnoudo = 0.0;
  int sugarwater = -1, sugar;
  for (int i = 0; i <= 30; i++) for (int j = 0; j <= 30; j++) {
    if (100*a*i + 100*b*j > f) continue;
    for (int l = 0; l <= 100; l++) for (int m = 0; m <= 100; m++) {
      if (100*a*i + 100*b*j + c*l + d*m > f) continue;
      if ((a*i + b*j) * e < c*l + d*m ) continue;
      double nownoudo = noudo(100*a*i + 100*b*j, c*l + d*m);
      if (nownoudo > maxnoudo) {
        maxnoudo = nownoudo;
        sugarwater = 100*a*i + 100*b*j + c*l + d*m;
        sugar = c*l + d*m;
      }
    }
  }
  if (sugarwater == -1) cout << 100*a << " " << 0 << endl;
  else cout << sugarwater << " " << sugar << endl;
  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#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 unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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; }

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

    int N;
    cin >> N;

    ll ans = 0;

    reple(i, 1, N)
    {
        ll n = N / i;

        ans += n * (2 * i + (n - 1) * i) / 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3688
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <set>

#define ll long long
#define ld long double
#define HS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f3f3f3f3f
#define point complex <double> 
#define all(a) a.begin(), a.end()
#define pi acos(-1)
#define mod 1000000007


using namespace std;
int n;
ld coin[3000];
ld dp[3000][3000];
ld solve(int headCnt, int tailCnt)
{

	if (headCnt + tailCnt == n)
		return (headCnt > tailCnt);
	


	if (dp[headCnt][tailCnt] != -1.0)
		return dp[headCnt][tailCnt];

	ld ans = 0;
	ans += (solve(headCnt, tailCnt + 1) * (1.0 - coin[headCnt + tailCnt]));
	ans += solve(headCnt + 1, tailCnt) * coin[headCnt + tailCnt];

	return dp[headCnt][tailCnt] = ans;


}

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

	for (int i = 0; i < 3000; i++)
		for (int j = 0; j < 3000; j++)
			dp[i][j] = -1.0;

	cout << setprecision(12) << solve(0, 0);

	return 0;
}

Measured memory_bytes: 144664
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si size()
#define bk back()
#define popb pop_back()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define ump unordered_map
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define fore(i,a,n) for(int i=a;i<=n;i++)
#define len length()

int main()
{
   int n;
   cin>>n;
   ll arr[n];
   forl(i,0,n) cin>>arr[i];
   ll dp[n][n];
   //dp[0][n-1]

   rfor(l,n-1,0)
   {
       forl(r,l,n)
       {
           if(r==l) dp[l][r]=arr[l];
           else {
               dp[l][r]=max(arr[l]-dp[l+1][r],arr[r]-dp[l][r-1]);
           }
       }
   }
   cout<<dp[0][n-1]<<endl;
}



Measured memory_bytes: 46464
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_VAL_MAX		10000005								// 最大値

// 内部変数
static FILE *szpFpI;											// 入力
static int si1DCnt[D_VAL_MAX];									// 約数数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i, j;
	char lc1Buf[1024];

	// データ - 初期化
	memset(si1DCnt, 0, sizeof(si1DCnt));

	// N - 取得
	int liN;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &liN);

	// 約数数 - セット
	for (i = 1; i <= liN; i++) {
		for (j = i; j <= liN; j += i) {
			si1DCnt[j]++;
		}
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// 合計 - 取得
	long long llSum = 0;
	for (i = 1; i <= liN; i++) {
		llSum += (long long)i * (long long)si1DCnt[i];
	}

	// 出力
	sprintf(lc1Buf, "%lld\n", llSum);
	fOutLine(lc1Buf);

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 40800
from collections import namedtuple
import math
Co = namedtuple('Co', 'x y')

def f(i, n, l, r):
    if i >= n:
        return
    il = Co(x=(1/3 * r.x + (1 - 1/3) * l.x), y=(1/3 * r.y + (1 - 1/3) * l.y))
    ir = Co(x=(2/3 * r.x + (1 - 2/3) * l.x), y=(2/3 * r.y + (1 - 2/3) * l.y))

    trix = 1/2 * (ir.x + il.x - math.sqrt(3) * ir.y + math.sqrt(3) * il.y)
    triy = 1/2 * (math.sqrt(3) * ir.x - math.sqrt(3) * il.x + ir.y + il.y)
    trico = Co(trix, triy)

    f(i+1, n, l, il)
    print(il.x, il.y)
    f(i+1, n, il, trico)
    print(trico.x, trico.y)
    f(i+1, n, trico, ir)
    print(ir.x, ir.y)
    f(i+1, n, ir, r)

if __name__ == '__main__':
    n = int(input())
    print(0, 0)
    f(0, n, Co(0,0), Co(100,0))
    print(100, 0)



Measured memory_bytes: 6176
sx,sy,tx,ty = map(int,input().split())
x = tx-sx
y = ty-sy
a = "R"*x+"U"*y+"L"*x+"D"*y+"L"+"U"*(y+1)+"R"*(x+1)+"DR"+"D"*(y+1)+"L"*(x+1)+"U"
print(a)

Measured memory_bytes: 61816
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
#define N 200086
using namespace std;
int n,k;
ll ans,a[N],tmp[N];
void solve(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)/2;solve(l,mid);solve(mid+1,r);
    int i=l,j=mid+1,t=l;
    while(i<=mid&&j<=r)
        if(a[i]<=a[j])tmp[t++]=a[i++];else{
            tmp[t++]=a[j++];ans+=(i-l);
        }
    while(i<=mid)tmp[t++]=a[i++];
    while(j<=r){tmp[t++]=a[j++];ans+=(i-l);}
    for(int i=l;i<=r;i++)a[i]=tmp[i];
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)a[i]+=(a[i-1]-k);
    solve(0,n);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
#define N 200020
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct Rook{
	int x,y,id;
	bool operator <(const Rook b)const{
		return x<b.x;
	}
}a[N];
int n;
vector<int> ys;
pair<ll,ll> ans[N];

inline int Abs(int x){
	return x>=0?x:-x;
}
inline int Dis(int i,int j){
	return Abs(a[i].x-a[j].x)+Abs(a[i].y-a[j].y);
}

int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i].id=i;
		a[i].x=read(),a[i].y=read();
		ys.push_back(a[i].y);
	}
	sort(a+1,a+n+1);
	ys.push_back(-inf),ys.push_back(inf);
	sort(ys.begin(),ys.end());
	memset(ans,-1,sizeof(ans));
	for(int S=1;S<=n;++S){
		if(~ans[a[S].id].first)continue;
		int by=lower_bound(ys.begin(),ys.end(),a[S].y)-ys.begin();
		int ly=by-1,ry=by+1,L=S,R=S;
		int las=-1;
		bool ok;
		vector<pair<int,int> > it;
		do{
			ok=false;
			for(int i:{L-1,R+1}){
				if(i<1||i>n)continue;
				bool pre=ys[ly]==a[i].y,suf=ys[ry]==a[i].y;
				if(pre||suf){
					int dir=(pre==(i==L-1));
					if(las^dir){
						if(~las)it.emplace_back(L,R);
						las=dir;
					}
					if(pre)--ly;else ++ry;
					if(i==L-1)--L;else ++R;
					ok=true;break;
				}
			}
		}while(ok);
		if(it.empty()||it.back()!=make_pair(L,R)){
			it.emplace_back(L,R);
		}
		static ll dp[N][2];
		int m=it.size();
		dp[m-1][0]=dp[m-1][1]=0;
		for(int u=m-1;u>=1;--u){
			int L1=it[u].first,R1=it[u].second;
			int L2=it[u-1].first,R2=it[u-1].second;
			dp[u-1][0]=min(dp[u][0]+((R1==R2)?Dis(L1,L2):Dis(L1,R1)+Dis(R1,L2)),dp[u][1]+Dis(R1,L1)+Dis(L1,L2));
			dp[u-1][1]=min(dp[u][1]+((L1==L2)?Dis(R1,R2):Dis(R1,L1)+Dis(L1,R2)),dp[u][0]+Dis(L1,R1)+Dis(R1,R2));
		}
		int eL=it[0].first,eR=it[0].second;
		for(int i=eL;i<=eR;++i){
			ans[a[i].id]=make_pair(R-L,min(dp[0][0]+Dis(eL,eR)+Dis(eR,i),dp[0][1]+Dis(eR,eL)+Dis(eL,i)));
		}
	}
	for(int i=1;i<=n;++i){
		printf("%lld\n",ans[i].second-ans[i].first);
	}
	return 0;
}



Measured memory_bytes: 14008
#include <algorithm>
#include <complex>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する

/*
 * ベルマンフォード方法による最短路問題
 * 0ビギナーであることに注意
 *                                 */
struct edge {
    int from, to;
    ll cost;
};
vector<edge> es; // 辺
vector<ll> d; //最短距離,0で初期化してね
int V, E;//頂点数と辺の数

bool find_negative_loop(int s) {
    //dは0で初期化しておくyu7y
    d[s] = 0;
    for (int i = 0; i < V-1; i++) {

        for (int j = 0; j < E; j++) {
            edge e = es[j];
            if (d[e.from] == INFl) continue;
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    return false;
}

/* negative check */
vector<bool> negative;

void negative_check() {
    negative = vector<bool>(V,false);
    for (int i = 0; i < V; i++) {

        for (int j = 0; j < E; j++) {
            edge e = es[j];
            if (d[e.from] == INFl) continue;
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                negative[e.to] = true;
//                if (i == V - 1) return true;
            }
        }
    }
//    return false;
}

void print_d() {
    if (DEBUG) {
        REP(i, 0, d.size()) {
            cout << d[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    queue<int> que;
    int N, M;
    cin >> N >> M;
    V = N;
    E = M;
    d = vector<ll>(V, INFl);
//    d[0] = 0;
    es = vector<edge>(E);

    REP(i, 0, M) {
        edge e;
        cin >> e.from >> e.to >> e.cost;
        e.from--;
        e.to--;
        e.cost *= -1;
        es[i] = e;
    }
//    d[0] = 0;
    find_negative_loop(0);
    ll ans = -d[N-1];
    negative_check();

    if (negative[N-1]) {
        cout << "inf" << endl;
    } else {
//        cout << -d[N-1] << endl;
        cout << -d[N - 1] << endl;
    }
    print_d();
    return 0;
}





Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,b;
    int e;
    scanf("%d %d",&a,&b);
   int c;
   int d;
   e = a + b;
   c = e / 2;
   d = e % 2;
   
   if(d > 0){
       c = c+1;
        printf("%d",c);
   }
   
   else {
 
   printf("%d",c);
}
    return 0;
}

Measured memory_bytes: 128
N = int(input())
S = input()

MOD = 998244353
# 0: ''
# 1: 'A'
# 2: 'B'
# 3: 'C'
# 4: 'AB'
# 5: 'BC'
# 6: 'CA'
dp = [N, 0, 0, 0, 0, 0, 0]
ans = 1
for c in reversed(S):
    # print(c)
    # print(dp)
    if c == 'R':
        if dp[5] > 0:
            ans = (ans * dp[5]) % MOD
            dp[5] -= 1
        elif dp[2] > 0:
            ans = (ans * dp[2]) % MOD
            dp[2] -= 1
            dp[4] += 1
        elif dp[3] > 0:
            ans = (ans * dp[3]) % MOD
            dp[3] -= 1
            dp[6] += 1
        else:
            ans = (ans * dp[0]) % MOD
            dp[0] -= 1
            dp[1] += 1
    if c == 'G':
        if dp[6] > 0:
            ans = (ans * dp[6]) % MOD
            dp[6] -= 1
        elif dp[1] > 0:
            ans = (ans * dp[1]) % MOD
            dp[1] -= 1
            dp[4] += 1
        elif dp[3] > 0:
            ans = (ans * dp[3]) % MOD
            dp[3] -= 1
            dp[5] += 1
        else:
            ans = (ans * dp[0]) % MOD
            dp[0] -= 1
            dp[2] += 1
    if c == 'B':
        if dp[4] > 0:
            ans = (ans * dp[4]) % MOD
            dp[4] -= 1
        elif dp[1] > 0:
            ans = (ans * dp[1]) % MOD
            dp[1] -= 1
            dp[6] += 1
        elif dp[2] > 0:
            ans = (ans * dp[2]) % MOD
            dp[2] -= 1
            dp[5] += 1
        else:
            ans = (ans * dp[0]) % MOD
            dp[0] -= 1
            dp[3] += 1
    # print(ans)

print(ans)


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

int N, Y;

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

    int res10000 = -1, res5000 = -1, res1000 = -1;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; i+j <= N; j++) {
            int k = N-i-j;
            int total = 10000*i+5000*j+1000*k;
            if (total == Y) res10000 = i, res5000 = j, res1000 = k;
        }
    }

    cout << res10000 << " " << res5000 << " " << res1000 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3fffffff
int h,n,opt[100005],a[1005],b[1005],ans = INF;

int main(){
	cin >> h >> n;
	for(int i = 1;i <= 10 * h;i++)
		opt[i] = INF;	
	opt[0] = 0; 
	for(int i = 1;i <= n;i++)
		cin >> a[i] >> b[i];
	for(int i = 1;i <= 10 * h;i++)
	    for(int j = 1;j <= n;j++)		
			if (i >= a[j]) 
				opt[i] = min(opt[i],opt[i - a[j]] + b[j]);
	for(int i = h;i <=  10 * h;i++)
		ans = min(ans,opt[i]);
	cout << ans << endl;
	return 0; 		
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>

using namespace std;

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

    cout << d[n/2] - d[n/2-1] << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
signed main(){
    double a,b;
    cin>>a>>b;
    double n=a/b;
    cout<<n<<endl;
}
//＼(^q^)／ｵﾜﾀ


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> p[40];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			int n;
			scanf("%d",&n);
			int s=0;
			int two=0;
			int one=0;
			for(int j=0;j<9;j++){
				int v;
				scanf("%d",&v);
				s+=v*(two+one);
				one=two;
				two=0;
				s+=v;
				if(v==10){
					two++;
					continue;
				}
				int L=v;
				scanf("%d",&v);
				s+=v*(two+one);
				one=two;
				two=0;
				s+=v;
				if(L+v==10){
					one++;
				}
			}
			bool ok=false;
			int v;
			scanf("%d",&v);
			s+=v*(two+one);
			one=two;
			two=0;
			s+=v;
			if(v==10){
		//		two++;
				ok=true;
			}
			int L=v;
			scanf("%d",&v);
			s+=v*(two+one);
			one=two;
			two=0;
			s+=v;
			if(v==10){
		//		two++;
				ok=true;
			}else if(v>0&&L+v==10){
		//		one++;
				ok=true;
			}
			if(ok){
				scanf("%d",&v);
				s+=v*(two+one);
				one=two;
				two=0;
				s+=v;
			}
			p[i]=make_pair(-s,n);
		}
		std::sort(p,p+a);
		for(int i=0;i<a;i++)printf("%d %d\n",p[i].second,-p[i].first);
	}
}

Measured memory_bytes: 1028
import java.util.*;

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

        int[] H = new int[N];
        for(int i = 0 ; i < N ; i++){
            H[i] = sc.nextInt();
        }
        sc.close();
        int ans = 1;
        int count = 0 ;
        for(int i = 1 ; i < N ; i++){
          //  System.out.println("ans : "+ ans);
          //  System.out.println("i : "+ i);

            for(int j = 0 ; j < i ; j++){

               // System.out.println(H[i]);
              //  System.out.println(H[j]);

                if(H[i] < H[j]){
                    break;
                }else{
                    count ++;
                }
            }    

            if(count == i){
                ans ++;
            }
          //  System.out.println("count : "+ count);
            count = 0;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 22868
INF = 1001001001
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
di = (-1, 0, 1, 0)
dj = ( 0,-1, 0, 1)

ans = 0
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#': continue
        dist = [[INF] * w for _ in range(h)]
        dist[si][sj] = 0
        q = deque([(si,sj)])
        while len(q) > 0:
            i,j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if (ni<0 or ni>=h or nj<0 or nj>=w): continue
                if s[ni][nj] == '#': continue
                if dist[ni][nj] != INF: continue
                q.append((ni,nj))
                dist[ni][nj] = dist[i][j] + 1
        for i in range(h):
            for j in range(w):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])
print(ans)


Measured memory_bytes: 3316
#include <bits/stdc++.h>   
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds;
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a; return gcd(b, a % b);}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}
void solve(){
  #ifndef ONLINE_JUDGE   
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  #endif
}
signed main(){
    cout<<setprecision(2);
    ll a;
    long double b;
    cin>>a>>b;
    if(a==0 or b==0.00){
        cout<<0<<endl;
        return 0;
    }
    long double mult=(long double)a*b;
    ll ans=mult;
    cout<<ans<<endl;
    //printclock;
    return 0;
}

Measured memory_bytes: 3692
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long 
#define MAX 25 * 1e13

int gcd( int a , int b){
  if( b == 0 ) return a;
  return gcd(b,a%b);
}
using namespace std;

int main(){
  ll a,b;
  ll mul = 0;
  cin >> a >> b;
  int g = gcd(a,b);
  mul = a * b ;
  cout << mul / g << endl;
  return 0;
}


Measured memory_bytes: 256
ans = 0
flag = 0
N = int(input())
a = []
b = []

for i in range(N):
    c,d = input().split()
    a.append(c)
    b.append(d)

e = input()

for i in range(N):
    if a[i] == e:
        flag = 1
        continue
    if flag == 1:
        ans += int(b[i])

print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();

		if(a*b*(a+b)%3==0) {
			System.out.println("Possible");
		}
		else {
			System.out.println("Impossible");
		}
	}
}

Measured memory_bytes: 22100
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
T = [INT() for _ in range(N)]

tmp = 1
for i in T:
	tmp = (tmp * i)//gcd(tmp, i)

print(tmp)

Measured memory_bytes: 5156
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

S = input()

ans = False
for i in range(0, 9):
    if S.count(str(i)*2) >= 1:
        ans = True

if ans:
    print("Bad")
else:
    print("Good")

Measured memory_bytes: 3924
import java.util.*;
import java.util.ArrayList;
import java.util.Collections;

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

        int N = sc.nextInt();
        int H = sc.nextInt();
        int[] a = new int[N];
        int[] b = new int[N];
        int maxa = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0; i<N; i++){
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            list.add(b[i]);
            maxa = Math.max(maxa, a[i]);
        }
        Collections.sort(list);
        int sum = 0;
        int bat = 0;
        for(int i=N-1; i>=0; i--){
            if(list.get(i)>maxa){
                sum += list.get(i);
                bat += 1;
            }
            if(sum>=H){
                break;
            }
        }
        int ans = 0;
        if(sum>=H){
            ans = bat;
        }
        else{
            sum = H - sum;
            if(sum%maxa==0){
                ans = sum / maxa + bat;
            }
            else{
                ans = sum / maxa + 1 + bat;
            }
        }
        System.out.println(ans);
    }
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int N,K;
int b[2002][2002];
int s[4002][4002];

int get(int x , int y){
	return s[x+K-1][y+K-1] + s[x-1][y-1] - s[x-1][y+K-1] - s[x+K-1][y-1];
}

int main(){
	cin >> N >> K;
	repp(i,0,N){
		int x,y;
		char c;
		cin >> x >> y >> c;
		if(c=='W') y += K;
		++b[x%(2*K)+1][y%(2*K)+1];
	}
	repp(i,1,4*K+1){
		repp(j,1,4*K+1){
			s[i][j] = s[i][j-1] + b[(i-1)%(2*K)+1][(j-1)%(2*K)+1];
		}
	}
	repp(j,1,4*K+1){
		repp(i,1,4*K+1){
			s[i][j] += s[i-1][j];
		}
	}
	int ans = 0;
	repp(i,1,2*K+1){
		repp(j,1,2*K+1){
			ans = max(ans , get(i,j) + get(i+K,j+K));
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 78464
a = input()
b = 0
c = 0
i = 0
while i < len(a) :
    if a[i] == "A" :
        b = b + 1
    if a[i] == "B" :
        c = c + 1
    i = i + 1
if (b > 0) and (c > 0) :
    print("Yes")
else:
    print("No")

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

int main()
{
	vector<int> v;
	int n, ans = 0;
	cin >> n;
	for(int i = 0; i < 2 * n; i++){
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i += 2){
		ans += v[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(N, M, G, S, T):
    INF = 10**10
    dp = [[INF for _ in range(N)] for __ in range(3)]
    dp[0][S] = 0
    q = [(0, S)]
    while q:
        d, v = heappop(q)
        for to in G[v]:
            if d + 1 >= dp[(d + 1) % 3][to]: continue
            dp[(d + 1) % 3][to] = d + 1
            heappush(q, (d + 1, to))
    print(dp[0][T] // 3 if dp[0][T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)


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

int main(void){
    char s[11]; 

    scanf("%s", s);
    s[0] = '2';
    s[1] = '0';
    s[2] = '1';
    s[3] = '8';

    printf("%s\n", s);

    return 0;

} 


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;

/*
二分探索 binary search
https://qiita.com/drken/items/97e37dd6143e33a64c8c
狭義: ソート済み配列の中から目的のものを高速に探索する
- 単純な線形探索では O(n)の時間がかかる
- 二分探索を行えば O(logn)の時間で済む

めぐる式二分探索
- x = left は条件を満たさない
- x = right は条件を満たす
- left と right の間に条件を満たすようになる境目がある！
-- 境目まではずっと条件を満たしておらず、境目から先はずっと条件を満たしている (単調性)
実装
- left は「常に」条件を満たさない
- right は「常に」条件を満たす
- right - left = 1 になるまで範囲を狭める (最後は right が条件を満たす最小)
*/
ll N,D,A;
vector<ll> a;

// index が条件を満たすかどうか
// 条件: 爆発が届かない
bool isOK(ll index, ll key) {
	if (a[index] >= key) return true;
	else return false;
}

// 汎用的な二分探索のテンプレ
ll binary_search(ll key) {
	ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	ll right = (ll)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}

	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}

ll ceil(ll A, ll B){
	ll ans = A/B;
	if (A%B!=0)ans++;
	return ans;
}

int main() {
	// 入力
	cin>>N>>D>>A;
	vector<P> XH;
	REP(i,N){
		ll X,H;cin>>X>>H;
		XH.pb(make_pair(X,H)); // (座標, HP)
	}
	
	// 解法
	sort(XH.begin(), XH.end()); // 座標順に並べる
	// 二分探索で iのモンスターを攻撃した時どこjまで攻撃が届くか調べる
	REP(i,N)a.pb(XH[i].first); // 探索を行う配列a
	ll reach[N]; // reach[i]: iを攻撃した時攻撃に巻き込まれない最小のindex
	REP(i,N){
		ll key = XH[i].first + D * 2 + 1; // 爆発が届かなくなる座標
		reach[i] = binary_search(key) ;
	}
	vector<ll> limit[N]; //limit[i]: i番目のモンスターから届かなくなる攻撃のindex
	REP(i,N){
		if (reach[i]<N)limit[reach[i]].pb(i);
	}

	// 貪欲で攻撃回数を計算
	ll ans = 0;
	ll HP[N];
	REP(i,N)HP[i] = XH[i].second;
	ll n_bomb[N];REP(i,N)n_bomb[i] = 0; // 各モンスターに攻撃した回数
	ll n_bomb_reach = 0; // 有効ダメージ
	// REP(i,N)printf("i: %lld, HP: %lld, reach: %lld\n", i, HP[i], reach[i]);
	REP(i,N){// 左から順にモンスターを攻撃
		if (limit[i].size()>0){ // 届かなくなる攻撃がある
			REP(j, limit[i].size()){
				n_bomb_reach -= n_bomb[limit[i][j]] * A; // 届かなくなった攻撃を減算
			}
		}
		if (HP[i]>n_bomb_reach){// モンスターiのHPが残ってるなら
			n_bomb[i] += ceil(HP[i] - n_bomb_reach, A);
			ans += n_bomb[i];
			n_bomb_reach += n_bomb[i] * A;
		}
	}

	//出力
	printf("%lld\n", ans);
}


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

int main() {
  char c;
  cin >> c;
  if( c=='a' || c=='e' || c=='i' || c=='o' || c=='u'){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,K;
  cin>>n>>K;
  long long ans;
  ans=1;
  for (int i=0;i<n;i++){
    ans*=K-1;
  }
 long long anse;
  anse=ans*K/(K-1);
  cout<<anse<<endl;
}

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

int a[501][501], h, w;
vector<string> v;

int main(){
    cin >> h >> w;
    for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)cin >> a[i][j];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w - 1; j++){
            if(a[i][j] % 2 == 1){
                a[i][j + 1]++;
                string s = to_string(i + 1) + " " + to_string(j + 1) + " " + to_string(i + 1) + " " + to_string(j + 2);
                v.push_back(s);
            }
        }
    }
    for(int i = 0; i < h - 1; i++){
        if(a[i][w - 1] % 2 == 1){
            a[i + 1][w - 1]++;
            string s = to_string(i + 1) + " " + to_string(w) + " " + to_string(i + 2) + " " + to_string(w);
            v.push_back(s);
        }
    }
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++)cout << v[i] << endl;
}

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

int main(){
	int N,M,X,Y,x(-100),y(100),m;
    cin >> N >> M >> X >> Y;
    for(int i = 0 ; i < N ; i ++){
    	cin >> m;
        if(x < m) x = m;
    }
    for(int i = 0 ; i < M ; i ++){
    	cin >> m;
        if(y > m) y = m;
    }
    if(X < Y && x < y && x < Y && X < y) cout << "No War" << endl; else cout << "War" << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long lli;
const int maxn = 5e5 + 50;
typedef pair<int, int> P;

int arr[maxn];
int a, b, c, d, e, f, g;
void solve();
int main()
{
	int t = 1;
//	cin >> t;
	for(int i=0; i<t; i++)
	{
		solve();
	}
	return 0;
}

// type below

void solve()
{
	cin >> a >> b >> c >> d;
	int one = a / d + (a % d != 0);
	int two = c / b + (c % b != 0);
	if(two <= one) cout << "Yes";
	else		   cout << "No";
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a , b , c ;
  	cin>>a>>b>>c;
  
  	if((b*c)>=a){
    cout<<"Yes"<<endl;
    }
  else{
  	cout<<"No"<<endl;
  }
	return 0;
}

Measured memory_bytes: 3632
//
//  header_useful.h
//  c++_acm
//
//  Created by 李弘辰 on 2019/7/23.
//  Copyright © 2019 李弘辰. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it before "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */


int main()
{
    int n;
    scanf("%d",&n);
    int a[200010] = {0};
    int in;
    for (int i = 0;i < n - 1;i ++) {
        scanf("%d",&in);
        a[in] ++;
    }
    for (int i = 1;i <= n;i ++) {
        printf("%d\n",a[i]);
    }
    return 0;
}


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

int main(){
    int n,m;
    cin>>n>>m;
    int a[m],dif[m-1];
    rep(i,m)cin>>a[i];
    sort(a,a+m);
    rep(i,m-1)dif[i]=a[i+1]-a[i];
    int ans=0;
    sort(dif,dif+m-1);
    if(n>=m){
        ans=0;
    }
    else{
        rep(i,m-n){
            ans+=dif[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>

namespace ABC171
{
  class A
  {
  public:
    A() = default;
    ~A() = default;


    void Run()
    {
      std::string a = {};
      std::cin >> a;

      int c = (int)(a.at(0));

      std::cout << (('A' <= c && c <= 'Z') ? "A" : "a") << std::endl;
    }
  };

}
int main()
{

  ABC171::A prob;
  prob.Run();

  return 0;
}




Measured memory_bytes: 2976
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(void)
{
  int n;
  int a[109] ={0};
  cin >> n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  sort(a,a+n);
  int ans=0;
  for(int i=n-1;i>=0;i-=2)ans+=a[i];
  for(int i=n-2;i>=0;i-=2)ans-=a[i];
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    a, b, c, d = na[0], na[1], na[2], na[3]

    print('Yes' if abs(c - a) <= d or (abs(b - a) <= d and abs(c - b) <= d) else 'No')


if __name__ == '__main__':
    main()



Measured memory_bytes: 2940
//##MohK..
//09/05/2020....3.00...
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    string a;
    cin>>a;
    if(a=="ABC")cout<<"ARC"<<endl;
    else cout<<"ABC"<<endl;


    return 0;
}



Measured memory_bytes: 3572
#include<iostream>
#include <string>
#include<vector>
typedef long long ll;

using namespace std;
int main()
{
	int n;
	cin >> n;
	int copy = n;
	int sum=0;
	while (1) {
		sum += n % 10;
		n /= 10;
		if (n == 0) break;
	}
	if (copy%sum==0) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256