akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdint>
#include <vector>
#include <utility>

std::vector<std::vector<uint32_t>> m;
std::vector<uint32_t> mI;

void input() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	uint32_t n;
	std::cin >> n;
	m.resize(n);
	for (auto &v : m) {
		v.resize(n - 1);
		for (uint32_t &i : v) {
			std::cin >> i;
			i--;
		}
	}
}

bool can_play_next(uint32_t a) {
	if (mI[a] >= m[a].size()) {
		return false;
	}
	uint32_t b = m[a][mI[a]];
	if (mI[b] >= m[b].size()) {
		return false;
	}
	return (m[a][mI[a]] == b) && (m[b][mI[b]] == a);
}

int32_t solve() {
	mI = std::vector<uint32_t>(m.size(), 0);
	std::vector<std::pair<uint32_t, uint32_t>> cur;
	std::vector<std::pair<uint32_t, uint32_t>> next;

	for (uint32_t i = 0;i < m.size();i++) {
		if ((m[i][0] < i) && (can_play_next(i))) {
			next.push_back({i, m[i][mI[i]]});
		}
	}
	uint32_t ans = 0;
	while (!next.empty()) {
		ans++;
		std::swap(next, cur);
		next.clear();

		for (const auto &p : cur) {
			mI[p.first]++;
			mI[p.second]++;
			if (can_play_next(p.first)) {
				next.push_back({p.first, m[p.first][mI[p.first]]});
			}
			if (can_play_next(p.second)) {
				next.push_back({p.second, m[p.second][mI[p.second]]});
			}
		}
	}

	for (uint32_t i : mI) {
		if (i != m[0].size()) {
			return -1;
		}
	}
	return ans;
}

int main() {
	input();
	std::cout << solve() << "\n";
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string A;
  cin >> A;
  if (A=="A"){
    cout << "A" << endl;
  }
  else if (A=="B"){
    cout << "A" << endl;
  }
  else if (A=="C"){
    cout << "A" << endl;
  }
  else if (A=="D"){
    cout << "A" << endl;
  }
  else if (A=="E"){
    cout << "A" << endl;
  }
  else if (A=="F"){
    cout << "A" << endl;
  }
  else if (A=="G"){
    cout << "A" << endl;
  }
  else if (A=="H"){
    cout << "A" << endl;
  }
  else if (A=="I"){
    cout << "A" << endl;
  }
  else if (A=="J"){
    cout << "A" << endl;
  }
  else if (A=="K"){
    cout << "A" << endl;
  }
  else if (A=="L"){
    cout << "A" << endl;
  }
  else if (A=="M"){
    cout << "A" << endl;
  }
  else if (A=="N"){
    cout << "A" << endl;
  }
  else if (A=="O"){
    cout << "A" << endl;
  }
  else if (A=="P"){
    cout << "A" << endl;
  }
  else if (A=="Q"){
    cout << "A" << endl;
  }
  else if (A=="R"){
    cout << "A" << endl;
  }
  else if (A=="S"){
    cout << "A" << endl;
  }
  else if (A=="T"){
    cout << "A" << endl;
  }
  else if (A=="U"){
    cout << "A" << endl;
  }
  else if (A=="W"){
    cout << "A" << endl;
  }
  else if (A=="X"){
    cout << "A" << endl;
  }
  else if (A=="Y"){
    cout << "A" << endl;
  }
  else if (A=="Z"){
    cout << "A" << endl;
  }
  else if (A=="V"){
    cout << "A" << endl;
  }
  else{
    cout << "a" << endl;
  }
}

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


