akhauriyash/Code-Regression huggingface dataset:
#ifdef LOCAL_BUILD
#include "pch.h"
#define DLOG(msg) cout << "#" << __LINE__ << ":" << msg << endl;
#else
#include <bits/stdc++.h>
#define DLOG(msg)
#endif
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> nums;
  int max_ = 0;
  for (int t, i = 0; i < n; ++i) {
    cin >> t;
    nums.push_back(t);
    max_ = max(max_, t);
  }
  int limit = 1;
  for (; limit * limit < max_; ++limit) {
  }
  vector<bool> primes(max_ + 1, true);
  for (int i = 2; i <= limit; ++i) {
    if (primes[i]) {
      for (int j = i + i; j <= max_; j += i) {
        primes[j] = false;
      }
    }
  }
  int count = 0;
  for (auto&& num : nums) {
    if (primes[num]) {
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 15276
#include <bits/stdc++.h>
#include <cctype>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, std::less<>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//*/998244353;
const int base = 2187;
const double eps = 1e-9;
const int N = 300'000;
const int LOGN = 60;

int n, m, k;

int b[N][LOGN];

void solve(int) {
  int64 k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> b[i][0];
    --b[i][0];
  }
  for (int i = 1; i < LOGN; ++i) {
    for (int j = 0; j < n; ++j) {
      b[j][i] = b[b[j][i - 1]][i - 1];
    }
  }
  int v = 0;
  for (int j = LOGN - 1; j >= 0; --j) {
    if (k - (1ll << j) >= 0) {
      k -= (1ll << j);
      v = b[v][j];
    }
  } 
  cout << v + 1 << '\n';
}

void precalc() {
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i) {
    solve(i);
  }
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}




Measured memory_bytes: 50516
#include <bits/stdc++.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int main() {
  double r;
  cin>>r;
  cout<<2*r*3.141592<<endl;
  return 0;
}


Measured memory_bytes: 3796
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
 
using namespace std;

int main()
{
	long long sum=0;
	long long n,m;
	scanf("%lld%lld",&n,&m);
	while(m--)
	{
		long long x;
		scanf("%lld",&x);
		sum=sum+x;
	}
	
	if(n-sum>=0)
	{
		printf("%lld",(n-sum));
	}
	else
	{
		printf("-1");
	}
	return 0;
 } 

Measured memory_bytes: 3828
#include "bits/stdc++.h"
#define YES "YES"
#define Yes "Yes"
#define NO "NO"
#define No "No"
#define YESNO OUT(three(solve(),YES,NO))
#define YesNo OUT(three(solve(),Yes,No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int long long
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<ppr, Vppr, greater<ppr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,1,1,-1,-1,0 }, dy[] = { 1,0,-1,0,1,-1,1,-1,0 };
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 4010;
const int SIZE3 = 305;
const int SIZE = SIZE1;
const LL p = 998244353;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut N, M, K, X, L, Y, H, W, Q, D,T;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], nums[SIZE], maps[SIZE2][SIZE2], answer = zero;
LL A[SIZE];
LL dist[SIZE2][SIZE2];
LL solve() {
	int N, M;
	cin >> N >> M;
	string s;
	queue<pr> qu;
	EFOR(i, 1, N){
		cin >> s;
		EFOR(j, 1, M) {
			maps[i][j] = s[j - 1] == '#';
			maps[i][j]++;
			if (maps[i][j] == 2) {
				qu.emplace(i, j);
				dist[i][j] = 1;
			}
		}
	}
	int maxim = 1;
	while (!qu.empty()) {
		pr now = qu.front();
		int y = now.first;
		int x = now.second;
		qu.pop();
		REP(i, 4) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			if (dist[ny][nx] == 0 and maps[ny][nx]) {
				qu.emplace(ny,nx);
				dist[ny][nx] = dist[y][x] + 1;
				MX(maxim, dist[ny][nx]);
				
			}
		}
	}
	cout << maxim - 1 << endl;
	return 0;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	solve();
	//	cin >> N;
	return 0;
}


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

namespace Q2
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            int N = int.Parse(line);
            line = Console.ReadLine();
            string[] strs = line.Split(' ');
            List<int> W = new List<int>();
            for (int i = 0; i < N; i++) W.Add(int.Parse(strs[i]));
            //W.Sort();
            int min = 10001;
            for(int i = 0; i < N; i++)
            {
                var left = 0;
                var right = 0;
                for(int j = 0; j <= i; j++)
                {
                    left += W[j];
                }
                for (int j = i+1; j < N; j++)
                {
                    right += W[j];
                }
                var abs = Math.Abs(left - right);
                if (min > abs) min = abs;
            }

            Console.WriteLine(min);
        }
    }
}


Measured memory_bytes: 11220
// Pratiyush Mishra(pratiush7)
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define repab(i,a,b) for(ll i=a;i<=b;i++)
#define ull unsigned long long int
#define ll long long int
#define LL_MAX 9223372036854775807
#define pb push_back
#define pf push_front
#define mp make_pair
#define popb pop_back
#define vl vector<ll>
#define bs(v,x) binary_search(v.begin(),v.end(),x)
#define popf pop_front
#define p() cout<<'\n'
#define p0(x) cout<<x<<" "
#define p1(x) cout<<x<<'\n'
#define p2(x,y) cout<<x<<" "<<y<<'\n'
#define p3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'
#define pr1(x) cout<<fixed<<setprecision(15)<<x<<'\n'
#define mod 1000000007
#define mod1 998244353
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define get(n) ll n;cin>>n
#define getvec(v,n) vector<ll> v(n);for(ll i=0;i<n;i++) cin>>v[i];
#define getstr(s) string s;cin>>s
#define all(x) x.begin(),x.end()
#define countBits(x) __builtin_popcount (x)
using namespace std;

