akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val s = readLine()!!

    var sum = 1
    var current = s[0]
    for (i in 1 until s.length) {
        if (current != s[i]) {
            current = s[i]
            sum++
        }
    }
    println(sum)
}




Measured memory_bytes: 33788
#include <cstdio>

using namespace std;
int a,b,c,d;
int main(){
    scanf("%d%d%d%d",&a,&b,&c,&d);
    int c_1,c_2;
    if(a%d) c_1=a/d+1;
    else c_1=a/d;
    if(c%b) c_2=c/b+1;
    else c_2=c/b;
    printf("%s",c_1>=c_2?"Yes":"No");
    return 0;
}

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

void print(int arr[], int n) {
	for(int i = 0; i < n; i++)
		cout << arr[i] << ' ';
	cout << '\n';
}

int main(void) {
	int n, k, s;
	while(cin >> n >> k >> s, n || k || s) {
		int arr[k];
		long ans = 0;
		for(int i = 0; i < k; i++)
			arr[i] = i+1;
		while(1) {
			//print(arr, k);
			long sum = 0;
			for(int i = 0; i < k; i++)
				sum += arr[i];
			if(sum == s)
				ans++;
			int i;
			for(i = k - 1; i >= 0; i--)
				if(arr[i] < n && arr[i] + k - i - 1 < n) {
					arr[i]++;
					break;
				}
			if(i < 0)
				break;
			for(int j = i + 1; j < k; j++)
				arr[j] = arr[j - 1] + 1;
		}
		cout << ans << '\n';
	}
}

Measured memory_bytes: 1156
#include <iostream>
#include <vector>
using namespace std;
struct WeightUnionFind{
	//
	vector<int> ran,par,wei;
	//
	WeightUnionFind(int n){
		init(n);
	}
	//
	void init(int n){
		for(int i=0;i<n;i++){
			par.push_back(i);
			ran.push_back(0);
			wei.push_back(0);
		}
	}
	//
	int find(int x){
		if(par[x]==x){
			return x;
		}else{
			int r=find(par[x]);
			wei[x]+=wei[par[x]];
			return par[x]=r;
		}
	}
	//
	int weight(int x){
		find(x);
		return wei[x];
	}
	//
	bool same(int x,int y){
		return find(x)==find(y);
	}
	//
	bool unite(int x,int y,int w){
		w+=weight(x);
		w-=weight(y);
		x=find(x);
		y=find(y);
		if(x==y){
			return false;
		}else if(ran[x]<ran[y]){
			swap(x,y);
			w=-w;
		}else if(ran[x]==ran[y]){
			ran[x]++;
		}
		par[y]=x;
		wei[y]=w;
		return true;
	}
	//
	int diff(int x,int y){
		return weight(y)-weight(x);
	}
	//
};
int main(){
	int N,Q;
	cin>>N>>Q;
	WeightUnionFind UF(N);
	while(Q--){
		int C;
		cin>>C;
		if(C==1){
			int X,Y;
			cin>>X>>Y;
			if(UF.same(X,Y)){
				cout<<UF.diff(X,Y)<<endl;
			}else{
				cout<<"?"<<endl;
			}
		}else{
			int X,Y,Z;
			cin>>X>>Y>>Z;
			UF.unite(X,Y,Z);
		}
	}
	return 0;
}


Measured memory_bytes: 4224
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations 
from bisect import bisect_left
def main():
    N = int(readline())
    L = [int(i) for i in readline().split()]
    L.sort()
    sig = 0
    for i in range(N):
        for j in range(i+1, N):
            l = bisect_left(L, L[i]+L[j], j+1)
            sig += l-j-1
    print(sig)
if __name__ == '__main__':
    main()


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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).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; }

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

int main()
{
    int N,M;
    cin >> N >> M;

    vector<set<int> > key;
    rep(i,N)
    {
        int K;
        set<int> tmp;
        cin >> K;
        rep(j, K)
        {
            int tmp2;
            cin >> tmp2;
            tmp.insert(tmp2);
        }
        key.push_back(tmp);
    }
    int ans = 0;
    rep(i,M)
    {
        bool flag = true;
        rep(j,key.size())
        {
            if( key[j].find( i+1 ) == key[j].end() ) flag = false;
        }
        if(flag) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);cout.precision(20);}} fast;