int main() {
    int n,m,l,r,left,right;
    cin >> n >> m;
    int a[n];
    rep(i,m){
        if(i == 0)cin >> left >> right;
        else{
            cin >> l >> r;
            left = max(left,l);
            right = min(right,r);
            if (left > right){
                cout << 0 << endl;
                exit(0);
            }
            }
    }
    cout << right-left+1 << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
N, A, B, C = map(int, input().split())
S = [input().strip("\n").replace("A", "0").replace("B", "1").replace("C", "2") for _ in range(N)]
Ans = [None] * N

def search(i, num):
    if i == N:
        if min(num) >= 0: return True
        else: return False
    if min(num) < 0: return False
    L = [num[0], num[1], num[2]]
    f = S[i][0]
    s = S[i][1]
    L[int(f)] += 1
    L[int(s)] -= 1
    if search(i+1, L):
        Ans[i] = f
        return True
    L[int(f)] -= 2
    L[int(s)] += 2
    if search(i+1, L):
        Ans[i] = s
        return True
    return False

def solve():
    if search(0, [A, B, C]):
        print("Yes")
        for i, a in enumerate(Ans):
            if a == "0": print("A")
            elif a == "1": print("B")
            else: print("C")
    else: print("No")
    #print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 120232
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <string>

int main()
{
  std::vector<int> As;
  int n;
  std::cin >> n;
  for (int i=0; i<n; ++i)
    {
      int tmp;
      std::cin >> tmp;
      As.push_back(tmp);
    }
  std::sort(As.begin(), As.end());

  std::string ans = "YES";
  for (int i=0; i<n-1; ++i)
    {
      if (As[i] == As[i+1]) ans = "NO";
    }
  std::cout << ans << std::endl;
}


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

int main(){
    int H,W;
    cin >> H >> W;
    int N;
    cin >> N;
    int A[H+2][W+2];
    int a;
    int from = 0;
    int to = 0;
    for(int i = 1; i <= N;i++){
        from = to;
        cin >> a;
        to += a;
        for(int j = from; j < to;j++){
            
            A[j/W][j%W] = i;
            //else A[j/W][N-j%W - 1] = i;
            //cout << N-j%W - 1 << endl;
        }

    }
    
    for(int i = 0; i < H;i++){
        for(int j = 0; j < W;j++){
            if(i%2==0){
                if(j == W-1)cout << A[i][j];
                else cout << A[i][j] <<" ";
            }else{
                if(j == W-1)cout << A[i][W-j-1];
                else cout << A[i][W-j-1] <<" ";
            }
        }
        cout << endl;
    }
}



Measured memory_bytes: 384
import java.util.*;
public class Main{
  public static void main(String[] args){
  	Scanner sc = new Scanner(System.in);
    int[] nums = new int[5];
    for(int i = 0;i < 5;i++){
      nums[i] = sc.nextInt();
    }
    int tail = Integer.MAX_VALUE;
    int min = 0;
    for(int j = 0;j < nums.length;j++){
      	int temp = nums[j] % 10;
    	if(temp != 0 && tail > temp){
        	tail = temp;
          	min = j;
        }
    }
    int sum = 0;
    for(int j = 0;j < nums.length;j++){
    	if(j != min){
          if(nums[j] % 10 == 0){
             sum += nums[j];
          }else{
            sum += (nums[j] / 10) *10 + 10;
          }
        }
    }
    System.out.println(sum + nums[min]);
  }
}

Measured memory_bytes: 27040
A, B, C, X, Y = map(int, input().split())
cntA = 0
cntB = 0
cntC = 0
value = 0
if 2*C<=A+B:
    #Cで買いそろえた方が安いので
    #(max(X, Y)-abs(X-Y))*2枚は買うことになる
    Cmaisu = (max(X, Y)-abs(X-Y))*2
    value += C * Cmaisu
    if (2*C<=A and X>Y) or (2*C<=B and X<Y):
        #abs(X-Y)枚についても2Cが安けりゃCで買う
        value += C * abs(X-Y) * 2
    else:
        if X>Y:
            value += A*(X-Y)
        else:
            value += B*(Y-X)
else:
    value += A*X+B*Y
print(value)

Measured memory_bytes: 61940
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

bit=[ 0 for _ in range(N+1) ]

#BIT 関数は全て1-indexed
def add(a,w):
    while a<=N:
        bit[a]+=w
        a+=a&-a

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret

#区間[l,r]に一律wを加える
def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)

#a番目のモンスターの体力を取得
def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  #区間に対する更新ができるBITを作成するために、値の差分をBITに持つ
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    #モンスターの体力がゼロ以下だったら何もしない
        pass
    else:
        x=X[i]
        pos=bisect_right(X,x+2*D)-1 #攻撃範囲の一番右側を二分探索で決定
        if h%A==0:   #hがAで割り切れる場合
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   #hをAで割って余りが出る場合は攻撃回数を+１する
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans


Measured memory_bytes: 75676
import java.util.Scanner;

public class Main {
    
    public static void main (String... args) {
        
        Scanner scanner = new Scanner(System.in);
        
        String[] nm = scanner.nextLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        
        int[][] matrixA = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] line = scanner.nextLine().split(" ");
            
