akhauriyash/Code-Regression huggingface dataset:
// Problem : C - Many Requirements
// Contest : AtCoder - AtCoder Beginner Contest 165
// URL : https://atcoder.jp/contests/abc165/tasks/abc165_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
#define pb push_back
#define PI acos(-1.0)
#define EPS 1e-4
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fout(S,x)            cout<<fixed<<setprecision(x)<<(S)<<endl
#define present(c,x) ((c).find(x) != (c).end())
#define T() ll t;cin>>t;while(t--)
#define mem(input,b) memset(input,b,sizeof(input))
#define ff first
#define ss second
#define fread(input) freopen("input","r",stdin)
#define fwrite(b) freopen("b","w",stdout)
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define FOREACH(i,c) for (__typeof ((c).begin()) i = (c).begin() ; i != (c).end() ; i++)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
vector<tuple<int,int,int,int> > store;
int n,m,q;
vector<int> a;
int result = 0;
int calc(){
	int sum = 0;
	for(int i=0;i<q;++i){
		int ai,bi,ci,di;
		ai = get<0>(store[i]);
		bi = get<1>(store[i]);
		ci = get<2>(store[i]);
		di = get<3>(store[i]);
		if(a[bi-1]-a[ai-1]==ci)
			sum += di;
	}
	return sum;
}
void recur(int idx, int prev){
	//trace(idx, prev, n);
	if(idx == n){
		result = max(result, calc());
		return;
	}
	for(int v=prev;v<=m;++v){
		a[idx] = v;
		recur(idx+1,v);
	}
}
int main(){
    fastio;
    cin>>n>>m>>q;
    for(int i=0;i<q;++i){
    	int a,b,c,d;
    	cin>>a>>b>>c>>d;
    	store.pb(make_tuple(a,b,c,d));
    }
    a.resize(n);
    recur(0,1);
    cout<<result<<endl;
    return 0;
}    


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).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; }

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;


int main(){
  int k,t; cin >> k >> t;
  vi a(t); rep(i,t) cin >> a[i];
  int amax = 0;
  rep(i,t) chmax(amax, a[i]);

  cout << max(2*amax-k-1, 0) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int n,cont=0;
	scanf("%d", &n);
	int arr[n];
	for(int i=0;i<n;i++)scanf("%d", &arr[i]);
	int *a = arr, *b=arr+1,*c=arr+2;
	for(;c<arr+n;a++,b++,c++){
		if((*a>*b && *b>*c)||(*a<*b && *b<*c))cont++;
	}
	printf("%d\n", cont);
	return 0;

}

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

const int MOD=1e9+7;
ll mod(ll x){
    ll res=x%MOD;
    return res+(res<0?MOD:0);
}
ll power(ll a, ll n){
    ll res=1;
    a=mod(a);
    for(;n>0;n>>=1){
        if(n&1)res=mod(res*a);
        a=mod(a*a);
    }
    return res;
}

int main(){
    string l;
    cin>>l;
    int n=l.size(),cnt=0;
    ll ans=0;
    for(int i=0; i<n; i++){
        if(l[i]=='0')continue;
        ans=mod(ans+mod(power(2,cnt)*power(3,n-i-1)));
        cnt++;
    }
    cout<<mod(ans+power(2,cnt));
    return 0;
}