/* define */
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) (upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X))
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define ctoi(C) (C-'0')
#define pow2(x) ((long long)((long long)1<<x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1,0,-1,0};
const long long dy[] = {0,1,0,-1};
const long long dx8[] = {1,1,0,-1,-1,-1,0,1};
const long long dy8[] = {0,1,1,1,0,-1,-1,-1};
const long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};
const long long dy9[] = {0,1,1,1,0,-1,-1,-1,0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
long long max(long long x,int y){return max(x,(long long)y);}
long long max(int x,long long y){return max((long long)x,y);}
long long min(long long x,int y){return min(x,(long long)y);}
long long min(int x,long long y){return min((long long)x,y);}

/* liblary */



/* main */

signed main(){
	ll N;
	string s;
	string t;
	cin >> N >> s >> t;
	REP(i,0,N){
		cerr << s.substr(s.size()-1-i) << ' ' << t.substr(0,i+1) << endl;
		if(s.substr(s.size()-1-i) == t.substr(0,i+1)){
			cout << s.size() + t.substr(i+1).size() << endl;
			return 0;
		}
	}
	cout << s.size() + t.size() << endl;
}

Measured memory_bytes: 256
main=print.solve=<<getLine
solve=(\(_,_,_,c)->c).foldl f(1,0,0,0)
f(r,a,b,c)v=case v of
  'A'->(r, g$a+r, b, c)
  'B'->(r, a, g$b+a, c)
  'C'->(r, a, b, g$c+b)
  '?'->(g$r*3, g$a*3+r, g$b*3+a, g$c*3+b)
g x=x`mod`(10^9+7)

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

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  ll d = c - a - b;
  cout << ( ( d > 0 && d * d > 4 * a * b) ? "Yes":"No" ) << endl;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;

int cnt[maxn];

vector<int> v;

int main(){
	int n, k, diff = 0;
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++){
		int a;
		scanf("%d", &a);
		cnt[a]++;
	}

	for(int i = 1; i < maxn; i++){
		if(cnt[i]){
			diff++;
			v.pb(cnt[i]);
		}
	}

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

	int ans = 0;
	for(int i = 0; i < diff - k; i++)
		ans += v[i];

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2168
#include <algorithm>
#include <bitset>
//#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
// namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
// using ll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}

int main() {
    ll A,B;
    cin >> A >> B;
    ll max_ = A + B;
    if(max_<A-B)
        max_ = A - B;
    if(max_<A*B)
        max_ = A * B;
    cout << max_ << endl;
}


Measured memory_bytes: 888
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

ll a[100002];
int main()
{
   ll n,k,cnt=0;
   cin>>n>>k;

    forn(i,n){
    cin>>a[i];
    if(a[i]>=k)
    cnt++;
    }

    cout<<cnt;
}

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

using namespace std;

typedef long long LL;

const int N = 110;

int main()
{
    string s;
    cin >> s;
    int y = 0, m = 0;
    y = (s[0] - '0') * 10 + s[1] - '0';
    m = (s[2] - '0') * 10 + s[3] - '0';

    int yymm = false, mmyy = false;
    if(m > 0 && m <= 12) yymm = true;

    swap(y, m);
    if(m > 0 && m <= 12) mmyy = true;

    if(yymm && mmyy) puts("AMBIGUOUS");
    else if(!yymm && !mmyy) puts("NA");
    else if(yymm) puts("YYMM");
    else if(mmyy) puts("MMYY");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int k;
  string s;
  cin >> k >> s;
  if(k>=s.size()) cout << s << endl;
  else {
    for(int i=0;i<k;i++){
      if(i==k-1){
        cout << s.at(i) << "..." << endl;
      }
      else{
      cout << s.at(i);
      }
    }
  }
}


Measured memory_bytes: 3632
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

int main() {
  int n;
  cin >> n;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    string s = to_string(i);
    if (s.size()%2 == 1) {
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string Replace(string str){
	int a,b;
	string p;
	cin>>a>>b>>p;
	for(int i=0;i<=b-a;i++) str[i+a]=p[i];
	return str;
}

string Reverse(string str){
	int a,b;
	cin>>a>>b;
	for(int i=0;i<=(b-a)/2;i++){
		char c=str[i+a];
		str[i+a]=str[b-i];
		str[b-i]=c;
	}
	return str;
}

void Print(string str){
	int a,b;
	cin>>a>>b;
	for(int i=a;i<=b;i++){
		cout<<str[i];
	}
	cout<<endl;
}

int main(){
	string str;
	int q;
	cin>>str>>q;
	for(int i=0;i<q;i++){
		string s;
		cin>>s;
		if(s=="replace") str=Replace(str);
		if(s=="reverse") str=Reverse(str);
		if(s=="print") Print(str);
	}
	return 0;
}



Measured memory_bytes: 3176
#include<iostream>
using namespace std;
inline long long factorial(long long n) {
	long long r = 1;
	for(; n > 1; n--)
		r *= n;
	return r;
}

long long calc_ord(long n) {
	long long p[8], a;
	for(int i = 0; i < n; i++) {
		cin >> p[i];
	}

	a = 0;
	for(int i = 0; i < n; i++) {
		long long l = 0;
		for(int m = 1; m < p[i]; m++) {
			int s = 1;
			for(int j = 0; j < i; j++) {
				if (p[j] == m) {
					s = 0;
					break;
				}
			}
			l += s;
		}
		a += l * factorial(n - i - 1);
	}
	return a;
}

int main() {
	long long n, a, b;
	
	cin >> n;
	a = calc_ord(n);
	b = calc_ord(n);
	cout << (a > b ? a - b : b - a);
	return 0;
}

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

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

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let s : Vec<char> = read::<String>().chars().collect();
    let mut ans = Vec::new();
    for x in &s {
        match *x {
            '0' => ans.push('0'),
            '1' => ans.push('1'),
            'B' => { 
                ans.pop();
            },
             _ => unimplemented!(),
        }
    }
    for x in &ans {
        print!("{}",x);
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

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

    map<string,int> strings;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        strings[s]++;
    }

    long long ans = 0;
    for(auto& p : strings){
        int pre_ans = p.second;
        ans += (long long) pre_ans*(pre_ans-1)/2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11136
N=int(input())
for h in range(1,3501):
  for n in range(1,3500):
    u=N*h*n
    s=4*h*n-N*n-N*h
    if s==0:continue
    if u%s==0:
      if u//s>0:
        print(h,n,u//s)
        exit()

Measured memory_bytes: 67004
//#include <bits/stdc++.h>
//#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstring>
#include<bitset>

#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)

using namespace std;
typedef long long ll;

#ifdef local
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
    for (auto x: a)
        cout << x << ' ';
    err(args...);
}
template<typename T, typename... Args>
void err(T a, Args... args) {
    cout << a << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif

const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const long double eps = 1e-6;
const int mod = 998244353;
const int maxn = 3e6;
const int N = 1e5+5;
const int M = 1e5+5;
const int NN = 1e3+5;

int _ = 0;
void testcase() {
    cout << "Case " << (++_) << ": ";
//    printf("Case %d: ", ++_);
}

typedef pair<int,int> pii;

//int dp[30][30];
//
//int getsg(int i, int j){
//    if(~dp[i][j])return dp[i][j];
//    vector<int> mex;
//    for(int k = 1; k <= i/2; ++k){
//        mex.PB(getsg(i-2*k, j+k));
//    }
//    for(int k = 1; k <= j/2; ++k){
//        mex.PB(getsg(i+k, j-2*k));
//    }
//    int &ans = dp[i][j];
//    ans = mex.size();
//    sort(mex.begin(), mex.end());
//    rep(k,mex.size()){
//        if(k != mex[k]){
//            ans = k;
//            break;
//        }
//    }
//    return ans;
//}


void work() {
//    mset(dp,-1);
//    dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
//    for(int i = 0; i <= 10; ++i){
//        for(int j = 0; j <= 10; ++j){
//            dbg(i,j,getsg(i,j));
//        }
//    }
    ll x, y;
    cin >> x >> y;
    if(x < y) swap(x,y);
    if(x >= y+2){
        cout << "Alice\n";
    }
    else{
        cout << "Brown\n";
    }

}


int main() {
#ifdef local
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // local
    IOS;
//    init();


//     int t;
//
//     cin >> t;
//     for(;t--;)
    work();

    return 0;
}


Measured memory_bytes: 256
import scala.io._

// e.g
// 1 2 3
// val Array(a, b) = readLine.split(" ").map(_.toInt) => Array(1, 2, 3)
// 5
// 1 2 3
// 4 5 6
// 7 8 9
// val lines = Source.stdin.getLines()
// データ個数読み取り
// val n = lines.next().toInt
// データ行n個読み取り
// val data = lines.take(n).map{ line => line.split(" ").map(_.toInt).toList }.toList => List(List(1, 2, 3), List(4, 5, 6), List(7, b, 9))

object Main {
  def main(args: Array[String]): Unit = {
    val n: Int = readLine.toInt
    val lst: List[(Int, Int)] = (1 to n).toList.map((_) => { val Array(a, b) = readLine.split(" ").map(_.toInt); (a, b)} )
    val ans: Int = lst.foldLeft(0)((x, y) => x + y._2 - y._1 + 1)
    println(ans)
  }
}


Measured memory_bytes: 30512
//
// Created by yamunaku on 2020/01/18.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int n;
    cin >> n;
    vector<pair<ll, ll>> p(n);
    rep(i, n){
        ll x, l;
        cin >> x >> l;
        p[i] = {x + l, x - l};
    }
    sort(all(p));
    ll now = -LINF;
    int ans = 0;
    rep(i, n){
        if(now <= p[i].second){
            now = p[i].first;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        int min = p[0];
        int ans = 1;
        for (int i = 1; i < n; i++) {
            if (p[i] < min) {
                ans++;
                min = p[i];
            }
        }
        System.out.println(ans);
    }

}


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

using namespace std;
using ll = long long;

int main() {
	int K;
	cin>>K;
	queue<ll> q;
	ll i = 1;
	while (i < 10) {
		q.push(i++);
	}

	ll x;
	while (K--) {
		x = q.front();
		//cout<<x<<endl;
		q.pop();
		if (x%10 != 0)  {
			q.push(x*10+x%10-1);
		}

		q.push(x*10+x%10);

		if (x%10 != 9) {
			q.push(x*10+x%10+1);
		}
	}

	cout<<x<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

vector<pair<ll,ll>> prime_factorize(ll N){
    vector<pair<ll,ll>> ret;
    for(ll a = 2; a * a <= N; a++){
        if(N % a != 0) continue;
        ll ex = 0;
        while(N % a == 0){
            ex++;
            N /= a;
        }
        ret.push_back({a, ex});
    }
    if(N != 1) ret.push_back({N, 1});
    return ret;
}

ll mod_pow(ll a, ll n, ll mod){
    ll ret = 1;
    while(n > 0){
        if(n & 1) ret = (ret*(a % mod))%mod;
        a = ((a%mod)*(a%mod)) % mod;
        n = n >> 1;
    }
    return ret;
}

ll mod_inv(ll a, ll mod){
    return mod_pow(a, mod-2, mod);
}

int main(){
    constexpr ll mod = 1e9+7;
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];

    vector<vector<pair<ll,ll>>> rec(N);
    map<ll,ll> mp;
    rep(i, 0, N){
        auto vec = prime_factorize(A[i]);
        rec[i] = vec;
        for(auto v : vec){
            if(mp.count(v.first) > 0){
                mp[v.first] = max(mp[v.first], v.second);
            }else{
                mp[v.first] = v.second;
            }
        }
    }

    ll mul = 1;
    for(auto p : mp){
        mul *= mod_pow(p.first, p.second, mod);
        mul %= mod;
    }

    ll ans = 0;
    rep(i, 0, N){
        ll div = 1;
        for(auto v : rec[i]){
            ll pw = mod_pow(v.first, v.second, mod);
            div *= mod_inv(pw, mod);
            div %= mod;
        }
        ans += (mul * div) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1536
N = int(input())
A = [0 for _ in range(N)]
X = [[[] for i in range(2)] for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i][0].append(x)
        X[i][1].append(y)
ans = 0
for i in range(pow(2,N)):
    binary = format(i, 'b').zfill(N)
    flag = True
    honest = 0
    for j in range(N):
        if int(binary[j]) == 0:
            continue
        for x, y in zip(X[j][0], X[j][1]):
            if int(binary[x-1]) != y:
                flag = False
                break
        honest += 1
    if flag:
        ans = max(ans, honest)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;


signed main(){
    int q; cin >> q;
    ll aa[q],bb[q];
    rep(i,q) cin >> aa[i] >> bb[i];
    rep(i,q){
        ll a=aa[i],b=bb[i];
        if(a>b) swap(a,b);
        if(a+1>=b){
            cout << 2*a-2 << endl;
            continue;
        }
        ll x = sqrt(a*b);
        if(x*x==a*b) x--;
        ll ok = 2*x-1;
        if(x*(x+1)>=a*b) ok--;
        cout << ok << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>

int main(int argc, char* argv[])
{
  int N;
  std::cin >> N;

  int s[N];

  for (int i = 1; i <= N; i++) {
    int a;
    std::cin >> a;
    s[a-1] = i;
  }

  for (int i = 0; i < N; i++) {
    std::cout << s[i]<< " ";
  }
  std::cout << std::endl;
}

Measured memory_bytes: 1152
from itertools import groupby
from operator import itemgetter

a = groupby(sorted(input() for _ in range(int(input()))))
a = [(len(tuple(g)), s) for s, g in a]
m = max(a, key=itemgetter(0))[0]
for k, s in a:
  if k == m:
    print(s)


Measured memory_bytes: 31940
#include <bits/stdc++.h>
using namespace std;
map<string,int> b;
char a[255];
int main(){
int n;
cin >> n;
bool ok=1;
int pr=-1;
for(int i=0;i<n;i++){
    string s;
    cin >> s;
    if(b.count(s)>0 || pr!=-1 && pr!=s[0])
        return puts("No")*0;
    pr=s[s.size()-1];
    b[s]=1;
}
    puts(ok?"Yes":"No");
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>

typedef long long ll;
using namespace std;

int main()
{
  int n, a, b;

  cin >> n >> a >> b;

  if (n * a > b) cout << b << endl;
  else  cout << n*a << endl;
  
  return 0;
}


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

int n;
vector<int> l;

int solve();

int main() {
  cin >> n;
  l.assign(2 * n, 0);
  for(int i = 0; i < 2 * n; ++i) cin >> l[i];
  sort(l.begin(), l.end(), greater<int>());
  cout << solve() << endl;
  return 0;
}

int solve() {
  int ans = 0;
  for(int i = 0; i < n; ++i) ans += l[i * 2 + 1];
  return ans;
}

Measured memory_bytes: 256
import sys
import numpy as np
N, K = map(int, sys.stdin.readline().rstrip().split())
A = np.array(list(map(int, sys.stdin.readline().rstrip().split())))
cnt = []

for i in range(41):
    cnt.append(np.count_nonzero(A >> i & 1))

cnt = cnt[::-1]
dp = [[0] * 2 for _ in range(42)]
ans = 0
base = 2**(41 - 1)

for i, c in enumerate(cnt, 1):
    if K >> (41 - i) & 1 == 1:
        dp[i][0] = dp[i - 1][0] + base * (N - c)
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i - 1][0] + base * c, dp[i - 1][1] + base * c,
                           dp[i - 1][1] + base * (N - c))
        else:
            dp[i][1] = dp[i - 1][0] + base * c

    else:
        dp[i][0] = dp[i - 1][0] + base * c
        if dp[i - 1][1] > 0:
            dp[i][1] = max(dp[i - 1][1] + base * c,
                           dp[i - 1][1] + base * (N - c))

    base //= 2

print(max(dp[41][0], dp[41][1]))

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if(A == B) {
    cout << C << endl;
  }
  
  if(A == C) {
    cout << B << endl;
  }
  
  if(C == B) {
    cout << A << endl;
  }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (a, b, c, d) = readLine()!!.split(' ').map { it.toLong() }

    val n = b - a + 1

    var ans = n
    ans -= (b / c) - ((a - 1) / c)
    ans -= (b / d) - ((a - 1) / d)

    val l = lcm(c, d)
    ans += (b / l) - ((a - 1) / l)

    println(ans)
}

private fun gcd(a: Long, b: Long): Long {
    if (b == 0L) return a
    return gcd(b, a % b)
}

private fun lcm(a: Long, b: Long): Long {
    return a * b / gcd(a, b)
}

Measured memory_bytes: 38376
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;

void file_put() {
    freopen("filename.in", "r", stdin);
    freopen("filename.out", "w", stdout);
}

int a[8],b[8]; ll ret=0;

int main() {
//	file_put();
	
	rep(i,1,8) scanf("%d",&a[i]),b[i]=a[i];
	ret=a[2]*2;
	ret+=((ll)a[1]/2+a[4]/2+a[5]/2)*4;
	a[1]&=1,a[4]&=1,a[5]&=1;
	if (a[1]+a[4]+a[5]==2) {
		if (!a[1] && b[1]) ret+=2;
		if (!a[4] && b[4]) ret+=2;
		if (!a[5] && b[5]) ret+=2;
	}
	if (a[1]+a[4]+a[5]==3) ret+=6;
	printf("%lld\n",ret>>1);
	
	return 0;
}



Measured memory_bytes: 256
number=list(map(int,input().split()))
n,m=number[0],number[1]
height=list(map(int,input().split()))
load=[[] for i in range(n+1)]
for i in range(m):
    tmp=list(map(int,input().split()))
    if tmp[1] not in load[tmp[0]]:
        load[tmp[0]].append(tmp[1])
    if tmp[0] not in load[tmp[1]]:
        load[tmp[1]].append(tmp[0])

box=[]
answer=0
for i in range(1,n+1):
    box=[]
    if len(load[i])==0:
        answer+=1
    for j in range(len(load[i])):
        box.append(height[load[i][j]-1])
    if box!=[]:
        if max(box)<height[i-1]:
            answer+=1
print(answer)

Measured memory_bytes: 95936
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1e18
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double n;
    cin >> n;
    long double a[(ll)n + 2];
    ll i;
    bool iszero = false;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] == 0)
            iszero = true;
    }
    if (iszero)
    {
        cout << "0\n";
        exit(0);
    }

    ll Max = 1;

    for (i = 0; i < n; i++)
    {
        if (a[i] > 1e18 || Max * a[i] > 1e18)
        {
            Max = -1;
            break;
        }
        else
            Max = Max * a[i];
    }
    cout << Max << "\n";

    return (0);
}

Measured memory_bytes: 5312
# coding: utf-8
# Your code here!

cand=[0,1]
for i in range(2,32):
    temp=i
    while True:
        temp*=i
        if temp<=1000:
            cand.append(temp)
        else:
            break

cand.sort()

X=int(input())

if X==1000:
    print(1000)
    exit()

for i in range(1,len(cand)):
    if X<cand[i]:
        print(cand[i-1])
        exit()



Measured memory_bytes: 3060
import java.util.*;
class Main {
 
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for(int i = 0; i < n; i++) {
            x[i] = stdIn.nextInt();
        }
        for(int i = 0; i < n; i++) {
            y[i] = stdIn.nextInt();
        }
        for(int p = 1; p <= 3; p++) {
            double dis = 0.0;
            for(int i = 0; i < n; i++) {
                dis += Math.pow(Math.abs(x[i] - y[i]),p);
            }
            System.out.println(Math.pow(dis, 1.0/p));
        }
        int max = 0;
        for(int i = 0; i < n; i++) {
            max = Math.max(max, Math.abs(x[i] - y[i]));
        }
        System.out.println(max);
         
    }
}



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

ll gcd(int a, int b)
{
  if(a < b){
    int tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
  }

  return b;
}

ll mygcd(int a, int b, int c)
{
  int ret = gcd(a, b);
  ret = gcd(ret, c);

  return ret;
}

int main()
{
  ll ans = 0;
  int k;
  cin >> k;

  for(int i = 1; i <= k; i++){
    for(int j = 1; j <= k; j++){
      for(int l = 1; l <= k; l++){
        ans += mygcd(i, j, l);
      }
    }
  }

  cout << ans;

  return 0; 
}


Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC167A
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string T = Console.ReadLine();
            T=T.Remove(T.Length-1,1);
            //Console.WriteLine(T);
            if (T == S)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 25616
#include "bits/stdc++.h"

using namespace std;

const int MOD = int(1e9) + 7;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    size_t N, M;
    cin >> N >> M;
    vector<bool> bad(N + 1);
    for (size_t i = 0; i < M; ++i) {
        int a; cin >> a;
        bad[a] = true;
    }
    vector<int64_t> dp(N + 1);
    dp[0] = 1;
    for (size_t i = 1; i <= N; ++i) {
        if (bad[i]) {
            continue;
        } else {
            if (i == 1) {
                dp[i] = dp[0];
            } else {
                dp[i] = dp[i - 1] + dp[i - 2];
                dp[i] %= MOD;
            }
        }
    }
    cout << dp[N] << "\n";
    return 0;
}


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

using namespace std;
typedef long long ll;

#define out(ans) cout << ans << endl
#define in(n) cin >> n
#define floop(i, N) for (ll i = 0; i < N; i++)
#define floop1(i, N) for (ll i = 1; i <= N; i++)
#define floopi(i, j, N) for (ll j = i + 1; j < N; j++)

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

void solve();

int main()
{
    solve();
}

void solve()
{
    int n, r;
    in(n);
    in(r);
    if (n < 10)
    {
        r += 100 * (10 - n);
    }
    out(r);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
vector<pl> G[MAX_N];
vi cen; //one or two
ll ans = 0;

int search_centroid(int v, int p) {
	int s = 1, m = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		if(p == n) continue;
		int t = search_centroid(n, v);
		s += t;
		MAX(m, t);
	}
	MAX(m, N - s);
	if(m <= N / 2) {
		cen.pb(v);
	}
	return s;
}

int loop(int v, int p, ll c) {
	int tsize = 1;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i].fst;
		ll nc = G[v][i].sec;
		if(p == n) continue;
		tsize += loop(n, v, nc);
	}
	ans += tsize * c * 2;
	return tsize;
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; ll c;
		cin >> a >> b >> c; a--; b--;
		G[a].pb(pl(b, c));
		G[b].pb(pl(a, c));
	}
	search_centroid(0, -1);
	if(sz(cen) == 2) {
		int c1 = cen[0], c2 = cen[1];
		loop(c1, c2, 0);
		loop(c2, c1, 0);
		ll cost;
		rep(i, 0, sz(G[c1])) {
			if(G[c1][i].fst != c2) continue;
			cost = G[c1][i].sec;
		}
		ans += (N - 1) * cost;
	}
	else {
		int c = cen[0];
		loop(c, -1, 0);
		ll cost = inf;
		rep(i, 0, sz(G[c])) {
			MIN(cost, G[c][i].sec);
		}
		ans -= cost;
	}
	cout << ans << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 15616
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int X, N;
    cin >> X >> N;

    set<int> s;
    REP(i, N) {
        int p;
        cin >> p;
        s.insert(p);
    }

    int m = inf;
    int c;
    FOR(i, -1, 105) {
        if (s.count(i) > 0) continue;

        if (abs(i - X) < m) {
            m = abs(i - X);
            c = i;
        }
    }

    print(c);
    
}


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