            for (int j = 0; j < m; j++) {
                matrixA[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        int[] matrixB = new int[m];
        for (int i = 0; i < m; i++) {
            matrixB[i] = Integer.parseInt(scanner.nextLine());
        }
        
        calcMatrix(matrixA, matrixB, n, m);
    }
    
    private static void calcMatrix(int[][] a, int[] b, int n, int m) {
        for (int i=0; i < n; i++) {
            int sum = 0;
            for (int j=0; j<m; j++) {
                sum += a[i][j] * b[j];
            }
            System.out.println(String.format("%d", sum));
        }
    }
}


Measured memory_bytes: 30288
#include<bits/stdc++.h>
#define INF 2000000000
#define int long long int
#define MOD 1000000007
#define pb push_back
#define cin1(n) (cin >> n)
#define cin2(a,b) (cin >> a >> b)
#define cin3(a,b,c) (cin >> a >> b >> c)
#define cout(n) (cout << n << endl)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fr first 
#define sc second 
#define EPS (1e-10)

using namespace std;

typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector<pair<int,int>> vpii;
typedef vector<string> vs;
typedef vector<vector<string>> vss;
typedef pair<int,int> pii;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
int a,b;
int p,q;


signed main() {
	cin1(n);

	int ans = 0;
	int i = 0;
	while(ans <= n) {
		ans = pow(2,i);
		i++;
	}
	cout(ans/2);

	return 0;
}





Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
const ll mod=20180623;
int main(){
    int n,s[200],ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int z=j+1;z<n;z++){
                if(s[i]+s[j]>s[z]&&s[i]!=s[j]&&s[i]!=s[z]&&s[j]!=s[z])
                    ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3624
// AtCoder :: Beginner Contest 177 :: A - Don't be late 
// https://atcoder.jp/contests/abc177/tasks/abc177_a

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int D, T, S;
    cin >> D >> T >> S;
    if (T * S >= D) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return EXIT_SUCCESS;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
main(){
  int n,x;
  cin>>n>>x;
  vector<int> l(n);
  for(auto& i:l)cin>>i;
  for(int i=1;i<n;++i)l[i]+=l[i-1];
  int r=upper_bound(l.begin(),l.end(),x)-l.begin()+1;
  cout<<r;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]

D = [C[i][0] for i in range(N)]

CNT_A = 0
CNT_B = 0
SUM = 0

C.sort(key=lambda x:x[0])

for i in range(N):
    if C[i][1] < M - CNT_B:
        SUM = SUM + C[i][0] * C[i][1]
        CNT_B = CNT_B + C[i][1]
    else:
        SUM = SUM + C[i][0] * max(0, M - CNT_B)
        CNT_B = CNT_B +  max(0, M - CNT_B)

print(SUM)

Measured memory_bytes: 29832
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) 998244353;
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << setiosflags(ios::fixed);
    int n, k;
    cin >> n >> k;
    int cnt = 0;

