akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <ll M = MOD> struct modint {
    ll val;
    modint(const ll x = 0) : val(x) {
        val = x;
        while(val < 0) val += M;
        while(val > M) val -= M;
    }

    modint operator+(const modint a) const { return modint(*this) += a; }
    modint operator-(const modint a) const { return modint(*this) -= a; }
    modint operator*(const modint a) const { return modint(*this) *= a; }
    modint operator/(const modint a) const { return modint(*this) /= a; }
    modint operator-() const { return modint(M-val); }
    modint inv() const {
        ll u = 1, v = 0, s = 0, t = 1, m = M, x = val;
        while (x) {ll q = m/x; swap(s -= q*u, u); swap(t -= q*v, v); swap(m -= q*x, x); }
        if(s < 0) s += M;
        return modint(s);
    }
    modint pow(ll n) const {
        ll u = 1, xx = val;
        while (n > 0){ if (n&1) u = u * xx % M; xx = xx * xx % M; n >>= 1; }
        return modint(u);
    }
    modint& operator+=(const modint a){ val += a.val; if(val >= M) val -= M; return *this; }
    modint& operator-=(const modint a){ val -= a.val; if(val < 0) val += M; return *this; }
    modint& operator*=(const modint a){ val = val * a.val % M; return *this; }
    modint& operator/=(const modint a){ val = val * a.inv().val % M; return *this;}

    modint& operator=(const int& x){
        val = x;
        while(val < 0) val += M;
        while(val > M) val -= M;
        return *this;
    }
};


class Factorial {
    using mint = modint<MOD>;
    vector<mint> facts, factinv;

public:
    explicit Factorial(int n) : facts(static_cast<u32>(n+1)), factinv(static_cast<u32>(n+1)) {
        facts[0] = 1;
        for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*mint(i);
        factinv[n] = facts[n].inv();
        for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1);
    }

    mint fact(int k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }

    mint operator[](const int &k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }

    mint C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[q] * factinv[p-q];
    }

    mint P(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[p-q];
    }

    mint H(int p, int q) const {
        if(p < 0 || q < 0) return 0;
        return q == 0 ? 1 : C(p+q-1, q);
    }
};


using mint = modint<MOD>;

int main() {
    int x, y;
    cin >> x >> y;
    mint ans = 0;
    Factorial f(x+y);
    for (int i = 0; i <= x; ++i) { // (1, 2)
        if(x-i == (y-2*i)*2) { // (2, 1)
            ans += f.C(i+y-2*i, i);
        }
    }
    cout << ans.val << "\n";
    return 0;
}

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

int n, m;
vector<int> a, b;
vector<int> flags(10);
vector<vector<int>> table(10, vector<int>(10));

int recurse(int num) {

    int flag = 1;
    for (int i = 1; i <= n && flag; i++) flag = flags[i];
    if (flag) return 1;
 
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (table[num][i] && !flags[i]) {
            flags[i] = 1;
            sum += recurse(i);
            flags[i] = 0;
        }
    }

    return sum;
}

