akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

size_t min_mod(size_t L, size_t R) {
  constexpr size_t DENOM = 2019;
  if (R - L >= DENOM)
    return 0;
  else {
    size_t min = DENOM - 1;
    for (size_t i = L; i < R; ++i)
      for (size_t j = i + 1; j <= R; ++j) min = std::min(min, (i * j) % DENOM);
    return min;
  }
}

int main() {
  size_t L, R;
  cin >> L >> R;
  cout << min_mod(L, R) << endl;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
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 ) * } } ; }
#[allow(unused_macros)]
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 ) * } } ; }
#[allow(unused_macros)]
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" ) } ; }

fn main() {
    input! {
        n: usize, k: usize,
        a: [u64; n]
    }

    let mut counted = count(&a).into_iter().map(|(k,v)| (v,k)) .collect::<Vec<_>>();
    counted.sort();
    let mut ret = 0;
    let mut kinds = counted.len();
    for i in 0..counted.len() {
        if kinds <= k {
            break;
        }
        ret += counted[i].0;
        kinds -= 1;
    }
    println!("{}", ret);
}

#[allow(dead_code)]
fn count<T: Eq + std::hash::Hash + Clone>(slice: &[T]) -> std::collections::HashMap<T, usize> {
    let mut hmap = std::collections::HashMap::new();
    for item in slice {
        *hmap.entry(item.clone()).or_insert(0) += 1;
    }
    hmap
}

Measured memory_bytes: 17172
#include<stdio.h>