    rep(i, n) {
        int h;
        cin >> h;
        if (h >= k) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,t;
int a[100005],mx[100005];
int profits,ans=0;
int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	mx[n]=a[n];
	for(int i=n-1;i>=0;i--)
	{
		mx[i]=max(mx[i+1],a[i]);
	}
	for(int i=1;i<=n;++i)
	{
		if(profits<mx[i]-a[i])
		{
			profits=mx[i]-a[i];
			ans=1;
		}
		else if(profits==mx[i]-a[i])
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define INF LLONG_MAX

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  
  int n;
  cin >> n;
  
  vector<int> a(n);
  int maxA = 0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    maxA = max(maxA,a[i]);
  }
  
  int closestVal = 0;
  double halfMax = maxA/2.0;
  double minDist = (double)maxA;
  for(int i=0;i<n;i++){
    if(a[i]==maxA) continue;
    if(abs(halfMax-(double)a[i])<minDist){
      minDist = abs(halfMax-(double)a[i]);
      closestVal = a[i];
    }
  }

  cout << maxA << " " << closestVal << endl;
  return 0;
}



Measured memory_bytes: 3812
#include <iostream>

using namespace std;
const int MAXN = 1e5 + 10;
int n, m;

int l[MAXN], r[MAXN];
int range[MAXN];

void solve() {
  for (int i=0;i<m;i++) {
    range[l[i]]++;
    range[r[i] + 1]--;
  }
  for (int i=1;i<=n;i++) {
    range[i] += range[i-1];
  }
  int cnt = 0;
  for (int i=0;i<=n;i++) {
    if (range[i] == m) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

int main() {
  cin >> n >> m;
  for (int i=0;i<m;i++) {
    cin >> l[i] >> r[i];
  }
  solve();
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 62;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  vector<ll> b(n, 0);
  rep(i, n) {
    if(i%2==0) b[0] += a[i];
    else b[0] -= a[i];
  }
  for(int i = n-1; i > 0; --i) {
    b[i] = 2* a[i] - b[(i+1)%n];
  }
  line_out(b);
}


Measured memory_bytes: 3712
from math import floor,ceil
import fractions
import collections
import itertools
from collections import deque
A,B,N=map(int,input().split())

piv=B/A  #基本数

#for i in range(0,30):
#    print(A,i,B,floor(A*i/B)-A*floor(i/B))

#A<=Bなら
#0,0,.. 1,1,.. ... (A-1),(A-1),...が
#先頭から(B%A)の数字まではceil(piv)こ、あとはfloor(piv)こ

cnt=0
#print(ceil(piv)*(B%A))
if A<=B:
    if N>=B-1:
        print(A-1)
    else:
        if ceil(piv)*(B%A)>N:
            print(floor(N/ceil(piv)))
        else:
            N=N-ceil(piv)*(B%A)
            #print(N,N//floor(piv))
            cnt=(B%A)
            print(cnt+N//floor(piv))
else:  #A>B
    l=[0]
    for i in range(1,B):
        l.append(max(l[i-1],floor(A*i/B)-A*floor(i/B)))
    #print(l)
    if N>=len(l):
        print(l[len(l)-1])
    else:
        print(l[N])





Measured memory_bytes: 73144
from collections import defaultdict, deque
import sys
input = sys.stdin.readline


def bfs(s, n, g):
    dist = [-1] * n
    dist[s] = 0
    que = deque([])
    que.append(s)
    while que:
        v = que.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)
    if -1 in dist:
        return True
    else:
        return False


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    gg = []
    for _ in range(m):
        a, b = [int(i) - 1 for i in input().split()]
        g[a].append(b)
        g[b].append(a)
        gg.append((a, b))
    ans = 0
    for a, b in gg:
        g[a].remove(b)
        g[b].remove(a)
        if bfs(0, n, g):
            ans += 1
        g[a].append(b)
        g[b].append(a)
    print(ans)
    return


if __name__ == "__main__":
    main()

Measured memory_bytes: 39536
#include <bits/stdc++.h>
#define DEBUG true
#define coutd if(DEBUG) cout
#define debugf if(DEBUG) printf
#define ff first
#define ss second
#define len(x) int(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const double PI = acos(-1);
const double EPS = 1e-9;

int main(){
	ios_base::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	k-=1;
	string st;
	cin >> st;
	st[k]='a'+st[k]-'A';
	cout << st << endl;
}



Measured memory_bytes: 256
#include<stdio.h>

#define N 100

int main()
{
  int i,j = 0,a,v,n;
  int A[N];
  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d",&A[i]);
  for(a = 0; a < n - 1 ; a++) printf("%d ",A[a]);
	
  printf("%d",A[n-1]);
	printf("\n");
   for(i = 1; i < n; i++)
    {
      v = A[i];
      j = i - 1;
      while(j >= 0 && A[j] > v){
	A[j + 1] = A[j];
	j--;
	A[j + 1] = v;
      }
      for(a = 0; a < n-1; a++){
	  printf("%d ",A[a]);
	}
      printf("%d",A[n-1]);
	printf("\n");	
      }
  return 0;
}



Measured memory_bytes: 2104
// E - Multiplication 4
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
int vpop(vector<int>& v){int x=v.back();v.pop_back();return x;}

int main(){
	int N, K; cin>>N>>K;
	vector<int> P, M;
	rep(i, N){
		int a; cin>>a;
		if(a < 0) M.push_back(a);
		else P.push_back(a);
	}

	sort(P.begin(), P.end());
	sort(M.rbegin(), M.rend());

	vector<int> p, m;
	while(int(p.size() + m.size()) < K){
		if(P.size() > 0 && M.size() <= 0) p.push_back(vpop(P));
		else if(P.size() <= 0 && M.size() > 0) m.push_back(vpop(M));
		else if(P.back() < -M.back()) m.push_back(vpop(M));
		else p.push_back(vpop(P));
	}

	if(m.size()%2){
		int pM = p.size() * M.size() > 0, mP = m.size() * P.size() > 0;
		if(pM & mP){
			if(abs((ll)p.back() * P.back()) < abs((ll)m.back() * M.back())){ p.pop_back(); m.push_back(vpop(M)); }
			else{ m.pop_back(); p.push_back(vpop(P)); }
		}
		else if (pM){ p.pop_back(); m.push_back(vpop(M)); }
		else if (mP){ m.pop_back(); p.push_back(vpop(P)); }
		else{
			while(m.size() > 0) p.push_back(vpop(m));
			while(P.size() > 0) p.push_back(vpop(P));
			while(M.size() > 0) p.push_back(vpop(M));
			sort(p.begin(), p.end(), [](int x, int y){ return abs(x) < abs(y); });
			while((int)p.size() > K) p.pop_back();
		}
	}

	ll ans = 1;
	int mod = 1'000'000'007;
	for(int a:p) ans = ans * a % mod;
	for(int a:m) ans = ans * a % mod;
	cout<< (ans+mod)%mod <<endl;
}


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

using namespace std;
using ll = int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using tpi = tuple<int, int, int>;

using vqi = vector<queue<int>>;
using vpi = vector<pii>;
using bs = bitset<60>;
using vbi = vector<bs>;

ll gcd(ll a, ll b) {
    if (a < b) {
        swap(a, b);
    }

    /* ユークリッドの互除法 */
    ll r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

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

constexpr int64_t __pow_mod(int64_t n, int64_t p, int64_t mod) noexcept {
    if (p == 0) {
        return 1;
    }
    if (p % 2 == 0) {
        int64_t t = __pow_mod(n, p / 2, mod);
        return (t * t) % mod;
    }
    return (n * (__pow_mod(n, p - 1, mod) % mod)) % mod;
}

constexpr int64_t pow_mod(int64_t n, int64_t p, int64_t mod) noexcept {
    int64_t res = __pow_mod(n, p, mod);
    if (res == 0) {
        res = mod;
    }
    return res;
}

void solve(long long N, std::vector<long long> X) {
    ll sum = 0;
    for (ll item : X) {
        sum += item;
    }
    ll p1 = ceil(sum / N);
    ll loss1 = 0;
    for (ll item : X) {
        loss1 += (p1 - item) * (p1 - item);
    }
    ll p2 = p1 - 1;
    ll loss2 = 0;
    for (ll item : X) {
        loss2 += (p2 - item) * (p2 - item);
    }
    ll p3 = p1 + 1;
    ll loss3 = 0;
    for (ll item : X) {
        loss3 += (p3 - item) * (p3 - item);
    }
    cout << min(loss1, min(loss2, loss3)) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
    long long N;
    std::cin >> N;
    std::vector<long long> X(N);
    for (int i = 0; i < N; i++) {
        std::cin >> X[i];
    }
    solve(N, std::move(X));
    return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  int ans = 0;
  ll calc = 0;
  while (N > 0) {
    N /= K;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }

const int MAX_N = 2000;
int n;
int l[MAX_N];

int main()
{
  fastio();

  cin >> n;
  forn(i,n) cin >> l[i];

  sort(l,l+n);

  ll ans = 0;
  forn(i,n) {
    for (int j = i+1; j < n; j++) {
      int a = lower_bound(l,l+n,l[i]+l[j]) - l - 1;
      int b = lower_bound(l,l+n,l[j]-l[i]+1) - l - 1;
      //cout << l[i] << " " << l[j] << " " << a << " " << b << endl;
      ans += a - b - 1;
      if (l[j] < 2*l[i]) ans--;
      //cout << ans <<endl;
    }
  }

  assert(ans % 3 == 0);

  cout << ans/3 << endl;

  return 0;
}


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

#define f first
#define s second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define px pair<db, db>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define input(a) for (auto& el : a) cin >> el;
#define output(a) cout << '!'; for (auto& el : a) cout << el << ' '; cout << '\n'; cout.flush();
#define sz(el) int(el.size())
#define sq(a) ((a) * (a))
#define xll bitset<128>
#define xmin(a,b) a = min(a, b)
#define xmax(a,b) a = max(a, b)
#define sun(a) sort(all(a)); a.resize(unique(all(a)) - a.begin());
/**/  /// extra
//#define forn(i,n) for (int i = 0; i < n; ++i)
//#define rforn(i,n) for (int i = n - 1; i >= 0; --i)
#define bn '\n'
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
//#define G vector<vector<pii>>
#define GVE vector<vector<edge>>
#define usi unordered_set<int>
#define usp set<pii>
/**/

using namespace std;

const int INF = 1'000'000'017;
const ll LLINF = 1'000'000'000'000'000'017LL;
const ld inf = 1.0 / 0.0;
const ld eps = 1e-9;
const int MOD = 998244353;

//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

//uniform_int_distribution<int> uid(l, r); [l, r]
//int x = uid(rng);

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    a[n] = INF;
    int cnt = 0;
    int c = 1;
    for (int i = 0; i < n; ++i) {
        if (a[i] < a[i + 1]) {
            xmax(cnt, c);
            c = 0;
        }
        ++c;
    }
    cout << max(cnt, c) - 1;
    return 0;
}


Measured memory_bytes: 640
'use strict';
process.stdin.on('data', function(chunk) {
  var inputs = chunk.toString().trim().split(' ');
  var a = Number(inputs[0]);
  var b = Number(inputs[1]);
 if (b-a >  0){
 	console.log('a < b')
 }
 	else if(a - b >0 ){
 		console.log ('a > b')
 	}
 	else {
 		console.log('a == b')
 	};

});
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 15560
using System;

namespace abca141
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            if(s=="Sunny")
            Console.WriteLine("Cloudy");
            if (s == "Cloudy")
                Console.WriteLine("Rainy");
            if (s == "Rainy")
                Console.WriteLine("Sunny");
        }
    }
}


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

#define N 100010
#define MAX 1000000000000000000

int main (void)
{
    int a;

    scanf("%d", &a);

    printf("%d", a +(a * a) + (a * a * a));

    return 0;
}


Measured memory_bytes: 1736
#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define LOCAL 1

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define dbg(...) cout<<#__VA_ARGS__ ": ["; for(auto e: __VA_ARGS__){cout<<e<<", ";} cout<<"]\n"
#define dbg1(...) cout<<#__VA_ARGS__ " "<< __VA_ARGS__ 
#else
#define dbg(...) 1;
#define dbg1(...) 1;
#endif

typedef long long ll;
typedef unsigned long long ull;
constexpr int R=5e6+69, INF=2e9+6969;

int h,w,k;
ll ans;
struct tab
{
	char t[10][10];
};
tab T,pusta;
tab color(int row, int col, tab A)
{
	for(int i=0;i<h;++i)
	{
		if(row&(1<<i))
		{
			for(int j=0;j<w;++j)
			{
				A.t[i][j]='&';
			}
		}
	}
	for(int i=0;i<w;++i)
	{
		if(col&(1<<i))
		{
			for(int j=0;j<h;++j)
			{
				A.t[j][i]='&';
			}
		}
	}
	return A;
}
ll ile(tab A)
{
	ll wyn = 0;
	for(int i=0;i<h;++i)
	{
		for(int j=0;j<w;++j)
		{
			if(A.t[i][j]=='#') wyn++;
		}
	}
	return wyn;
}
void show(tab A)
{
	for(int i=0;i<h;++i)
	{
		for(int j=0;j<w;++j)
		{
			printf("%c ", A.t[i][j]);
		}
		puts("");
	}
}
int main()
{
	
	scanf("%d%d%d", &h, &w, &k);
	for(int i=0;i<h;++i)
	{
		for(int j=0;j<w;++j)
		{
			cin >> T.t[i][j];
		}
	}
	//  show(color(0,0,T));
	//  return 0;
	for(int i=0;i<(1<<h);++i)
	{
		for(int j=0;j<(1<<w);++j)
		{
			ll cur = ile(color(i,j,T));
			if(cur == k)
			{
				//  printf("%d %d\n", i,j);
				ans++;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using sl = set<ll>;

const ll MAX_VAL = 3234566667;
vl ans;
sl S;

void dfs(ll x) {
    if (x > MAX_VAL) return;
    S.insert(x);
    ll nx = x * 10;
    for (int i = -1; i <= 1; i++) {
        dfs(nx + min(9LL, max(0LL, x%10 + i)));
    }
}

int main() {
    int K; cin >> K;
    for (int i = 1; i < 10; ++i) {
        dfs(i);
    }
    ans = vl(S.begin(), S.end());
    cout << ans[K-1] << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <stdio.h>

int     main(void)
{
    int     i, j;
    int     h, w;
    
    while (scanf("%d%d\n", &h, &w) == 2 && (h|w) != 0)
    {
        i = 0;
        while (i < h)
        {
            j = 0;
            while (j < w)
            {
                if (h + w == 0)
                    break;
                printf("#");
                j++;
            }
            printf("\n");
            i++;
        }
        printf("\n");
    }
    return (0);
}



Measured memory_bytes: 2040
import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))


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

signed main (){
	int n,wmax;
	
	cin>>n>>wmax;
	int dp[n+1][wmax+1]={0};
	int weight[n+1];
	int value[n+1];
	for (int i=0;i<n;i++)
	cin>>weight[i]>>value[i];
	for (int i=0;i<=n;i++){
		for (int j=0;j<=wmax;j++){
			if (i==0||j==0) dp[i][j]=0;
			else if (weight[i-1]<=j){
				int a=dp[i-1][j-weight[i-1]]+value[i-1];
				int b=dp[i-1][j];
				//cout<<a<<"    "<<b;
				dp[i][j]=max(a,b);
			}
			else
			dp[i][j]=dp[i-1][j];
		}
		//cout<<endl;
	}
	cout<<dp[n][wmax]<<endl;
				
}


Measured memory_bytes: 79104
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,d,i,j,k,n,m,y,l,r,ans = 0;
	string	s;
	cin >> n >> d;
	vector<vector<ll>>	x(n , vector<ll>(d));

	for(i=0;i<n;i++) for(j=0;j<d;j++) cin >> x[i][j];

	for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) {
		l = 0;
		for(k=0;k<d;k++) {
			l += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
		}
		m = sqrt(l) + 2;
		for(r=1;r<=m;r++) {
			if (r*r == l) {
				ans++;
				break;
			}
		}
	}

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


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if(max(A,C) - min(A,C) <= D){
    cout << "Yes" << endl;
  }
  
  else if(max(A,B) - min(A,B) <= D && max(B,C) - min(B,C) < D){
  cout << "Yes" << endl;
  }
else{
cout << "No" << endl;
}
}


Measured memory_bytes: 3584
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define rt0 return 0;
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

signed main() {
    int n, k; cin >>n >>k;
    vll p(n);
    rep(i, n) cin >>p[i], ++p[i];

    vll s(n+1, 0);
    rep(i, n) s[i+1] = s[i] + p[i];

    ll res = 0;
    for (int i = 0; i+k <= n; ++i) res = max(res, s[i+k] - s[i]);
    cout << fixed << setprecision(10) << (double)(res)/2 << endl;
}


Measured memory_bytes: 6356
#include<iostream>
using namespace std;
#define absi(x) ((x)<0?-1*(x):(x))
#define strt(i,j) (absi(s[i]-s[j]))
int s[100002];
int main()
{
	int n,f,i,t=0;
	cin>>n;
	for(f=0;f<n;f++)cin>>s[f];
	for(f=0;f<(n-1);f++)t+=strt(f,f+1);
	t+=absi(s[0]);
	t+=absi(s[n-1]);
	cout<<(t-absi(s[0])-strt(0,1)+absi(s[1]))<<endl;
	for(i=1;i<(n-1);i++)
	cout<<(t-strt(i-1,i)-strt(i,i+1)+strt(i-1,i+1))<<endl;
	cout<<(t-absi(s[n-1])-strt(n-2,n-1)+absi(s[n-2]))<<endl;
	return 0;
}

Measured memory_bytes: 1664
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		char[] input=new Scanner(System.in).nextLine().toCharArray();
		int x=0;
		for(int i=0;i<input.length;i++) {
			if(input[i]=='1') {
				x++;
			}
		}
		System.out.println(x);
	}
}