typedef long long ll;
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define endl '\n'
const int N = 1e5 + 10;
using namespace std;

int main() {
    IO;
    int n, a[N], mx = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    int req = mx / 2, dist = 1e9 + 2, ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == mx) continue;
        if (abs(a[i] - req) < dist) {
            ans = a[i];
            dist = abs(a[i] - req);
        }
    }
    cout << mx << " " << ans << endl;


}


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

int main() {
  string s; cin>>s;
  int size=s.size();
  while (true){
    size-=2;
    string a=s.substr(0,size/2);
    string b=s.substr(size/2,size/2);
    if (a==b){
      cout<<size<<endl;
      break;
    }
  }
}

Measured memory_bytes: 256
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define popb pop_back
#define mt make_tuple 
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second 
#define ull unsigned long long  
#define pii pair<int, int>
#define piii pair<int,pii>
#define beg begin
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define int ll
using ll = long long;
const int N = 3*1e5 +5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using namespace std;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#endif


void solve()
{
    int n , m ;
    cin >> n >> m ;
    int maxl = 0 , minr = inf ;
    rep(i,m){
        int l,r ;
        cin >> l >> r; 
        maxl = max(maxl,l) ;
        minr = min(minr, r) ;
    }
    cout << max(0ll, minr-maxl+1) ;
}   

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        //cout << endl ;
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i, a, b) for(long long i=a; i<=b; ++i)
#define REPN(i, a, b) for(long long i=a; i<=b; --i)
#define rep(i, a, b) for(long long i=a; i<b; ++i)
#define rep0(i,b) for(long long i=0; i<b; ++i)
#define REP0(i,b) for(long long i=0; i<=b; ++i)
#include<cmath>
#include <iomanip>
using namespace std;