int main(){
  fio;
  get(n);
  vector<string> s;vl t;
  rep(i,n){
    getstr(title);get(time);
    s.pb(title);
    t.pb(time);
  }
  getstr(x);
  ll index;
  rep(i,n){
    if(x==s[i])
      index=i;
  }
  ll ans=0;
  repab(i,index+1,n-1)
    ans+=t[i];
  p1(ans);
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] a = new int[N];
		int[] b = new int[N];
		sc.fill(a, b);
		int[] c = new int[M];
		int[] d = new int[M];
		sc.fill(c, d);

		for (int i = 0; i < N; i++) {
			int index = -1;
			int distance = Integer.MAX_VALUE;
			for (int j = 0; j < M; j++) {
				int tmp = Math.abs(a[i] - c[j]) + Math.abs(b[i] - d[j]);
				
				if (tmp < distance) {
					distance = tmp;
					index = j + 1;
				}
			}
			// output
			System.out.println(index);
		}
	}

	private static boolean isDebug = System.getProperty("sun.desktop") != null;

	private static void debug(Object... o) {
		if (isDebug) {
			System.err.println(Arrays.deepToString(o));
		}
	}

	public static class Scanner {
		private BufferedInputStream inputStream;

		public Scanner(InputStream in) {
			inputStream = new BufferedInputStream(in);
		}

		public int nextInt() throws IOException {
			int num = 0;
			int sign = 1;

			int read = skip();
			if (read == '-') {
				sign = -1;
				read = inputStream.read();
			}

			do {
				num = num * 10 + sign * (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public void fill(int[] a) throws IOException {
			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
			}
		}

		public void fill(int[] a, int[] b) throws IOException {
			if (a.length != b.length) {
				throw new IllegalArgumentException();
			}

			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
				b[i] = nextInt();
			}
		}

		public long nextLong() throws IOException {
			long num = 0;

			int read = skip();
			do {
				num = num * 10 + (read - 0x30);
			} while ((read = inputStream.read()) > 0x20);

			return num;
		}

		public void fill(long[] a) throws IOException {
			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
			}
		}

		public void fill(long[] a, long[] b) throws IOException {
			if (a.length != b.length) {
				throw new IllegalArgumentException();
			}

			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
				b[i] = nextLong();
			}
		}

		public long[] nextLong(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++) {
				array[i] = nextLong();
			}

			return array;
		}

		public String next() throws IOException {
			StringBuilder builder = new StringBuilder();

			int read = skip();
			do {
				builder.append((char) read);
			} while ((read = inputStream.read()) > 0x20);

			return builder.toString();
		}

		private int skip() throws IOException {
			int read;
			while ((read = inputStream.read()) <= 0x20)
				;

			return read;
		}
	}
}


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

int main() {
	int N, Ai;
	set<int> A;
	cin >> N;
	for (int i = 0; i<N; i++) {
		cin >> Ai;
		A.insert(Ai);
	}
	cout << (A.size() == N ? "YES" : "NO") << endl;
	return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
  	ll n, p;
  	cin >> n >> p;
	string s;
  	cin >> s;
  	reverse(all(s));
	
  	if(p == 2 || p == 5){
      	ll ans = 0;
      	rep(i,n){
        	if((s[i]-'0')%p == 0){
            	ans += n-i;
            }
        }
      	cout << ans << endl;
		return;
    }
  
  	vll amari(n); 	// amari[i] = 10^i を p で割った余り
  	amari[0] = 1;
  	vll data(n);	// data[i] 
	data[0] = (s[0]-'0') % p;
  	rep(i,n-1){
    	amari[i+1] = (10*amari[i]) % p;
		data[i+1] = (data[i] + (s[i+1]-'0') * amari[i+1]) % p;
    }
  
  	/*
  	rep(i,n){
      	cout << i << ": " << amari[i] << " " << data[i] << endl;
    }
    //*/
  
    vll cnt(p,0);
  	cnt[0]++;
  	rep(i,n){
    	cnt[data[i]]++;
    }
  	
  	/*
    rep(i,p) cout << cnt[i] << " ";
  	cout << endl;
  	//*/
  	
  	ll ans = 0;
  	rep(i,p){
    	ans += cnt[i]*(cnt[i]-1)/2;
    }
  	cout << ans << endl;
	return;
}

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

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

const int maxM=100010;
string S[maxM];

int main(){
    int N,M;
    cin >> N >> M;
    int nums[M];
    for(int i=0;i<M;i++){
        cin >> nums[i] >> S[i];
    }
    bool acc[N+1];
    int was[N+1];
    fill(acc,acc+N+1,false);
    fill(was,was+N+1,0);
    int numac=0, numwa=0;
    for(int i=0;i<M;i++){
        if(acc[nums[i]]) continue;
        if(S[i]=="AC"){
            numac++;
            numwa+=was[nums[i]];
            acc[nums[i]]=true;
        }
        else if(S[i]=="WA"){
            was[nums[i]]++;
        }
    }
    cout << numac << " " << numwa << endl;
    return 0;

}

Measured memory_bytes: 6528
#include <stdio.h>
#include <string.h>
int main() {
    int kata; 
	char huruf[100];
    scanf("%d", &kata);
    scanf("%s", huruf);
    int sLen = strlen(huruf);
    if(sLen > kata) {
        for(int i = 0; i < kata; i++) {
            printf("%c", huruf[i]);
        }
        printf("...\n");
    } else {
        printf("%s", huruf);
    }
    return 0;
}

