akhauriyash/Code-Regression huggingface dataset:
// https://atcoder.jp/contests/abc088/tasks/abc088_d
// (白いマスの個数) - (最短経路でゴールする際に通る白いマスの個数)
// 幅優先探索で最短経路を通る時の白いマスの個数を算出する
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using P = pair<int, int>;
P u = P(-1, 0);
P d = P(1, 0);
P l = P(0, -1);
P r = P(0, 1);
P dir[4] = { u, d, l, r };

int main()
{
    int H, W;
    scanf("%d %d", &H, &W);
    vector<vector<bool>> s(H, vector<bool>(W));
    int white = 0;
    for (int i = 0; i < H; ++i)
    {
        char str[60];
        scanf("%s", str);
        for (int j = 0; j < W; ++j)
        {;
            if (str[j] == '.')
            {
                s[i][j] = true;
                ++white;
            }
            else
            {
                s[i][j] = false;
            }
        }
    }
    constexpr int inf = 1 << 30;
    vector<vector<int>> dp(H, vector<int>(W, inf));
    dp[0][0] = 1;
    queue<P> q;
    q.push(P(0, 0));
    while(!q.empty())
    {
        P cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            P next = P(cur.first + dir[i].first, cur.second + dir[i].second);
            if (next.first >= 0 && next.first < H && next.second >= 0 && next.second < W && s[next.first][next.second])
            {
                dp[next.first][next.second] = dp[cur.first][cur.second] + 1;
                s[next.first][next.second] = false;
                q.push(next);
            }
        }
    }
    
    if (s[H - 1][W - 1])
    {
        printf("%d\n", -1);
        return 0;
    }

    printf("%d\n", white - dp[H - 1][W - 1]);
    
    return 0;
}


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

const int mod = 1e9+7;
int memo[22][(1<<22)] = {0};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(n));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> arr[i][j];
        }
    }
    memo[0][0] = 1;
    for(int i = 0; i < n; ++i) {
        for(int bit = 0; bit < n; ++bit) {
            if(arr[i][bit]) {
                for(int mask = 0; mask < (1<<n); ++mask) {
                    if(mask&(1<<bit)) continue;
                    memo[i+1][mask|(1<<bit)] += memo[i][mask];
                    memo[i+1][mask|(1<<bit)] %= mod;
                }
            }
        }
    }
    cout << memo[n][(1<<n)-1] << '\n';
    return 0;
}


























Measured memory_bytes: 215296
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
maxA = max(a for a,b in AB)
dp = [0]*(H+maxA)
for i in range(1,H + maxA):
  dp[i] = min(dp[i-a]+b for a,b in AB)
print(dp[H])

Measured memory_bytes: 3664
#include <stdio.h>