typedef long long ll;

int MODE = 1e9+7;
ll ans;


class Node
{
public:

    ll value;
    Node *next;


    Node(ll value)
    {
        this->value = value;
        next = nullptr;
    }
};


class LinkedList
{
public:
    Node *head = nullptr;
    Node *tail = nullptr;

    void insertAtTail(ll value)
    {
        Node *node = new Node(value);
        if(head == nullptr)
        {

            head = node;
            tail = node;
            return ;
        }
        else
        {
            tail->next = node;
            tail = node;
            return ;
        }

    }


    void show()
    {
        Node *temp = head;

        while(temp != nullptr)
        {
            cout<<temp->value<<" ";
            temp = temp->next;
        }
        cout<<endl;
    }


};





int main()
{

    int n;
    cin>>n;
    ll dp[n][n];
    memset(dp, -1, sizeof(dp));
    ll arr[n];
    rep0(i, n)
    {
        cin>>arr[i];
    }
    ll prefix[n+1];
    prefix[0] = 0;
    rep0(i, n+1)
    {
        prefix[i] = prefix[i-1] + arr[i];
    }
    for(int i=0; i<n; ++i)
    {
        dp[i][i] = 0;
    }


    for(int i=n-2; i>=0; --i)
    {

        for(int j=i+1; j<n; ++j)
        {
            dp[i][j] = 1e18+5;
            ll s =  prefix[j] - prefix[i-1];           
            for(int k = i; k<j; ++k)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s);
            }
        }
    }


    /*for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            cout<<dp[i][j]<<"\t";
        }
        cout<<endl;
    }*/


    cout<<dp[0][n-1]<<endl;



    return 0;

}