Measured memory_bytes: 1708
#include<iostream>
#include<string>
#include<algorithm>

static const int N = 1000;
#define INF (1 << 20)

int p[N];
int m[N][N];

int main() {
    int n; std::cin >> n;
    for(int i = 1; i <= n; i++) {
        std::cin >> p[i-1] >> p[i];
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            m[i][j] = 0;
        }
    }
    for(int l = 2; l <= n; l++) {
        for(int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = INF;
            for(int k = i; k <= j - 1; k++) {
                m[i][j] = std::min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
            }
        }
    }
    std::cout << m[1][n] << std::endl;
    return 0;
}


Measured memory_bytes: 7000
h,w,d = gets.split.map(&:to_i)
a = Array.new(h*w+1)
h.times do |y|
  gets.split.map(&:to_i).each_with_index do |v,x|
    a[v] = [y,x]
  end
end

def dist(a,b)
  (a[0]-b[0]).abs + (a[1]-b[1]).abs
end

dp = Array.new(h*w+1, 0)
1.upto(h*w) do |i|
  dp[i] = dp[i-d] + dist(a[i],a[i-d]) if 0 < i - d
end

q = gets.to_i
q.times do
  start, goal = gets.split.map(&:to_i)
  ans = dp[goal] - dp[start]
  puts ans
end

Measured memory_bytes: 11516
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  ll n, a, b;
  cin >> n >> a >> b;
  ll c = n/(a+b);
  ll d;
  if(n- (c*(a+b)) <= a) d = n-(c*(a+b));
  else d = a;
  cout <<  c*a + d << endl;
  system("pause");
}


Measured memory_bytes: 504
#include<iostream>
using namespace std;
string S;
char R;
int main(){
  cin >> S;
  int count =0;
  if ((S[0]=='R') && (S[1]=='R') && (S[2]=='R')){
    count =3;
  }
  else if (((S[0]=='R') && (S[1]=='R')) || ((S[1]=='R') && (S[2]=='R'))){
    count =2;
  }
  else if ((S[0]=='R') || (S[1]=='R') || (S[2]=='R')){
    count =1;
  }
  else {
    count =0;
  }
  cout << count <<endl;
}
  




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

int main(){
  
  int N;
  int count = 0;
  bool hantei ;
  int min;
  
  cin >> N;
  vector<int> suuretu(N);
  
  for(int i = 0; i < N; i++){
  	cin >> suuretu.at(i);}
  
  min = suuretu.at(0);
  
  for(int i = 0; i < N; i++){    
    
    if(min >= suuretu.at(i)){
    	min = suuretu.at(i);
    	count++;}
        
  }
  
  cout << count << endl;

}

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

double PI = 3.141592653589793238462643383279;

int main() {
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    
    double Mangle = m / 60 * 2 * PI;
    double Hangle = (60 * h + m) / 12 / 60 * 2 * PI;

    double radian = max(Hangle, Mangle) - min(Hangle, Mangle);

    double ans = sqrt(a * a + b * b - 2 * a * b * cos(radian) );

    printf("%.10lf\n", ans);
    return 0;
}

Measured memory_bytes: 4264
import itertools
N = int(input())
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x, y))

s = 0
c = 0
for x in itertools.permutations(X):
    for i in range(N-1):
        s += ((x[i][0] - x[i+1][0]) ** 2 + (x[i][1] - x[i+1][1]) ** 2) ** 0.5
    c += 1

print(s / c)

Measured memory_bytes: 3188
#include <cmath>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> status(n, false);
    int wa = 0;
    int ca = 0;
    int p;
    string s;
    for (int i = 0; i < m; i++) {
        cin >> p >> s;
        p--;
        if (status[p] >= 0) {
            if (s == "WA") {
                status[p]++;
            } else {
                ca++;
                wa += status[p];
                status[p] = -1;
            }
        }
    }
    cout << ca << " " << wa << endl;
    return 0;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(long long i=(l);i<(r);i++)
#define dec(i, l, r)   for(long long i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    LL x, y;cin >> x >> y;
    if(abs(x-y) <= 1){
        cout << "Brown" << endl;
    }else{
        cout << "Alice" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define REL

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <cassert>
#include <complex>
#include <stack> 
#include <random>

using namespace std;

typedef int64_t i64;
typedef long long LL;
typedef long long ll;
typedef long double LD;
typedef complex <LD> cld;
typedef unsigned int uint;
typedef complex <double> cd;
typedef unsigned long long ULL;

#define endl "\n"
#define dendl "\n\n"
#define mp make_pair
#define mt make_tuple
#define size(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

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

template <typename T>
T sqr(T a) {
	return a * a;
}

template <typename T>
int sign(T a) {
	if (a == 0)
		return 0;
	return (a > 0 ? 1 : -1);
}

template <typename T>
bool uax(T& a, const T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T>
bool uin(T& a, const T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <typename T1, typename T2>
istream& operator >> (istream& in, pair<T1, T2>& p) {
	in >> p.first >> p.second;
	return in;
}

template <typename T1, typename T2>
ostream& operator << (ostream& out, pair<T1, T2>& p) {
	out << p.first << ' ' << p.second;
	return out;
}

mt19937_64 rnd(0);

const int LOG = 64;
const int N = (int)1e5 + 7;
const int MAXN = (int)3e3 + 7;
const int MOD = (int)998244353;
const int INF = (int)1e9 + 7;
const int CONST = 450;
const LL LINF = (i64)1e18;
const LD PI = 3.1415926535897932384626433832795;
const LD EPS = 1;

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

int n, m, ans[N];
vector <int> gr[N];

void solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	queue <int> q;
	q.push(0);
	int cnt = 0;
	fill(ans + 1, ans + n, INF);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		cnt++;
		for (int v : gr[u]) {
			if (ans[v] == INF) {
				ans[v] = u;
				q.push(v);
			}
		}
	}
	if (cnt != n) {
		cout << "No";
		return;
	}
	cout << "Yes\n";
	for (int i = 1; i < n; i++)
		cout << ans[i] + 1 << endl;
}

int main() {
	double start = clock();
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
#else
	cout << fixed << setprecision(20);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	rnd.seed(time(0));
#endif

	int t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}

#ifdef _DEBUG
	cout << endl << "Time is " << (clock() - start) / 1000.0;
#endif
}