int main()
{
  char buff[13];
  scanf("%s", buff);
  printf("%c%c%c%c %c%c%c%c%c%c%c%c\n",
    buff[0], buff[1], buff[2], buff[3],
    buff[4], buff[5], buff[6], buff[7],
    buff[8], buff[9], buff[10], buff[11]);
  return 0;
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    string S;
    cin >> S;
    ll r = 0, g = 0, b = 0;
    REP(i, N) {
        if (S[i] == 'R')
            r++;
        else if (S[i] == 'G')
            g++;
        else
            b++;
    }

    ll ans = r * g * b;
    FOR(i, N, 2) {
        REP(j, i) {
            ll d = i - j;
            if (j - d >= 0) {
                if (S[i] != S[j] && S[j] != S[j - d] && S[i] != S[j - d])
                    ans--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
	int n = int.Parse(ReadLine());
	int[] tmp = ReadIntArray();
	int[] a = tmp.Concat(new int[]{0}).ToArray();
	int r = 0; // right
	for (int i = 0; i < n; i++){ r += Math.Abs(a[i+1] - a[i]); }

	int l = 0; // left
	int pos = 0;
	for (int i = 0; i < n; i++)
	{
	    r -= Math.Abs(a[i+1] - a[i]);
	    int ans = l + r + Math.Abs(a[i+1] - pos);
	    WriteLine(ans);
	    l += Math.Abs(a[i] - pos);
	    pos = a[i];
	}
    }
}


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

using namespace std;

int main() {
    string s, t;
    int i, count;

    count = 0;
    cin >> s >> t;

    for (i = 0; i < 3; i++) {
        if (s[i] == t[i]) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}



Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().strip().split()))

c = 1000
s = 0

for i in range(n - 1):
    if A[i] < A[i + 1]:
        s += c // A[i]
        c -= (c // A[i]) * A[i]
    elif A[i] > A[i + 1]:
        c += s * A[i]
        s = 0
c += s * A[n - 1]

print(c)


Measured memory_bytes: 9212
N=int(input())
ans=N
for i in range(N+1): 
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    s=N-i
    while s>0:
        cnt+=s%9
        s//=9
    ans=min(ans,cnt)
print(ans)


Measured memory_bytes: 41068
//============================================================================
// Name        : ProjG.cpp
// Author      : Yong Kiat
// Version     :
// Copyright   : By Algotae.
// Description : Hello World in C++, Ansi-style
//============================================================================
 
#include <iostream>
 
using namespace std;
 
int main() {
	int N, W;
	cin >> N >> W;
 
	int weights[N];
	int values[N];
	for (int i = 0; i < N; i++) {
		cin >> weights[i] >> values[i];
	}
 
	long long dp[100001] = { 0 };
	for (int i = 0; i < N; i++) {
		for (int w = W; w >= weights[i]; w--) {
			dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
		}
	}
 
	cout << dp[W];
 
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using vc = vector<char>;
using pll = pair<ll, ll>;
template<class T> void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T> void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U> bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U> bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T> bool even(T n) { return ! (n & 1); }
template<class T> bool odd(T n) { return n & 1; }
template<class T> ll rup(T a, T b) { return a % b ? a / b + 1 : a / b; }
template<class T> ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T> ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;
ll intpow(ll a, ll n, ll _mod=numeric_limits<ll>::max()) { ll p=1; while (n) { if (n&1) p=p*a%_mod; a=a*a%_mod; n>>=1; } return p; } 
ll modc(ll a, char op, ll b, ll _mod=mod)
{
        a %= _mod; b %= _mod; ll res = 1;
        switch (op) {
        case '+': res = (a + b) % _mod; break;
        case '-': res = (a - b) % _mod; break;
        case '*': res = a * b % _mod; break;
        case '/': res = modc(a, '*', modc(b, '^', _mod-2, _mod), _mod); break;
        case '^': res = intpow(a, b, _mod); break;
        case 'P': rep(i, a-b+1, a+1) res = modc(res, '*', i, _mod); break;
        case 'C': res = modc(modc(a, 'P', b, _mod), '/', modc(b, 'P', b, _mod)); break;
        } 
        if (res < 0) { res += _mod; } return res;
}



int main()
{
        ll N, T;
        cin >> N >> T;
        vll A(N);
        rep(i, 0, N) cin >> A[i];

        vll mx(N);
        ll tmp = -inf;
        repreverse(i, N-1, 0) {
                if (tmp < A[i]) {
                        tmp = A[i];
                }
                mx[i] = tmp;
        }

        ll rmx = -inf;
        rep(i, 0, N-1) {
                chmax(rmx, mx[i+1]-A[i]);
        }

        ll ans= 0;
        rep(i, 0, N-1) {
                ll diff = mx[i+1] - A[i];
                if (diff == rmx) ++ans;
        }

        cout << ans << endl;
        //print1d(mx);
}


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

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

bool same(int x, int y) { return root(x) == root(y); }

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  int n;
  cin >> n;
  cout << (1110 - n) << endl;
}

Measured memory_bytes: 256
N = int(input())
Hn = list(map(int, input().split()))
max_total = 0
total = 0
for n in range(N-1):
  if Hn[n+1] <= Hn[n]:
    total += 1
    max_total = max(total, max_total)
  else:
    total = 0
print(max_total)


Measured memory_bytes: 14252
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[11],b[11];
	for(int i=0;i<10;i++){
		cin>>a[i];
	}
	sort(a,a+10);
	for(int i=0;i<10;i++){
		cin>>b[i];
	}
	sort(b,b+10);
	cout<<a[9]+a[8]+a[7]<<" "<<b[9]+b[8]+b[7]<<endl;
}

Measured memory_bytes: 3124
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main(void){
	int N,M,count=0,sum;
	vector<int> A;
	cin >> N >> M;
	int tmp;
	for (int i=0;i<N;i++){		
		cin >> tmp;
		A.push_back(tmp);
	}
	sum = accumulate(A.begin(),A.end(),0);
	for (int i=0;i<N;i++){
		if(A[i] >= float(sum)/(4*M)){
			count++;
		}
	}
	if(count >= M)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
    	new Main(); 
    }
 
    public Main() {
    	new A().doIt();
    }
    class A{
    	class Par{
    		int sw,sh,ew,eh;
    		public Par(int sw,int sh,int ew,int eh){
    			this.sw = sw;
    			this.sh = sh;
    			this.ew = ew;
    			this.eh = eh;
    		}
    	}
    	void doIt(){
    		while(true){
    			ArrayList<Par> array = new ArrayList<Par>();
    			int n = sc.nextInt();
    			if(n == 0)break;
    			array.add(new Par(0,0,1,1));
    			int sw = 0,sh = 0,ew = 1,eh = 1;
    			for(int i = 1;i < n;i++){
    				int num = sc.nextInt();
    				int side = sc.nextInt();
    				Par p = array.get(num);
    				int mw = 0,mh = 0;
    				if(side == 0){
    					mw = -1;
    					mh = 0;
    				}else if(side == 1){
    					mw = 0;
    					mh = -1;
    				}else if(side == 2){
    					mw = 1;
    					mh = 0;
    				}else{
    					mw = 0;
    					mh = 1;
    				}
    				array.add(new Par(p.sw+mw,p.sh+mh,p.ew+mw,p.eh+mh));
    				sw = Math.min(sw, p.sw+mw);
    				sh = Math.min(sh, p.sh+mh);
    				ew = Math.max(ew, p.ew+mw);
    				eh = Math.max(eh, p.eh+mh);
    			}
    			System.out.println((ew - sw)+" "+(eh - sh));
    		}
    	}
    }
}

