akhauriyash/Code-Regression huggingface dataset:
import sys
from bisect import bisect_left

input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

cumsum = [0]
for i in range(len(B)):
    b = B[i]
    a_idx = bisect_left(A, b)
    cumsum.append(cumsum[i] + a_idx)
# print('cumsum', cumsum)

ans = 0
for i in range(len(C)):
    c = C[i]
    b_idx = bisect_left(B, c)
    ans += cumsum[b_idx]
print(ans)


Measured memory_bytes: 21600
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
    
    int a,b;
    char op;
        
        while(op!='?'){
            switch(op){
                case'+':
                cout<<a+b<<endl;
                break;
                
                case'-':
                cout<<a-b<<endl;
                break;
                
                case'*':
                cout<<a*b<<endl;
                break;
                
                case'/':
                cout<<a/b<<endl;
                break;
                
            }
            cin>>a>>op>>b;
        }
    }



Measured memory_bytes: 3084
require 'set'; require 'prime'
INF=Float::INFINITY
n = gets.chomp.to_i

ct, ca = gets.split.map(&:to_i)
(n-1).times do
  t, a = gets.split.map(&:to_i)
  l=0; r = 10**18
  mid = 0
  while l < r -1
    mid = (l + r) /2
    if ct <= t * mid && ca <= a * mid
      r = mid
    else
      l = mid
    end
  end
  if ct <= t * mid && ca <= a * mid
    mid = mid
  else
    mid = mid + 1
  end
  ct = t * mid
  ca = a * mid
  # p [ct, ca]
end

puts ct + ca


Measured memory_bytes: 2556
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for(ll i=0; i<n; i++)
#define all(v) v.begin(), v.end()
#define vec vector

/*  <<bit全探索>>
 
    for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
        bitset<ビット数> s(tmp);
    }
*/
 
/*　<<stringで読み込んだ数列を一桁ずつint型へ変換>>
 
    string str;
    int N[桁数];
 
    cin >> str;
 
    for (int i = 0; i < 桁数; ++i) {
 
        N[i] = (int)(str[i] - '0');  //str[i]　はchar型なのでchar→intへ変換
 
        //cout << N[i] << endl;  //確認のため表示
    }
*/
 
typedef long long ll;

///////////////////////////////////////////////////////////////////////////


int main() { 

    ll A, B, N;
    cin >> A >> B >> N;
    
    int f, g;

        f = floor(A * (B - 1) / B) - A * floor((B - 1) / B);

        g = floor(A * N / B) - A * floor(N / B);    
    if(B - 1 < N){
    cout << f << endl;
    }
    else{
    cout << g << endl;
    }

}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char ar[3];
  for(auto i=0;i<3;++i) cin>>ar[i];
  if(ar[0]=='R'&&ar[1]=='R'&&ar[2]=='R')
    cout<<3;
  else if((ar[0]=='R'&&ar[1]=='R')||(ar[1]=='R'&&ar[2]=='R'))
    cout<<2;
  else if(ar[0]=='R'||ar[1]=='R'||ar[2]=='R')
    cout<<1;
  else
    cout<<0;
}

Measured memory_bytes: 3636
main = do
  s <- getContents
  let v = map (map read . words) . lines $ s
  let w = map solve v
  let x = map (\x-> if x then "YES" else "NO") $ w
  mapM_ putStrLn x

solve::[Double] -> Bool
solve [xa,ya,xb,yb,xc,yc,xd,yd] =
  abs(dot u v)/len(u)/len(v) < eps
  where u = (xb-xa, yb-ya)
        v = (xd-xc, yd-yc)
        dot (a,b) (c,d) = a*c + b*d
        len (a,b) = sqrt(a^2+b^2)
        eps=1e-12

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

#define int long long
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> inline bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
struct Init {
    Init() {
        cout << fixed << setprecision(20);
    };
} init;

int N, M, C;
int A[22][22], B[22];
signed main() {
    cin >> N >> M >> C;
    for (int i = 0; i < M; i++) { cin >> B[i]; }
    for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> A[i][j]; }}
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int cur = C;
        for (int j = 0; j < M; j++) { cur += A[i][j] * B[j]; }
        ans += cur > 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    s = input()
    count = 0
    new_left = 0
    new_right = 0

    # See:
    # https://www.youtube.com/watch?v=5FOTOiV5p0U
    for si in s:
        if si == '(':
            count += 1
        else:
            count -= 1

            if count == -1:
                count = 0
                new_left += 1

    new_right = count

    print('(' * new_left + s + ')' * new_right)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        class Point {
            double x, y;
            public Point(double inX, double inY) {
                x = inX;
                y = inY;
            }
            public double getDistance(Point p2) {
                double dst;
                dst = Math.pow(this.x - p2.x, 2.0) + Math.pow(this.y - p2.y, 2.0);
                dst = Math.sqrt(dst);
                return dst;
            }
        }
        Point p1 = new Point(Double.parseDouble(scan.next()), Double.parseDouble(scan.next()));
        Point p2 = new Point(Double.parseDouble(scan.next()), Double.parseDouble(scan.next()));

        System.out.println(p1.getDistance(p2));
    }
}



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