int main() {
    cin >> n >> m;
    a.resize(m); b.resize(m);
    for(int i = 0; i < m; i++) cin >> a[i] >> b[i];
    for(int i = 0; i < m; i++) table[a[i]][b[i]] = table[b[i]][a[i]] = 1;
    flags[1] = 1;
    int ans = recurse(1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
  cout << endl;
}
signed main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
  }
  vvi b(20, vi(n));
  for(int i=0;i<n;++i) {
    for(int j=0;j<20;++j) {
      b[j][i] = (a[i]>>j) & 1;
    }
  }
  vvi r(20, vi(n));
  for(int i=0;i<20;++i) {
    int now = n;
    int prev = n;
    for(int j=n-1;j>=0;--j) {
      if(b[i][j]) {
        prev = now;
        now = j;
      }
      r[i][j] = prev-1;
    }
  }
  vi mi(n);
  for(int i=0;i<n;++i) {
    int tmp = INF;
    for(int j=0;j<20;++j) {
      tmp = min(tmp, r[j][i]);
    }
    mi[i] = tmp;
  }
  ll ans = 0;
  for(int i=0;i<n;++i) {
    ans += mi[i] - i + 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 33136
#include<iostream>
#include<cstring>

using namespace std;

int main() {
	
	char A[1201];
	
	while( cin.getline(A,1201)) {
	
	for(int i=0;i<strlen(A);i++) {
		
		if( A[i] > 96 && A[i] < 123 )
		A[i] -= 32;
		else if( A[i] > 64 && A[i] < 91 )
		A[i] += 32;
		
	}
	
	cout << A << "\n";
}
	return 0;
}


Measured memory_bytes: 3088
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

signed main(void)
{
  int n, a, b;
  cin >> n >> a >> b;
  int ret = n;
  REP(i, n) {
    int t;
    cin >> t;
    if(a <= t && t < b) ret--;
  }
  cout << ret << endl;

  return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll inf = 1e6+5;
typedef pair<int, bool> pib;

int main() {
    int n,m; cin >> n >> m;
    int tp = 0;
    int total = 0;
    for (int i = 0; i < n; i++){
        int cur; cin >> cur; tp += cur;
        if (tp <= m){
            total++;
        }
        else{
            break;
        }
    }
    cout << total+1;
}



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

using namespace std;

mt19937_64 mt_rnd_64(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
    return (mt_rnd_64() % (r - l + 1)) + l;
}
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

#define rall(x) (x).rbegin(), (x).rend()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const ll INF = 1e9;

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

    ll n;
    cin >> n;
    string a;
    cin >> a;
    if (n % 2) {
        cout << "No" << endl;
        return 0;
    }
    for (ll i = 0; i < n / 2; ++i) {
        if (a[i] != a[i + n / 2]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
using namespace std;
struct knapSack{
    long long val;
    long long wt;
};
long long solve(vector<knapSack> ar,int n,int w)
{
    vector<vector<long long >> dp(n+1,vector<long long >(w+1,0));
    /*for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= w;j++)
            {
                cout<<dp[i][j]<<" ";
            }
            cout<<"\n";
        }*/
    for(int i = 1;i <= n;i++)
    {
        long long currentWeight = ar[i-1].wt;
        long long currentVal = ar[i-1].val;
        //cout<<currentWeight<<" "<<currentVal<<"\n";
        for(int j = 1;j < w+1;j++)
        {
            if(currentWeight > j)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],(dp[i-1][j-currentWeight] + currentVal));
        }
    }
    /*for(int i = 0;i < n;i++)
    {
        for(int j = 0;j <= w;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    return dp[n][w];
}
int main() {
    int n,w;
    cin>>n>>w;
    vector<knapSack> ar(n);
    for(int i = 0;i < n;i++)
        cin>>ar[i].wt>>ar[i].val;
    cout<<solve(ar,n,w);
}

Measured memory_bytes: 83144
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template < typename T > string tost( const T& n ) { ostringstream stm; stm << n; return stm.str();}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
int const INF = 1001001001;


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

string S;
cin >> S;
if(S[2] == S[3] && S[4] == S[5]) cout << "Yes" << endl;
else cout << "No" << endl;

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector> 
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <cerrno>
#include <stdio.h>
#include <stdlib.h>
#include <cfenv>
#include <stack>
#include <math.h>
#include <iomanip>
#include <limits>
#include <queue>
#define ll long long int
#define pb push_back
#define mp make_pair
#define MOD 2019

using namespace std;

int main(){

    int N;
    cin >> N;

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

    ll ans = 0;

    for(int i=0;i<N;i++){
        while(vec[i]%2==0){
            ans++;
            vec[i]/=2;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int toInt(string s){
  int res = 0;
  for(int i=0;i<s.size();i++){
    int k;
    if(isalpha(s[i]))k = 1;
    else k = s[i++] - '0';
    int b = 1;
    if(s[i] == 'm')b = 1000;
    if(s[i] == 'c')b = 100;
    if(s[i] == 'x')b = 10;
    res += k*b;
  }
  return res;
}

string toMCXI(int a){
  string res;
  string u[] = {"m","c","x","i"};
  int b = 1000;

  for(int i=0;i<4;i++){
    int k = a/b;
    if(k==1)res += u[i];
    else if(k)res += (char)('0'+k) + u[i];
    a -= k*b;
    b /= 10;
  }
  return res;
}

int main(){
  int n;
  string s1,s2;
  
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s1 >> s2;
    cout << toMCXI( toInt(s1) + toInt(s2) ) << endl;
  }
}

Measured memory_bytes: 1208
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<algorithm>
using namespace std;

int main(){
	int x,y,z;
	cin>>x>>y>>z;
	x-=z;
	y+=z;
	x/=y;
	cout<<x;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int i = 1;
  long sum = 0;
  while(i <= N) {
    if (i%15 != 0 && i%5 != 0 && i%3 != 0) {
      sum += i;
    }
    i++;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3156
#include <stdio.h>

int main(void){
  unsigned long a_in,b_in,
                a = 0,b = 0,
                a_,b_;
  while(feof(stdin) == 0){
    scanf("%u %u\n",&a,&b);
    a_in = a;
    b_in = b;
    if(a < b){
      a_ = a;
      a = b;
      b = a_;
    }
    while(b != 0){
      b_ = a % b;
      a = b;
      b = b_;
    }
    printf("%u %u\n",a,(unsigned long long)a_in * (unsigned long long)b_in /a);
  }
  return 0;
}

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

int main() {
  int h,w;
  cin>>h>>w;
  vector<string> vec(h);
  for(int i=0;i<h;i++){
    cin>>vec.at(i);
  }
  int a=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(vec.at(i).at(j)!='#'){
        a++;
      }
    }
    if(a==w){
      for(int j=0;j<w;j++){
        vec.at(i).at(j)='@';
      }
    }
    a=0;
  }
  for(int i=0;i<w;i++){
    for(int j=0;j<h;j++){
      if(vec.at(j).at(i)!='#'){
        a++;
      }
    }
    if(a==h){
      for(int j=0;j<h;j++){
        vec.at(j).at(i)='@';
      }
    }
    a=0;
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(vec.at(i).at(j)!='@'){
        cout<<vec.at(i).at(j);
      }
    }
    cout<<endl;
  }  
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main()
{
    char s[100];
    long i,n;
    
    scanf("%s",s);
    n=strlen(s);
    for(i=0;i<n;i++)
    {
        printf("x");
    }
    printf("\n");
    
    
    return 0;
}


Measured memory_bytes: 128
n = int(input())
a = list(int(x) for x in input().split(" "))
center = sum(a) / 2

sum = 0
diff = float('inf')
for x in a:
    if abs(sum + x - center) > diff:
        break
    sum += x
    diff = abs(sum - center)

print(int(diff * 2))


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

typedef long long ll;

ll cnt(int n) {
  return 1LL * n * (n - 1) / 2;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  int a[n];
  vector<int> freq(n + 1, 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    ++freq[a[i]];
  }
  ll tot = 0;
  for (int i = 1; i <= n; i++) {
    tot += cnt(freq[i]);  
  }
  for (int i = 0; i < n; i++) {
    cout << tot - freq[a[i]] + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 4224
import java.util.*;

class Reader {
  Scanner sc = new Scanner(System.in);

  public int ini() {
    return sc.nextInt();
  }

  public int[] vi(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = sc.nextInt();
    return a;
  }
}

public class Main extends Reader {
  public static void main(String[] args) {
    Main main = new Main();
    main.show(main.solve());
  }

  int x;
  int n;
  int[] a;

  public Main() {
    x = ini();
    n = ini();
    a = vi(n);
  }
  
  int solve() {
    int ans = 0;
    int mini = x;
    int cnt[] = new int[102];
    for (int i = 0; i < n; i++) cnt[a[i]] = 1;
    for (int i = 0; i <= 101; i++) {
      if (cnt[i] != 0) continue;
      int dist = Math.abs(i - x);
      if (dist < mini) {
        mini = dist;
        ans = i;
      }
    }
    return ans;
  }

  int calc(int left, int right) {
    int ans = 0;
    for (int i = left; i <= right; i++) {
      ans += i;
    }
    return ans;
  }

  void show(int ans) {
    System.out.println(ans);
  }
}


Measured memory_bytes: 35512
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

x = 0
y = 0
for i in range(n):
    a = A[i]
    b = B[i]
    if a > b:
        y += a - b
    elif a < b:
        diff = b - a
        if diff % 2 == 0:
            x += diff // 2
        else:
            x += diff // 2 + 1
            y += 1
#print(x, y)
if x >= y:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 4596
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, z = 0;
    string s;
    cin >> n >> s;
    for (int i = 1 ; i < n ; i++) {
    	string a = s.substr(0, i), b = s.substr(i, n - i);
    	int c[26] = {}, d[26] = {}, e = 0;
    	for (int j = 0 ; j < i ; j++) c[a[j] - 'a'] = 1;
        for (int j = 0 ; j < n - i ; j++) d[b[j] - 'a'] = 1;
        for (int j = 0 ; j < 26 ; j++) if (c[j] && d[j]) e++;
        z = max(z, e);
	}
	cout << z;
}

Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int n, l, m=0, sum=0; 
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> l;
		m=max(m, l);
		sum+=l;
	}
	sum-=m;
	if(m<sum){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

using namespace std;

struct UnionFind {
  UnionFind(int32_t n)
      : parent(vector<int32_t>(n, 0)), size(vector<int32_t>(n, 0)) {
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      size[i] = 1;
    }
  }

  int32_t Root(int32_t a) {
    if (parent[a] == a) {
      return a;
    } else {
      return parent[a] = Root(parent[a]);
    }
  }

  bool IsSame(int32_t a, int32_t b) { return Root(a) == Root(b); }

  void Unite(int32_t a, int32_t b) {
    a = Root(a);
    b = Root(b);

    if (a == b) return;

    if (size[a] > size[b]) {
      parent[b] = a;
      size[a] += size[b];
      size[b] = 0;
    } else {
      parent[a] = b;
      size[b] += size[a];
      size[a] = 0;
    }
  }

  int32_t Size(int a) { return size[Root(a)]; }

  vector<int32_t> parent;
  vector<int32_t> size;
};  // struct UnionFind

struct Edge {
  int from;
  int to;
};

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  UnionFind uf(N + 10);
  vector<vector<Edge>> friends(N);
  vector<vector<Edge>> enemies(N);
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    friends[A].emplace_back(Edge{A, B});
    friends[B].emplace_back(Edge{B, A});
    uf.Unite(A, B);
  }
  for (int i = 0; i < K; i++) {
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    enemies[A].emplace_back(Edge{A, B});
    enemies[B].emplace_back(Edge{B, A});
  }

  for (int i = 0; i < N; i++) {
    int answer = uf.Size(i) - 1;
    for (const Edge& e : friends[i]) {
      if (uf.IsSame(i, e.to)) {
        answer--;
      }
    }
    for (const Edge& e : enemies[i]) {
      if (uf.IsSame(i, e.to)) {
        answer--;
      }
    }
    cout << answer;
    if (i + 1 < N) cout << " ";
    else cout << endl;
  }

  return 0;
}


Measured memory_bytes: 14028
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
const ll INF = 1145148931919810;
int main(){
    map<char, ll> m;
    for(ll i = 0; i < 26; i++) m['A' + i] = i;
    ll dist[26][26];
    for(ll i = 0; i < 26; i++)for(ll j = 0; j < 26; j++) dist[i][j] = (i == j ? 0 : INF);
    ll h, w;
    char start, goal;
    cin >> h >> w >> start >> goal;
    string s[h];
    for(ll i = 0; i < h; i++) cin >> s[i];
    for(ll i = 0; i < h; i++){
        char now;
        bool st = 0;
        for(ll j = 0; j < w; j++){
            if('A' <= s[i][j] && s[i][j] <= 'Z'){
                if(st){
                    dist[m[now]][m[s[i][j]]] = dist[m[s[i][j]]][m[now]] = 1;
                    st = 0;
                }
                now = s[i][j];
            }else if(s[i][j] == '-'){
                st = 1;
            }
        }
    }
    for(ll i = 0; i < w; i++){
        char now;
        bool st = 0;
        for(ll j = 0; j < h; j++){
            if('A' <= s[j][i] && s[j][i] <= 'Z'){
                if(st){
                    dist[m[now]][m[s[j][i]]] = dist[m[s[j][i]]][m[now]] = 1;
                    st = 0;
                }
                now = s[j][i];
            }else if(s[j][i] == '|'){
                st = 1;
            }
        }
    }
    //for(ll i = 0; i < 26; i++)for(ll j = i + 1; j < 26; j++) cout << (char)('A' + i) << ", " << (char)('A' + j) << ": " << dist[i][j] << endl;
    for(ll k = 0; k < 26; k++)for(ll i = 0; i < 26; i++)for(ll j = 0; j < 26; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    cout << dist[m[start]][m[goal]] << endl;
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  
  sort(L.begin(), L.end());
  
  int sum = 0;
  for (int i = 0; i < N-1; i++) {
    sum += L.at(i);
  }
  
  if (sum > L.at(N-1)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

  


Measured memory_bytes: 256
k = int(input())
a = [7] * (10 ** 7)
if k == 2:
    print(-1)
    exit()
for i in range(10 ** 7-1):
    a[i] %= k
    if a[i] == 0:
        print(i + 1)
        exit()
    a[i + 1] = a[i] * 10+7
print(-1)

Measured memory_bytes: 141864
#!/usr/bin/ruby
class Fixnum
	def pow_binary_mod(y)
		x = self
		z = 1
		while y != 0
			while y % 2 == 0
				x = x * x % 1000000007
				#y = y / 2
				y = y >> 1
			end
			y = y - 1
			z = z * x % 1000000007
		end
		z
	end
end
x,y=gets.split.map(&:to_i)
p x.pow_binary_mod(y)

Measured memory_bytes: 6100
package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"os"
	"strconv"
)

func main() {
	n, d := readInt(), readInt()
	ans := 0
	for i := 0; i < n; i++ {
		x, y := readInt(), readInt()
		if x*x+y*y <= d*d {
			ans++
		}
	}
	fmt.Println(ans)
}

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	log.SetFlags(log.Lshortfile)
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readInt() int {
	return int(readInt64())
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


Measured memory_bytes: 4904
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


int main() {
    int n, m;
    while(true) {
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        vector<int> h_vec, w_vec;
        unordered_map<int, int> heights, widths;
        for(int i = 0; i < n; i++) {
            int h; cin >> h;
            h_vec.emplace_back(h);
        }
        for(int i = 0; i < m; i++) {
            int w; cin >> w;
            w_vec.emplace_back(w);
        }
        for(int i = 0; i < n; i++) {
            int h = 0;
            for(int j = i; j < n; j++) {
                h += h_vec[j];
                heights[h]++;
            }
        }
        for(int i = 0; i < m; i++) {
            int w = 0;
            for(int j = i; j < m; j++) {
                w += w_vec[j];
                widths[w]++;
            }
        }
        int ans = 0;
        for(const auto h : heights) {
            auto search = widths.find(h.first);
            if(search != widths.end()) {
                ans += h.second*search->second;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 29960
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

ll modadd(ll x, ll y) {
    return ((x + y) % mod + mod) % mod;
}

ll modminus(ll x, ll y) {
    return (x - y + mod) % mod;
}

ll multiply(ll x, ll y) {
    return (x % mod) * (y % mod) % mod;
}

ll modpower(ll x, ll y) {
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % mod;
    } else if (y % 2 == 0) {
        ll p = modpower(x, y / 2);
        return p * p % mod;
    } else {
        ll p = modpower (x, y / 2);
        return (p * p) % mod * (x % mod) % mod;
    }
}

ll divide(ll x, ll y) {
    return multiply(x, modpower(y, mod - 2));
}

ll frac[1000000];
ll invfrac[1000000];

void fracinvfrac(ll n) {
    frac[0] = 1;
    for (int i = 1; i <= n; i++) {
        frac[i] = multiply(frac[i - 1], i);
    }
    invfrac[n] = divide(1, frac[n]);
    for (int i = n - 1; i >= 0; i--) {
        invfrac[i] = multiply(invfrac[i + 1], i + 1);
    }
}

ll inv[100010];
ll invsum[100010];
ll memo[100010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll x[N];
    REP(i, 0, N) {
        cin >> x[i];
    }
    ll y[N - 1];
    REP(i, 0, N - 1) {
        y[i] = x[i + 1] - x[i];
    }
    fracinvfrac(N + 3);
    inv[0] = 0;
    invsum[0] = 0;
    REP(i, 0, N - 1) {
        inv[i + 1] = divide(1, i + 1);
        invsum[i + 1] = invsum[i] + inv[i + 1];
    }
    REP(i, 0, N - 1) {
        memo[i] = multiply(invsum[i + 1], frac[N - 1]);
    }
    ll ans = 0;
    REP(i, 0, N - 1) {
        ans = modadd(ans, multiply(memo[i], y[i]));
    }
    cout << ans << endl;
}


Measured memory_bytes: 9984
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
main(){
  int n;
  cin>>n>>n;
  int a[n];
  r(i,n)cin>>a[i];
  sort(a,a+n);
  int x=0,y=a[n-1];
  r(i,n-1)x+=a[i];
  cout<<max(0,y-x-1)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define loop(i,n) rep(i,0,n)
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<pair<int,int>> vp(n);
    loop(i,n){
        int a;
        cin >> a;
        vp[i]={a,i+1};
    }
    sort(vp.begin(),vp.end());
    loop(i,n){
        cout << vp[i].second << (i==n-1?"\n":" ");
    }
    return 0;
}

Measured memory_bytes: 1536
def main():
    int(input())

    d = {}
    ans = 0
    d_get = d.get
    for i, height in enumerate(input().split()):
        height = int(height)
        # 引き算のほうの i は足し算のよりも大きい。
        # 従って，このように順番に見ていく必要がある。
        got = d_get(i + height) or 0
        d[i + height] = got + 1
        ans += d_get(i - height) or 0

    return ans


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

# 大いに参考にした。
# https://kmjp.hatenablog.jp/entry/2020/05/03/1030


Measured memory_bytes: 46300
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

#define MAX_K 100000

int k;
ll a[MAX_K];

bool isOK(ll n, bool fi){
    REP(i,k){
        n = n - n % a[i];
    }
    if(fi) return n >= 2;
    else return n <= 2;
}

signed main(){
    cin >> k;
    REP(i,k){
        cin >> a[i];
    }
    ll ng = -1, ok = LINF;
    while(abs(ok - ng) > 1){
        ll mid = (ng + ok) / 2;
        if(isOK(mid, true)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    ll ans = ok;
    ng = LINF, ok = -1;
    while(abs(ok - ng) > 1){
        ll mid = (ng + ok) / 2;
        if(isOK(mid, false)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    if(ans > ok) cout << -1 << endl;
    else cout << ans << " " << ok << endl;
    return 0;
}

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

const long long int MOD = 1000000007;

long long int mpow(long long int x, int n)
{
    if(n == 0)
        return 1;

    long long int k = 1;
    while(n > 1)
    {
        if(n % 2 == 1)
        {
            k *= x;
            k %= MOD;
        }
        x *= x;
        x %= MOD;
        n /= 2;

    }
    return (k * x) % MOD;
}

int n, k;
ll memo[101010];

ll rec(int m)
{
    if(memo[m] != 0) return memo[m];

    ll ret = mpow(m, n);
    for(int i = 2; i <= m; i++)
    {
        ret = (MOD + ret - rec(m / i)) % MOD;
        //ret -= rec(m / i);
    }
    
    memo[m] = ret;
    return ret;
}

int main()
{
    cin >> n >> k;
    memo[1] = 1;
    ll res = 0;
    for(int i = k; i >= 1; i--)
    {
        res += (i * rec(k / i)) % MOD;
        res %= MOD;
    }
    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 3728
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main(void){
    // Your code here!
    int a[3], k, ans;
    for (int i = 0; i < 3; i++) cin >> a[i];
    cin >> k;
    sort(a, a + 3);
    ans = a[0] + a[1] + a[2] * pow(2, k);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>

#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define REP(i,a,n) for(int i = (a);i < (n);i++)
#define PI 3.14159265359
#define MOD 1000000007
#define chmax(a,b) if(a < b)a = b

using namespace std;

int main(){
    int a,b,c,x,y,ans = 0;
    cin >> a >> b >> c >> x >> y;
    if (a+b > 2*c) {
        int m = min(x,y);
        ans += 2*c*m;
        x -= m;
        y -= m;
    }
    if(a > 2*c){
        ans += 2*c*x;
        x = 0;
    }
    if(b > 2*c){
        ans += 2*c*y;
        y = 0;
    }
    ans += x*a+y*b;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,x,a,cnt1,cnt2;
int main(){
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++){
		cin>>a;
		if(a<x) cnt1++;
		else cnt2++;
	}
	cout<<min(cnt1,cnt2)<<endl;
	return 0;
} 

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    li = list(map(int, input().split()))

    max_n = max(li)
    max_i = li.index(max_n)

    diff = 0

    for i in range(3):
        if i == max_i:
            continue

        diff += max_n - li[i]

    if diff % 2 == 0:
        print(diff//2)
    else:
        print((diff+1)//2 + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;i++)
const ll INF=1e18;
const int inf=2e9;
const ll MOD=1000000007;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};

int main(){
    ll N,K,S;cin>>N>>K>>S;
    if(S!=1000000000){
        rep(i,K){if(i)cout<<" ";cout<<S;}
        rep(i,N-K)cout<<" "<<S+1;
        cout<<endl;
    }
    else{
        rep(i,K){if(i)cout<<" ";cout<<S;}
        rep(i,N-K)cout<<" "<<S-1;
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int s,w;cin>>s>>w;
    if(w>=s)cout<<"unsafe";
    else cout<<"safe";
    return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for(auto& i: S) cin >> i;

  vector<vector<bool>> mark(H, vector<bool>(W));
  for(auto i=0; i<H-1; ++i) for(auto j=0; j<W-1; ++j) for(auto y: {i, i+1}) for(auto x: {j, j+1}) mark[i][j] = mark[i][j] ^ (S[y][x] == '#');

  vector<vector<int>> sum(H, vector<int>(W, 1));
  for(auto i=0; i<H-1; ++i) for(auto j=0; j<W-1; ++j) {
    sum[i][j+1] += sum[i][j];
    if(mark[i][j]) sum[i][j+1] = 1;
  }
  sum[H-1].assign(W, 0);

  auto ans = max(H, W);
  for(auto j=0; j<W; ++j) {
    stack<pair<int, int>> s;
    for(auto i=0; i<H; ++i) {
      auto nex = i;
      while(!s.empty() && s.top().first >= sum[i][j]) {
        nex = s.top().second;
        ans = max(ans, (i-nex+1) * s.top().first);
        s.pop();
      }
      s.emplace(sum[i][j], nex);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 22656
n = int(input())
n+=1
a = [0]+ list(map(int, input().split( )))
al = 0
for i in range(1,n+1):
    al += abs(a[i-1]-a[i%n])

for i in range(1,n):
    al2 = al
    al2 -= abs(a[i]-a[(i+1)%n])
    al2 -= abs(a[i]-a[(i-1)%n])
    al2 += abs(a[i-1]-a[(i+1)%n])
    print(al2)


Measured memory_bytes: 66924
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
typedef long long ll;
#define rep(i,n) for(int i = 0;i<n;++i)
#define repc(bit,k,n) for (int bit = (1<<k)-1;bit < (1<<n); bit = next_combination(bit))
#define repi(itr,vec) for(auto itr = vec.begin();itr!=vec.end();++itr)
using namespace std;
using Graph = vector<vector<int> >;

/* next combination
 * usage:repc(bit,k,n)
 * */
int next_combination(int sub) {
  int x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}

/* uniq
 * usage:uniq(vec)
 * */
void uniq(vector<int> &vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return;
}

int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
  int n,m;cin>>n>>m;
  vector<vector<int> >data;
  rep(i,m){
    int a,b;cin>>a>>b;
    data.push_back({a,b});
  }
  sort(data.begin(),data.end());
  int ans = 1;
  int rem = data.back()[0];
  while(!data.empty()){
    if(data.back()[1]<=rem){
      ans++;
      rem = data.back()[0];
    }
    data.pop_back();
  }
  cout << ans<<endl;



        return 0;
}

Measured memory_bytes: 8364
import java.util.Scanner;
class Main{
    public static void main(String[] args){
	Scanner key=new Scanner(System.in);
	int a=key.nextInt();
	int b=key.nextInt();
	int c=key.nextInt();
	int min;
	min=Math.min(a+b,a+c);
	min=Math.min(min,b+c);
	System.out.println(min);
    }
}

Measured memory_bytes: 22100
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vii         vector<pair<int,int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define endl '\n'
#define int long long int
using namespace std;
bool fail = false;
vi adj[(int)2e5];
int dfs(int cur, int P){
    int cnt = 0;
    for(int child: adj[cur]){
        if(child == P)continue;
        cnt += dfs(child, cur);
    }
    if(cnt >=2)fail = true;
    return cnt == 0;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    int n;cin >> n;
    if(n == 1){
        cout << "First";
        return 0;
    }
    if(n == 2){
        cout << "Second";
        return 0;
    }
    FOR(i, n-1){
        int x, y;cin >> x >> y;
        x--, y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    FOR(i, n-1){
       if(adj[i].size() > 1){
        fail |= dfs(i, -1);
        break;
       } 
    }
    if(fail)cout << "First";
    else cout << "Second";
}




Measured memory_bytes: 8704
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>


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

  int n, t;
  std::cin >> n >> t;
  std::vector<int> vt(n);
  for (auto&& e : vt) {
    std::cin >> e;
  }
  std::int64_t sum = t;
  for (decltype(vt)::size_type i = 1; i < vt.size(); i++) {
    sum += std::min(t, vt[i] - vt[i - 1]);
  }
  std::cout << sum << std::endl;

  return EXIT_SUCCESS;
}


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

using ll = long long;

using namespace std;

int main(){
  int n;
  cin >> n;
  cin.ignore();
  int i = 0;
  int tmp;
  int cnt = 0;
  for (i = 0; i < n; i++){
    cin >> tmp;
    cin.ignore();
    if(tmp != i + 1){
      ++cnt;
    }
  }
  if(cnt <= 2){
    cout << "YES" << endl;
    return 0;
  } else {
    cout << "NO" << endl;
    return 0;
  }

}


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

int main(){
  ll n;
  scanf("%lld",&n);
  vector <Pair> v(n);
  for(auto &x : v)
	scanf("%lld%lld",&x.first,&x.second);
  
  sort(v.begin(),v.end(),[](Pair x, Pair y){
	  if(x.second <= y.second){
		  if(x.first > y.first && x.second == y.second)
			return false;
		  return true;
	  }
	  return false;
  });
  
  bool flag = true;
  ll now = 0;
 
  for(int i = 0 ; i < n; i++){
	   now += v[i].first;
	  if(now > v[i].second){
		  flag = false;
		  break ;
	  }
  }
  
  puts(flag?"Yes":"No");
  
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main(){
  int w,i=0,l;
  char c;
  string s,out,ss;
  cin>>s;
  cin>>w;
  l=s.length();
  while(i<l){
    ss=s.substr(i,1);
    c=ss[0];
    out.push_back(c);
    i+=w;
  }
  cout<<out<<endl;
  return 0;
}


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

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}




void _main() {
        string s;
        cin >> s;
        if (s == "Sunny") cout << "Cloudy";
        else if (s == "Cloudy") cout << "Rainy";
        else cout << "Sunny";
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}

Measured memory_bytes: 3556
N, K = map(int, input().split())
A = [int(n) for n in input().split()]

from collections import Counter
from operator import itemgetter


A_cnt = Counter(A)
# print(A_cnt)
# print([v for k, v in sorted(A_cnt.items(), key = itemgetter(1))[:K]])
print(N - sum([v for k, v in sorted(A_cnt.items(), key = itemgetter(1), reverse = True)[:K]])\
)

Measured memory_bytes: 39300
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr ll INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

vector<ll> sum(410);
vector<vector<ll>> dp(410, vector<ll>(410, -1));

// [l, r)
ll solve(int l, int r){
    if(0 <= dp[l][r]) return dp[l][r];
    if(r - l == 1) return dp[l][r] = 0;

    ll val = INF;
    for(int i=l+1; i<r; i++){
        // [l, r) -> [l, i) and [i, r)
        ll cost = sum[r] - sum[l];
        chmin(val, solve(l, i) + solve(i, r) + cost);
    }

    return dp[l][r] = val;
}

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

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

    cout << solve(0, n) << endl;
}

Measured memory_bytes: 1664
/*input
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

*/

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

typedef pair<int, int> pii;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  vector<int> v;
  int n, m; cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    v.emplace_back(x);
  }
  sort(v.begin(), v.end());

  vector<pii> v2;
  for (int i = 0; i < m; i++) {
    int b, c; cin >> b >> c;
    v2.emplace_back(c, b);
  }
  sort(v2.begin(), v2.end(), greater<pii>());

  int offset = 0;
  for (auto pp: v2) {
    for (int i = 0; offset < n && i < pp.second; ++i, ++offset) {
      if (pp.first < v[offset]) {
        break;
      }
      v[offset] = pp.first;
    }
  }

  long long sum = 0;
  for (auto e: v) {
    sum += e;
  }
  cout << sum;
  return 0;
}