Measured memory_bytes: 40984
#include<stdio.h>
int main (){
    int sz,num,i,j;
    char ch;
    int counter[26] = {0};

    while(scanf("%c",&ch) != EOF){

        if(ch >='A' && ch <= 'Z'){
            num = ch - 'A';
            counter[num]++;
        }

        if(ch >='a' && ch <= 'z'){
            num = ch - 'a';
            counter[num]++;
        }
    }

    for(i = 0,ch = 'a';i < 26;i++,ch++){
        printf("%c : %d\n",ch,counter[i]);
    }
    return 0;
}




Measured memory_bytes: 2092
#include "bits/stdc++.h"
using namespace std;

const int N = 210;
int sum[N];

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

    int max = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '(') sum[i]++;
        else sum[i]--;
        sum[i] += sum[i - 1];
        max = min(max, sum[i]);
    }

    if (max < 0) {
        max *= -1;
        s = string(max, '(') + s;
        n = s.size();
    }

    memset(sum, 0, sizeof sum);
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '(') sum[i]++;
        else sum[i]--;
        sum[i] += sum[i - 1];
    }

    if (sum[n] > 0) s = s + string(sum[n], ')');
    cout << s << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int H,W,K;
vector<string> S;
void input(){
    fast_io();
    cin >> H >> W >> K;
    for (int i = 0; i < H; i++)
    {
        string s; cin >> s;
        S.push_back(s);
    }
}

int solve(){
    vector<vector<int>> A(H,vector<int>(W,0));
    int c = 1;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if(S[i][j]=='#') {
                A[i][j] = c;
                c++;
            }
        }
    }

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W-1; j++)
        {
            if(A[i][j+1]==0) A[i][j+1] = A[i][j];
        }

        for (int j = W-1; j > 0; j--)
        {
            if(A[i][j-1]==0) A[i][j-1] = A[i][j];
        }

    }

    for (int j = 0; j < W; j++)
    {
        for (int i = 0; i < H-1; i++)
        {
            if(A[i+1][j]==0) A[i+1][j] = A[i][j];
        }

        for (int i = H-1; i > 0; i--)
        {
            if(A[i-1][j]==0) A[i-1][j] = A[i][j];
        }
    }



    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }


    return 0;
}   

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

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int n;
string s;
ll ans = 0;

void solve(ll x,ll y){
    if(x==n+1){
        ans += y;
        return;
    }
    ll cur = 0;
    for(ll i=x;i<=n;i++){
        cur = (10*cur) + (s[i]-'0');
        solve(i+1,y+cur);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin>>n>>m;
    cout<<max(0LL,n-m)<<endl;
}


Measured memory_bytes: 3640
n = int(input())
lst = [0, 0, 0, 0, 0]
for i in range(n):
  s = input()
  if s[0] == "M":
    lst[0] += 1
  if s[0] == "A":
    lst[1] += 1
  if s[0] == "R":
    lst[2] += 1
  if s[0] == "C":
    lst[3] += 1
  if s[0] == "H":
    lst[4] += 1

ans = 0
for i in range(3):
  for j in range(i+1, 4):
    for k in range(j+1, 5):
      ans += lst[i]*lst[j]*lst[k]
      
print(ans)

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

int main() {
    while (true) {
        int input;
        cin >> input;
        if (input == 0) {
            break;
        }
        int change = 1000 - input;
        int coin = 0;
        while (change > 0) {
            if (change >= 500) {
                change -= 500;
            } else if (change >= 100) {
                change -= 100;
            } else if (change >= 50) {
                change -= 50;
            } else if (change >= 10) {
                change -= 10;
            } else if (change >= 5) {
                change -= 5;
            } else {
                change--;
            }
            coin++;
        }
        cout << coin << endl;
    }
}

Measured memory_bytes: 0
fun main(args : Array<String>) {
    val annena = Array(5,{readLine()!!.toInt()})
    val k = readLine()!!.toInt();
    
    if (annena.max()!! - annena.min()!! <= k) {
        println("Yay!")
        
    }else{
        println(":(")
    }
}

Measured memory_bytes: 34320
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int n, m, r; cin >> n >> m >> r;
    vector<vector<pair<int, int>>> adj(n + 10); // vertex, weight
    vector<int> cities(r);
    for (int &x : cities) {
        cin >> x;
    }
    for (int i = 0; i < m; i++) {
        int u, v, d; cin >> u >> v >> d;
        adj[u].emplace_back(v, d);
        adj[v].emplace_back(u, d);
    }
    const ll inf = (ll) 1e12;
    auto getdist = [&](int from) {
        vector<ll> dist(n + 10, inf);
        dist[from] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.emplace(0, from);
        while (!pq.empty()) {
            auto p = pq.top(); pq.pop();
            ll d = p.first, v = p.second;
            for (auto edge : adj[v]) {
                ll newd = d + edge.second, u = edge.first;
                if (dist[u] > newd) {
                    dist[u] = newd;
                    pq.emplace(newd, u);
                }
            }
        }
        return dist;
    };
    vector<vector<ll>> d;
    for (int i = 0; i <= n; i++) {
        d.emplace_back(getdist(i));
    }
    ll res = inf;
    sort(cities.begin(), cities.end());
    do {
        ll cur = 0;
        for (int i = 1; i < r; i++) {
            cur += d[cities[i - 1]][cities[i]];
        }
        res = min(res, cur);
    } while (next_permutation(cities.begin(), cities.end()));
    cout << res << "\n";
}


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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M;
vpl pts[MAXN];
ll dp[MAXN];
ll seg[3 * MAXN], lazy[3 * MAXN];
ll ans;