int main() {
    int N;
    vector <int> b(9);
    vector <int> c(N);
    int cnt=0;
    int r = 0;
    
    for(int i = 0; i < 9 ;i++){
        cin >> b.at(i);
    }
    cin >> N ;

    for(int i = 0; i< N;i++){
        cin >> c.at(i);
        for(int j =0; j < 9; j++){
                if(c.at(i) == b.at(j)){
                    b.at(j) = 0;
                    cnt ++;
                }
        }
    }

    
    if(b.at(0) == 0){
        if(b.at(4) == 0){
            if(b.at(8)== 0){
                r = 1;
            }
        }
    }
    if(b.at(2) == 0){
        if(b.at(4) == 0){
            if(b.at(6)== 0){
                r = 1;
            }
        }
    }
    for(int i = 0; i< 3 ;i ++){//横のビンゴ調べる
        if(b.at(3*i) ==0){
            if(b.at(3*i+1)==0){
                if(b.at(3*i+2)==0){
                    r = 1;
                }
            }
        }
    }
    for(int i = 0; i< 3 ;i ++){//縦のビンゴ調べる
        if(b.at(i) ==0){
            if(b.at(i+3)==0){
                if(b.at(i+6)==0){
                    r = 1;
                }
            }
        }
    }

    if(r==1){
        cout <<"Yes"<<endl;
    }
    else{
        cout << "No" << endl;
    }


}


Measured memory_bytes: 384
#include<stdio.h>
int main()
{
 
int A,B;
scanf("%d\n%d",&A,&B);
if(A+B==3)
{
    printf("3\n");
}
else if(A+B==5)
{
    printf("1\n");
}
else
{
    printf("2\n");
}
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    multiset<int> ms;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ms.insert(-x);
        int tmp = x - 1;
        auto it = ms.find(-tmp);
        if (it != ms.end()) {
            ms.erase(it);
            continue;
        }
        it = ms.upper_bound(-tmp);
        if (it != ms.end()) ms.erase(it);
    }
    cout << ms.size();
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,A[200001],B[200001],C[200001];
    ll ans=0;
    cin>>n;
    rep(i,n) cin>>A[i];
    rep(i,n) cin>>B[i];
    rep(i,n-1) cin>>C[i];
    rep(i,n) ans+=B[A[i]-1];
    rep(i,n-1) if(A[i]+1==A[i+1]) ans+=C[A[i]-1];
    cout<<ans;
}

Measured memory_bytes: 2304
import heapq

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

change = []
for m in range(M):
    B, C = map(int, input().split())
    change.append((B, C))
change.sort(key=lambda x: -x[1])

change2 = []
for c in change:
    change2.extend([c[1]] * c[0])
    if len(change2) >= N:
        change2 = change2[:N]
        break


heapq.heapify(A)

for c in change2:
    x = heapq.heappop(A)
    if x >= c:
        # 先頭すでに十分大きい場合は抜ける
        heapq.heappush(A, x)
        break
    else:
        x = max(x, c)
        heapq.heappush(A, x)

print(sum(A))


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

int main()
{
	int n, a, b, sum = 0;
	cin >> n >> a >> b;
	if (n == 10000) {
		if (a == 1) sum += 10000;
		n -= 1;
	}
	for (int i = 1; i <= n; i++) {
		int c = i / 1000;
		int d = (i - c * 1000) / 100;
		int e = (i - c * 1000 - d * 100) / 10;
		int f = i - c * 1000 - d * 100 - e * 10;
		if ((a <= (c + d + e + f)) && ((c + d + e + f) <= b)) {
			sum += i;
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
      if(i == n - 1) {
        System.out.println(arr[i]);
      } else {
        System.out.print(arr[i] + " ");
      }
    }
    for(int i = 1; i < n; i++) {
      int key = arr[i];
      int j = i - 1;
      while(j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
      for(int k = 0; k < n; k++) {
        if(k == n - 1) {
          System.out.println(arr[k]);
        } else {
          System.out.print(arr[k] + " ");
        }
      }
    }
  }
}



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

int main(void){
    
  int a ,b;
  int max ,max1,max2;
  cin >> a >> b;
  
  max = a+b;
  max1 = a-b;
  max2 = a*b;

  if(max >= max1 && max >= max2){
    
    cout << max << endl;
  }

  else if(max1 >= max && max1 >= max2){
    cout << max1 << endl;
  }
  else{
    cout << max2 << endl;
  }
  return 0;
  
}


Measured memory_bytes: 256
/**
 *    author        : Sudipta Banik Trisha 
 *    created       : August 31, 2020 12:18 AM
 *    Problem Name  : C - Count Order
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/abc150/tasks/abc150_c
 *    @genarated by : ai-virtual-assistant
**/

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

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int>v(n);
    for(int i=0; i<n; i++) {
        v[i] = i+1;
    }

    vector<int>p(n),q(n);
    for(int i=0; i<n; i++) cin >> p[i];
    for(int i=0; i<n; i++) cin >> q[i];

    int cnt=0, a=0, b=0;

    do {
        cnt++;

        for(int i=0; i<n; i++) {
            if(a == 0 && v == p) a = cnt;
            if(b == 0 && v == q) b = cnt;

            if((a!=0 && b==0) || (a==0 && b!=0) ) break;
        }

    }while(next_permutation(v.begin(),v.end()));
    
    cout << abs(a-b) << endl;
    return 0 ;
}