Measured memory_bytes: 512
def main():
    n, m = map(int, input().split())
    num = [0] * n
    reserved = [False] * n
    for _ in range(m):
        s, c = map(int, input().split())
        s -= 1
        if reserved[s]:
            if c != num[s]:
                print(-1)
                exit()
        else:
            reserved[s] = True
            num[s] = c
    if n > 1 and not reserved[0]:
        num[0] = 1
    if n > 1 and num[0] == 0:
        print(-1)
    else:
        print("".join(map(str, num)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 9136
#include<stdio.h>
#include<iostream>
using namespace std;
long long LTF_GBS(long long x,long long y)
{
	long long i,m,M,flag=0,gbs;
	M=(x>y)? x:y;
	m=(x>y)? y:x;
	for(i=M;i>=1;i--)
	   if(M%i==0&&m%i==0)
		  break;
	  gbs=m*M/i;
    return gbs;
} 
int main(void)
{
	long long a,b,c;
	scanf("%lld%lld",&a,&b);
	c=LTF_GBS(a,b);
	printf("%lld",c);
	return 0;
}

Measured memory_bytes: 256
//C
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long LL;

int main(){
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int N;
	scanf("%d", &N);
	int a[N + 1];
	int maks = 0;
	LL ans = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
		maks = max(maks, a[i]);
		ans += (maks - a[i]);
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 4548
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int a,b;
    cin >> a >> b;
    if(a + b == 15) cout << "+" << endl;
    else if(a * b == 15) cout << "*" << endl;
    else cout << "x" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, readline().rstrip().split())
    P = list(map(int, readline().rstrip().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().rstrip().split())
        uf.union(x-1, y-1)
    
    res = 0
    for i, p in enumerate(P):
        if uf.same(p - 1, i):
            res += 1
    
    print(res)

if __name__ == '__main__':
    main()

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

int main() {
 int N;
  cin >> N;
  double p;
  double odd;
  if(N%2==0) odd=N/2;
  if(N%2==1) odd=N/2+1;
  p = odd / N;
  cout << p << endl;
}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

bool c[11];
char str[1001];
int p;

bool formula()
{
    bool a;
    if (str[p] == 'T') {
        a = true;
        ++p;
    } else if (str[p] == 'F') {
        a = false;
        ++p;
    } else if ('a' <= str[p] && str[p] <= 'k') {
        a = c[str[p] - 'a'];
        ++p;
    } else if (str[p] == '-' && str[p + 1] != '>') {
        ++p;
        a = !formula();
    } else {
        ++p;
        bool l = formula();
        if (str[p] == '*') {
            ++p;
            bool r = formula();
            a = l && r;
        } else if (str[p] == '+') {
            ++p;
            bool r = formula();
            a = l || r;
        } else if (str[p] == '-' && str[p + 1] == '>') {
            p += 2;
            bool r = formula();
            a = !l || r;
        }
        ++p;
    }
    return a;
}

bool equation()
{
    bool l = formula();
    ++p;
    bool r = formula();
    return l == r;
}

int main()
{
    for (;;) {
        gets(str);
        if (str[0] == '#')
            break;

        bool f = true;
        for (int i = 0; i < 2048; ++i) {
            for (int j = 0; j < 11; ++j)
                c[j] = i & (1 << j);

            p = 0;
            f = f && equation();
        }
        puts(f ? "YES" : "NO");
    }

    return 0;
}

Measured memory_bytes: 944
#include <iostream>

using namespace std;


int main()
{
    int n,count=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int x;
        cin>>x;
        if( i%2 !=0  && x%2!=0)
        {
            count++;
        }
        
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k,a,m,c;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a;
    }
    if(n==k){
       cout<<"1"<<endl;

    }
    else{
        m=k;
        c=1;
        while(m<n){
            m+=(k-1);
            c++;
        }
        cout<<c<<endl;
    }
    return 0;
}


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

long long gcd(long long a, long long b){
	return b==0?a:gcd(b,a%b);
}

long long lcm(long long a, long long b){
	return a/gcd(a,b)*b;
}

int main() {
	int n;
	long long ans;
	cin >> n;
	long long a[n]={};
	for (int i=0;i<n;i++){
		cin >> a[i];
	}
	ans=a[0];
	for (int i=1;i<n;i++){
		ans= lcm(ans,a[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int s; cin >> s;
    VI a(1000000,0);
    a[0] = s;
    FOR(i,1,a.size()){
        if(a[i-1] % 2 == 0) a[i] = a[i-1] / 2;
        else a[i] = 3 * a[i-1] + 1;
        rep(j,i){
            if(a[i] == a[j]){
                OUT(i+1);
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 8064
M = 10**6
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 4*10**4):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(C[r] - C[l-1])


Measured memory_bytes: 67296
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
#define stp(x)  setprecision(x)
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,Q;
    cin>>n>>m>>Q;
    int l,r,q,p;
    vector<vector<ll> > sum(n+5,vector<ll>(n+5));
    rep(i,m){
	cin>>l>>r;
	sum[l][r]++;
    }
    REP(i,1,n+1){
	REP(j,1,n+1){
	    sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	}

    }
    rep(i,Q){
	cin>>p>>q;
	cout<<sum[q][q]-sum[p-1][q]-sum[q][p-1]+sum[p-1][p-1]<<'\n';
    }
    return(0);
}



Measured memory_bytes: 2944
#include<stdio.h>
 int main(void)
{
int n,t,ans=0,i=1;
scanf ("%d %d",&n,&t);
   n=n+1;
int array1[101],array2[101];
for (i;i<n;i++){
	scanf("%d %d",&array1[i],&array2[i]);
	if(array2[i]<=t) {if(ans==0) ans=array1[i];
		else if(ans>array1[i]) ans=array1[i];}
}
if(ans==0) printf("TLE");
else printf("%d",ans);
return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long fact(unsigned int n)
{
	if(n == 0)
		return 1;
	else
		return fact(n-1)*n;
}

int main()
{
	int n;
	scanf("%d",&n);
	printf("%lld\n",fact(n));
	return 0;
}

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

string S;
int A,B,C,D;
int a,b;

int main(){
	//cin>>S;
	cin>>A>>B>>C>>D;

	while(1){
		C -= B;
		if(C<=0){
			cout<<"Yes"<<endl;
			return 0;
		}
		A -= D;
		if(A<=0){
			cout<<"No"<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 3632
#include <iostream>
#include <string.h>
using namespace std;
int main(void){
  string s;
  cin >> s;
  int min=1000;
  for(int i=0;i<s.length()-2;i++){
    int n = (s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0');
    if(min>abs(n-753)){
      min=abs(n-753);
    }
  }

  cout << min << endl;
  
  return 0;  
}


Measured memory_bytes: 764
N = int(input())
Vs = [ input().split() for _ in range(N)]
Vs = list(map(lambda x: (x[0], int(x[1])),Vs))
Vss = sorted(Vs, key=lambda x: (x[0], -x[1]))

for v in Vss:
    print(Vs.index(v)+1)

Measured memory_bytes: 3060
A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
N = int(input())
listb = [int(input()) for i in range(N)]

for item in listb:
    for i in range(3):
        if A1[i] == item:
            A1[i] = 0
    for j in range(3):
        if A2[j] == item:
            A2[j] = 0
    for k in range(3):
        if A3[k] == item:
            A3[k] = 0
if sum(A1) == 0 or sum(A2) == 0 or sum(A3) == 0:
    print('Yes')
    exit()
for i in range(3):
    if A1[i] == A2[i] and A2[i] == A3[i]:
        print('Yes')
        exit()
if A1[0] == A2[1] == A3[2] or A1[2] == A2[1] == A3[0]:
    print('Yes')
    exit()
print('No')


Measured memory_bytes: 3064
from collections import defaultdict
N, M = [int(_) for _ in input().split()]
V = defaultdict(list)
for i in range(M):
    A, B = [int(_) for _ in input().split()]
    V[A].append(B)
    V[B].append(A)

def solve(N, M, V):
    result = [1, V[1][0]]
    used = [False] * (N + 1)
    for x in result:
        used[x] = True

    def check_edge(i):
        for e in V[result[i]]:
            if not used[e]:
                if i == -1:
                    result.append(e)
                else:
                    result.insert(i, e)
                used[e] = True
                return True
        return False

    while True:
        if check_edge(0): continue
        if check_edge(-1): continue
        return result

result = solve(N, M, V)
print(len(result))
print(*result)


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

template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};
using namespace std;
void solve(){
   int c;
   cin>>c;
   set<int>s;
   int u;
   for(int i=0;i<c;i++){
      cin>>u;
       s.insert(u);
   }
   cout<<s.size();

}
int main(){
    std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
  return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ns(n);
    for (int i=0; i<m; ++i) {
        int num1, num2; cin >> num1 >> num2;
        ns[--num1]++; ns[--num2]++;
    }
    for (int i: ns) cout << i << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b){
    return *(int*)b - *(int*)a;
}

int main(int argc, char *argv[]){    
    int n,m;
    scanf("%d %d", &n,&m);

    int array[n];
    int sum = 0;
    for(int i = 0; i < n; i++){
        scanf("%d",array+i);
    }
    qsort(array, n,sizeof(int),compare);

    for(int i = 0; i< n;i++){
        sum+=array[i];
    }

    for(int i = 0; i<m;i++){
        if(array[i] < (double)sum/(4*m)){
            printf("No");
            return 0;
        }
    }

    printf("Yes");

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

    string s, t; cin >> s >> t;
    if (s.size() != t.size() - 1) {
        cout << "No" << endl;
        return 0;
    }
    string subt = t.substr(0, s.size());
    if (s == subt) cout << "Yes";
    else cout << "No";
    cout << endl;


    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#define N 1000001

int spf[N], u[N], s[17], d, i, k;
char* r = "pairwise";

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

main(j) {
    while (++i < N)spf[i] = i;
    for (i = 2; i * i < N; i++) {
        for (j = i * i; j < N; j += i) {
            if (spf[j] == j)
                spf[j] = i;
        }
    }
    for (scanf("%*d"); ~scanf("%d", &j); k = 0) {
        d = gcd(d, j);
        for (; j > 1; j /= spf[j]) {
            i = spf[j];
            if (u[i]) r = "setwise";
            s[k++] = i;
        }
        while(k--)u[s[k]] = 1;
    }
    printf("%s coprime\n", d > 1 ? "not" : r);
    return 0;
}


Measured memory_bytes: 9544
def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if y==0:
        return x
    elif x%y==0:
        return y
    else:
        return GCD(y,x%y)

N=int(input())
A=list(map(int,input().split()))

L=[0 for i in range(N+2)]
R=[0 for i in range(N+2)]

for i in range(1,N+1):
    L[i]=GCD(L[i-1],A[i-1])
for i in range(N):
    R[N-i]=GCD(R[N-i+1],A[N-i-1])

G=[0 for i in range(N+2)]
for i in range(1,N+1):
    G[i]=GCD(L[i-1],R[i+1])

print(max(G))

Measured memory_bytes: 14400
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = sorted(ZZ(), reverse=True)
    F = sorted(ZZ())

    if sum(A) <= K:
        print(0)
        return

    cost = list()
    for a, f in zip(A, F): cost.append(a*f)

    ok = 10 ** 12
    ng = -1

    while ok - ng > 1:
        mid = (ok+ng)//2
        cc = 0
        for i in range(N): cc += max(0, (cost[i]-mid+F[i]-1)//F[i])
        if cc <= K: ok = mid
        else: ng = mid
    print(ok)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 121036
#include <iostream>

using namespace std;

int main() {
  int sum = 0, a;
  for(int i = 0; i < 3; i++) {
    cin >> a;
    sum += a;
  }

  if(sum >= 22) {
    cout << "bust";
  } else {
    cout << "win";
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

int main()

{
    ll a, b, n;
    cin >> a >> b >> n;
    if(b == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    ll ans = -1e18;

    n = min(n, b - 1);

    ans = max(ans, (a * n) / b - a * (n / b));

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


Measured memory_bytes: 3184
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int[] A)
        {
            int xor = 0;
            var bit = new bool[31];
            foreach (int a in A)
            {
                xor ^= a;
                for (int i = 0; true; ++i)
                {
                    if (((a >> i) & 1) != 0)
                    {
                        bit[i] = true;
                        break;
                    }
                }
            }
            int cnt = 0;
            for (int i = 30; i >= 0; --i)
            {
                if ((xor & (1 << i)) != 0)
                {
                    if (bit[i])
                    {
                        ++cnt;
                        xor ^= (1 << i) - 1;
                    }
                    else
                    {
                        return -1;
                    }
                }
            }
            return cnt;
        }

        static void Main(string[] args)
        {
            int N = ReadInt();
            var A = new int[N];
            for (int i = 0; i < N; ++i) { A[i] = ReadInt(); }
            Console.WriteLine(Solve(A));
        }
    }
}


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

int main() {
	int n; cin >> n;
	int d;
	for(int i = n; i > 0; i/=10){
		d += i%10;
	}
	cout << ((n%d == 0) ? "Yes" : "No") << '\n';
	
	return 0;
}

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

int main(void)
{
  long long a, b, c;
  long long cnt=0;
  cin>>a>>b>>c;

  while(a%2==0 && b%2==0 && c%2==0)
    {
      long long a_prev = a;
      long long b_prev = b;
      long long c_prev = c;
      a = b_prev/2 + c_prev/2;
      b = a_prev/2 + c_prev/2;
      c = a_prev/2 + b_prev/2;
      
      if(a==a_prev && b==b_prev && c==c_prev)
	{
	  cnt = -1;
	  break;
	}
      cnt++;
    }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdint>
using namespace std;

const int N_MAX = 100;

int main(){
    int N;
    string W[N_MAX];

    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> W[i];
    }

    bool ans = true;
    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(W[i] == W[j]) {
                ans = false;
            }
        }
        if(W[i - 1].back() != W[i].front()) {
            ans = false;
        }
        if(!ans) {
            break;
        }
    }

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


Measured memory_bytes: 256
s = input()
ans = len(s)
for c in set(s):
    new_s = s
    while len(set(new_s)) > 1:
        tmp = ""
        for i in range(len(new_s) - 1):
            tmp += c if new_s[i] == c or new_s[i + 1] == c else new_s[i]
        new_s = tmp
    ans = min(ans, len(s) - len(new_s))
print(ans)


Measured memory_bytes: 41580
A,B,K = map(int,input().split())
for i in range(K):
  if i%2 == 0:
    if A%2==1: A-=1
    B += A//2
    A = A//2
  else:
    if B%2==1: B-=1
    A += B//2
    B = B//2
print(A,B)

Measured memory_bytes: 38384
s = input()

if(len(s) % 2 == 0):
    s = s[:-2]
else:
    s = s[:-1]

while(s != ""):
    if(s[:len(s)//2] == s[len(s)//2:]):
        print(len(s))
        break
    s = s[:-2]


Measured memory_bytes: 8996
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

k = ni()

def bfs():
    q = deque()
    for n in range(1, 10):
        q.append(n)
    i = 1
    while len(q):
        p = q.popleft()
        if i == k:
            return p
        i += 1
        if p % 10 != 0:
            q.append(p * 10 + (p % 10 - 1))
        q.append(p * 10 + p % 10)
        if p % 10 != 9:
            q.append(p * 10 + (p % 10 + 1))

print(bfs())

Measured memory_bytes: 12488
import fractions
import math

def divide_two(x):
    ans = 0
    while x > 0:
        if x % 2 == 0:
            ans += 1
            x = x // 2
        else:
            break
    return ans

n, m = map(int, input().split())
a = list(map(int, input().split()))
flag = [divide_two(i) for i in a]

if sum(flag) != flag[0] * n:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int H, W, K;
	cin >> H >> W >> K;
	vector<vector<char>> c(H);
	int sum = 0;
	for (int i = 0; i < H; i++) {
		c[i].resize(W);
		for (int j = 0; j < W; j++) {
			cin >> c[i][j];
			if (c[i][j] == '#') {
				sum++;
			}
		}
	}
	int cnt = 0;
	for (int a = 0; a < (1 << H); a++) {
		vector<int> xv;
		for (int i = 0; i < H; i++) {
			if (a & (1 << i)) xv.emplace_back(i);
		}
		for (int b = 0; b < (1 << W); b++) {
			vector<int> yv;
			for (int j = 0; j < W; j++) {
				if (b & (1 << j)) yv.emplace_back(j);
			}
			if (xv.empty() && yv.empty()) {
				if (sum == K) cnt++;
			} else if (!xv.empty() && yv.empty()) {
				int cnt2 = 0;
				for (auto x : xv) {
					for (int l = 0; l < W; l++) {
						if (c[x][l] == '#') cnt2++;
					}
				}
				if (sum - cnt2 == K) cnt++;
			} else if (xv.empty() && !yv.empty()) {
				int cnt3 = 0;
				for (auto y : yv) {
					for (int l = 0; l < H; l++) {
						if (c[l][y] == '#') cnt3++;
					}
				}
				if (sum - cnt3 == K) cnt++;
			} else {
				int cnt4 = 0;
				for (auto x : xv) {
					for (auto y : yv) {
						if (c[x][y] == '#') cnt4++;
					}
				}
				int cnt5 = 0;
				for (auto x : xv) {
					for (int l = 0; l < W; l++) {
						if (c[x][l] == '#') cnt5++;
					}
				}
				for (auto y : yv) {
					for (int l = 0; l < H; l++) {
						if (c[l][y] == '#') cnt5++;
					}
				}
				if (sum - cnt5 + cnt4 == K) cnt++;
			}
		}
	}
	cout << cnt << '\n'; 
	return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,n) for(lli i=0;i<n;i++)
#define repb(i,n) for(lli i=n-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define bg() begin()
#define en() end()
#define ft first
#define sc second
#define vect_lli_it vector<lli>::iterator
#define set_lli_it set<lli>::iterator
#define inf 1e18
#define all(X) X.begin(),X.end()
#define iterate(X) for(it=X.begin();it!=X.end();it++)
lli combi(lli n,lli k)
{
    lli ans=1;
    k=k>n-k?n-k:k;
    lli j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli findlcm(vector <lli> arr, lli n)
{
    lli ans = arr[0];
    for (lli i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));

    return ans;
}
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n;
    cin>>n;
    vector <lli> arr;
	lli x;
	rep(i,n){
		cin>>x;
		arr.pb(x);
	}
	vector <lli> sum_arr;
	rep(i,n){
		sum_arr.pb(i+arr[i]+1);
	}
	vector <lli> diff_arr;
	rep(i,n){
		diff_arr.pb(i-arr[i]+1);
	}
	sort(all(sum_arr));
	sort(all(diff_arr));
	vect_lli_it itl,itu;
	lli ans=0;
	rep(i,sum_arr.size()){
		itl=lower_bound(all(diff_arr),sum_arr[i]);
		itu=upper_bound(all(diff_arr),sum_arr[i]);
		if(itl!=diff_arr.en() && itu!=diff_arr.en() && *itl==sum_arr[i]){
			ans=ans+(itu-diff_arr.bg())-(itl-diff_arr.bg());
		}
		else if(itl!=diff_arr.en() && *itl==sum_arr[i]){
			ans=ans+diff_arr.size()-(itl-diff_arr.bg());
		}
	}
	cout<<ans;
    return 0;
}


Measured memory_bytes: 9508
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int len=a.size();
    int len1=b.size();
    if(len==len1){
    	for(int i=0;i<len1;i++){
    	cout<<a[i]<<b[i];
	}
	cout<<endl;
	}else{
		for(int i=0;i<len1;i++){
    	cout<<a[i]<<b[i];
	}
	cout<<a[len-1];
	cout<<endl;
	}
    
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

que = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())

print(que[n-1])

Measured memory_bytes: 3316
#input one int
#a = int(input())

#input some val
#a, b, c = (int(i) for i in input().split())
#val = [[int(i) for i in input().split()] for i in range(N)]

#input matrix
#a = [input().split() for i in range()]

x, y = (int(i) for i in input().split())
res = x + (y/2)
print(int(res))

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

int main() {
  int n;
  cin>>n;
  vi a(n);
  rep(i,n) cin>>a[i];
  int ans=0;
  map<int,int> mp;
  rep(i,n){
    mp[a[i]]++;
  }
  for(auto x:mp){
    if(x.second>x.first){
      ans+=x.second-x.first;
    }
    if(x.second<x.first){
      ans+=x.second;
    }
  }
  cout<<ans<<endl;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> X(M);
  for (int i = 0; i < M; i++) cin >> X.at(i);
  sort(X.begin(), X.end());
  int ans = 0;
  if (N < M) {
    vector<int> Y(M-1);
    for (int i = 0; i < M-1; i++) {
      Y.at(i) = X.at(i+1)-X.at(i);
    }
    sort(Y.begin(), Y.end());
    for (int i = 0; i < M-N; i++) {
      ans += Y.at(i);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
// By Mohit Gupta
#include <bits/stdc++.h>
using namespace std;
//DEBUG 
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define printint(v) copy(begin(v), end(v), ostream_iterator<int>(cout," "))
#define printintv(s,e) copy(s,e, ostream_iterator<int>(cout," "))
#define forstl(i,v) for(auto &i: v)
#define all(v) (v).begin(), (v).end()
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for ll)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define pb push_back
#define fi first
#define se second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
#pragma GCC optimize ("-O2")
const int LIM = 5e5+5, MOD = 998244353;
int t,n,m,k,x,y;
 
 
int32_t main()
{
    IOS;
    string str;
    cin>>str;
    if(str=="ABC") cout<<"ARC"<<ln;
    else cout<<"ABC"<<ln;
}


Measured memory_bytes: 3540
import scala.io.StdIn

object Main extends App {

  // 1 2 3 4  5  6
  // 1 3 6 10 15 21
  val a = StdIn.readLine().split(" ").map(_.toInt)
  val index = a(1) - a(0)
  val r = (1 to index).sum
  println(r - a(1))
}


Measured memory_bytes: 25520
#include<stdio.h>

int main(void){
    
    int a, b, c;
    int num = 0;
    int i;
    
    
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    for(i = a; i <= b; i++){
        if((c % i) == 0) num++;
    }
    
    printf("%d\n", num);
    
    return 0;
}


Measured memory_bytes: 2104
s=input()
n=len(s)

ans=1

for i in range(int((n-1)/2)):
    if s[i]==s[int((n-1)/2)-1-i]:
        continue
    else:
        ans=0


for i in range(int((n+3)/2),n):
    if s[i]==s[n-1-i]:
        continue
    else:
        ans=0


for i in range(int((n-1)/2)):
    if s[i]==s[n-1-i]:
        continue
    else:
        ans=0
        break



if ans==1:
    print("Yes")
if ans==0:
    print("No")

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

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int q = Integer.parseInt(sc.next());
        
        int[] point = new int[n+1];
        Arrays.fill(point, k-q);
        for(int i = 0; i < q; i++){
            point[Integer.parseInt(sc.next())]++;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++){
            if(point[i] > 0){
                sb.append("Yes").append(System.lineSeparator());
            }else{
                sb.append("No").append(System.lineSeparator());
            }
        }
        
        System.out.println(sb);
    }
}

Measured memory_bytes: 48412
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF INT_MAX
#define LLINF LLONG_MAX
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007
#define MODB  998244353 

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (T& x: vec) { is >> x; }
    return is;
}

int main() {
	ll ans = 0;
	ll tmp;
	//int n; cin >> n;
	string s; cin >> s;
	if (s[s.size()-1]=='s') cout << s + "es" << endl;
	else cout << s+"s" << endl;
	
	//cout << ans << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
#include<numeric>
#include<complex>
#include<ctype.h>

using namespace std;
typedef long long ll;

#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 p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void pV(vector<ll> A){
    cout << "[vector]" << endl;
    for(int i=0; i<A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    // input
    int N, M;
    cin >> N >> M;

    vector<ll> devisorList;

    // Mの約数を求める & 答えにならないものは入れない
    ll sqrtM = sqrt(M);
    ll M_N = M / N;
    FOR(i, 1, sqrtM+1){
        if(M % i == 0){
            ll yaku0 = i;
            if(yaku0 <= M_N){
                devisorList.push_back(yaku0);
            }

            ll yaku1 = M / i;
            if(yaku1 <= M_N){
                devisorList.push_back(yaku1);
            }
        }
    }

    sort(ALL(devisorList));

    ll len = devisorList.size();
    p(devisorList[len-1]);
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct Node {
    int sx, tx, sy, ty;
    Node() { sx = inf; tx = -inf; sy = inf; ty = -inf; }
    Node(int _sx, int _tx, int _sy, int _ty) { sx = _sx, tx = _tx, sy = _sy, ty = _ty; }
};
using V = Node;
#define def Node()
template<int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { 
        return Node(min(l.sx, r.sx), max(l.tx, r.tx), min(l.sy, r.sy), max(l.ty, r.ty));
    };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2);
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





int N, d;
tuple<int, int, int> points[201010];
int bv[201010];
SegTree<1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> d;
    rep(i, 0, N) {
        int x, y, b; cin >> x >> y >> b;
        points[i] = make_tuple(b, x, y);
        bv[i] = b;
    }
    sort(points, points + N);
    sort(bv, bv + N);

    rep(i, 0, N) {
        int x, y, b;
        tie(b, x, y) = points[i];
        st.update(i, Node(x, x, y, y));
    }
    
    ll ans = 0;
    rep(i, 0, N) {
        int L = i;
        int R = upper_bound(bv, bv + N, bv[i] + d) - bv;

        auto no = st.get(L, R);

        ll sx = no.sx;
        ll tx = no.tx;
        ll sy = no.sy;
        ll ty = no.ty;
        chmax(ans, (tx - sx) * (ty - sy));
    }
    cout << ans << endl;
}



Measured memory_bytes: 14212
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++){
    cin >> a[i];
  }
  vector<int> b(n);
  for (int i=0; i<n; i++){
    if (a[i]<0) b[i] = (-1)*a[i];
    else b[i]=a[i];
  }
  int mc=0;
  long long int ac=0;
  for (int i=0; i<n; i++) if(a[i]<0) mc++;
  if (mc%2==0){
    for (int i; i<n; i++){
      ac += b[i];
    }
  }
  else{
    int m;
    m=b[0];
    for (int i=1; i<n; i++){
      m=min(m,b[i]);
    }
    for (int i; i<n; i++){
      ac += b[i];
    }
    ac=ac-2*m;
  }
  cout << ac << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i< (n); i++)
#define REP(i,n) for (int i = 1; i<= (n); i++)
const int INF = 1000000007;
using ll = long long;
using namespace std;

int main() {
    string n;
    cin >> n;
    if (n[n.length()-1] == '2' || n[n.length()-1] == '4' || n[n.length()-1] == '5' || n[n.length()-1] == '7' || n[n.length()-1] == '9') {
        cout << "hon" << endl;
    } else if (n[n.length()-1] == '0' || n[n.length()-1] == '1' || n[n.length()-1] == '6' || n[n.length()-1] == '8'){
        cout << "pon" << endl;
    } else {
        cout << "bon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3568
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

#define mod 1000000007

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

long long N,ans,now,previous;//prev: 0:tate,1:yoko
string s1,s2;

int main(){
    cin>>N>>s1>>s2;
    if(s1[0]==s2[0]){
        ans=3;
        now=1;
        previous=0;
    }//tate
    else{
        ans=6;
        now=2;
        previous=1;
    }//yoko
    while(now<N){
        if(s1[now]==s2[now]){
            now+=1;
            if(previous==0){
                ans=(ans*2)%mod;
            }//tatetate
            else{
                ans=(ans*1)%mod;
            }//yokotate
            previous=0;
        }
        else{
            now+=2;
            if(previous==0){
                ans=(ans*2)%mod;
            }//tateyoko
            else{
                ans=(ans*3)%mod;
            }//yokoyoko
            previous=1;
        }
    }
    out(ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s,t;cin>>s>>t;
  print(t+s);
  return 0;
}

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

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define le(x) (int) x.length()
#define rsz resize

using namespace std;
typedef vector <int> vi;
typedef vector <vector <int> > vii;
typedef pair <int, int> pii;
typedef queue <int> qi;
typedef double db;
typedef long long ll;
typedef long double ld;
 
const long double PI=3.141592653589793238462643383279502884;
const long long PRIME1=1e9+787;
 
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll minll(ll a,ll b) {return a<=b?a:b;}
ll maxll(ll a,ll b) {return a>=b?a:b;}

int main () {
    fast;
    int x;
    cin>>x;
    if (x<600) {
        cout<<8;
        return 0;
    }
    if (x<800) {
        cout<<7;
        return 0;
    }
    if (x<1000) {
        cout<<6;
        return 0;
    }
    if (x<1200) {
        cout<<5;
        return 0;
    }
    if (x<1400) {
        cout<<4;
        return 0;
    }
    if (x<1600) {
        cout<<3;
        return 0;
    }
    if (x<1800) {
        cout<<2;
        return 0;
    }
    if (x<2000) {
        cout<<1;
        return 0;
    }
    return 0;
}
 
 


Measured memory_bytes: 3632
N = int(input())
Wlist = list(map(int,input().split()))
total = sum(Wlist)
zenhan,zenhan1 = 0,0
kouhan,kouhan1 = 0,0
for i in range(N):
  if zenhan <= total/2:#仮に足したものが全体の半分の値以下か
    # s1 >= s2
    zenhan = zenhan + Wlist[i]
  else:
    # s1 >= s2
    kouhan = sum(Wlist[i::])
    #print(zenhan)
    #print(kouhan)
    # s1 < s2
    zenhan1 = zenhan - Wlist[i-1]
    kouhan1 = sum(Wlist[i-1::])
    #print(zenhan1)
    #print(kouhan1)
    break
abs0 = abs(zenhan - kouhan)
abs1 = abs(zenhan1 - kouhan1)
print([abs1,abs0][abs0 < abs1])

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

int main(){
    long long n;
    cin>>n;
    long long arr[n];
    long long sum[n+1];
    sum[0]=0;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        sum[i+1]=arr[i]+sum[i];
    }
    long long ans=0;
    long long mod=1e9+7;
    for(int i=0; i<n; i++){
        // cout<<arr[i]<<" "<<sum[n]<<" "<<sum[i+1]<<endl;
        ans=(ans%mod+((arr[i]%mod)*((sum[n]-sum[i+1])%mod))%mod)%mod;
    }
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6708
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    d = defaultdict(int)
    for _ in range(N):
        a, b = map(int, readline().split())
        d[a] += b
    A = sorted(d.items(), key=lambda x:x[0])
    count = 0
    for key, value in A:
        count += value
        if count>=K:
            print(key)
            break
if __name__ == '__main__':
    main()


Measured memory_bytes: 21356