void push(int w, int L, int R)
{
	if (lazy[w] == 0) return;
	seg[w] += lazy[w];
	if (L != R)
	{
		lazy[w << 1] += lazy[w];
		lazy[w << 1 | 1] += lazy[w];
	}
	lazy[w] = 0;
}
void update(int w, int L, int R, int a, int b, ll v)
{
	push(w, L, R);
	if (b < L || R < a) return;
	if (a <= L && R <= b)
	{
		lazy[w] += v;
		push(w, L, R);
		return;
	}
	int mid = (L + R) >> 1;
	update(w << 1, L, mid, a, b, v);
	update(w << 1 | 1, mid + 1, R, a, b, v);
	seg[w] = max(seg[w << 1], seg[w << 1 | 1]);
	return;
}
ll query(int w, int L, int R, int a, int b)
{
	push(w, L, R);
	if (b < L || R < a) return -LLINF;
	if (a <= L && R <= b)
	{
		return seg[w];
	}
	int mid = (L + R) >> 1;
	return max(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	FOR(i, 0, M)
	{
		int l, r; ll v;
		cin >> l >> r >> v; l--; r--;
		pts[r].PB({l, -v});
		dp[0] += v;
	}
	//(x, v) means you pay v if x...cur are all 0s
	//dp[x] = best cost, given that x - 1 is a 1:
	// cerr << dp[0] << endl;
	update(1, 0, N + 1, 0, 0, dp[0]);
	// cerr << "UPDATE " << 0 << ' ' << 0 << ' ' << dp[0] << endl;
	FOR(i, 1, N + 2)
	{
		dp[i] = query(1, 0, N + 1, 0, i - 1);
		update(1, 0, N + 1, i, i, dp[i]);
		for (pll p : pts[i - 1])
		{
			int x = p.fi; ll v = p.se;
			// cerr << "UPDATE " << 0 << ' ' << x << ' ' << v << endl;
			update(1, 0, N + 1, 0, x, v);
		}
		// cerr << "QUERY " << 0 << ' ' << i - 1 << ' ' << dp[i] << endl;
		// cerr << "UPDATE " << i << ' ' << i << ' ' << dp[i] << endl;
	}
	FOR(i, 0, N + 2)
	{
		ckmax(ans, dp[i]);
		// cerr << dp[i] << ' ';
	}
	// cerr << endl;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 22144
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			String s = sc.next();

			int a = Integer.parseInt(s.substring(0, 2));
			int b = Integer.parseInt(s.substring(2));

			if (isMonth(a)) {
				if (isMonth(b)) {
					System.out.println("AMBIGUOUS");
				} else if (isYear(b)) {
					System.out.println("MMYY");
				} else {
					System.out.println("NA");
				}
			} else if (isYear(a)) {
				if (isMonth(b)) {
					System.out.println("YYMM");
				} else {
					System.out.println("NA");
				}
			} else {
				System.out.println("NA");
			}
		}

	}

	private static boolean isMonth(int i) {
		if (0 < i && i < 13) {
			return true;
		}
		return false;
	}

	private static boolean isYear(int i) {
		if (0 <= i && i < 100) {
			return true;
		}
		return false;
	}
}

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

typedef pair<int,int> pii;
const int N = 1e5;

int n;
vector<int> adj[N+5][4];
int ans[N+5];