Measured memory_bytes: 22996
# coding: utf-8
# Your code here!
# B問題
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(N):
    count = 0
    l = list(map(int,input().split()))
    for a in range(M):
        count+= B[a] * l[a]
        #print(count)
    if count + C > 0:
        ans+=1
print(ans)

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

struct edge {
  int from;
  int to;
  ll cost;
  edge(int f, int t, ll c): from(f), to(t), cost(c) {};
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll l; cin >> l;
  int r = log2(l);
  int n = r+1;
  vector<edge> E;
  rep(i, r) {
    E.push_back({i, i+1, 0});
    E.push_back({i, i+1, 1LL<<i});
  }
  for(int i=n-2; i>=0; i--) {
    if(l-(1LL<<i) >= 1LL<<r) {
      E.push_back({i, n-1, l-(1LL<<i)});
      l -= (1LL<<i);
    }
  }
  cout << n << ' ' << E.size() << "\n";
  for(auto e: E) cout << e.from+1 << ' ' << e.to+1 << ' ' << e.cost << "\n";
  return 0;
}


Measured memory_bytes: 3712
import heapq

def solve():
  n = int(raw_input())
  ar = raw_input().split(' ')
  iar = [int(s) for s in ar]
  
  early = iar[:n]
  mid = iar[n:-n]
  late = iar[-n:]

  heapq.heapify(early)
  tmpsum = sum(early)
  esums = [tmpsum]
  for i in range(n):
    heapq.heappush(early, mid[i])
    emin = heapq.heappop(early)
    tmpsum += (mid[i] - emin)
    esums.append(tmpsum)
  #print esums
 
  lateinv = [-x for x in late]
  heapq.heapify(lateinv)
  tmpsum = sum(lateinv)
  lsums = [tmpsum]
  for i in range(1,n+1):
    heapq.heappush(lateinv, -mid[-i])
    lmax = heapq.heappop(lateinv)
    tmpsum += (-mid[-i] - lmax)
    lsums.append(tmpsum)
  #print lsums
  
  best = float("-inf")
  for i in range(n+1):
    score = esums[i] + lsums[n-i]
    #print 'i=',i,',n-i=',n-i,',esums[i]=',esums[i],',lsums[n-i]=',lsums[n-i],'score=',score
    if(best < score) : best = score
  return best