Measured memory_bytes: 3672
#include<cstdio>
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
long long A,B,C;
long long cmin(long long x,long long y){return x<y?x:y;}
int main()
{
	scanf("%lld%lld%lld",&A,&B,&C);
	if(A&1&&B&1&&C&1)printf("%lld\n",cmin(cmin(A*B,B*C),C*A));
	else printf("0\n");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;

 
int main(){
	srand(unsigned(time(NULL)));
	char judge[20][20];
	int N;
	int ai_hand;
	int max[20];
	int max_hand_win=0;
	int out_hand;
	int max_hand;
	int ave_max=0;
	bool ave[20];
	for(int i=0;i<20;i++){
		ave[i]=0;
	}
	int out_hands[20];
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>judge[i];
		max[i]=0;
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(judge[i][j]=='o'){
				max[i]+=3;
			}
			if(judge[i][j]=='-'){
				max[i]+=1;
			}
		}
	}
	for(int i=0;i<N;i++){
		ave_max+=max[i];
		if(max_hand_win<max[i]){
			max_hand_win=max[i];
			max_hand=i;
		}
	}
	
	ave_max=ave_max/N;
	
	////
	ave_max=max_hand_win-15;
	
	////
	
	for(int i=0;i<N;i++){
		if(max[i]>ave_max){
			ave[i]=1;
		}
	}
	int count=0;
	for(int i=0;i<N;i++){
		if(ave[i]==1){
			out_hands[count]=i;
			count++;
		}
	}
	if(count==0){
		out_hands[0]=max_hand;
		count++;
	}
	
	
	for(int i=0;i<1000;i++){
		
		cout<<out_hands[rand()%count]+1<<endl;
		cin>>ai_hand;
		fflush(stdout);
		
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
//main関数にCOMinit();を忘れない

int main(){
    COMinit();
    int N,M; cin>>N>>M;
    vector<int> pcnt;
    int lim=M;
    for (int i = 2; i <=sqrt(lim) ; ++i) {
        int tmp=0;
        while(M%i==0){
            tmp++;
            M/=i;
        }
        if(tmp>0) pcnt.push_back(tmp);
    }
    if(M!=1) pcnt.push_back(1);

    ll ans=1ll;
    for(auto cnt:pcnt){
        (ans*=COM(cnt+N-1,N-1))%=MOD;
    }

    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 4992
N = int(input())
A = list(map(int,input().split()))
min1 = 1000000000
for i in range(max(A)+1):
  sum1 = 0
  for j in range(N):
    sum1 += ((i - A[j]) ** 2)
  if(sum1 < min1):
    min1 = sum1
    
print(min1)

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
using namespace std;

int N,K;
int a[101010];
int main (){
    cin >> N >> K;
    for(int i=0; i<N; i++) cin >> a[i];
    N -= K;
    int cnt = 1;
    while( N > 0) {
        N -= K - 1;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 640
//--------------------------------------------------
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,avx,avx2,popcnt,fma")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//--------------------------------------------------
#include <bits/stdc++.h>
//#include <chrono>
//#include <set>
//#include <map>
//#include <deque>
//#include <cmath>
//#include <queue>
//#include <cassert>
//#include <random>
//#include <bitset>
//#include <iomanip>
//#include <numeric>
//#include <time.h>
//#include <ctime>
//#include <string>
//#include <cstdio>
//#include <vector>
//#include <cstdlib>
//#include <iostream>
//#include <algorithm>
//#include <unordered_map>
//#include <unordered_set>
//#include <fstream>
//#include <stack>
//#include <cstring>
//--------------------------------------------------
#define forn(i, n) for(int i = 0; i < n; i++)
#define forw(i, n) for(int i = n-1; i >= 0; --i)
#define forns(i, n, s) for(int i = s; i < n; i++)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
//----------------------------------------------------
using namespace std;
//----------------------------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef vector<ll> lnum;
typedef complex<ld> comp;
//----------------------------------------------------
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;
const ll inf = 1e18;
const int base = 1e9;
const ld PI = 3.14159265358979;
//----------------------------------------------------
#define endl '\n';
//----------------------------------------------------
int n, k;
string str;
ll fact[2*1000*1000+1];
//----------------------------------------------------
unsigned int bitcount(ull val) { return __builtin_popcount(val) + __builtin_popcount(val >> 32); }

void local() {
    freopen("test.in", "r", stdin);
}

void remote() {
}

void read() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> k;
    cin >> str;
    n = str.length();
}

ll qpow(ll val, ll n){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = (res * val) % mod;
        val = (val * val) % mod;
        n >>= 1;
    }
    return res;
}

ll binomial(ll n, ll k){
    return (fact[n] * qpow(fact[n-k], mod-2) % mod) * qpow(fact[k], mod-2) % mod;
}

int main() {
#ifdef MY_DEBUG
    local();
#else
    remote();
#endif
    read();

    fact[0] = 1;
    forns(i, n+k+1,1)
        fact[i] = (fact[i-1] * i) % mod;

    ll ans = 0;
    for(int i = n+k-1; i >= n-1; i--){
        ll free = n+k-1 - i, loc = i;
        ans += (binomial(loc, n-1) * qpow(25, loc - (n-1)) % mod) * qpow(26, free) % mod;
        ans %= mod;
    }

    cout << ans << endl;

}


Measured memory_bytes: 19816
n = list(map(int, input().split()))
n.sort()
sum = 0
k1 = n[2] - n[1]
n[0] += 1
n[1] += 1
sa = n[1] - n[0]
m,d = divmod(sa,2)
if d == 1:
    sum += 2
sum += k1 + m
print(sum)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.AGC_Challenge
{
    class _001_B
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            long[] nx = ReadLongs();
            long n = nx[0];
            long x = nx[1];
            Console.WriteLine(Length(n, x));
        }

        static long Length(long n, long x)
        {
            long min = Math.Min(n - x, x);
            long max = n - min;
            long cnt = max / min;

            if (max % min == 0)
            {
                return min * 3 * cnt;
            }
            else
            {
                long margin = max % min;
                return min * 3 * cnt + Length(margin + min, min);
            }
            /*
            if (x <= n - x)
            {
                long cnt = (n - x) / x;
                if ((n - x) % x == 0)
                {
                    return x * 3 * cnt;
                }
                else
                {
                    long margin = (n - x) % x;
                    return x * 3 * cnt + Length(margin + x, x);
                }
            }
            else
            {

                long cnt = x / (n - x);
                if (x % (n - x) == 0)
                {
                    return (n - x) * 3 * cnt;
                }
                else
                {
                    long nextX = x % (n - x);
                    return (n - x) * 3 * cnt + Length(n - x + nextX, nextX);
                }
            }
            */
        }

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


Measured memory_bytes: 13140
#include <stdio.h>
int main(void){
    int i = 1;
    int n,x;
    
    scanf("%d",&n);
    for(i = 1; i <= n; i++){
        x = i;
        if (x % 3 == 0){
            printf(" %d",i);
        }
        else {
            if(x % 10 == 3){
                printf(" %d",i);
            }
            else{
                while(x != 0){
                    if(x % 10==3){
                    printf(" %d",i);
                    break;
                    }
                    x = x / 10;
                }
            }
        }
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 2068
#include <stdio.h>

int main(void)
{
	int a[3], soe = 0;
	int kazu1, kazu2, kazu3;
	int max, middle, min;
	
	scanf("%d %d %d", &a[0], &a[1], &a[2]);
	
	for (max = 0; soe <= 2; ++soe){
		
		if (max < a[soe]){
			max = a[soe];
			kazu1 = soe;
		}
		
	}
	
	soe = 0;
	
	for (min = 10000; soe <= 2; ++soe){
		
		if (min > a[soe]){
			min = a[soe];
			kazu2 = soe;
		}
	}
	
	soe = 0;
	
	for (middle = a[0]; soe <= 2; ++soe){
		
		if ((a[soe] < max) && (a[soe] > min)){
			
			middle = a[soe];
		
		
		}
		
	}
	
		

	soe = 0;
	
	while (soe < 3){
		if (soe != kazu1 && soe != kazu2){
			
			printf("%d %d %d\n", min, a[soe], max);
		}
		
		soe++;
	}
	
	
	return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<P> ans;
    ll start = 1;
    ll end = N;
    if (N % 2) {
        rep(i, M) {
            ans.push_back(make_pair(start, end));
            start++;
            end--;
        }
    } else {
        for (int i = 0; i < (M + 1) / 2; i++) {
            ans.push_back(make_pair(i + 1, N - i));
        }
        for (int i = (M + 1) / 2; i < M; i++) {
            ans.push_back(make_pair(i + 1, N - i - 1));
        }
    }
    rep(i, M) {
        cout << ans[i].first << " " << ans[i].second << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 5304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define FOR(itr, v) for (auto itr = (v).begin(); itr != (v).end(); ++itr)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
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; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    int x; cin >> x;
    int ans = 1;
    Rep(i, 2, x + 1)
    {
        int v = i * i;
        while(v <= x)
        {
            chmax(ans, v);
            v *= i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3616
using System;

namespace AizuOnLine
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string[] data = Console.ReadLine().Split(' ');
                int h = Convert.ToInt32(data[0]);
                int w = Convert.ToInt32(data[1]);

                if (h == 0 && w == 0) { break; }

                for (int x = 0; x < h; x++)
                {

                    Console.WriteLine(new String('#', w));
                }

                Console.WriteLine(string.Empty);
            }
        }
    }
}

Measured memory_bytes: 8944
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
using namespace std;

int main() {
    string s; cin >> s;
    cout << s.rfind('Z') - s.find('A') + 1 << endl;
}


Measured memory_bytes: 640
use std::io;
use std::str;

fn read<T: str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .map(|x| T::from_str(x).ok().unwrap())
        .collect()
}

fn read_lines<T: str::FromStr>(n: usize) -> Vec<T> {
    let mut v = Vec::new();
    for _i in 0..n {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        v.push(T::from_str(s.trim()).ok().unwrap())
    }
    v
}

fn main() {
    let options = read::<usize>();
    let mut strings: Vec<String> = read_lines(options[0]);
    strings.sort();
    println!("{:}", strings.join(""));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
#define p pair<ll, ll>
using namespace std;

int used[100005];
int main() {
    int n, k;
    cin >> n >> k;
    vector<p> v;
    for (int i = 0; i < n; i++) {
        ll t, d;
        cin >> t >> d;
        v.push_back(p(d, t));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    priority_queue<p, vector<p>, greater<p>> que;
    ll sum = 0, x = 0;
    for (int i = 0; i < k; i++) {
        p cur = v[i];
        if (used[cur.second]) {
            sum += cur.first;
            que.push(p(cur.first, cur.second));
            continue;
        }
        sum += cur.first;
        x++;
        used[cur.second] = 1;
    }
    ll ans = sum + x * x;
    for (int i = k; i < n; i++) {
        p cur = v[i];
        if (used[cur.second]) continue;
        if (que.empty()) break;
        p nx = que.top();
        que.pop();
        used[cur.second] = 1;
        sum -= nx.first;
        sum += cur.first;
        x++;
        ans = max(ans, sum + x * x);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3696
#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
double d,p[10],h[10];
int n,b;
double u;
bool allok(double m){
	rep(i,n){
		double x=p[i];
		while(x>u) x-=u;
		if((4.0*m/u/u)*(-x*x+u*x)<h[i]) return false;
	}
	return true;
}
int main(){
	cin>>d>>n>>b;
	rep(i,n) cin>>p[i]>>h[i];
	double ans=1e100;
	rep(bounce,b+1){
		u=d/(bounce+1);
		double ub=1e10,lb=u/4;
		rep(tt,200){
			double m=(ub+lb)/2;
			if(allok(m)) ub=m;
			else lb=m;
		}
		double vy=sqrt(2.0*ub),vx=u/2.0/vy;
		ans=min(ans,sqrt(vx*vx+vy*vy));
	}
	printf("%.12f\n",ans);
}

Measured memory_bytes: 1240
#include <iostream>
#include <cstdio>
#include <cassert>

using namespace std;


class Solution{

public:
    long long minbase(long long n, long long s){

        long long b;
        for(b = 2ll; b * b <= n; b ++)
            if(sum(n, b) == s) return b;
//        assert(b * b > n);

        if(s == n) return n + 1ll;
        if(s == 1ll) return n;
//        if(s > (b - 1) + (b - 1)) return -1;

        long long res = LONG_LONG_MAX;
        for(long long k1 = 1; k1 < b; k1 ++){
            long long k2 = s - k1;
            if(k2 >= 0 && (n - k2 > 0) && (n - k2) % k1 == 0){
                long long tb = (n + k1 - s) / k1;
                if(k1 < tb && k2 < tb){
//                    assert(sum(n, tb) == s);
                    res = min(res, tb);
                }
            }
        }
        return res == LONG_LONG_MAX ? -1 : res;
    }

private:
    long long sum(long long n, long long b){

        long long res = 0ll;
        while(n){
            res += n % b;
            n /= b;
        }
        return res;
    }
};


int main() {

//    cout << Solution().minbase(87654ll, 30ll) << endl;
//    // 10
//
//    cout << Solution().minbase(87654ll, 138ll) << endl;
//    // 100
//
//    cout << Solution().minbase(87654ll, 45678ll) << endl;
//    // -1
//
//    cout << Solution().minbase(31415926535ll, 1ll) << endl;
//    // 31415926535
//
//    cout << Solution().minbase(1ll, 31415926535ll) << endl;
//    // -1
//
//    cout << Solution().minbase(31415926535ll, 31415926535ll) << endl;
//    // -1

//    cout << Solution().minbase(100000000000ll, 1ll) << endl;
//    // 10

//    cout << Solution().minbase(1ll, 1ll) << endl;
//    // 2

    long long n, s;
    scanf("%lld%lld", &n, &s);
    printf("%lld\n", Solution().minbase(n, s));

    return 0;
}


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

#define se second
#define fi first
#define mk(a,b) make_pair(a,b)

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

int N;
vector<pll> V;
ll S;
ll INF = 1001001001001001001;

ll unit(int l,int r,int bef)
{
    if(V[l].se == INF || V[r].se == INF)return V[r].fi - V[l].fi;
    ll res = 0;
    if((bef == 0 && V[l].se >= V[r].se) || (bef == 1 && V[l].se < V[r].se) || bef == -1)
        res += V[r].fi - V[l].fi;
    if(V[l].se < V[r].se)
    {
        V[r].se += V[l].se;
        return res + unit(l + 1,r,0);
    }
    else
    {
        V[l].se += V[r].se;
        return res + unit(l,r - 1,1);
    }
    return 0;
}

int main()
{
    scanf("%d%lld",&N,&S);
    V.push_back(mk(S,INF));
    for(int i = 0; i < N; i++)
    {
        ll x,p;
        scanf("%lld%lld",&x,&p);
        V.push_back(mk(x,p));
    }

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

    printf("%lld\n",unit(0,N,-1));
    return 0;
}


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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = ~(1<<28);

void printFixedDouble(double d, int fix) {
    cout << std::fixed;
    cout << std::setprecision(fix) << d << endl;
}

// #include <vector>
// #include <iostream>

std::vector<int> combination_list;

template<class TFunc>
void combination(const int depth, TFunc &func, short type = 0, int min = 1, int max = -1, int nowdepth = 0) {
    if (nowdepth == 0) {
        combination_list = std::vector<int>(depth);
    }
    if (min > max) {
        max = depth;
    }
    if (depth == nowdepth) {
        func(combination_list);
    } else {
        for (int i = min; i <= max; i++) {
            int newMin;
            switch(type) {
                case 0:
                    newMin = min;
                    break;
                case 1:
                    newMin = i;
                    break;
                case 2:
                    newMin = i+1;
                    break;
            }
            combination_list[nowdepth] = i;
            combination(depth, func, type, newMin, max, nowdepth+1);
        }
    }
}


struct Datum {
    int startId;
    int endId;
    int sum;
    int point;
};

int main() {
    int N, aMax, inputsNum;
    cin >> N >> aMax >> inputsNum;

    vector<Datum> list;
    
    rep(l, inputsNum) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--;
        b--;
        list.push_back({.startId=a, .endId=b, .sum=c, .point=d});
    }

    int max = 0;
    auto func = [&](vint vec) {
        int tmpmax = 0;
        rep(i, inputsNum) {
            if (vec[list[i].endId] - vec[list[i].startId] == list[i].sum) {
                tmpmax += list[i].point;
            }
        }
        max = std::max(tmpmax, max);
    };
    combination<decltype(func)>(N, func, 1, 1, aMax);
    cout << max << endl;
}

Measured memory_bytes: 3580
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 16
#define mod 1000000007

int n, m, x, y, i, limit;
int adj[maxN], pre[1 << maxN];
ll dp[1 << maxN];
bool us[1 << maxN];

ll poww[maxN * maxN];


int any(int conf) {
    int i;
    int ans = 0;

    for (i = 0; i < n; i++) {
        if (conf & (1 << i)) {
            ans += pre[adj[i] & conf];
        }
    }

    return poww[ans];
}

int solve(int conf) {
    int act, act2, i;
    ll aux;
    if (us[conf]) return dp[conf];
    us[conf] = true;

    dp[conf] = 1;
    for (act = conf; act > 0; act = (act - 1) & conf) {
        act2 = conf ^ act;
        aux = 1;

        if ((act & 3) != 3 && (act & 3) != 0) continue;

        for (i = 0; i < n; i++) {
            if (act & (1 << i)) {
                aux *= poww[ pre[adj[i] & act2] ] + mod - 1;
                aux %= mod;
            }
        }

        for (i = 0; i < n; i++) {
            if (act2 & (1 << i)) {
                aux *= poww[ pre[adj[i] & act] ];
                aux %= mod;
            }
        }

        if (aux == 0) continue;

        if (act & 3)
            dp[conf] += aux * solve(act);
        else
            dp[conf] += aux * any(act);

        dp[conf] %= mod;
    }

    dp[conf] %= mod;
    return dp[conf];
}

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%d%d", &n, &m);
    poww[0] = 1;
    for (i = 1; i <= n * n; i++) poww[i] = (poww[i - 1] * 2) % mod;

    for (i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        x--; y--;
        adj[x] |= 1 << y;
    }

    limit = 1 << n;
    for (i = 0; i < limit; i++) pre[i] = __builtin_popcount(i);

    cout << (poww[m] + mod - solve(limit - 1)) % mod;


    return 0;
}


Measured memory_bytes: 512
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <climits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main() {
#ifdef RUN_LOCAL
  ifstream in("../input.txt");
  cin.rdbuf(in.rdbuf());
#endif

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

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

  vector<vector<double>> dp(n + 1, vector<double>(n + 1));
  dp[0][0] = 1.0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      dp[i + 1][j] += dp[i][j] * (1 - p[i]);
      dp[i + 1][j + 1] += dp[i][j] * p[i];
    }
  }

  double res = 0;
  for (int j = (n / 2) + 1; j <= n; ++j) {
    res += dp[n][j];
  }

  cout << fixed << setprecision(10) << res << endl;

  return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int cnt = 0;
    while (a >= b) {
        b *= 2;
        cnt++;
    }
    while (b >= c) {
        c *= 2;
        cnt++;
    }
    cout << (cnt <= k ? "Yes" : "No") << endl;
    return 0;
}

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

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

#define RATE 380000.0

//C++14 (GCC 5.4.1)
int main() {
    int N;
    cin >>N;

    vector<double> x(N);
    vector<string> u(N);
    rep(i,N) cin >>x[i]>> u[i];
    
    //-----------------------------------
    int ans=0;
    double anss=0;
    rep(i,N){
        if(u[i]=="BTC"){
            anss+=x[i];
        }else{
            ans+=x[i];
        }
    }

    cout << (anss*RATE+ans) <<endl;
    return (0);
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M,K = map(int,readline().split())

for i in range(N+1):
    for j in range(M+1):
        if i*j+(N-i)*(M-j) == K:
            print('Yes')
            exit()
print('No')

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

using namespace std;

string s;
int k;

void input() {
    cin >> k;
    cin >> s;
}

void judge() {
    if(s.length() > k) {
        s = s.substr(0, k) + "...";
    }
    cout << s << endl;
}

int main() {
    input();
    judge();
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	long long a;
	string op;
	long long b;
	cin >> a >> op >> b;

	if (op == "+")
	{
		cout << a + b;
	}
	else
	{
		cout << a - b;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl

#define nl cout<<"\n"
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007

//write your function here
void fun()
{

}


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

    //start code from here
    string s,t;
    cin>>s>>t;
    ll count=0;
    for (ll i = 0; i < s.length(); i++)
    {
        if(s[i]!=t[i])
        count++;
    }
    cout<<count;
    nl;


}

Measured memory_bytes: 3792
#include <cstdio>
#include <algorithm>    
#include <iostream>
#include <vector>
#include <queue>
// #include <map>
#include <iomanip>
#include <cstring>
#include <cmath>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int uii;
typedef pair<int,int> pii;
typedef unsigned long long uLL; 
typedef vector<int> vii; 

const int maxn = 1234;
int d[maxn][maxn];
char s[maxn][maxn];
const int inf = 1e9 + 7; 
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		cin >> (s[i] + 1);
	}
	if(s[1][1] == '.') d[1][1] = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(s[i][j] == '.'){
				d[i][j] = (d[i][j] + d[i - 1][j] + d[i][j - 1]) % inf;
			}
		}
	}
	cout << d[n][m] << endl;
	return 0;
}

Measured memory_bytes: 6272
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){ 
    string s; cin >> s;
    int n = s.size();
    ll res = 0;
    int up = 0, down = 0, is_up = true;
    rep(i, n){
        if(s[i]=='<'){
            if(!is_up){
                //集計
                res += max(up, down);
                rept(num, 1, up)res += num;
                rept(num, 1, down)res += num;

                up = 0, down = 0;
                is_up = true;
            }
            up++;
        }else{
            if(is_up){is_up = false;}
            down++;
        }
    }
    res += max(up, down);
    rept(num, 1, up)res += num;
    rept(num, 1, down)res += num;

    cout << res << ln;
}