Measured memory_bytes: 4852
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll a, b, c;
  char x;
  cin >> a >> b >> x >> c;
  b = b*100+c;
  print(a*b/100);
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
int gcd(int a,int b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

//重みある時
using Edge = pair<int,int>;
using Graph = vector<vector<Edge> >;

int main() {
    int n,m;
    cin >> n >> m;
    ll ans = 0;
    priority_queue<int> pq;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pq.push(a);
    }
    while(m--){
        int tmp = pq.top();
        pq.pop();
        tmp /= 2;
        pq.push(tmp);
    }
    while(!pq.empty()){
        int tmp2;
        tmp2 = pq.top();
        pq.pop();
        ans += tmp2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

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

	return gcd(b, a % b);
}

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


int main()
{
	int N;
	ll M;
	cin >> N >> M;

	auto l = 1ll;
	vector<ll> a(N);
	for (auto i = 0; i < N; ++i)
	{
		cin >> a[i];
		a[i] /= 2;
		l = lcm(l, a[i]);
	}

	for (auto i = 0; i < N; ++i)
	{
		if (l / a[i] % 2 == 0)
		{
			l = M + 1;
			break;
		}
	}

	auto ans = (M / l + 1) / 2;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
a = sum(A)

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

if A[0] != 0:
    print(-1)
    exit()

B = [0]*(N+1)  #深さiの頂点数のmax
B[0] = 1

for i in range(1,N+1):
    B[i] = min(a,B[i-1]*2-A[i])
    if B[i] < 0:
        print(-1)
        exit()

ans = A[N]

r = A[N]
for i in range(N-1,-1,-1):
    ans += A[i] + min(B[i],r)
    r = A[i]+min(B[i],r)

print(ans)

Measured memory_bytes: 83392
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int,input().split())) for i in range(M)]
BC.sort(key = lambda x:-x[1])