if __name__ == '__main__' :
  print solve()

Measured memory_bytes: 45172
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

const int mod = 1000000007;
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}



int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    if((b-a)%2==0){
        cout << (b-a)/2 << endl;
        return 0;
    }
    ll fw = n-a+n-b;
    ll bc = a+b-2;
    cout << (min(fw,bc)+1)/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_N 20000
#define MAX_M 16

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int ans, ans1, ans2, ans3;
int a, b, c;

int main(){
	bool f = 1;
	while (cin >> a >> b >> c){
		if (f == 0)continue;
		if (a > b)swap(a, b);
		if (b > c)swap(b, c);
		if (a + b > c&&b + c > a&&c + a > b){
			ans++;
			if (a*a + b*b == c*c){
				ans1++;
			}
			else if (a*a + b*b > c*c){
				ans2++;
			}
			else ans3++;
		}
		else f = 0;
	}
	cout << ans << " " << ans1 << " " << ans2 << " " << ans3 << endl;
}

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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define debug(i) cout << i << endl;
#define debugarr(a) for(auto i : a) cout << i << " ";

#define lli long long
#define vi vector<int>
#define vli vector<li>
#define vlli vector<lli>
#define pi pair<int,int>
#define pli pair<li, li>
#define vpi vector<pi>

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);

    string code;
    cin >> code;

    bool ok = true;

    for(int i = 0; i < code.size() - 1; i++) {
        if(code[i] == code[i+1]) ok = false;
    }

    if(ok) cout << "Good" << endl;
    else cout << "Bad" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const int mod = 1000000007;