int main(){
    int A,B,C,D;
    scanf("%d %d %d %d",&A,&B,&C,&D);

    if(B<C){
        printf("0\n");
        return 0;
    }
    if(D<A){
        printf("0\n");
        return 0;
    }

    if(A>C){
        if(B>D){
            printf("%d\n",D-A);
        }else{
            printf("%d\n",B-A);
        }
    }else{
        if(B>D){
            printf("%d\n",D-C);
        }else{
            printf("%d\n",B-C);
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
int main() {//言語変えろ言語変えろ言語変えろ言語変えろ言語変えろ
            
int n;cin>>n;
  vector<string>a(n);
 
  int ans=1;
  
  rep(i,n){cin>>a.at(i);   }
   sort(all(a));
  
  rep(j,n-1){if(a.at(j)!=a.at(j+1)){ans++;}}
  
  
  cout<<ans<<endl;
}

Measured memory_bytes: 9556
n = int(input())
atai_lis = list(map(int,input().split()))

def gusu(a):
    if a % 2 == 0:
        return a // 2
    else:
        return -1

flag = True
cnt = 0

while flag:
    atai_lis = list(map(gusu,atai_lis))
    if -1 in atai_lis:
        flag = False
    else:
        cnt += 1


print(cnt)

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

int main(){
  int n;
  int m;
  int count;
  int amax=0;
  cin >> n;
  vector<string> s(n);
  for(int i=0;i<n;i++){
    cin >> s[i];
  }
  cin >> m;
  vector<string> t(m);
  for(int i=0;i<m;i++){
    cin >> t[i];
  }
  for(int i=0;i<n-1;i++){
    count=1;
    for(int j=i+1;j<n;j++){
      if(s[i]==s[j]){
        count++;
      }
    }
    for(int k=0;k<m;k++){
      if(s[i]==t[k]){
        count--;
      }
    }
    amax=max(amax,count);
  }
  if(amax<=0){
    cout << 0 << endl;
  }else{
    cout << amax << endl;
  }    
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007

using namespace std;

int main(void) {
	stack<int>p;
	stack<int>s;
	int n;
	
	while (cin >> n) {
		if (n == 0) {
			s.push(p.top());
			cout << s.top() << endl;
			p.pop();
		}
		else {
			p.push(n);
		}
	}
	
	return 0;
}

Measured memory_bytes: 2988
import itertools

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]

ans = 0
cnt = 0

for a in A:
    for i in range(W):
        if a[i] == "#":
            cnt += 1


def countData(lhs, rhs):
    cnt = 0
    for i in range(H):
        if i in lhs:
            continue
        for j in range(W):
            if j in rhs:
                continue
            if A[i][j] == '#':
                cnt += 1
    return cnt


def countRow(lhs, rhs):
    cnt = 0
    for i in range(H):
        if i == lhs:
            continue
        if i == rhs:
            continue
        for j in range(W):
            if A[i][j] == '#':
                cnt += 1
    return cnt


def countCol(lhs, rhs):
    cnt = 0
    for i in range(H):
        for j in range(W):
            if j == lhs:
                continue
            if j == rhs:
                continue
            if A[i][j] == '#':
                cnt += 1
    return cnt


if cnt < K:
    print(0)
    exit()

stRowlist = [i for i in range(H)]
stCollist = [i for i in range(W)]

# 行列
for i in range(H):
    for rows in itertools.combinations(stRowlist, i):
        for j in range(W):
            for cols in itertools.combinations(stCollist, j):
                cnt = countData(rows, cols)
                if (cnt == K):
                    ans += 1


print(ans)


Measured memory_bytes: 68936
#include<stdio.h>
int strLen (char ar[])
{
    int i=0,c=0;
    while (ar[i]!='\0')
    {
        c++;
        i++;
    }
    return c;
}
int main()
{
    char ar[1000],br[1000],cr[1000];
    scanf ("%s %s",ar,br);
    int l,i,j=0,k,r=0,s=0;
    l=strLen(ar);
    while (ar[j]!='\0')
    {
        cr[j]=ar[j];
        j++;
    }
    for (i=l,k=0;i<(2*l),k<l;i++,k++)
    {
        ar[i]=cr[k];
    }
    ar[2*l]='\0';
    int p,q,z=1,f=1,g=1;
    p=l-1;
    for (r=0;(r+p)<(2*l);r++)
    {
        if (br[0]==ar[r])
        {
            q=r;
            while (br[z]!='\0')
            {
                if (ar[q+z]==br[z])
                {
                    f=1;
                    z++;
                    continue;
                }
                else if (ar[q+z]!=br[z])
                {
                    f=0;
                    break;
                }
            }
            if (f==1)
            {
               g=1;
               break;
            }
            else if (f==0)
            {
                g=0;
                continue;
            }
        }
        else if (br[0]!=ar[r])
        {
            g=0;
            continue;
        }
    }
    if (g==1)
    {
        printf ("Yes\n");
    }
    else if (g==0)
    {
        printf ("No\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ld long double
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
const int inf=1e9+7;

int main()
{
	ll n;
	cin>>n;
	ll a[n];
	loop(i,0,n)
	{
		cin>>a[i];
	}
	vector< vector<ll> > dp(n,vector<ll>(n,0));
	loop(i,0,n) dp[i][i]=a[i];
	loop(k,1,n)
	{
		loop(i,0,n-k)
		{
			dp[i][i+k]=max(a[i]-dp[i+1][i+k],a[i+k]-dp[i][i+k-1]);
		}
	}
	cout<<dp[0][n-1];
	return 0;
}




Measured memory_bytes: 70656
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] S = sc.next().toCharArray();
		int N = S.length;
		int[] ans = new int[N];
		Arrays.fill(ans, 1);
		int[] cons = new int[N];
		Arrays.fill(cons, 1);
		for(int i = 1; i < N; i++) {
			if(S[i] == 'R' && S[i] == S[i-1]) {
				ans[i] += ans[i-1];
				ans[i-1] = 0;
				cons[i] = cons[i-1];
				cons[i]++;
			}
		}
		for(int i = N-2; i >= 0; i--) {
			if(S[i] == 'L' && S[i] == S[i+1]) {
				ans[i] += ans[i+1];
				ans[i+1] = 0;
				cons[i] = cons[i+1];
				cons[i]++;
			}
		}
		for(int i = 1; i < N; i++) {
			if(S[i] == 'L' && S[i] != S[i-1]) {
				int T = ans[i] + ans[i-1];
				if(cons[i-1] % 2 == 0 && cons[i] % 2 == 1) {
					ans[i-1] = T/2;
					ans[i] = (T+1)/2;
				}
				else {
					ans[i-1] = (T+1)/2;
					ans[i] = T/2;
				}
			}
		}
		for(int i = 0; i < N; i++)
			System.out.print(ans[i] + " ");
		System.out.println();

	}

}

Measured memory_bytes: 45020
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
// clang-format on

int main(void)
{
  int N;
  int A, B;
  cin >> N >> A >> B;
  if (N == 1) {
    cout << "Hello World" << endl;
  }
  else if (N == 2) {
    cout << A + B << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
    #pragma comment(linker, "/stack:200000000")
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    #include<bits/stdc++.h>
    #define int long long
    # define mo 1000000007
    using namespace std;
    #define goku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    signed main(){
        goku
      int n,k;
      cin>>n>>k;
      int a[n];
      for(int i=0;i<n;i++)
        cin>>a[i];
        sort(a,a+n);
      int su=0;
      for(int i=0;i<max((int)0,n-k);i++)
        su+=a[i];
      cout<<su;
       return 0;
    }


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int MOD=1000000007;
const int nmax=501234;

int n,a[17][17],bt[17],flg[1<<17];
ll dp[1<<17],dp2[1<<17];
queue<int> q2;

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j) scanf("%d",&a[i][j]);
    for(int i=1; i<=n+1; ++i) bt[i]=1<<i-1;
    for(int i=2; i<=n; ++i)
        for(int i2=bt[i]+1; i2<bt[i+1]; ++i2)
            for(int j=1; j<i; ++j) if(i2&1<<j)
                    for(int k=0; k<j; ++k) if(i2&1<<k) dp[i2]+=a[j][k];
    for(int i=2; i<=n; ++i)
        for(int i2=bt[i]+1; i2<bt[i+1]; ++i2){
            int s=i2;
            do{
                ll tmp3=dp[s]+dp2[s^i2];
                if(dp2[i2]<tmp3) dp2[i2]=tmp3;
                s=i2&(s-1);
            }while(s>=bt[i]);
        }
    printf("%lld",dp2[(1<<n)-1]);
    return 0;
}


Measured memory_bytes: 1280
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;

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

    int N;
    cin >> N;
    vector<vector<ll>> A(10, vector<ll>(10));
    for (int i = 0; i <= N; i++) {
        string s = to_string(i);
        int top = s[0] - '0';
        int bottom = s[s.size() - 1] - '0';
        A[top][bottom]++;
    }

    ll ans = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            ans += A[i][j] * A[j][i];
        }
    }

    cout << ans - 1 << endl;
}