index = 0
l = len(A)

for i in range(len(BC)):
    for j in range(BC[i][0]):
        if index == l or A[index] >= BC[i][1]:
            break
        else:
            A[index] = BC[i][1]
            index += 1

print(sum(A))
    


Measured memory_bytes: 36088
import java.util.Scanner;

public class Main {
	
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        long A = sc.nextLong();
        
        if (A == 3 || A == 5 || A == 7) {
        	System.out.println("YES");
        } else {
        	System.out.println("NO");
        }
    }

}	

Measured memory_bytes: 22996
N, K = list(map(int, input().split(' ')))

A=[0]*N
D=[0]*K
for i in range(K):
  D[i]=int(input())
  a=list(map(int, input().split(' ')))
  for index in a:
    A[index-1]=A[index-1]+1
    
print(A.count(0))

Measured memory_bytes: 9212
N,*A = map(int,open(0).read().split())
#A：次に光るボタン

P =[0]+[0 for i in range(N)]#各ボタンを押した回数

a = 1 #現在光っているボタン

for i in range(1,N+1):
  P[a]+=1
  a = A[a-1]
  if P[a]>1:
    print(-1)
    exit()
  if a == 2:
    print(i)
    exit()

Measured memory_bytes: 59952
#include <stdio.h>

int main(void)
{
    int N, A, B, t;

    scanf("%d %d %d", &N, &A, &B);

    t = N * A;

    if (t <= B)
    {
        printf("%d", t);
    } else
    {
        printf("%d", B);
    }

    return 0;
}

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

using namespace std;

int main (void) {
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());

    if ( s < t )
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256