const int mod998 = 998244353;

int N;
ll x, y, X[2], Y[2], res, MIN, MAX;
pair<ll, ll>xy[200000];
int main() {
	cin >> N;
	X[0] = Y[0] = 0xE869120E869120;
	for (int i = 0; i < N; ++i) {
		cin >> x >> y;
		if (x > y)
			swap(x, y);
		X[0] = min(X[0], x);
		X[1] = max(X[1], x);
		Y[0] = min(Y[0], y);
		Y[1] = max(Y[1], y);
		xy[i] = mkp(x, y);
	}
	res = (X[1] - X[0])*(Y[1] - Y[0]);
	sort(xy, xy + N);
	MIN = intmax;
	MAX = X[1];
	for (int i = 1; i < N; ++i) {
		MAX = max(MAX, xy[i - 1].second);
		MIN = min(MIN, xy[i - 1].second);
		res = min(res, (Y[1] - X[0])*(MAX - min(xy[i].first, MIN)));
	}
	cout << res << endl;
	return 0;
}

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

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

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        if(tmp % 2 == 0){
        if(tmp % 3 != 0 && tmp % 5 != 0){
            cout << "DENIED" << endl;
            return 0;
        }}
    }   

    cout << "APPROVED" << endl;

    return 0;
}

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

inline void cmin(int&x, const int&y) {if(x > y) x = y;}
inline void cmax(int&x, const int&y) {if(x < y) x = y;}
inline void cmin(ll&x, const ll&y) {if(x > y) x = y;}