void dfs(int now, int par, int war){
	ans[now] = war;
	for(int i=0;i<adj[now][0].size();i++){
		int cur = adj[now][0][i];
		if(cur == par) continue;
		dfs(cur,now,war);
	}
	
	for(int i=0;i<adj[now][1].size();i++){
		int cur = adj[now][1][i];
		if(cur == par) continue;
		dfs(cur,now,1-war);
	}
	return;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		w&=1;
		adj[u][w].push_back(v);
		adj[v][w].push_back(u);
	}
	dfs(1,-1,0);
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 18432
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }

int n;
vi va, vb;

void init()
{
	cin >> n;
	va.resize(n);	REP(i, n) cin >> va[i];
	vb.resize(n);	REP(i, n) cin >> vb[i];
}


int main()
{
	init();
	int ans = 0;

	for (int bit = 28; bit >= 0; bit--)
	{
		REP(i, n)
		{
			va[i] &= (~(1 << bit + 1));
			vb[i] &= (~(1 << bit + 1));
		}

		sort(ALL(vb));

		int p = 1 << bit;
		int cnt = 0;

		REP(i, n)
		{
			cnt += lower_bound(ALL(vb), 2 * p - va[i]) - lower_bound(ALL(vb), p - va[i]);
			cnt += vb.end() - lower_bound(ALL(vb), 3 * p - va[i]);
		}

		if (cnt & 1)
			ans |= (1 << bit);
	}

	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll  long  long
#define INF 1000000000000000000LL
#define pll pair<long long , long long>
const int MAX=5e6+9;
const ll MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int main() 
{
    int n , k;
    cin>>n>>k;
    ll mx=0;
    ll c[n+1];
    int p[n+1];
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++)
        cin>>c[i];
    ll ans = c[1];
    int vis[n+1];
    for(int i=1;i<=n;i++){
        ans = max(ans,c[i]);
        memset(vis, 0 , sizeof(vis));
        ll cur = 0;
        int t = i;
        vector<ll>now;
        while(vis[t]!=1){
            vis[t]=1;
            cur = cur+c[t];
            now.push_back(cur);
            t=p[t];
        }
        ll mx = now[0];
        for(int j=1;j<min((int)now.size() , k);j++)
            mx =max(now[j] , mx);
        int u = (int)(now.size());
        int rem=k%u;
        u = k/u;
        if(u<=0)
            ans = max(ans, mx);
        else
        {
            mx = now[0];
             for(int j=0;j<now.size();j++){
               // cout<<now[j]<<" ";
                mx =max(now[j] , mx);
            }
           // cout<<endl;
            if (rem==0)
                ans = max(ans, cur*(ll)(u-1)+mx);
            ans = max(ans, mx);
             ans =max(ans, cur*(ll)u);
            for(int j=0;j<rem;j++)
                ans =max(ans, now[j]+cur*(ll)u);
        }

    }
    cout<<ans;

}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

void output(int a, int b) {
	printf("%d %d\n", a, b);
}