Measured memory_bytes: 3692
#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    }
    let mut i = 1;
    let s = a.iter().sum::<usize>();
    let mut factors = vec![];
    loop {
        if i * i > s {
            break;
        }
        if s % i == 0 {
            factors.push(i);
            factors.push(s / i);
        }
        i += 1;
    }
    factors.sort();
    factors.reverse();

    for &f in &factors {
        let mut s1 = 0;
        let mut v = vec![];
        for &ai in &a {
            if ai % f != 0 {
                s1 += f - ai % f;
                v.push(ai % f);
            }
        }
        v.sort();
        let mut s2 = 0;
        for i in 0..v.len() {
            if s1 == s2 {
                break;
            }
            s2 += v[i];
            s1 -= f - v[i];
        }
        if s1 == s2 && s1 <= k {
            println!("{}", f);
            return;
        }
    }
}


Measured memory_bytes: 4352
#include <stdio.h>
int main() {
    int A, B, C, D;
    scanf("%d %d %d %d", &A, &B, &C, &D);
    while (1) {
        C=C-B;
        if(C<1) {
            printf("Yes\n");
            break;
        }
        A=A-D;
        if(A<1) {
            printf("No\n");
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1624
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
    int n;
    ll t;
    cin >> n >> t;
    ll s[n];
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    ll ans = 0;
    ll e = 0;
    for(int i = 1; i < n; i++){
        if(e + t >= s[i]){
            ans += s[i] - e;
            e = s[i];
        } else {
            ans += t;
            e = s[i];
        }
    }
    ans += t;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

object Main extends App {

  val sc = new Scanner(System.in);

  val n = sc.nextInt();
  val k = sc.nextInt();
  val ls = Array.fill(n)(sc.nextInt());

  @scala.annotation.tailrec
  def search(answer1: Int, answer2: Int): Int = {
    val mid = (answer1 + answer2) / 2;
    val c = ls.map { l =>
      (l - 1) / mid;
    }.sum;
    if (answer1 + 1 >= answer2) {
      if (c > k) {
        answer2;
      } else {
        answer1;
      }
    } else {
      if (c > k) {
        search(mid, answer2);
      } else {
        search(answer1, mid);
      }
    }
  }

  val answer = search(1, ls.max);

  println(answer);
}

Measured memory_bytes: 69448
a,b,c = map(int, input().split())

if a >= b >= c:
    print("%d %d %d" % (c,b,a))
elif a >= c >= b:
    print("%d %d %d" % (b,c,a))
elif b >= a >= c:
    print("%d %d %d" % (c,a,b))
elif b >= c >= a:
    print("%d %d %d" % (a,c,b))
elif c >= b >= a:
    print("%d %d %d" % (a,b,c))
elif c >= a >= b:
    print("%d %d %d" % (b,a,c))



Measured memory_bytes: 5600
/* # */

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <deque>
#include <map>
#include <iomanip>
#include <functional>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cstring>
//#pragma warning(disable:4996)

using namespace std;


/** Type Define **/
typedef long long int           ll;
typedef pair<int, int>          pii;
typedef pair<ll, ll>            pll;
typedef vector<string>          vs;
typedef vector<bool>            vb;
typedef vector<int>             vi;
typedef vector<long long>		vl;
typedef vector<vi>              vvi;
typedef vector<vl>				vvl;
typedef vector<char>            vch;
#define		it(x)  x.begin() 
#define		all(x)  x.begin(), x.end()
#define		pb(x)   push_back(x)
constexpr int           inf = 0x3f3f3f3f;
constexpr long long 	INF = 9123456789123456789;
constexpr long long     MOD = 1000000007LL;
/*************************************************/
void sol() {
    ll n, k;
    cin >> n >> k;
    if (n == k) cout << "0\n";
    else if (n < k) {
        ll ans = n < (k - n) ? n : (k - n);
        cout << ans << endl;
    }
    else {
        n = n % k;
        ll ans = n < (k - n) ? n : (k - n);
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cin.tie(nullptr);
    sol();


    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> p;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, n) for(int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define srep(i, from, to) for(int i = from; i < (int)(to); i++)
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<int> a = vector<int>(n);
  vector<int> b = vector<int>(n);
  vector<int> c = vector<int>(n);
  rep(i, n) {
    cin >> a[i] >> b[i] >> c[i];
  }
  vector<vector<int>> dp = vector<vector<int>>(n + 1, vector<int>(3));
  rep(i, n) {
    dp[i + 1][0] = max(dp[i][1] + a[i], dp[i][2] + a[i]);
    dp[i + 1][1] = max(dp[i][0] + b[i], dp[i][2] + b[i]);
    dp[i + 1][2] = max(dp[i][0] + c[i], dp[i][1] + c[i]);
  }

  int ans = max(max(dp[n][0], dp[n][1]), dp[n][2]);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6912
use std::io::*;
use std::collections::BinaryHeap;

fn read<T: std::str::FromStr>() -> T {
    let stdin = stdin();
    let mut buf = String::new();
	stdin.lock().read_line(&mut buf);
	buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
	read::<String>().trim().split_whitespace()
        .map(|w| w.parse().ok().unwrap()).collect()
}

fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    cost: usize,
    pos: usize
}

impl Ord for State {
    fn cmp(&self, other: &State) -> std::cmp::Ordering {
        if self.cost == other.cost {
            self.pos.cmp(&other.pos)
        } else {
            other.cost.cmp(&self.cost)
        }
    }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

#[derive(Clone)]
struct Edge {
    node: usize,
    cost: usize
}

fn dijkstra_all(mat: &Vec<Vec<Edge>>, s: usize) -> Vec<usize> {
    let mut heap = BinaryHeap::new();
    let mut cost: Vec<usize> = vec![usize::max_value();mat.len()];
    cost[s] = 0;
    heap.push(State {cost: 0, pos: s});
    while let Some(State {cost: c, pos: p}) = heap.pop() {
        if c > cost[p] {
            continue;
        }
        for e in &mat[p] {
            let next = State {cost: c + e.cost, pos : e.node};
            if next.cost < cost[next.pos] {
                heap.push(next);
                cost[next.pos] = next.cost;
            }
        }
    }
    cost
}

fn main() {
    let v = read_vec::<usize>();
    let (n,m,s,t) = (v[0],v[1],v[2]-1,v[3]-1);
    let w = read_mat::<usize>(m);
    let mut cy: Vec<Vec<Edge>> = vec![Vec::new();n];
    let mut cs: Vec<Vec<Edge>> = vec![Vec::new();n];
    for x in w {
        let u = x[0]-1;
        let v = x[1]-1;
        cy[u].push(Edge {node: v, cost: x[2]});
        cy[v].push(Edge {node: u, cost: x[2]});
        cs[u].push(Edge {node: v, cost: x[3]});
        cs[v].push(Edge {node: u, cost: x[3]});
    }
    let route1 = dijkstra_all(&cy, s);
    let route2 = dijkstra_all(&cs, t);
    let mut route_tot: Vec<(usize,usize)> = (0..n).map(|i| (route1[i] + route2[i], i)).collect();
    route_tot.sort_by(|a,b| a.0.cmp(&b.0));
    let mut idx = 0;
    for y in 0..n {
        while route_tot[idx].1 < y {
            idx += 1;
        }
        println!("{}",10usize.pow(15) - route_tot[idx].0);
    }
}


Measured memory_bytes: 33524
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <functional>
#include <tuple>
#include <climits>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <numeric>
#include <map>
#include <cmath>
#include <cstdlib>
#include <iomanip>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> a(N);
    for(auto &aa : a) cin >> aa;
    const int min = *min_element(a.begin(), a.end());
    const int max = *max_element(a.begin(), a.end());
    
    if(min == max) {
        cout << 0 << endl;
        return 0;
    }
    int minimum = numeric_limits<int>::max();
    for(int i=min; i<=max; i++) {
        int m = 0;
        for(auto &aa : a) m += (aa-i)*(aa-i);
        if(minimum > m) minimum = m;
    }
    cout << minimum << endl;
}


Measured memory_bytes: 256
A =list(str(input()))
B =list(str(input()))
C =list(str(input()))
P=A
for i in range(len(A)+len(B)+len(C)+3):
    if P[0] == 'a':
        P.pop(0)
        P=A
        if len(A) ==0:
            print('A')
            break
    elif P[0] =='b':
        P.pop(0)
        P=B
        if len(B) ==0:
            print('B')
            break
    elif P[0] =='c':
        P.pop(0)
        P=C
        if len(C) ==0:
            print('C')
            break

Measured memory_bytes: 9028
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
  ll n;
  cin>>n;
  vector<ll> v;
  ll sum = 0;
  rep(i,0,n){
    ll a;
    cin>>a;
    v.pb(a);
    sum += a;
  }
  ll l = 0;
  ll r = sum;
  ll mn = 1000000000000000000;
  rep(i,0,v.sz){
    l += v[i];
    r -= v[i];
    mn = min(mn,max(l,r)-min(l,r));
  }
  cout << mn << endl;
  return 0;
}

Measured memory_bytes: 2420
#include <stdio.h>
  
int main(void){
    int n,x,i,j,k;
    while(1){
    int c=0;
    scanf("%d %d",&n,&x);
    if(n==0 && x==0){
        break;
    }
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            for(k=j+1;k<=n;k++){
                if(i+j+k==x){
                    c++;
                }
            }
        }
    }
    printf("%d\n",c);
    }
    return 0;
}
 

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, k, n) for(auto i = k; i != n; i++)
#define rrep(i, n) RREP(i, n, 0)
#define RREP(i, n, k) for(auto i = n; i != k; i--)
#define all(x, r) (x), (x)+(r)
#define ALL(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " " << x << endl
#define exst(x, data) (data).find(x) != (data).end()
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define np next_permutation
#define b32 bitset<32>