inline void read(int&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}

const int N = 201000, Inf = 1e9;

struct node {
	int x, y;
	friend inline bool operator < (const node&A,const node&B)
		{return A.x != B.x ? A.x < B.x : A.y  < B.y;}
}p[N];

int min_x, min_y;
int max_x, max_y;
int n;

int main(){
	read(n);
	min_x = min_y = Inf;
	max_x = max_y = 0;
	for(int i=1,x,y;i<=n;++i) {
		read(x), read(y);
		if(x > y) swap(x, y);
		p[i].x = x, p[i].y = y;
		cmin(min_x, x), cmax(max_x, x);
		cmin(min_y, y), cmax(max_y, y);
	}
	sort(p+1,p+n+1);
	ll ans = (ll)(max_x - min_x) * (max_y - min_y);
	int mi = Inf, mx = p[n].x;
	for(int i=1;i<=n;++i){
		if(i != 1) cmin(ans, (ll)(max_y - min_x) * (mx - min(p[i].x, mi)));
		cmax(mx, p[i].y), cmin(mi, p[i].y);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



#n=int(input())
#n,m=input_list()
#a=input_list()

s=input()
ans=0
s=[i if i!="?" else "D" for i in s]
print("".join(s))

Measured memory_bytes: 28772
from collections import deque
 
N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]

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 -= 1
        y -= 1
        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

uf = UnionFind(N)
for i in range(len(hint_list)):
    uf.union(hint_list[i][0],hint_list[i][1])
    
print(-min(uf.parents))

Measured memory_bytes: 50444