Measured memory_bytes: 4312
#include <iostream>
#include <bits/stdc++.h>
#define mod 998244353
#define point complex<double>
#define pi acos(-1)
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

void Fastio(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
ld n, dp[305][305][305];
ld solve(int i, int y, int j){
    if(i+y+j==0)
        return 0;
    if(dp[i][y][j]!=-1)
        return dp[i][y][j];
    ld res=1, c0 = ( i + y + j);
    if(i)res+=solve(i-1, y+1, j)*((ld)i)/n;
    if(y)res+=solve(i, y-1, j+1)*((ld)y)/n;
    if(j)res+=solve(i, y, j-1)*((ld)j)/n;
    return dp[i][y][j]=res / c0 * n;
}
int main()
{
    Fastio();
    int ttt=1; //cin>>ttt;
    while(ttt--){
        cin>>n;
        int c1=0, c2=0, c3=0;
        for(int i=0; i<n; i++){
            int x; cin>>x;
            if(x==1)c1++;
            else if(x==2)c2++;
            else c3++;
        }
        for(int i=0; i<305; i++){
            for(int y=0; y<305; y++){
                for(int j=0; j<305; j++){dp[i][y][j]=-1;}
            }
        }
        cout<<fixed<<setprecision(9)<<solve(c3, c2, c1)<<'\n';
    }

    return 0;
}


Measured memory_bytes: 447180
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;

int main() {
	ll h, w;
	cin >> h >> w;
	ll one, two, three;
	vector<ll> s;
	// h devide
	one = h / 3 * w;
	two = (h - (h / 3)) / 2 * w;
	three = h * w - one - two;
	s.push_back(max(max(one, two), three) - min(min(one, two), three));
	ll mind = h * w;
	for (int i = 1; i < h; i++) {
		one = i * w;
		two = (h - i) * (w / 2);
		three = h * w - one - two;
		mind = min(mind, max(max(one, two), three) - min(min(one, two), three));
	}
	s.push_back(mind);
	//w devide
	one = w / 3 * h;
	two = (w - (w / 3)) / 2 * h;
	three = h * w - one - two;
	s.push_back(max(max(one, two), three) - min(min(one, two), three));
	mind = h * w;
	for (int i = 1; i < w; i++) {
		one = i * h;
		two = (w - i) * (h / 2);
		three = h * w - one - two;
		mind = min(mind, max(max(one, two), three) - min(min(one, two), three));
	}
	s.push_back(mind);
	ll ans = *min_element(s.begin(), s.end());
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from heapq import heappush,heappop,heapify
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

V,E,r=map(int,input().split())
G=[[] for _ in range(V)]
for i in range(E):
    s,t,d=map(int,input().split())
    G[s].append((d,t))
dist=dijkstra(G,r,V)
for i in range(V):
    print(dist[i] if dist[i]!=INF else 'INF')


Measured memory_bytes: 89280
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    edge_to_idx = {}
    for i in range(n - 1):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        E[u].append(v)
        E[v].append(u)
        edge_to_idx[u, v] = edge_to_idx[v, u] = i

    def path(v, p, target):
        # base case
        if v == target:
            return 1 << edge_to_idx[v, p]
        res = 0
        for nv in E[v]:
            if nv == p:
                continue
            res |= path(nv, v, target)
        if res > 0 and p != -1:
            res |= 1 << edge_to_idx[v, p]
        return res

    m = int(input())
    constraints = [None] * m
    for i in range(m):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        constraints[i] = path(u, -1, v)

    res = 1 << (n - 1)
    # inc - exc principle
    for U in range(1, 1 << m):
        coef = 1 if bin(U).count('1') & 1 else -1
        binary = 0
        for i in range(m):
            if (U >> i) & 1:
                binary |= constraints[i]
        cnt = (n - 1) - bin(binary).count('1')
        res -= coef * (1 << cnt)

    print(res)
resolve()

Measured memory_bytes: 43704
n, a, b = map(int,input().split())
if a >= n:
    print(n)
elif a + b > n:
    print(a)
else:
    _i = n // (a + b)
    _j = n % (a + b)
    if _j - a <= 0:
        _j = _j
    else:
        _j = a
    ans = a * _i + _j
    print(ans)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
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; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    int N; cin >> N;
    vector<int> cnt(N);
    rep(i,N-1) {
        int a; cin >> a;
        --a;
        ++cnt[a];
    }
    rep(i,N) cout << cnt[i] << endl;
    return 0;
}


Measured memory_bytes: 4052
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <iomanip>
using namespace std;
int main() {
	long long n, k[100005], ans;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
	}
	sort(k, k + n);
	int a = 0, b = n - 1, aa, bb;
	ans = k[n - 1] - k[0];
	while (a < b) {
		aa = a + 1;
		bb = b - 1;
		if (aa == bb) {
			if (k[b] - k[aa] > k[bb] - k[a]) {
				ans += k[b] - k[aa];
				a = aa;
			}
			else {
				ans += k[bb] - k[a];
				b = bb;
			}
		}
		else {
			ans += k[b] - k[aa], ans += k[bb] - k[a];
			a = aa;
			b = bb;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=3009;
int n,t,a[N],b[N],dp[N];
int main(){
  cin>>n>>t;
  for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)if(a[i]>a[j])swap(a[i],a[j]),swap(b[i],b[j]);
  int ans=0;
  for(int i=1;i<=n;i++)
    for(int j=t-1;j>=0;j--){
      ans=max(ans,dp[j]+b[i]);
      if(j+a[i]<t)dp[j+a[i]]=max(dp[j+a[i]],dp[j]+b[i]);
    }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 384