using ll = long long;
using Pii = pair<int,int>;
using Tiii = tuple<int, int, int>;
template<class T>using V = vector<T>;

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

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

    int N, K; cin >> N >> K;
    V<int> A = V<int>(N); rep(i,N) cin >> A[i];

    int GCD = A[0]; REP(i,1,N) GCD = gcd(GCD,A[i]);
    int M = *max_element(ALL(A));
    if(M==K || (M>K && K%GCD == 0)) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;
}


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

int main() {
  int n;cin>>n;
  vector<int> a(n+1);
  ll ans = 0;
  // 連想配列を使う map
  map<int,int> mp;
  for(int i=1; i<=n; i++) {
    cin>>a[i];
    ans+=mp[i-a[i]];
    mp[i+a[i]]++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 21096
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
template <typename T>
string to_string(const T &n){ostringstream stm;stm << n;return stm.str();}
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = LLONG_MAX;

vector<int> G[112345];
int dp[100100];
int rec(int v){
    if(dp[v]!=-1)return dp[v];

    int res=0;
    for(auto nv:G[v]){
        res=max(res,rec(nv)+1);
    }
    dp[v]=res;
    return res;
}
signed main(){
    int N,M;
    cin>>N>>M;
    rep(i,M){
        int x,y;
        cin>>x>>y;
        x--;y--;
        G[x].push_back(y);
    }
    rep(i,N)dp[i]=-1;

    int res=0;
    rep(i,N)res=max(res,rec(i));
    cout<<res<<endl;


 
}

Measured memory_bytes: 8448
A, B = map(int, input().split())
if not A & 1 and B & 1:
    ans = (B-A)//2+1 & 1
else:
    ans = (B-A)//2 & 1
if A & 1:
    ans ^= A
if not B & 1:
    ans ^= B
print(ans)


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define e18 (long long)(1e18)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}


void solve()
{
  ll n; cin >> n;
  // ll x, y, z; cin >> x >> y >> z;
  // ll a, b, c; cin >> a >> b >> c;
  // string s; cin >> s;
  vector<ll> a(n); rep(i, n) cin >> a[i];
  unsigned long long  ans = 1;
  bool ok = true;
  rep(i, n) {
    if(a[i] == 0) {
      cout << 0 << endl;
      return;
    }
    if(ans > e18 / a[i]) ok = false;
    ans *= a[i];

  }
  if(!ok) {
    cout << -1 << endl;
    return;
  }

  cout << ans << endl;
  // cout << (ok?"Yes":"No") << endl;
}


int main(void)
{
  // ll t; cin >> t; REP(i, t)
  solve();
}


Measured memory_bytes: 4048
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

#define rep(i,n) for(ll i = 0; i < n; i++)

typedef long long ll;

using namespace std;

int main(){
  ll n,max = 1;
  cin >> n;
  for(ll i = 2; i * i <= n; i++){
    if(n % i == 0) max = i;
  }
  cout << (max-1) + (n/max-1) << endl; 
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
 
using namespace std;
 
#define INF 1000000000
#define EPS 1e-9
#define PI acos(-1)
 
typedef long long ll;
typedef pair<ll, int> P;
 
#define MAX_R 1005
#define MAX_C 1005
#define mod 100000007

int r, c;
int a1, a2;
int b1, b2;

ll solve(int a, int b){

  a = abs(a);
  b = abs(b);

  if(a == 0 || b == 0)
    return 1;

  ll dp[MAX_R+1][MAX_C+1];

  memset(dp, 0, sizeof(dp));

  for(int i = 0; i <= a; i++){
    dp[i][0] = 1;
  }
  for(int i = 0; i <= b; i++){
    dp[0][i] = 1;
  }

  for(int i = 1; i <= b; i++){
    for(int j = 1; j <= a; j++){
      dp[j][i] = (dp[j-1][i] + dp[j][i-1]) % mod;
    }
  }

  return dp[a][b] % mod;

}

int main(){

  vector<P> d;

  cin >> r >> c >> a1 >> a2 >> b1 >> b2;

  int dx[] = {0,r,r,0,-r,-r,-r,0,r};
  int dy[] = {0,0,c,c,c,0,-c,-c,-c};

  for(int i = 0; i < 9; i++){
    ll tmp = (a1+dx[i] - b1) * (a1+dx[i]-b1) + (a2+dy[i]-b2) * (a2+dy[i]-b2);
    d.push_back(P(tmp, i));
  }

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

  ll ans = 0;

  ans += solve(b1 - (a1 + dx[d[0].second]), b2 - (a2 + dy[d[0].second]));

  for(int i = 1; i < 9; i++){
    if(d[i-1].first != d[i].first)
      break;
    else
      ans = (ans + solve(b1 - (a1 + dx[d[i].second]), b2 - (a2 + dy[d[i].second]))) % mod;
  }

  cout << ans % mod << endl;

  return 0;

}

Measured memory_bytes: 9112
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int L;
vi A;

vector<vi> dp;

vi d={0,1,2,1,0};

signed main(){

    in(L);
    resz(L,A);
    in(A);
    resize(dp,L+1,5);
    rep(i,5) dp[0][i]=0;
    vi costs(3);
    REP(i,1,L+1){
        // int cost0=A[i];
        // int costEven=A[i]&1;
        // int costOdd=A[i]%2==0;
        costs[0]=A[i-1];
        costs[1]=(A[i-1]==0)?2:A[i-1]&1;
        costs[2]=A[i-1]%2==0;
        // show(costs);
        rep(j,5){
            int mn=INF;
            rep(k,j+1){
                mn=min(mn,dp[i-1][k]);
            }
            dp[i][j]=mn+costs[d[j]];
        }
    }
    int ans=INF;
    rep(i,5){
        ans=min(ans,dp[L][i]);
    }
    out(ans);

    return 0;
}


Measured memory_bytes: 15872
end = False

while end is False:
	m, f, r = map(int, input().split())
	if m == f == r == -1:
		end = True
	else:
		if m == -1 or f == -1:
			grade = 'F'
		elif m + f >= 80:
			grade = 'A'
		elif m + f >= 65:
			grade = 'B'
		elif m + f >= 50:
			grade = 'C'
		elif m + f >= 30:
			if r >= 50:
				grade = 'C'
			else:
				grade = 'D'
		else:
			grade = 'F'

		print(grade)



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

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

	int ans = 0;
	for(int i=0; i<N-1; i++){
			for(int j=i+1; j<N; j++){
			ans += d[i] * d[j];
		}
	}

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


Measured memory_bytes: 256
#include<cstdio>
long long n,x,y,mod,ans,p[4001][4001],f[8001],vis[4001][4001];
long long mi(long long k,long long p)
{
	if (!p)return 1;
	long long s=mi(k,p/2);
	s=s*s%mod;
	if (p%2)s=s*k%mod;
	return s;
}
long long c(long long n,long long m)
{
	return f[n]*mi(f[m],mod-2)%mod*mi(f[n-m],mod-2)%mod;
}
int main()
{
	mod=1000000007;
	f[1]=1;
	for (int i=2;i<=8000;i++)f[i]=f[i-1]*i%mod;
	scanf("%lld",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		p[2000-x][2000-y]++;
		ans=(ans+c(2*x+2*y,2*y))%mod;
		vis[x+2000][y+2000]++;
	}
	ans=mod-ans;
	for (int i=0;i<=4000;i++)
		for (int j=0;j<=4000;j++)
		{
			if (i)p[i][j]=(p[i][j]+p[i-1][j])%mod;
			if (j)p[i][j]=(p[i][j]+p[i][j-1])%mod;
			ans=(ans+vis[i][j]*p[i][j])%mod;
		}
	printf("%lld",ans*mi(2,mod-2)%mod);
}

Measured memory_bytes: 188928
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N,M;
char buf[5];


int main(){

	scanf("%d %d",&N,&M);

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

		buf[i] = '@';
	}

	int s,c;

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

		scanf("%d %d",&s,&c);
		s--;

		if(buf[s] == '@'){

			buf[s] = c+'0';
		}else{

			if(buf[s]-'0' != c){

				printf("-1\n");
				return 0;
			}
		}
	}

	if(N > 1 && buf[0] == '0'){

		printf("-1\n");
		return 0;

	}else{

		for(int i = 0; i < N; i++){
			if(buf[i] == '@'){

				if(i == 0 && N > 1){

					buf[i] = '1';

				}else{

					buf[i] = '0';
				}
			}

			printf("%c",buf[i]);
		}
		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 256
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
P = [1 for _ in range(10**6+1)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6+1,i):
        P[j] = 0
Q = {}
for i in range(2,10**6+1):
    if P[i]==1:
        Q[i] = 0
Q1 = sorted(list(Q.keys()))
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    a = A[i]
    for b in Q1:
        if a%b==0:
            cnt = 0
            while a%b==0:
                a = a//b
                cnt += 1
            Q[b] = max(Q[b],cnt)
            if a==1:break
        elif b>1000 and a>1:
            Q[a] = max(Q[a],1)
            break
        else:continue
lcmA = 1
for b in Q:
    cnt = 1
    for i in range(Q[b]):
        cnt = (cnt*b)%p
    lcmA = (lcmA*cnt)%p
tot = 0
for i in range(N):
    tot = (tot+lcmA*pow(A[i],p-2))%p
print(tot)

Measured memory_bytes: 113904
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  ll n,c,k;
  cin >> n >> c >> k;
  vector <ll> t;
  REP(i,n){
    ll T;
    cin >> T;
    t.pb(T);
  }
  sort(t.begin(),t.end());
  ll num = 0;
  REP(i,t.size()){
    ll sum = 0;
    ll g = 0;
    ll r = 0;
    REP(j,c){
      if(i+j == t.size()){
	r = j-1;
	break;
      }
      
      if(t[i+j]-t[i] > k){
	r = j-1;
	break;
      }
      if(j == c-1){
	r = c-1;
	
      }
    }
    num++;
    i += r;
    //cout << r << endl;
  }
  cout << num << endl;
  return 0;
}



Measured memory_bytes: 1400
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;

#define ll long long
#define F(i,a,b) for(int i=a;i<=b;++i)
#define R(i,a,b) for(int i=a;i<b;++i)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define cpy(a,b) memcpy(a,b,sizeof(b))
#pragma comment(linker, "/STACK:102400000,102400000")
inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

ll x,ans;

int main()
{
    while(scanf("%lld",&x)==1)
    {
        ans=x/11*2;
        x%=11;
        if(x)
        {
            if(x>6) ans+=2;
            else ans+=1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    set<string> S;
    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        S.insert(s);
    }
    cout << S.size() << '\n';
    return 0;
}

Measured memory_bytes: 19184
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
 
 
#define F first
#define S second
#define ll long long
#define pb push_back
#define db double
#define ld long double
#define ppb pop_back
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define all(x) (x).begin(),(x).end()
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TEST int T; cin >> T; while(T--)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//#define int long long
 
const int N = 1e5 + 1, inf = 2e9 + 7, mod = 1e9 + 7;
const ll INF = 2e18 + 7, MOD = 1e15 + 7;

int a[404], n;
ll dp[404][404];

ll rec(int l, int r) {
    if(dp[l][r]) return dp[l][r];
    ll ans = INF, sum = 0;
    for (int i = l; i < r; i++) {
        sum += a[i];
        ans = min(ans, rec(l, i) + rec(i + 1, r));
    }
    sum += a[r];
    return dp[l][r] = ans + sum;
}

signed main() { __
//    freopen("lcm.in", "r", stdin);
//    freopen("lcm.out", "w", stdout);
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        dp[i][i] = a[i];
    }
    cout << rec(1, n) - sum;
    return 0;
}



Measured memory_bytes: 1664
n = int(input())
a = ''
for i in range(1,n+1):
    x = i
    if x % 3 == 0:
        a = a + ' ' + str(i)
    elif x % 10 == 3:
        a = a + ' ' + str(i)
    else:
        x = x // 10
        while True:
            if x == 0:
                break
            else:
                if x % 10 == 3:
                    a = a + ' ' + str(i)
                    break
                x = x // 10

print(a)


Measured memory_bytes: 5628
class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

    #出力用
    def __str__(self):
        return "\n".join("{}: {}".format(r,self.members(r)) for r in self.roots())
        #"\n"はただの改行コード
        #str(辞書)を改行しながら表示する
        #print(インスタンス)で__str__に飛ぶ
        #出力過程で、membersで全要素にfindをしてる→逐一経路圧縮されてる！


n,m=map(int,input().split())
A=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ; b-=1
    A.append([a,b])

ans=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if j==i:
            continue
        uf.union(*A[j])
    
    if len(uf.roots())!=1:
        ans+=1
print(ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch))
f|=ch=='-',ch=getchar();
while(isdigit(ch))
x=x*10+(ch^48),ch=getchar();
return f?-x:x;}
int main(){ 
int n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
int kk=(k-i*m),a=n-i-i;
if(!kk||a&&(kk>>31&1)==(a>>31&1)&&kk%a==0&&kk/a<=m){
cout<<"Yes"<<endl;
return 0;}
}
cout<<"No"<<endl;}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, x;
  cin >> n >> k;
  vector<int>v;
  for(int i = 0; i < k; ++i){ 
    cin >> x;
    v.push_back(x);
  }
  auto good = [&] (int cur) {
    while(cur != 0) {
      int d = cur%10;
      cur/=10;
      for(auto dig : v) {
        if(dig == d)return false;
      }
    }
    return true;
  };
  while(!good(n)) {
    ++n;
  }
  cout << n << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define ll  long long 
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
#define mod 1000000007
  vector<ll>to[1000005];