void solve(){
	int n;
	scanf("%d", &n);
	if ((n & (n - 1)) == 0) {
		printf("No\n");
		return;
	}
	printf("Yes\n");
	output(n + 1, n + 2);
	for(int i = 2; i + 1 <= n; i += 2) {
		output(1, i);
		output(i, i + 1);
		output(n + i, n + i + 1);
		output(n + i + 1, 1);
	}
	if (n % 2 == 0) {
		int ind = 1;
		for(; (n & ind) == 0; ind *= 2);
		output(n + n, n + n - ind + 1);
		output(ind, n);
	}
	/*if (n % 4 == 2) {
		output(n + n, n + n - 1);
		output(2, n);
	}
	if (n % 4 == 0) {
		output(n + n, n + n - 3);
		output(4, n);
	}*/
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 2304
/*
首先搞定一个性质，就是假如小矩形横着或者竖着的长度小于等于大矩形的1/2肯定不行， 因为两个负权值的合并起来也一定是负权值，
这样的话就判断了不可行的情况， 然后考虑这样相当于形成了一个横竖十字交
将负数放在交上肯定会更合适
所以直接在十字的某个元素放-数就好了

结果发现交不成十字的也要考虑， 因为这样也可能是更优的,那么贪心来放， 第一个不能放的放上

发现更能转换成一般模型， 在刚要过界的地方看看是否合适， 这样先弄再判断所有权值 再输出正误

发现还忽略一个问题， 有时候不选择1会更优 ， 其他数字都加一的情况下， 这个可以减去一部分，使得总权值更大QWQ

*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
#define M 550
using namespace std;
int read() {
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}

ll a, b, c, d, ans, s1, s2;
int note[M][M];
int main() {
	a = read(), b = read(), c = read(), d = read();
	int ct =1000000000 / (c * d);
	int op = c * d - 1;
	for(int i = 1; i <= a; i++) {
		for(int j = 1; j <= b; j++) {
			if((i % c == 0) && (j % d == 0)) note[i][j] = op * ct * -1 - 1, s2++;
			else note[i][j] = ct, s1++;
			ans += note[i][j];
		}
	}
	if(ans <= 0) {
		cout << "No\n";
		return 0;
	}
	cout << "Yes\n";

	for(int i = 1; i <= a; i++) {
		for(int j = 1; j <= b; j++) {
			cout << note[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

Measured memory_bytes: 3840
while True:
	try:
		xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2 = map(float,raw_input().split())
	except EOFError:
		break
	
	if xa1 > xb2 or xa2 < xb1 or ya1 > yb2 or ya2 < yb1:
		print "NO"
	else:
		print "YES"

Measured memory_bytes: 6256
import sys
N,Y = map(int,input().split(" "))

man_max = Y//10000

go_max = Y // 5000

sen_max = Y // 1000


for i in range(N,-1,-1):
    for j in range (N-i+1):
        if 10000*i +5000*j +1000*(N-(i+j)) == Y: 
            print(str(i)+" "+str(j) + " " + str(N-(i+j)))
            sys.exit()
print("-1 -1 -1")

Measured memory_bytes: 3064
a = int(input())
b = input().split()

for i in range(0,len(b)):
    b[i]=int(b[i])



state=1
for x in b:
    if x==0:
        state=0
        print("0")
        break

res=1
if state==1:
    for x in b:
        res*=x
        if res>1000000000000000000:
            print("-1")
            state=0
            break

if state==1:
    print(res)


Measured memory_bytes: 88840
#include <iostream>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define nt _int128
#define inf (int)1e9

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	// cin >> t;
	t  = 1;
	while (t--)
	{
		ll n, k;
		cin >> n >> k;
		ll arr[n];
		for (ll i = 0; i < n; i++) cin >> arr[i];
		ll dp[n];
		for (ll i = 0; i < n; i++)
			dp[i] = 999999999;
		dp[0] = {0};

		for (ll i = 1; i < n; i++)
		{

			ll j = max(0LL, i - k);
			for (j; j < i; j++)
			{
				dp[i] = min(dp[i], abs(arr[i] - arr[j]) + dp[j]);
			}
		}
		cout << dp[n - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
from collections import defaultdict
import math

N = int(input())
s = [str(sorted(input())) for _ in range(N)]
rl_s = defaultdict(int)
for _s in s:
  rl_s[_s] += 1

c = 0
for v in rl_s.values():
  c += sum([i for i in range(v)])
print( c )
  

Measured memory_bytes: 24564
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<< "\n"


int main(){
    int n;
    cin >> n;
    REP(i,n+1){
        if (i==0) continue;
        else if(i%3==0)cout << " " << i;
        else{
            int num = i;
            while(num!=0){
                if(num%10==3){
                    cout << " "<<i;
                    break;
                }
                else num /= 10;
            }
            continue;
        }
    }
    cout << endl;
}


Measured memory_bytes: 3084
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[derive(Debug)]
struct Dp (i64, i64);
impl Dp {
    fn chmin(&mut self) -> &mut Dp {
        if self.0 > self.1 {
            self.0 = self.1;
            self
        } else {
            self
        }
    }
    fn chmax(&mut self) -> &mut Dp {
        if self.0 < self.1 {
            self.0 = self.1;
            self
        } else {
            self
        }
    }
}

fn main() {
    input!{
        N: usize,
        abc: [[i64; 3]; N],
    }
    let mut dp = vec![vec![0; 3]; N+1];

    for i in 0..N {
        for j in 0..3 {
            for k in 0..3 {
                if j == k {continue;}
                dp[i+1][k] = Dp (dp[i+1][k], dp[i][j] + abc[i][k]).chmax().0;
            }
        }
    }
    let mut ret = 0;
    for j in 0..3 {
        ret = Dp (ret, dp[N][j]).chmax().0;
    }
    println!("{}", ret);
}



Measured memory_bytes: 18684
#include <bits/stdc++.h>
using namespace std;
#define INF (long)(1e9+7)
int main(){
    string s; cin>>s;
    vector<long[4]> dp(s.size()+1); 
    dp[0][0]=1;
    for(int i=1;i<=s.size();i++){
        for(int j=0;j<=3;j++){
            dp[i][j]=dp[i-1][j];
            if(s[i-1]=='?')
                dp[i][j]*=3;
            dp[i][j]%=INF;
        }
        if(s[i-1]!='?')
            dp[i][s[i-1]+1-'A']+=dp[i-1][s[i-1]-'A'];
        else{
            for(int j=1;j<=3;j++){
                dp[i][j]+=dp[i-1][j-1];
               dp[i][j]%=INF;
            }
        }
    }
    cout<<dp[s.size()][3]%INF;
}   

Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define il inline
#define re register
#define fo(i,j,k) for(register int i=j;i<=k;i++)
#define inf 0x7fffffff
typedef long long ll;
using namespace std;
il ll read()
{
	re ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f*x;	
}
ll n,k,ans;
int main()
{
	n=read(),k=read();
	if(n>=k)
	{
		n=n%k;
		ans=min(n,k-n);
		printf("%lld\n",ans);
	}
	else
	{
		ans=min(n,k-n);
		printf("%lld\n",ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  int N,L;
  cin>>N>>L;
  int sum=0;
  vector<int> aji(N+1);
  bool hantei=false;
  rep2(i,1,N+1){
    sum+=L+i-1;
    aji.at(i)=L+i-1;
    if(L+i-1==0){
      hantei=true;
    }
  }
  sort(aji.begin(),aji.end());
  if(hantei){
    cout<<sum<<endl;
    return 0;
  }else if(sum>0){
    cout<<sum-aji.at(1)<<endl;
  }else{
    reverse(aji.begin(),aji.end());
    cout<<sum-aji.at(1)<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
i=n
for j in csgraph.depth_first_order(csr_matrix((t[:n-1],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):i-=1;t[j-1]=c[i]
print(sum(c[:-1]),*t[:n])

Measured memory_bytes: 27868
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#define MAXDEG 524288
#define LGDEG 19
#define HIGHEST 262144
#define MAXDEGN 1000005
#define MAXN 700005
#define MAXNN 700005
#define EPS 0.1
using namespace std;
struct Complex{
    double re,im;
    Complex(void):re(0.0),im(0.0){}
    Complex(double tr,double ti=0.0):re(tr),im(ti){}
    Complex(const Complex& tc):re(tc.re),im(tc.im){}
    friend Complex operator+(const Complex& lhs,const Complex& rhs);
    friend Complex operator-(const Complex& lhs,const Complex& rhs);
    friend Complex operator*(const Complex& lhs,const Complex& rhs);
    friend Complex operator-(const Complex& x);
};

typedef long long ll;

const double pi=acos(-1.0);
int rev[MAXDEGN];
Complex a[MAXDEGN],b[MAXDEGN],t[MAXDEGN];

const int p=200003;
const int ppw=200002;
const int gp=5;
int logp[MAXNN];
ll cnts[MAXN];
int arrr[MAXNN];

void fft(Complex* f,int is_inv=0);

signed main(void){
    int cur=1;
    logp[cur]=0;
    for (int i=1;i<ppw;i++)
        cur=cur*gp%p,logp[cur]=i;
    int n,nn=0;
    scanf("%lld",&n);
    for (int i=1;i<=n;i++){
        int t;
        scanf("%lld",&t);
        if (!t)
            continue;
        cnts[logp[t]]++;
        arrr[++nn]=t;
    }
    for (int i=0;i<ppw;i++)
        a[i].re=cnts[i];
    rev[0]=0;
    for (int i=1;i<MAXDEG;i++)
        rev[i]=(i&1)?(HIGHEST^(rev[i>>1]>>1)):(rev[i>>1]>>1);
    fft(a);
    for (int i=0;i<MAXDEG;i++)
        a[i]=a[i]*a[i];
    fft(a,1);
    for (int i=0,ub=ppw+ppw;i<=ub;i++)
        cnts[i]=a[i].re+EPS;
    ll ans=cnts[0];
    cur=1;
    for (int i=1,ub=ppw+ppw;i<=ub;i++){
        cur=cur*gp%p;
        ans+=1ll*cnts[i]*cur;
    }
    for (int i=1;i<=nn;i++)
        ans-=1ll*arrr[i]*arrr[i]%p;
    assert(!(ans&1));
    ans/=2;
    printf("%lld\n",ans);
    return 0;
}

void fft(Complex* f,int is_inv){
    for (int i=0;i<MAXDEG;i++)
        t[i]=f[rev[i]];
    for (int i=0;i<LGDEG;i++){
        int cur_len=1<<i;
        int tran_len=cur_len<<1;
        Complex omega_n=Complex(cos(pi/cur_len),sin(pi/cur_len)); //2pi/tran_len=pi/cur_len
        (is_inv)?(omega_n.im=-omega_n.im):(0);
        for (int unit_l=0;unit_l<MAXDEG;unit_l+=tran_len){
            Complex omega=Complex(1.0,0.0);
            for (int k=0;k<cur_len;k++,omega=omega*omega_n){
                //kth couple
                int cpa=unit_l+k;
                int cpb=cpa+cur_len;
                Complex a_val=t[cpa];
                Complex b_val=omega*t[cpb];
                t[cpa]=a_val+b_val;
                t[cpb]=a_val-b_val;
            }
        }
    }
    for (int i=0;i<MAXDEG;i++)
        f[i]=t[i];
    if (is_inv)
        for (int i=0;i<MAXDEG;i++)
            f[i].re/=MAXDEG,f[i].im/=MAXDEG;
}

Complex operator+(const Complex& lhs,const Complex& rhs){
    return Complex(lhs.re+rhs.re,lhs.im+rhs.im);
}
Complex operator-(const Complex& lhs,const Complex& rhs){
    return Complex(lhs.re-rhs.re,lhs.im-rhs.im);
}
Complex operator*(const Complex& lhs,const Complex& rhs){
    return Complex(lhs.re*rhs.re-lhs.im*rhs.im, lhs.re*rhs.im+lhs.im*rhs.re);
}
Complex operator-(const Complex& x){
    return Complex(-x.re,-x.im);
}

Measured memory_bytes: 26732
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    full = 2**N
    dp = [float('inf')] * full
    dp[0] = 0
    for m in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        state = 0
        for c in C:
            state += 2**(c-1)
        
        for i in range(full):
            if dp[i] != float('inf'):
                dp[i|state] = min(dp[i] + a, dp[i|state])
        
    
    if dp[-1] == float('inf'):
        return -1

    return dp[-1]

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

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

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	if (a + 1 == b) {
		cout << "Borys" << endl;
	}
	else {
		if ((b - a) % 2 == 0) {
			cout << "Alice" << endl;
		}
		else {
			cout << "Borys" << endl;
		}
	}

	return 0;
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int A, B, K;
	cin >> A >> B >> K;
	for (int i = A; i >= 1; --i){
		if (A%i == 0 && B%i == 0) K--;
		if (K == 0){
			cout << i << '\n';
			return 0;
		}
	}
	cout << flush;
	//for (int i = 0; i < 1e9; ++i){for (int j = 0; j < 1e9; ++j){}}
	
}

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

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

int main(){
    int n;
    ll lcm=1;
    cin>>n;
    for(int i=0;i<n;i++){
        ll t;
        cin>>t;
        lcm=t/gcd(t,lcm)*lcm;
    }
    cout<<lcm<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <utility>

#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; i++)

typedef long long ll;
using namespace std;

int main() {
    
    int a, b, c;
    cin >> a >> b >> c;

    if (a + b + 1 >= c) {
        cout << b + c << endl;
    } else {
        cout << a + b + 1 + b << endl;
    }
    
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    m = int(input())
    DC = [list(map(int, input().split())) for _ in range(m)]
    total = 0
    res = 0
    for d, c in DC:
        r = c * d
        res += c
        while r // 10:
            q, r = divmod(r, 10)
            res += q
            r += q
        total += r

    while total // 10:
        q, total = divmod(total, 10)
        res += q
        total += q

    print(res - 1)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 103836
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    if(a <= c && c <= b){
        cout << "Yes\n";
    }else if(a >= c && c >= b){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
}


Measured memory_bytes: 256
import numpy as np
A,B,H,M = list(map(int,input().split()))
tansin = H*30 + M / 2.0
tyosin = M * 6


theta  = min(abs(tansin-tyosin), 360 - abs(tansin-tyosin))

C = np.sqrt(A**2 + B**2 - 2*A*B*np.cos(np.pi * theta/ 180))

print(C)


Measured memory_bytes: 27192
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <climits>
#include <map>
#include <queue>
#include <cmath>

using namespace std;

using int64 = long long;
using P = pair<char,int>;

void divisers(int64 n, map<int64,int64>& mp) {
    while(n%2==0) n/=2,mp[2]++;
    int64 stop = sqrt(n);
    for (int64 i=3; i<=stop; i+=2) {
        while(n%i==0) n/=i,mp[i]++;
    }
    if (n!=1) mp[n]++;
}

int main() {
    int64 n,p;
    cin >> n >> p;
    map<int64, int64> mp;
    divisers(p, mp);

    int64 ans = 1;
    for (auto [a,b] : mp) {
        for (int i=0; i<b/n; i++) ans *= a;
    }
    cout << ans << endl;
}

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

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(n) for(int i = 0; i < n; i++)
#define run(i, a, b) for(int i = a; i < b; i++)
#define cinarr(arr, n) repi(n) cin >> arr[i]
#define coutarr(arr, n) repi(n) cout << arr[i] << " "; cout << endl
#define vi vector<int>
#define ff first
#define ss second
#define pb push_back
#define cinset(st, n) {int _t; repi(n) {cin >> _t; st.insert(_t);}}


typedef long long int ll;
typedef unsigned long long int ull;

int main(){
    FAST_IO
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    
    ll ans = max(max(a * c, a * d), max(b * c, b * d));
    cout << ans << endl;
}


Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;
const int Maxn = 100005;
int arr[Maxn];
int dp[Maxn];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
	}
	dp[1] = 0;
	dp[2] = abs(arr[1] - arr[2]);
	for (int i = 3; i <= n; ++i) {
		dp[i] = min(dp[i - 2] + abs(arr[i - 2] - arr[i]), dp[i - 1] + abs(arr[i - 1] - arr[i]));
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 1024
// Copyright 2019 yaito3014
#include "bits/stdc++.h"
using namespace std;
int main() {
  std::cout.tie(0); std::ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int ans = 0;
  for (int i = 1; i <= N; ++i)
    if (((int)log10(i) + 1) % 2)++ans;
  cout << ans << endl;
}


Measured memory_bytes: 640