Measured memory_bytes: 1784
h,w,a,b = map(int,input().split()) #入力
mod = 10**9+7 

#前計算　f[i] = i!
f=[1]
for i in range(h+w):
  f.append(f[i]*(i+1)%mod)

#C(n,r,p) = ( n! * r!^(p-2) * (n-r)!^(p-2) )%p
#pythonだとpow()で二分累乗法が使える
def comb(n, r, p):
  return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p

#紫点ごとに調べる
ans=0
for i in range(b, w):
  ans+= comb(h+i-a-1, i, mod) * comb(w-1-i+a-1, a-1, mod) % mod

print(ans%mod)

Measured memory_bytes: 11028
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
c=[list(map(int,input().split())) for i in range(m)]
def d(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
for i in a:
    ans=10101001010
    ch=0
    for j in range(m):
        if d(i,c[j])<ans:
            ch=j
            ans=d(i,c[j])
    print(ch+1)


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

int main(){
    int n;
    cin >> n;
    vector<tuple<string,int,int>> p(n);
    for (int i = 0; i < n; i++){
        string s;
        int num;
        cin >> s >> num;
        p[i] = make_tuple(s,-1*num,i);
    }

    sort(p.begin(),p.end());
    for (int j = 0; j < n; j++){
        cout << get<2>(p[j]) + 1 << endl;
    }

}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int a[2002][2002];
int b[2002][2002];
char s[4];
inline int f(int (*d)[2002],int sx,int sy,int ex,int ey){
	return d[ex][ey]-d[ex][sy]-d[sx][ey]+d[sx][sy];
}
int main()
{
	int i,j,n,m;
	scanf("%d%d",&n,&m);
	while(n--){
		scanf("%d%d%s",&i,&j,s);
		if(s[0]=='W')a[i%(m+m)+1][j%(m+m)+1]++;
		else b[i%(m+m)+1][j%(m+m)+1]++;
	}
	for(i=1;i<=m+m;i++)for(j=1;j<=m+m;j++){
		a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
	}
	int ans=0,cnt=0;
	for(i=1;i<=m;i++)for(j=1;j<=m;j++){
		cnt=f(a,0,0,i,j)
		+f(b,i,0,i+m,j)
		+f(a,i+m,0,m+m,j)
		+f(b,0,j,i,j+m)
		+f(a,i,j,i+m,j+m)
		+f(b,i+m,j,m+m,j+m)
		+f(a,0,j+m,i,m+m)
		+f(b,i,j+m,i+m,m+m)
		+f(a,i+m,j+m,m+m,m+m);
		ans=max(ans,cnt);
		cnt=f(b,0,0,i,j)
		+f(a,i,0,i+m,j)
		+f(b,i+m,0,m+m,j)
		+f(a,0,j,i,j+m)
		+f(b,i,j,i+m,j+m)
		+f(a,i+m,j,m+m,j+m)
		+f(b,0,j+m,i,m+m)
		+f(a,i,j+m,i+m,m+m)
		+f(b,i+m,j+m,m+m,m+m);
		ans=max(ans,cnt);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 31488
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
total = sum(A_list)
count = 0
for a in A_list:
    if a >= total * (1 / (4*M)):
        count += 1
if count >= M:
    print("Yes")
else:
    print("No")

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

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int a, b;
    cin>>a>>b;   
    int ok = 0;  
    for(int i=1; i<=1009; i++){
        if (a==(i*8)/100 and b==(i*10)/100){
            cout<<i;
            ok = 1;
            break;
        }
    }
    if (!ok){
        cout<<-1;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int ans=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='+')ans++;
		if(s[i]=='-')ans--;
	}
	cout << ans <<endl;
	return 0;	
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
  string s, t;
  cin >> s >> t;
  int sz = s.size();
  
  if (s== t){
    cout << "Yes" << endl;
    return 0;
  }
  
  int n;
  bool cont = false;
  for (int i=0; i<sz; i++){
    if(s[0] == t[i]){
      n = i;
    }
    for (int j=n; j<sz; j++){
      if (s[j-n] != t[j]){
        break;
      }
      if (j == sz-1){
        cont = true;
      }
    }
    if(cont){
      for (int j=0; j<n; j++){
        if(s[j+sz-n] != t[j]){
          break;
        }
        if (j == n-1){
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }
  
  cout << "No" << endl;
  return 0;
      
}

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

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

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

    int n, k;
    cin >> n >> k;

    bool b[10] = {false};
    rep(i, k) {
        int t;
        cin >> t;
        b[t] = true;
    }

    for (int i = n; 1; i++){
        string s = to_string(i);

        bool ok = true;

        for (int j = 0; j < s.size(); j++){
            int t = s[j]-'0';
            if(b[t]){
                ok = false;
                break;
            }
        }

        if(ok){
            cout << stoi(s) << endl;
            break;
        }
    }
}


Measured memory_bytes: 256
(let* ((n (read))
       (m (read))
       (lst (make-array (list n m) :initial-contents (loop :repeat n :collect (concatenate 'list (read-line)))))
       (ans (make-array (list n m) :initial-element 0)))
  (defun accessor (x y)
    (if (and (<= 0 x (1- n)) (<= 0 y (1- m)))
        (if (char= #\. (aref lst x y))
            (incf (aref ans x y))
            (setf (aref ans x y) #\#))))
  (loop :for y :from 0 :upto (1- m)
        :do(loop :for x :from 0 :upto (1- n) :do(if (char= #\# (aref lst x y))
                                               (loop :for p :from (1- y) :upto (1+ y)
                                                     :do(loop :for q :from (1- x) :upto (1+ x) :do(accessor q p))))))
  (loop :for x :from 0 :upto (1- n) :do(loop :for y :from 0 :upto (1- m) :do(princ (aref ans x y))) :do (format t "~%")))

Measured memory_bytes: 20832
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
string S;

int main()
{
	cin >> S;
	int cnt = 0;
	int l = S.length();
	rep(i,l/2)
	{
		if(S[i] != S[(l-1)-i]) cnt++;		
	}	
	cout << cnt << endl;
}

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

int main() {
  int n, q, t;
  string name;
  queue<pair<string, int>> Q;

  cin >> n >> q;

  for (int i = 0; i < n; i++) {
    cin >> name >> t;
    Q.push(make_pair(name, t));
  }

  pair<string, int> u;
  int elaps = 0, a;

  while (!Q.empty()) {
    u = Q.front(); Q.pop();
    a = min(u.second, q); // 処理する時間

    u.second -= a; // 残り時間の更新
    elaps += a; // 経過時間を加算

    if (u.second > 0) {
      Q.push(u); // 処理が完了していなければキューに追加
    } else {
      cout << u.first << " " << elaps << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 6348