int main(){
  string a;cin>>a;
  rep(i,3)cout<<a[i];
}


Measured memory_bytes: 27032
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var sc = bufio.NewScanner(os.Stdin)

const inf = 1 << 60
const mod int = 1e9 + 7

func ri() (n int) {
	sc.Scan()
	for _, v := range sc.Bytes() {
		n = n*10 + int(v-48)
	}
	return
}

func main() {
	sc.Split(bufio.ScanWords)
	n := ri()

	d := make([]int, n)
	for i := 0; i < n; i++ {
		d[i] = ri()
	}

	sort.Ints(d)

	// fmt.Println(d)

	x := n / 2
	ans := d[x] - d[x-1]
	fmt.Println(ans)
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		for (int i = 0 ; i < N; i++)
			a[i] = sc.nextInt();
		for (int i = 0; i < N; i++) {
			int trg = a[i];
			int j = i - 1;
			while (j >= 0 && trg < a[j]){
				a[j+1] = a[j];
				j--;
			}
			a[j+1] = trg;
			for (int k = 0; k < a.length-1; k++)
				System.out.printf("%d ", a[k]);
			System.out.println(a[a.length-1]);
		}
	}
}

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

const int N = 1e5 + 5;
long long c, res, a[N], l[N], r[N], mx[N];
int n, v[N];
long long calc() {
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        l[i] = l[i-1] - 2 * (a[i] - a[i-1]) + v[i];
        mx[i] = max(mx[i-1], l[i]);
    }
    for (int i = n; i >= 1; --i) {
        r[i] = r[i+1] - (a[i+1] - a[i]) + v[i];
        ans = max(ans, mx[i-1] + r[i]);
    }
    return ans;
}
int main() {
    scanf("%d%lld", &n, &c);
    a[n+1] = c;
    for (int i = 1; i <= n; ++i) scanf("%lld%d", &a[i], &v[i]);
    res = calc();
    for (int i = 1; i <= n; i++) a[i] = c - a[i];
    for (int i = 1; i <= n / 2; i ++) {
        int j = n - i + 1;
        swap(a[i], a[j]);
        swap(v[i], v[j]);
    }
    res = max(res, calc());
    printf("%lld", res);
}


Measured memory_bytes: 3712