Measured memory_bytes: 10620
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i=1; i<=9; i++) {
            for(int j=1; j<=9; j++) {
                if(i*j == n) {
                    System.out.println("Yes");
                    return;
                }
            }
        }

        System.out.println("No");

    }


}


Measured memory_bytes: 21972
#include <stdio.h>

int main() {
	int n, m, h[200000], dd[200010] = { 0 }, ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &h[i]);
	}
	for (int i = 0; i < m; i++) {
		int s, t;
		scanf("%d%d", &s, &t);
		if (h[s-1] >= h[t-1])dd[t]++;
		if (h[s-1] <= h[t-1])dd[s]++;
	}
	for (int i = 1; i <= n; i++) {
		if (dd[i] == 0)ans++;
	}
	printf("%d", ans);
	return 0;
}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define V vector<int>
#define M map<int,int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int,V,greater<int>>

#define pb(a) push_back(a)
#define mp make_pair

#define dump(x)  cout << #x << " = " << (x) << "\n";
#define COUT(x) cout<<(x)<<"\n"

int main()
{
	int n = 0;
	cin >> n;
	vector<int> num(n);
	REP(i, n)
	{
		cin >> num[i];
	}
	int ans = INF;

	REP(i, n)
	{
		int buf = 0;
		int buf1 = 0;
		for (int j = 0; j < n; j++)
		{
			if (j <= i)
			{
				buf += num[j];
			}
			else
			{
				buf1 += num[j];
			}
		}
		int diff = abs(buf - buf1);
		ans = min(ans, diff);
	}


	COUT(ans);

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int a[10];
	for(int i = 0; i < 10; i++) {
		scanf("%d\n", a+i);
	}
	sort(a,a+10);
	printf("%d\n%d\n%d\n",a[9],a[8],a[7]);
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main()
{
    Hello
    int n;
    cin >> n;
    if(n >= 30) cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 3552
import Control.Applicative ((<$>))

main :: IO ()
main = solve <$> map read <$> words <$> getLine >>= print

solve :: [Int] -> Int
solve [a, b, c, x, y]
  | a + b <= 2 * c = a * x + b * y
  | x > y && a > 2 * c = 2 * c * x
  | x > y = 2 * c * y + (x - y) * a
  | b > 2 * c = 2 * c * y
  | otherwise = 2 * c * x + (y - x) * b


Measured memory_bytes: 508
#include<bits/stdc++.h>
#define maxn 500100
using namespace std;
typedef long long ll;
struct Data{
	ll sz,sum,ans,id;
	Data(){}
	Data(ll sz,ll sum,ll ans,ll id):sz(sz),sum(sum),ans(ans),id(id){}
	bool operator<(const Data& d)const{return sum*d.sz>d.sum*sz;}
}d[maxn];
int n,fa[maxn],f[maxn],val[maxn],c0,id[maxn];
priority_queue<Data>Q;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;++i)
		scanf("%d",&fa[i]);
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<=n;++i)scanf("%d",&val[i]),c0+=val[i]==0,id[i]=i;
	sort(id+2,id+n+1,[](int a,int b){return val[a]<val[b];});
	for(int i=1;i<=n;++i){
		d[id[i]]=Data(1,val[id[i]],val[id[i]],id[i]);
		if(id[i]>1)Q.push(d[id[i]]);
	}
	while(Q.size()){
		Data nw=Q.top();
		Q.pop();
		if(d[nw.id].sz!=nw.sz)continue;
		int x=nw.id;
		x=f[x]=find(fa[x]);
		d[x].ans+=nw.ans+d[x].sz*nw.sum;
		d[x].sz+=nw.sz;
		d[x].sum+=nw.sum;
		if(x!=1)Q.push(d[x]);
	}
//	printf("[%d]",d[1].ans);
	printf("%lld",1ll*n*(n+1)/2-d[1].ans-1ll*c0*(c0+1)/2);
}

Measured memory_bytes: 23660
N, M, C = map(int, input().split())
b_list = list(map(int, input().split()))

a_list = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for a_ in a_list:
    pro = 0
    for a, b in zip(a_,b_list):
        pro += a * b
    if pro+C >0:
        ans += 1
    
print(ans)


Measured memory_bytes: 3060
/*
  This C++ Source Is
  Writen By syksykCCC
  (2020)
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for(register int i = x; i < y; i++)
#define REP(i, x, y) for(register int i = x; i <= y; i++)
#define per(i, x, y) for(register int i = x; i > y; i--)
#define PER(i, x, y) for(register int i = x; i >= y; i--)
#define repl(i, x, y) for(register long long i = x; i < y; i++)
#define REPL(i, x, y) for(register long long i = x; i <= y; i++)
#define perl(i, x, y) for(register long long i = x; i > y; i--)
#define PERL(i, x, y) for(register long long i = x; i >= y; i--)
#define LLL __int128
#define int128 __int128
#define DEBUG(x) cerr << #x << " : " << x << endl
using namespace std;
typedef unsigned int uint;
typedef long long int64;
typedef long long LL;
typedef unsigned long long uint64;
typedef long long ULL;
typedef long double LLF;
template<typename T> inline void read(T &val)
{
	val = 0; char c = getchar(); int f = 1;
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { val = (val << 3) + (val << 1) + (c ^ 48); c = getchar(); }
	val *= f;
}
template<typename T> void write_(T val) { if(!val) return; write_(val / 10); putchar(val % 10 + 48); }
template<typename T> inline void write(T val)
{
	if(val == 0) putchar(48);
	else if(val < 0) { putchar('-'); write_(-val); }
	else write_(val);
}

const int N = 2e5 + 5;
int n, a[N], pos[N], tmp[N], lis[N];
int ans[N];
vector<int> G[N];

void dfs(int u)
{
	if(a[u] > lis[lis[0]])
	{
		tmp[u] = 0;
		pos[u] = ++lis[0];
		lis[pos[u]] = a[u];
	}
	else
	{
		pos[u] = lower_bound(lis + 1, lis + lis[0] + 1, a[u]) - lis;
		tmp[u] = lis[pos[u]];
		lis[pos[u]] = a[u];
	}
	ans[u] = lis[0];
	for(int v : G[u])
	{
		if(ans[v]) continue;
		dfs(v);
	}
	lis[pos[u]] = tmp[u];
	if(!tmp[u]) lis[0]--;
}

int main()
{
#ifdef LOCAL
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin >> n;
	REP(i, 1, n) cin >> a[i];
	rep(i, 1, n)
	{
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	REP(i, 1, n) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 31932
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto X = readln.chomp;
    int s, r;
    foreach (c; X) {
        if (c == 'S') {
            ++s;
        } else if (s > 0) {
            --s;
        } else {
            ++r;
        }
    }
    writeln(s + r);
}

Measured memory_bytes: 2556
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int[] weights = new int[n];
        long[] values = new long[n];

        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
            values[i] = scanner.nextLong();
        }

        long[][] dp = new long[n][w + 1];
        System.out.println(maxValue(weights, values, dp, w, n - 1));
    }

    public static long maxValue(int[] weights, long[] values, long[][] dp, int w, int n) {

        if (n == -1) {
            return 0;
        }

        if (dp[n][w] > 0) {
            return dp[n][w];
        }

        long rp = -1;
        //放
        if (weights[n] <= w) {
            rp = maxValue(weights, values, dp, w - weights[n], n - 1) + values[n];
        }
        //不放
        long rnp = maxValue(weights, values, dp, w, n - 1);

        dp[n][w] = Math.max(rp, rnp);
        return dp[n][w];
    }
}

Measured memory_bytes: 125524
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#define MOD 1000000007
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
int n,q;
P a[214514];
vector<int> t[214514];
int sum[214514]={};
void tansaku(int s){
    for(int i=0;i<t[s].size();i++){
        sum[t[s][i]]+=sum[s];
        tansaku(t[s][i]);
    }
    return;
}
signed main(){
    cin>>n>>q;
    for(int i=0;i<n-1;i++){
        cin>>a[i].first>>a[i].second;
        if(a[i].second<a[i].first)swap(a[i].first,a[i].second);
        a[i].first--;
        a[i].second--;
        t[a[i].first].push_back(a[i].second);
    }
    for(int i=0;i<q;i++){
        int p,x;
        cin>>p>>x;
        sum[p-1]+=x;
    }
    tansaku(0);
    for(int i=0;i<n-1;i++){
        cout<<sum[i]<<" ";
    }
    cout<<sum[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 27776
import itertools
n,m,x = map(int,input().split())
c = []
a = []
tmp = 0
ans = []
for i in range(n):
    tmp = list(map(int,input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])

num = [0,1]
p = itertools.product(num,repeat = n)

for i in p:
    tmp = [0 for i in range(m)]
    tmpans = 0
    for j in range(len(i)):
        if i[j] == 1:
            tmpans += c[j]
            for k in range(m):
                tmp[k] += a[j][k]
    if min(tmp) >= x:
        ans.append(tmpans)
if ans:
    print(min(ans))
else:
    print(-1)

Measured memory_bytes: 68804
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int q;
  cin >> q;
  ll bsum = 0;
  multiset< tuple< ll, int > > st;
  int s, ai, bi;
  cin >> s >> ai >> bi;
  st.insert(make_tuple(ai, 0));
  bsum += bi;
  auto itr = st.begin();
  ll diffsum = 0;

  for (int i=1; i<q; ++i) {
    int s;
    cin >> s;
    if (s==1) {
      ll ai, bi;
      cin >> ai >> bi;
      st.insert(make_tuple(ai, i));
      diffsum += abs(get<0>(*itr)-ai);
      if (st.size()%2==0 && get<0>(*itr) > ai) {
        itr--;
      }
      else if (st.size()%2==1 && get<0>(*itr) <= ai) {
        itr++;
        auto new_itr = itr;
        new_itr--;
        //cout << get<0>(*new_itr) << "/" << get<0>(*itr) << endl;
        diffsum += get<0>(*(new_itr--)) - get<0>(*itr);
      }
      bsum += bi;

      //cout << bsum << "+" << diffsum << endl;
      //cout << get<0>(*itr) << " " << bsum + diffsum << endl;
    } else {
      //cout << bsum << " " << diffsum << endl;
      cout << get<0>(*itr) << " " << bsum + diffsum << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 12800
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	sBytes := []byte(s)
	ok := true
	for i, s := range sBytes {
		if s == 'U' || s == 'D' {
			continue
		}

		if (i%2 == 0 && s == 'R') ||
			(i%2 == 1 && s == 'L') {
			continue
		}
		ok = false
	}

	if ok {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
n,a,b=map(int,input().split())
s=input()
cnt_a=0
cnt_b=0
for i in range(n):
  if s[i]=="a":
    if cnt_a+cnt_b<a+b:
      cnt_a+=1
      print("Yes")
    else:
      print("No")
  elif s[i]=="b":
    if cnt_a+cnt_b<a+b and cnt_b<b:
      cnt_b+=1
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Measured memory_bytes: 9196
var stdin = require("fs").readFileSync("/dev/stdin", "utf8");

//console.log(stdin)
var a =  stdin.split("\n")
var s = a[0]
var t = a[1]

var s_length=s.length
var t_length=t.length
var diff=s_length-t_length

var array =[]

//console.log(diff)

for (let i = 0, scope_length=t.length ; i <= diff; i++, scope_length++){
var slice=s.slice(i, scope_length)
//var slice=s.slice(0,1)
//console.log(slice)
//console.log(t_length)
if(slice===t){
array.push(0)
// console.log(0)
}
else{
  var sum = 0
 for (let c = 0, k = 1; c <=t_length; k++, c++){
   var slice2=slice.slice(c,k)
   var slice3= t.slice(c,k)
   //console.log(slice2);
  // console.log(slice3);
   if(slice2!==slice3){
     sum ++;
     //console.log(sum);
   }

 }
array.push(sum)
}

}
console.log(array.reduce((a,b)=>Math.min(a,b)))


Measured memory_bytes: 32344
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
long long int mod = (long long int)1000000007;
using namespace std;

void solve()
{
    ll i,j,k,n;
    std::cout.precision(10);
    int yes=0;
    cin>>n;
    ll curr=1;
    ll sub=0;
    ll len=0;
    // while(curr*(ll)26<n)
    // {
        
    //     curr*=(ll)26;
    //     sub+=curr;
    //     len++;
    // }
    
    // len++;
    // n-=sub;
    
   
    string p="";
    while(n>0)
    {
        n-=1;
        p+=('a'+n%26);
        n/=26;
    }
    reverse(p.begin(),p.end());
    cout<<p;
    
  
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int i,j,k;
    int t;
    std::cout.precision(10);
    t=1;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,c,k,t[N];
int main()
{
	scanf("%d%d%d",&n,&c,&k);
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	sort(t+1,t+n+1);
	int ans=0;
	for (int i=1;i<=n;){
		int last=i;
		while (t[last]+k>=t[i]&&i<last+c&&i<=n) i++;
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


struct edge{int to;ll cap;int rev;};
struct Dinic{
private:
    int n;
    vector<vector<edge>> v;
    vector<int> dist,iter;
public:
    Dinic(int sz):n(sz),v(sz),dist(sz),iter(sz){}
    
    void addedge(int from,int to,ll cap){
        int x=v[to].size(),y=v[from].size();
        v[from].push_back({to,cap,x});
        v[to].push_back({from,0,y});
    }
    
    void bfs(int s){
        fill(dist.begin(),dist.end(),-1);
        queue<int> q;
        dist[s]=0;
        q.push(s);
        while(q.size()){
            int x=q.front();q.pop();
            rep(i,v[x].size()){
                edge &e=v[x][i];
                if(e.cap>0&&dist[e.to]<0){
                    dist[e.to]=dist[x]+1;
                    q.push(e.to);
                }
            }
        }
    }
    
    ll dfs(int x,int t,ll f){
        if(x==t)return f;
        for(int& i=iter[x];i<(int)v[x].size();++i){
            edge& e=v[x][i];
            if(e.cap>0&&dist[x]<dist[e.to]){
                ll d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    v[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }

    ll max_flow(int s,int t){
        ll flow=0;
        while(1){
            bfs(s);
            if(dist[t]<0)return flow;
            fill(iter.begin(),iter.end(),0);
            ll f;
            while((f=dfs(s,t,1LL<<62))>0)flow+=f;
        }
    }
};
int main(){
    int n;
    cin>>n;
    Dinic dn(n+2);
    ll ans = 0;
    rep(i,n){
        int x;cin>>x;
        if(x>0){
            ans += x;
            dn.addedge(n, i, x);
        }
        else dn.addedge(i, n+1, -x);
    }
    rep(i,n){
        for(int j=2*i+2;j<=n;j+=i+1){
            dn.addedge(j-1, i,longinf);
        }
    }
    cout<<ans - dn.max_flow(n, n+1)<<endl;
    return 0;
}

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

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

  double n, m, d;
  cin >> n >> m >> d;
  if (d == 0) cout << setprecision(20) << (m - 1) / n << endl;
  else cout << setprecision(20) << (m - 1) * 2 * (n - d) / n / n << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();

    Integer a[] = new Integer[N];
    for(int i = 0; i < N ; i++){
      a[i] = sc.nextInt();
    }
    Arrays.sort(a, Comparator.reverseOrder());

    a[0] = a[0]/2;

    int sum = 0;

    for(int i = 0; i < N; i++){
      sum += a[i];
    }
    System.out.println(sum);
}
}

Measured memory_bytes: 21844
#include <iostream>
#include<vector>
#define INF 100000001
using namespace std;

int main() {
	int n,m;
	cin>>n>>m;
	vector<int>coin(m+1),dp(n+1,INF);
	dp[0]=0;
	for(int i=0;i<m;++i){
		cin>>coin[i];
	}
	for(int i=0;i<m;++i){
		for(int j=0;j+coin[i]<=n;++j){
			dp[j+coin[i]]=min(dp[j+coin[i]],dp[j]+1);
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}


Measured memory_bytes: 3184
S = input()
X,Y = map(int, input().split())

cnt_T = 0
cnt = 0

step_X = []
step_Y = []
sx = 0
sy = 0
for s in S:
    if s == "F":
        cnt += 1
    else:
        if cnt_T == 0:
            sx = cnt
            cnt = 0
            cnt_T += 1
        elif cnt_T % 2 == 0:
            step_X.append(cnt)
            cnt = 0
            cnt_T += 1
        else:
            step_Y.append(cnt)
            cnt = 0
            cnt_T += 1



if cnt_T == 0:
    sx = cnt
    cnt = 0
    cnt_T += 1
elif cnt_T % 2 == 0:
    step_X.append(cnt)
    cnt = 0
    cnt_T += 1
else:
    step_Y.append(cnt)
    cnt = 0
    cnt_T += 1


dp_X = set()
dp_X.add(sx)
for i in step_X:
    tmp = set()
    for x in dp_X:
        tmp.add(x + i)
        tmp.add(x - i)
    dp_X = tmp

dp_Y = set()
dp_Y.add(sy)
for i in step_Y:
    tmp = set()
    for y in dp_Y:
        tmp.add(y + i)
        tmp.add(y - i)
    dp_Y = tmp

if X in dp_X and Y in dp_Y:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 3944
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

const long long LL_INF = (long long) 2e18 + 5;

int N;
vector<long long> A, prefix_sum;
vector<vector<long long>> dp;
vector<vector<int16_t>> opt;

int main() {
    scanf("%d", &N);
    A.resize(N);
    prefix_sum.assign(N + 1, 0);

    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        prefix_sum[i + 1] = prefix_sum[i] + A[i];
    }

    dp.assign(N + 1, vector<long long>(N + 1, LL_INF));
    opt.assign(N + 1, vector<int16_t>(N + 1, -1));

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

    // Knuth optimization: opt[i][j - 1] <= opt[i][j] <= opt[i + 1][j].
    for (int i = N - 1; i >= 0; i--)
        for (int j = i + 2; j <= N; j++)
            for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
                long long candidate = dp[i][k] + dp[k][j] + prefix_sum[j] - prefix_sum[i];

                if (candidate < dp[i][j]) {
                    dp[i][j] = candidate;
                    opt[i][j] = k;
                }
            }

    printf("%lld\n", dp[0][N]);
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main()
{
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    int x = max(X, Y);
    int n = min(X, Y);
    int c2 = C * 2;

    int ans = min(A * X + B * Y, c2 * x);
    ans = min(ans, c2 * n + A * max(0, X - n) + B * max(0, Y - n));
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#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;


#define NUM 1005

enum Type{
	finish_same,
	finish_another,
};

ll N,K;
ll const MOD = 1000003;
ll dp1[2][NUM][NUM];
ll dp2[NUM];
ll dp3[NUM];
ll fact[NUM];

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}


void init_dp(){

	for(int i = 0; i <= N; i++){
		dp2[i] = 0;
		dp3[i] = 0;
		for(int k = 0; k <= N; k++){
			dp1[finish_same][i][k] = 0;
			dp1[finish_another][i][k] = 0;
		}
	}
}

void func(){

	ll ans = 0;

	if(K >= N){
		K = N-1;
		ans = 2;
	}

	init_dp();

	dp1[finish_same][1][1] = 1;
	dp1[finish_another][1][1] = 0;

	for(int len = 2; len <= N; len++){

		for(int i = 1; i <= K; i++){
			dp1[finish_another][len][1] += dp1[finish_same][len-1][i];
			dp1[finish_another][len][1] %= MOD;
		}
		for(int i = 2; i <= K; i++){
			dp1[finish_another][len][i] += dp1[finish_another][len-1][i-1];
			dp1[finish_another][len][i] %= MOD;
		}

		for(int i = 1; i <= K; i++){
			dp1[finish_same][len][1] += dp1[finish_another][len-1][i];
			dp1[finish_same][len][1] %= MOD;
		}
		for(int i = 2; i <= K; i++){
			dp1[finish_same][len][i] += dp1[finish_same][len-1][i-1];
			dp1[finish_same][len][i] %= MOD;
		}
	}

	for(int len = 1; len <= N; len++){

		for(int i = 1; i <= K; i++){
			dp2[len] += dp1[finish_another][len][i];
			dp2[len] %= MOD;
		}
	}

	for(int len = 1; len <= N; len++){
		for(int i = 1; i < K; i++){
			dp1[finish_another][len][i+1] += dp1[finish_another][len][i];
			dp1[finish_another][len][i+1] %= MOD;
		}
	}

	for(ll len = 1; len <= N; len++){
		for(int p = 1; p <= min(len,K); p++){
			dp2[len] += dp1[finish_another][len-p][K-p];
			dp2[len] %= MOD;
		}
	}

	for(int len = 1; len <= N; len++){
		dp3[len] = (2*dp2[len])%MOD;
		for(int i = 2; i < len; i++){
			if(len%i != 0)continue;

			dp3[len] -= dp3[i];
			dp3[len] = (dp3[len]+MOD)%MOD;
		}
	}


	for(int cycle_len = 1; cycle_len <= N; cycle_len++){
		if(N%cycle_len != 0)continue;

		ans += dp3[cycle_len]*mod_inverse(cycle_len,MOD);
		ans %= MOD;
	}

	printf("%lld\n",ans);
}

int main(){

	fact[0] = 1;
	for(ll i = 1; i < NUM; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	while(true){
		scanf("%lld %lld",&N,&K);
		if(N == 0 && K == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 18876
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct knife
{
	long long k;
	long long ff;
};
knife f[100001];
int cmp(knife a,knife b)
{
	if(a.ff==b.ff)
	{
		return a.k>b.k;
	}
	return a.ff>b.ff;
}
int main()
{
	long long n,h,ans=0,tmp=0;
	scanf("%lld %lld",&n,&h);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld %lld",&f[i].k,&f[i].ff);
		tmp=max(tmp,f[i].k);
	}
	sort(f+1,f+1+n,cmp);
	long long tot=0;
	for(long long i=1;i<=n;i++)
	{
		if(f[i].ff>tmp)
		{
			ans+=f[i].ff;
			tot++;
		}
		if(ans>=h)
		{
			printf("%lld\n",tot);
			return 0;
		}
	}
	long long a=(h-ans)/tmp;
	long long b=(h-ans)%tmp;
	if(b==0) printf("%lld\n",a+tot);
	else printf("%lld\n",a+tot+1);
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>

int main()
{
    int w, h, x, y, r;

    std::cin >> w >> h >> x >> y >> r;

    int x1, x2, y1, y2;

    x1 = x + r;
    x2 = x - r;
    y1 = y + r;
    y2 = y - r;

    if (x1 >= 0 && x1 <= w && x2 >= 0 && x1 <= w && y1 >= 0 && y1 <= h && y2 >= 0 && y2 <= h)
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }

    return 0;
}



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

for i in range(M):
  p, y = map(int, input().split())
  D[p-1].append((y, i)) #市ごとにリストに入れる．この時，元の順番をタプルの1番目の要素として入れておく
    
ans = [None]*M

for i, d in enumerate(D): #enumerateは要素の中身とインデックス番号を持ってこれる．print(i, d)で確認
  d.sort()
  for k, (y, j) in enumerate(d): #こちらも同様．(y, j)となっているため，yには年数が，jには元の順番の情報が入る
    ans[j] = str(i+1).zfill(6) + str(k+1).zfill(6) #ans[j]に12桁の認識番号を挿入

print(*ans, sep = '\n') 
#普通にprint(ans)とするとリストが出力される
#print(*ans)とすると，リストの要素がスペース区切りで出力される
#printのオプションsepで，文字の区切りをスペース出なく，改行に指定

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

int main() {
  int n;
  ll k,ans = 0,mod = 1000000000+7;
  cin >> n >> k;
  vector<int>a(n);
  for(int i = 0;i < n;i++) cin >> a[i];
  for(int i = 0;i < n;i++){
    ll p = 0,b = 0;
    rep(i+1,j,n)if(a[i]>a[j])b++;
    rep(0,j,n)if(a[i]>a[j])p++;
    ans+=b*k%mod;
    ans%=mod;
    ans+=k*(k-1)/2%mod*p%mod;
    ans%=mod;
  }
  cout << ans << endl;
}

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

const double PI=3.14159265358979323846;

double calc_th(int h, int m) {
  return abs(30.0 * h + 0.5 * m - 6.0 * m);
}

int main() {
  int a, b, h, m;
  cin >> a >> b >> h >> m;

  double th = calc_th(h, m);
  double x = a * a + b * b
    - 2 * a * b * cos(PI / 180 * th);
  cout << fixed << setprecision(15) << sqrt(x) << endl;
}


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

int main() {
	
	int A, B;
	cin >> A >> B;

	if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0) {

		cout << "Possible" << endl;

	}
	else {

		cout << "Impossible" << endl;

	}

	return 0;
}

Measured memory_bytes: 764
#include <cstdio>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
int N; char t[12]; long long ans;
string ts; map<string, long long> s;
int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%s", t); ts = string(t);
    sort(ts.begin(), ts.end());
    s[ts]++;
  }
  for(auto x : s) {
    ans += x.second*(x.second-1)/2;
  }
  printf("%ld", ans);
}

Measured memory_bytes: 11136
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sum_a = sum(a)
for i in range(n):
    tmp = min(a[i], b[i])
    a[i] -= tmp
    b[i] -= tmp
    tmp = min(a[i + 1], b[i])
    a[i + 1] -= tmp
    b[i] -= tmp
ans = sum_a - sum(a)
print(ans)

Measured memory_bytes: 19156
#include <iostream>
#include <queue>

using namespace std;

static const int N=100;
static const int INF=-1;
int M[N][N],n;
int d[N];

void bfs(int s){
  queue<int> q;
  q.push(s);

  for(int i=0;i<n;i++){
    d[i]=INF;
  }

  d[s]=0;

  while(!q.empty()){
    int u=q.front();
    q.pop();
    for(int v=0;v<n;v++){
      if(M[u][v]==0) continue;
      if(d[v]!=INF) continue;
      d[v]=d[u]+1;
      q.push(v);
    }
  }
}

int main(){
  cin>>n;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j]=0;
    }
  }

  int u,k,v;

  for(int i=0;i<n;i++){
    cin>>u>>k;
    u--;
    for(int j=0;j<k;j++){
      cin>>v;
      v--;
      M[u][v]=1;
    }
  }

  bfs(0);

  for(int i=0;i<n;i++){
    cout<<i+1<<" "<<((d[i]==INF)?(-1):d[i])<<endl;
    }
  return 0;
}

Measured memory_bytes: 3132